다단계 페이지 테이블 사이즈 줄이기

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

본질: 페이징 시스템의 가장 큰 부작용은 가상 주소 공간이 커질수록(32비트 $\rightarrow$ 64비트) 메모리를 매핑하기 위한 '페이지 테이블(지도)' 자체가 수십 MB에서 수백 GB까지 커져, 정작 유저 프로그램이 쓸 메모리(RAM)를 지도가 다 잡아먹는 배보다 배꼽이 큰 사태가 터진다는 점이다.

메커니즘 (다단계/Hierarchical): 이를 막기 위해 페이지 테이블을 책의 '목차'처럼 2단계, 3단계, 4단계로 쪼갠다. 가장 핵심인 대목차(Root Directory)만 메모리에 항상 올려두고, **실제 사용하지 않는 빈 가상 메모리 구역의 하위 페이지 테이블은 아예 메모리에 생성조차 하지 않는 동적 할당(Dynamic Allocation)**이 가능해진다.

트레이드오프: 다단계 페이징은 물리 메모리 낭비를 극적으로(99% 이상) 줄여주지만, 페이지 테이블을 4번 쪼개면 주소를 한 번 찾을 때 램을 4번이나 읽어야 하는 **메모리 접근 지연(Page Walk Overhead)**을 낳는다. 이를 하드웨어 TLB 캐시로 덮고(Cover) 있는 것이 현대 OS의 현실이다.

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

개념:
- 1단계 (단일) 페이지 테이블: 가상 주소의 페이지 개수만큼 무조건 배열(Array)의 칸을 다 만들어두는 1차원 구조.
- 다단계 페이지 테이블 (Multi-level Paging): 페이지 테이블을 여러 계층(Directory $\rightarrow$ Middle $\rightarrow$ Table)으로 트리(Tree)처럼 나누어 관리하는 구조.
필요성 (메모리 폭발의 공포):
- 32비트 시스템에서 가상 메모리 크기는 4GB다. 페이지 크기가 4KB면 총 100만 개의 페이지가 나온다.
- 페이지 번호를 적어두는 엔트리 1개가 4바이트라고 하면, **프로세스 1개당 "순수 페이지 테이블 용량"만 딱 4MB(100만 * 4바이트)**가 필요하다.
- 프로세스를 1,000개 띄우면? 지도(Table) 크기만 4GB가 되어 물리 램이 터져버린다.
- 심지어 프로세스는 보통 코드, 데이터, 스택만 쓰므로 4GB 가상 주소 중 99%는 텅텅 비어있는데(Sparse Address Space), 1단계 테이블은 이 안 쓰는 99%의 주소록 칸도 무조건 만들어둬야 했다.
- 해결책: "안 쓰는 구역의 지도는 아예 만들지 말자!" 목차(Directory)만 만들어두고, 진짜로 그 동네에 아파트(메모리)를 지을 때만 그 동네의 상세 지도(Page Table)를 메모리에 올리자는 아이디어가 나왔다.
💡 비유:
- 1단계 페이징 (종이 지도책): 전 세계 모든 골목길 지도가 담긴 두꺼운 책을 들고 다닌다. 내가 평생 한국 밖을 나갈 일이 없는데도, 아프리카 사하라 사막의 골목길 지도(빈 공간)까지 억지로 들고 다녀야 해서 가방(RAM)이 무거워 터진다.
- 다단계 페이징 (인터넷 지도 앱): 내 폰에는 전 세계 '국가 목록(1단계 Root)'만 있다. 내가 "한국"을 누르면 "한국의 시/도 지도(2단계)"만 다운받는다. 내가 아프리카를 갈 일이 없으면 아프리카 지도는 평생 폰(RAM)에 다운받을 일이 없다. 가방이 텅텅 비고 가벼워진다.
발전 과정:
1. 1-Level Paging: 16비트 시절, 메모리가 작아 가능했음.
2. 2-Level Paging: 32비트(x86) 환경의 표준. (Page Directory + Page Table)
3. 4-Level Paging: 64비트(x86-64) 환경. 가상 주소가 너무 방대해져 4단계로 쪼갬.
4. 5-Level Paging: 테라바이트급 서버를 위해 인텔 Ice Lake부터 도입된 최신 구조.
📢 섹션 요약 비유: 두꺼운 백과사전(페이지 테이블)을 통째로 펴놓고 보는 대신, 목차만 책상에 올려놓고 필요할 때만 서고에서 해당 챕터의 낱장만 빼오는 궁극의 메모리 다이어트 기술입니다.

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

