다단계 페이징 (Hierarchical Paging)

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

본질: 다단계 페이징(Hierarchical Paging)은 32비트/64비트 시스템에서 기하급수적으로 거대해지는 단일 1차원 페이지 테이블의 용량을 줄이기 위해, 페이지 테이블 자체를 또 다른 페이지로 쪼개어 트리(Tree) 구조의 목차를 만드는 아키텍처다.

가치: 실제로 사용하지 않는 허공의 주소 공간에 대해서는 하위 레벨의 테이블을 아예 생성하지 않음으로써(Null Pointer), 페이지 테이블이 차지하는 물리적 램(RAM) 낭비를 극적으로 최소화한다.

융합: 단점인 "메모리 접근 횟수 증가(3단계 페이징은 장부를 3번 읽어야 함)"라는 치명적인 오버헤드를, **TLB(Translation Look-aside Buffer)**라는 하드웨어 캐시의 99% 적중률과 결합하여 완벽하게 상쇄시킨다.

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

개념: 다단계 페이징은 '페이지 테이블을 위한 페이지 테이블'을 두는 방식이다. 책의 맨 앞에 있는 대주제 목차(Outer Page Table)를 보고 중간 목차를 찾은 뒤, 중간 목차(Inner Page Table)를 보고 실제 페이지를 찾아가는 2단계 이상의 계층적 검색 구조다.
필요성: 32비트 시스템에서 4KB 페이지를 쓰면 프로세스당 4MB의 페이지 테이블이 필요하다. 100개 프로세스가 뜨면 장부 크기만 400MB다. 64비트 시스템이라면? 이론상 페이지 테이블 하나가 **수십 페타바이트(PB)**라는 지구상에 존재할 수 없는 크기가 된다. 하지만 실제 프로그램은 64비트 주소 공간 중 극히 일부(수십 MB)만 사용한다. "안 쓰는 주소의 빈칸 장부까지 메모리에 올려두는 미친 짓을 그만두자"는 절박함에서 탄생했다.
💡 비유: 다단계 페이징은 전 세계 인명 사전을 만드는 것과 같다. 1차원 테이블은 80억 명의 이름을 가나다순으로 한 권의 두꺼운 책(수천 톤의 무게)으로 엮은 것이다. 다단계 페이징은 일단 '대륙별 얇은 책 1권(1단계)'을 만들고, 아시아를 펼치면 '국가별 책 번호'가 나온다. 한국 책(2단계)을 펼치면 '도시별 책 번호'가 나온다. 사람이 살지 않는 남극(안 쓰는 주소 공간)은 아예 하위 책 자체를 인쇄하지 않음으로써 엄청난 종이(메모리)를 아끼는 기법이다.
등장 배경 및 64비트의 공포:
1. 1단계 페이징의 한계: 16비트 시절에는 1차원 배열 장부 하나면 충분했다.
2. 성긴 주소 공간(Sparse Address Space): 32/64비트 시대에는 메모리의 양 끝단(코드와 스택)만 쓰고 중간 수 GB~TB는 텅텅 비어있는 구조가 흔해졌다.
3. 목차의 계층화: 빈 공간을 표현하기 위해 1차원 배열의 빈칸을 유지하지 말고, 아예 최상위 목차에서 "여기부터 저기까지는 아무것도 없음(Null)"이라고 표시한 뒤, 그 하위 테이블 자체를 메모리에 만들지 않는(동적 할당) 다단계 트리 구조가 채택되었다.

┌──────────────────────────────────────────────────────────────────────┐
│        1단계 페이징 vs 2단계(다단계) 페이징의 메모리 낭비 비교       │
├──────────────────────────────────────────────────────────────────────┤
│                                                                      │
│ [ 1차원 배열 페이징: 안 쓰는 공간도 장부를 다 만들어야 함! ]         │
│  인덱스 0: [ 프레임 5 ] (사용 중)                                    │
│  인덱스 1: [ 프레임 8 ] (사용 중)                                    │
│  인덱스 2: [   NULL   ] (안 씀. 그래도 칸은 차지함)                  │
│  ... (수십만 개의 텅 빈 NULL 칸들)                                   │
│  인덱스 999,999: [ 프레임 2 ] (사용 중)                              │
│  ▶ 결과: 실제로 3칸만 쓰는데 장부는 100만 칸(4MB) 램 차지.           │
│                                                                      │
│ [ 2단계 페이징: 안 쓰는 공간은 가지치기! ]                           │
│       [ 1단계 목차 테이블 ]                                          │
│  0번 줄 ──포인터──▶ [ 2단계 테이블 A 생성! ] ──▶ (Fr 5, 8)           │
│  1번 줄 ── NULL ──▶ (2단계 테이블 아예 안 만듦! 램 절약!)            │
│  ...                                                                 │
│  1023번 줄 ──포인터─▶ [ 2단계 테이블 B 생성! ] ──▶ (Fr 2)            │
│  ▶ 결과: 1단계 목차(4KB) + 2단계 테이블 2개(8KB) = 12KB만 소모!      │
└──────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이 구조는 메모리 절약의 극치를 보여준다. 프로그램은 보통 코드 영역(앞쪽)과 스택 영역(뒤쪽)만 쓰고 중간을 엄청나게 비워둔다. 2단계 페이징에서는 이 거대한 중간 영역에 해당하는 1단계 목차가 그저 NULL을 가리키게 된다. 따라서 그 거대한 공간을 커버할 수천 개의 2단계 장부들은 아예 램(RAM)에 생성(Allocate)되지도 않는다. 4MB가 12KB로 줄어드는 마법이다.

