Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

이번 장에서는 가용 공간 관리를 둘러싼 이슈들에 대해 논의한다. 가용 공간 관리는 페이징을 이용해 관리하는 공간을 고정된 사이즈의 단위들로 나누면 쉬워진다. 이러한 경우, 이 고정된 사이즈의 단위들의 리스트를 가지고 클라이언트가 그것들 중 하나를 요청하면 첫 번째 엔트리를 반환하면 된다.

가용 공간 관리가 어려워지는 건 관리 중인 가용 공간이 여러 사이즈의 단위를 가지고 있을 때다. 예를 들어 유저 레벨의 메모리 할당 라이브러리를 사용하거나 OS가 세그먼테이션으로 물리 메모리를 관리한다고 해보자. 어느 경우든 외부 단편화 문제가 발생한다.

외부 단편화 (external segmentation)
가용 공간의 총합이 요청된 크기보다 큼에도 불구하고 서로 다른 크기의 작은 조각들로 조각나있어 연속적인 공간 할당의 요청이 실패하는 문제.

1. Assumptions

다음의 논의는 아래의 가정들을 가지고 이루어진다.

malloc()과 free()로 제공되는 기본적인 인터페이스를 사용

• void malloc(size_t size)
  + 프로그램에 의해 요청되는 바이트 수를 전달하기 위해 단일 파라미터 size를 사용한다.
  + 요청이 성공하면 새로 할당된 가상 주소 공간의 포인터를 반환한다.
• void free(void *ptr)
  + 포인터를 받아 그에 해당하는 공간의 할당을 해제한다.
  + 사용자는 해제되는 공간의 크기를 명시하지 않고, 라이브러리가 포인터만으로 해당 메모리 공간의 크기를 알아내야 한다.

이 라이브러리가 관리하는 공간은 heap 공간이며, 힙 안의 가용 공간을 관리하기 위해서 사용되는 일반적인 자료구조는 가용 리스트(free list) 라고 불린다. 가용 리스트는 메모리에서 관리되는 영역 내의 모든 가용 공간 청크들에 대한 참조를 포함하고 있다. 이 자료 구조는 꼭 리스트일 필요는 없으며, 가용 공간을 추적하는 기능만 할 수 있으면 된다.

외부 단편화 문제에 초점

할당자(allocator) 들은 외부 단편화를 해결하기도 해야하지만, 내부 단편화 문제도 해결해야 한다. 하지만 아래의 논의는 단순성을 위해 외부 단편화에 초점을 맞춰 이루어진다.

내부 단편화 (internal fragmentation)
할당자가 요청된 것보다 큰 메모리 청크를 주어 발생하는 메모리 낭비 문제를 내부 단편화라고 한다.

메모리 재배치가 일어나지 않음

메모리가 한 번 클라이언트에게 넘겨지고 나면 메모리의 다른 위치로 재배치시키는 일은 일어나지 않는다고 가정한다. malloc()으로 얻은 메모리는 그에 맞는 free()가 일어나기 전까지는 해당 프로그램의 소유가 되어 따로 재배치가 일어나는 일은 없고, 가용 공간 압축과 같은 일도 일어나지 않는다.

할당자는 연속적인 영역을 바이트로 관리한다.

어떤 경우 할당자는 영역이 자라도록 요청할 수도 있다. 하지만 단순화를 위해 그 영역들이 평생동안 하나의 고정된 사이즈만을 가진다고 가정한다.

2. Low-level Mechanisms

정책에 대해 알아보기 전에, 먼저 대부분의 할당자들이 사용하는 공통적인 메커니즘들을 알아보자.

Splitting and Coalescing

가용 리스트는 힙에 남아있는 가용 공간에 대해 설명하는 요소들의 집합이다. 다음과 같은 30 바이트의 힙이 있다고 해보자.

이 힙의 가용 리스트는 두 원소를 가지고 있을 것이다. 첫 번째 엔트리는 0-9의 10 바이트, 그리고 나머지는 남은 한 가용 세그먼트에 대한 것이다

10 바이트를 넘는 모든 요청들은 실패할 것이다. 왜냐하면 위 힙에는 그 사이즈에 맞는 하나의 연속적인 메모리 청크가 없기 때문이다. 요청이 정확히 10 바이트인 경우에는 당연히 성공할 것이다. 그렇다면 요청이 10 바이트보다 작은 경우에는 어떨까?

단 한 바이트의 메모리만을 요청한다고 가정해보자. 이 경우 할당자는 분할(splitting) 이라고 하는 동작을 수행할 것이다. 분할은 요청을 만족시킬 수 있는 가용 메모리 청크를 찾아 둘로 나누는 것이다. 이렇게 분리되어 만들어진 두 청크 중 하나는 호출자에게 반환되고, 나머지는 리스트에 남는다. 즉 1 바이트에 대한 요청이 만들어지면, 할당자는 가용 공간을 둘로 나눠 요청된 1 바이트는 호출자에게 반환하고 나머지 9 바이트는 그대로 가용 리스트에서 관리한다.

