分頁表
分頁表(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).