커널 메모리 할당자: 버디 시스템(Buddy System)과 슬랩(Slab) 할당 · 해설

난이도: 상

모범답안

1. 버디 시스템(Buddy Allocator)

커널은 물리 메모리를 2의 거듭제곱 크기 블록(order 0 = 1페이지, order 1 = 2페이지, … order n = 2ⁿ 페이지)으로 관리한다. 각 order마다 자유 블록 리스트를 둔다.

할당(split): 요청 크기를 만족하는 최소 order의 블록을 찾는다. 없으면 더 큰 order 블록을 반으로 쪼개(split) 내려온다. 예: order 3 요청인데 order 5만 있으면 5→4→4, 4→3→3 식으로 분할하며 나머지 반쪽(버디)을 각 order 리스트에 넣는다.
해제(coalesce): 블록을 반납할 때 버디(같은 크기의 짝, 주소가 블록 크기만큼 XOR로 정해지는 인접 블록)가 비어 있으면 둘을 합쳐 한 단계 큰 블록으로 만든다. 재귀적으로 병합해 큰 연속 블록을 복원한다.
버디의 정의: 크기 2ᵏ 블록의 버디 주소는 addr XOR (2ᵏ × 페이지크기). 이 정수 연산으로 짝을 O(1)에 찾는다.

버디는 연속 물리 블록을 빠르게 확보·병합해 외부 단편화를 완화한다. 대신 요청을 2의 거듭제곱으로 올림하므로 내부 단편화가 생긴다(예: 5페이지 요청 → 8페이지 할당, 3페이지 낭비).

2. 슬랩/슬럽 할당자

버디의 최소 단위는 페이지라, task_struct·inode·dentry 같은 작은 커널 객체를 페이지 단위로 받으면 낭비가 크다. 슬랩 할당자는 버디에서 페이지(들)를 받아 **같은 크기·같은 타입 객체들의 배열(slab)**로 잘게 나눠 관리한다.

객체 재사용: 객체를 free해도 초기화된 상태로 캐시에 남겨, 다음 할당 시 생성자 비용을 아낀다(구식 SLAB의 constructor/destructor 아이디어).
크기 클래스별 캐시: kmalloc-32, kmalloc-64… 처럼 크기별 캐시를 둬 같은 크기 요청을 그 캐시에서 처리 → 외부 단편화 억제.
per-CPU 캐시: CPU마다 지역 free 리스트를 둬 락 없이(또는 최소 경합으로) 할당해 멀티코어 확장성을 높인다(SLUB이 이 구조를 단순·효율화).
캐시 컬러링: slab마다 시작 오프셋을 조금씩 달리해 서로 다른 slab의 같은 오프셋 객체가 같은 캐시 라인/셋에 몰리는 걸 분산(캐시 충돌 완화).

계층 관계: 버디(페이지) → 슬랩(페이지를 객체로 분할) → 커널 코드. 큰 연속 메모리는 버디가, 작은 동일 크기 객체는 슬랩이 담당한다.

3. 내부 vs 외부 단편화

내부 단편화: 할당 단위가 요청보다 커서 블록 안이 낭비. 버디의 2의 거듭제곱 올림이 대표적.
외부 단편화: 자유 공간 총량은 충분한데 연속 공간이 없어 큰 요청을 못 채움. 가변 크기 할당에서 발생. 버디의 병합과 슬랩의 크기 클래스가 이를 억제한다.
요약: 버디는 외부 단편화를 병합으로 다루되 내부 단편화를 감수하고, 슬랩은 동일 크기 클래스로 외부 단편화를 억제한다.

4. 게임 서버 유저 공간에의 시사점

유저 공간 할당자 tcmalloc/jemalloc은 커널 아이디어를 그대로 차용한다: 크기 클래스(작은 요청을 몇십 개 버킷으로 반올림), per-thread/per-CPU 캐시(락 경합 회피), **아레나(arena)**로 스레드 간 분리. 큰 할당은 페이지 단위로 OS에서 직접 받는다.

게임 서버 설계 시사점:

오브젝트 풀/슬랩식 풀: 엔티티, 패킷 버퍼, 세션처럼 크기가 고정되고 수명이 짧은 객체는 슬랩처럼 미리 떼어 재사용하면 매 프레임 할당/해제 지터와 단편화를 없앤다.
크기 클래스 정렬: 자주 쓰는 버퍼를 캐시 라인/2의 거듭제곱에 맞추면 false sharing과 내부 단편화를 함께 관리할 수 있다.
per-thread 풀: 틱 처리 스레드마다 지역 풀을 두면 할당 경합이 사라진다(작업 훔치기 시 반환 스레드 교차 주의).
트레이드오프: 풀은 메모리를 선점(peak 기준 예약)하고, 크기 클래스는 내부 단편화를 받아들인다. 다형·가변 크기 객체엔 부적합하니 대상 객체를 선별해 적용한다.

핵심 요약