[운영체제] 15. Free-space Management

Reference - Operating Systems: Three Easy Pieces

 

 

https://pages.cs.wisc.edu/~remzi/OSTEP/

Operating Systems: Three Easy Pieces

 

 

Free space management

 

- Low-level mechanism

heap allocator에서 사용되는 splitting과 coalescing(분할과 병합), 할당된 영역의 크기를 추적하는 방법, 여유 공간에 리스트를 만들어 여유 공간의 위치를 추적하는 방법에 대해 알아보겠다.

 

heap allocator에 대한 가정

1. malloc() / free(void* ptr)으로 메모리 할당 / 해제

2. No compaction

3. Contiguous region of bytes is allocated.

4. Total free space is fixed

 

- Splitting and Coalescing

 

30바이트 크기의 heap이 있을 때, 10~20바이트 메모리를 사용중이라고 하자.

이를 해제하면, 아래와 같이 나타낼 수 있다.

 

 

이러한 경우, 20바이트 크기의 요청이 들어오면 연속적이지 않기에 컴퓨터는 이를 수행할 수 없다.

이를 위해 Coalescing(병합)이 필요하다.

 

 

heap은 위와 같은 병합을 통해 20Byte 데이터를 할당할 수 있게 된다.

 

- Tracking the size of allocated regions

 

free()는 size를 포함하지 않는데, 어떻게 할당된 region의 size를 알 수 있을까?

이는 할당되는 메모리 바로 위에 header에서 할당된 영역의 크기를 저장함으로써 가능해진다.

free(ptr)을 호출하면 free는 ptr 헤더의 시작 지점을 찾아내고, 헤더+헤더에 저장된 할당 메모리 크기만큼의 메모리를 해제한다. 

 

free space에 free list를 build하는 과정

1. linked list를 만든다.

2. mmap() system call을 통해 특정 영역 메모리 포인터를 넘겨준다.

3. linked list에 free chunk를 할당한다.

4. malloc()과 free()가 호출될때마다 list를 관리한다.

5. sbrk()로 필요에 따라 heap size를 증가시킨다.

 

Allocation이 요청되면, library가 먼저 충분한 공간이 있는지 확인한다. 공간이 있으면, free chunk를 요청된 사이즈만큼의 chunk와 나머지 남은 chunk로 split하고, 이후 free list에서 size of free chunk를 방금 allocation한 size만큼 줄인다.

 

4KB heap이 있다고 하면, 먼저 free list 크기인 8bytes만큼 공간이 줄어 4088 bytes가 남고,

이후 100bytes allocation을 요청하면 free list 8 bytes + 100 bytes 만큼을 사용해서 할당한 뒤, free list에 적힌 남은 free chunk는 3980이 된다.

 

 

이후 free()를 하면, free list에 하나 이상의 공간이 저장된다. coalescing을 하지않으면 free space는 나누어져있다.

즉, 해제한 뒤 병합을 하지않으면 fragmentation이 발생하고, 모든 공간이 free해도 할당한 공간을 사용할 수 없는 문제가 있다. heap에 할당된 공간을 늘리고 싶은 경우 sbrk()로 heap size를 증가시키기도 한다.

 

- Managing Free Space : Basic strategies

 

여유공간이 많을 때 어디에 할당해야 할까? 그 방법들은 정답이 없고, 각각의 장단점이 있다.

- Best Fit : 요청한 메모리보다 큰 여유공간들 중 가장 작은 곳에 할당 - 메모리 낭비 최소화, 찾는 비용 발생

- Worst Fit : 요청한 메모리보다 큰 여유공간들 중 가장 큰 곳에 할당 - 찾는 비용 발생

- First Fit : 여유공간을 순서대로 탐색하여 적합하면 바로 할당 - 빠른 속도, 메모리 사용 불균등할 수 있음.

- Next Fit : First Fit과 유사하나, 여유공간을 탐색할 때 방금 할당한 그 다음 공간부터 탐색.