📢 섹션 요약 비유: 호텔에서 방명록을 관리할 때, 1호부터 10만 호까지 빈 줄이 빽빽한 거대한 방명록을 두는 대신, "1층 장부"만 놔두고, 손님이 1층에 투숙할 때만 "101호~110호 상세 장부"를 새로 꺼내어 책상에 놓는 유연한 관리법입니다.

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

32비트 아키텍처의 주소 분할 (2-Level Paging)

과거 32비트 CPU(예: 인텔 Pentium)가 4KB 페이지를 사용할 때, 32개의 비트(Bit)는 다음과 같이 세 토막으로 쪼개어 번역된다.

$p_1$ (Outer Page Number, 10비트): 1단계 목차 테이블의 인덱스. ($2^{10} = 1024$칸)
$p_2$ (Inner Page Offset, 10비트): 2단계 상세 테이블의 인덱스. ($2^{10} = 1024$칸)
$d$ (Page Offset, 12비트): 물리 4KB 안에서의 최종 위치. ($2^{12} = 4096$바이트)

┌─────────────────────────────────────────────────────────────────────┐
│              2단계 페이징(Two-Level Paging) 주소 번역의 여정        │
├─────────────────────────────────────────────────────────────────────┤
│                                                                     │
│ [ CPU 가상 주소 발출 ]                                              │
│ ┌───────┬───────┬────────────┐                                      │
│ │ P1(5) │ P2(8) │ d (1050)   │                                      │
│ └───────┴───────┴────────────┘                                      │
│     │       │        │ (Offset은 그냥 끝까지 패스)                  │
│     │       ▼        │                                              │
│     │   ┌────────────────────┐                                      │
│     │   │ [ 2단계 테이블 ]    │                                     │
│     │   │ 8번째 칸 -> Fr 12 ─┼──────────────┐                       │
│     ▼   └────────────────────┘              │                       │
│ ┌──────────────────────┐  ▲                  │                      │
│ │ [ 1단계 테이블 ]      │  │                  ▼                     │
│ │ 5번째 칸 -> 2단계 주소 │──┘         ┌────────┬────────────┐       │
│ └──────────────────────┘            │ Fr 12  │ d (1050)   │         │
│                                     └────────┴────────────┘         │
│                             [ 변환된 최종 물리 주소 (RAM 접근) ]    │
└─────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이 다이어그램은 페이징의 아름다움이자 끔찍함을 동시에 보여준다. CPU가 데이터를 한 번 읽기 위해, 1) P1을 들고 1단계 장부를 읽어 2단계 장부 위치를 찾고, 2) 그곳으로 가서 P2를 들고 2단계 장부를 읽어 실제 프레임 번호를 찾고, 3) 마지막으로 알아낸 프레임 주소로 진짜 데이터를 읽어온다. 총 메모리 접근이 3번(장부 2번 + 데이터 1번) 발생하여, 시스템 속도는 이론상 1/3 토막이 난다.

현대 64비트 시스템의 4단계 / 5단계 페이징

32비트에서는 2단계면 충분했지만, 64비트는 너무나 넓어 2단계로도 장부가 감당이 안 된다.

인텔 x86_64 아키텍처: 64비트 중 하위 48비트만 사용하며, 이를 무려 **4단계(4-Level Paging)**로 쪼갰다.
- PGD (Page Global Directory) -> PUD (Upper Dir) -> PMD (Middle Dir) -> PTE (Page Table Entry) 순서로 램을 4번이나 뒤진다.
최신 5단계 페이징: 서버 램 용량이 수백 TB로 늘어나자, 인텔은 5단계 페이징(5-Level Paging)을 하드웨어에 추가했다. (램을 5번 뒤짐)
📢 섹션 요약 비유: 우주(64비트)에서 내 방을 찾으려면 은하계 지도(1단계) -> 태양계 지도(2단계) -> 지구 지도(3단계) -> 한국 지도(4단계)를 차례대로 뒤져야 비로소 내 집 주소를 알 수 있는 끝없는 꼬리물기 탐색전입니다.

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