앞서의 30 바이트 힙을 다시 보자. 만약 중간에 할당된 공간을 할당 해제하면 어떤 일이 일어날까? 만약 단순히 해제된 가용 공간을 리스트에 넣기만 한다면 리스트는 다음과 같이 될 것이다.

하지만 가용 리스트를 이렇게 관리하면, 전체 힙이 모두 할당 해제되어 있음에도 가용 리스트는 각각 10 바이트를 가지는 세 청크로 나누어지게 된다. 사용자가 20 바이트 할당을 요청하는 경우, 리스트를 순회하더라도 사용 가능한 부분을 찾을 수 없어 실패하게 되는 것이다.

이러한 문제를 해결하기 위해서 할당자는 메모리 할당이 해제될 때 가용 공간을 통합(coalesce) 한다. 아이디어는 간단하다. 메모리가 해제되면 해제되는 영역 주변을 함께 확인해, 가용 공간이 있다면 하나의 큰 덩어리로 합병시키는 것이다. 따라서 메모리 통합이 완료되면 가용 리스트는 다음과 같이 될 것이다.

메모리 통합을 통해 할당자는 응용 프로그램이 더 큰 크기의 가용 공간을 사용하게 할 수 있다.

Tracking The Size Of Allocated Regions

free()는 사이즈에 파라미터를 사용하지 않고 주어진 포인터만을 통해 할당 해제할 영역의 크기를 결정한다. 이를 위해 대부분의 할당자들은 보통 반환되는 메모리 청크의 바로 앞에 추가 정보 비트를 담은 헤더 블럭을 덧붙인다.

헤더는 할당된 영역의 사이즈, 할당 해제 속도를 올리기 위한 추가적인 포인터들, 추가적인 무결성 확인을 위한 매직 넘버, 그 외의 다른 정보들을 포함한다. 다음과 같이 영역의 크기와 매직 넘버만을 포함한 헤더가 있다고 가정해보자.

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

만약 사용자가 free(ptr)을 호출하면 라이브러리는 다음과 같은 포인터 연산을 통해 어디서부터 헤더가 시작하는지를 알아낸다.

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

헤더의 포인터를 알아내면 라이브러리는 매직 넘버를 확인하고, 간단한 계산을 통해 할당 해제될 영역의 크기를 계산한다. 이렇게 헤더를 사용할 때 주의할 점은, 할당 해제될 영역의 크기는 사용자에게 할당된 공간의 크기에 헤더의 크기를 더한 것이라는 점이다. 그러므로 사용자가 N 바이트 메모리를 요청했을 때, 라이브러리는 단순히 N 바이트의 가용 공간을 찾는 게 아니라 N + (헤더의 크기)만큼의 가용 공간을 찾아야 한다.

Embedding A Free List

지금까지는 가용 리스트를 개념적으로만 써왔다. 그렇다면 이 가용 리스트는 실제로는 어떻게 만들 수 있을까?

4KB 메모리 청크가 있다고 하자. 이를 가용 리스트로 관리하려면 먼저 리스트를 초기화해야한다. 초기화를 할 때, 이 리스트는 사이즈가 4096인 엔트리를 하나만 가지게 될 것이다.

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;

이 코드를 실행하면, 리스트는 4088의 사이즈를 가지는 하나의 엔트리를 가진다. head 포인터는 이 엔트리가 가지는 범위의 시작 주소를 가지고 있다. 이 시작 주소는 16KB라고 하자.

여기에 100 바이트의 메모리 할당이 요청되었다고 하자. 라이브러리는 우선 이 요청을 수용할 수 있는 충분히 큰 청크를 찾아야 한다. 지금 리스트에는 하나의 엔트리 밖에 없으므로 이 것이 선택될 것이다. 그러면 청크는 둘로 나뉘게 된다. 하나는 헤더와 요청된 크기의 청크고, 나머지는 가용 청크다. 헤더의 크기가 8 바이트라고 가정한다면 결과는 다음과 같다.

100 바이트의 할당 요청에 대해, 라이브러리는 하나의 가용 청크에서 108 바이트를 분할해 할당하고 그 포인터를 반환한다. 기존에 있던 가용 청크의 헤더는 할당한 만큼 사이즈를 줄이면서 뒤로 밀려난다.

