D-OS-Ch04cec-Inverted_Page_Table

Inverted Page Table

Motivation

我們想要節省 page table 所需的記憶體空間

Philosophy

傳統的 page table 都是以 page ID 為索引，也就是 page table 紀錄的是「對於一個 page ID，它對應的 frame ID 是什麼？」

Inverted page table 則是以 frame ID 為索引，整個系統維護「唯一的」page table，這個 page table 紀錄的是「對於每個 frame ID，它的使用者（process）是誰以及其對應的 page ID 是什麼？」

How it works?

1. CPU 請求 $(\text{pid},p,d)$ 對應的 physical address
2. 系統拿著 $(\text{pid},p,d)$ 去 inverted page table 搜尋 ($O(n)$)
3. 如果在 page table 第 $i$ 個位置找到 $(\text{pid},p)$ 則此 page 對應的 frame ID 就是 $i$
4. $(i,d)$ 便是所求 physical address

---

Analysis

Save space

page table 大小只取決於「實際 memory 大小」，不會因為 process 變多改變 page table 大小

Very Slow…

Inverted page table 需要搜尋整個表才能找到想要的東西

實務上會配合 hash table 來加速搜尋

---

Share Memory for Inverted Page Table

Challenge

share memory 要將多個 page 指向同一個 frame，但是 inverted page table 的設計注定讓一個 frame 只能對應到一個 page

Resolution

我們將每個 frame 對應的 entry 變成一個 linked list，這樣一個 frame 就可以對應到多個 $(\text{pid},p)$

---

Address-Space Identifier (ASID)

D-OS-Ch04ceca-ASID