빈 공간 관리

관리하고 있는 공간이 고정 크기 단위로 나누어져 있는 경우 빈 공간 관리는 쉽다. 그런 경우 그냥 이 고정 크기 단위의 리스트를 유지하면 된다. 클라이언트가 그 중 하나를 요청하면 첫 번째 항목을 반환하면 된다.

빈 공간 관리가 더 어렵고 흥미로운 경우는 관리하는 공간이 가변-크기 빈 공간들의 집합으로 구성되어 있는 경우이다. 이 경우는 malloc() 과 free() 에서처럼 사용자-수준 메모리-할당 라이브러리에서, 그리고 세그멘테이션으로 물리 메모리를 관리하는 운영체제에서 발생한다. 어느 경우에도 외부 단편화가 존재한다. 빈 공간의 전체 크기가 요청한 것보다 크더라도 요청한 크기만큼의 연속된 빈 공간이 존재하지 않으면 요청은 실패할 수 있다.

17.1 가정

malloc()과 free() 에서 제공하는 것과 같은 기본 인터페이스를 가정한다. 구체적으로 void *malloc (size_t size)는 응용 프로그램이 응용 프로그램이 요청 바이트수를 나타내는 변수 size를 받아들인다. 이 함수는 요청된 크기와 같거나 큰 영역을 가리키는, 타입이 없는 또는 C언어의 용어로 void 포인터를 반환한다. 대응되는 루틴 void free(void *ptr)는 포인터를 인자로 전달받고 해당 영역을 해제한다.

이 라이브러리가 관리하는 공간은 역사적으로 힙(heap)으로 불리며, 힙의 빈 공간을 관리하는 데는 일반적인 링크드리스트가 사용된다. 이 자료구조는 영역 내의 모든 빈 청크에 대한 주소를 자고 있다. 물론, 이 자료 구조는 반드시 리스트일 필요는 없고 빈 공간들을 표현할 수 있는 자료 구조면 충분하다.

또한 클라이언트에게 할당된 메모리는 다른 위치로 재배치될 수 없다고 가정한다. 예를 들어, 프로그램이 malloc()을 호출하여 힙의 일부 영역에 대한 포인터를 받으면, 그 메로리 영역은 대응하는 free()를 통하여 바나환될 때까지 프로그램이 소유하게 되고 라이브러리에 의해 다른 위치로 옮겨질 수 없다.

17.2 저수준 기법들

세부 정책에 대해 자세히 설명하기 전에 설명하기 전에 먼저 대부분의 할당기에서 사용되는 일반적인 기법에 대해 논의한다. 첫 번째로 분할(splitting) 과 병합(coalescing) 의 기초에 대해서 알아본다. 두 번째로 할당된 영역의 크기를 빠르고 상대적으로 쉽게 파악할 수 있는 방법을 설명한다. 마지막으로, 빈 공간과 사용중인 공간을 추적하기 위해 빈 공간 내에 간단한 리스트를 구현하는 방법에 대해 설명할 것이다.

분할과 병합

빈 공간 리스트는 힙에 있는 빈 공간들의 집합이다. 30바이트의 힙이 있다고 가정하자

이 힙의 빈 공간 리스트에는 2개의 원소가 있다. 하나는 첫 번째 10 바이트의 빈 세그멘트(바이트 0-9)를 설명하고 다른 하나는 나머지 빈 세그멘트(바이트 20-29)를 표현한다.

10바이트를 초과하는 모든 요청은 실패하여 NULL을 반환하고, 10바이트 보다 적은 요청에 대해서는 분할(splitting) 로 알려진 작업을 수행한다. 요청을 만족시킬 수 있는 빈 청크를 찾아 이를 둘로 분할해 첫 번째 청크는 호출자에게 반환하고, 두 번째 청크는 리스트에 남게된다. 따라서 위의 예에서 1바이트의 요청이 발생하고 할당기가 리스트의 두 번쨰 원소를 사용하여 요청을 충족시키기로 했다고 가정하자. malloc() 은 20(1바이트가 할당된 영역의 주소)을 반환하고 최종 빈 리스트는 다음과 같이 될 것이다.