이번에는 힙에 각각 100 바이트(헤더를 포함하면 108 바이트) 씩 할당된 세 개의 영역이 있다고 해보자. 앞에서부터 총 324 바이트가 이 영역들을 위해 할당되는데, 만약 free()로 메모리 할당을 해제하면 어떤 일이 일어날까? free(16500)으로 중간의 청크를 할당 해제한다고 해보자. 힙은 가상 메모리 16KB = 16384 byte에서 시작한다. 여기에다 맨 앞의 청크의 크기(108)와 중간 청크의 헤더의 크기(8)을 더하면 사용자에게 할당된 공간의 주소 16500이 나온다.

16500에서 헤더의 크기를 빼 헤더의 위치를 찾으면 라이브러리는 해제될 영역의 사이즈를 알 수 있다. 라이브러리는 이를 가용 리스트에 헤드에 추가함으로써 해제한다. 이제 가용 리스트는 작은 청크 하나와 큰 청크 하나를 원소로 가지게 된다. 만약 현재 사용 중인 나머지 두 청크도 할당 해제하고 나인접한 청크들과 통합하면, 가용 리스트는 처음과 같이 힙 전체를 하나의 원소로 갖게 된다.

Growing The Heap

마지막으로 얘기해봐야 할 메커니즘이 있다. 힙에 공간이 부족한 경우에는 어떻게 해야할까? 가장 간단한 접근법은 그냥 요청 처리에 실패하는 것이다. 어떤 경우에는 이 접근법이 유일한 선택지가 될 수도 있다.

대부분의 전통적인 할당자는 작은 사이즈의 힙에서부터 시작해, 공간이 부족하면 OS에 더 많은 메모리를 요청한다. 즉 힙의 크기를 키우기 위해 시스템 콜을 호출하고 새로운 청크를 할당한다. sbrk 요청을 처리하기 위해 OS는 우선 가용 물리 페이지를 찾고, 이를 요청한 프로세스의 주소에 매핑한 후, 확장된 힙의 주소값을 반환한다. 요청을 처리하기 위한 힙의 확장이 가능해지는 것이다.

3. Basic Strategies

가용 공간 관리를 위한 기본적인 전략들을 살펴 보자. 이상적인 할당자는 빠르면서도 단편화를 최소화할 수 있어야 한다. 하지만 할당과 해제 요청은 프로그래머의 임의에 따라 결정되므로, 특정 전략은 다른 입력이 주어졌을 때에는 제대로 작동하지 않을 수 있다.

Best Fit

Best-fit은 가용 리스트를 탐색하면서 요청된 사이즈보다 크거나 같은 첫 번째 메모리 청크들을 찾고, 그 중 가장 작은 것 하나를 반환한다. Best-fit은 사용자의 요청을 만족시킬 수 있는 사이즈에 가장 가까운 블럭을 반환함으로써 낭비되는 공간을 줄이려고 하지만, 여기에는 비용이 있다. 깊은 고려 없이 간단한 구현은 탐색을 할 때 큰 성능상 패널티를 만들 수 있기 때문이다.

Worst Fit

Worst-fit은 best-fit과 반대로, 가장 큰 청크를 찾아 요청된 양만큼을 반환한다. 이때 분할되고 남은 것들은 가용 리스트에 남는다. Best-fit 접근법에서는 공간을 할당했을 때, 작은 가용 청크들만이 남아버릴 수 있는데, worst-fit은 큰 가용 청크를 남긴다. 다만, 이 전략은 best-fit과 마찬가지로 가용 공간 전체에 대한 탐색을 필요로 하기 때문에 마찬가지로 비용이 크다. 대부분의 연구들은 이 접근법이 성능상으로 좋지 못하다고 말한다. 단편화도 심할 뿐더러 오버헤드도 크기 때문이다.

First Fit

First-fit은 충분히 큰, 가장 첫 번째 블럭을 찾아 요청된 크기만큼을 사용자에게 반환한다. Worst-fit과 마찬가지로 남은 가용 공간은 추후의 요청들을 위해 가용 리스트에 남게 된다. First-fit은 전체 리스트를 탐색할 필요는 없다는 점에서 속도의 측면에서 이점을 가지고 있지만, 리스트의 전반부에는 작게 쪼개진 가용 청크들이 많이 생길 수 있다는 단점을 가지고 있다.

여기서는 할당자가 가용 리스트의 순서를 어떻게 관리하느냐가 중요한 이슈가 된다. 이에 대한 한 접근법은 주소-기반의 정렬을 사용하는 것이다. 리스트를 가용 공간의 주소에 따라 정렬하면 통합이 쉬워지고, 단편화도 줄어든다.

Next Fit

Next-fit은 first-fit과 달리 리스트의 맨 처음에서부터 탐색을 시작하지 않고 마지막으로 본 위치에서부터 탐색을 시작한다. 이를 위해서는 마지막으로 본 위치에 대한 추가적인 포인터가 필요하다. 이 아이디어는 가용 공간에 대한 탐색이 리스트 전체에서 좀 더 균일하게 일어나게 함으로써, 리스트의 앞쪽이 잘게 쪼개지는 것을 막는다. 성능은 first-fit과 비슷하다.

