C語言中文網
首頁 > 編程筆記 > 操作系統筆記 閱讀:858

頁表結構完全攻略

本節我們將探討組織頁表的一些最常用技術,包括分層分頁哈希頁表倒置頁表

分層分頁

大多數現代計算機系統支持大邏輯地址空間(232?264)。在這種情況下,頁表本身可以非常大。例如,假設具有 32 位邏輯地址空間的一個計算機系統。如果系統的頁大小為 4KB(212),那么頁表可以多達 100 萬的條目(232/212)。假設每個條目有 4 字節,那么每個進程需要 4MB 物理地址空間來存儲頁表本身。顯然,我們并不想在內存中連續地分配這個頁表。這個問題的一個簡單解決方法是將頁表劃分為更小的塊。完成這種劃分有多個方法。

兩級頁表方案
圖 1 兩級頁表方案

一種方法是使用兩層分頁算法,就是將頁表再分頁(圖 1)。例如,再次假設一個系統,具有 32 位邏輯地址空間和 4K 大小的頁。一個邏輯地址被分為 20 位的頁碼和 12 位的頁偏移。因為要對頁表進行再分頁,所以該頁碼可分為 10 位的頁碼和 10 位的頁偏移。這樣,一個邏輯地址就分為如下形式:


 
其中 ρ1 是用來訪問外部頁表的索引,而 ρ2 是內部頁表的頁偏移。采用這種結構的地址轉換方法如圖 2 所示。

兩級32位分頁架構的地址轉換
圖 2 兩級 32 位分頁架構的地址轉換

由于地址轉換由外向內,這種方案也稱為向前映射頁表

考慮一個經典系統 VAX 的內存管理。VAX 是數字設備公司的小型機。從 1977 年到 2000 年,VAX 是最受歡迎的小型機。VAX 架構支持兩級分頁的一種變體。

VAX 是一個 32 位的機器,它的頁大小為 512 字節。進程的邏輯地址空間分為 4 個區,每個區為 230 字節。每個區表示一個進程的邏輯地址空間的不同部分。邏輯地址的頭兩個高位表示適當的區,接下來的 21 位表示區內的頁碼,最后的 9 位表示所需的頁內偏移。

通過這種分頁方式,操作系統可以僅當進程需要時才使用某些區。虛擬地址空間的有的區經常根本未使用,多層頁表也沒有這些空間的條目,進而大大減少了存儲虛偽內存數據結構的所需內存。

VAX 架構的一個地址如下:

VAX 架構地址

其中 s 表示區號,ρ 是頁表的索引,而 d 是頁內偏移。即使采用此方法,一個 VAX 進程如使用一個區,單層頁表的大小為 221X4B = 8MB。為了進一步減少主存的使用,VAX 對用戶進程的頁表進行分頁。

對于 64 位的邏輯地址空間的系統,兩層分頁方案就不再適合。為了說明這一點,假設系統的頁面大小為 4KB(212)。這時,頁表可由多達 252 個條目組成。如果采用兩層分頁,那么內部頁表可方便地定為一頁長,或包括 210 個 4 字節的條目。地址形式如下圖所示:


外部頁表有 242 個條目,或 244 字節。避免這樣一個大頁表的顯而易見的方法是,將外部頁表再進一步細分。(這種方法也可用于 32 位處理器,以增加靈活性和有效性。)

外部頁表的劃分有很多方法。例如,我們可以對外部頁表再分頁,進而得到三層分頁方案。假設外部頁表由標準大小的頁組成(210 個條目或者 212 字節)。這時,64 位地址空間仍然很大:


外部頁表的大小仍然為 234 字節(16GB)。

下一步是四層分頁方案,這里第二級的外部頁表本身也被分頁,等等。為了轉換每個邏輯地址,64 位的 UltraSPARC 將需要 7 個級別的分頁,如此多的內存訪問是不可取的。從這個例子可以看出,對于 64 位的架構,為什么分層頁表通常被認為是不適當的。

哈希頁表

處理大于 32 位地址空間的常用方法是使用哈希頁表,采用虛擬頁碼作為哈希值。哈希頁表的每一個條目都包括一個鏈表,該鏈表的元素哈希到同一位置(該鏈表用來解決處理碰撞)。每個元素由三個字段組成:虛擬頁碼映射的幀碼指向鏈表內下一個元素的指針

該算法工作如下,虛擬地址的虛擬頁碼哈希到哈希表,用虛擬頁碼與鏈表內的第一個元素的第一個字段相比較,如果匹配,那么相應的幀碼(第二個字段)就用來形成物理地址;反之,如果不匹配,那么與鏈表內的后續節點的第一個字段進行比較,以查找匹配的頁碼。

該方案如圖 3 所示。

哈希頁表
圖 3 哈希頁表

已提出用于 64 位地址空間的這個方案的一個變體。此變體采用聚簇頁表,類似于哈希頁表;不過,哈希表內的每個條目引用多個頁(例如 16)不是單個頁。因此,單個頁表條目可以映射到多個物理幀。聚簇頁表對于稀疏地址空間特別有用,這里的引用是不連續的并且散布在整個地址空間中。

