17. Free-Space Management

 

Splitting 

• 빈 공간에 대한 요청이 있을 때, 두 부분으로 쪼개서 요청만큼 return 하고 나머지 부분을 다시 free로 관리
• 이후 free list를 update 시켜준다 

 

 

Coalescing 

• 각 free chunk의 size가 요청한 크기보다 작아서, 연속되어 있는 작은 free chunk 들을 하나로 merge 후 return 
• 서로 붙어 있는 free chunk 들만 large single free chunk로 만들 수 있다. 
• free list가 address 순서대로 안되어있을수도 있음 => 정렬을 하든 해서 찾고 합치기

 

 

Tracking The Size of Allocated Regions

• free(void *ptr)은 포인터의 시작 주소만 받지, 크기는 모르는데 어떻게 전체를 해제할 수 있을까?

=> malloc을 할 때, 추가적인 바이트(여기서 8byte)를 더 자동으로 할당 시키고, 여기에 size 정보 저장

 

 

 

The Header of Allocated Memory Chunk

• 위에서 추가적으로 할당한 8byte를 구조체로 정의 

/* a simple header */
typedef struct __header_t{
    int size;
    int magic;
} header_t;

• 이 header의 시작 부분을 hptr ==> dealloc 을 빨리 할 수 있게 함
• magic number 는 integrity checking을 위해 존재
• 이러한 header가 존재하기 때문에, user가 N byte를 요청하더라도 시스템에서는 N + size of header 만큼의 free 공간을 찾는다.

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

• 그냥 void* ptr을 header_t 형으로 변환해서 8 byte 만큼의 배열로 취급 
• ptr - 1 => ptr에서 뒤로 8byte만큼 간 것과 동일 == header의 시작을 알게됨
• 이 hptr을 이용하여 size와 magic num의 정보를 얻을 수 있다.
• 전체 free 할 공간은 malloc으로 할당한 부분 + header 부분까지

 

 

Embedding A Free List

• malloc()과 같은 typical memory-allocator가 아직 구현되지 않은 상태라고 가정해보자.
• malloc, free를 쓰지 않고 free list(heap)을 관리 해야할 때, 어떻게 할 수 있을까?

typedef struct __node_t{
    int size;
    struct __node_t *next;
} node_t;


/* mmap() system call 사용
-> 원래 file을 메모리에 대응하기 위해 사용 했는데, 
여기서는 OS로부터 페이지 단위로 메모리를 할당받기 위해서 사용 */

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:

• malloc이 없기 때문에, node를 직접 heap 안에 수동으로 집어 넣음 
• 실제 free하게 사용할 수 있는 부분은 header 8byte을 제외한 4088 size

 

 

Free Space With Chunks Allocated

• virtual address에서 heap의 시작주소가 16KB고,  4KB 만큼의 free chunk가 있다고 가정.
• 4KB(=4096)에서 100씩 세번 할당 => 남은 free chunk size를 구할 수 있어야 함
• 4096이지만 header 부분 제외 4088부터 108씩 세번 빼주면 3764를 구할 수 있다.

 

 

Free Space With free()

• 위 예시에서, 할당받은 세 부분 중 두번째 영역을 다시 free list로 돌려보내보자.
• free list에 추가는 head의 바로 뒤에 된다고 가정.
• head는 새롭게 추가된 free list의 주소를 가짐 => 16KB(시작주소) + 108(윗부분 할당 크기) = 16492
• free list의 첫번째 노드는, 다음 노드의 주소값을 가짐 => 16492 + 108 + 108 = 16708

 

Free Space With Freed Chunks

• 모든 공간을 free list로 다 돌려 보내면, 위와 같은 free list가 구성된다.
• free한 순서랑, free list의 순서랑 헷갈리지 않길 바람(지금 new node 추가 방식이 head 뒤라서 이렇게 됨)
• total free chunk size = 3764 + 100 + 100 + 100 = 4064

