[OS] 메모리를 가변크기로 할당하여 사용할 때 여유 공간 관리방법 (Free Space Management) - OS 공부 11

안녕하세요 Pingu입니다!

 

저번 글에서는 메모리 가상화를 위한 주소 변환 방법 중 Segmentation을 사용하는 방법을 알아봤었는데요, segmentation은 메모리를 가변 크기로 할당하여 사용하는 방법으로 이를 사용하면 고려해야 하는 문제 중 메모리의 여유 공간을 어떻게 관리할지에 대한 문제와 external fragmentation(외부 단편화)문제가 있었습니다. 그래서 이번 글에서는 여유 공간 관리 방법과 단편화 문제에 대해 알아보려고 합니다. 제가 공부할 때 참고하고 있는 OSTEP 책에서는 Chapter 17 - Free Space Management 부분입니다!

Free-Space Management

이번 글에서는 아까 말한 대로 메모리의 여유 공관 관리와 메모리 공간의 관리 시스템에 대해 알아보려고 합니다. 우선 지금까지 배운 내용인 malloc()과 segmentation 기법은 메모리를 가변 크기로 할당합니다. 사실 다음 글에서 알아볼 Paging 기법을 사용하여 고정 크기로 할당하면 여유 공간을 관리하는 것이 더 쉬울 수 있습니다. 하지만 아직까지는 가변 크기로 할당하는 것만 배웠고 여기서 발생하는 문제에 대해 알아보려고 합니다. 우선 가변 크기로 할당하면 external fragmentation(외부 단편화)라는 문제가 발생합니다. 이는 뒤에서 자세하게 알아보겠지만 간단하게 말하면...

위의 그림과 같이 16KB 크기의 메모리가 존재하고 프로세스 A, B가 메모리를 사용 중이라고 가정하겠습니다. 현재 남은 여유 공간은 7KB죠?  그런데 6KB 크기의 메모리를 필요로 하는 프로세스 C가 실행되고 싶고 공간도 있지만 실행되지 못하는 위와 같은 경우를 외부 단편화라고 합니다. 

 

외부 단편화가 있으니 내부 단편화도 있겠죠? 이것 역시 나중에 알아볼 것이지만 간단히만 말하면 고정 크기로 할당하는 Paging기법에서 할당을 4KB 단위로 한다고 생각해보겠습니다. 어떤 프로세스가 1KB만 필요한데도 불구하고 4KB를 할당해주는 것이죠. 즉 3KB만큼 낭비가 발생하고 이렇게 낭비가 발생하는 것을 내부 단편화라고 합니다.

 

이번 글에서는 이러한 문제들을 어떻게 하면 최소화할 수 있을지에 대해 알아보겠습니다.

Assumptions

이번 글에서 여유 공간 관리를 설명하기 위해 몇 가지 가정을 세워보겠습니다. 물론 가정들은 언제나 그랬듯 차츰 없애볼 것입니다.

 

malloc(), free()를 기억하시나요? malloc()은 매개변수의 값만큼 메모리를 할당하고 free()는 포인터를 매개변수로 받아 해당 포인터의 메모리를 해제했습니다. 여기서 free()를 사용할 땐 포인터만 전달하는데도 메모리가 해제됩니다. 즉 라이브러리가 포인터의 메모리 할당 크기를 알 수 있는 방법이 있는 것이죠. 이에 대해서는 나중에 알아보도록 하고, 우선 이 두 함수는 Heap이라는 메모리 공간을 관리합니다. Heap은 여유 공간이며 필요할 때마다 할당을 해주며 사용합니다. 

 

이번 글에서는 아까 알아본 외부, 내부 단편화에서 외부 단편화에 중점을 둬서 설명할 예정입니다. 그리고 메모리가 클라이언트에게 할당되면 메모리의 다른 위치로 재배치할 수 없다는 가정을 하나 세우겠습니다. 마지막으로 메모리를 할당할 때 연속적인 공간을 할당하며 한 번 할당된 메모리의 크기는 변하지 않는다고 가정하겠습니다.

 

방금 정의한 가정들을 정리하면 다음과 같습니다.

1. 외부 단편화에 대해 중점적으로 보겠습니다.
2. 메모리는 할당되면 다른 위치로 재배치되지 않습니다.
3. 메모리를 할당할 땐 연속적인 공간을 할당하며 할당된 메모리의 크기는 변하지 않습니다.

