Free-Space Management

free-space management

고정된 크기를 사용하는 paging을 이용하면 빈공간 관리가 쉬워진다. 하지만 가변크기일때는 빈공간 관리가 보다 어렵다.

segment도 최대 크기는 일정하지만 그 최대 크기를 모두 segment로 사용하지는 않기 때문에 이것 역시 가변적이다.

 

segment가 아닌 base and bound방식을 쓰더라도 한 덩어리의 크기는 가변이다.

또 이 segment를 사용하는 과정에서 남은 공간이 너무 조금씩 흩어져 있어서 사용할 수가 없는 external fragmentation현상이 생길 수 있다.

20bytes의 공간이 있는데도 15bytes의 메모리 할당 요청을 받으면 실패한다.

 

 

메모리의 할당과 반납

void *malloc(size_t size) //메모리 할당 요청
voif free(void *ptr) //메모리 반납

또한 메모리 할당을 요청하는 malloc()은 필요한 사이즈를 매개변수로 받아 할당받은 메모리의 시작주소를 반환한다. 하지만 free()를 통해 이 공간이 반환될 때는  시작 포인터값만 매개변수로 주고 사이즈는 주지 않는 것을 볼 수 있다.

즉, 메모리가 할당될때부터 반환될때까지 size정보는 유지되고 있는 것이다.

 

 

Low-Level mechanism

1. 분할(splitting)

 

 

분할은 메모리 할당 요청을 받고나서 사용할수있는 공간이 있으면 떼어주고 남은 빈공간을 또 관리하는 것이다.

 

만일 1바이트의 메모리 할당 요청을 받는다면 20에서 1바이트를 떼어주고 나머지 9바이트를 다시 리스트로 관리할 수 있다.

 

 

 

 

 

 

2. 병합(coalescing)

사용되다가 반납된 메모리공간을 다시 리스트로 추가해 관리된다.

그리고 주소상 연결이 가능하다면 병합을 통해 그렇게 관리되는 각 조각들을 하나로 묶어 그만큼 큰 메모리 공간을 할당해줄 수 있다.

 

 

 

 

 

 

 

 

allocated region plus header

요청한 메모리 크기는 20byte였다고 해도, header부분에 size정보와 magic값(free할때 안전하게 할 수 있도록 함.)이 들어가기 때문에 사실 해당 요청으로 할당받게되는 메모리는 28byte이다.

따라서 메모리 공간을 free() 해줄때 이 부분까지 고려해야 한다.

allocate, free

메모리에 allocate되었던 값들이 free되면서 linked list구조인 free list의 맨앞으로 들어가는 것을 볼 수 있다.

(이 경우 병합은 한번도 일어나지 않음. 따라서 사실상 한덩어리지만 네덩어리인 것처럼 나타난다.)

 

또한 주목할만한 부분은 메모리에 allocate되어있는 영역의 header에는 size와 magic number가 들어가고, free space로 들어간 영역의 header에는 size와 next가 들어간다는 것이다. 여기서 next가 0이면 null로, 해당값이 free list의 마지막이라는 뜻이다.

 

 

Growing the heap

heap이든 stack이든 segment나 공간이 모자랄 때는 sbrk()라는 system call을 통해 늘려줄 수 있다.

 

 

Basic strategies

새로운 memory allocation요청이 들어올 경우, 크기가 맞는 것을 찾아야 한다.

그리고 이것을 찾는 기법에는 여러가지가 있다.

 

1. Best Fit (가장 잘 맞는 것, 딱 맞는 것)

모든 노드를 전부 search해야 하므로 성능면에서 손해이다. (exhaustive search)

또, external fragmentation이 심해진다는 단점이 있다.

 

2. Worst Fit (가장 넉넉한 것, 헐렁한 것)

external fragmentation을 줄임.

그러나 이것또한 모든 노드를 전부 search해야 하므로 성능면에서 손해이다. (exhaustive search)

 

3. First Fit (처음으로 발견한 들어갈 수 있는 곳)

들어갈만한 곳을 처음 찾으면 거기에 넣는다. 

빠르다는 것이 장점이지만, linked list전반부에 작은 조각이 모인다는 단점이 있다.

 

4. Next Fit (이전에 어디서 allocate했는지를 기억했다가 그 다음부터 찾는 것)

first fit의 단점이 개선된다.

 

Buddy system (buddy allocation)

임의의 크기를 주는것이 아니라 정해진 크기대로 나누어놓고 할당해주는 것.

예를 들어, 6KB를 요청하면 8KB를 할당하고, 10KB를 요청하면 16KB를 할당한다.

그러나 내부적으로 안쓰는 공간(internal fragmentation)이 발생한다는 단점이 있다.