• 만약 이 상태에서 malloc(4000)을 하면, 각 free 노드의 사이즈가 충족되지 않아서  4064 > 4000 임에도 할당 불가
• => External Fragmentation
• 이를 해결하기 위해 Coalescing을 함. 
• => 모두 합쳐지면 free list의 head는 16384를 가리키고, 그 사이즈는 4088이 돼서 할당 가능
• (4064 => 4088 은 header 공간 차이 , merge 했기 때문에 + 24byte가 된 것)

 

 

Growing The Heap 

• 대부분의 heap은 시작할 때 매우 작은 사이즈를 할당 받음.
• 사용하다 부족하면 brk()나 sbrk() system call을 사용하여 OS에 추가 메모리 할당을 요청
• 이 때, 추가적으로 할당 받는 메모리는 physical mem에서 연속적인 공간에 위치할 필요는 없다.

 

 

Managing Free Space: Basic Strategies 

• free space를 다루는 일반적인 방법들

• Best Fit : free list를 다 살펴보고, 요청받은 메모리를 할당해줄 수 있는 가장 작은 사이즈의 노드 선택
• Worst Fit : Best Fit과 비슷하나, 가장 큰 사이즈의 노드를 선택함

=> free list를 전부 탐색해야만 선택을 할 수 있다는 단점 존재, So?

• First Fit : 앞에서부터 탐색, 만족이 되는 사이즈의 노드가 나오면 바로 pick 
• Next Fit : 앞에서부터 선택해서 pick 하는데, 다음번에 또 요청이 들어오면 그 pick한 다음 노드부터 탐색 시작
• => 계속 앞에 노드만 사용하면, 앞에 노드 사이즈는 점점 작아지고, 작은 사이즈의 요청만 계속 들어오면 또 앞에 노드에서만 할당을 하게 됨, 이후에 큰 사이즈의 요청이 들어올 때 그걸 만족할 노드를 찾으러 뒤로 많이 가야하는 First Fit의 단점을 보완 => free list의 노드들을 균형있게 사용할 수 있게 됨. 

 

 

Other Approaches: Buddy Allocation

• allocator가 요청 받은 사이즈를 충분히 할당 할 수 있을만큼 반으로 계속 나눠서 할당하는 방식 
• 다음에 또 7KB를 요청하면, 쪼갠 정보가 남아 있어서 그냥 8KB를 return 할 수 있게 됨
• 만약 dealloc을 했는데, 옆 공간이 할당 x 면, 자동으로 coalecsing 진행 돼서 합쳐진다.

• 만약 alloc(1025)를 하면, 만족하는 최소 byte가 2KB라서, 2048 - 1025, 즉 1023의 공간은 사용x인데 낭비가 됨
• => Internal Frgmentation

 

Other Approaches: Segregated List

• 어떤 패킷같은 것에 자주 요청되는 메모리 사이즈가 존재한다고 할 때, 매번 할당해주는 것이 아니라 한번에 크게 할당해 놓고, 그 메모리를 자주 요청되는 byte size로 나눈 배열로 관리(memory pool), 요청될 때마다 그 배열 원소를 하나씩 return 하는 방식으로 free list를 관리한다. 
• 위의 buddy allocation의 단점도 해결 가능 => 애매한 byte의 사이즈를 미리 잘라놓으면, 낭비되는 공간 줄이기 가능
• 근데 이 memory pool의 크기를 얼마로 해야 할지에 대해서는 open question.
• => Slab allocator가 해결해주고 있다.

• slab allocator
• 리눅스 커널에서 사용, 각각의 object(구조체 변수 => lock 같은거)를 위한 memory pool(= object cache)을 만들어줌 
• 각각의 object에서 할당 요청이 오면, 주 memory allocator로 보내지 않고 각 memory pool에서 해결
• 처음에는 memory pool을 작게 시작했다가, pool이 꽉 차면 더 달라고 요청하는 방식으로 해결.