한 장으로 정리하는 Malloc-Lab 기초 다지기

Moon·2022년 10월 31일

컴퓨터시스템(CS:APP) 9장을 바탕으로 작성하였습니다👏

학습 목표 : 동적 메모리 할당을 직접 개발하면서, 메모리, 포인터 개념에 익숙해진다.

(아래 질문에 답할 수 있다면 패스하셔도 좋습니다.👏👏)

포인터는 무엇이며, 어떤 역할을 할까요?
가상메모리란 무엇이며, 왜 만들었을까요?
시스템콜은 무엇이며, 언제 사용할까요?
sbrk/mmap 함수의 역할은 무엇인가?
데이터 세그먼트에는 어떤 데이터가 저장될까요?
메모리 할당은 어떻게 이루어질까요?
메모리 단편화는 어떤 상태이며, 왜 발생할까요?

📚참고도서📚
Computer Systems: A Programmer's Perspective, Global Edition (Paperback, 3 ed)
Chapter 9. Virtual Memory 를 보고 공부하였습니다. 한글 버전이 있긴 한데.. 개인적으로 저는 보기 힘들었습니다.. (처음에 보고 '응용이'가 뭔가 했습니다..)

포인터는 무엇이며, 어떤 역할을 할까요?
-> 포인터란, 간접 주소 지정방식을 활용하여 메모리를 효과적으로 사용하는 기술입니다. 자세한 설명은 C언어, 포인터에 적어두었습니다.

1. 가상메모리란 무엇이며, 왜 만들었을까요?

🌻등장 배경🌼 : CPU에 대한 요구가 증가함에 따라 프로세스가 느려지고, 너무 많은 프로세스들이 너무 많은 메모리를 요구하면 일부는 실행할 수 없다. 또한 메모리는 손실에 취약하다

등장 : 해결사 가상메모리(Virtual Memory, VM)는 메인 메모리의 추상화를 제공한다. 가상메모리는 각 프로세스에 통합된 사적 주소 공간을 제공한다.

가상메모리는 중요한 3가지 역할을 수행한다

캐싱 도구로서의 VM
가상메모리는 디스크에 저장된 N개의 바이트 크기의 셀 배열로 구성된다. 디스크 안의 배열 정보는 메인 메모리에 캐시된다. 캐시는 블록 단위로 분할 되며, 디스크와 메인 메모리 사이의 징검다리 역할을 한다. 분할된 블록을 가상페이지라 부르며, 3개의 중첩되지 않는 부분집합으로 나뉘어진다.

Unallocated : 아직 할당되지 않은 페이지
Cached : 현재 메인 메모리에 캐시되어 할당된 페이지
Uncached : 메인 메모리에 캐시되지 않고 할당된 페이지
모든 캐시처럼 VM는 가상페이지가 DRAM 어딘가에 캐시되어있는지 결정하기 위한 방법을 갖고 있어야 한다. 이를 위해 가상페이지를 물리페이지로 매핑하는 '페이지 테이블'이 물리 메모리에 저장된 자료구조의 조합으로 제공된다. 페이지 테이블 엔트리(PTE)는 페이지 테이블의 배열이다. 각 PTE가 한 개의 유효비트(valid), n비트의 주소 필드로 구성되었다고 가정하고, 유효비트가 세팅되었다면 주소 필드는 가상페이지가 캐시되어 대응되는 DRAM의 물리페이지의 시작을 나타낸다.

아래 예제는 8개의 가상페이지와 4개의 물리페이지로 구성되는 페이지 테이블을 보여준다. 4개의 가상페이지(VP1,VP2,VP4,VP7)는 현재 DRAM에 캐시 되어 있다.
Unallocated : VP0, VP5
Cached : VP1, VP2, VP4, VP7
Uncached : VP3, VP6!