32비트 시스템의 2단계 페이징 아키텍처 (x86 기준)

논리 주소 32비트를 어떻게 쪼개서 테이블 사이즈를 줄이는지 수학적으로 분해한다.

논리 주소 분할 (10 + 10 + 12 = 32비트):
- p1 (10 bits): Page Directory Index (대목차 번호)
- p2 (10 bits): Page Table Index (소목차 번호)
- d (12 bits): Offset (4KB 페이지 내의 정확한 번지)

  ┌───────────────────────────────────────────────────────────────────┐
  │                 2단계 페이징을 통한 "메모리 다이어트" 동작 원리          │
  ├───────────────────────────────────────────────────────────────────┤
  │                                                                   │
  │  [ CR3 레지스터 ] ──▶ [ 1단계: Page Directory (항상 RAM에 있음) ]       │
  │                       (1024칸 * 4Byte = 딱 4KB 크기!)                 │
  │                                                                   │
  │                       [ 0번 칸 (Code 영역) ] ───▶ [ 2단계 Page Table 0 ]│
  │                       [ 1번 칸 (텅 빔) ]      ───▶ (NULL! 메모리 할당 안 함)│
  │                       [ 2번 칸 (텅 빔) ]      ───▶ (NULL! 메모리 할당 안 함)│
  │                       ...                                         │
  │                       [ 1023번 칸 (Stack) ]  ───▶ [ 2단계 Page Table X ]│
  │                                                                   │
  │  ★ 기적의 결과:                                                       │
  │   - 1단계 페이징이었다면 무조건 [ 4MB ]의 지도가 램에 있어야 했다.              │
  │   - 2단계 페이징에서는 Code용 테이블(4KB) + Stack용 테이블(4KB) +             │
  │     Root 디렉터리(4KB) = 고작 [ 12KB ]면 지도를 완벽하게 그릴 수 있다!!        │
  │   - 약 99.7%의 메모리 공간 절약 (Memory Saving) 성공!                 │
  └───────────────────────────────────────────────────────────────────┘

[다이어그램 해설] "어? 쪼개면 4MB 덩어리가 1024개 생기니까 총 용량은 오히려 $4KB + 4MB$로 더 커지는 거 아니야?" 라고 묻는다면 반만 맞다. 만약 프로세스가 4GB 가상 메모리를 1바이트도 안 남기고 100% 꽉 채워 쓴다면, 2단계 페이징이 1단계보다 오히려 용량을 더 먹는다. 하지만 현실의 프로그램은 가상 메모리의 1%도 쓰지 않는 듬성듬성한(Sparse) 구조다. 중간에 텅 비어있는 99%의 가상 공간에 대해서는 아예 2단계 테이블(4KB)을 malloc 해주지 않기 때문에, 현실 세계에서는 기적적인 압축 효과가 나타나는 것이다.

역방향 페이지 테이블 (Inverted Page Table)

다단계로 쪼개도 64비트 환경에서는 너무 벅차다. 발상을 180도 뒤집은 아키텍처다.

원리: 기존 방식은 "프로세스마다" 가상 주소 지도를 가졌다. 역방향 방식은 **"시스템 전체에 딱 1개의 물리 램(RAM) 지도"**만 둔다.
크기: 램이 16GB고 프레임이 4KB면, 테이블 크기는 프로세스가 1만 개든 10만 개든 상관없이 무조건 4백만 칸(약 16MB)으로 영구 고정된다.
검색 방식: 가상 주소 p를 주면, 이 테이블의 꼭대기부터 끝까지 훑으면서 "지금 이 프레임 안에 가상 주소 p를 쓰는 프로세스가 있나?"를 $O(N)$으로 뒤져서 프레임 번호를 역산한다. 검색이 너무 느리므로 보통 **해시 테이블(Hash Table)**을 결합하여 속도를 보완한다. (PowerPC, IA-64 등에서 제한적 사용)
📢 섹션 요약 비유: 다단계 페이징이 "주민등록번호(가상)를 주면 집 주소(물리)를 찾아주는 책"이라면, 역 페이지 테이블은 "전국 집 주소록(물리)을 펴놓고, 그 집에 사는 사람 이름(가상)을 찾는 짓"입니다. 책이 딱 한 권이라 공간은 엄청 적게 차지하지만, 찾을 때 숨이 넘어갑니다.

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

