OSTEP 17 Free Space Management

메모리에 빈 공간이 이렇게 존재한다고 해보자. 프로세스 A가 메모리 10을 차지하고 있고, 빈 공간의 전체 크기는 20이다. 하지만 각각 10으로 파편화 되어 있기 때문에 프로세스 B의 15바이트의 요청은 실패할 것이다. 이 문제를 이번 장에서 해결해보자.

1. 가정

매번 하듯 몇 가지 가정을 하고 시작하자.

malloc()과 free()에서 제공하는 것과 같은 기본 인터페이스를 가정한다.

void *malloc(size_t size)는 프로그램이 요청한 바이트 수를 나타내는 size를 받아들이고, 요청된 크기와 같거나 더 큰 영역을 가리키는 void 포인터를 반환한다.

void free(void *ptr)는 포인터를 전달받고 해당 영역을 해제한다. 메모리 공간을 해제할 때 사용자는 라이브러리에게 크기를 전달하지 않는다. 라이브러리는 포인터만으로 해제하고자 하는 메모리 영역의 크기를 파악해야 한다.

우리는 오늘 외부 단편화 방지에 초점을 둘 것이다.

외부 단편화: 위에서 본 그림처럼 메모리 공간이 여러 개의 작은 조각으로 나뉘어 메모리를 효과적으로 사용하지 못하는 상태. 내부 단편화: 할당된 메모리 영역 내에서 사용되지 않는 공간이 발생하는 것.

또, 클라이언트에게 할당된 메모리는 다른 위치로 재배치될 수 없다고 가정할 것이다. 즉 malloc()을 호출해서 힙의 일부를 할당받은 경우, 그 메모리 영역은 free()를 호출하기 전 까지 프로그램이 소유하게 되고, 다른 위치로 옮겨질 수 없다. 이 경우 메모리 압축 기법을 사용할 수 없다.

2. 저수준 기법들

우선 대부분의 할당기에서 사용되는 일반적인 기법에 대해 알아보자.

분할과 병합

빈 공간 리스트는 힙에 있는 빈 공간들의 집합이다.

이 힙의 빈 공간 리스트에는 다음과 같이 두 개의 원소가 있을 것이다.

10바이트보다 큰 요청은 모두 실패하여 NULL을 반환할 것이다. 만약 1바이트를 요청한다면 어떻게 될까? 이 경우 할당기는 분할(splitting) 이라는 작업을 수행한다. 요청을 만족시킬 수 있는 빈 청크를 찾아 이를 둘로 분할한다. 첫 번째 청크는 호출자에게 반환되고, 두 번째 청크는 리스트에 남게 된다. 위의 그림에서 1바이트 요청이 발생하고, 할당기가 리스트의 두 번째 원소를 사용하기로 했다면 다음과 같이 될 것이다.

malloc()은 20(1바이트가 할당된 영역의 주소)을 반환하고, 빈 공간의 주소는 21부터 시작하고, 길이는 9가 될 것이다. 요청이 특정 빈 청크의 크기보다 작은 경우 분할 기법을 사용한다.

분할에 동반되는 기법은 빈 공간의 병합(coalescing) 이다. 응용 프로그램이 free(10)을 호출하여 힙의 중간에 존재하는 공간을 반환하면 어떻게 될까?

이 빈 공간을 리스트에 추가하면 다음과 같은 모양이 될 것이다. 힙 전체가 비어 있지만 10바이트 길이의 청크 3개로 나누어져 있다. 사용자가 20바이트를 요청하는 경우, 단순한 리스트 탐색은 실패할 것이다.

할당기는 이런 문제를 해결하기 위하여 빈 공간을 병합한다. 메모리 청크를 반환할 때 해제되는 청크의 주소화 바로 인접한 빈 청크의 주소를 살펴보고, 새로 해제된 빈 공간이 왼쪽의 빈 청크와 바로 인접해 있다면, 하나의 더 큰 빈 청크로 병합한다. 최종적으로 길이 30짜리 원소 하나가 존재하는 모양이 될 것이다.

할당된 공간의 크기 파악

