[OSTEP] 20. Paging: Smaller Tables

1. 간단한 해결책: Bigger Pages#

가장 직관적인 방법은 Page Size를 키워서 페이지 수(=PTE 수)를 줄이는 것입니다.

예를 들어 32-bit 주소 공간에서 Page Size를 $4\text{KB} \rightarrow 16\text{KB}$로 올리면 다음과 같이 변화합니다.

• Offset: $12\text{bit} \rightarrow 14\text{bit}$
• VPN: $20\text{bit} \rightarrow 18\text{bit}$
• PTE 개수: $2^{20} \rightarrow 2^{18}$
• Page Table: $4\text{MB} \rightarrow 1\text{MB}$

즉, Page Size를 4배 키우면 Page Table도 정확히 4배 줄어듭니다.

2. Hybrid 접근법: Paging + Segmentation#

Linear Page Table이 큰 이유는 사용하지 않는 가상 주소 영역까지 PTE를 전부 만들어 들고 있기 때문입니다. 일반적인 프로세스 주소 공간은 Code, Heap, Stack만 듬성듬성 쓰고, 중간에 큰 Hole(빈 공간)이 남는 경우가 많습니다.

Figure 20.1: 대부분이 비어있는(Sparse) 주소 공간의 예시. 이 빈 공간을 위해 Page Table을 유지하는 것은 낭비입니다.

그래서 나온 아이디어가 “세그먼트별로 Page Table을 따로 두자” 입니다.

• Code segment용 Page Table
• Heap segment용 Page Table
• Stack segment용 Page Table

이때 Segmentation의 Base/Bounds 개념을 재활용합니다.

• Base: “세그먼트 자체의 시작”이 아니라 해당 세그먼트 Page Table의 물리 주소
• Bounds: 해당 Page Table의 끝(=유효한 페이지 개수)

3. Multi-level Page Tables#

Hybrid가 Segmentation을 끌어온 타협이라면, Multi-level은 Page Table 자체를 Paging하자 라는 접근입니다.

Figure 20.2: (문제점) 대부분이 Invalid인 Linear Page Table. 낭비되는 공간이 많습니다.

핵심 아이디어는 간단합니다.

1. Linear Page Table을 페이지 크기 단위로 조각냅니다.
2. 어떤 조각(Page Table Page) 안에 유효한 PTE가 하나도 없으면, 그 조각은 아예 할당하지 않습니다.
3. 대신, 어떤 조각이 존재하는지 추적하는 상위 구조가 필요합니다. → Page Directory

4. Multi-level을 손으로 따라가기: Detailed Example#

OSTEP는 Multi-level이 어떻게 인덱싱되는지를 작은 예제로 풀어줍니다.

가정:

• 주소 공간: $16\text{KB}$
• 페이지 크기: $64\text{B}$
• 가상 주소: $14\text{bit}$ (VPN $8\text{bit}$ + Offset $6\text{bit}$)
• PTE 크기: $4\text{B}$

Linear Page Table은 $2^8 = 256$ 엔트리 → $256 \times 4\text{B} = 1\text{KB}$가 됩니다. 그런데 페이지가 $64\text{B}$이므로, $1\text{KB}$ Page Table은 $1024 / 64 = 16$개의 Page Table Page로 나눌 수 있고, 각 Page Table Page는 $64 / 4 = 16$개의 PTE를 담습니다.

1
// 1. 가상 주소 분해
2
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
3
(PDIndex, PTIndex) = Split(VPN)
4

5
// 2. Page Directory 접근 (첫 번째 메모리 접근)
6
PDEAddr = PageDirBase + (PDIndex * sizeof(PDE))
7
PDE = AccessMemory(PDEAddr)
8

9
if (PDE.Valid == False) {
10
    RaiseException(SEGMENTATION_FAULT) // 존재하지 않는 조각
11
} else {
12
    // 3. Page Table 접근 (두 번째 메모리 접근)
13
    // PDE.PFN은 해당 Page Table Page의 물리 주소를 가리킴
14
    PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
15
    PTE = AccessMemory(PTEAddr)
16

17
    if (PTE.Valid == False) {
18
        RaiseException(SEGMENTATION_FAULT) // 유효하지 않은 페이지
19
    } else if (CanAccess(PTE.ProtectBits) == False) {
20
        RaiseException(PROTECTION_FAULT)
21
    } else {
22
        // 4. TLB 업데이트 및 재실행
23
        TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
24
        RetryInstruction()
25
    }
26
}

