289. 다단계 페이지 테이블 (Multilevel Page Table)

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

본질: 다단계 페이지 테이블 (Multilevel Page Table)은 거대한 단일 페이지 테이블을 트리 구조로 쪼개, 실제로 접근한 주소 구간의 하위 테이블만 만드는 희소 최적화 기법이다.

가치: 가상 주소 공간이 커질수록 페이지 테이블 자체가 차지하는 메모리가 폭증하는데, 다단계 구조는 이 관리 오버헤드를 실사용 영역 중심으로 줄여 64비트 시스템을 현실적으로 만든다.

판단 포인트: 메모리는 절약되지만 주소 변환 단계가 늘어나는 만큼, TLB (Translation Lookaside Buffer) 적중률·Huge Page·가상화 계층까지 함께 봐야 성능 이점을 지킬 수 있다.

Ⅰ. 개요 및 필요성

다단계 페이지 테이블은 페이지 테이블 자체를 여러 층의 인덱스로 분해한 계층형 주소 변환 구조다. 핵심 목적은 "가상 주소 공간 전체에 대한 장부를 한 번에 만들지 말고, 실제로 쓰는 구역의 장부만 단계별로 생성하자"는 데 있다. 운영체제는 이 구조를 통해 드문드문 사용되는 거대한 주소 공간을 관리하면서도, 페이지 테이블 때문에 RAM (Random Access Memory)을 과도하게 소모하는 문제를 피한다.

이 구조가 필요해진 이유는 단일 페이지 테이블의 크기가 주소 공간 증가 속도를 따라가지 못하기 때문이다. 예를 들어 32비트 주소 공간에서 페이지 크기가 4KB이면 약 1M개의 항목이 필요하고, 항목당 4바이트만 잡아도 프로세스마다 약 4MB의 테이블이 든다. 64비트 환경에서는 이 장부를 단일 배열로 유지하는 것이 사실상 불가능해지므로, 페이지 테이블도 "필요한 만큼만 펼치는 구조"로 진화해야 했다.

아래 그림은 왜 다단계가 필요한지를 보여준다. 코드·힙·스택처럼 일부 구간만 쓰는 프로세스라면, 빈 가상 주소 구간의 하위 테이블은 아예 만들지 않아도 된다.

┌────────────────────────────────────────────────────────────────────────────┐
│        희소한 가상 주소 공간과 다단계 페이지 테이블의 생성 범위          │
├────────────────────────────────────────────────────────────────────────────┤
│ 가상 주소 공간                                                            │
│ ┌──── 코드 ────┬──────────── 미사용 ────────────┬── 힙 ──┬──── 스택 ────┐ │
│ └─────┬────────┴────────────────────────────────┴───┬────┴──────┬───────┘ │
│       │                                             │           │         │
│       ▼                                             ▼           ▼         │
│   [하위 테이블 생성]                            [미생성]   [하위 테이블 생성] │
│                                                                    [생성] │
│                                                                            │
│ 상위 테이블은 "어느 구간이 사용 중인가"만 가리키고, 비어 있는 구간은 NULL  │
└────────────────────────────────────────────────────────────────────────────┘

즉 다단계 페이지 테이블은 데이터 페이지를 아끼는 기법이 아니라, 페이지 테이블 메타데이터를 희소하게 유지하는 기법이라는 점이 중요하다. 그래서 가상 메모리 시스템이 커질수록 그 가치가 더 커진다.

📢 섹션 요약 비유: 거대한 전국 주소록을 통째로 인쇄하는 대신, 시도 색인만 먼저 두고 실제로 사는 동네의 상세 주소록만 꽂아 두는 방식과 같다. 사람이 없는 동네의 책자는 애초에 인쇄하지 않으니 서가 공간이 크게 줄어든다.

Ⅱ. 아키텍처 및 핵심 원리