4. Other Approaches

Segregated Lists

분리 리스트(segregated list) 를 사용하는 접근법에 대해 알아보자. 기본 아이디어는 한 프로그램이 특정 크기의 할당을 자주 요청한다면, 정확히 그 사이즈를 전담하는 리스트를 만들어 사용하는 것이다. 해당 사이즈를 제외한 다른 요청들은 일반적인 메모리 할당자가 처리한다.

이 접근법이 갖는 이점은 명확하다. 특정 사이즈의 요청을 전담하는 청크를 이용함으로써 단편화에 대한 고려를 적게 해도 되고, 해당 사이즈에 한해서는 할당이나 해제 요청 또한 리스트에 대한 복잡한 탐색 없이 빠르게 이루어질 수 있다.

다만 이 접근법에서는 특별 관리할 메모리 크기를 어떻게 정할 것인지가 문제가 된다. 슬랩 할당자(slab allocator)라 알려진 할당자는 이 이슈를 훌륭하게 처리한다. 커널은 부팅 시 자주 요청될 것 같은 커널 오브젝트들을 위한 여러 개의 오브젝트 캐시(object cache)들을 만든다. 이 캐시들은 각각이 특정 사이즈의 분리 가용 리스트이며, 해당 크기의 메모리 할당 및 해제 요청을 빠르게 처리한다.

만약 주어진 사이즈의 캐시에 공간이 부족해지면, 이는 일반 메모리 할당자에 슬랩을 요청한다. 반대로 만약 주어진 슬랩의 오브젝트들에 담긴 참조의 수가 모두 0이 되면, 일반 메모리 할당자는 이들을 모두 회수한다.

슬랩 할당자는 할당 해제된 오브젝트들을 초기화된 상태로 특정 캐시 리스트에 담아두기 때문에, 오브젝트의 잦은 할당-반환의 오버헤드를 효과적으로 줄인다.

Buddy Allocation

통합은 할당자에게 있어 중요한 문제이기 때문에, 이 통합을 쉽게 만들기 위한 접근법들이 있다. 그 중 한 가지는 이진 버디 할당자(binary buddy allocator)이다.

이 시스템에서 가용 메모리는 $2^N$ 사이즈의 커다란 공간으로 생각된다. 메모리 할당 요청이 만들어지면, 가용 공간은 요청을 수용할 수 있을 만큼은 큰 블럭을 만들 때까지 재귀적으로 둘로 나누어진다.

그런데 유저가 7KB의 메모리 할당을 요청했다고 하자. 이 접근법에서는 2의 제곱수인 블럭만을 할당할 수 있기 때문에 8KB 블럭을 만들어 할당하게 될 것이므로 내부 단편화가 발생한다.

하지만 버디 할당은 블럭을 해제할 때 빛을 발한다. 8KB 블럭을 가용 리스트로 되돌릴 때, 할당자는 이 블럭의 8KB 버디가 가용 상태에 있는지를 확인하고, 만약 그렇다면 두 블럭을 16KB의 블럭 하나로 병합한다. 할당자는 이후에도 병합된 블럭의 버디를 확인하는 식으로 재귀적으로 인접한 가용 블럭들을 병합해나간다.

버디 할당이 잘 작동하는 이유는 특정 블럭의 버디를 찾는 일이 아주 쉽기 때문이다. 각 버디 블럭의 주소는 서로 하나의 비트만 다른데, 이 비트는 블럭의 버디 트리에서의 레벨에 의해 정해진다.

Other Ideas

위 접근법들은 메모리가 확장됨에 따라 리스트 탐색의 속도 또한 느려질 수 있다는 점에서, 확장성에 있어서의 한계를 가지고 있다. 보다 진보된 할당자들은 성능과 구현 단순성을 서로 교환해, 더 복잡한 자료 구조를 이용함으로써 이런 비용을 줄이려 한다.

현대의 시스템들이 여러 개의 프로세서들을 사용하고, 멀티스레드 작업을 많이 한다는 것을 생각하면, 메모리 할당자는 멀티프로세서 기반 시스템에서도 잘 작동하도록 만들어야 할 것이다.

5. Summary

이 장에서는 기초적인 메모리 할당자들 대해 논의했다. 이런 할당자들은 C 프로그램이나 그 기저에서 메모리를 관리하는 OS와 긴밀하게 연결되어있다. 좀 더 빠르고, 공간적으로 효율적이며, 확장성 있는 할당자를 만들기 위한 노력은 현대 컴퓨터 시스템에서도 계속 되고 있다.