Free Space Management

우리는 그래서 남는 공간을 어떻게 관리해 주어야 할까요?

Free space management는 variable sized unit이 포함되어 있어 매우 까다롭습니다. (segmentation 사용할 경우, heap allocation 사용할 경우 발생)

 

그리고 Externel fragmentation문제가 반드시 발생하게 되어있죠.

이를 minimize 해주는 것이 좋은 Free space management algorithm이라고 할 수 있습니다.

---

Low-level mechanisms

기본적인 mechanism에 대해 살펴보자면

Memory interfaces는 다음과 같은 두개의 함수가 사용됩니다.

• void* malloc(size_t size)
• void free(void* ptr)

Compaction이 일어나지 않습니다. 즉 memory가 한번 allocate되면 다시 옮겨지지 않는다는 뜻입니다.

그리고 연속적으로 allocate됩니다.

전체 free space는 고정되어 있습니다. 다만, 실전에서는 system call인 sbrk를 사용하면 전체 free space를 늘릴 수 있습니다.

---

Free list

Free space는 free list인 linked list로 저장되는데

이 Free list는 기본적으로 Splitting과 Coalescing이라는 두개의 method로 관리됩니다.

 

---

Splitting

malloc(n)을 요청하면 n보다 큰 크기의 free chunck of memory를 찾은다음에, 이를 두개의 chunck로 나눕니다.

First chunck는 caller로 return되며 Second chunck는 free list에 유지됩니다.

Coalescing

free(주소)를 요청하면 addr:주소 len: chunk size인 unit이 free list로 반환됩니다.

아래의 주소공간을 보면 나뉘어져 있지만 하나의 연속된 free space라는 것을 알 수 있습니다. 이를 free가 끝날때 Coalescing(병합)해줌으로 하나의 큰 공간으로 만들어 줍니다.

---

Header of memory chunck

free(void *ptr)은 size를 넣어주지 않았는데 어떻게 size까지 알아서 반환되는 걸까요? 이는 Header block의 존재 덕분입니다.

ptr위의 고정된 byte의 header가 size의 정보를 담고 있기 때문이죠. 이를 읽음으로써 free할 수 있게 됩니다.

 

Header는 다음과 같은것도 포함할 수 있습니다.

메모리 할당 해제를 빠르게 해주기 위한 다른 포인터, 유효성 검사(integrity check) 를 위한 magic number, 등등..

 

그런데 이렇게 되면 header에 대한 정보도 memory에 포함시켜줘야합니다.

즉, 제가 malloc(N)을 하면 실제로 할당되는 bit수는 N+header size가 되는 셈입니다.

---

Embedding A Free List

아까의 free list는 concept만 다룬 것이고 실제로는 어떻게 구현될까요?

1. linked list를 생성하고 초기화합니다.
2. kernel에서 memory를 가져옴으로써 heap을 생성합니다. (mmap)
3. 한개의 거대한 free chunck를 linked list에 할당해 줍니다.
4. list를 malloc과 free가 들어올때마다 아까와 같이 관리해줍니다.
5. heap size를 늘리고 싶으면 sbrk를 통해 늘려줍니다.

코드 상으로는 다음과 같이 구현됩니다.

//mmap() returns a pointer to a chunck of free space
node_t *head = mmap(NULL, 4096, .... );
head->size = 4096 - size(node_t) // minus header size
head->next = NULL;

만약 여기서 malloc(n)이라는 요청이 들어왔다고 합시다.

그렇다면 첫번째로 n+header_size보다 큰 공간이 있는지 확인해야 합니다.

 

그 후 free chunck를 두개로 나누고 한개는 request에 사용하고 다른 한개는 free list에 남겨둡니다.

free list에 있는 chunk의 사이즈는 줄여주어야 합니다.

만약 free를 해 줄 경우 다음과 같이 해 줍니다.

그후 연속된 Free list가 있다면 Coalescing해 줍니다.

 

---

Which Fit should we use?

 

Best Fit (가장 별로)

 

Free space에서 들어갈 수 있는 자리 중 제일 작은 것을 찾습니다.

List를 두개로 쪼개지 않고 그냥 제일 작은 chunk 덩어리를 반환합니다.

Full Search가 요구됩니다.

 

Worst fit

 

제일 큰 것을 찾습니다.

List를 두개로 쪼개어 remain한 chunck를 계속 관리합니다.

Full Search가 요구됩니다,

 

First Fit

 

첫번째로 찾은 충분한 크기의 chunck를 사용합니다.

 

Next Fit

 

가장 마지막에 들어간 공간으로부터 가장 적합한 chunck를 찾습니다.