페이징 테이블 사이즈 최적화 기법 3대장

기법	장점 (메모리 관점)	단점 (속도 관점)	적용 분야
다단계 페이징 (Hierarchical)	안 쓰는 테이블을 동적 할당하여 극적인 메모리 절약	번역 단계가 깊어져 Page Walk 지연($O(depth)$)	모든 현대 PC / 서버 OS 표준
해시 페이지 테이블 (Hashed)	64비트 주소 공간에서 테이블 크기를 해시 충돌 수준으로 억제	해시 충돌(Collision) 해결을 위한 체이닝(Chaining) 탐색 지연	주소 공간이 극도로 큰 시스템
역방향 페이지 테이블 (Inverted)	프로세스 수와 무관하게 시스템 램 크기에만 비례 (최소 공간)	주소를 역으로 찾아야 해서 극단적인 탐색 시간 $O(N)$ 소모	일부 특수 아키텍처

과목 융합 관점

컴퓨터구조 (CA) - Memory Wall: 다단계 페이징은 메모리 용량 부족 문제를 해결했지만, '메모리 장벽'이라는 재앙을 불렀다. 4단계 페이징(x86-64)에서 TLB Miss가 나면, CPU는 진짜 데이터 1번을 읽기 위해 RAM(Root $\rightarrow$ Dir $\rightarrow$ Mid $\rightarrow$ PT)을 무려 4번이나 추가로 다녀와야 한다(Page Walk). 평소 100ns 걸리던 메모리 접근 시간이 순간적으로 500ns로 뛰어버린다.
TLB의 절대적 권력: 이 5배의 지연을 막는 유일한 구원자가 바로 CPU 내부의 캐시인 TLB다. 다단계 페이징이 실전에서 쓸만한 이유는, TLB 적중률(Hit Ratio)이 99%를 넘기 때문에 "어차피 100번에 1번만 Page Walk를 갈 거면 이 정도 손해(Trade-off)는 감수하자"는 하드웨어와 소프트웨어의 도박이 성공했기 때문이다.
📢 섹션 요약 비유: 짐(페이지 테이블)을 줄이기 위해 택배를 4번 갈아타는 끔찍한 국도(다단계 페이징)를 만들었습니다. 하지만 우리가 평소에 타고 다니는 하이패스 직통 고속도로(TLB)가 워낙 빵빵해서, 1년에 한두 번 국도를 탈 때의 짜증 정도는 가볍게 눈감아 주고 있는 상황입니다.

Ⅳ. 실무 적용 및 기술사적 판단

실무 시나리오

시나리오 — 클라우드 OOM(Out Of Memory) 킬러의 숨겨진 주범 (Page Table Bloat): Node.js/Python 기반의 웹 크롤러 프로세스 1,000개를 도커로 띄웠다. 프로세스당 실제 사용하는 메모리는 10MB밖에 안 되는데, 노드의 32GB 램이 꽉 차서 OOM이 났다.
- 원인 분석: cat /proc/meminfo | grep PageTables를 쳐보니, 페이지 테이블 자체가 10GB를 먹고 있었다! 다단계 페이징이라 할지라도, 프로세스를 너무 많이(1,000개) 띄우거나, 가상 메모리 공간 이곳저곳(힙 끝, 스택 끝, mmap 공간)에 산발적으로(Fragmentation) 데이터를 할당하면 그 성긴 공간들을 매핑하기 위해 2단계, 3단계 페이지 테이블들이 무수히 동적 할당되어 메모리 누수 뺨치는 오버헤드를 낳는다 (Page Table Bloat).
- 대응 (아키텍처 적용): 쓸데없이 멀티프로세스로 띄우지 말고, 주소 공간(CR3) 하나를 공유하는 **멀티스레드(Multi-Thread)**나 비동기 이벤트 루프(Coroutines) 모델로 아키텍처를 변경해야 한다. 스레드는 페이지 테이블을 100% 공유하므로 스레드가 1,000개 떠도 페이지 테이블 용량은 1개분(수 MB)으로 완벽하게 다이어트된다.
시나리오 — 데이터베이스(Oracle, SAP HANA) 성능을 위한 Huge Page 도입: 위의 문제와 정반대로, 페이지 테이블이 너무 많아서 TLB 캐시 미스가 폭발하고 시스템 성능이 안 나온다.
- 해결책 (Huge Pages): 리눅스 커널의 기본 페이지(4KB) 대신 **2MB (Huge Page)**를 적용한다.
- 다단계 테이블 파괴 효과: 2MB 페이지를 쓰면 x86-64의 4단계 페이징 트리에서 마지막 4단계 테이블(PTE) 층이 아예 사라져 버리고 3단계(PMD)에서 끝난다. 주소 번역 단계가 1단계 줄어들어 Page Walk 속도가 25% 빨라지며, 1,000개의 매핑을 기억해야 할 테이블이 2개로 압축되므로 페이지 테이블 자체가 먹는 메모리 용량(Bloat)도 기적적으로 줄어든다. 거대 서버 엔지니어링의 치트키다.

