버디 시스템 (Buddy System) 할당기

핵심 인사이트 (3줄 요약)

본질: 버디 시스템(Buddy System) 할당기는 메모리를 요청받았을 때, 전체 물리 메모리를 무조건 2의 승수(2^k) 크기로만 반씩 쪼개어(Split) 할당하고, 반환될 때는 쪼개졌던 자신의 쌍둥이 조각(Buddy)과 초고속으로 병합(Coalescing)하는 커널 메모리 할당 기법이다.

가치: 일반적인 가변 분할 방식의 느린 탐색과 병합 오버헤드를 비트 연산 기반의 O(1) 초고속 병합으로 해결하면서, 고정 분할 방식의 장점(빠른 속도)과 가변 분할의 장점(유연성)을 황금비율로 융합했다.

융합: 비록 구조상 2의 승수로 올림 처리하느라 내부 단편화(Internal Fragmentation)가 발생하지만, 악성 외부 단편화(External)를 효과적으로 방어하여 오늘날 리눅스 커널(Linux Kernel)의 물리 페이지 프레임 할당을 담당하는 핵심 엔진으로 자리 잡았다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념: 버디 시스템은 메모리를 1MB, 512KB, 256KB 등 정확히 $2^k$ 크기의 블록들로만 유지 관리하는 동적 할당 알고리즘이다. 21KB를 요구하면 21KB를 잘라주지 않고 무조건 32KB($2^5$)를 할당해버린다. 프로세스가 종료되면, 이 32KB는 자신과 원래 한 몸이었던 '쌍둥이(Buddy) 32KB'가 비어있는지 확인하고 즉시 합쳐져 64KB로 퓨전(Fusion)한다.
필요성: 기존의 최적/최초 적합(Best/First-Fit) 알고리즘은 흩어진 빈 구멍을 합치기(병합) 위해 긴 연결 리스트 장부를 앞뒤로 스캔해야 했다. 이 오버헤드는 1분 1초가 급한 운영체제 커널의 심장부(커널 메모리 할당)에서는 치명적인 병목이었다. 외부 단편화로 메모리가 너덜너덜해지는 것을 막으면서도 "장부를 뒤질 필요 없이 빛의 속도로 병합하는 마법"이 절실했다.
💡 비유: 버디 시스템은 A4 용지를 반으로 접어 자르는 색종이 놀이와 같다. A4 한 장이 있다. 좀 작은 종이가 필요하면 반으로 잘라 A5 두 장(쌍둥이)을 만든다. 더 작은 게 필요하면 A5 하나를 잘라 A6 두 장을 만든다. 나중에 다 쓰고 A6를 반납할 때, 내 짝꿍 A6도 비어있으면 스카치테이프로 붙여 다시 A5로 부활시키는 완벽한 이진 트리(Binary Tree) 복구 시스템이다.
등장 배경 및 아키텍처 타협:
1. 가변 분할의 실패: 프로세스 크기(예: 13KB)에 딱 맞춰 잘라주었더니, 나중에 빈 공간을 합칠 때 옆집 주소가 뭔지 찾느라 CPU가 고통받았다.
2. 수학적 우회 (2의 승수): 공학자들은 "무조건 2의 승수로만 자르자"고 합의했다. 이렇게 하면 쪼개진 쌍둥이(Buddy)의 주소는 자신의 주소에서 비트(Bit) 1개만 뒤집으면(XOR 연산) 0.001초 만에 알아낼 수 있다.
3. 내부 단편화의 수용: 17KB를 요구하면 32KB를 줘야 하므로 무려 15KB의 내부 단편화가 버려진다. 하지만 외부 단편화 방어력과 초고속 런타임 속도를 얻기 위해 이 공간적 낭비를 쿨하게 지불(Trade-off)하기로 했다.

┌───────────────────────────────────────────────────────────────────┐
│           버디 시스템(Buddy System)의 쪼개기와 할당 시각화        │
├───────────────────────────────────────────────────────────────────┤
│                                                                   │
│ [ 초기 상태: 1024KB 통짜 메모리 하나 ]                            │
│ ┌─────────────────────────────────────────────────────┐           │
│ │ 1024KB (전체 텅 빈 공간)                               │        │
│ └─────────────────────────────────────────────────────┘           │
│                                                                   │
│ [ 100KB 프로세스 A 요청 발생 ]                                    │
│ 1. 100KB가 들어갈 가장 가까운 2의 승수는? → 128KB ($2^7$)         │
│ 2. 1024를 반으로 쪼갬 → 512, 512                                  │
│ 3. 512 하나를 반으로 쪼갬 → 256, 256                              │
│ 4. 256 하나를 반으로 쪼갬 → 128, 128 (원하던 크기 도달!)          │
│                                                                   │
│ ▶ 쪼개진 메모리 최종 결과:                                        │
│ ┌──────┬──────┬─────────────┬────────────────────────┐            │
│ │A:128 │빈 128│  빈방 256   │       빈방 512         │            │
│ └──────┴──────┴─────────────┴────────────────────────┘            │
│  (100KB사용)                                                      │
│  (28KB 내부단편화 낭비)                                           │
└───────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 버디 시스템은 마치 세포 분열처럼 동작한다. 100KB를 원한다고 100KB를 맞춰 주지 않는다. 무조건 128KB 방을 준다. 이 128KB 방의 짝꿍(Buddy)은 바로 옆에 있는 빈방 128KB다. 나중에 A가 종료되면, 이 두 128KB 방은 쌍둥이이므로 묻지도 따지지도 않고 결합하여 256KB로 복원된다. 이 '규격화된 쪼개기와 합치기'가 핵심 철학이다.

