페이징의 공간 문제
지난번에 우리는 TLB(Translation Lookaside Buffer)를 통해 페이징의 치명적인 약점인 '느린 속도'를 극복하는 과정을 정리했다. 하드웨어의 도움으로 주소 변환 속도는 비약적으로 빨라졌다. 하지만 속도 문제를 해결하고 나니, 이제는 공간(Space) 문제가 발목을 잡았다. Huge Page Table 문제를 리뷰해보자:
32비트 주소 공간에서 4KB 페이지를 사용할 경우, 프로세스 하나당 약 4MB의 페이지 테이블이 필요하다. 100개의 프로세스가 돌면? 무려 400MB가 페이지 테이블 저장에만 쓰인다.
오늘은 이 거대한 메모리 낭비를 줄이기 위해 고안해낸 두 가지 전략, 하이브리드 기법(Hybrid Approach)과 멀티 레벨 페이지 테이블(Multi-level Page Table)에 대해 알아 본다.
그리고 물리 메모리 자체가 커서 발생하는 성능 저하를 해결하기 위한 역방향 페이지 테이블(Inverted Page Table), Huge Page에 대해 알아보겠다.
1. 선형 페이지 테이블의 비효율성
왜 이렇게 메모리가 낭비될까? 가장 단순한 형태인 선형 페이지 테이블(Linear Page Table)은 배열 형태다. 문제는 프로세스의 주소 공간 대부분이 비어 있다(Invalid)는 점이다.
우리는 힙(Heap)과 스택(Stack) 사이에 거대한 빈 공간이 있음을 알고 있다. 하지만 선형 테이블은 배열의 인덱스로 접근하기 때문에, 이 빈 공간에 대해서도 "여기는 비어있음(Invalid)"이라고 표시하기 위한 메모리 공간을 할당해야 한다. 쓰지도 않는 땅을 위해 등기부등본을 떼어놓는 꼴이다.
 |
| Lineaar Page Table |
2. 절충안: 하이브리드 기법 (Hybrid Approach)
"페이지 테이블의 낭비가 심하다면, 세그멘테이션의 아이디어를 빌려오면 어떨까?"
이것이 하이브리드 기법의 출발점이다.
개념: 세그멘테이션과 페이징의 결합
프로세스 전체에 대해 하나의 거대한 페이지 테이블을 만드는 대신, 논리적 단위인 세그먼트(Segment)별로 페이지 테이블을 나누어 관리하는 방식이다.
코드(Code)용 페이지 테이블
힙(Heap)용 페이지 테이블
스택(Stack)용 페이지 테이블
 |
| Hybrid Page Table |
작동 원리
이제 하드웨어의 Base 레지스터는 세그먼트의 시작 주소가 아니라, 해당 세그먼트의 페이지 테이블의 물리 주소를 가리킨다. Bound 레지스터는 페이지 테이블의 끝(크기)을 나타낸다.
 |
| Naive vs. Hybrid Approach |
한계점
이 방식은 힙과 스택 사이의 거대한 빈 공간에 대해 페이지 테이블을 만들지 않아도 되므로 메모리를 절약할 수 있다. 하지만 세그멘테이션이 가졌던 고질적인 문제, 외부 단편화(External Fragmentation)가 다시 발생한다. 페이지 테이블의 크기가 세그먼트마다 제각각이기 때문에(Variable size), 이를 물리 메모리에 연속적으로 할당하기가 까다롭기 때문이다.
 |
| Design of Hybrid Approach |
3. 정석적인 해결책: 멀티 레벨 페이지 테이블 (Multi-level Page Table)
하이브리드 방식의 한계를 넘어서기 위해, 현대 시스템은 멀티 레벨 페이지 테이블이라는 더 정교한 트리 구조를 채택했다.
핵심 아이디어: "페이지 테이블을 페이징하자"
이 기법의 핵심은 거대한 선형 페이지 테이블 자체를 잘게 쪼개는 것이다.
선형 페이지 테이블을 페이지 크기(예: 4KB) 단위로 자른다.
이 잘린 조각(Chunk)이 유효한지 아닌지를 관리하기 위해 페이지 디렉토리(Page Directory)라는 새로운 구조를 도입한다.
만약 특정 조각 내의 모든 항목이 '사용 안 함(Invalid)'이라면, 그 조각에 해당하는 페이지 테이블은 아예 할당하지 않는다.
 |
