CSAPP (p.890 ~ 901)
Virtual Memory
Explicit Free Lists
implicit free list는 free 블록을 관리하는 간단한 방법이지만 블록 할당에 필요한 시간이 전체 힙 블록 개수에 비례함
explicit free list는 free 블록 내부에 predecessor와 successor에 대한 포인터를 저장함으로써 블록 할당에 필요한 시간을 free 블록 개수에 비례하도록 줄임
free list의 ordering에는 LIFO ordering과 address ordering이 있음
전자는 새로이 free된 블록을 리스트 맨 앞에 저장하고, free와 coalesce 작업이 상수 시간에 이루어진다는 장점을 가짐
후자는 주소 순서대로 리스트를 유지하고, 리스트에서 블록을 저장할 위치를 찾는 데 선형 시간이 걸리지만, first fit placement policy를 사용했을 때 LIFO ordering보다 메모리 활용성이 좋음
explicit free list를 사용하면 블록이 헤더, 푸터, 포인터를 모두 포함할 수 있을 만큼 커야 하므로 최소 블록 크기가 커지고, 이는 잠재적인 내부 단편화 유발 가능함
Segregated Free Lists
비슷한 크기의 블록들을 저장하는 여러 개의 free list를 관리함으로써 블록 할당 시간을 줄이는 방법
모든 가능한 블록 크기 집합을 size class라고 불리는 equivalence class로 파티셔닝하고, 각 size class마다 free list를 둠
free list 내부에서는 블록이 크기 오름차순으로 정렬됨
크기 n인 블록을 찾을 때 적절한 free list를 탐색하고, 크기가 맞는 블록이 없으면 다음 리스트들을 탐색함
-
Simple Segregated Storage
각 size class의 free list는 size class의 최대 크기를 갖는 동일 크기 블록들로 구성됨
특정 크기의 블록을 할당하기 위해 적절한 free list를 확인하고 비어 있지 않다면 splitting 없이 첫 번째 블록을 할당함
비어 있다면 allocator는 OS에 고정 크기의 추가 메모리를 요청한 후 이를 동일 크기 블록으로 나누고 연결하여 새 free list를 생성함
블록을 free하기 위해 allocator는 적절한 free list 맨 앞에 블록을 삽입함
블록 할당과 free에 상수 시간이 걸리는 장점을 가짐
각 메모리 chunk 내에 동일 크기 블록만 가지고, splitting과 coalescing이 없기 때문에 블록 내에 헤더, 푸터가 필요 없음
또한 free list 앞쪽에서만 insert, delete가 일어나므로 리스트가singly linked여도 상관없음
따라서 블록은 successor에 대한 one-word(4 byte) 포인터만 필요하고, 최소 블록 크기도4 byte임
그러나 splitting이 없으므로내부 단편화에, coalescing이 없으므로외부 단편화에 취약함 -
Segregated Fits
각 free list는 size class와 연관되어 explicit 또는 implicit list로 관리됨
각 list는 size class에 속하는 다양한 크기 블록을 가질 수 있음
블록을 할당하기 위해 적절한 free list에 first fit 방식으로 탐색하고, 찾지 못한다면 다음으로 큰 size class의 free list를 탐색함
블록을 찾지 못한다면 OS로부터 추가 힙 메모리를 요청하고, 이를 활용해서 블록을 할당함, 이때 남는 메모리는 split해서 적절한 free list에 저장함
블록을 free하는 경우 coalesce 작업을 거침
빠르고 메모리 활용성이 좋아서GNU malloc과 같은production-quality allocator에서 사용되는 방식 -
Buddy Systems
segregated fit의 specal case로 각 size class가2의 제곱꼴임
요청된 블록 크기는 가장 가까운 2의 제곱으로 올림됨
처음에는 2^m 크기의 free 블록 하나만 존재함
2^k 크기의 블록을 할당하기 위해 최대한 맞는 크기의 블록을 찾고, 더 크다면 재귀적으로 절반으로 split함
이때 남은 반쪽을buddy라고 부르고 적절한 free list에 저장함
블록을 free하기 위해서는 free buddy와 coalesce하는 작업을 계속하고, allocated buddy를 만나면 중단함
블록 주소와 크기가 주어졌을 때 buddy의 주소를 계산하기 쉽다(1 bit만 다름)는 점이 핵심
탐색과 coalescing이 빠르지만 power-of-2 블록 크기를 가진다는 제약조건 때문에 상당한 내부 단편화를 유발할 수 있음
