Hierarchical Page Table
Why we need it?
對於 32-bit 系統，每個 process 都需要一個 4MB 的 page table（假設 page 4KB），並且這 4MB 還必須是連續的
而且一個 process 也根本不會用到整個 4GB 的 logical address space——大部分的 entry 實際上都是 invalid，所以這 4MB 只是在浪費空間
Basic Concept
Introduction
我們讓 page table 本身也分頁，原本
| ---- 20 bits (page number) ---- | --- 12 bits (offset) --- |
變成
| p1 (10 bits) | p2 (10 bits) | d (12 bits) |
整個翻譯的過程變成三個步驟：
- CPU 拿出 ，去查 outer page table，找到對應的 inner page table 的地址
- 拿著 的地址去查那張 inner page table，找到實際的 frame number
- 把 frame number 和 offset 接起來得到 physical address
Analysis
Why save space?
outer page table 的每個 entry 對應著一張 inner page table，但 inner page table 可能整張都沒被用到過
因此，在 process 剛建立時我們可以只建立 outer page table，只有當該 inner page table 中的某個 entry 變成 valid 時我們才建立對應的 inner page table
Doesn’t save time…
每次 TLB miss 時我們會需要先查 outer page 再查 inner page，然後拿著 physical address 得到資料 需要三次 memory access
所以實際上所需時間更長
Hierarchical Page Table for 64-bit Architectures
對於 64-bit 的架構我們會有更多的 page entries 需要分成更多 page，所以會變成像是有 outer page 1, outer page 2,…
但這樣會讓 overhead 變超大，所以對於 64-bit 系統我們不會用此方式