5. 더 깊은 계층: More Than Two Levels#

2-level로 끝나지 않는 이유는 간단합니다. “각 레벨의 조각이 한 페이지에 딱 들어가게 만들자” 가 목표인데, Page Directory 자체가 너무 커질 수 있기 때문입니다.

OSTEP 예제:

• VA = $30\text{bit}$
• Page = $512\text{B}$ → Offset $9\text{bit}$
• VPN = $21\text{bit}$
• PTE $4\text{B}$ → 한 페이지($512\text{B}$)에 PTE 128개 → 인덱스에 $7\text{bit}$ 필요

즉, $21\text{bit}$ VPN 중 하위 $7\text{bit}$는 PT Index로 쓰고 나면, 상위에 $14\text{bit}$가 남습니다. 그런데 Directory가 $2^{14}$ 엔트리이고 PDE가 $4\text{B}$라면, Directory 크기는 $2^{14} \times 4\text{B} = 64\text{KB}$로 128페이지가 됩니다. 이러면 Directory도 한 페이지에 들어가게 하자는 목표가 깨지므로, Directory를 다시 Paging하고 상위 Directory를 추가해서 트리를 더 깊게 만듭니다.

6. Inverted Page Tables#

Multi-level과는 다른 방향으로, 공간을 더 줄이는 접근이 Inverted Page Table입니다.

• “프로세스마다 Page Table”을 두는 대신,
• 시스템에 단 하나의 Page Table만 두고,
• 엔트리는 “가상 페이지”가 아니라 물리 페이지(Physical Page)마다 하나씩 둡니다.

즉, 각 엔트리는 대략 다음 정보를 담습니다.

• 이 물리 페이지를 누가(어떤 Process) 쓰는지
• 그 프로세스의 어떤 VPN이 매핑되는지

문제는 Lookup입니다. 가상주소(VPN) → PFN을 찾으려면 테이블을 검색해야 하므로, 선형 탐색은 비싸고 보통 해시(Hash) 를 사용하여 속도를 높입니다 (예: PowerPC).

7. Swapping the Page Tables to Disk#

지금까지는 Page Table이 항상 물리 메모리(커널 소유) 에 있다고 가정했습니다. 하지만 트릭을 다 써도 Page Table이 너무 커질 수 있고, 이때 일부 시스템은 다음과 같이 동작합니다.

• Page Table을 Kernel Virtual Memory에 두고,
• 메모리 압박이 크면 Page Table의 일부를 디스크로 Swap Out 하기도 합니다.

8. 요약 (Summary)#

• Bigger Pages: Page Table은 줄지만 Internal Fragmentation이 커짐.
• Hybrid (Paging + Segmentation): Hole을 피할 수 있으나, Page Table이 가변 크기로 흩어지며 외부 단편화 성격의 문제와 복잡성이 다시 등장.
• Multi-level Page Table: Page Table을 Page-sized 조각으로 나누고, 필요한 조각만 할당.
  • Sparse Address Space에 강함.
  • TLB Miss 시 Page Walk 비용(추가 접근)이 증가.
• More Than Two Levels: Directory도 Page-sized Unit으로 유지하려면 트리를 더 깊게 해야 함.
• Inverted Page Table: “물리 페이지당 1엔트리”로 공간을 줄이는 대신 Lookup을 해시 등으로 해결.
• Swapping PT to Disk: Page Table조차 메모리에 다 못 두면 일부를 디스크로 내릴 수 있음.

9. 용어 정리#

• Linear Page Table: VPN을 인덱스로 바로 접근하는 배열형 페이지 테이블
• Internal Fragmentation: 할당 단위(페이지) 내부에서 남는 낭비
• Hybrid (Paging + Segmentation): 세그먼트별로 별도 Page Table을 두는 접근
• Page Directory: Page Table 조각들의 존재/위치를 추적하는 상위 테이블
• PDE (Page Directory Entry): Page Directory의 엔트리 (조각 존재 여부 + PFN 등)
• Multi-level Page Table: Page Directory를 루트로 하는 트리형 페이지 테이블
• Page Walk: TLB Miss 시 Page Table을 따라가며 변환을 찾는 과정
• Inverted Page Table: 물리 페이지당 하나의 엔트리를 갖는 단일 페이지 테이블 구조

Reference#

• Operating Systems: Three Easy Pieces - Chapter 20: Paging: Smaller Tables