메모리 관리를 위한 도구로서의 VM
가상메모리는 메모리 관리를 현저하게 단순화하였고, 메모리를 보호하기 위한 자연스런 방법을 제공한다. 지금까지 하나의 가상 주소공간을 물리 주소공간으로 매핑하는 한 개의 페이지 테이블을 가정하였지만, 다수의 가상페이지들이 동일한 공유된 물리 페이지에 매핑될 수 있다는 점에 주목해야한다.
(1) 링킹 단순화 : 가상 주소공간은 동일한 기본 포맷을 사용한다. 예를 들어, 코드 세그먼트는 항상 가상주소 0x400000에서 시작한다. 이러한 통일성은 링커의 설계와 구현을 단순화 해준다.
(2) 로딩 단순화 : 목적파일의 .data와 .text섹션들을 새롭게 생성된 프로세스에 로드할 때, 코드와 데이터 세그먼트를 가상의 페이지에 할당하고 이들을 무효로 표시하고(캐시되지 않은 상태) PTE를 목적파일의 해당 위치를 가리키게 한다.
(3) 공유 단순화 : 모든 C프로그램은 printf와 같은 표준 라이브러리 루틴을 호출하는데, 운영체제는 다수의 프로세스가 가상페이지들을 동일한 물리페이지들로 적절하게 매핑해서 한 개의 사본을 공유하도록 한다
(4) 메모리 할당 단순화 : run중인 프로세스가 추가적인 힙 공간을 요청할 때, 운영체제는 적당한 수의 연속적인 가상메모리 페이지를 할당하고 이들을 물리 메모리 내에 위치한 임의의 물리페이지로 매핑한다.
메모리 보호를 위한 도구로서의 VM
가상주소 공간을 제공하면 사적 메모리를 다른 프로세스로부터 분리할 수 있다. CPU가 주소를 만들 때마다 PTE를 읽기 때문에 PTE에 허가 비트를 추가해서 주소 번역 하드웨어가 가상페이지 내용으로의 접근을 제어하는 것은 간단하다.

🤔프로그래머는 가상메모리 동작 방식을 왜 이해해야할까?🤔

(1) 가상메모리는 중심이다(어떻게 시스템이 동작하는 지 이해할 수 있다)

가상메모리를 중심으로 어셈블러, 링커, 로더, 프로세스 등에서 중요한 역할을 차지한다.

(2) 가상메모리는 강력하다(내가 설계한 프로그램의 성능을 향상)

메모리 블록을 생성, 삭제, 매핑하여 다른 프로세스들과 공유할 수 있는 강력한 기능을 제공한다.

(3) 가상메모리는 위험하다(프로그램 수행 에러를 피할 수 있다)

잘못된 포인터를 갖는 프로그램은 'Segmentation fault' 등을 만나 종료되거나 죽기 전까지 수 시간 조용히 실행될 수 있다. 최악은 잘못된 결과로 프로그램이 끝까지 실행되는 것.

2. 시스템콜은 무엇이며, 언제 사용할까요?

인터럽트, 시스템콜 유튜브 영상(쉬운코드) 영상을 참고하여 작성하였습니다.

운영체제(OS)는 '커널 모드'와 '유저 모드'로 구성된다. 우리가 개발하는 프로그램은 일반적으로 유저 모드에서 실행된다. 시스템 콜은 OS가 제공하는 기능으로 커널 영역의 기능을 사용자 모드에서 사용하게 해주는 기능이다. 프로그램 실행 중에 인터럽트가 발생하거나 시스템 콜을 호출하게 되면 커널모드로 전환된다. 커널 모드는 프로그램의 현재 CPU상태를 저장하고 CPU에서 커널 코드가 실행된다. 처리가 완료되면, 중단됐던 프로그램의 CPU 상태를 복원하고 통제권을 유저 모드로 넘겨준다.커널모드는 시스템을 보호하기 위해 존재한다. 우리가 개발한 프로그램이 함부로 하드웨어를 점유하면, 문제가 발생할 수 있다.
시스템콜은 프로세스/스레드 관련 외에도 다양한 시스템콜이 존재하지만, 우리는 이번 학습에서 메모리와 관련된 시스템콜만을 다루도록 한다!

3. sbrk/mmap 함수의 역할은 무엇인가?

