다단계 페이지 테이블(Multi-level Page Table) — “메모리 낭비를 줄이는 똑똑한 주소 변환 구조”
시작 — 왜 ‘작은 페이지 테이블’이 필요한가?
페이징은 가상 주소를 물리 주소로 변환하기 위한 핵심 메커니즘이지만, 단점이 하나 있습니다 — 바로 “페이지 테이블이 너무 크다”는 거죠.
예를 들어 32비트 주소공간(4GB)을 4KB 페이지로 나눈다면, 한 프로세스당 약 백만 개의 페이지 엔트리가 필요합니다. 각 엔트리가 4바이트라면 한 프로세스의 페이지 테이블 크기는 4MB! 프로세스가 100개만 있어도 페이지 테이블만 400MB가 되는 셈입니다.
이건 명백한 낭비이죠. 그래서 등장한 것이 바로 다단계 페이지 테이블입니다.
해결 아이디어 1 — 페이지를 크게 만들자?
가장 단순한 해결책은 페이지 크기를 키우는 겁니다. 4KB → 16KB로 키우면 페이지 수가 4배 줄고, 페이지 테이블 크기도 4배 줄어듭니다.
하지만 이렇게 하면 각 페이지 안에 낭비되는 공간이 많아집니다. 즉, 내부 단편화(Internal Fragmentation) 문제가 발생합니다. 메모리 낭비를 줄이려다 다른 형태의 낭비가 생기는 셈이죠.
그래서 대부분의 시스템은 여전히 4KB나 8KB 같은 작은 페이지 크기를 유지합니다.
해결 아이디어 2 — 세그먼트와 페이징의 하이브리드
“페이지 테이블이 너무 크면, 필요한 부분만 만들면 되지 않을까?” 이런 생각에서 등장한 것이 세그먼트+페이징 혼합 방식입니다.
즉, 전체 주소 공간에 대해 하나의 거대한 페이지 테이블을 두는 대신, 코드, 힙, 스택 같은 각 세그먼트별로 작은 페이지 테이블을 하나씩 두는 방식이에요.
이렇게 하면 각 세그먼트가 실제 사용하는 영역만큼만 테이블을 만들면 되니까 낭비가 크게 줄어듭니다.
💬 하지만 문제도 있습니다. 세그먼트 경계가 고정되어 있어 융통성이 떨어지고, 세그먼트 크기 단위로 외부 단편화가 다시 발생할 수 있습니다.
해결 아이디어 3 — 다단계 페이지 테이블
세그먼트를 없애면서도 메모리 낭비를 줄이는 방법은 없을까요? 바로 그 답이 다단계 페이지 테이블(Multi-level Page Table)입니다.
아이디어는 간단합니다. 페이지 테이블을 페이지 단위로 쪼개고, 사용하지 않는 부분은 아예 안 만든다!
이를 위해 “페이지 디렉터리(Page Directory)”라는 구조를 도입합니다. 페이지 디렉터리는 각 페이지 테이블 조각이 메모리에 존재하는지, 어디에 있는지를 알려주는 일종의 주소록 역할을 합니다.
예전엔 주소록 한 권에 전 세계 모든 사람의 이름이 들어있었어요. 하지만 이제는 “도시별 주소록”을 만들어두고, 사용자가 사는 도시의 주소록만 꺼내 쓰는 식으로 바뀐 겁니다.
2단계 페이지 테이블의 구조 이해하기
2단계 구조에서는 VPN(Virtual Page Number)을 두 부분으로 나눕니다.
- 상위 비트: 페이지 디렉터리 인덱스 (PD Index)
- 하위 비트: 페이지 테이블 인덱스 (PT Index)
주소 변환은 이렇게 진행됩니다:
- PD Index로 페이지 디렉터리에서 PDE(Page Directory Entry) 찾기
- PDE가 가리키는 페이지 테이블을 찾아서 PT Index로 PTE 찾기
- PTE가 가리키는 물리 페이지의 PFN과 offset을 결합하여 물리 주소 생성
예를 들어 16KB 주소 공간을 64바이트 페이지로 나눈다면, 전체 256개의 페이지 엔트리가 필요합니다. 이걸 16개의 페이지(각 16엔트리)로 쪼개면, 디렉터리는 단 16개의 엔트리만 가지면 충분하죠.
결과적으로, 사용 중인 부분만 실제로 테이블이 메모리에 존재하고, 나머지 비어 있는 영역은 테이블조차 생성되지 않습니다.
예제: 주소 변환 과정 한눈에 보기
가상주소: 0x3F80 (VPN = 254)
상위 4비트 → PD Index = 1111 → 디렉터리의 마지막 엔트리 선택
해당 PDE가 유효 → 페이지 테이블 페이지(PFN=101)로 이동
하위 4비트 → PT Index = 1110 → 해당 엔트리의 PFN=55
물리주소 = (55 << 6) + 0 = 0x0DC0즉, 가상 주소 0x3F80은 물리 주소 0x0DC0에 매핑됩니다. 페이지 디렉터리 → 페이지 테이블 → 물리 페이지 순으로 탐색한 결과죠.
더 깊은 트리: 3단계 이상 구조
주소 공간이 커지면, 페이지 디렉터리 자체가 너무 커지는 문제가 생깁니다. 예를 들어 30비트 주소공간에 512바이트 페이지를 쓰면, 디렉터리 하나가 128페이지나 차지할 수 있어요.
그래서 디렉터리 자체도 여러 페이지로 쪼개고, 상위 디렉터리가 하위 디렉터리를 가리키는 구조로 확장합니다.
이게 바로 3단계, 4단계 페이지 테이블의 개념입니다. x86-64의 4단계 페이징(PML4 → PDPT → PD → PT)이 대표적인 예시죠.
다단계 페이지 테이블의 시간-공간 트레이드오프
- ✅ 장점: 희소한 주소공간(sparse address space)에 매우 효율적
- ✅ 관리 용이: 각 조각이 페이지 단위라 메모리 할당과 해제가 단순
- ⚠️ 단점: TLB 미스 시 접근 횟수가 늘어남 (디렉터리 + 테이블 두 번)
- ⚠️ 복잡성 증가: 하드웨어와 OS의 구현이 더 어려워짐
즉, 메모리를 절약하려면 CPU 시간이 조금 더 들고, 속도를 우선시하면 메모리가 더 필요합니다. 이것이 바로 time-space trade-off입니다.
변형 구조: Inverted Page Table
더 극단적인 방식으로는 Inverted Page Table이 있습니다. 여기서는 프로세스마다 페이지 테이블을 두는 대신, 물리 메모리 전체에 대해 단 하나의 테이블만 둡니다.
각 엔트리는 “이 물리 페이지를 어느 프로세스의 어떤 가상 페이지가 쓰고 있는가”를 저장하죠. 대신 역방향 탐색이 필요하므로, 보통 해시 테이블과 함께 사용합니다. PowerPC 아키텍처가 이런 방식을 사용합니다.
페이지 테이블도 스왑될 수 있다?
놀랍게도 페이지 테이블도 너무 커지면 디스크로 스왑될 수 있습니다. OS는 커널 가상 메모리 공간을 이용해 페이지 테이블 일부를 디스크에 내보내고, 필요할 때 다시 불러옵니다. 이렇게 해서 물리 메모리 압박을 줄이는 거죠.
정리 — 작은 테이블, 큰 아이디어
- 단순한 선형 테이블은 낭비가 심하다.
- 세그먼트+페이징은 낭비를 줄이지만 복잡하다.
- 다단계 페이지 테이블은 낭비를 최소화하면서도 세그먼트보다 유연하다.
결국 다단계 페이지 테이블은 “필요한 만큼만, 동적으로” 메모리를 사용하는 구조입니다. 희소한 주소공간을 다루는 현대 OS에서는 거의 필수적인 설계죠.