Low-level Mechanisms

우선 메모리 관리에 대해 알아보기 전에 메모리를 할당해주는 allocator(할당자)에서 사용되는 몇 가지 메커니즘을 살펴보겠습니다. 먼저 대부분의 할당자에서 일반적인 기술인 분할, 병합에 대해서 알아보겠습니다. 그런 뒤 할당된 영역의 크기를 빠르고 쉽게 추적할 수 있는 방법을 알아보겠습니다. 마지막으로 여유 공간 안에 간단한 리스트를 만들어서 어디가 여유 공간인지 추적하는 방법에 대해 알아보겠습니다!

 

Splitting and Coalescing (분할과 병합)

아까 여유 공간이 어디인지 저장하는 리스트를 하나 만든다고 했었죠? 그 리스트의 존재를 기억하며 다음 예를 보겠습니다.

 

위의 그림은 30바이트 크기의 Heap입니다. 위의 heap에는 여유 공간이 2개 있습니다. 0~10, 20~30이 여유 공간입니다. 아까 세운 가정 때문에 10바이트 보다 큰 요청은 할 수 없습니다. 잠깐 그림으로 보면 아래와 같이 여유공간을 나타내는 리스트가 있습니다.

그렇다면 10바이트 보다 작은 1바이트 요청은 어떨까요? 이러한 경우 할당자는 메모리를 splitting(분할)합니다. 여기선 20~30을 분할한다고 가정해보겠습니다. 20~20을 사용한다고 하고 이 부분을 할당해주기로 하고 malloc()을 호출합니다. 

그럼 위와 같이 여유 공간 리스트가 변경될 거예요. 그럼 이제 메모리의 모든 부분을 해제해보겠습니다.

위와 같이 나타나겠죠? 근데 여기서 만약 20바이트의 요청이 오면 어떻게 될까요? 머리가 좋은 여러분은 두 개 합쳐서 주면 되겠네!라고 생각하시겠지만 컴퓨터는 위와 같이 여유 공간 리스트가 존재하면 10바이트 이하의 요청만 처리 가능합니다. 따라서 위와 같은 메모리는 0~30으로 한 번에 나타내야지 방금 문제를 해결할 수 있습니다. 여기서 할당자는 coalescing(병합)을 사용합니다.

위와 같이 메모리를 병합한 결과를 볼 수 있습니다. 그리고 이건 heap의 최초 모습이기도 합니다.

Tracking The Size Of Allocated Regions

아까 free()는 얼마의 메모리를 해제할지 알려주지 않는다고 했었죠? 그럼 포인터만 가지고 어떻게 이를 정확한 크기만큼 해제할 수 있는지 알아보겠습니다. 이를 수행하기 위해 할당자는 메모리에 보관되는 공간에서 가장 위에 존재하는 header 블록에 정보를 추가합니다.

위의 그림처럼 ptr(포인터)이 20 바이트 크기가 할당된 블록을 가리킨다고 예를 들어보겠습니다. 이때 header에는 할당된 영역의 크기가 저장되는 것이죠. 물론 이 때 무결성 검사를 위한 매직넘버 및 다른 정보들도 저장할 수 있습니다. 여기서 매직넘버란 어떠한 정보를 저장하기 전에 채워두는 값 정도로 생각하면 됩니다. 그럼 매직넘버가 함께 저장된 예를 볼까요?

위처럼 header에 size와 함께 매직 넘버라는 정보가 함께 저장되었습니다. 이러한 메모리를 해제하기 위해 free(ptr)을 호출하면 free는 간단한 포인터 연산을 사용하여 헤더의 시작 지점을 찾아냅니다. 그런 뒤 헤더의 크기와 헤더에 저장되어있던 할당된 크기만큼의 메모리를 해제합니다.

Embedding A Free List

지금까지는 여유공간의 위치를 저장하는 리스트를 그냥 존재한다고 생각했는데, 이젠 어떻게 존재하는지에 대해 알아보겠습니다.

 

4KB짜리 heap이 있으며 가상 메모리의 주소가 16KB부터 시작한다고 가정해보겠습니다. 이는 처음에는 여유 공간이기 때문에 리스트에 추가해줘야 합니다. 리스트의 처음에는 4KB(헤더 크기 제외)라는 정보가 하나 있어야겠죠? 그럼 이제 이렇게 heap을 초기화하고 heap에 여유 공간 리스트의 첫 번째 요소를 넣는 코드를 살펴보겠습니다. system call인 mmap()에 의해 heap이 할당되었다고 가정하겠습니다.

