[OS] 페이지 테이블의 공간 효율화 단계: Multi-level과 Inverted Page Table

 

 

지난 포스팅에서 TLB의 도입으로 메모리에 2번 접근해서 시간이 증가하는 Page table의 문제는 해결해보았다. 오늘은 기존 array-based Page table의 남은 한 가지 문제점인 "사이즈가 너무 크다."라는 문제를 해결해 보려고 한다.

 

 

Page table의 문제

공간의 오버헤드가 발생한다. 

 

• 위를 보면 32bit 주소 공간에서 4KB 페이지를 이용할 때, 2³² / 2¹² = 2²⁰, 즉 2²⁰의 페이지가 나온다. 페이지마다 4바이트짜리 엔트리(PTE)가 필요하니까 4MB짜리 테이블이 프로세스 하나당 생긴다.

 

 

문제의 핵심 

문제는 간단하다.

공간 낭비다. Linear Page Table(선형 페이지 테이블)은 "가상 주소의 모든 페이지에 대해 하나씩 엔트리(PTE)를 갖는 단순한 구조"이다. 현실적으로 대부분의 프로세스는 주소 공간 전체를 쓰지 않는다. 코드, 힙, 스택을 빼면 나머지는 대부분 비어 있는(Invalid) 영역이다.

 

그런데 Linear Page Table은 이 비어 있는 구간조차 전부 엔트리를 갖고 있어야 한다. 말 그대로 "텅 빈 창고를 위해 창고 관리자 10만 명을 고용하는 꼴"이다.

 

 

---

 

 

Solution: 페이지를 키우자

 

"페이지 크기를 늘리면 테이블 크기도 줄겠지."

실제로 페이지 크기를 4KB에서 16KB로 키우면, 32비트 주소 공간에서 PTE 개수가 4분의 1로 줄어든다. (당연하다. 페이지 크기를 4KB에서 16KB로 키우면, 한 페이지가 담당하는 주소 범위가 넓어지므로 전체 페이지 수가 4분의 1로 줄어든다. 즉, 32비트 주소 공간에서offset 비트가 12 → 14로 증가하면서, 가상 페이지 번호(VPN) 비트가 20 → 18로 줄어들고, 이에 따라 PTE 수도 2²⁰ → 2¹⁸개로 감소한다.)

 

 

즉, 페이지 테이블이 4MB → 1MB로 줄어드는 셈이다.

하지만 페이지가 커질수록 내부 단편화(Internal Fragmentation)가 심해진다. 한 페이지 안에서 실제로는 데이터가 조금만 차지해도 남은 공간이 전부 낭비된다.

 

 

 

Observation

 

16KB 주소 공간에서 실제로 유효한 페이지는 코드, 힙, 스택 몇 개뿐이다. 나머지 대부분은 전부 invalid 상태다.

즉, 대부분의 페이지 테이블이 사용되지 않는 채로 있다. 이 지점에서 바로 Multi-level Page Table로 이어진다.

 

 

 

 

---

 

 

Multi-level Page Tables: 필요할 때만 공간을 쓰자

기본 아이디어는 간단하다. "Linear 페이지 테이블에서 낭비되는 공간을 만들지말자"

 

그래서 전체 페이지 테이블을 여러 "블록"으로 쪼개고(Page Table Page로 만든다), 그 블록을 관리하는 또 다른 테이블 페이지 디렉터리(Page Directory)를 만든다.

페이지 디렉터리가 각각의 블록을 체크해서 invalid라면 할당하지 않는다.

 

 

Page Directory의 역할은 "Page Table Page"가 어디 있는지 가리키는 지도이다.

• 각 항목 하나(= Page Directory Entry, PDE)가 "Page Table Page 하나"를 가리킨다.
• PDE 안에는 그 Page Table Page의 물리 주소(PFN)가 들어 있다.
• 그리고 그 Page Table Page가 유효한지 나타내는 Valid bit도 있다.

 

 

결국 우리가 갖게 되는 구조는 트리(Tree)처럼 생긴다. 필요한 부분만 실제 페이지 테이블을 두고, 나머지는 디렉터리에서 "비었음" 표시만 해두는 것이다.

 

Linear vs Multi-level Page Table

두 구조의 차이를 직관적으로 비교해보자.

• Linear Page Table:
  • 모든 페이지에 대해 엔트리를 하나씩 가짐.
  • 비어 있든 말든 다 관리해야 함.