| Page Directory |
구조와 주소 변환
이제 가상 주소는 세 부분으로 나뉜다.
PD Index: 페이지 디렉토리에서 몇 번째 항목인지?
PT Index: 페이지 테이블에서 몇 번째 항목인지?
Offset: 실제 페이지 내 위치.
CPU는 PDBR(Page Directory Base Register)을 통해 디렉토리를 찾고, 거기서 페이지 테이블을 찾고, 최종적으로 물리 프레임을 찾아간다 (단계가 많아짐).
 |
| Exmple of Multi-level Page Table |
이때, 이름부터 '멀티 레벨'이듯, 페이지 디렉토리는 하나 이상이 될 수 있다.
 |
| Exmple of Multi-level Page Table (deep) |
장점: 메모리 효율성과 유연성
멀티 레벨 페이징은 두 가지 큰 이점을 준다.
메모리 절약: 사용하지 않는 주소 공간에 대해서는 페이지 테이블을 아예 만들지 않는다.
유연한 관리: 페이지 테이블 조각들이 물리 메모리에 연속적으로 있을 필요가 없다. 빈 공간 어디에든 흩뿌려 놓을 수 있어 관리가 매우 쉽다 [cite: 20].
단점: 시간-공간 트레이드오프 (Time-Space Trade-off)
하지만 세상에 완벽한 기술은 없다. TLB Miss가 발생했을 때의 비용이 커졌다.
기존: 페이지 테이블 접근(1번) -> 데이터 접근
멀티 레벨: 페이지 디렉토리 접근(1번) -> 페이지 테이블 접근(1번) -> 데이터 접근
메모리 공간을 아끼는 대신, TLB Miss 시 메모리 접근 횟수가 늘어나는(Latency) 비용을 지불한 것이다.
4. 관점의 전환과 스케일의 확장
앞서 다룬 멀티 레벨 페이지 테이블은 가상 주소 공간이 넓을 때 발생하는 낭비를 줄이는 데 탁월했다. 하지만 문득 이런 의문이 들 수 있다. "가상 주소 공간이 아니라, 물리 메모리 자체가 엄청나게 커지면 어떻게 되지?"
현대 시스템은 수십 기가바이트(GB)에서 테라바이트(TB) 단위의 물리 메모리를 탑재한다. 이런 환경에서는 프로세스마다 페이지 테이블을 따로 두는 것 자체가 부담일 수 있다. 이 문제를 해결하기 위해 매핑의 방향을 뒤집어버린 역방향 페이지 테이블(Inverted Page Table)과, 페이지 크기 자체를 키워 TLB 효율을 극대화하는 Huge Page 기법에 대해 알아보겠다.
5. 역방향 페이지 테이블 (Inverted Page Table)
기존 페이지 테이블의 논리는 "가상 주소 0번 페이지가 물리 주소 어디에 있는가?"였다. 즉, 가상 페이지 개수만큼의 항목(Entry)이 필요했다. 역방향 페이지 테이블은 이 질문을 뒤집는다.
"물리 주소 0번 프레임은 현재 어떤 프로세스의 몇 번 가상 페이지가 쓰고 있는가?"
핵심 구조 및 원리
이 테이블은 시스템 전체에 딱 하나만 존재한다. 테이블의 항목(Entry) 개수는 가상 페이지 개수가 아니라, 물리 메모리의 페이지 프레임 개수와 동일하다.
변환 방식: 가상 주소(VPN)가 들어오면, 해시 함수(Hash Function)를 통해 테이블의 인덱스를 찾는다.
매핑: 해당 인덱스(PTE)에 기록된
PID(Process ID)와VPN이 현재 요청한 것과 일치하는지 확인한다.결과: 일치한다면, 그 인덱스 자체가 물리 프레임 번호(PFN)가 된다.
 |