📢 섹션 요약 비유: 피자를 조각낼 때 무조건 반, 반의반, 반의반의 반으로만 자르는 칼잡이입니다. 손님이 애매한 크기를 원해도 무조건 한 조각 규격을 던져주어 부스러기 낭비(내부 단편화)는 생기지만, 나중에 남은 조각들을 다시 합쳐 동그란 피자를 만들기에는 세계 최고로 쉬운 방식입니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

버디(Buddy)의 수학적 조건

두 메모리 블록이 "버디(쌍둥이 짝꿍)"가 되려면 반드시 다음 세 가지 조건을 동시에 만족해야 한다.

크기가 정확히 똑같아야 한다. (예: 둘 다 64KB)
반드시 같은 큰 블록에서 분할되어 나온 형제여야 한다. (옆에 있는 64KB라도 부모가 다르면 합칠 수 없음)
물리적으로 인접해 있어야 한다.

이 조건 덕분에, 주소 A를 가진 크기 K의 블록의 짝꿍(Buddy) 주소는 하드웨어적으로 단 번의 비트 XOR 연산(A XOR K)으로 찾아낼 수 있다. (리스트 장부를 스캔할 필요가 전혀 없다!)

병합(Coalescing)의 연쇄 폭발 아키텍처

프로세스가 종료되어 메모리를 반환할 때, 버디 시스템의 진가가 폭발한다.

┌─────────────────────────────────────────────────────────────────────────────┐
│              버디 반환 시 연쇄 병합 (Domino Coalescing)                     │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│ [ 현재 상태 ]                                                               │
│ ┌──────┬──────┬─────────────┬────────────────────────┐                      │
│ │A:128 │빈 128│  빈방 256   │       빈방 512         │                      │
│ └──────┴──────┴─────────────┴────────────────────────┘                      │
│                                                                             │
│ [ 프로세스 A (128KB) 종료 및 반환 ]                                         │
│ 1단계: A가 나감. 내 짝꿍(빈 128)이 비어있네? 합체! → [빈 256] 생성.         │
│ 2단계: 새로 생긴 256의 짝꿍(빈 256)이 옆에 비어있네? 합체! → [빈 512] 생성. │
│ 3단계: 새로 생긴 512의 짝꿍(빈 512)이 옆에 비어있네? 합체! → [빈 1024] 복원!│
│                                                                             │
│ ▶ 결과: 1초도 안 되는 찰나의 3번 XOR 연산만으로                             │
│        잘게 찢어졌던 메모리가 완벽한 1024KB 통짜 블록으로 부활함!           │
└─────────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 가변 분할의 First-Fit이었다면 이 쪼개진 방들을 합치기 위해 메모리 주소를 비교하고 포인터를 갱신하느라 수십 사이클을 낭비했을 것이다. 버디 시스템은 마치 도미노가 쓰러지듯, 쌍둥이들이 비어있기만 하면 눈 깜짝할 사이에 최상위 거대 노드(Big Block)로 연쇄 융합한다. 이 강력한 '거대 블록 복원력' 덕분에 외부 단편화에 대한 내성이 극강으로 올라간다.

자료구조 (Free List Array)

버디 시스템을 구현하는 운영체제는 단 하나의 장부가 아니라, **크기별로 배열(Array of Linked Lists)**을 만들어 장부를 유지한다.

List[0]: 4KB 빈방들 모음
List[1]: 8KB 빈방들 모음
List[5]: 128KB 빈방들 모음 만약 128KB가 필요하면 List[5]를 열어보고, 없으면 List[6](256KB)에서 하나를 꺼내 반으로 쪼갠 뒤 128KB 하나는 할당하고 남은 128KB는 List[5]에 꽂아 넣는다. 탐색 속도는 철저하게 $O(1)$에 수렴한다.
📢 섹션 요약 비유: 물방울(메모리) 두 개가 만나면 순식간에 두 배 크기의 큰 물방울로 뽁! 하고 합쳐지는 슬라임 액체괴물 같은 구조적 유연성을 자랑합니다.