brk,sbrk 시스템콜은 malloc 함수와 같은 메모리 할당을 요청할 때 사용되는 시스템콜이다. malloc 함수를 실행 후 실제 메모리를 할당받기 위해선 brk, sbrk 또는 mmap 시스템콜을 수행해야한다.

함수	역할	방식	반환값
brk	데이터 세그멘트 크기 변경	brk의 인자인 addr에서 지정한 값으로 설정	성공(0), 실패(1), 에러(ENOMEM)
sbrk	데이터 세그멘트 크기 변경	데이터 세그멘트를 increment bytes만큼 증가	성공(이전 program break값), 실패(void포인터 형으로 -1), 에러(ENOMEM)
mmap	새 가상메모리 영역 요청	아래 코드 참고	성공(매핑된 메모리 주소 반환), 실패(MAP_FAILED)

#include <unistd.h>
#include <sys/mman.h>

void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);

4. 데이터 세그먼트에는 어떤 데이터가 저장될까요?

[Malloc-lab] 메모리 영역(데이터 세그먼트)를 참고하여 작성하였습니다.

프로세스는 CPU가 실행 파일에 있는 명령들을 실행할 수 있도록 OS가 실행 파일의 명령들을 읽어서 메모리에 재구성한 것이다. 프로세스는 세그먼트(여러 정보나 데이터를 기억하는 메모리 공간)의 집합으로 구성된다. (아래 그림)

코드(Code) 세그먼트

실행할 프로그램의 코드가 저장되는 영역으로 Text 영역이라고도 함
CPU는 이 영역에서 명령어를 하나씩 가져와 처리함
코드 영역은 소스코드가 저장되는 영역으로, 컴퓨터가 실행해야 할 명령어들이 순서대로 쌓이는 메모리 영역이다. 코딩한 것을 실행시키면 CPU가 알아서 코드 영역에 저장된 명령어들을 하나씩 가져가 처리하는 방식으로, 컴퓨터가 알아서 처리하기 때문에 따로 신경 쓸 필요가 없는 영역이다.

데이터(Data) 세그먼트

전역 변수(gloabl)와 정적 변수(static)가 할당되는 영역
프로그램이 시작될 때 할당되어, 프로그램이 종료하면 소멸됨
- 전역 변수(gloabl) => 함수 외부에 선언되어 있으므로 프로그램이 시작할 때 생성되고, 프로그램이 끝날 때 소멸
- 정적 변수(static)=> 선언한 위치에서 메모리가 생성되고, 프로그램이 끝날 때 소멸

스택(Stack) 세그먼트

사용자에 의해 메모리가 할당되고 해제되는 영역
필요에 의해 동적으로 메모리를 할당할 때 사용
가상 메모리 영역을 관리함
프로그램 동작 시(런타임)에 크기가 결정됨
메모리 주소값에 의해서만 참조되고 사용되는 영역
- 힙(heap) => 메모리의 낮은 주소에서 높은 주소의 방향으로 할당됨.
- 지역 변수(stack) => 메모리의 높은 주소에서 낮은 주소의 방향으로 할당

#include <stdio.h>

int x = 1;              // Data 영역
int y;                  // BSS 영역: 초기화 되지 않은 데이터(전역 변수)

int main(){
    int z;                  // Stack 영역: 지역 변수
    static int st_a;        // BSS 영역
    static int st_b = 1;    // Data 영역: static
    char* c;                // Stack 영역
    c = malloc(10);         // Heap 영역
    y = 2;                  // Code 영역
 
    return 0;
}

5. 메모리 할당은 어떻게 이루어질까요?

🤔동적 메모리 할당기가 뭔가요? 왜 사용하나요?🤔

C언어, 메모리 할당에 정답(정적 메모리 할당 등)을 대해 정리해놓았습니다. 한 번 보고 오시면 좋을 거 같습니다. 이번 게시글에서는 동적 메모리 할당 과정을 중심으로 자세히 다뤄보도록 하겠습니다.

🥘malloc과 free를 활용한 메모리 할당 맛보기🍲

아래 그림은 18워드(책에 16워드라고 나와있으나 오타입니다!)의 작은 힙을 malloc과 free를 통해 관리하는 것을 보여준다.
그림(a) : 4워드 블록을 요청하며, 이 블록의 첫 번째 워드를 가리키는 포인터를 리턴한다.
그림(b) : 5워드 블록을 요청하며, 6워드 블록을 할당하는데 이유는 이 예제가 더블 워드 경계에 정렬되도록 하기 위해 1워드가 추가 패딩된 것이다.
그림(c) : 6워드 블록을 요청하며, malloc은 가용 블록에서 6워드 블록을 할당
그림(d) : free로 호출이 리턴된 후에 포인터 p2는 여전히 malloc된 블록을 가리킨다
그림(e) : 2워드 블록을 요청하며, 이전 단계에서 반환된 블록의 부분을 할당하고, 새로운 블록의 포인터를 리턴한다

.
1. 묵시적 가용 리스트(Implicit free list)

할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 구조를 필요로 한다.
한 블록은 1워드 헤더, 데이터, 추가적인 패딩으로 구성된다.
헤더에는 블록 크기와 할당(또는 가용) 상태를 인코딩한다.
묵시적 가용 리스트는 가용 블록이 헤더 내 필드에 의해 묵시적으로 연결된다.
묵시적 가용 리스트의 장점은 단순성이나, 가용 리스트를 찾기 위해 드는 비용이 전체 할당된 블록을 탐색하는 비용과 같은 것이 단점이다.

👨‍🏭할당할 블록 배치 방법을 알아보자!👩‍🏭

어플리케이션이 블록을 요청할 때, 할당기는 요청한 블록을 저장하기에 충분한 가용 블록을 리스트에서 검색한다
할당기가 요청한 블록을 찾을 수 없다면, 커널에게 sbrk 함수를 호출해 추가적인 힙 메모리를 요청한다

이름	검색방식	장점	단점
First fit	리스트를 처음부터 검색해서 크기가 맞는 첫번째 가용 블록을 선택	리스트 마지막에 가장 큰 가용 블록을 남겨놓음	큰 블록을 찾는 경우 검색 시간 증가
Next fit	이전 검색이 종료된 지점부터 검색을 시작	First fit에 비해 빠른 속도	First fit에 비해 낮은 메모리 이용도
Best fit	모든 가용 블록을 검색 후 크기가 맞는 가장 작은 블록 선택	가장 메모리 이용도가 높음	힙을 완전히 다 검색해야함

💃가용 블록을 연결해보자🕺

할당기가 할당한 블록을 반환할 때, 새롭게 반환하는 블록에 인접한 다른 가용 블록이 있을 수 있다.
인접 가용 블록을 '연결'해놓지 않으면, 오류 단편화가 발생할 수 있다.
예를 들어, 아래 그림에서 4워드를 요청하게 되면 두 개의 가용 블록 전체의 크기는 요청을 만족시킬 정도로 충분히 크지만 실패하게 된다.
할당기는 블록이 반환될 때마다 인접 블록을 통합해서 즉시 연결을 선택할 수 있다.

🤔할당기는 어떻게 연결을 구현할까?🤔
1) 현재블록의 헤더는 다음 블록의 헤더를 가리키며, 이것이 다음 블록이 가용한지 결정하기 위해 체크한다.
2) 이전 블록과 연결하기 위해서는, (묵시적 가용 리스트의 경우) 현재 블록에 도달할 때까지 전체 리스트를 검색해서 이전 블록의 위치를 기억하면 된다
3) 이렇게 되면, free호출이 힙의 크기에 비례하는 시간을 소모할 것이라는 한계가 있다. 복잡한 가용 리스트 구조를 설계하더라도 검색 시간은 상수가 될 수 없다.

