Free-Space Management
Introduction
나중에 다룰 paging을 이용하면 메모리를 고정된 크기로 나누기 때문에 메모리 관리가 더 쉽다.
free-space management가 어려운 이유는 user-level에서 malloc을 이용해 고정되지 않은 크기의 메모리를 할당하기 때문이다.
바로 이런 이유 때문에 external fragmetation이 발생한다.
- external fragmentation
free space가 used space 사이사이에 존재하는 경우 발생하는 fragmentaion
- internal fragmentation
사용할 공간보다 할당한 공간이 더 크기 때문에 메모리 공간이 낭비되는 경우 발생하는 fragmentation
Assumptions
malloc()과 free()가 제공된다고 가정하자.
malloc()은 size라는 인자를 전달받아 size 만큼 공간을 할당받고, pointer를 return 한다.
free()는 할당된 메모리를 free 해주는데, 이때 size를 입력하지 않아도 알아서 잘 해준다. 즉 library가 free할 size를 알 수 있다는 뜻이다.
이런 메모리는 heap 영역에 있으며, heap에 free space를 관리할 수 있는 free list라는 구조체가 있다. 이 free list에는 free chunk에 대한 레퍼런스가 존재한다.
또 메모리가 할당되면 free 되기 전까지 다른 장소에 재배치될 수 없다고 가정하자.
마지막으로 allocator가 연속하는 메모리를 관리한다고 가정하자. 예를 들어 연속되는 10KB 이상의 free space가 있어야 10KB를 할당할 수 있다.
Low-level Mechanisms
- Splitting and Coalescing
요청한 크기보다 더 큰 free space가 있을 때, allocator가 free space를 찾아서 메모리를 할당해 주면서 두개로 split 하는 것을 splitting이라고 한다.
반대로 나눠져 있는 free된 공간을 하나로 합쳐서 큰 free space로 만드는 것을 coalescing이라고 한다.
- Tracking The Size Of Allocated Regions
앞서 말했듯이 free()는 size를 인자로 전달받지 않는다.
따라서 header가 이런 정보들을 포함해야 한다.
헤더에 할당한 size와 integiry check를 위한 magic number가 있다고 가정하자.
- heap에 있는 used space header
typedef struct __header_t {
int size;
int magic;
} header_t;ptr = malloc(20)을 실행하면, 위 그림처럼 메모리를 할당받을 것이다.
헤더 크기가 더해져야 하므로 free region의 size는 header size + free size가 된다.
- Embedding A Free List
free list를 어떻게 구현할까? 4KB의 heap 공간이 있다고 가정하자.
- free list node
typedef struct __node_t {
int size;
struct __node_t *next;
} node_t;free space에 대한 정보를 관리하기 위해 위와 같은 구조체가 있을 것이다.
초기화가 끝나면 아래 그림처럼 될 것이다.
4096바이트 중 첫 헤더에게 8바이트(size, next)를 할당해서 4088바이트가 남았고, 첫 번째 노드의 size가 그 값을 가지고 있는 그림이다. 다음 노드는 없으므로 next node의 주소는 NULL이다.
만약 100바이트를 할당해 달라는 요청이 오면, library는 node들을 탐색하면서 100보다 큰 free space가 있는지 찾을 것이다. 위 경우 첫 번째 node에서 size가 4088이니 바로 다음에 공간을 할당해 줄 것이다.
100바이트를 3개 malloc 하고 가운데를 free했다고 가정하자.
그럼 위 그림처럼 free 한 node가 head가 되고, 기존 head를 next로 가리킬 것이다. (이런 방식으로 free list를 관리한다고 가정했을 경우)
- Growing The Heap
heap 공간을 다 쓰면 sbrk() 같은 syscall로 heap을 늘린다.
Basic Strategies
free space를 관리하는 몇 가지 전략이 있다.
Best Fit
요청된 크기보다 크거나 같은 free space들을 찾고, 그중 가장 작은 free space을 할당한다.
공간 낭비를 줄일 수 있지만, 탐색하는데 cost가 든다.
external fragment가 심해진다.
Worst fit
best fit과 반대로, 할당할 수 있는 가장 큰 free space를 할당한다.
best fit처럼 모든 노드를 탐색하는 cost가 발생하면서 fragment도 발생한다.
split 된 메모리도 크기가 크니까 사용 가능하다. → external fragment가 살짝 더 좋다.
First fit
항상 노드의 첫 부분에서 탐색을 시작하며, 요청을 만족할 수 있는 free space를 발견하면 바로 할당 한다.
First Fit은 속도에 큰 이점이 있는 대신 free space의 순서에 큰 영향을 받는다.
맨 앞부터 탐색하므로 list 전반부에 free space가 모인다.
address-based ordering을 같이 사용하는데, 이는 coalescing에 유리하고 fragmentation 현상을 줄여준다.
Next fit
가장 마지막에 탐색한 주소 다음부터 탐색을 시작한다.
때문에 가장 마지막에 탐색한 주소를 담는 pointer 공간이 추가로 필요하다.
first fit과 거의 비슷하지만, 초반에 탐색을 반복하는 행동을 피할 수 있다.
Buddy Allocation
coalescing을 단순하게 구현하려는 시도들이 있었고, binary buddy allocator가 좋은 예시이다.
먼저 가장 큰 size를 이라고 생각한다. 그리고 탐색을 시작하면, 가장 큰 size의 공간을 가장 적절한 size가 될 때까지 recursive 하게 반으로 나눈다.
이 방법은 메모리를 크기로 할당하므로 남은 공간이 생겨서 internal fragmentation이 발생한다.
Buddy Allocation은 free할 때 유리하다.
free를 위해 tree를 따라 올라가면서 크기가 같은 buddy를 찾아 coalasing 한다. 모든 공간을 모으거나, 남은 used space가 없을 때까지 반복한다.
Uploaded by Notion2Tistory v1.1.0