free(void *ptr) 함수는 할당된 크기를 매개변수로 받지 않는데 어떻게 정확히 해제할 수 있을까? 이 작업을 위해 할당기는 추가 정보를 헤더 블럭에 저장한다. 헤더 블럭은 메모리에 유지되며, 보통 해제된 청크 바로 직전에 위치한다.

사용자가 ptr = malloc(20); 을 호출하였다고 가정하자. 헤더는 할당된 크기 (20바이트) 를 저장해야 한다. 또, 해제 속도를 향상시키기 위한 추가의 포인터, 부가적인 무결성 검사를 제공하기 위한 매직 넘버 및 기타 정보를 저장할 수 있다.

typedef struct __header_t {
    int size;
    int magic;
} header_t;

사용자가 free(ptr); 호출을 하면 라이브러리는 헤더의 시작 위치를 파악하기 위해 포인터 연산을 한다.

void free(void *ptr) {
    header_t *hptr = (void *)ptr − sizeof(header_t);
    // rest of code
}

헤더를 가리키는 포인터를 얻어 내면, 매직 넘버가 기대하는 값과 일치하는지 안정성 검사 (sanity check)를 실시한다. assert(hptr->magic == 1234567) 헤더의 크기와 해제된 영역의 크기를 더해 총 해제된 메모리의 크기를 계산한다.

때문에, 사용자가 $N$바이트의 메모리 청크를 요청하면, 운영체제는 $N + header\_size$ 크기인 청크를 찾는다.

빈 공간 리스트 내장

이러한 리스트를 빈 공간에 어떻게 구현할 수 있을까? 4096 바이트 크기의 메모리 청크가 있다고 하자. 이를 빈 공간 리스트로 관리하기 위해 먼저 리스트를 초기화해야 한다. 처음에 리스트는 4096 - header size 항목 하나를 가지고 있다.

typedef struct __node_t {
    int size;
    struct __node_t *next;
} node_t;

빈 공간 리스트에 첫 번째 원소를 넣는 코드를 살펴보자.

// mmap()이 빈 공간의 청크에 대한 포인터를 반환
node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE,
                                MAP_ANON|MAP_PRIVATE, −1, 0);
head−>size = 4096 − sizeof(node_t);
head−>next = NULL;

이 때 100바이트 메모리 청크가 요청되면 어떻게 될까? 이 요청을 처리하기 위해 우선 충분한 크기의 청크를 찾는다. 이 청크는 이제 다음과 같이 분할된다.

헤더를 8바이트라고 가정하면 기존 하나의 빈 청크 중 108바이트를 할당하고, 할당 영역을 가리키는 포인터를 반환한다. 그리고 할당된 공간 직전 8바이트에 헤더 정보를 넣고, 남은 빈 노드를 3980(4088-108)으로 축소한다.

이런 방식으로 100바이트씩 3번 할당된 힙의 모습을 살펴보자.

힙의 시작 부분 324바이트가 할당 되어 있다. 할당 영역 중 가운데를 free()하면 어떻게 될까?

이제 빈 공간 리스트의 첫 번째 원소는 작은 빈 청크 (100바이트 크기, 리스트의 헤드가 가리킴) 이고, 두 번째 원소는 큰 빈 청크 (3764 바이트 크기) 이다. 리스트가 하나 이상의 원소를 가지게 되었고, 단편화가 발생하였다.

남은 두 개의 사용중인 청크가 해제된다고 하자. 병합이 없다면 작은 단편으로 이루어진 빈 공간 리스트가 될 것이다.

모든 메모리가 비어 있지만, 전부 조각나 있기 대문에 한 청크가 아니라 단편으로 이루어진 메모리처럼 보인다. 이를 해결하기 위해 리스트를 순회하면서 인접한 청크를 병합 하면 된다. 병합이 완료되면 힙은 전체 하나의 큰 청크가 된다.

힙의 확장