경계 태그로 연결하기
1) 경계태그를 사용하면 상수 시간 이전에 블록을 연결할 수 있다
2) 각 블록의 끝 부분에 헤더를 그대로 복사한 풋터(footer) 경계태그를 추가한다
3) 할당기는 시작 위치와 이전 블록의 상태를 자신이 풋터를 조사해 결정할 수 있으며, 이것은 항상 현재 블록의 시작 부분에서 한 워드 떨어진 곳에 위치한다
🙆아래 예시를 보면 이해가 쉽다🙆
Case1) 이전, 다음 모두 블록 할당(a)
Case2) 이전 블록 할당(a), 다음 블록 가용(f)
Case3) 이전 블록 가용(f), 다음 블록 할당(a)
Case4) 이전, 다음 모두 블록 가용(f)

.
2. 명시적 가용 리스트(Explicit free list)

블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 묵시적 가용 리스트는 범용 할당기에 적합하지 않다.
이보다 더 좋은 방법은 가용 블록들을 일종의 명시적 자료구조로 작성하는 것이다.
예를 들어, 힙은 아래 그림처럼, 각 가용 블록 내에 pred와 succ 포인터를 포함하는 이중 연결 가용리스트로 구성할 수 있다.
명시적 리스트의 단점은 가용 블록들에 모든 필요한 포인터뿐만 아니라 헤더, 풋터까지 포함해야 하기 때문에 블록이 충분히 커야한다. 결과적으로, 최소 블록 크기가 커지고 잠재적인 내부 단편화 가능성이 증가한다.

.
3. 분리 가용 리스트(Segregated free list)

할당시간을 줄이기 위해 분리저장장치(segregated storage)를 활용하여 다수의 가용 리스트를 유지하며, 각 리스트를 동일한 크기의 블록들로 저장한다
예를 들어,
1) 크기(size class)가 1인 블록, 2인 블록, ..., 2^10 집합으로 관리
2) 크기 n의 블록이 필요하다면, 적당한 가용 리스트 검색
3) 단일 크기가 맞는 블록이 없다면 다음 리스트 검색
분리저장장치를 두 가지 방법으로 나누어 볼 수 있다
- 간단한 분리 저장장치
👨‍💻과정👨‍💻 가용리스트는 각각 크기 클래스의 가장 큰 원소의 크기를 갖는다. 적절한 가용리스트를 검색하고, 리스트가 비어있지 않다면, 가용 블록은 절대 분할하지 않고 첫 번째 블록에 할당한다.
🍖장점🍖 블록을 할당하고 반환하는 것 모두 상수시간 연산(빠름), 블록 당 오버헤드가 없고 헤더와 풋터 모두 필요없다
🍆단점🍆 내부 단편화와 외부 단편화에 취약하다

- 분리 맞춤 (malloc의 방식)
👨‍💻과정👨‍💻이 방식에서 할당기는 크기 클래스와 연관된 가용리스트의 배열을 관리한다. 크기가 맞는 블록을 위해 해당 가용리스트를 first-fit방식으로 검색한다. 블록을 분할하고, 나머지를 적당한 가용리스트에 삽입한다. 만일 찾지 못하면, 다음 크기의 클래스를 위한 가용리스트를 검색한다. 어디서도 크기가 맞는 블록을 찾지 못 하면 추가적인 힙 메모리를 요청한다.
🍖장점🍖 빠르고 메모리 관리가 효율적
🍆단점🍆 검색이 전체 힙이 아니라 힙의 특정 부분에 제한된다

버디 시스템 : 각 크기 클래스가 2의 제곱인 특수한 경우의 분리 맞춤 방식
-> 블록의 주소와 크기가 주어지면 이 블록의 버디 주소를 쉽게 계산

6. 메모리 단편화는 어떤 상태이며, 왜 발생할까요?

할당기 개발자는 처리량과 메모리 이용도를 최대화하려는 성능 목표를 달성하기 위해 노력한다. 힙 이용도를 희생한다면, 처리량을 최대화하는 할당기를 작성하기는 쉬우나 이 때 단편화가 발생한다.
단편화는 가용 메모리가 할당 요청을 만족시킬 수 없을 때 발생하며, 내부 단편화와 외부단편화로 나뉜다.

1. 내부단편화