Free-space 관리
리스트를 비롯하여 hashed 리스트, 트리 등 다양한 데이터 구조체를 통해 OS는 free-space를 관리한다.
Variable size
ex) Segmentation
가변 크기 단위를 관리하는 것은 복잡할 뿐더러, 외부 단편화에 대해 다룰 필요가 있다.
Fixed size
ex) Paging
고정 크기 단위를 관리하는 것은 상대적으로 쉽다.
주로 free fixed-size 리스트로 관리된다.
"relocated", "swap-out"
- 프로세스 2는 동적으로 "relocated"
- 프로세스가 중지(suspended)될 때 'swap-out'되어 디스크의 swap 공간으로 갈 수 있다.
Fragmentaion(단편화)
-
외부 단편화(external fragmentation)
: 주로 가변 크기 할당에 의해 발생한다. -
내부 단편화(internal fragmentation)
: 주로 고정 크기 할당에 의해 발생한다. (base/limit 레지스터 기반의 연속 할당 기법, 불연속 할당의 Paging 기법)
Free-Space Allocation policy
1) Best-fit
: 할당 요청 사이즈보다 같거나 큰 free-space chunk 중 가장 작은 크기의 공간을 할당한다.
할당 후 남은 공간(위 예에선 1B)을 최소화할 수 있다.
2) Worst-fit
: 할당 요청 사이즈보다 같거나 큰 free-space chunk 중 가장 큰 크기의 공간을 할당한다.
위 예에선 20B의 공간을 다시 남길 수 있다. 이 후 이 공간은 상대적으로 크기에(best-fit의 예시보다) 할당될 가능성이 높아진다.
3) First-fit
: 할당 요청 사이즈보다 같거나 큰 free-space chunk 중 head(free-space list의)에서 가장 처음으로 발견한 공간을 할당한다.
Best/Worst-fit 방식은 모든 free-space에 대해 선형 탐색을 진행해야 한다. First-fit은 가장 처음에 나온 가용 공간을 할당하기에 탐색에 대한 오버헤드를 줄일 수 있다.
4) Next-fit
: 가장 마지막에 할당된 공간 이 후의 가용 공간을 할당한다.
first-fit은 head부터 앞 쪽에 할당 후 작은 조각들(외부 단편화 유발)을 계속 남길 수 있다. 이러한 단점을 극복시킬 수 있다.
5) Buddy allocation
: 'splitting/coalescing' 방식에 최적화 되어있다.
free-space를 2^n의 크기로 할당한다.
자신의 짝(buddy)와 coalescing한다.