다단계 페이지 테이블의 동작 주체는 MMU (Memory Management Unit)다. MMU는 가상 주소를 여러 구간으로 나눈 뒤, 상위 테이블에서 하위 테이블의 위치를 찾고, 마지막 단계에서 PTE (Page Table Entry)를 읽어 물리 프레임 번호를 얻는다. 마지막으로 페이지 오프셋을 붙여 물리 주소를 완성한다.

대표적인 x86-64 4단계 구조를 기준으로 보면, 48비트 가상 주소는 보통 9비트 + 9비트 + 9비트 + 9비트 + 12비트로 나뉜다. 앞의 네 구간은 각각 상위 레벨 인덱스이고, 마지막 12비트는 페이지 내부 오프셋이다. 각 단계가 512개 엔트리를 가지는 이유는 9비트가 2^9 = 512개의 선택지를 만들기 때문이다.

단계	역할	비트 수	결과
Level 4	최상위 디렉터리 선택	9비트	다음 단계 테이블 주소
Level 3	중간 디렉터리 선택	9비트	다음 단계 테이블 주소
Level 2	하위 디렉터리 선택	9비트	마지막 테이블 주소
Level 1	최종 PTE 선택	9비트	물리 프레임 번호 + 제어 비트
Offset	페이지 내부 위치	12비트	최종 바이트 위치

아래 그림은 MMU가 페이지 테이블 워크 (Page Table Walk)를 수행하는 순서를 압축한다.

┌────────────────────────────────────────────────────────────────────────────┐
│            4단계 페이지 테이블 워크 (Page Table Walk) 흐름               │
├────────────────────────────────────────────────────────────────────────────┤
│ 가상 주소                                                                 │
│ ┌──── L4 ────┬──── L3 ────┬──── L2 ────┬──── L1 ────┬──── Offset ─────┐ │
│ └────┬───────┴────┬───────┴────┬───────┴────┬───────┴────────┬────────┘ │
│      ▼            ▼            ▼            ▼                ▼          │
│   [L4 테이블] -> [L3 테이블] -> [L2 테이블] -> [L1 PTE] -> [Frame+Off] │
│      │            │            │            │                           │
│      └─ 없으면 페이지 폴트 또는 미매핑 영역 판단                        │
└────────────────────────────────────────────────────────────────────────────┘

이 구조의 병목은 명확하다. TLB 미스가 발생하면 CPU는 실제 데이터에 접근하기 전에 페이지 테이블을 여러 번 읽어야 한다. 하지만 반대로 보면, 사용하지 않는 주소 범위는 하위 테이블을 아예 만들지 않으므로 프로세스별 메모리 오버헤드를 크게 낮출 수 있다. 결국 다단계 페이지 테이블은 메모리 절약과 추가 메모리 참조 비용을 맞바꾸는 구조적 타협이다.

📢 섹션 요약 비유: 건물 호수를 찾기 위해 시청 → 구청 → 동사무소 → 관리사무소를 차례로 거치는 셈이다. 절차는 길어지지만, 전국 모든 건물 정보를 한 건물 관리실에 몰아넣지 않아도 된다는 장점이 생긴다.

Ⅲ. 비교 및 연결

다단계 페이지 테이블의 성격은 단일 페이지 테이블, 역 페이지 테이블 (Inverted Page Table)과 비교할 때 가장 선명해진다. 단일 구조는 접근 단계가 짧지만 테이블이 너무 커지고, 역 구조는 물리 메모리 기준으로 장부를 줄일 수 있지만 해시 탐색과 공유 페이지 처리 복잡도가 커진다. 다단계 구조는 그 중간에서 "주소 공간은 크지만 실제 사용은 희소하다"는 현대 프로세스의 특성을 가장 잘 활용한다.

구분	단일 페이지 테이블	다단계 페이지 테이블	역 페이지 테이블
장점	탐색 단계 단순	희소 영역에서 메모리 절약	물리 메모리 기준으로 크기 제한
약점	주소 공간이 커질수록 비현실적	TLB 미스 시 워크 비용 증가	검색·공유 처리 복잡
적합 환경	작은 주소 공간	범용 32/64비트 OS	매우 큰 메모리 시스템

