Free-Space Management

Memory Compaction

앞서 말했던 External Fragmentation을 막기 위해서는 할당되지 않은 공간을 하나로 합쳐 연속된 공간으로 만드는 작업이 필요하다. 이를 Memory Compaction이라 한다.

 

 

Splitting과 Coalescing

위와 같은 주소 공간에서 사용하지 않는 영역의 크기보다 작은 크기에 메모리 요청이 들어오면

한 영역을 둘로 나누어 요청이 들어온 만큼을 할당해주는데 이를 Splitting이라 한다.

---

위 그림과 같이 Free List에 연속된 주소에 빈 공간이 들어있다면

이렇게 하나의 덩어리로 합칠 수 있는데 이를 Coalescing이라 한다.

 

 

메모리 공간의 구조

각각의 메모리 공간에는 header 부분이 있고 그 안에 여러가지 정보를 담고 있다.

할당된 영역의 경우에는 영역의 유효성 검사를 위한 magic number와 영역의 크기를 나타내는 size값이 있고

할당되지 않은 영역은 다음 할당되지 않은 영역을 가리키는 next 포인터와 size값이 저장되어 있다.

 

만약 두번째 영역을 할당 해제하게 되면 오른쪽 그림처럼 magic number 대신 다음 할당 영역의 포인터값을 저장한다.

이로서 반환된 영역이 Free List에 삽입되게 되는 것이다.

 

 

메모리 할당 기법

이렇게 할당되지 않은 영역들을 List로 관리한다면 메모리 할당 요청이 들어오면 우리는 어떤 메모리를 할당해줄지 선택해야 한다. 이를 위한 여러가지 방법을 알아보자.

 

1. Best Fit (최적 적합)

요청받은 크기보다 큰 영역 중 가장 작은 영역을 할당한다.

가장 작은 영역을 할당하므로 낭비되는 메모리가 적지만 External Fragmentation이 발생할 가능성이 높다.

 

2. Worst Fit (최악 적합)

할당되지 않은 영역 중 가장 큰 영역을 할당한다.

가장 큰 영역부터 할당하므로 Best Fit에 비해 External Fragmentation이 발생할 가능성이 적다.

 

3. First Fit (최초 적합)

Free List 순회 중 첫번째로 나오는 할당 가능한 영역을 할당한다.

 

4. Next Fit (차순 적합)

마지막으로 할당한 영역 다음의 할당 가능한 영역을 할당한다.

 

※ Best Fit과 Worst Fit은 할당 시마다 모든 Free List를 순회해봐야 하므로 시간이 오래 걸리는 반면

First Fit과 Next Fit은 상대적으로 짧은 시간에 할당 영역을 찾을 수 있다.

 

※ Segregate List

가장 자주 요청되는 메모리의 크기를 기억하여 이를 위한 별도의 Free List에 저장하는 방법이다.

이후 해당하는 크기의 요청이 들어올 때 메모리의 낭비 없이 할당할 수 있다는 장점이 있다.

하지만 어떤 크기의 메모리를 따로 저장할 지 선택해야 한다는 문제점이 있다.

 

※ Buddy Allocation

모든 공간을 2의 제곱수 크기로 나누어 요청이 들어온 크기보다 큰 영역 중 가장 작은 영역을 할당한다.

2의 제곱수 크기로 영역을 할당해주기 때문에 External Fragmentation이 적게 발생하고 Coalescing이 용이하지만

Internal Fragmentation이 발생하여 메모리가 낭비된다는 단점이 있다.