分頁表

**分頁表**（page table）是一種資料結構，它用於電腦作業系統中的虛擬記憶體系統，其儲存了虛擬位址到實體位址間的對映。虛擬位址在存取行程中是唯一的，而實體位址在硬體（比如記憶體）中是唯一的。

## 分頁表的角色

在作業系統中使用虛擬記憶體，每個行程會認為使用一塊大的連續的記憶體。事實上，每個行程的記憶體散布在實體記憶體的不同區域。或者可能被調出到備份儲存中 (一般在硬碟)。當一個行程請求自己的記憶體，作業系統負責把程式生成的虛擬位址，對映到實際儲存的實體記憶體上。作業系統在分頁表中儲存虛擬位址到實體位址的對映。每個對映被稱為分頁表項（page table entry，PTE）。

## 轉換過程

CPU 的記憶體管理單元（memory management unit MMU）儲存最近用過的對映快取，來自作業系統分頁表。被稱為轉譯後備緩衝區（translation lookaside buffer, TLB）。TLB 是一個索引快取。

當需要將虛擬位址轉換為實體位址時，首先搜尋 TLB。如果找到匹配（TLB 命中），則返回實體位址並繼續記憶體存取。然而，如果沒有匹配（稱為 TLB 未命中），則記憶體管理單元或作業系統 TLB 未命中處理器通常會尋找頁表中的位址對映以檢視是否存在對映（頁面遍歷）。如果存在，則將其寫回 TLB（這必須完成，因為硬體通過虛擬記憶體系統中的 TLB 存取記憶體），並且重新啟動錯誤指令（這也可以並列發生）。此後續轉換將找到 TLB 命中，並且記憶體存取將繼續。

## 轉換失敗

有兩種原因導致分頁表尋找失敗。第一種，如果該位址沒有可用的轉換，這意味該虛擬位址的記憶體存取是無效的。這通常是程式錯誤導致，作業系統需要處理這個問題。現代作業系統會傳送一個段錯誤訊號給出錯程式。

當實體記憶體中不存在這個頁，也會引起分頁表尋找失敗。如果請求的頁面被調出實體記憶體，給其他頁騰出空間，會引起這個錯誤。這種情況下，頁被分配到儲存在媒介上的輔助儲存，例如硬碟。（這種輔助儲存，或叫備用儲存，如果是一個硬碟分割區或者交換檔案，經常稱之為交換分割區，如果是檔案，叫做分割區檔案或頁檔案。）這時候，分頁需要從硬碟放回到實體記憶體中，這類操作通常會導致一種稱為系統抖動（thrashing）的情況，通過局部性原理（principle of locality）來預測將來可能會存取的塊，避免出現系統抖動。

當實體記憶體沒滿的時候，這是一個簡單操作。頁被寫回實體記憶體，頁表和轉換備用緩衝會更新，指令重新啟動。然而，當實體記憶體已滿，一個或多個頁要被調、為請求的頁面騰出空間時候。頁表需要更新，標識出那些在實體記憶體被調出的頁，然後標識那些從硬碟調入實體記憶體的頁。TLB 也需要更新，包括去掉調出的頁，重新啟動指令。頁的調入調出請見頁置換演算法。

## 分頁表資料

最簡單的分頁表系統通常維護一個影格表和一個分頁表。影格表處理影格對映資訊。更進階系統中，影格表可以處理頁屬於的位址空間，統計資訊和其他背景資訊。

分頁表處理頁的虛擬位址和物理影格的對映。還有一些輔助資訊，如當前存在標識位 (present bit)，髒資料標識位或已修改的標識位，位址空間或行程 ID 資訊。

輔助儲存，比如硬碟可以用於增加實體記憶體。頁可以調入和調出到實體記憶體和磁碟。當前存在標識位可以指出那些頁在實體記憶體，哪些頁在硬碟上。頁可以指出如何處理這些不同頁。是否從硬碟讀取一個頁，或把其他頁從實體記憶體調出。

髒資料標識位可以最佳化效能。一個頁從硬碟調入到實體記憶體中，讀取後調出，當頁沒有更改不需要寫回硬碟。但是如果頁在調入實體記憶體後被修改，會標記其為髒資料，意味著該頁必需被寫回備用儲存。這種策略需要當頁被調入到記憶體後，後備儲存保留一份頁的拷貝。有了髒資料標誌位，一些頁隨時會同時存在於實體記憶體和後備儲存中。