비교 1: 1차원 테이블 vs 다단계 페이징

비교 항목	1차원 페이지 테이블	다단계 (Hierarchical) 페이징
메모리 낭비 (장부)	최악 (안 쓰는 빈칸도 수백 MB 차지)	최상 (안 쓰는 가지는 NULL 처리해 아예 안 만듦)
장부의 연속성	수백 MB가 램 상에 무조건 연속되어야 함	4KB짜리 장부 조각들이 램 곳곳에 흩어져도 됨 (테트리스 용이)
번역 오버헤드	장부 1번 읽음 (빠름)	장부 2~4번 읽음 (극도로 느림)

TLB라는 완벽한 방패 (오버헤드의 상쇄)

다단계 페이징의 "메모리 4번 접근"이라는 끔찍한 오버헤드를 들으면 "이걸 컴퓨터라고 쓸 수 있나?" 싶다.
하지만 **TLB(주소 번역 캐시)**가 이 모든 절망을 구원한다.
TLB에 한 번 주소 매핑(P1+P2+P3+P4 -> Frame)이 등록(Hit)되면, 그 뒤로는 **장부 탐색 4단계를 모조리 생략(Bypass)**하고 1클럭 만에 곧바로 물리 램으로 직행한다.
TLB Hit Ratio가 99%에 달하기 때문에, 1%의 Miss 상황에서만 4번의 페널티(Page Table Walk)를 맞을 뿐, 평상시 체감 속도는 1단계 페이징과 완벽하게 똑같다.

┌──────────┬────────────┬────────────┬─────────────────────────┐
│ 아키텍처   │ 장부 크기 절약│ 번역 페널티   │ TLB 적중 시 지연│
├──────────┼────────────┼────────────┼─────────────────────────┤
│ 1단계 페이징│ 전혀 안 됨   │ RAM 1번 읽음 │ 없음 (0)         │
│ 4단계 페이징│ 완벽한 절약  │ RAM 4번 읽음 │ 없음 (0)         │
└──────────┴────────────┴────────────┴─────────────────────────┘

[매트릭스 해설] 컴퓨터 공학자들의 배짱을 볼 수 있다. "어차피 TLB 캐시가 99% 막아주니까, Miss 났을 때 장부 4번 뒤져서 엄청 느려지는 건 눈 딱 감고 무시하자. 대신 그 1%의 느림을 감수하고 시스템의 가용 램(RAM)을 수백 MB 확보하는 것이 훨씬 이득이다"라는 극한의 트레이드오프 전술이다.

📢 섹션 요약 비유: 목적지를 찾을 때 지도를 4번(4단계) 갈아타며 보는 건 끔찍하지만, 내비게이션(TLB)에 한 번 즐겨찾기 해두면 다음부턴 지도를 아예 안 보고 1초 만에 찾아가기 때문에 지도 찾는 복잡함은 큰 문제가 안 되는 원리입니다.

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

실무 시나리오: KPTI 패치와 다단계 페이징의 충돌

문제 상황: 인텔 CPU의 보안 버그(Meltdown)를 막기 위해 리눅스는 유저 테이블과 커널 테이블을 찢어버리는 KPTI 패치를 적용했다.
4단계 페이징 워크(Walk)의 악몽:
- 컨텍스트 스위치가 일어날 때마다 TLB 캐시가 다 날아간다.
- 캐시가 없으니 CPU는 어쩔 수 없이 램에 있는 4단계 페이지 테이블(PGD->PUD->PMD->PTE)을 4번 연속으로 덜그럭거리며 읽어와야 한다 (Page Table Walk).
- 이 무거운 4단계 램 접근이 초당 수만 번 터지자, AWS 클라우드 서버의 CPU iowait(대기 시간)가 폭발하여 서버가 다운되는 현상이 벌어졌다.
실무적 타협:
- 이 거대한 다단계 페이징 페널티를 줄이는 유일한 해법은 TLB 미스 자체를 줄이는 것뿐이다.
- 따라서 서버 관리자들은 DB나 캐시 시스템에 **Huge Page(거대 페이지)**를 강제로 켜서 TLB 적중률을 99.9%로 높여 4단계 워크(Walk)가 아예 발생하지 않게 멱살 잡고 하드캐리하는 식으로 시스템을 연명시킨다.