Ⅲ. 융합 비교 및 다각도 분석

비교 1: 일반 동적 할당(First/Best-Fit) vs 버디 시스템

비교 항목	일반 가변 분할 할당	버디 시스템 (Buddy System)
할당 단위	프로세스가 요구한 크기(바이트)에 정확히 맞춤	$2^k$ (2, 4, 8, 16...) 단위로 강제 반올림
내부 단편화	전혀 없음 (0%)	치명적임 (요구량에 따라 최대 49.9% 낭비)
외부 단편화	치명적 발생 (33% 낭비, OOM 유발)	병합이 너무 빨라 거대 구멍이 잘 복원됨 (우수)
탐색 및 병합	장부 스캔에 O(N) 시간 소요 (느림)	비트 연산을 통한 O(1) 초고속 병합 (극강의 속도)

극단적인 내부 단편화의 비극 (Trade-off)

버디 시스템의 유일하고도 치명적인 약점은 바로 '내부 단편화'다.

프로세스가 만약 33KB를 요청했다면?
버디 시스템은 가장 가까운 2의 승수인 64KB를 통째로 내어주어야 한다.
결과적으로 64 - 33 = 31KB가 그 방 안에서 아무도 쓰지 못한 채 공중으로 증발해버린다. (거의 50%의 내부 단편화)
공학자들은 이 거대한 공간적 손실을 감수하고서라도, 커널 레벨에서는 '탐색/병합 속도 보장'과 '큰 블록의 외부 단편화 파괴 방어'가 훨씬 더 갚지다고 판단했다.

┌──────────┬────────────┬────────────┬──────────────────────────────────┐
│ 최적화 포인트│ 가변 분할(동적)│ 페이징(가상)  │ 버디 시스템(커널)     │
├──────────┼────────────┼────────────┼──────────────────────────────────┤
│ 속도 확보  │ ❌ 느림      │ 🟡 TLB 필요 │ 🟢 비트연산 초고속          │
│ 단편화 방어 │ ❌ 둘 다 뚫림 │ 🟢 외부 방어 │ 🟡 외부는 강함, 내부 약함│
│ 주 적용처  │ 낡은 OS, User앱│ OS 논리 주소 │ OS 커널 물리 메모리      │
└──────────┴────────────┴────────────┴──────────────────────────────────┘

[매트릭스 해설] 범용 유저 애플리케이션에서는 버디 시스템을 거의 쓰지 않는다. 메모리 낭비가 너무 심하기 때문이다. 하지만 하드웨어와 가장 가까운 OS 커널(리눅스)은 디바이스 드라이버나 커널 자료구조를 띄우기 위해 "반드시 물리적으로 연속된" 메모리 조각이 필요하다(페이징의 가상 주소 가라치기가 안 통함). 이 물리적 연속 공간을 가장 빠르고 파편화 없이 잘라주는 유일한 해답이 버디 시스템이었다.

📢 섹션 요약 비유: 3만 1천 원짜리 물건을 사는데 잔돈 깎아주기 귀찮다고 5만 원을 내고 거스름돈을 안 받는 쿨한 재벌(내부 단편화 낭비)입니다. 돈은 낭비하지만 계산하는 시간(스캔 속도)은 빛처럼 빠릅니다.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오: Linux 커널의 Page Frame 할당 (Zone Allocator)

상황: 리눅스 커널이 부팅될 때 16GB 물리 메모리를 관리해야 한다. 리눅스는 메모리를 4KB 크기의 '페이지 프레임' 단위로 쪼갠다.
리눅스 커널의 선택:
- 리눅스 커널은 물리 프레임을 나눠줄 때 바로 이 버디 시스템 알고리즘을 심장 엔진으로 사용한다.
- 4KB 프레임을 기본 단위(Order 0)로 하여, 1개(4KB), 2개(8KB), 4개(16KB), 8개, ..., 최대 1024개(4MB, Order 10)의 연속된 페이지 프레임을 2의 승수 단위로 묶어서 free_area 배열(장부)에 보관한다.
디바이스 드라이버의 요청:
- 네트워크 랜카드 드라이버가 DMA 버퍼용으로 연속된 물리 메모리 15KB를 커널에 요청(kmalloc)한다.
- 커널 버디 시스템은 "15KB? 오케이 16KB(Order 2, 프레임 4장) 블록 던져줄게!" 하고 $O(1)$ 속도로 잘라서 던져준다.
- 이 견고한 버디 할당기 덕분에 리눅스 서버는 수백 일 동안 켜져 있어도 커널 영역의 물리적 외부 단편화로 죽는 일이 거의 발생하지 않는다.

