CSAPP 책은 쌩으로 읽는다면 이해하기 매우 어렵습니다.
따라서 소단원만 그대로 따라가되, 내용을 이해하기 쉽게 재구성했습니다.
9.9.13 명시적 가용 리스트
1. 묵시적 가용 리스트의 한계
묵시적 가용 리스트를 사용해서 간단한 할당기를 만들어볼 수 있었다.
하지만 묵시적 가용 리스트는 일반적인 목적인 할당기에 적합하지 않다.
블록 할당 시간이 힙 블록의 총 개수에 비례하여 선형적으로 증가하기 때문이다.
따라서 힙 블록의 수가 사전에 작다고 알려진 특수한 경우만 사용할 수 있다.
2. 명시적 가용 리스트란?
더 나은 방법은 free 블록들을 명시적인 자료구조로 관리하는 것이다.
가용 블록의 본문(body)는 프로그램이 사용하지 않기 때문에, 블록 내부에 자료구조를 구현할 포인터를 저장할 수 있다.
예를 들어, 위 그림처럼 각 가용 블록 안에 이전 블록(pred)과 다음 블록(succ)을 가리키는 포인터를 넣어, 힙을 이중 연결 리스트 형태로 구성할 수 있다.
3. 명시적 가용 리스트의 장점
명시적 가용 리스트를 사용하면, first-fit 할당 시간 복잡도가 전체 블록 수가 아닌 가용 블록 수에 비례하게 된다.
따라서, 전체 힙을 흝는 것보다 훨씬 빠르게 할당할 수 있다.
4. free 시 리스트 정렬에 따른 차이
가용 리스트를 어떤 순서로 유지할지에 따라 free하는 비용이 달라진다.
1) LIFO(후입선출) 방식
새로 해제된 블록을 리스트의 맨 앞에 추가한다.
이 경우 free하는 데 걸리는 시간은 O(1)이다.
또한, first-fit 배치 정책과 함께 사용하면 최근에 사용한 블록까지 검사하게 된다.
만약 경계 태그(boundary tags)를 사용하면, 블록 병합(coalescing)도 상수 시간 안에 수행할 수 있다.
2) 주소 순서(Address Order) 방식
블록들을 메모리 주소 순서대로 유지한다.
이 경우 free할 때 적절한 위치를 찾기 위해 선형 시간 탐색이 필요하다.
하지만 이런 방식은 메모리 활용률이 더 좋아서, LIFO 방식보다 적은 단편화로 인해 best-fit과 비슷한 수준의 성능을 낼 수 있다.
5. 명시적 가용 리스트의 단점
명시적 리스트 방식는 free 블록 안에 이전, 다음 포인터를 저장해야 하므로 블록이 그만큼 커야 한다.
또한, header와 footer까지 필요한 경우가 많아 최소 블록 크기가 커질 수밖에 없다.
결과적으로, 메모리 내부에서 낭비되는 공간이 생기기 쉬워지고, 내부 단편화(internal fragmentation)의 가능성이 높아진다.