• Multi-level Page Table:
  
  • 페이지 테이블을 여러 블록(Page Table Page)으로 나누고,
  • 그 블록이 실제로 필요할 때만 메모리에 올림.
  • 그리고 그 블록들을 찾기 위해 Page Directory라는 상위 표를 둔다.
    → 즉, 필요한 페이지 테이블만 존재한다.

 

Page Directory는 "어디에 어떤 Page Table이 있는지"를 알려주는 지도 같은 존재다. 각 항목(PDE, Page Directory Entry)은 "이 구간에 대응하는 페이지 테이블이 실제로 존재하는가?" 를 알려주는 Valid Bit, 그리고 "존재한다면 그 페이지 테이블이 메모리의 어디 있는가?"를 나타내는 PFN(Page Frame Number)를 가진다.

 

 

 

1. 처음엔 단일 테이블(Linear)로 시작한다. 가상 주소 공간 전체에 대해 PTE를 다 만들어둔다.

 

 

2. 다음엔 테이블을 잘게 나눈다.
→ 각 테이블 조각을 "Page Table Page"로 만든다.
→ 그리고 이 조각들을 가리키는 "Page Directory"를 만든다.

 

 

 

3. 이제 구조는 트리(Tree)처럼 바뀐다. 루트(Page Directory)→ 자식(Page Table Pages)→ 리프(Actual Pages)

이 트리 구조는 놀라울 정도로 단순하면서 효율적이다. 안 쓰는 부분(= invalid PTE만 있는 구간)은 아예 Page Table Page 자체를 만들지 않는다. 이게 바로 메모리를 절약하는 핵심 포인트다.

 

 

주소 변환 과정 

Multi Level Page Table을 쓰면 주소 변환도 살짝 복잡해진다. 이제 가상 주소(VA)는 3부분으로 쪼개진다.

1. One page directory Index → 어느 하위 테이블(Page Table Page)을 볼지 결정
2. Secondary Page Table Index → 그 하위 테이블에서 어떤 엔트리를 볼지 결정
3. Offset → 실제 물리 페이지 내 위치

 

결국 주소 하나 변환하려면 두 번의 메모리 접근(디렉터리, 테이블)이 필요하다. 조금 느려지긴 하지만, 메모리 낭비는 획기적으로 줄어든다.

 

"시간을 조금 쓰고 공간을 아낀다."

바로 시간-공간 트레이드오프(Time-Space Tradeoff)의 전형이다.

 

 

Two-Level Page Tables

32비트 시스템을 예로 들어보자.

• 페이지 크기: 4KB
• 한 PTE 크기: 4B
• 페이지 크기가 2^12B니까 offset은 12bits
• VPN이 20bits인데 Multi Level Page Table에서는 두 단계로 나눔
  • Page Directory 자체도 한 페이지(4KB)에 딱 들어가게 만들자. (Page Directory도 결국 메모리에 저장되는 하나의 테이블 이기 때문)
  • 즉, 한 페이지 크기 / 엔트리 하나의 크기(PDE)이므로, Page Directory 안에는 1024개의 PDE가 들어간다. (4KB / 4B = 1024)
  • 따라서 Page Directory는 10bits, Secondary도 10bits

 

주소 비트는 이렇게 나뉜다.

• Directory (Page Directory)
  • 어느 Page Table Page를 봐야 하는가를 알려주는 상위 테이블
• Secondary (Page Table Page)
  • 그 안에서 어떤 물리 페이지로 매핑되는가를 담은 실제 테이블

 

 

 

---

 

 

Multi Level Page Table의 장단점

장점

• 메모리 효율적
  → 안 쓰는 페이지 테이블은 아예 만들지 않음.
• 유연한 구조
  → 페이지 단위로 나눠서 메모리에 연속되지 않고 흩어놔도 됨.
  (큰 연속 공간이 필요 없음)
• 동적으로 확장 가능
  → 프로그램이 커지면 필요한 부분만 새로 할당 가능.

단점

• 주소 변환 속도가 느림
  (예전엔 한 번에 되던 게 이제 두세 번 접근해야 함)
• 구조가 복잡해짐
  (OS 입장에서 관리해야 할 단계가 늘어남)

 

 

"시간과 공간의 트레이드오프."
공간을 아끼려면 시간이 들고, 속도를 높이려면 공간이 든다.

 

 

 

 

구체적인 예시: 16KB 주소 공간

예시를 보자.

 

 

전체 전제

• 가상 주소 공간: 16KB = 2¹⁴ → 가상 주소 길이 14비트
• 페이지 크기: 64B = 2⁶ → Offset = 6비트
• 남는 비트(= VPN): 14 − 6 = 8비트 → VPN = 8비트 (총 256 페이지)
• PTE 크기: 4B

 