이제 빈 공간이 20이 아니라 21부터 시작하고 빈 공간의 빌이가 9이다. 분할에 당연히 동반되는 기법은 빈 공간의 병합(coalescing) 이다. 응용프로그램이 free(10)을 호출하여 힙의 중간에 존재하는 공간을 반환할 때 다음과 같이 된다.

무슨 문제가 있는지 살펴보자. 힙 전체가 비어있지만 10바이트 길이의 청크 3개로 나누어져 있다. 사용자가 10바이트를 초과하는 메모리를 요청한다면 단순한 리스트 탐색은 빈 청크를 발견하지 못하고 실패를 반환한다.

이 문제는 메모리 청크가 반환될 때 빈 공간들을 병합함으로써 해결이 가능하다. 메모리 청크를 반환할 때 해제되는 청크의 주소와 바로 인접한 빈 청크의 주소를 검사해, 새로 해제된 빈 공간이 기존에 존재하는 빈 청크와 바로 인접해 있다면 하나로 병합한다. 병합 이후의 최종 리스트는 다음과 같다.

할당된 공간의 크기 파악

free(void * ptr) 인터페이스는 크기를 매개변수로 받지 않는다. 포인터가 인자로 전달되면 malloc 라이브러리는 해제되는 메모리 영역의 크기를 신속히 파악하여 그 공간을 빈 공간 리스트에 추가할 수 있다고 가정한다.

이 작업을 위해 대부분의 할당기는 추가 정보를 헤더(header) 블럭에 저장한다. 헤더 블럭은 메모리에 유지되며 보통 해제된 청크 바로 직전에 위치한다.

위의 그림에서는 ptr이 가리키는 크기 20바이트의 할당된 블럭을 검토하고 있다. 사용자는 malloc()을호출하고 그 결과를 ptr에 저장하였다고 가정하자.

헤더는 적어도 할당된 공간의 크기는 저장해야 한다. 또한 해제 속도를 향상시키기 위한 추가의 포인터, 부가적인 무결성 검사를 제공하기 위한 매직 넘버, 및 기타 정보를 저장할 수 있다. 다음과 같이 할당 영역의 크기와 매직 넘저는 저장하는 간단한 헤더를 가정하자.

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

위의 코드는 아래의 그림과 비슷하다

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