슬랩(Slab) 할당기와의 완벽한 공조 (커널의 투트랙)

버디 시스템이 내부 단편화(33KB 요청 시 64KB 줌)로 메모리를 너무 심하게 버리는 문제를 보완하기 위해, 리눅스는 버디 시스템 위에 **슬랩 할당기(Slab Allocator)**를 이중으로 얹었다.

거대한 땅(수십 KB 단위)은 버디 시스템이 큼직하게 잘라주고,
그 땅 안에서 작은 오브젝트(수십 Byte 단위)들은 슬랩 할당기가 현미경처럼 잘게 썰어서 나누어준다.
이 버디-슬랩 콤보는 커널 메모리 관리의 완성형으로 불린다. (다음 키워드에서 상세 서술)
📢 섹션 요약 비유: 고기를 손질할 때 거대한 도끼(버디 시스템)로 소의 뼈대에 맞춰 큼직한 덩어리로 쳐낸 다음, 셰프의 정밀한 회칼(슬랩 할당기)로 손님 입에 쏙 들어갈 크기로 썰어내는 완벽한 이중 분업 시스템입니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

정량/정성 기대효과

구분	내용
메모리 할당/해제 O(1) 달성	수학적 비트 XOR 연산과 배열 인덱싱을 통해 탐색 루프 없이 가장 빠른 커널 속도 보장
외부 단편화 내성	해제 즉시 도미노처럼 거대 블록으로 융합(Coalescing)되어 물리적 덩어리가 쪼개진 채 방치되는 현상 억제
연속된 물리 메모리 보장	DMA 장치나 하드웨어 드라이버가 필수적으로 요구하는 '물리적으로 이어져 있는 램 공간'을 안정적으로 제공

결론 및 미래 전망

버디 시스템 (Buddy System) 할당기는 "어떻게 하면 가장 완벽하게 딱 맞춰 자를까(Best-Fit)"를 포기하고 "어떻게 하면 가장 빠르고 쉽게 원상 복구시킬까"로 철학적 방향을 전환한 위대한 알고리즘이다. 무조건 2의 배수로 자른다는 단순 무식한 규칙 하나가 끔찍했던 장부 스캔의 오버헤드를 비트 연산의 우아함으로 승화시켰다. 50%에 달하는 엄청난 내부 단편화라는 대가를 치르면서도 수십 년간 리눅스 커널의 최하단 코어 엔진 자리를 지키고 있다는 사실은, 소프트웨어 공학에서 '예측 가능한 빠른 속도'와 '단편화 복원력'이 얼마나 압도적인 가치인지를 증명하는 살아있는 역사다.

📢 섹션 요약 비유: 부서진 도자기 조각을 풀로 이어 붙이는 고통(압축/병합)을 겪느니, 아예 처음부터 블록들을 레고처럼 규격화(2의 승수)시켜놔서 눈 감고도 1초 만에 조립과 해체를 할 수 있게 만든 하드웨어적 타협의 예술입니다.

📌 관련 개념 맵 (Knowledge Graph)

내부 단편화 (Internal Fragmentation) | 버디 시스템이 2의 승수로 무조건 올림 할당을 하면서 발생하는 가장 치명적인 부작용 공간 낭비
병합 (Coalescing) | 조각난 메모리가 반환될 때 쌍둥이(Buddy)와 합쳐지는 과정으로, 버디 시스템이 세계에서 가장 빠름
슬랩 할당기 (Slab Allocator) | 버디 시스템이 유발하는 내부 단편화 낭비를 커버하기 위해 그 위에 얹어서 작은 객체를 캐싱하는 2차 할당기
가변 분할 방식 (Variable Partition) | 버디 시스템의 뼈대가 되는 연속 메모리 동적 할당 아키텍처
XOR 비트 연산 | 내 짝꿍(Buddy) 메모리 블록의 시작 주소를 장부 검색 없이 1클럭만에 찾아내는 수학적 마법

👶 어린이를 위한 3줄 비유 설명

버디 시스템이 무엇인가요? 거대한 초콜릿을 친구들과 나눌 때, 무조건 반으로 쪼개고, 또 반으로만 쪼개서 나눠주는 아주 공평하고 단순한 규칙이에요.
왜 딱 맞춰 안 자르나요? 친구가 조금만 달라고 해서 이상한 모양으로 딱 맞춰 자르면, 나중에 친구가 남긴 조각들을 다시 합쳐서 원래의 네모난 초콜릿으로 되돌리기가 너무 힘들거든요.
어떤 효과가 있나요? 무조건 반으로만 잘랐기 때문에, 친구가 다 먹고 남은 조각을 돌려주면 원래 붙어있던 짝꿍 조각과 1초 만에 착! 하고 붙여서 다시 큰 네모로 완벽하게 복구할 수 있답니다.