Linear Page Table

• PTE 개수: 256(=2⁸)
• 테이블 크기: 256 × 4B = 1KB

 

 

이걸 Multi Level Page Table로 바꿔보자

 

Step 1: Split Table into Page-Sized Units

• "페이지 단위(64B)"로 Page Table을 쪼갠다는 뜻.
• 1KB(= 1024B) ÷ 64B = 16개의 Page Table Page(PT Page)
• PT Page 한 장에 들어가는 PTE 수: 64B ÷ 4B = 16개
  → 즉, 각 PT Page = PTE 16개를 담음.

이렇게 하면 Page Table 전체(1KB)가 64B짜리 블록 16개로 나뉨.

 

Step 2: Index into Page Directory

• 이제 이 16개 PT Page를 가리키는 Page Directory가 필요.
• PDE(디렉터리 엔트리) 개수 = PT Page 개수 = 16
• PDE 크기 = 4B → Page Directory 전체 크기 = 16 × 4B = 64B
  (한 페이지(64B)에 딱 맞음 → "fit in a page")

 

중요한 비트 분할

• 전체 가상 주소는 14비트이고, Offset이 6비트이므로 VPN은 8비트.
• 이 VPN 8비트를 다시 상위 4비트 + 하위 4비트로 쪼갠다:
  • 상위 4비트 → Page Directory Index (PDIndex)
    (왜 4비트? 디렉터리 엔트리가 16개 = 2⁴개이니 4비트로 인덱싱)
    • 역할: Page Directory에서 PDE[PDI]를 찾는다. 그 PDE는 "해당 Page Table Page의 물리 주소"를 가리킨다.
  • 하위 4비트 → Page Table Index (PTIndex)
    (각 PT Page 안에 PTE가 16개 = 2⁴개)
    • 역할:  PDE가 가리킨 Page Table Page로 가서, 그 안에서 PTE[PTI]를 찾는다.

 

 

 

 

 

Step 3: Page Table Page에서 PTE 찾기

이 단계까지 연결해 보면 완전히 이해가 된다.

1. PDE 주소 계산: PDEAddr = PageDirBase + (PDIndex × sizeof(PDE)) = PageDirBase + (PDIndex × 4)

• PDE의 valid=0이면: 해당 범위는 PT Page 자체가 없음 → 페이지 폴트

 

2. PTE 주소 계산 (PDE가 valid일 때):

PTEAddr = (PDE.PFN << PAGE_SHIFT) + (PTIndex × sizeof(PTE)) = PTPageBase + (PTIndex × 4)

• PDE 안의 PFN으로 그 PT Page의 물리 주소를 얻는다.

 

3. 물리 주소 완성: PhysAddr = (PTE.PFN << PAGE_SHIFT) + Offset

• PTE가 가리키는 물리 프레임(PFN) + Offset(6비트)

 

 

계산 정리

상위 비트 (Page Directory Index)	전체 페이지 테이블을 여러 'Page Table Page'로 나눈 것 중 하나를 고르는 비트	전체 Page Table 크기 ÷ 한 Page 크기 → 조각 개수 → log₂(조각 개수)	PDE index 비트 수
하위 비트 (Page Table Index)	선택된 Page Table Page 안에서 몇 번째 PTE를 고르는 비트	한 Page 크기 ÷ 한 PTE 크기 → PTE 개수 → log₂(PTE 개수)	PTE index 비트 수
마지막 비트 (Offset)	실제 페이지 내부 바이트 주소	페이지 크기 = 2ⁿ → n비트	Offset 비트 수

 

 

 

크기 비교

Linear Page Table	16개의 페이지
Multi-Level Page Table	3개의 페이지만 필요 (1 Page Directory + 2 valid Page Table Pages)

안 쓰는 페이지 테이블을 만들지 않아서 메모리 절약이 가능하다는 걸 보여준다. (코드, 힙, 스택만 쓰니까 2개만 유효)

 

 

---

 

 

실제 주소 변환 예시

가상 주소 예: 0x3F80 (2진수로 1111 1110 000000) 이 주소의 구성은 다음과 같이 쪼개진다

• 상위 4비트 (1111) → Page Directory Index (15번 PDE)
• 다음 4비트 (1110) → Page Table Index (14번 PTE)
• 하위 6비트 (000000) → 페이지 내부 offset

변환 과정

1. Page Directory 탐색

• PDI = 1111 (15)
• Page Directory의 15번째 엔트리(PDE[15])를 읽는다.
• PDE[15]의 Valid bit = 1, PFN = 101 (이건 Page Table Page의 프레임 번호).
  → 즉, Page Table Page #5(2진 101번 프레임)를 가리킴.

