외부·내부 메모리 단편화와 Paging

“단편화 0인 할당기”는 없다. 외부 단편화를 없애면 내부 단편화가 생기고, 내부 단편화를 없애면 메타데이터 비용이 붙는다. 이 글에서는 메모리 단편화를 정리하면서 페이지 폴트와 같은 뿌리에서 갈라져 나온 문제라는 걸 확인한 과정을 이야기하려 한다 — 외부와 내부 단편화가 각각 누구의 공간을 못 쓰게 만드는지, Paging이 무엇을 죽이고 무엇을 받아들였는지, 그리고 게임 엔진의 Frame·Pool·Arena 할당기가 공통으로 쓰는 회피 트릭이다.

메모리 단편화 — 페이지 폴트와 같은 뿌리에서

정리하면서 새로 잡힌 통찰만 압축해 남긴다.

외부 단편화 vs 내부 단편화 — 누가 못 쓰는 공간을 만드는가

항목	외부 단편화	내부 단편화
위치	블록과 블록 사이	한 블록 내부
누구의 공간?	누구의 것도 아님(free인데 작아서 못 씀)	이미 어떤 요청자에게 할당됨(여백)
원인	가변 크기 할당·해제 반복	크기 클래스·정렬 padding
해법 방향	합치거나(Compaction) 페이지로 추상화(Paging)	크기 클래스 세분화·전용 풀(Slab·Pool)
비유	주차장에 차들이 띄엄띄엄 — 큰 차가 못 들어옴	소형차가 대형 칸 점유 — 옆 공간 낭비

이 둘은 trade-off 관계. Paging은 외부 단편화를 구조적으로 없애지만 페이지 단위 정렬로 내부 단편화를 만든다. Slab은 내부 단편화를 거의 0으로 줄이지만 클래스별 메타데이터·캐시 오버헤드가 따라온다. “단편화 0인 할당기”는 존재하지 않고, 워크로드에 맞춰 한쪽 비용을 받아들이는 선택이 본질.

Paging이 외부 단편화를 구조적으로 없앤다는 발상

26번에서 “페이지 폴트는 매핑이 없을 때 OS 개입”이라고 했는데, 27번을 쓰면서 다시 보니 Paging의 본질적 동기가 외부 단편화 해결이라는 게 명확해졌다. 가변 크기 가상 영역을 고정 크기(4KB) 페이지로 잘게 쪼개 물리 메모리에 매핑하는 순간, 물리 단위의 외부 단편화는 정의상 사라진다 — 모든 페이지 프레임이 같은 크기니까 어떤 free 프레임이든 어떤 페이지든 받을 수 있다.

그 대가가 ——

1. 페이지 테이블·TLB 비용(25·26번에서 이미 다룸)
2. 페이지 단위 내부 단편화 — 4097바이트만 쓰는 영역도 페이지 2개(8KB) 점유. 마지막 페이지의 4095바이트는 못 씀
3. 페이지 폴트의 빈도 — demand paging은 첫 접근 시 매번 minor fault

26번과 27번을 묶어서 보면 — “OS는 외부 단편화를 Paging으로 죽이는 대신, 페이지 폴트와 페이지 단위 내부 단편화라는 새 비용을 받아들였다.” 이건 면접에서 두 주제를 잇는 한 줄로 쓰기 좋다.

Buddy System — 빠른 합병의 대가는 50% 내부 단편화

Linux 커널의 페이지 프레임 할당기. 2의 거듭제곱 크기 블록만 다루고 인접 buddy와 자동 분할·병합(coalescing).

핵심 메커니즘 — buddy 주소는 XOR로 계산 ——

크기 128B 블록의 buddy 주소 = 자기 주소 XOR 128
크기 256B 블록의 buddy 주소 = 자기 주소 XOR 256

이 XOR 트릭 덕분에 해제 시 buddy가 free인지 O(1)로 확인하고, free면 즉시 합쳐 더 큰 블록을 만든다. 재귀적으로 위로 올라가며 합치니까 외부 단편화 완화가 자동.

대가는 최악 50% 내부 단편화 ——

요청	할당	낭비
65바이트	128바이트	63바이트(48%)
129바이트	256바이트	127바이트(49%)
1025바이트	2048바이트	1023바이트(49%)

요청이 2의 거듭제곱 바로 위면 거의 절반이 버려진다. 그래서 Linux는 buddy 위에 Slab Allocator를 한 층 더 얹어 — buddy가 큰 페이지 청크를 주면 slab이 그걸 같은 크기 객체 슬롯으로 잘게 쪼개 내부 단편화를 회수한다. 두 알고리즘이 계층을 이루는 게 핵심.