힙 공간이 부족한 경우에는 어떻게 해야 할까? 우선 실패하고 NULL을 반환하는 방법이 있다. 또, 대부분의 전통적인 할당기는 운영체제로부터 더 많은 메모리를 요청한다. 할당기는 힙을 확장하기 위하여 특정 시스템 콜 sbrk 등을 호출한다. 그런 후 확장된 영역에서 새로운 청크를 할당한다. 이 요청을 수행하기 위해 운영체제는 빈 물리 페이지를 찾아 요청 프로세스의 주소 공간에 매핑한 후 새로운 힙의 마지막 주소를 반환한다. 이제부터 더 큰 힙을 사용할 수 있게 된다.

3. 기본 전략

이상적인 할당기는 속도가 빠르고 단편화를 최소로 해야 한다. 우리는 몇 가지 기본 정책에 대해 알아 보고 각각의 장단점에 대해 논의할 것이다.

최적 적합 (Best Fit)

최적 적합 전략은 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾아서 가장 작은 크기의 청크를 반환하는 방식이다. 이는 공간의 낭비를 줄이려는 전략이지만, 항상 전체를 검색해야 하기 때문에 성능 저하를 초래할 수 있다.

최악 적합 (Worst Fit)

최악 적합은 최적 적합의 반대 방식으로, 가장 큰 빈 청크를 찾아 요청된 크기만큼 반환하고 나머지 부분은 빈 공간 리스트에 계속 유지하는 방식이다. 최악 적합은 작은 청크 대신 커다란 빈 청크를 남기려고 시도하지만, 이 또한 전체를 탐색해야 하므로 비용이 높다. 또한, 단편화 문제를 해결하지 못하고 오버헤드가 커질 수 있다.

최초 적합 (First Fit)

최초 적합은 요청보다 큰 첫 번째 블록을 찾아 반환하는 방식이다. 이 방식의 장점은 항상 전체를 탐색할 필요가 없어 빠르다는 것이다. 그러나 리스트의 시작부분에 작은 블록이 많이 생기는 문제가 있을 수 있다.

다음 적합 (Next Fit)

다음 적합은 최초 적합과 비슷하지만, 항상 리스트의 처음부터 탐색하는 대신 마지막으로 찾았던 원소를 가리키는 포인터를 유지하여 탐색을 진행하는 방식이다. 이 방법은 리스트의 첫 부분에만 단편화가 집중되는 것을 방지할 수 있다.

4. 다른 접근법

Segregated Lists

가장 먼저 알아볼 방법은 segregated list(분리된 리스트)를 사용하는 것이다. 이는 자주 요청되는 메모리 크기가 있다면 이를 위한 별도의 메모리를 계속 유지하는 방법이다. 이렇게 하면 기기의 요청에 의해 매번 할당할 필요도 없고 매번 할당할 때마다 발생하는 단편화 문제도 줄일 수 있다.

이렇게 자주 사용되는 메모리 크기를 할당하는 방법 중 slab 할당자라는 것이 있다. 이 할당자는 커널이 부팅될 때 자주 요청되는 메모리 크기를 객체 캐시로 할당한다. 그래서 해당 크기만큼 요청이 발생하면 바로바로 메모리를 할당할 수 있다. 만약 처음 만든 모든 캐시를 사용 중일 때 요청이 발생하면 일반적인 방법으로 메모리를 할당합니다. 이러한 방법을 사용하면 오버헤드가 낮아진다.

Buddy Allocation

합병을 단순화하기 위해 설계된 방식이 buddy allocation 방법이다. 우선 이 방법은 항상 여유 메모리가 $2^N$의 크기로 존재한다고 가정한다. 메모리 요청이 있을 때 이를 만족시키는 가장 작은 블록을 찾을 때까지 반으로 쪼갠다. 이를 그림으로 보면 아래와 같다.

처음에 64KB가 있었는데 8KB의 요청이 들어왔다. 그래서 64KB를 반으로 쪼갠 32KB를 또 반으로 쪼갠 16KB를 또 반으로 쪼갠 둘 중 하나에 현재 요청을 할당한다. 그런 뒤 이 공간을 해제할 때는 바로 자신과 함께 쪼개진 메모리, 즉 buddy를 찾고 사용하고 있지 않다면 바로 합병한다. 이렇게 하면 합병을 쉽게 할 수 있다.