12. Virtualization) Free-Space

이번 챕터는 메모리 관리 측면에 대해 살펴 볼것이다. 

frees space가 고정된 크기로 나뉘어 있으면 공관관리가 편할 것이다. 하지만 OS가 segementation으로 virtual memory를 관리하고, 사용자 레벨의 메모리 할당 라이브러리 (malloc, free등)로 인해 free space는 다양한 크기를 갖게 된다.

이와 같이 free space가 서로 다른 크기의 조각으로 분리되는 것을 external fragmentation이라고 한다.

만약 15k의 메모리를 요청할 때, 총 free space의 공간은 20k로 충분하더라도, 하나의 연속된 메모리 공간이 없기 때문에 실패할 것이다.

그리고 free list는 위와 같이 표현될 수 있을것이다.

반대로 10K보다 작은 메모리를 1K 메모리를 요청한다고 해보자. allocator은 splitting을 통해 free chunk를 찾고 둘로 나눌 것이다.

그 다음 첫번째 chunk를 할당하고 두번째 chunk는 아래 사진과 같이 free list에 있을것이다. 

이때 addr:10, len:10의 메모리가 free되기어진다면 free list의 상태는 다음과 같아진다.

이제 free space의 총 공간은 30k지만 3조각으로 쪼개어 있기때문에 10k보다 큰 메모리 요청이 온다면 실패할 것이다.

이 문제는 근접해 있는 free list의 chunk들을 합쳐주면 해결될 것이다. 그리고 이 기술을 coalescing이라고 한다.

coalecing을 통해 allocator은 더 큰 메모리가 이용가능하게끔 보장해준다.

Tracking The Size Of Allocated Regions

이쯤에서 우리가 라이브러리를 통해 동적 메모리를 놓아줄때, 즉 free(void *ptr)을 할 때 파라미터의 크기를 모르는데 free list에 어떻게 다시 통합해줄지 궁금할 수 있다. 이를 위해서 대부분의 allocator들은 메모리에 간단한 정보를 담고 있는 header block을 가지고 있다.

우리가 free(ptr)을 호출하면 라이브러리는 반환하는 포인터 공간의 헤더를 읽고 free list에 메모리를 반환하게 된다.

그래서 우리가 N크기의 메모리를 요청하면 실제로는 N+header size만큼의 공간을 사용하게 된다.

Basic strategies for managing free space

위의 예를 보면 알 수 있듯 이상적인 allocator은 gragmentation을 최소화 하면서 빨라야 한다.

그렇다면 메모리를 할당할때 free space에서 어떤 기준으로 메모리를 선택할까?

일반적인 4가지 전략을 살펴보자.

Best fit

Best fit 전략은 free memory chunk 중에서 요청한 메모리 크기보다 큰 것 중 가장 작은것을 선택한다.

Best fit의 의도는 사용자가 요청한 메모리 크기에 가장 근접한 free space를 할당하여 낭비되어지는 공간을 줄이는 것이다.

하지만 다른 전략들 보다 performance가 좋지 않다.

Worst Fit

Worst Fit은 Best Fit의 정반대이다. 가장 큰 free space chunk를 찾아 할당하고 남은 (큰) chunk를 free list에 두는 것이다.

그렇기 때문에 Best Fit에서 small chunk들이 매우 많은 것에 비해 큰 free한 chunk를 남긴다. 하지만 Worst Fit도 free space를 full search해야하기 때문에 성능에 좋지 않고 과한 fragmentation로 이어질 수 있다.

First Fit

first fit은 단순하게 가장 첫번째 찾은 크기에 맞는 free chunk를 할당하는 것이다. 이것은 속도 측면에서 엄청난 이점이 있다.

하지만 free list의 시작부분부터 fragment가 굉장히 많이 발생한다는 문제점이 있다.

Next Fit

Next Fit은 free list 내부에 pointer를 하나 두고 마지막 위치에서 부터 search를 시작한다. 이를 통해 free list에 골고루 fragmentation이 생기도록 할 수 있다.