| Inverted Page Table |
장점: 메모리 효율성
프로세스가 몇 개든 상관없이, 페이지 테이블의 크기는 물리 메모리 크기에 비례하여 고정된다. 따라서 프로세스별로 테이블을 만들 필요가 없어 메모리 효율이 매우 높다.
단점: 해시 충돌과 공유의 어려움
물론 대가는 있다.
해시 충돌(Hash Collision): 서로 다른 VPN이 같은 해시 값을 가질 수 있다. 이 경우 체이닝(Chaining)으로 연결된 리스트를 뒤져야 하므로 최악의 경우 접근 시간이 길어진다.
페이지 공유(Page Sharing): 하나의 물리 프레임은 하나의 가상 페이지(VPN)와만 매핑되도록 설계되어 있어, 여러 프로세스가 메모리를 공유하는
Shared Memory구현이 까다롭다.
6. Huge Page: 크기가 곧 성능
페이지 테이블 구조를 아무리 개선해도 해결되지 않는 문제가 있다. 바로 TLB의 커버리지(Coverage)다.
메모리가 커지면 페이지 개수도 늘어나고, 한정된 용량의 TLB로는 전체 메모리의 아주 일부만 커버할 수 있다. 그 결과 TLB Miss가 빈번해져 성능이 떨어진다.
해결책은 단순하면서도 확실하다. "페이지를 크게 만들자."
기존 4KB 대신 2MB, 1GB 크기의 페이지를 사용하면, TLB 항목 하나가 커버하는 메모리 영역이 512배(4KB -> 2MB)로 늘어난다.
관리 방식: Explicit vs Transparent
Huge Page를 사용하는 방식은 크게 두 가지로 나뉜다.
Explicit Huge Page (Hugetblfs): 사용자가 직접 "나는 큰 페이지가 필요해"라고 OS에 예약하고 할당받는다. DB 같은 전문적인 애플리케이션에서 주로 쓴다.
Transparent Huge Page (THP): OS(Linux Kernel)가 알아서 관리한다. 사용자는 모르게 백그라운드에서 4KB 페이지들을 모아 2MB로 합친다.
THP의 작동 메커니즘
리눅스의 THP는 다음과 같은 과정을 통해 동적으로 페이지를 관리한다.
Promotion (승격): 가상 주소와 물리 주소가 모두 연속적인 4KB 페이지들이 발견되면, 이를 합쳐 하나의 Huge Page로 만든다 .
 |
| Promotion |
Compaction (압축): 물리 메모리에 연속된 공간이 부족하면, 흩어진 페이지들을 정리(Compaction)하여 거대한 페이지가 들어갈 공간을 만든다.
 |
| Compaction |
Demotion (강등): 메모리 압박이 심해지거나 일부만 해제해야 할 때, 다시 4KB로 쪼갠다.
 |
| Demotion |
THP의 한계: Latency Spikes
THP는 편리하지만 위험 요소가 있다.
Tail Latency: OS가 백그라운드에서 열심히 페이지를 합치고(Compaction) 옮기는 동안 CPU 자원을 쓰기 때문에, 애플리케이션의 반응 속도가 갑자기 느려지는 현상이 발생할 수 있다.
메모리 낭비: 2MB 페이지를 할당했는데 실제로는 4KB만 쓴다면 내부 단편화가 커진다.
그래서 데이터베이스(Oracle, Redis 등)는 예측 가능한 성능을 위해 THP를 끄는 것(Turn-off)을 권장하기도 한다.
마치며
컴퓨터 공학은 끊임없는 트레이드오프(Trade-off)의 연속이다.
하이브리드 기법은 메모리를 아꼈지만 외부 단편화를 불렀다.
멀티 레벨 페이지 테이블은 메모리 효율과 유연성을 모두 잡았지만, 복잡도와 TLB Miss 비용을 높였다.
역방향 페이지 테이블은 물리 메모리가 중심이 되는 시스템에서 공간 효율을 극대화했다.
Huge Page는 하드웨어 캐시(TLB)의 한계를 소프트웨어적 정책(크기 증가)으로 돌파했다.
이 모든 기술은 결국 주소 변환 비용을 최소화하기 위한 기법을 고안하는 과정에서 나온 결과물이다. 어떤 기법이 최고라고 말할 수는 없다. 시스템의 목적(범용 OS vs 전용 DB 서버)과 하드웨어 스펙에 따라 적절한 전략을 선택하는 안목이 필요함을 느낀다.
이것으로 페이징과 페이지 테이블에 대한 긴 공부를 마쳤다. 다음에는 물리 메모리가 꽉 찼을 때 벌어지는 일, 즉 Swapping(교체 알고리즘)에 대해 다루며 메모리 관리 학습을 마무리하려 한다.