倒置頁表

通常,每個進程都有一個關聯的頁表。該進程所使用的每個頁都在頁表中有一項(或者每個虛擬頁都有一項,不管后者是否有效)。這種表示方式比較自然,因為進程是通過虛擬地址來引用頁的。操作系統應將這種引用轉換成物理內存的地址。

由于頁表是按虛擬地址排序的,操作系統可計算出所對應條目在頁表中的位置,可以直接使用該值。這種方法的缺點之一是,每個頁表可能包含數以百萬計的條目。這些表可能需要大量的物理內存,以跟蹤其他物理內存是如何使用的。

為了解決這個問題,我們可以使用倒置頁表。對于每個真正的內存頁或幀,倒置頁表才有一個條目。每個條目包含保存在真正內存位置上的頁的虛擬地址,以及擁有該頁進程的信息。因此,整個系統只有一個頁表,并且每個物理內存的頁只有一條相應的條目。

倒置頁表
圖 4 倒置頁表

圖 4 顯示了倒置頁表的工作原理,由于一個倒置頁表通常包含多個不同的映射物理內存的地址空間,通常要求它的每個條目保存一個地址空間標識符。地址空間標識符的保存確保了,具體進程的每個邏輯頁可映射到相應的物理幀。采用倒置頁表的系統包括 64 位 UltraSPARC 和 PowerPC。

為了說明這種方法,這里描述一種用于 IBM RT 的倒置頁表的簡化版本。IBM 是最早采用倒置頁表的大公司:從 IBM System 38、RS/6000,到現代的 IBM Power CPU。

對 IBM RT,系統內的每個虛擬地址為一個三元組:

〈進程id,頁碼,偏移〉

每個倒置頁表條目為二元組〈進程 id,頁碼〉,這里進程 id 用來作為地址空間的標識符。當發生內存引用時,由〈進程 id,頁碼〉組成的虛擬地址被提交到內存子系統。然后,搜索倒置頁表來尋找匹配。如果找到匹配條目,如條目 i,則生成物理地址〈i,偏移〉。如果找不到匹配,則為非法地址訪問。

雖然這種方案減少了存儲每個頁表所需的內存空間,但是它增加了由于引用頁而查找頁表所需的時間。由于倒置頁表是按物理地址來排序的,而查找是根據虛擬地址的,因此查找匹配可能需要搜索整個表。這種搜索需要很長時間。

為了解決這個問題,可以使用一個哈希表,以將搜索限制在一個或最多數個頁表條目。當然,每次訪問哈希表也增加了一次內存引用,因此每次虛擬地址的引用至少需要兩個內存讀:一個用于哈希表條目,另一個用于頁表。(記住:在搜索哈希表之前,先搜索 TLB,這可改善性能。)

采用倒置頁表的系統在實現共享內存時會有困難。共享內存的通常實現為,將多個虛擬地址(共享內存的每個進程都有一個虛擬地址)映射到一個物理地址。這種標準的方法不能用于倒置頁表,因為每個物理頁只有一個虛擬頁條目,一個物理頁不可能有兩個(或多個)共享的虛擬地址。

解決這個問題的一個簡單技術是,只允許頁表包含一個虛擬地址到共享物理地址的映射。這意味著,對未映射的虛擬地址的引用會導致頁錯誤。

Oracle SPARC Solaris

以一個現代的 64 位 CPU 和與其緊密集成并提供低開銷虛擬內存的操作系統為例,來進行分析。Solaris 運行于 SPARC 處理器上,是一個真正 64 位的操作系統;它需要通過多級頁表來提供虛擬內存且不會用完所有物理內存。它的做法有點復雜,但通過哈希表有效地解決了問題。

它有兩個哈希表:一個用于內核,一個用于所有用戶進程。每個將虛擬內存的內存地址映射到物理內存。每個哈希表條目代表一個已映射的、連續的、虛擬內存區域;比每個條目僅代表一頁,更為有效。每個條目都有一個基地址和一個表示頁數多少的跨度。

如果每個地址都要搜索哈希表,那么虛擬到物理的轉換時間會太長;因此 CPU 有一個 TLB,它用于保存轉換表條目(TTE),以便進行快速硬件查找。這些 TTE 緩存駐留在一個轉換存儲緩沖區(TSB),其中包括最近訪問頁的有關條目。當引用一個虛擬地址時,硬件搜索 TLB 以進行轉換。如果沒有找到,硬件搜索內存中的 TSB,以查找對應于導致查找虛擬地址的 TTE。

這種 TLB 查找功能常見于現代 CPU。如果 TSB 中找到了匹配,CPU 將 TSB 條目復制到 TLB,進而完成內存轉換。如果 TSB 中未找到匹配,則中斷內核,以搜索哈希表。然后,內核從相應的哈希表中創建一個 TTE,并保存到 TSB 中;而 CPU 內存管理單元會通過 TSB 自動加載 TLB。最后,中斷處理程序將控制返回到 MMU,完成地址轉換,獲得內存中的字節或字。

所有教程

優秀文章

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo