分頁表(page table)是一種數據結構,它用於電腦作業系統中的虛擬記憶體系統,其儲存了虛擬地址到實體位址間的對映。虛擬地址在訪問行程中是唯一的,而實體位址在硬件(比如主記憶體)中是唯一的[1]

分頁表的角色

Thumb
Relationship between pages addressed by virtual addresses and the frames in physical memory, within a simple address space scheme. Physical memory can contain pages belonging to many processes. Pages can be paged to disk if used infrequently, or if physical memory is full. Not all pages are in physical memory in the above diagram.

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

轉換過程

Thumb
虛擬地址到實體位址的轉換過程。 如果虛擬記憶體地址不存在於TLB,轉換會被重設並通過分頁表和硬件尋找。

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的快速虛擬索引特性。

參考文獻

參見

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.