CSAPP 9.9.14 - 분리 가용 리스트와 버디 시스템

명시적 가용 리스트는 가용 블록만 검색한다. 그래도 큰 요청에 맞는 블록을 찾으려면 작은 가용 블록들을 계속 지나갈 수 있다.

분리 가용 리스트(segregated free list) 는 가용 블록을 크기별로 나누어 여러 리스트에 저장한다. Notion의 9.9.14 기록에 있는 일반적인 분리 리스트와 버디 시스템을 함께 정리했다.

크기 클래스마다 리스트를 하나씩 둔다

각 리스트가 담당하는 크기 범위를 크기 클래스(size class) 라고 한다. 개념적으로는 다음처럼 구성할 수 있다.

[0] {1}       → 가용 블록들
[1] {2}       → 가용 블록들
[2] {3~4}     → 가용 블록들
[3] {5~8}     → 가용 블록들
...
[k] {4097~∞}  → 가용 블록들

클래스 범위를 2의 거듭제곱으로 나누거나, 작은 크기는 더 촘촘하게 나누고 큰 크기만 넓게 묶을 수 있다. 위 숫자는 분류 원리를 보여주는 예다. 실제 블록 크기는 메타데이터와 정렬 조건을 만족해야 한다.

필요한 블록 크기가 24바이트이면 {17~32} 클래스를 출발점으로 삼는다. 다만 그 안의 블록이 모두 24바이트 이상이라는 뜻은 아니다. 클래스가 비어 있거나 충분히 큰 블록이 없으면 더 큰 클래스를 검색한다.

Simple segregated storage: 같은 크기로 잘라 두기

이 방식은 한 클래스에 정확히 같은 크기의 블록을 넣는다. 예를 들어 {17~32} 클래스가 32바이트 단위라면 20바이트 요청에도 32바이트 블록 전체를 준다.

할당할 때는 리스트의 맨 앞 블록을 꺼내고, 반환할 때는 다시 맨 앞에 넣는다. 클래스가 비면 큰 메모리 덩어리를 확보해 같은 크기로 나누어 리스트를 만든다.

이 단순한 모델은 개별 요청마다 블록을 분할하지 않으며, 반환 시 이웃 블록과 연결하지도 않는다.

메타데이터를 줄일 수 있는 이유

같은 영역의 블록 크기가 일정하고, 별도 관리 정보로 주소가 속한 클래스와 영역을 알 수 있다면 블록마다 크기를 반복해 저장할 필요가 없다.

이웃의 가용 여부를 보고 합치지 않으므로 경계 태그가 필요하지 않다.
맨 앞에서만 넣고 빼므로 pred 없이 succ 하나로 단일 연결 리스트를 만들 수 있다.
가용 블록의 공간을 succ 저장에 재사용할 수 있다.

블록마다 헤더와 푸터가 불필요해질 수 있다는 뜻이지, 할당기 전체에 관리 정보가 전혀 필요 없다는 뜻은 아니다.

빠른 대신 공간을 낭비할 수 있다

20바이트 요청에 32바이트를 주면 남는 12바이트는 내부 단편화다.

또 32바이트 클래스의 블록들을 많이 반환했더라도, 연결하지 않는 단순한 모델에서는 그것들을 합쳐 64바이트 요청에 줄 수 없다. 빈 공간이 다른 클래스에 묶여 있어 메모리를 더 확보해야 할 수 있다.

Segregated fit: 클래스 안에서 찾고, 필요하면 분할하기

segregated fit은 한 클래스 안에 그 범위에 속하는 여러 크기의 블록을 둘 수 있다. 각 클래스는 묵시적 또는 명시적 리스트로 구성할 수 있으며, 여기서는 명시적 리스트를 생각한다.

다음은 헤더·푸터가 각각 4바이트, 포인터가 8바이트이고 8바이트 정렬을 사용하는 예다. 두 연결 포인터까지 넣을 수 있도록 최소 블록 크기를 24바이트로 잡았다.

class[0] {24~32}   → [24] ⇄ [32] ⇄ [24]
class[1] {33~64}   → [40] ⇄ [48]
class[2] {65~128}  → 비어 있음
class[3] {129~256} → [200] ⇄ [144]
...

할당 과정

요청한 페이로드에 메타데이터와 정렬을 반영해 asize를 계산한다.
asize가 속한 클래스에서 검색을 시작한다.
리스트에서 asize 이상인 가용 블록을 찾는다.
없으면 더 큰 클래스로 넘어간다.
찾은 블록은 가용 리스트에서 제거한다.
남는 공간으로 유효한 가용 블록을 만들 수 있으면 분할하고, 남은 조각을 해당 클래스에 넣는다.
어느 클래스에도 적합한 블록이 없으면 힙을 확장한다. 확장도 실패할 수 있다.

30바이트 요청을 실제로 계산해보면

헤더·푸터를 합쳐 8바이트가 필요하므로 30바이트 요청은 38바이트가 된다. 8의 배수로 올리면 asize = 40이다.

크기 48인 가용 블록을 찾았다면, 요청에 필요한 크기를 빼고 8바이트가 남는다. 그러나 8바이트는 새 가용 블록의 메타데이터와 연결 포인터를 담기에 너무 작다. 이 경우 분할하지 않고 48바이트 전체를 할당한다.

반면 크기 200인 블록이라면 160바이트가 남으므로 분할할 수 있다.

48바이트 후보:
[할당 48]                 ← 남는 8바이트를 따로 떼지 않음
 
