버디 메모리로 외부 단편화를 관리하는 이진 분할 방식

빈 공간을 다시 큰 블록으로 만드는 할당자

버디 메모리(Buddy Memory)는 큰 메모리 요청이 작은 빈 공간들 때문에 실패하는 외부 단편화를 다루기 위한 할당 알고리즘이다. 메모리를 2의 거듭제곱 크기 블록으로 관리하며, 필요한 크기에 맞춰 절반씩 분할한다.

요청 크기 이상인 가장 작은 블록을 선택하고, 반환된 블록은 같은 크기의 인접 블록과 다시 합친다. 이진 트리로 블록 관계를 관리할 수 있어 할당·해제·병합은 O(log n) 시간 복잡도로 처리한다.

하한선은 최소 할당 단위이며 보통 4KB로 둔다. 상한선은 물리 메모리 크기에 따라 2^n 형태로 정한다.

요청이 들어오면 먼저 2의 거듭제곱 크기로 올림한다. 예를 들어 18KB를 요청하면 32KB(2^5 × 1KB) 블록을 할당한다. 해당 크기의 빈 블록이 없으면 더 큰 블록을 계속 절반으로 나눠 버디 쌍을 만든다.

64KB 메모리에서 16KB를 요청하는 경우의 분할은 다음과 같다.

초기: [64KB]
분할 1: [32KB] [32KB]
분할 2: [16KB] [16KB] [32KB]
할당: [16KB(할당)] [16KB(free)] [32KB(free)]

한쪽 절반은 요청에 할당하고 나머지 절반은 프리 리스트에 남긴다. 필요한 크기에 도달할 때까지 이 과정은 재귀적으로 반복될 수 있다.

1024KB 메모리에서 여러 요청을 처리하면 블록 관계는 다음처럼 변한다.

[1024KB]

분할: 1024 → 512 + 512
분할: 512 → 256 + 256
분할: 256 → 128 + 128
할당: [128(A)] [128] [256] [512]

분할: 128 → 64 + 64
할당: [128(A)] [64(B)] [64] [256] [512]

분할: 256 → 128 + 128
할당: [128(A)] [64(B)] [64] [128(C)] [128] [512]

B의 64KB 블록을 해제하면, 같은 크기의 버디가 비어 있는지 확인한다.

병합: 64 + 64 → 128
상태: [128(A)] [128] [128(C)] [128] [512]

버디 주소는 현재 주소와 블록 크기의 XOR 연산으로 구한다. 블록 주소가 0x1000이고 크기가 16KB라면 버디는 0x5000이다. 두 블록이 비어 있고 크기가 같으며 인접해 있으면 더 큰 블록으로 병합하고, 상위 레벨에서도 병합을 시도한다.

각 이진 트리 노드는 하나의 메모리 블록을 나타낸다. 왼쪽과 오른쪽 자식은 각각 블록의 절반이며, 리프 노드는 최소 할당 단위에 해당한다.

트리 높이는 전체 메모리 크기와 최소 단위의 비율로 정해진다. 1024KB를 4KB 단위로 관리하면 log₂(256) = 8이다. 할당과 해제, 병합은 모두 O(log n)으로 처리된다.

블록 크기 범위는 다음과 같이 계산한다.

하한선: 2^k (보통 k=12, 4KB)
상한선: 2^n (물리 메모리 크기)
레벨 수: n - k + 1

각 크기(order)는 프리 리스트 배열로 관리할 수 있다.

struct free_list {
    struct list_head list;  // 빈 블록 리스트
    unsigned long count;    // 블록 개수
};

struct free_list free_area[MAX_ORDER];

블록은 할당 가능한 Free, 사용 중인 Allocated, 분할된 Split 상태로 구분한다. 메타데이터에는 블록 시작 주소, 블록 크기(order), 상태 비트맵을 둔다.

버디 메모리는 인접한 빈 버디 블록을 자동으로 합쳐 큰 연속 메모리를 다시 확보한다. 버디 주소를 XOR로 계산하므로 주소 탐색은 상수 시간 O(1)으로 끝나며, 상위 레벨까지 병합할 수 있다.

이진 분할 구조는 구현과 유지보수가 비교적 단순하고, 최악의 경우에도 O(log n) 성능을 보장한다. 예측 가능한 성능이 필요한 실시간 시스템에도 맞는 특성이다.

반면 2의 거듭제곱 크기만 사용할 수 있다는 제약은 내부 단편화를 만든다. 18KB 요청에 32KB를 할당하면 14KB가 남고, 낭비율은 43.75%다. 요청 크기와 실제 할당 크기의 차이는 다음처럼 커질 수 있다.

요청 크기	할당 크기	낭비	낭비율
9KB	16KB	7KB	43.75%
17KB	32KB	15KB	46.88%
33KB	64KB	31KB	48.44%
65KB	128KB	63KB	49.22%

요청 크기가 2^n + 1이면 2^(n+1) 블록이 할당되어 낭비율이 거의 50%에 이를 수 있다. 4KB, 8KB, 16KB, 32KB처럼 중간 크기를 선택할 수 없으므로 작은 객체를 직접 다루기에는 비효율적이다.

Slab Allocation은 버디 메모리에서 큰 블록을 받은 뒤, 이를 특정 크기 객체를 위한 캐시로 나누는 방식이다. 객체 단위로 할당하고 해제하므로 내부 단편화를 줄이고 빠른 재사용과 캐시 효과를 얻을 수 있다.

동작은 큰 슬랩을 버디 메모리에서 할당하고, 슬랩을 작은 객체로 분할한 뒤 객체 단위로 관리하는 흐름이다.

버디: 64KB 블록 할당
Slab: 64개의 1KB 객체 생성
할당: 정확히 1KB씩 할당 가능

리눅스 커널에서는 task_struct, inode 같은 커널 객체를 포함해 작은 객체를 관리할 때 이 방식을 활용한다.

리눅스 커널에서는 버디 메모리가 페이지 프레임 할당자와 GFP(Get Free Pages)에 쓰이며, Slab/SLUB/SLOB과 결합한다. 제한된 메모리를 다루는 임베디드 시스템과 실시간 OS에서는 예측 가능한 성능과 메모리 관리 특성이 유용하다.

가상화 환경에서는 게스트 OS 메모리 할당, 메모리 풍선(Ballooning), 동적 메모리 관리 경로에서 관련된다. 데이터베이스는 버퍼 풀 관리와 대량 메모리 할당, 빠른 할당·해제가 필요한 영역에서 이 구조를 활용할 수 있다.