임베디드(IoT) 시스템에서의 선택

라즈베리파이나 작은 IoT 기기들은 메모리가 적어서 다단계 페이징을 깊게 할 필요가 없다. 그래서 ARM 아키텍처 중 가벼운 버전은 2단계 페이징만 지원하여 하드웨어 회로를 단순화하고, Page Table Walk 시 발생하는 전력 소모를 극적으로 줄인다.

📢 섹션 요약 비유: 평소엔 비서(TLB)가 다 기억해줘서 몰랐는데, 비서가 휴가(캐시 플러시)를 가버리자 사장님(CPU)이 직접 서류창고(RAM)에 가서 4개의 복잡한 캐비닛(4단계)을 뒤적거리느라 회사 업무가 마비되는 대기업의 민낯입니다.

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

정량/정성 기대효과

구분	내용
메모리(RAM) 용량 구원	안 쓰는 가상 주소 공간의 페이지 테이블을 생성하지 않아, 기가바이트 급 장부 낭비를 KiloByte 수준으로 압축
장부의 파편화 할당	수십 MB짜리 연속된 1차원 테이블 대신, 4KB짜리 작은 테이블 여러 개로 찢어 RAM의 빈 프레임 아무 곳에나 매핑 가능
64비트 컴퓨팅 실현	이 다단계 트리 구조 압축이 없었다면 64비트의 광활한 주소 공간은 페이지 테이블 폭발로 인해 영원히 이론 속에만 머물렀을 것임

결론 및 미래 전망

다단계 페이징 (Hierarchical Paging)은 무한대로 커지는 가상 메모리와 한정된 물리 램 사이의 모순을 '트리(Tree) 구조의 압축'으로 우아하게 풀어낸 컴퓨터 과학의 걸작이다. 장부를 3번, 4번 읽어야 하는 지옥 같은 하드웨어 페널티를 만들었지만, 이를 다시 TLB라는 캐시로 덮어버린 공학자들의 연쇄적인 문제 해결 과정은 경이롭기까지 하다. 미래에는 가상화 계층(Hypervisor) 때문에 이 다단계 테이블이 2차원(Extended Page Table, 8번~24번 램 접근)으로까지 깊어지고 있지만, 하드웨어 주소 번역 가속기(IOMMU)의 발전으로 우리는 여전히 이 무거운 장부의 존재조차 느끼지 못한 채 빛의 속도로 컴퓨터를 사용하고 있다.

📢 섹션 요약 비유: 수억 권의 책이 있는 도서관에서 책을 찾을 때, 한 권의 거대한 색인표를 만드는 대신, 층별 안내도 -> 구역 안내도 -> 서가 안내도의 다단계 트리를 만듦으로써 안내 책자의 부피를 획기적으로 줄인 천재적인 카탈로그 디자인입니다.

📌 관련 개념 맵 (Knowledge Graph)

페이징 (Paging) | 메모리를 4KB로 찢어 외부 단편화를 없앤 대신, 거대한 주소 번역 장부를 낳은 근본 아키텍처
페이지 테이블 (Page Table) | 다단계 페이징 이전의 거대하고 뚱뚱했던 1차원 배열 형태의 주소 번역 장부
TLB (Translation Lookaside Buffer) | 다단계 페이징의 '램 4번 읽기' 지연을 0초로 상쇄시켜 주는 99% 적중률의 구원자 캐시 칩셋
역 페이지 테이블 (Inverted Page Table) | 다단계 페이징으로도 감당이 안 되는 메모리 낭비를 잡기 위해, 아예 프레임 기준으로 테이블을 하나만 만드는 역발상 기법
Sparse Address Space (성긴 주소 공간) | 64비트 환경에서 실제로는 찔끔만 쓰고 중간이 텅텅 빈 메모리 공간으로, 다단계 페이징이 효율을 발휘하는 주 무대

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

다단계 페이징이 무엇인가요? 100층짜리 거대한 아파트(가상 메모리)의 안내 책자를 100장짜리 두꺼운 책으로 만들지 않고, 그냥 1장짜리 '층수 요약본'만 엘리베이터에 붙여놓는 거예요.
왜 그렇게 하나요? 사실 이 아파트에는 사람이 1층과 100층에만 살아서, 2층~99층 안내 책자를 굳이 종이 아깝게(메모리 낭비) 만들 필요가 없거든요.
어떻게 찾아가나요? 1층 요약본을 보고 100층으로 올라간 다음, 100층에 도착해서 그 층의 상세 지도를 다시 보는 식(2단계 탐색)으로 똑똑하게 찾아간답니다.