// 여유 공간에 대한 정보를 저장할 node 구조체
typedef struct __node_t {
    int               size;
    struct __node_t  *next;
} node_t;

// mmap()
node_t *head = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MMAP_ANON | MAP_PRIVATE, -1, 0);
// 4KB에서 여유 공간 정보 구조체의 메모리만큼 뺀 것이 사이즈
head -> size = 4096 - sizeof(node_t);
// 아직 다음 메모리가 없으니 NULL
head -> next = NULL;

우선 4096의 크기를 할당했지만 여유 공간을 저장할 노드의 사이즈만큼 실제 크기는 작아집니다. 위에서는 8만큼의 크기가 줄어서 4088만큼의 크기를 사용할 수 있겠네요! 

즉 처음에는 위와 같은 구조를 갖게 됩니다. 이제 100바이트만큼 할당 요청이 발생했다고 생각해보겠습니다. 먼저 이 요청의 요구 메모리만큼 공간이 있는지 확인합니다. 현재는 4088 크기를 갖는 공간 하나만 존재하므로 할당할 수 있습니다. 따라서 이를 2개로 분할해서 할당해줍니다. 그럼 여유 공간 리스트가 아래와 같이 변하게 됩니다.

따라서 100바이트를 요청하면 위와 같이 노드의 크기 때문에 108바이트가 사용되며 남은 사이즈는 3980이 됩니다. 이젠 이렇게 100바이트가 3번 할당된 상태를 살펴보겠습니다.

100바이트 할당을 3번 하면 위의 그림과 같이 구성됩니다. 그럼 만약 일부를 free()하면 어떻게 될까요? 그럼 지금 sptr 포인터를 반환하는 과정을 살펴보겠습니다. 이는 가상 메모리 16500에 해당하는 부분으로 사실 free(16500)이라고 표현될 수도 있습니다. 프로그램은 이를 반환하며 바로 사용 가능 리스트에 추가합니다.

그러면 이제 위와 같이 메모리가 구성됩니다. 즉 이런 상황부터 여유 공간 리스트에 하나 이상의 공간이 저장되는 것입니다. 현재는 여유 공간이 나누어져 있지만 이는 어쩔 수 없습니다. 그럼 이제는 모든 공간에 할당한 메모리 부분을 해제해보겠습니다.

그럼 이렇게 되는데요, 지금처럼 해제한 뒤 병합하는 과정을 거치지 않으면 단편화가 발생합니다. 즉 위와 같은 상태에서는 모든 공간이 free 하지만 최대로 할당할 수 있는 공간은 3764바이트인 문제가 발생합니다.

Growing The Heap

그렇다면 heap에 할당된 공간을 늘리고 싶다면 어떻게 해야 할까요? Heap에 할당된 메모리를 모두 사용한 상태에서 메모리 할당 요청이 들어왔을 때 이를 무작정 거절하는 방법도 있긴 합니다. 하지만 이는 너무 무책임한 방법이므로 보통 할당자들은 OS에 메모리를 추가적으로 요청합니다. 빈 메모리를 찾은 뒤 OS는 새로운 공간의 끝 값을 반환합니다. 이때부터 heap의 크기가 증가하게 됩니다.

Basic Strategies

지금까지는 여유 공간이 어디인지 저장하는 방법과 할당된 메모리가 할당될 때 해야 할 일에 대해 알아봤습니다. 그럼 이번에는 많은 여유 공간이 있을 때 어디에 할당할지에 대해 생각해보겠습니다. 정말 직관적이므로 이해하기도 쉬운 개념입니다!

 

우선 이상적인 할당자는 빠르고 단편화를 최소화합니다. 하지만 메모리 할당과 해제는 임의적이므로 개발자가 잘못 사용하면 지금부터 알아볼 방법마다 효율적이지 못하는 경우가 있을 수 있습니다. 따라서 이번에 알아볼 방법들은 어떤 게 최고라기보다는 각각 장단점이 있고 이를 알아보도록 하겠습니다.

Best Fit

