이번 장에서는 근본적인 메모리 관리, 특히 free-space management에 대한 내용을 중점적으로 살펴볼 것이다.
관리하는 메모리 공간을 고정된 크기(fixed-size unit)로 나누면 쉽다. 고정된 크기의 메모리 리스트를 갖고있다가 요청이 오면 리스트의 첫번째 원소를 리턴하면 된다.
하지만 free-space가 다양한 크기의 메모리 유닛으로 구성되어진다면 관리하는 것이 어려워진다. 이것은 유저레벨에서의 메모리 할당과 해제( malloc(), free() ), virtual memory를 활용하기 위해 OS가 실행하는 segmentation, external-fragmentation등에서 찾아볼 수 있다.
위의 그림에서 볼 수 있듯이 free-space는 총 20byte인데 *fragmented8되어있기 때문에 15byte의 할당이 필요한 요청은 실패하게된다.
Assumtion
void malloc(size_t size), void free(void ptr)에 대해서 알아볼 것이다. malloc()으로 지정한 크기 혹은 더 큰 사이즈의 메모리를 할당받는다. 그리고 free()를 통해 할당받은 메모리를 해제하는데 이때 얼마만큼의 크기를 해제해야하는지 인자로 넘겨주지 않아도 할당한 만큼 해제가 이루어지게된다. 이 부분에 대해서는 이 장의 뒷부분에서 이야기를 나눠 볼 것이다.
external-fragmentation에 대해 걱정한 것 처럼, Allocator들은 internal-fragmentation에 대해서 신경써야 한다. 만약 allocator가 요청한 것 보다 더 큰 메모리공간을 제공하는 경우 요청한 만큼을 사용하고 남는 메모리 공간에 대해서 internal-fragmentation이 발생한다. 하지만 이번에 우리는 external-fragementation에 대해서만 살펴 볼 것이다.
이제 아래와 같은 가정을 할 것이다.
- 메모리를 할당하면 할당 한 메모리의 위치가 재조정되지 않는다.
프로그램이 malloc()으로 메모리를 할당받으면 free()를 할 때 까지 같은 메모리공간을 점유한다. 따라서 fragmentation을 해결하기 위한 유용한 방법인 compaction은 발생하지 않는다. 하지만 OS가 segmentation을 수행할 때 fragmentation을 해결하기 위해 compaction이 발생할 수는 있다. - allocator는 연속적인 메모리공간을 관리한다.
유저레벨에서 heap영역을 증가시켜야 하는 요청이 발생할 수도 있지만 이번에는 고정된 크기로 가정할 것이다.
Low-level mechanism
policy에 대해서 깊게 탐구하기 전에 기본적인 allocator들의 splitting(나누기), coalescing(합치기) 방법과 어떻게하면 빠르고 쉽게 할당한 메모리 크기를 알 수 있는지에 대해서 알아볼 것이다. 그리고 free-space를 파악할 수 있는 간단한 free list에 대해서 알아볼 것이다.
Splitting and Coalescing
위의 그림에서 볼 수 있듯이 총 30byte의 heap segment에서 0-9, 20-29byte가 free-space이다. 따라서 이 heap segment에 대한 free list는 아래와 같이 구성될 수 있다.
언급했듯이 10byte 이상의 메모리 할당은 실패할 것이다. 정확하게 10byte의 요청이 오면 쉽게 성공 할 것인데 만약 10byte보다 더 작은 메모리 할당 요청이 온다면 어떻게될까...?
예를들어 free list에 10byte의 free chunk가 존재하는데 1byte의 할당 요청이온다면 이 경우 splitting이라는 방법을 활용하게된다.
그래서 1byte를 할당할 수 있는 free list에 존재하는 2개의 free chunk에서 allocator가 2번째(20-29)를 사용하기로 했다면 2번째 free chunk를 2개의 chunk로 splitting한다. 그래서 첫번째 chunk는 1byte를 할당하고 두번째 chunk는 그대로 free list에 남아있는다.
따라서 free list에서는 20-29byte를 차지하던 2번째 chunk가 21-29byte로 크기가 변하게된다.
이처럼 free chunk보다 요청되는 메모리의 크기가 더 작을 때 splitting이 유용하게 사용된다.
그렇다면 또다른 예시로 만약 사용중이던 10byte의 메모리를 free()한다면 어떻게될까?
그렇다면 단순하게 free list에 반환된 10byte만큼을 아래와같이 추가하면 된다.
만약 10byte씩 3개의 chunk로 나뉜 상태에서 20byte의 할당 요청이 들어온다면 당연히 할당에 실패할 것이다. 이러한 문제를 해결하기위해서 allocator는 3개의 free chunk를 하나의 free chunk로 coalescing한다.
Tracking The Size Of Allocated Regions
free()에 해제해야 하는 메모리의 크기가 없다는 것을 알고있으므로, 우리는 해제 할 포인터를 매개변수로 받았을 때 해제되어야 할 크기를 파악하고, 해제된 메모리를 free list에 추가해야함을 알고있다.
이를 위해서 대부분의 allocator들은 약간의 메모리를 더 써서 head block이라는 곳에 추가적인 정보를 저장하고 있다.
예를들어 20byte의 메모리를 할당받았다고 하자, 이때 헤더에는 해제를 위한 포인터주소와, 무결성검사를 제공하기 위한 magic number 및 기타 다른 정보들을 갖고있다.
typedef struct
{
int size;
int magicNumber;
} header_t;간단하게 위와같은 헤더가 있을 때 우리는 포인터 연산을 활용하면 쉽게 header의 정보를 얻을 수 있다.
해제해야하는 ptr을 header_t로 형변환 한 후 포인터를 -1만큼 이동시키면 17.2와 같이 hptr의 위치를 얻을 수 있다(header_t는 8byte이므로). 그 후에는 무결성 검사를 위해 magicNumber와 예상되는 값이 맞는지를 확인하고 해제되는 메모리의 크기가 header+유저에게 할당된 메모리 크기가 맞는지를 확인하면 된다.
결론적으로 유저가 N만큼의 메모리 할당을 요청했을 때 allocator는 N만큼의 메모리공간을 찾는 것이 아닌, N + header만큼의 메모리공간을 찾는다.
Basic Strategies
free space를 관리하는 기본적인 방법들에대해서 알아보자.
이상적인 allocator는 빠르고, fragmentation을 최소화해야한다.
안타깝게도 malloc, free의 과정이 프로그래머의 의도에 따라서 수행되기 때문에 특정한 방법은 꽤나 안좋은 결과를 발생시킨다. 따라서 가장 좋은 방법에 대해서 말하기보단, 기본적인 방법들의 장단점에 대해 논해볼 것이다.
Best Fit
- free list에서 요청된 크기보다 충분히 큰 free chunk들을 찾는다.
- 충분히 큰 free chunk들 중에서 가장 작은 녀석을 free list에 추가한다.
간단하게 생각할 수 있는 쉬운 방법이다. 하지만 적합한 free chunk를 찾기위해서 모든 경우를 다 살펴봐야하므로 상당히 고비용이다.
Worst Fit
worst fit은 best fit의 반대이다. 가장 큰 free chunk를 free list에 추가한다.
하지만 역시나 적합한 free space를 찾기 위해 반복을 해야하므로 고비용이다. 그리고 더 나쁜것은 추가적인 fragmentation이 발생할 수 있다는 점이다.
First Fit
이름 그대로 요청을 만족할 수 있는 가장 첫번째 메모리 블록을 반환하는 것이다.
first fit은 속도면에서 장점이 있다. 하지만 작은 크기의 메모리를 할당할 때는 free list를 훼손시킬 수 있다. 따라서 allocator는 free list의 순서를 어떻게 관리할 것인가가 매우 중요한 문제이다. 이를 위한 한가지 방법은 free space 주소의 순서를 유지하여 coalescing을 쉽게만들고, fragmentation을 줄이도록 하는address-based ordering기법이다.
Next Fit
항상 첫번째로 조건에 부합하는 결과를 찾는 first-fit과 달리, next-fit은 가장 마지막에 수행되었던 주소의 위치를 기억한다. 따라서 free list에 대한 검색을 좀더 균일하게 분산시켜 free list의 앞부분에서 fragmentation이 발생하지 않도록 한다.
segregated List
segregated List방법은 자주 사용되는 할당 크기만 전담하는 list가 따로 있고, 그 외의 경우에는 일반적인 allocator가 할당을 수행한다.
이렇게 함으로써 fragmentation의 위험이 크게 줄어들 수 있고, 자주 사용되는 메모리의 크기인 경우 free space를 찾지 않아도 되기 때문에 할당과 해제가 꽤나 빠르게 이루어질 수 있다.
하지만 이 방법에도 어느정도의 메모리를 자주 사용된다고 판단하여 할당할 것인지에 대한 문제는 남아있다.
이에 대한 해결책으로 간단하게, kernel이 시작할 때 object cache가 할당되는데, 이 object cache가 자주 할당되고 해제되기 때문에 object cache는 segregated list로 관리된다.
그리고 주어진 cache가 사용가능한 메모리 공간이 부족할 때 일반적인 allocator에게 메모리 slab를 요청하여 추가적인 메모리를 할당받고, 반대로 slab내의 참조 카운트가 0이되면 일반적인 allocator가 다시 메모리를 회수한다.
Buddy Allocator
예를들어 64KB의 free space가 7KB 요청에 부합하는 크기로 계속해서 splitting되어 아래와 같은 그림이 되었다고 하자.
8KB는 할당되어 리턴되었지만 internal fragmentation이 발생한다.
그런데 할당한 메모리가 해제될 때 일반적인 allocator는 buddy allocator의 메모리가 해제되어있는지를 확인한다. 그래서 해제되어있다면 할당한 메모리 8KB + buddy allocator의 8KB를 coalescing하게된다. 또다시 16KB와 그 buddy allocator가 coalescing하여 결국 다시 원래의 64KB의 free space로 되돌아가게 된다.
출처 : OSTEP
