메모리 단편화 최적화 총정리 — Buddy Allocator까지 한 번에
malloc/free 힙 관리에서 단편화를 줄이는 핵심 설계들과 Buddy 알고리즘의 작동 원리/구현 포인트를 정리합니다.
1) 단편화(내부/외부) 한눈에 이해
- 외부 단편화: 빈 공간 총합은 충분한데 연속 블록이 부족해서 큰 할당이 실패하는 현상.
- 내부 단편화: 요청보다 큰 블록을 제공하거나 정렬/헤더 때문에 블록 내부에서 낭비되는 공간.
예) [free 10][used 8][free 10] → 총 free=20, but 16바이트 연속 블록이 없어 실패2) 단편화 최적화 툴킷
- Split: 큰 free 블록을 잘라 요청 크기만큼 할당, 나머지는 free로 유지.
- Coalesce: free 시 인접 free 블록을 병합해 큰 블록 유지.
- 헤더/바운더리 태그: 블록 앞/뒤에 size, alloc 비트 저장 → 인접 블록 상태 확인, O(1) 병합.
- 주소순 free-list: free-list를 주소순으로 유지하면 병합 판단이 단순해짐.
- 크기별 분리 리스트 (segregated): 자주 쓰는 크기는 전용 리스트로 탐색/파편화 감소.
- 고정 크기 캐시 (slab): 동일 타입 객체를 고정 크기 캐시에서 관리 → 내부 단편화/초기화 비용 절감.
- Buddy: 2^k 크기만 사용해 split/merge를 규칙적으로 수행 → 외부 단편화 억제 & 빠른 병합.
3) Segregated-fit / Slab
Segregated-fit
크기 클래스를 미리 정의(예: 8,16,32,64, …)하여 크기별 free-list로 관리. 탐색 범위가 작아져 빠르고, 자주 쓰는 크기에서 외부 단편화가 줄어듭니다. 남는 부분을 split해 인접 클래스로 넘기면 내부 단편화도 일정 수준으로 제한됩니다.
Slab (고정 크기 객체)
커널/서버에서 특정 구조체를 반복적으로 할당/해제할 때 유리. 슬랩(페이지 단위) 안을 동일 크기의 슬롯들로 나누고, 초기화 상태를 캐시하여 할당/해제의 오버헤드와 내부 단편화를 낮춥니다.
[Slab: 1 page]
| obj | obj | obj | obj | ... | → 동일 크기 슬롯, 빠른 할당/해제, CPU 캐시 친화
4) Best/First/Next-fit + Coalesce 전략
- First-fit: 처음 만난 충분히 큰 블록. 빠르지만 초반부가 조각날 수 있음.
- Next-fit: 이전 탐색 위치 이후부터 검색. 파편 분산 기대.
- Best-fit: 가장 근접한 크기의 블록. 내부 단편화 감소 기대, 탐색 비용↑, 작은 파편 가능.
코어 포인트: 어떤 fit을 써도 coalesce 정책(즉시/지연), free-list 정렬(주소/크기), boundary tag의 유무가 단편화/성능에 큰 영향을 줍니다.
5) Buddy Allocator 깊게 보기
5-1) 핵심 아이디어
- 블록 크기를 2^k로만 유지. (최소 주문
order_min, 최대 주문order_max) - 할당은 요구 크기 이상인 가장 작은 2^k 블록으로 round-up 후, 맞는 크기가 나올 때까지 반으로 분할(split).
- 해제는 같은 order의 버디가 free면 즉시 병합(merge)하여 상위 order로 큼지막하게 만든다.
5-2) 버디 찾기 (주소 XOR 규칙)
베이스 주소를 0으로 가정하면, order k 블록의 크기는 size = 1 << k이고, 한 블록의 시작 주소 addr에 대해 버디는:
buddy = addr XOR size (또는 buddy = addr ^ (1 << k))즉, 해당 크기 비트(2^k 자리)를 토글하면 이웃 버디의 시작 주소가 됩니다. 시작 주소가 그 크기 배수인지(정렬) 확인이 중요합니다.
5-3) 자료구조
- free-lists[order]: 각 order별로 이중 연결 리스트(또는 단순 리스트)로 free 블록을 관리.
- 각 free 노드는 블록 시작 주소만 있으면 충분(헤더에 size/order와 링크 포인터 저장).
- O(1)에 수록/삭제가 가능하고, 버디 주소 계산으로 병합 여부 판단도 O(1).
5-4) 할당 절차 (의사코드)
// 요청 n 바이트
n' = roundup_pow2(max(n + header, MIN_BLOCK)) // 2^k 반올림
k = order_of(n')
for o in range(k, MAX_ORDER+1):
if free_list[o] not empty:
// o에서 블록 하나 꺼내고 k가 될 때까지 반으로 쪼갠다
blk = pop(free_list[o])
while o > k:
o -= 1
split = blk + (1 << o) // 절반 주소
push(free_list[o], split) // 한 쪽은 free-list에 반환
// blk는 남겨 계속 쪼갬
return blk + header_size
// 여기까지 없으면 힙 확장 or 실패
5-5) 해제 절차 (의사코드)
blk = user_ptr - header_size
o = order_of(blk) // 헤더에서 order 읽기
addr = start_of(blk)
while o <= MAX_ORDER:
buddy = addr ^ (1 << o)
if buddy is free in free_list[o]:
// buddy 제거 후 병합
remove(free_list[o], buddy)
addr = min(addr, buddy)
o += 1 // 상위 order로 승격
else:
break
push(free_list[o], addr)
5-6) 예시 (간단 시각화)
전체 풀: 2^4 = 16바이트 (order=4)
[16]
8바이트 요청 → 8로 round-up
[8][8] // split 한 번
<- 할당
다시 8바이트 free → 인접 buddy(다른 [8])도 free면 merge:
[16] // 재병합 성공
5-7) 장단점
| 장점 | 단점 |
|---|---|
| O(1)에 가까운 빠른 split/merge (버디 계산, 주소 정렬) | 2^k 제한으로 내부 단편화 증가(최대 낭비 < 2배) |
| 병합(코얼레스)이 단순하여 장기 외부 단편화 억제 | 요청 분포가 “애매한 크기”에 몰리면 효율 저하 |
| 크기별 free-list로 탐색 비용 낮음 | 헤더/메타데이터, 정렬 제약으로 약간의 오버헤드 |
5-8) 내부 단편화 상한
요청 크기 n을 2^k로 반올림할 때, 낭비는 < 2^k − n. 최악 비율은 거의 50% 부근까지 나올 수 있습니다. 단, 실제 워크로드에서 자주 쓰는 크기를 별도 segregated로 빼거나, 작은 크기만 buddy에 태우는 식으로 보완합니다.
5-9) 변형/개선
- Hybrid: 소형 크기는 segregated-list/슬랩, 중대형은 buddy.
- Lazy coalesce: 즉시 병합 대신 필요할 때 병합해 캐시 지역성↑.
- Bitmap buddy: free-list 대신 비트맵으로 상태 관리(캐시 친화/간결).
6) Buddy vs Segregated vs 일반 Free-list
| 기법 | 탐색 속도 | 외부 단편화 | 내부 단편화 | 베스트 케이스 | 워스트/주의 |
|---|---|---|---|---|---|
| Buddy | 빠름 (O(1) 수준) | 낮음(병합 쉬움) | 높을 수 있음 (2^k 제약) | 다양 크기 균형, 병합 잦은 워크로드 | 요청이 2^k 경계에 애매하면 낭비↑ |
| Segregated/Slab | 매우 빠름 | 작은 크기에서 매우 낮음 | 작은 고정 크기는 낮음 | 자주 쓰는 크기가 뚜렷함 | 희귀 크기 분포엔 별도 백업 전략 필요 |
| Free-list(First/Best-fit) | 중간~느림(탐색 비용 큼) | coalesce에 따라 좌우 | 클래스 없으니 중간 | 간단한 구현, 다양한 크기 유연 | 탐색/병합 정책 미흡 시 장기 파편화 |
7) 구현 체크리스트
- 헤더: size/order, alloc 비트, (옵션) 가드(magic)/체크섬.
- 정렬: 페이지/캐시라인/아키텍처 정렬 요구를 만족.
- coalesce: boundary tag 또는 buddy XOR 규칙으로 O(1) 병합.
- zeroing/INIT: 보안/안정성 요구 시 할당/해제 시 초기화 정책.
- 성능 계측: 평균/최대 탐색 길이, split/merge 횟수, 내부/외부 단편화 지표 추적.
- 하이브리드: 소형(슬랩/segregated) + 중대형(buddy/페이지) 조합 고려.
- 확장/반납: 메모리 부족 시 힙 확장(sbrk/mmap), 장기 유휴 블록은 OS 반납(munmap) 여부.
// Buddy에서 자주 쓰는 계산 요약
size(k) = 1 << k
order(n) = ceil_log2( max(n + header, MIN_BLOCK) )
buddy(a,k)= a ^ (1 << k)
merge 조건: (buddy free) && (둘 다 같은 order) → 상위 order로 승격