의사결정 및 튜닝 플로우

  ┌───────────────────────────────────────────────────────────────────┐
  │                 메모리 테이블 오버헤드 최적화 아키텍처 플로우              │
  ├───────────────────────────────────────────────────────────────────┤
  │                                                                   │
  │   [서버 튜닝 중, 페이지 테이블 용량과 TLB 미스로 인한 병목 발견]              │
  │                │                                                  │
  │                ▼                                                  │
  │      가상 메모리를 너무 넓게 휘저어 쓰는(Sparse) 프로세스들이 수만 개 떠 있는가? │
  │          ├─ 예 ─────▶ [멀티프로세스 -> 멀티스레드 아키텍처 전환]       │
  │          │            (스레드 간 페이지 테이블 공유로 테이블 용량 오버헤드 박살냄)│
  │          └─ 아니오 (거대한 프로세스 1개가 수백 GB를 통째로 쓰고 있다)       │
  │                │                                                  │
  │                ▼                                                  │
  │      [Huge Page(2MB / 1GB) 튜닝 강력 권고]                           │
  │      - 효과 1: 다단계 트리의 높이(Depth)가 1~2계층 줄어 탐색 속도 증가.  │
  │      - 효과 2: 페이지 테이블 자체가 점유하는 커널 메모리 용량이 1/500로 극감.│
  └───────────────────────────────────────────────────────────────────┘

[다이어그램 해설] "메모리 32GB 꽂았는데 왜 부족하지?"라고 할 때, 개발자들은 자기 앱의 User Space 메모리릭만 의심한다. 시스템 아키텍트는 Kernel Space에 숨어있는 Page Table이라는 거대한 괴물을 볼 줄 알아야 한다. 이 괴물은 프로세스가 늘어날수록 조용히, 그러나 기하급수적으로 서버의 피(RAM)를 빨아먹는다.

도입 체크리스트

KSM (Kernel Samepage Merging): 수백 개의 가상머신(VM)을 띄우는 KVM 클라우드 환경에서, 각 VM이 윈도우 OS를 띄우느라 들고 있는 똑같은 내용의 페이지들(DLL 등)을 백그라운드 스레드가 스캔하여 물리 프레임 하나로 합치고(Merge) 다단계 페이지 테이블 포인터를 하나로 모아주어 물리 램을 엄청나게 절약해 주는(Overcommit) KSM 데몬을 활성화했는가?
📢 섹션 요약 비유: 수만 권의 책(메모리)을 관리하려고 두꺼운 엑셀 장부(단일 페이지 테이블)를 만들었더니 장부 놓을 자리도 부족해졌습니다. 그래서 장부를 카테고리별 작은 수첩(다단계)으로 나누고, 아예 책들을 두꺼운 합본(Huge Page)으로 묶어버리거나 같은 책은 하나로 합쳐버려서(KSM) 장부 관리를 편하게 만든 도서관의 진화입니다.

Ⅴ. 기대효과 및 결론

정량/정성 기대효과

