分頁表
分頁表（page table）是一種數據結構，它用於計算機操作系統中的虛擬內存系統，其存儲了虛擬地址到物理地址間的映射。虛擬地址在訪問進程中是唯一的，而物理地址在硬件（比如內存）中是唯一的[1]。
分頁表的角色
在操作系統中使用虛擬內存，每個進程會認為使用一塊大的連續的內存。事實上，每個進程的內存散布在物理內存的不同區域。或者可能被調出到備份存儲中(一般在硬盤)。當一個進程請求自己的內存，操作系統負責把程序生成的虛擬地址，映射到實際存儲的物理內存上。操作系統在分頁表中存儲虛擬地址到物理地址的映射。每個映射被稱為分頁表項（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的快速虛擬索引特性。
參考文獻
- ^ Home — Memory Management Reference 4.0 documentation. www.memorymanagement.org. [2018-08-15]. （原始內容存檔於2020-12-13）.
