CSAPP 책은 쌩으로 읽는다면 이해하기 매우 어렵습니다.
따라서 소단원만 그대로 따라가되, 내용을 이해하기 쉽게 재구성했습니다.
9.9.7 할당한 블록의 배치
프로그램이 k바이트짜리 블록을 요청하면, 할당기는 free list(가용 리스트)에서 요청한 크기 이상을 담을 수 있는 블록을 찾아야 한다.
이때 어떤 블록을 고를지 결정하는 기준을 placement policy(배치 정책)라고 한다.
대표적인 배치 정책은 First Fit, Next Fit, Best Fit이 있다.
1. First Fit
free list의 처음부터 검색해서, 처음으로 요청 크기에 맞는 블록을 선택한다.
-
장점
리스트의 끝에 큰 free block들이 남을 가능성이 크다.
(앞쪽부터 작은 블록들을 차례로 잘라 쓰니깐, 뒤에 큰 덩어리들이 남게 된다.) -
단점
리스트 앞부분이 작은 조각들로 채워질 수 있다.
그렇게 되면, 큰 블록을 찾는 데 시간이 오래 걸릴 수 있다.
2. Next Fit
free list를 매번 처음부터 검색하지 않고, 이전 검색이 끝난 지점부터 이어서 검색한다.
이 방식은 Donald Knuth가 First Fit의 대안으로 제안한 것이다.
지난번에 찾았던 블록 근처에서 다음에 쓸 것도 있을 확률이 높다는 아이디어에서 출발했다.
-
장점
리스트 앞부분이 작은 조각들로 가득 찼을 때, First Fit보다 빠르게 동작할 수 있다. -
단점
First Fit보다 메모리 활용도가 떨어질 수 있다.
(작은 빈틈들이 더 쉽게 남아버리는 경향이 있다.)
3. Best Fit
free list의 모든 블록을 검사해서, 요청 크기에 딱 맞는 가장 작은 블록을 선택한다.
-
장점
연구 결과, First Fit이나 Next Fit보다 메모리 활용도가 더 좋은 경우가 많았다.
(남는 빈공간이 작아지기 때문) -
단점
Simple Free List 구조(예: implicit free list)에서는 힙 전체를 다 뒤져야 하므로 성능이 떨어질 수 있다.
나중에는 힙 전체를 다 뒤지지 않고도 Best Fit에 가깝게 동작할 수 있는 Segregated Free List 같은 더 정교한 방법을 살펴볼 예정이다.