또한 이 구조는 TLB, Huge Page, 페이지 폴트, 가상화와 직접 연결된다. TLB는 반복 번역을 캐시해 다단계 워크 비용을 줄이고, Huge Page는 마지막 일부 단계를 생략해 워크 깊이를 얕게 만든다. 반대로 페이지 폴트가 잦거나 메모리 접근 지역성이 낮으면, 다단계 구조의 이론적 절약 효과보다 실성능 손해가 더 크게 체감될 수 있다.

즉 다단계 페이지 테이블은 독립된 주제가 아니라, 가상 메모리 성능 생태계의 중심 축이다. 페이지 테이블 형식만 이해해서는 부족하고, 캐시 계층과 접근 패턴까지 함께 봐야 경계가 드러난다.

📢 섹션 요약 비유: 단일 테이블은 한 권짜리 초대형 백과사전이고, 다단계는 색인과 분권 체계가 있는 도서관이며, 역 페이지 테이블은 책 위치 기준 재고 시스템에 가깝다. 무엇이 빠른지는 "어떻게 찾는가"와 "얼마나 큰 장서를 다루는가"에 따라 달라진다.

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

실무에서는 "다단계 구조를 쓸 것인가"보다 "다단계 구조의 비용을 무엇으로 완화할 것인가"가 더 중요한 질문이다. 현대 범용 운영체제는 사실상 다단계 페이지 테이블을 기본 전제로 삼지만, 데이터베이스·가상화 플랫폼·대용량 메모리 서버에서는 TLB 압박과 페이지 테이블 워크 지연이 실제 병목이 된다.

예를 들어 4KB 페이지를 촘촘히 쓰는 대용량 메모리 워크로드는 PTE 수가 폭증하고, TLB 엔트리도 빠르게 소진한다. 이때 2MB Huge Page를 쓰면 마지막 단계 일부를 생략할 수 있어 워크 깊이와 TLB 미스를 함께 줄일 수 있다. 반대로 메모리 사용량이 들쭉날쭉하거나 내부 단편화가 치명적인 서비스에서는 Huge Page가 오히려 낭비를 늘릴 수 있으므로 무조건적인 채택은 위험하다.

가상화 환경에서는 문제가 한 단계 더 복잡해진다. 게스트 운영체제의 페이지 테이블과 하이퍼바이저의 2차 변환 테이블(EPT/NPT)이 겹치면, TLB 미스 한 번의 비용이 더욱 커진다. 따라서 기술사 관점에서는 "주소 변환 구조 자체"보다 워크로드 지역성, Huge Page 전략, 가상화 중첩 여부를 함께 판단해야 한다.

체크리스트

메모리 사용 패턴이 희소한가, 아니면 넓고 촘촘한가?
TLB 미스와 페이지 테이블 워크가 실제 CPU 스톨 원인인가?
Huge Page 도입 시 내부 단편화 증가를 감당할 수 있는가?
가상머신·컨테이너 환경에서 2차 주소 변환 비용을 측정했는가?

안티패턴

주소 공간이 큰 이유만으로 성능도 자동으로 좋을 것이라 착각하는 설계
TLB 적중률과 페이지 크기 정책 없이 무작정 4KB 페이지만 고집하는 운영
가상화 계층을 쓰면서도 Nested Page Table 비용을 모니터링하지 않는 튜닝
📢 섹션 요약 비유: 창고를 선반별로 잘 나눠 두는 것만으로 작업이 빨라지지는 않는다. 지게차 동선, 자주 찾는 물건의 위치, 창고가 한 겹인지 두 겹인지까지 함께 봐야 진짜 운영 효율이 나온다.

Ⅴ. 기대효과 및 결론

