Buddy System

작동방식

버디 시스템은 각 크기 클래스가 2의 제곱인 특수한 경우의 분리 맞춤 방식이다. 2^m개의 워드를 갖는 힙이 주어졌을 때, 각 블록의 크기가 2^k인 (0 <= k <= m) 분리 가용 리스트를 운영하는 것이다. 요청된 블록들의 크기는 인접한 2의 제곱으로 올림해서 할당된다. (가령 17바이트를 할당하려면 32바이트 크기의 블록이 필요하다.)

크기가 2^k인 k <= j <= m인 크기 2^j인 첫번째 가용블록을 찾는다.
j = k가 될때까지 재귀적으로 블록을 절반으로 쪼개면서 가용블록을 찾는다.
이렇게 분할을 수행할 때, 각각의 나머지 절반(버디)는 해당 가용 리스트에 배치된다.

크기 2^k 블록을 반환하려면 free 가용 버디들은 계속해서 연결된다. 할당된 버디를 만나면 연결을 중단한다.

핵심사항

버디 시스템의 중요한 특징은 블록의 주소와 크기가 주어지면 이 블록의 버디 주소를 계산하는 것이 쉽다는 것이다. 왜냐하면 버디의 크기는 블록의 크기와 같을 것이고 블록과 버디의 주소는 딱 한비트만 다르기 때문이다.

CSAPP 9.9장에도 나와있는 예시지만 크기 32바이트인 블록의 주소가 xxx...x000000일 때 이 블록의 버디의 주소는 xxx...x100000가 될 것이며 이는 원래 블록의 주소와 딱 한 비트 위치만 다르다.
(책에는 버디의 주소가 xxx...x10000으로 나와있긴 하지만 오타라고 생각하는 게 맞을 것 같다.)

장점과 단점

버디 시스템의 중요한 장점은 빠른 검색과 연결이다.

비슷하게 속도에 강점이 있는 방식인 분리 맞춤 방식은 할당하려는 블록의 크기에 알맞는 리스트에 대해서 first-fit 방식으로 검색을 수행해야 하는 반면, 버디 시스템은 어떤 블록의 크기와 위치를 알고 있다면 버디에 해당하는 블록의 크기와 위치를 바로 알 수 있다는 것이 주요한 장점이라고 생각한다.

반면 주요 단점으로는 블록 크기가 2의 제곱으로 제한된다는 사실은 상당한 내부 단편화를 유발할 수 있다는 점이 있다. 그렇기 때문에 버디 시스템은 범용으로 사용하기에는 부적합하며 그 대신 블록 크기를 사전에 2의 제곱으로 맞추고 할당할 수 있는 경우에는 효율적으로 사용할 수 있을 것이다.