구분	1단계 (단일) 페이지 테이블	다단계 (Hierarchical) 페이지 테이블	개선 효과
정량 (테이블 크기)	32비트 기준 무조건 프로세스당 4MB 할당	사용하는 양에 비례해 수 KB~MB 동적 할당	OS 커널 메모리 낭비 90% 이상 절감
정량 (변환 속도)	1번의 배열 인덱싱 (매우 빠름)	트리 구조로 4번 읽음 (Page Walk 느림)	(단점) 속도를 내어주고 공간을 취함
정성 (확장성)	64비트 환경에서 아예 구현 불가능	무한한 가상 주소 공간 쪼개기 가능	x86-64 및 최신 칩셋 가상 메모리의 유일한 대안

미래 전망

5-Level Paging (인텔 Ice Lake 이후): 빅데이터와 AI 붐으로 인해 물리적 서버 메모리가 수십 테라바이트를 넘어가자, 4단계(4-level, 48비트 가상 주소, 256TB 한계)로도 모자라게 되었다. 그래서 루트 디렉터리를 한 번 더 감싸는 5단계 페이징(57비트 가상 주소, 128PB 한계)이 메인라인 리눅스 커널에 도입되었다. 이는 공간 확장을 위해 탐색 시간(Latency)을 한 번 더 희생한 하드웨어의 눈물겨운 땜질이다.

결론

다단계 페이지 테이블(Hierarchical Paging) 사이즈 줄이기는 컴퓨터 과학의 가장 위대한 트레이드오프인 **"공간(Memory)을 얻기 위해 시간(Time)을 판다"**는 명제를 가장 극단적으로 보여주는 건축물이다. 페이징 시스템을 구하기 위해 무려 4~5번의 포인터 추적(Pointer Chasing)이라는 미친 속도 저하를 허락했고, 그 떨어진 속도를 다시 메꾸기 위해 TLB라는 비싼 하드웨어 캐시를 발라버리는 거대한 폭탄 돌리기의 연속이었다. 하지만 이 위태로운 곡예 덕분에, 오늘날 64비트 시대의 프로그램들은 우주만큼 넓은 가상 메모리 공간을 에러 하나 없이 공짜로 펑펑 쓸 수 있게 되었다.

📢 섹션 요약 비유: 방이 좁다고 침대를 접이식(다단계 테이블)으로 바꿨습니다. 잘 때마다 침대를 펴고 접는 건(Page Walk) 너무 귀찮지만, 덕분에 방을 10배로 넓게 쓸 수 있습니다. 그리고 평소에는 낮잠용 소파(TLB)에서 자니까 귀찮음도 별로 못 느낍니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
Paging (페이징)	프로세스를 4KB로 조각내어 외부 단편화를 없앤 대신, 100만 줄짜리 매핑 테이블(장부)이라는 괴물을 낳은 근원
Page Walk (페이지 워크)	다단계로 쪼개진 테이블의 루트부터 말단까지 포인터를 따라 램(RAM)을 4번이나 읽어 내려가는 무거운 탐색 행위
TLB (Translation Lookaside Buffer)	다단계 페이징으로 인해 박살 난 주소 번역 속도를, 캐싱을 통해 기적적으로 $O(1)$ 속도로 되살려낸 하드웨어 호흡기
Huge Pages (대용량 페이지)	테이블 단계(Depth)를 줄이고, 테이블 용량을 압축하여 Page Walk와 메모리 낭비를 동시에 부수는 고성능 서버의 필살기
Inverted Page Table (역 페이지 테이블)	다단계로 쪼개도 모자라자, 아예 시스템 전체에 딱 1개의 테이블만 두어 공간 낭비의 종지부를 찍으려 한 학술적 시도

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

전 세계 골목길이 다 적힌 엄청나게 두꺼운 지도책(1단계 테이블)을 가방에 넣고 다니려니까 허리가 부러질 것 같았어요.
그래서 책을 다 찢어버리고, '국가 이름표(1단계 목차)'만 남겼어요. 내가 미국에 놀러 갈 때만 동사무소에 가서 '미국 상세 지도(2단계 목차)'를 뽑아왔죠! (다단계 페이징)
이렇게 하니까 가방은 엄청 가벼워졌어요(메모리 절약). 지도를 찾을 때 단계를 두 번 거쳐야 해서 조금 느려졌지만, 그래도 허리가 안 아픈 게 최고랍니다!