void free(void \*ptr) {
	header_t \*hptr = (header_t \*) ptr - 1;
    ...

헤더를 가리키는 포인터를 얻으면, 라이브러리는 매직 넘버가 기대하는 값과 일치하는지 비교하여 안전성 검사(sanity check) 를 실시한다. 그리고 새로 해제된 영역의 크기를 간단한 수학을 통해 계산한다(즉, 헤더의 크기를 영역 크기에 합산함). 빈 영역의 크기는 헤더 크기와 사용자에게 할당된 영역의 크기를 더한 값이다. 사용자가 N 바이트의 메모리 청크를 요청하면 라이브러리는 크기 N의 빈 청크를 찾는 것이 아니라 빈 청크의 크기 N 더하기 헤더의 크기인 청크를 탐색한다.

빈 공간 리스트 내장

새로운 노드를 위한 공간이 필요할 때 malloc()을 호출한다. 메모리 할당 라이브러리 루틴에서는 이것이 불가능하므로 빈 공간 내에 리스트를 구축해야한다.

4096바이트 크기의 메모리 청크가 있다고 하자. 즉, 힙의 크기는 4KB이다. 이를 빈 공간 리스트로 관리하기 위해서 먼저 리스트를 초기화해야 한다. 시작시에는 리스트에 4096(빼기 헤더 크기) 길이의 항목이 하나 존재한다. 이 리스트 노드의 설명은 다음과 같다.

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

힙을 초기화하고 힙에 빈 공간 리스트의 첫 번째 원소를 넣는 코드를 살펴보자. 힙은 시스템 콜 mmap()을 호출하여 얻어진 영역에 구축된다고 가정한다.

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

이 코드의 실행 후 리스트는 크기 4088의 항목 하나만을 가지게 된다. 매우 작은 힙이지만, 우리의 논의를 위해서는 충분하다. head 포인터는 이 영역의 시작 주소를 담고 있다. 영역의 시작 주소를 16KB라고 가정하자. 이때 힙의 모양은 다음과 비슷하다.

100바이트 메모리 청크가 요청되었다고 생각해 보자. 이 요청을 처리하기 위해 라이브러리는 먼저 충분한 크기의 청크를 찾는다. 4088바이트의 청크가 선택되고, 빈 영역의 크기와 헤더의 크기 더한 값을 충족시킬 수 있는 청크와 나머지 빈 청크 두개로 분할한다. 헤더의 크기를 8바이트라고 가정하면(정수형의 크기와 정수형의 매직 넘버), 이제 힙의 공간의 모습은 다음과 비슷할 것이다.

100바이트에 대한 요청이 오면 라이브러리는 기존 하나의 빈 청크 중 108바이트를 할당하고 할당 영역을 가리키는 포인터(그림의 ptr)를 반환한다. 그리고 나중에 free()에서 사용할 수 있도록 할당된 공간 직전 8바이트에 헤더 정보를 넣는다. 그런 후 하나 남은 빈 노드를 3980바이트로 축소한다.

100바이트씩(또는 헤더 포함 108바이트) 할당된 3개의 공간이 존재하는 힙은 다음과 같다.

그림에서 볼 수 있듯이 힙의 시작 부분 324바이트가 현재 할당되어 있다. 3개의 헤더와 호출 프로그램에 의해 3개의 100바이트 영역이 사용중이다. 빈 공간 리스트는 여전히 head가 가리키는 하나의 노드로 구성되어 있지만 세 번의 분할 이후 3764바이트로 축소된 모습이다. 프로그램이 free()를 통해 일부 메모리를 반환하면 어떻게 될까?

이 예제에서 응용 프로그램은 free(16500)을 호출하여 할당 영역 중 가운데 청크를 반환한다. 16500은 메모리 영역의 시작 주소 16384, 이전 메모리 청크의 크기 108, 해제되는 청크의 헤더 8바이트를 모두 더해서 나온 값이다. 그림에서 이 값은 sptr이 나타낸다.

라이브러리는 신속히 빈 공간의 크기를 파악하고, 빈 청크를 빈 공간 리스트에 삽입한다. 빈 공간 리스트의 헤드 쪽에 삽입한다고 가정하면 공간의 모양은 다음과 같다.

이제 빈 공간 리스트의 첫 번째 원소는 작은 빈 청크(100바이트 크기이며 리스트의 헤드가 가리킴)이고 두번째 원소의 큰 빈 청크(3764바이트)이다. 드디어 우리 리스트가 하나 이상의 원소를 가진다! 불행하지만 흔히 일어나는 단편화가 발생하였다.

마지막으로 마지막 2개의 사용 중인 청크가 해제된다고 하자. 이들이 병합되지 않는다면 단편화된 채로 있을것이다.

그림에서 볼 수 있듯이리스트가 병합되지 않아 문제가 생겼다. 해결책은 간단하다: 리스트를 순회하면서 인접한 청크를 병합하면 된다. 병합이 완료되면 힙은 전체 하나의 큰 청크가 된다.

힙의 확장

힙의 공간이 부족한 경우에는 보통 NULL을 반환하지만 이 방법은 한계가 있다. 대부분의 전통적인 할당기는 적은 크기의 힙으로 시작하여 모두 소진하면 운영체제로부터 더 많은 메모리를 요청한다. 할당기는 힙을 확장하기 위하여 특정 시스템 콜(예, 대부분의 Unix 시스템에서는 sbrk)을 호출한다. 그런 후 확장된 영역에서 새로운 청크를 할당한다. sbrk 요청을 수행하기 위해 운영체제는 빈 물리 페이지를 찾아 요청 프로세스의 주소 공간에 매핑한 후, 새로운 힙의 마지막 주소를 반환한다. 이제부터 더 큰 힙을 사용할 수 있고 요청은 성공적으로 충족될 수 있다.

17.3 기본 전략

빈 공간 할당을 위한 기본 전략에 대해 살펴보자. 이상적인 할당기는 속도가 빠르고 단편화를 최소로 해야 한다. 불행하게도 할당과 해제 요청 스트림은 무작위, 결국 프로그래머에 의해 결정되기 때문에, 어느 특정 전략도 잘 맞지 않는 입력을 만나면 성능이 매우 좋지 않을 수 있다. 우리는 최선의 정책을 설명하는 것이 아니라 몇 가지 기본 정책에 대해 이야기하고 각각의 장점과 단점을 논의한다.

최적 적합(Best Fit)

먼저 빈 공간 리스트를 검색하여 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾는다. 그 후, 후보자 그룹 중에서 가장 작은 크기의 청크를 반환한다. 이 청크는 최적 청크라고 불린다. 최소 적합이라고도 불릴 수 있다. 빈 공간 리스트를 한번만 순회하면 반환할 정확한 블럭을 찾을 수 있다.

최적 적합의 배경은 간단하다. 사용자가 요청한 크기에 가까운 블럭을 반환함으로써 최적 적합은 공간의 낭비를 줄이려고 노력한다. 그러나 이에는 비용이 수반된다. 정교하지 않은 구현은 해당 빈 블럭을 찾기 위해 항상 전체를 검색해야 하기 때문에 엄청난 성능 저하를 초래한다.

최악 적합(Worst Fit)

최악 적합은 최적 적합의 반대 방식이다. 가장 큰 빈 청크를 찾아 요청된 크기 만큼만 반환하고 남는 부분은 빈 공간 리스트에 계속 유지한다. 최악 적합의 목적은 최적 적합방식에서 발생될 수 있는 작은 청크들을 방지하는 것이다. 그러나, 한번 항상 빈 공간 리스트 전체를 탐색해야 하는 오버헤드가 존재한다.

최초 적합(First Fit)

최초 적합은 간단하게 요청보다 큰 첫 번째 블럭을 찾아서 요청만큼 반환한다. 먼저와 같이 남은 빈 공간은 후속 요청을 위해 계속 유지된다.

최초 적합은 속도가 빠르다는 것이 장점이다. 원하는 블럭을 찾기 위해 항상 빈 공간 리스트 전체를 탐색할 필요가 없다. 그러나 때때로 리스트의 시작에 크기가 작은 객체가 많이 생길 수 있다. 따라서 할당기가 빈 공간 리스트의 순서를 관리하는 방법이 쟁점이다. 한 가지 방법은 주소-기반 정렬(address-based ordering) 을 사용하는 것이다. 리스트를 주소로 정렬하여 병합을 쉽게 하고, 단편화로 감소시킨다.

다음 적합(Next Fit)

항상 리스트의 처음부터 탐색하는 대신 다음 적합 알고리즘은 마지막으로 찾았던 원소를 가리키는 추가의 포인터를 유지한다. 아이디어는 빈 공간 탐색을 리스트 전체에 더 균등하게 분산시키는 것이다. 리스트의 첫 부분에만 단편이 집중적으로 발생하는 것을 방지한다. 이러한 접근 방식은 전체 탐색을 하지 않기 때문에 최초 적합의성능과 비슷하다.

17.4 다른 접근법

메모리 할당을 향상시키기 위한 기술과 알고리즘 몇가지를 알아보자.

개별 리스트

특정 응용프로그램이 한 두개 자주 요청하는 크기가 있다면, 그 크기의 객체를 관리하기 위한 별도의 리스트를 유지하는 방법이 있는데 이를 개별 리스트(segregated list) 라고 한다. 다른 모든 요청은 더 일반적인 메모리 할당기에 전달된다.

이 방법은 특정 크기의 요청을 위한 메모리 청크를 유지함으로써 단편화 가능성을 상당히 줄일 수 있다. 요청된 크기의 청크만이 존재하기 때문에 복잡한 리스트 검색이 필요하지 않으므로 할당과 해제 요청을 신속히 처리할 수 있다.

이 경우, 지정된 크기의 메모리 풀과 일반적인 풀에 얼마만큼의 메모리를 할당해야 하는지에 대한 문제는 특수목적 할당기인 슬랩 할당기(slab allocator) 로 해결한다.

커널이 부팅될 떄 커널 객체를 위한 여러 객체 캐시(object cache) 를 할당한다. 커널 객체란 락, 파일 시스템 아이노드 등 자주 요청되는 자료구조들을 일컫는다. 객체 캐시는 지정된 크기의 객체들로 구성된 빈 공간 리스트이고 메모리 할당 및 해제 요청을 빠르게 서비스 하기 위해 사용된다. 아이노드들로 구성된 객체 캐시가 있고, 락 구조만을 담고있는 객체캐시도 있다. 기존에 할당된 캐시 공간이 부족하면 상위 메모리 할당기에게 추가 슬랩을 요청한다. 요청의 전체 크기는 페이지 크기의 정수배이다. 반대로, 슬랩 내 객체들에 대한 참조 횟수가 0이 되면 상위 메모리 할당기는 이 슬랩을 회수할 수 있다. VM시스템이 더 많은 메모리를 필요로 할 떄 실제 회수가 일어난다.

슬랩 할당 방식은 빈 객체들을 사전에 초기화된 상태로 유지한다는 점에서 개별 리스트 방식보다 우수하다. Bonwick은 자료 구조의 초기화와 반납에는 많은 시간이 소요된다는 것을 발견하였다. 반납된 객체들을 초기화된 상태로 리스트에 유지하여 슬랩 할당기는 객체당 잦은 초기화와 반납의 작업을 피할 수 있어서 오버헤드를 현저히 감소시킨다.

버디 할당

빈 공간의 합병은 할당기의 매우 중요한 기능이기 때문에 합병을 간단히 하는 방법들이 설계되었다. 하나의 좋은 예가 이진 버디 할당기(binary buddy allocator) 이다. 빈 메모리는 처음에 크기 2N인 하나의 큰 공간이다. 메모리 요청이 발생하면, 요청을 충족시키기에 충분한 공간이 발견될 때까지(그리고 더 분할하면 공간이 너무 작아져서 요청을 만족시킬 수 없을 때까지) 빈 공간을 2개로 계속 분할한다. 이 시점에서 요청된 블럭이 사용자에게 반환된다. 다음 그림은 64KB 빈 공간을 분할해 7KB 블럭을 할당하는 예이다.

이 그림에서 가장 왼쪽의 8KB 블럭이 할당되고 사용자에게 반환된다. 이 방식은 2의 거듭제곱 크기 만큼의 블럭만 할당할 수 있기 때문에 내부 단편화로 고생할 수 있다.

버디 할당기의 아름다움은 블럭이 해제될 때 있다. 8KB 블럭은 빈 공간 리스트에 반환하면 할당기는 "버디" 8KB가 비어 있는지 확인한다. 비어 있다면 두 블럭을 병합하여 16KB로 만든다. 할당기는 다음 16KB의 버디가 비어 있는지 확인한다. 비어 있다면 이 두 블럭을 다시 병합한다. 이 재귀 합병은 트리를 따라 전체 빈 공간이 복원되거나 버디가 사용 중이라는 것이 밝혀질 때 까지 계속 올라간다.

버디 할당이 잘 작동하는 이유는 특정 블럭의 버디를 결정하는 것이 쉽다는 데 있다. 앞에서 빈 공간에 존재하는 블럭의 주소를 한번 생각해 보자. 각 버디 쌍의 주소는 오직 한 비트만 다르다. 어느 위치의 비트가 다른가는 버디 트리의 수준에 따라 달라진다.

기타 아이디어

앞에서 설명한 접근 방식들의 한 가지 문제점은 확장성이다. 빈 공간들의 개수가 늘어남에 따라 리스트 검색이 매우 느려질 수 있다. 좀 더 정교한 할당기는 복잡한 자료구조를 사용하여 이 비용을 줄인다. 균형 이진 트리(balanced binary tree), 스플레이 트리(splay tree), 또는 부분 정렬 트리(partially ordered tree)가 좋은 예이다.