2. Page Table 탐색

• PDE가 가리키는 Page Table Page(프레임 #5)로 이동.
• PTI = 1110 (10진수 14)
• 해당 Page Table Page의 14번째 PTE를 읽는다.
• 그 PTE는 실제 물리 페이지 프레임 번호(PFN) = 55

3️⃣ Offset 추가

페이지 크기가 64B(=2⁶)니까

• 최종 물리 주소 = (PTE.PFN << 6) + offset
• 즉, 물리 주소는 PFN × 페이지 크기 + offset

 

---

 

 

More than Two Levels

현실의 시스템은 주소공간이 훨씬 크다. 그래서 2단계로는 테이블 자체가 너무 커져서 감당이 안 된다.

문제 상황

• 가상 주소: 30비트 (약 1GB 주소 공간)
• 페이지 크기: 512B = 2⁹ bytes
  → Offset = 9비트
  → 남은 21비트가 VPN

 

 

한 PTE 크기 = 4B
한 페이지 크기 = 512B

→ 한 페이지에 들어가는 PTE 수: 512 / 4 = 128개 = 2⁷

즉, Page Table Page 하나가 2⁷개의 PTE를 가짐.

 

전체 PTE 수 = 2²¹

각 페이지당 2⁷개 PTE → 필요한 페이지 테이블 페이지 수 = 2²¹ / 2⁷ = 2¹⁴ (16384개)

즉, 페이지 테이블 하나 만들려면 16,384개의 페이지가 필요하다. → Page Directory에 2¹⁴개의 항목이 필요하다는 뜻이다

 

 

Page Directory의 크기를 계산

• PDE 개수: 2¹⁴
• PDE 하나 크기: 4B
  → Page Directory 크기 = 2¹⁴ × 4B = 64KB

한 페이지 크기 = 512B인데, Page Directory 크기가 64KB면 128페이지를 차지한다.

즉, Page Directory 자체가 한 페이지(512B)에 들어가지 않게 되면, 이를 다시 쪼개서 또 다른 디렉터리로 관리해야 한다. 이것이 바로 '3-Level Page Table' 구조가 등장한 이유이다.

 

 

 

 

해결책: Page Directory도 페이지 단위로 쪼개자

이게 바로 3단계 페이지 테이블(Three-Level Page Table) 개념이다.

"Page Table을 쪼갰듯이, Page Directory도 쪼개서 여러 페이지로 만들자."

• 최상단: Top-level Directory (상위 디렉터리)
• 중간단: Page Directory (중간 디렉터리)
• 하단단: Page Table Page (실제 PTE들이 있는 곳)

 

이제 각 레벨의 크기를 맞춰서 한 페이지에 꼭 맞게 만든다.

 

 

 

상위 7비트	1st Directory Index	최상위 디렉터리에서 어떤 Page Directory를 볼지
중간 7비트	2nd Directory Index	그 Page Directory 안에서 어떤 Page Table Page를 볼지
하위 7비트	Page Table Index	해당 Page Table Page 안의 어떤 PTE를 볼지
마지막 9비트	Offset	512B 페이지 내부 주소

 

 

각 테이블(Page Table, Page Directory, Top Directory) 모두 → 자기 자신이 한 페이지(512B)에 꼭 맞게 설계되어 있음.

 

단계 수(level)는 주소 공간 크기에 따라 가변적
→ 16KB면 2단계로 충분
→ 1GB면 3단계 필요
→ 64bit 시스템이면 4단계 이상 필요

 

 

---

 

 

 

 

Inverted Page Tables: 페이지 테이블을 뒤집어서 효율을 높이자

우리가 지금까지 배운 페이지 테이블은 모두 가상 주소 → 물리 주소 방향이었다.
즉, Virtual Page Number(VPN) 를 넣으면 Physical Frame Number(PFN) 가 나오는 구조다.

근데 여기서 문제가 생긴다. 프로세스가 많아지고 주소 공간이 커질수록, 프로세스마다 이런 테이블을 하나씩 들고 있으면 메모리가 터져버린다. 

 

그래서 생각한게 "거꾸로 하면 어떨까?"이다.

 

기존 방식의 문제

기존 페이지 테이블 구조를 다시 보면 이렇게 생겼다 

VPN	PFN
0x00	5
0x01	9
0x02	2

프로세스마다 이런 테이블을 하나씩 갖고 있고, 각 테이블은 "내 가상 페이지(VPN)가 물리 메모리의 어디(PFN)에 있는가"를 기록한다. 문제는, 프로세스가 많을수록 이 테이블도 기하급수적으로 많아진다는 것.
→ 프로세스 100개면 테이블도 100개
→ 그 중 대부분은 invalid (빈 공간)
→ 결국 메모리 낭비가 심하다.

 

 

핵심 아이디어

기존의 “가상 → 물리” 매핑을 “물리 → 가상”으로 뒤집는다.

기존 (일반 Page Table)	Inverted Page Table
각 가상 페이지마다 물리 프레임 번호를 저장	각 물리 프레임마다 어떤 가상 페이지가 연결됐는지 저장

 

즉, 기존엔 프로세스마다 내가 가진 가상 주소 → 물리 주소를 기록했다면, 이제는 이 물리 메모리 페이지는 어떤 프로세스의 어떤 가상 페이지와 연결되어 있는가를 기록하는 구조이다. 이 테이블은 "PFN 기준으로 정렬되어 있다" 따라서 N개의 물리 프레임이 있다면 엔트리도 N개이다.

 

 

CPU 입장

CPU는 여전히 가상 주소를 가지고 메모리에 접근하려고 한다. 즉, 어떤 프로세스가 이렇게 말한다 "나는 PID=5, VPN=0x12 페이지에 접근하고 싶다"

그럼 CPU는 이 정보를 가지고 Inverted Page Table에서 "이 페이지가 어떤 물리 프레임(PFN)에 저장되어 있는가?"를 찾아야한다. 여기서 PID(Process ID)를 함께 사용하는 이유는, 서로 다른 프로세스가 같은 VPN을 가질 수 있기 때문이다. 따라서 <PID, VPN>의 조합을 통해 시스템 전체에서 유일한 식별 키(Key)를 만들 수 있다.

 

검색 방법 1: 선형 탐색 (너무 느림)

테이블이 PFN 기준으로 정렬되어 있으니까, CPU는 테이블 전체를 돌면서 일치하는 항목을 찾아야 한다.

이 방식은 시간낭비가 너무 심하다. 

 

검색 방법2: 해시(Hashing)

이 문제를 해결하기 위해 해시 테이블(Hash Table) 구조를 도입한다. 핵심 아이디어는 간단하다.

<PID, VPN>을 합쳐서 하나의 키(Key)로 만들고, 이 키를 해시 함수에 넣어서 해당 PFN을 바로 찾아내자.

 

 

 

 

 

구조적으로 보면

• 시스템 전체에 딱 하나의 페이지 테이블만 존재
• 각 물리 페이지(Frame)에 엔트리 하나씩 존재
• 각 엔트리에는 <PID, VPN>이 저장돼 있다. (즉, 이 물리 프레임은 어느 프로세스의 어느 가상 페이지인가)

 

 

작동 방식

1. TLB Miss가 발생하면, 운영체제는 Inverted Page Table을 검색해야한다.
2. <PID, VPN>이 일치하는 항목을 찾아야 하므로, 단순 선형 검색은 비효율적이므로 → 해시(Hashing)를 사용한다.
3. 해시 테이블은 <PID, VPN> 쌍을 해싱해서 빠르게 해당 물리 프레임(PFN)을 찾을 수 있도록 한다.

 

 

Inverted Page Tables의 장단점

장점

• 시스템 전체에 테이블 하나만 있어서 메모리 사용량이 감소한다.

단점

• 해시 검색이 필요하므로 검색 속도가 느리고, 해시 충돌 가능성이 있다. 

 

결국 Inverted Page Table은 메모리를 극단적으로 아끼는 대신, 검색 속도를 포기하는 구조라고 보면 된다.

 

 

---

 

 

 

정리

 

문제	Linear Page Table은 대부분 invalid 엔트리로 낭비가 많음
해결책	Multi-Level Page Table을 사용해 필요한 테이블만 생성
구조	주소를 [상위 인덱스][하위 인덱스][Offset]으로 분리
확장	3-Level, 4-Level 구조로 큰 주소공간 지원
trade-off	메모리는 절약되지만, 탐색 단계가 늘어나서 속도는 느려짐

메모리 효율을 위해 시간(탐색단계)을 희생한 구조다.

 

 

결국 Paging의 발전은 공간을 효율적으로 쓰기 위한 단계이다. Linear → Multi-level → Inverted로 갈수록 메모리 절약은 커지지만, 주소 변환은 점점 복잡해진다. 운영체제는 이 두 가지 사이에서 끊임없이 균형을 맞추는 구조를 택하고 있다.

 

 

 

 

 

출처: 경북대학교 한명균 교수님, “운영체제” 강의 자료