Best fit은 요청한 메모리보다 큰 여유 공간들 중 가장 작은 것에 할당하는 방법입니다. 이렇게 글로 보는 것보다 예를 보면 바로 이해할 수 있습니다. 예를 들어 10KB의 메모리 요청이 들어왔다고 가정해보겠습니다. 여유 공간은 9KB, 11KB, 14KB가 있다고 해보겠습니다. 이 상황에서 Best fit을 사용하면 10KB보다 큰 11KB, 14KB가 후보인데 그중에서 가장 작은 것이니 11KB가 됩니다. Best fit의 장점은 메모리의 낭비를 최소화한다는 것입니다. 하지만 이러한 공간을 찾기 위한 비용이 발생하게 되는 것이 단점입니다.

Worst Fit

Worst fit은 방금 알아본 Best fit과는 반대로 요청한 메모리보다 큰 여유 공간들 중 가장 큰 곳에 할당하는 방법입니다. Worst fit 역시 예를 들어보면, 아까와 동일하게 10KB의 메모리 요청이 들어왔고 여유공간은 9,11,14KB가 있다고 해보겠습니다. 이 상황에서 Worst fit을 사용하면 11, 14KB가 후보인데 이 중 가장 큰 값인 14KB에 할당하게 됩니다. Worst fit은 여유공간 중 가장 큰 곳에 할당하여 최대한 큰 여유 공간을 남겨두려는 것입니다. 하지만 이 방법 역시 이러한 공간을 찾기 위한 비용이 발생하는 것이 단점입니다.

First Fit

First fit은 메모리의 여유 공간을 순서대로 탐색하며 적합한 곳이 나타나면 바로 할당해버리는 방법입니다. 이 방법은 빠른 속도가 장점입니다. 하지만 여유공간이 크던 작던 할당 해버리고 항상 어떠한 순서에 맞게 할당하므로 메모리 사용에 최적화된 방법은 아닙니다. 또한 어떤 순서로 탐색할 것인가에 대한 고민도 해야 하는데, 그중 한 가지 방법은 주소 기반 순서를 사용하는 것입니다. 

Next Fit

Next fit은 First fit과 거의 비슷한데요, First fit은 항상 일정 순서로 탐색했기 때문에 메모리 사용이 불균등할 수 있었습니다. 하지만 Next fit은 이를 보완하여 방금 할당한 그 위치 다음 공간부터 탐색합니다. 즉 예를 보면..

위와 같이 메모리가 존재하고 파란 부분은 사용 중인 부분이라고 생각해보겠습니다. 첫 번째 그림에서 4KB의 요청이 들어오면 먼저 메모리의 앞 쪽부터 탐색합니다. 3KB는 작으므로 넘어가고 그다음 공간인 4KB에 메모리를 할당합니다. 그런 뒤 다음 요청이 들어오면 다시 3KB부터 찾는 것(이건 first fit입니다.)이 아닌 그다음 위치인 또 다른 4KB 위치를 탐색하는 것이 next fit입니다.

Other Approaches

지금까지 알아본 방법들 외에도 메모리를 할당할 때 효율적으로 하기 위한 기술과 알고리즘들이 있는데요, 이 중 몇 가지에 대해 알아보도록 하겠습니다.

Segregated Lists

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

 

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

Buddy Allocation

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

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

 

버디 할당이 좋은 이유는 특정 부분의 버디와 합치는 것이 아주 쉽기 때문입니다. 버디 트리의 레벨에 따라 결정되는 비트로 합병을 빠르게 할 수 있다는 점이 장점이죠!

Other Ideas

요즘엔 다중 프로세서가 대부분이며 다중 스레드를 사용하기 때문에 메모리를 할당하는 할당자의 성능이 아주 중요합니다. 이번에 배운 내용들은 정말 많은 방법 중 하나일 뿐이므로 더 알아보는 것도 좋은 공부가 될 것 같습니다!

Summary

이번 글에서 메모리 할당자가 어떻게 메모리를 할당하고 해제하는지 간단하게 알아봤습니다. 더 좋은 성능을 낼 수 있는 방법을 찾기 위해 아직도 많은 노력을 하고 있다고 합니다. 다음 글에서는 지금까지 메모리를 할당할 때 사용하던 가변 크기의 할당방법이 아닌 고정 크기 할당 방법인 page를 사용한 할당 방법에 대해 알아보겠습니다.

 

감사합니다.