反轉分頁表（inverted page table）

我們目前看過的每一種分頁表都按「頁」來組織：「這一頁，對應哪個頁框？」這意味著每個行程、每頁一筆項目——行程一多、位址空間一大，那就是龐大無比的表。把問題反過來問。實體記憶體只有「一份」、頁框數目固定，那何不保留「一張」按「頁框」組織的表，改問「這個頁框，此刻住著哪個行程的哪一頁？」這種翻轉的組織方式就是反轉分頁表：整台機器，每個實體頁框一筆項目。

具體而言，反轉分頁表的項目數恰好等於實體記憶體中的頁框數——一張全域的表，而非每個行程一張。第 i 號項目描述頁框 i，記錄此刻存在其中的是「哪一頁」，並標明這頁屬於哪個行程：所以每筆項目存一組（行程 id, 頁號）（外加控制位元）。因為這張表是以頁框為鍵、你卻以（行程, 頁）來查，翻譯時必須在表中「搜尋」內容與你手上的（行程 id, 頁號）相符的那一筆；找到它的索引就是頁框號。為了避免掃描所有項目，真實系統加上一個雜湊函式（與一個 TLB），讓搜尋從接近正確之處開始。最大的節省在空間：表的大小如今只取決於實體 RAM 的多寡，而非行程位址空間的數目或大小——所以無論你跑一個行程還是一千個，它都一樣大。

反轉分頁表在位址空間非常大的機器上才顯重要，那裡傳統的每個行程一張表會大得無法承受；某些 64 位元架構正是基於這個理由採用它。誠實的取捨是真實存在的。第一，查找更難：你無法單純以頁號索引，必須搜尋（因此要雜湊、因此 TLB 失誤時要多做工）。第二，也更棘手的是，「共享」頁變得彆扭：一般分頁表能用兩筆項目把兩個行程的頁對應到同一個頁框，但嚴格的反轉表每個頁框只有「一筆」項目，因此無法自然地記錄兩個不同的頁共用那個頁框——需要特別處理。所以反轉表以較慢、較複雜的查找與笨拙的共享，換取緊湊。