이전 글에서 메모리 가상화와 관련된 기본적인 내용들을 알아봤다. Internal Fragmentation 문제는 Segmentation으로 해결할 수 있었지만, Segmentation으로 인해 또다른 문제인 External Fragmentation 문제를 맞닥뜨리게 되었다.
이번 글에서는 External Fragmentation 문제를 최소화할 수 있는 여러 방법들에 대해 알아보도록 하자.
1. Low-Level Mechanisms
먼저 Low-Level 관점에서 메모리 관리 기법들을 알아보자.
위의 그림과 같이 10~20KB는 프로세스에 할당되어 있고, 0~10KB, 20~30KB이 비어 있는 Heap 공간을 가정하자.
빈 공간은 Linked List로 관리되는데, 예시와 같이 각 노드는 사용 가능한 메모리의 시작 주소와, 그 크기를 담고 있다. 현재는 11KB 이상의 주소 공간을 필요로 하는 프로세스가 있다면, External Fragmentation이 발생하게 될 것이다.
1) Splitting
만약 10KB 크기의 메모리를 할당해야 하는 경우, 단순히 addr 0 노드를 삭제하면 되겠지만, 만약 그보다 더 작은 크기의 메모리를 할당해야 하는 경우는 어떻게 해야 할까? 이렇듯 메모리 할당을 진행하는 경우 Splitting이라는 방법이 사용된다.
Splitting은 메모리 할당 요청을 충족할 수 있는 빈 메모리 청크를 찾아 이를 두 개로 분할하는 방법이다. 새로운 프로세스에 1KB를 할당하는 예시를 살펴보자.
두 번째 노드의 addr이 21로 변하고, len이 9로 변했다. 이는 기존 addr 20 위치의 빈 메모리 청크를 쪼개서, 20KB ~ 21KB 크기의 메모리를 새로운 프로세스에 할당한 것이다.
2) Coalescing
그렇다면 사용자가 요청한 메모리 크기가 빈 청크의 크기보다 클 경우에는 어떻게 해야할까? 이 때 Coalescing(병합) 방법을 사용할 수 있다.
위의 그림을 살펴보면, 기존에는 빈 메모리 청크가 3개의 노드에 분리되어 기록되어 있기 때문에, 10KB 이상의 메모리는 할당할 수 없는, External Fragmentation 문제가 발생하게 된다.
이를 해결하기 위해 운영체제는 이어진 빈 공간을 병합할 수 있는데, 그 결과 addr이 0, len이 30인, 통합된 메모리 공간이 생성되었음을 볼 수 있다. 현재 예시에서 빈 메모리 공간의 크기는 30KB이기에 이보다 더 큰 메모리 할당은 진행할 수 없지만, 적어도 External Fragmentation로 인한 문제는 최소화할 수 있게 되었다.
2. Tracking The Size Of Allocated Regions
C 언어를 공부했다면, malloc(size_t size), free (void *ptr) 함수를 알고 있을 것이다. malloc(size_t size) 함수는 프로세스가 요청한 바이트 수를 나타내는 size를 인자로 받지만, free (void *ptr) 함수는 메모리의 시작 주소인 ptr 만을 인자로 받고 있다. 그렇다면 free (void *ptr) 호출할 시, 해제할 메모리의 크기는 어떻게 알 수 있는 것일까? Free List를 통해 메모리를 할당하고 해제하는 과정을 보다 자세히 살펴보자.
ptr = malloc(20);과 같이 20 바이트의 메모리를 할당하면, 대부분의 메모리 할당기는 메모리 블록에 헤더(header) 정보를 추가한다.
위의 그림과 같이, 헤더 블락은 size와 magic으로 구성되어 있다. size는 할당된 메모리의 크기를 나타내는 것임을 쉽게 알 수 있지만, magic은 무엇일까? magic은 무결성 검사(Integrity Check)를 위해 사용되는데, magic number의 손상 여부에 따라, 메모리 영역이 의도치 않게 변조되거나 손상되었는지 확인할 수 있게 된다.
typedef struct __header_t {
int size;
int magic;
} header_t;위는 간단한 실제 헤더의 예시이다. 따라서 Free list에서 여유가 있는 빈 공간을 찾을 때, 할당하려는 메모리의 크기에 더해, 헤더를 위한 공간까지 포함할 수 있는 노드를 탐색해야 한다.
3. Free List 구현
이제 구체적으로 Free List를 구현하는 내용에 대해 살펴보자.
typedef struct __node_t {
int size;
struct __node_t *next;
} nodet_t;위와 같이 Free list의 노드를 정의할 때, malloc의 호출은 아래와 같이 이루어진다.
// mmap() returns a pointer to a chunk of free space
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; 위는 mmap 호출을 통해 Free List의 첫 번째 노드를 초기화하는 예시이다. 위의 예시에서 mmap은 4096B 크기의 메모리 블록을 할당하고, 해당 블록에 대한 포인터를 반환한다. head->size는 첫 번째 메모리 블록의 크기를 나타내는데, 여기서 sizeof(node_t)만큼의 공간은 Free List의 헤더를 저장하는 데 사용되기에 실제로 할당 가능한 공간은 4096 - sizeof(node_t) 바이트이다.
결과적으로, 위와 같이 4088(4096-8)B 크기의 메모리가 Free List에 할당된 것을 볼 수 있다. 이 때 헤더의 위치는 16KB라고 하자. 프로세스가 100B 만큼의 공간을 요청한다면, 운영체제는 Free list의 head node부터 (100+8)B 이상의 빈 공간을 탐색하게 된다.
Free List를 초기화 한 직후에 100B를 할당하는 상황이므로, 4088만큼의 빈 공간을 가지고 있는 head node를 108KB 기준으로 Splitting하게 된다. 그 결과 위의 그림과 같이 노드의 size가 3980로 줄어들고, 16KB + 108B의 위치로 head가 이동하게 된다.
위는 같은 크기의 메모리 할당을 2번 더 진행한 예시이다. 이제 메모리 해제를 수행해보자.
메모리 해제의 결과, Free List에 두 개의 Free 노드가 생겨, External Fragmentation이 발생한 것을 볼 수 있다. 현재는 한 번 시스템으로부터 메모리를 할당받으면, 임의로 그 위치가 변하지 않는다고 가정하고 있다. 따라서 현재의 Fragmentation 문제는 Coalescing으로 해결할 수 없다.
그렇다면 첫 번째 메모리와 세 번째 메모리도 해제한 경우를 생각해보자.
Free 메모리가 연속적으로 배치되었기 때문에, Coalescing을 통해 External Fragmentation 문제를 해결할 수 있게 되었다. 각 Fragment들을 합쳐 초기 상태와 같이 16KB 크기의 메모리 공간으로 만들어 줄 수 있다.
만약 가용한 Free List가 아예 없는 경우, 시스템은 메모리가 부족하다고 응답하거나, Heap에 더 큰 공간을 할당할 수 있다. 대부분의 Memory Allocator(할당기)는 작은 크기의 힙에서 시작한 후, 메모리가 부족해지면 운영체제로부터 더 많은 메모리를 요청하는 방식으로 동작한다.
예를 들어, 대부분의 UNIX 시스템에서는 sbrk() 또는 brk()와 같은 시스템 콜을 통해 추가 메모리를 요청하여 힙을 확장하고, 부족한 메모리를 동적으로 확보한다.
4. Basic Strategies
위의 예시에서는 단순히 가장 먼저 찾는 충분한 노드 공간을 Splitting하는 방식으로 메모리 할당을 진행하였는데, 이를 포함한 기본적인 노드 공간 선택 기법을 알아보자.
1) Best Fit
요청 크기보다 크거나 같은 Free Chunk 중에서 가장 작은 (최대한 딱 맞는) Chunk를 선택하여 할당한 후, 남은 메모리는 Free List에 유지한다.
이 방식은 메모리 공간의 효율적 사용을 목표로 하지만, 작은 Chunk들을 많이 남겨 External Fragmentation을 유발할 수 있다. 또한, 모든 빈 공간 노드를 조회해봐야 한다는 측면에서 오버헤드가 발생한다.
2) Worst Fit
Best Fit과는 반대로, 가장 큰 (여유 있는) Free Chunk를 찾아 요청된 메모리 크기만큼 할당한 후, 남은 메모리는 Free List에 유지한다.
큰 Chunk를 할당하므로 남은 메모리 조각이 여전히 크고 유용할 가능성이 높지만, 공간이 비효율적으로 사용돨 수 있다.
3) First Fit
요청된 크기와 같거나 큰 첫 번째 Free Chunk를 선택하여 할당하고, 할당 후 남은 메모리는 Free List에 남긴다.
이 방식은 검색 속도가 빠르지만, 메모리 앞부분에 작은 Chunk들이 남아 Fragmentation을 초래할 수 있다.
4) Next Fit
First Fit과 유사하지만, 할당 요청 시 리스트의 시작부터 검색하지 않고, 마지막으로 검색이 끝난 위치부터 검색을 시작한다.
이렇게 하면 Free List의 특정 구간이 반복적으로 검색되는 것을 피할 수 있지만, 검색 효율이 떨어질 수 있다.
5. Other Approaches
1) Segregated List
Segregated List는 메모리 할당을 더 효율적으로 관리하기 위한 방법으로, 크기별로 메모리 블록들을 나누어 관리하는 기법이다.
이는 주로 Slab Allocator라는 방식으로 구현되며, 동일한 크기의 객체들을 위한 캐시(슬랩)를 미리 만들어두고, 객체가 자주 요청되는 경우 해당 캐시에서 빠르게 할당하는 방식으로 동작한다.
특정 캐시가 여유 공간이 부족해지면, 보다 일반적인 Memory Allocator로부터 새로운 메모리를 요청하여 캐시를 확장한다.
2) Buddy Allocation
Buddy Allocation은 메모리 공간을 이진수 기반으로 나누는 방식이다. Allocator는 최소한의 크기로 요청을 수용할 수 있는 메모리 블록을 찾기 위해, 메모리를 2의 제곱 크기로 계속 나눈다.
위는 7KB의 크기의 메모리를 할당하는 예시이다. 이 경우 2의 제곱 단위로 메모리를 나누다가, 7KB를 수용할 수 있는 최소 크기인 8KB가 되었을 때 해당 크기의 메모리를 할당한다.
위의 경우에서 볼 수 있듯이, 정확히 2의 제곱 단위 크기의 메모리를 할당하는 것이 아닌 이상 Buddy Allocation은 Internal Fragmentation 문제가 발생한다.
하지만, Buddy Allocation의 장점은 Coalescing에 있다. 할당된 메모리가 해제되면, 해당 블록의 버디(바로 연결되어 있는 같은 크기의 메모리 Chunk)의 할당 여부를 판단하고, 해당 Chunk가 사용되지 않고 있다면 즉시 병합을 진행할 수 있기 때문이다.
마치며
이번 글에서는 Fragment를 최소화한다는 목적과 함께 Free Space를 관리하는 여러 기법에 대해 알아봤다. 현재까지 내용의 흐름을 정리해보자.
-
운영체제가 각 프로세스를 독립적으로 관리하기 위해, 각 프로세스에게 물리 메모리를 할당하여 독립적인 가상 주소 공간을 가질 수 있도록 했다.
-
이 때 메모리를 고정된 크기로 할당할 경우, 실제로 사용하지 않는 여분의 공간이 남게 되는 Internal Fragmentation가 발생하였다.
-
메모리 공간을 Segment 형태로 관리하며, Internal Fragmentation 문제를 해결하였다. 하지만 그 결과, External Fragmentation이라는 또다른 문제가 발생하게 되었다.
-
이번 글에서 External Fragmentation를 완화할 수 있는 여러 기법들에 대해 알아봤다.
따라서 이번 글에서 소개된 기법들을 사용하더라도, External Fragmentation 문제는 여전히 발생한다. 이러한 문제를 기억하며, 다음 글부터는 Paging에 대해 알아보도록 하자!