언리얼 FMemory와 게임 메모리 패턴

UE5의 FMemory는 추상화 계층. 백엔드로 ——

• FMallocBinned2 — 크기 클래스별 bin 기반, 기본값
• FMallocTBB — Intel TBB(스레드 친화)
• FMallocJemalloc — 일부 플랫폼

게임 엔진이 범용 malloc을 거의 안 쓰고 패턴화된 할당기를 쓰는 이유는 단편화 회피 ——

패턴	동작	단편화 회피 메커니즘
Frame Allocator(Linear)	한 프레임 동안만 쓰고 프레임 끝에 통째로 reset	개별 free 없음 → 단편화 발생 불가
Pool Allocator	같은 크기·짧은 수명 객체(총알·파티클) N개 미리 잡고 재사용	같은 크기만 다루니 외부 단편화 0
Arena Allocator	범위 시작에 큰 블록 하나, 범위 끝에 한 번에 free	개별 free 없음 → 단편화 누적 불가

세 패턴의 공통점 — “개별 free를 안 한다”. free가 없으면 외부 단편화 자체가 발생할 수 없다는 게 핵심 통찰. 단편화는 “할당/해제 패턴이 정해진 시간 축을 따라 흩어질 때” 생기는 부산물이라, 그 시간 축을 제거(프레임·범위·풀)하면 단편화도 같이 사라진다.

콘솔(PS5·XSX)은 swap이 사실상 없어 단편화 누적 = OOM 크래시. 그래서 콘솔 인증(TRC/XR) 통과를 위해서는 메모리 풀과 워킹 셋 관리가 필수. PC만 만들 때 안 보이던 비용이 콘솔 포팅에서 첫 OOM 크래시로 드러나는 게 흔한 패턴이라고 정리.

---

정리 — 단편화를 보는 네 가지 시각

1. CS 26·27번을 묶는 한 문장 — “OS는 외부 단편화를 Paging으로 죽이는 대신, 페이지 폴트와 페이지 단위 내부 단편화를 받아들였다” — 26번 페이지 폴트와 27번 메모리 단편화는 별개 주제처럼 보이지만, Paging이라는 메커니즘이 두 주제를 가로지른다. 외부 단편화를 구조적으로 없애는 대가가 페이지 폴트와 페이지 단위 내부 단편화. 두 비용은 trade-off가 아니라 같은 설계 결정의 양면. 면접에서 두 주제를 잇는 흐름으로 사용 가능
2. Buddy + Slab의 계층 구조 — 각자의 약점을 위에서 보완 — Buddy는 빠른 합병 대신 최악 50% 내부 단편화. Slab은 내부 단편화 0이지만 같은 크기 객체에만 효과. Linux는 Buddy가 페이지 청크를 주고 Slab이 그걸 객체 슬롯으로 쪼개는 계층을 두어 두 약점을 동시에 잡는다. “단편화 0인 단일 할당기는 없다. 계층화로 약점을 상쇄한다”가 메모리 관리의 핵심 패턴
3. 게임 엔진 메모리 패턴의 공통 트릭 — “개별 free를 안 한다” — Frame Allocator(매 프레임 reset), Pool Allocator(같은 크기 재사용), Arena Allocator(범위 끝에 한 번에 free). 세 패턴 모두 개별 free 호출 자체를 없애 단편화가 발생할 시간 축을 제거. 단편화는 “할당·해제가 시간 축을 따라 흩어질 때” 생기는 부산물이라는 시각 변화
4. 콘솔의 단편화 비용은 PC와 차원이 다르다 — swap이 없다 — PC는 단편화로 큰 블록 부족 → 새 페이지를 OS에서 받음 → 워킹 셋 증가 → 캐시 미스↑·페이지 폴트↑ 정도. 콘솔(PS5·XSX)은 swap이 사실상 없어 단편화 누적이 곧 OOM 크래시. 콘솔 인증(TRC/XR)은 메모리 풀과 워킹 셋 관리가 필수. PC만 만들 때 안 보이는 비용이 콘솔 포팅에서 첫 OOM으로 터지는 게 전형

---

핵심 요약 — Paging은 외부 단편화를 구조적으로 없애는 대신 페이지 폴트와 페이지 단위 내부 단편화를 받아들인 설계라는 것. 그리고 게임 엔진의 Frame·Pool·Arena 할당기가 단편화를 피하는 공통 트릭은 “개별 free를 하지 않는다”는 한 가지다.