다단계 페이지 테이블의 가장 큰 효과는 주소 공간 확장성을 메모리 현실성과 연결해 준다는 점이다. 이 구조 덕분에 운영체제는 매우 큰 가상 주소 공간을 각 프로세스에 제공하면서도, 실제로 사용하지 않는 주소 구간에 대한 페이지 테이블 메모리는 거의 쓰지 않을 수 있다. 특히 코드·힙·스택이 띄엄띄엄 배치되는 일반적인 프로세스에서는 효과가 크다.

물론 한계도 분명하다. TLB가 충분히 받쳐주지 못하면 다단계 워크 비용이 성능 손실로 드러나고, 단계 수가 늘수록 하드웨어 복잡도와 워크 지연도 함께 커진다. 그래서 이 구조는 "언제나 빠른 방식"이 아니라, 희소한 주소 공간을 감당하기 위한 가장 현실적인 방식으로 기억해야 한다.

미래 방향도 같은 축에서 이어진다. 첫째, 5단계 페이징처럼 더 큰 주소 공간을 수용하는 확장이 진행된다. 둘째, Huge Page와 하드웨어 워크 캐시가 워크 비용을 줄인다. 셋째, 가상화와 메모리 암호화 환경에서도 주소 변환 계층을 덜 비싸게 만드는 방향으로 진화한다.

결론적으로 다단계 페이지 테이블은 "메모리 주소를 잘게 나눠 관리하는 기술"이 아니라, 거대한 주소 공간을 관리 가능한 장부 크기로 접어 넣는 구조적 설계법이다. 주소 변환 단계가 늘어나는 비용은 남지만, 그 대가로 현대 시스템은 거대한 가상 메모리 모델을 실용적으로 유지할 수 있게 되었다.

📢 섹션 요약 비유: 다단계 페이지 테이블은 펼치면 거대한 지도지만, 실제로는 필요한 구역만 접어서 들고 다니는 여행 지도와 같다. 길 찾는 순서는 조금 늘어도, 배낭 안에 들어갈 만큼 가벼워진다는 점이 핵심이다.

📌 관련 개념 맵

개념	연결 포인트
페이지 테이블 (Page Table)	다단계 구조의 각 레벨을 이루는 기본 번역 장부다.
PTE (Page Table Entry)	최종 단계에서 물리 프레임 번호와 권한 비트를 제공하는 엔트리다.
MMU (Memory Management Unit)	각 레벨을 따라가며 주소 변환을 실제 수행하는 하드웨어다.
TLB (Translation Lookaside Buffer)	다단계 워크 비용을 캐시로 숨겨 체감 성능을 지키는 핵심 장치다.
Huge Page	페이지 수를 줄여 테이블 깊이와 TLB 압박을 동시에 완화하는 최적화 수단이다.
역 페이지 테이블 (Inverted Page Table)	페이지 테이블 크기 문제를 다른 축에서 풀려는 대안 구조다.

📈 관련 키워드 및 발전 흐름도

단일 페이지 테이블
        │
        ▼
페이지 테이블 크기 폭증 문제
        │
        ▼
다단계 페이지 테이블
        │
        ├──────────────▶ TLB (Translation Lookaside Buffer) 최적화
        │
        ├──────────────▶ Huge Page 기반 워크 깊이 축소
        │
        └──────────────▶ 역 페이지 테이블 · Nested Paging 확장

이 흐름은 "단순 번역 장부"에서 출발해, 주소 공간 확장 문제를 해결하고, 이후 성능 최적화와 가상화 대응으로 확장되는 진화를 보여준다.

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

다단계 페이지 테이블은 엄청 두꺼운 주소책을 한 권으로 들고 다니지 않고, 구역별로 나눠 필요한 것만 꺼내 보는 방법이에요.
그래서 친구가 없는 동네 책은 아예 만들지 않아도 되어 메모리를 아낄 수 있어요.
대신 주소를 찾을 때 책을 몇 번 더 넘겨야 해서, 자주 찾는 주소는 TLB라는 작은 암기장에 미리 적어 두는 거예요.