200바이트 후보:
[할당 40][가용 160]       ← 160은 해당 크기 클래스에 다시 삽입

원문의 분할 예시에서 8바이트 정렬과 맞지 않던 블록 크기는 정렬 조건에 맞춰 정리했다. 핵심은 남는 공간이 있다는 것과 별도의 가용 블록을 만들 수 있다는 것은 다르다는 점이다.

반환 과정

반환한 블록과 물리적으로 인접한 가용 블록들을 연결한다. 이때 이웃들은 기존 크기 클래스의 리스트에서 먼저 제거해야 한다. 합친 뒤에는 최종 크기를 기준으로 새 클래스에 삽입한다.

합치거나 나누면 블록의 크기가 달라진다. 따라서 단순히 헤더만 고치는 것이 아니라, 크기 클래스 소속까지 바뀔 수 있다는 점을 기억해야 한다.

버디 시스템: 블록 크기도 2의 거듭제곱으로 제한하기

버디 시스템(buddy system) 은 segregated fit의 특수한 형태로 볼 수 있다. 크기 클래스뿐 아니라 실제 블록 크기까지 2의 거듭제곱으로 제한한다.

요청에 필요한 전체 공간 이상인 가장 작은 2의 거듭제곱 크기를 선택한다. 아래 예시는 분할 원리에 집중하기 위해 메타데이터 비용은 생략한다.

64짜리 블록에서 8을 할당하기

처음에는 크기 64의 가용 블록 하나만 있고, 8 크기의 블록이 필요하다고 해보자. 작은 클래스에 블록이 없으므로 큰 블록을 찾은 뒤 절반씩 나눈다.

처음: [                  64                  ]
       0
 
분할: [        32        ][        32        ]
       0                  32
 
분할: [   16   ][   16   ][        32        ]
       0        16        32
 
분할: [8][8]    [   16   ][        32        ]
       0  8      16        32

맨 앞의 8을 할당하고, 나머지 반쪽은 각 크기 리스트에 남긴다.

8 리스트  → 오프셋 8
16 리스트 → 오프셋 16
32 리스트 → 오프셋 32

버디는 같은 부모 블록을 나눈 두 반쪽이다

크기가 같고 인접했다고 무조건 버디인 것은 아니다. 같은 큰 블록을 절반으로 나누어 생긴 두 블록이어야 한다.

범위 0~7과 8~15   → 크기 16의 블록에서 나온 버디
범위 0~15와 16~31 → 크기 32의 블록에서 나온 버디
범위 0~31과 32~63 → 크기 64의 블록에서 나온 버디

오프셋 0의 8바이트 블록을 반환하면, 버디가 같은 크기의 가용 블록인지 확인하고 합친다. 합친 블록의 버디도 가용이면 반복한다.

오프셋 8, 크기 8이 가용  → 합쳐서 크기 16
오프셋 16, 크기 16이 가용 → 합쳐서 크기 32
오프셋 32, 크기 32가 가용 → 합쳐서 크기 64

버디가 할당되어 있거나 더 작은 블록들로 나뉘어 있다면, 그 단계에서 바로 하나로 합칠 수는 없다.

버디 위치는 XOR로 계산할 수 있다

정렬된 관리 영역 안에서 영역 시작 기준의 오프셋을 사용하면 다음처럼 계산할 수 있다.

버디 오프셋 = 현재 블록 오프셋 XOR 블록 크기
 
크기 8,  오프셋 0  → 0 XOR 8   = 8
크기 8,  오프셋 16 → 16 XOR 8  = 24
크기 16, 오프셋 0  → 0 XOR 16  = 16
크기 16, 오프셋 32 → 32 XOR 16 = 48

임의의 시작 주소를 사용하는 경우에는 기준 주소를 빼서 오프셋으로 계산한 뒤 다시 더해야 한다. 위치 계산은 빠르지만, 버디가 같은 크기의 가용 상태인지 확인하는 관리 정보는 여전히 필요하다.

내부 단편화와 빠른 분할·연결의 맞교환

버디의 위치를 쉽게 계산하고, 분할·연결 규칙을 단순하게 만들 수 있다는 것이 장점이다. 이웃 크기를 찾기 위한 푸터도 필수는 아니다. 다만 여러 크기 단계를 오르는 전체 연결 과정은 XOR 한 번으로 모두 끝나는 것은 아니다.

단점은 요청 크기를 2의 거듭제곱으로 올리면서 생기는 내부 단편화다. 메타데이터를 제외한 예로, 65바이트 요청에 128바이트 블록을 주면 63바이트가 남는다.

페이지 단위로 연속한 물리 메모리를 확보하는 것처럼 할당 단위가 맞는 상황에서는 유용하다. Linux의 물리 페이지 할당기도 버디 구조를 사용한다. Linux 물리 메모리 문서

방식	클래스 내부 블록	분할·연결	주된 고려 사항
Simple segregated storage	같은 크기	단순 모델에서는 하지 않음	빠르지만 클래스 간 공간 재사용이 어려움
Segregated fit	범위 안의 여러 크기	가능	탐색·분할·클래스 이동을 관리해야 함
Buddy system	2의 거듭제곱 크기	절반 분할·버디끼리 연결	규칙은 단순하지만 내부 단편화가 커질 수 있음

함께 읽기

#csapp #malloc #seglist #buddy-system

시리즈에서 이어 읽기 · CSAPP 메모리 관리 →