如果不是單位址空間作業系統，位址空間或行程 id 資訊是必要的，記憶體管理系統需要知道頁對應的行程。兩個不同意圖的行程可以使用兩個相同的虛擬位址。分頁表必需為兩個行程提供不同的虛擬記憶體。用虛擬記憶體頁關聯行程 ID 頁可以幫助選擇要調出的頁，當頁關聯到不活躍行程上，特別是那些主要頁碼被調出的行程，相比活躍行程需要頁的可能性會更小。

## 分頁表類型

有一些不同的分頁表類型，適合不同應用場景。本質上，准系統分頁表必需儲存虛擬位址，實體位址排在之後，還有一些可能的位址空間資訊。

### 倒排分頁表

_倒排分頁表_(IPT) 被認為是一個標準 RAM 的 TLB 的 off-chip 擴充。不同於一個真實的分頁表，IPT 不需要處理所有當前對映。作業系統要準備處理遺失，就像 mips 風格的軟體填充 TLB。

IPT 把分頁表和影格表結合成一個資料結構。其核心是一個固定大小的表，表的行數等於記憶體中的影格數。如果有 4000 個影格，倒排分頁表有 4000 行。每個行的表項對應虛擬記憶體頁碼，物理頁頁碼（不是實體位址），一些其他資料，建立碰撞鏈。

從所有 IPT 核心結構中搜尋表項效率很低，所以我們用雜湊表來對映虛擬位址（或可能需要的位址空間 / PID 資訊）對應的 IPT 索引，這裡會使用衝突鏈。雜湊表被稱作雜湊錨點表。雜湊方式沒對覆蓋率做通常的最佳化，原始速度更理想。當然，雜湊表會有衝突。由於這個雜湊方式，我們使用時候會經歷很多衝突，所以表中 VPN 建立的每個表項，會檢查是否是已被檢索的表項或衝突。

在搜尋對映時候，使用雜湊錨點表。如果沒有表項存在，會出現一個頁錯誤。否則，表項被找到。依賴於架構，表項被重新放入 TLB，記憶體指令重新啟動，或跟蹤衝突鏈直到結束，然後出現頁錯誤。

這種模式種，一個虛擬位址可以分成 2 部分。前半段是虛擬頁碼，後半段是頁中的偏移量。

這種設計的主要問題在於雜湊方式 cache 命中率較弱。基於樹的設計，忽略在分頁表表項中置換相鄰位置的相鄰頁。但是一個倒排分頁表把表項離散，會破壞參照的空間局部性。為了減少這個問題，作業系統會使雜湊表空間最小，平衡增長的未命中比率。通常會有一個雜湊表，在實體記憶體中連續，共享給所有行程。記憶體碎片會導致預處理分頁表不現實，所以用一個預處理標識消除不同行程的頁的歧義。從行程中去掉分頁表項或許有點慢，作業系統會忽略重用預處理標識值，延遲面對這個問題，選擇忍受大量記憶體浪費，用於對映預處理雜湊表。

### 多級分頁表

倒排分頁表為所有實體記憶體中的影格，建立一個對映列表。但是這個可能會比較浪費。相反，我們通過保持一些覆蓋當前虛擬記憶體區塊的分頁表，建立一個包含虛擬頁對映的分頁表資料結構。比如，我們建立 1024 個小於 4K 的頁，覆蓋 4M 的虛擬記憶體。

這非常有用，因為通常虛擬記憶體的頂部和底部用於正在執行的行程，頂部通常用於文字和資料段，底部用於堆疊，空閒記憶體居中。多級分頁表會保持少量較小分頁表，僅覆蓋記憶體頂部和底部，只有確實需要時候才建立新的。每種較小分頁表被一個主分頁表連結再一起，有效的建立一個樹型資料結構。需要不只 2 級，可能有多級。

這種模式下，一個虛擬位址可以分成三部分：根分頁表的索引，子分頁表的索引，子分頁表偏移量。多級分頁表也叫做分級分頁表。

### 虛擬分頁表

已經提到了，在虛擬位址空間中為每個虛擬頁建立分頁表結構，最終會導致浪費。但是我們可以把分頁表放入虛擬記憶體，允許虛擬記憶體管理分頁表記憶體，來避免過多空間被涉及。

但是一部分這種線性分頁表結構，需要一直存在於實體記憶體，來防範迴圈頁錯誤。會尋找一個不存在於分頁表中的重要部分，在當前分頁表中沒有。

### 巢狀分頁表

巢狀分頁表可以被用於增加硬體虛擬化的效能。為分頁表虛擬化提供硬體支援，會大大降低類比的需要。x86 下虛擬化當前的選擇是 Intel 的擴充分頁表特性，和 AMD 的快速虛擬索引特性。

## 參考文獻

## 參見

* 轉譯後備緩衝區
* 快取檔案置換機制
* 指標
* PaX
* W^X