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

內存分頁機制完全攻略

分段允許進程的物理地址空間是非連續的。分頁是提供這種優勢的另一種內存管理方案。然而,分頁避免了外部碎片和緊縮,而分段不可以。

不僅如此,分頁還避免了將不同大小的內存塊匹配到交換空間的問題,在分頁引入之前采用的內存管理方案都有這個問題。由于比早期方法更加優越,各種形式的分頁為大多數操作系統采用,包括大型機的和智能手機的操作系統。實現分頁需要操作系統和計算機硬件的協作。

基本方法

實現分頁的基本方法涉及將物理內存分為固定大小的塊,稱為頁幀,而將邏輯內存也分為同樣大小的塊,稱為頁面。當需要執行一個進程時,它的頁從文件系統或備份存儲等處,加載到內存的可用幀。備份存儲劃分為固定大小的塊,它與單個內存幀或與多個內存幀(簇)的大小一樣。

這個相當簡單的方法功能強且變化多。例如,邏輯地址空間現在完全獨立于物理地址空間,因此,一個進程可以有一個 64 位的邏輯地址空間,而系統的物理內存小于 264 字節。

分頁的硬件支持
圖 1 分頁的硬件支持
 
分頁的硬件支持如圖 1 所示。由 CPU 生成的每個地址分為兩部分:頁碼和頁偏移。頁碼作為頁表的索引。頁表包含每頁所在物理內存的基地址。這個基地址與頁偏移的組合就形成了物理內存地址,可發送到物理單元。內存的分頁模型如圖 2 所示。

邏輯內存和物理內存的分頁模型
圖 2 邏輯內存和物理內存的分頁模型

頁大小(與幀大小一樣)是由硬件來決定的。頁的大小為 2 的冪;根據計算機體系結構的不同,頁大小可從 512 字節到 1GB 不等。將頁的大小選為 2 的冪可以方便地將邏輯地址轉換為頁碼和頁偏移。如果邏輯地址空間為 2m,且頁大小為 2n 字節,那么邏輯地址的高 m-n 位表示頁碼,而低 n 位表示頁偏移。這樣,邏輯地址就如下圖所示:

邏輯地址

其中 p 作為頁表的索引,而 d 作為頁的偏移。

使用4字節的頁對32字節的內存進行分頁的例子
圖 3 使用 4 字節的頁對 32 字節的內存進行分頁的例子

例如,假設如圖 3 所示的內存。這里,邏輯的地址的 n 為 2,m 為 4。采用大小為 4 字節而物理內存為 32 字節(8 頁),下面說明程序員的內存視圖如何映射到物理內存。

邏輯地址 0 的頁碼為 0,頁偏移為 0。根據頁表,可以查到頁碼 0 對應幀 5,因此邏輯地址 0 映射到物理地址 20((5X4) + 0)。邏輯地址 3(頁碼為 0,頁偏移為 3)映射到物理地址 23((5X4)+ 3)。邏輯地址 4 的頁碼為 1,頁偏移為 0,根據頁表,頁碼 1 對應為幀 6。因此,邏輯地址 4 映射到物理地址 24((6X4) + 0)。邏輯地址 13 映射到物理地址 9。

讀者可能注意到,分頁本身是一種動態的重定位。每個邏輯地址由分頁硬件綁定為某個物理地址。采用分頁類似于采用一組基址(重定位)寄存器,每個基址對應著一個內存幀。

采用分頁方案不會產生外部碎片:每個空閑幀都可以分配給需要它的進程。不過,分頁有內部碎片。注意,分配是以幀為單位進行的。如果進程所要求的內存并不是頁的整數倍,那么最后一個幀就可能用不完。

例如,如果頁的大小為 2048 字節,一個大小為 72 776 字節的進程需要 35 個頁和 1086 字節。該進程會得到 36 個幀,因此有 2048-1086 = 962 字節的內部碎片。在最壞情況下,一個需要 n 頁再加 1 字節的進程,需要分配 n + 1 個幀,這樣幾乎產生整個幀的內部碎片。

如果進程大小與頁大小無關,那么每個進程的內部碎片的均值為半頁。從這個角度來看,小的頁面大小是可取的。不過,由于頁表內的每項也有一定的開銷,該開銷隨著頁的增大而降低。再者,磁盤 I/O 操作隨著傳輸量的增大也會更為有效。

一般來說,隨著時間的推移,頁的大小也隨著進程、數據和內存的不斷增大而增大。現在,頁大小通常為 4KB?8KB,有的系統可能支持更大的頁。有的 CPU 和內核可能支持多種頁大小。例如,Solaris 根據按頁所存儲的數據,可使用 8KB 或 4MB 的大小的頁。研究人員正在研究,以便支持快速可變的頁大小。

通常,對于 32 位的 CPU,每個頁表條目是 4 字節長的,但是這個大小也可能改變。一個 32 位的條目可以指向 232 個物理幀中的任一個。如果幀為 4KB(212),那么具有 4 字節條目的系統可以訪問 244字節大小(或 16TB)的物理內存。

這里我們應該注意到,分頁內存系統的物理內存的大小不同于進程的最大邏輯大小。當進一步探索分頁時,我們將引入其他的信息,這個信息應保存在頁表條目中。該信息也減少了可用于幀地址的位數。因此,一個具有 32 位頁表條目的系統可訪問的物理內存可能小于最大值。32 位 CPU 采用 32 位地址,意味著,一個進程的空間只能為 232 字節(4GB)。因此,分頁允許我們使用的物理內存大于 CPU 地址指針可訪問的空間。

當系統進程需要執行時,它將檢查該進程的大小(按頁來計算),進程的每頁都需要一幀。因此,如果進程需要 n 頁,那么內存中至少應有 n 個幀。如果有,那么就可分配給新進程。進程的第一頁裝入一個已分配的幀,幀碼放入進程的頁表中。下一頁分配給另一幀,其幀碼也放入進程的頁表中,等等(圖 4 )。

空閑幀
圖 4 空閑幀

需要注意的是,程序員視圖的內存和實際的物理內存看似清楚地分離。程序員將內存作為一整塊來處理,而且它只包含這一個程序。事實上,一個用戶程序與其他程序一起分散在物理內存上。程序員視圖的內存和實際的物理內存的不同是通過地址轉換硬件來協調的。

邏輯地址轉變成物理地址。這種映射程序員是不知道的,它是由操作系統控制的。注意,根據定義,用戶進程不能訪問不屬于它的內存。它無法訪問它的頁表規定之外的內存,頁表只包括進程擁有的那些頁。

由于操作系統管理物理內存,它應知道物理內存的分配細節:哪些幀已分配,哪些幀空著,總共有多少幀,等等。這些信息通常保存在稱為幀表的數據結構中。在幀表中,每個條目對應著一個幀,以表示該幀是空閑還是已占用;如果占用,是被哪個(或哪些)進程的哪個頁所占用。

另外,操作系統應意識到,用戶進程是在用戶空間內執行,所有邏輯地址需要映射到物理地址。如果用戶執行一個系統調用(例如,要進行I/O),并提供地址作為參數(例如,一個緩沖),那么這個地址應映射,以形成正確的物理地址。

操作系統為每個進程維護一個頁表的副本,就如同它需要維護指令計數器和寄存器的內容一樣。每當操作系統自己將邏輯地址映射成物理地址時,這個副本可用作轉換。當一個進程可分配到 CPU 時,CPU 分派器也根據該副本來定義硬件頁表。因此,分頁增加了上下文切換的時間。

硬件支持

每個操作系統都有自己的保存頁表的方法。有的為每個進程分配一個頁表。頁表的指針,與其他寄存器的值(如指令計數器),一起存入進程控制塊。當分派器需要啟動一個進程時,它應首先加載用戶寄存器,并根據保存的用戶頁表來定義正確的硬件頁表值。其他操作系統提供一個或多個頁表,以便減少進程的上下文切換的開銷。

頁表的硬件實現有多種方法,最為簡單的一種方法是將頁表作為一組專用的寄存器來實現。由于每次訪問內存都要經過分頁映射,因此效率是一個重要的考慮因素,這些寄存器應用高速邏輯電路來構造,以高效地進行分頁地址的轉換。CPU 分派器在加載其他寄存器時,也需要加載這些寄存器。

當然,加載或修改頁表寄存器的指令是特權的,因此只有操作系統才可以修改內存映射表。具有這種結構的一個例子是 DEC PDP-11。它的地址有 16 位,而頁面大小為 8KB。因此頁表有 8 個條目,可放在快速寄存器中。

如果頁表比較小(例如 256 個條目),那么頁表使用寄存器還是令人滿意的。但是,大多數現代計算機都允許頁表非常大(例如 100 萬個條目)。對于這些機器,采用快速寄存器來實現頁表就不可行了。因而需要將頁表放在內存中,并將頁表基地址寄存器(PTBR)指向頁表。改變頁表只需要改變這一寄存器就可以,這也大大降低了上下文切換的時間。

采用這種方法的問題是訪問用戶內存位置的所需時間。如果需要訪問位置i,那么應首先利用PTBR的值,再加上i的頁碼作為偏移,來查找頁表。這一任務需要內存訪問。根據所得的幀碼,再加上頁偏移,就得到了真實物理地址。接著就可以訪問內存內的所需位置。

采用這種方案,訪問一個字節需要兩次內存訪問(一次用于頁表條目,一次用于字節),內存訪問的速度就減半。在大多數情況下,這種延遲是無法忍受的,我們還不如采用交換機制!

這個問題的標準解決方案是采用專用的、小的、查找快速的高速硬件緩沖,它稱為轉換表緩沖區(TLB)。TLB 是關聯的髙速內存。TLB 條目由兩部分組成:鍵(標簽)和值。當關聯內存根據給定值查找時,它會同時與所有的鍵進行比較。如果找到條目,那么就得到相應值的字段,搜索速度很快。

現代的 TLB 查找硬件是指令流水線的一部分,基本上不添加任何性能負擔。為了能夠在單步的流水線中執行搜索,TLB 不應大,通常它的大小在 32?1024 之間。有些 CPU 采用分開的指令和數據地址的 TLB。這可以將 TLB 條目的數量擴大一倍,因為查找可以在不同的流水線步驟中進行。

通過這個演變,我們可以看到 CPU 技術的發展趨勢:系統從沒有 TLB 發展到具有多層的 TLB,與具有多層的高速緩存一樣。

TLB 與頁表一起使用的方法如下,TLB 只包含少數的頁表條目。當 CPU 產生一個邏輯地址后,它的頁碼就發送到 TLB。如果找到這個頁碼,它的幀碼也就立即可用,可用于訪問內存。如上面所提到的,這些步驟可作為 CPU 的流水線的一部分來執行;與沒有實現分頁的系統相比,這并沒有減低性能。

如果頁碼不在 TLB 中(稱為TLB未命中),那么就需訪問頁表。取決于 CPU,這可能由硬件自動處理或通過操作系統的中斷來處理。當得到幀碼后,就可以用它來訪問內存(見圖 5)。另外,將頁碼和幀碼添加到 TLB,這樣下次再用時就可很快查找到。

帶TLB的分頁硬件
圖 5 帶 TLB 的分頁硬件

如果 TLB 內的條目已滿,那么會選擇一個來替換。替換策略有很多,從最近最少使用替換(LRU),到輪轉替換,到隨機替換等。有的 CPU 允許操作系統參與 LRU 條目的替換,其他的自己負責替換。另外,有的 TLB 允許有些條目固定下來,也就是說,它們不會從 TLB 中被替換。通常,重要內核代碼的條目是固定下來的。

有的 TLB 在每個 TLB 條目中還保存地址空間標識符(ASID)。ASID 唯一標識每個進程,并為進程提供地址空間的保護。當 TLB 試圖解析虛擬頁碼時,它確保當前運行進程的 ASID 與虛擬頁相關的 ASID 相匹配。如果不匹配,那么就作為 TLB 未命中。

除了提供地址空間保護外,ASID 也允許 TLB 同時包括多個不同進程的條目。如果 TLB 不支持單獨的 ASID,每次選擇一個頁表時(例如,上下文切換時),TLB 就應被刷新(或刪除),以確保下一個進程不會使用錯誤的地址轉換。否則,TLB 內可能有舊的條目,它們包含有效的頁碼地址,但有從上一個進程遺留下來的不正確或無效的物理地址。

在 TLB 中查找到感興趣頁碼的次數的百分比稱為命中率。80% 的命中率意味著,有 80% 的時間可以在 TLB 中找到所需的頁碼。如果需要 100ns 來訪問內存,那么當頁碼在 TLB 中時,訪問映射內存需要 100ns。如果不能在 TLB 中找到,那么應先訪問位于內存中的頁表和幀碼(100ns),并進而訪問內存中的所需字節(100ns),這總共要花費 200ns。

為了求得有效內存訪問時間,需要根據概率來進行加權:

有效訪問時間=0.80X100 + 0.20X200= 120ns

對于本例,平均內存訪問時間多了 20% (從100?120ns)。

對于 99% 的命中率,這是更現實的,我們有:

有效訪問時間=0.99X100 + 0.01X200= 101ns

這種命中率的提高只多了 1% 的訪問時間。

如前所述,現代 CPU 可能提供多級 TLB。因此,現代 CPU 的訪問時間的計算,比上面的例子更為復雜。例如,Intel Core i7 CPU 有一個 128 指令條目的 L1 TLB 和 64 數據條目的 L1 TLB。當 L1 未命中時,CPU 花費 6 個周期來檢查 L2 的 TLB 的 512 條目。L2 的未命中意味著,CPU 需要通過內存的頁表條件來查找相關的幀地址,這可能需要數百個周期,或者通過中斷操作系統以完成它的工作。

這種系統的分頁開銷的完整性能分析,需要關于每個 TLB 層次的命中率信息。然而,從這可以看到一條通用規律,硬件功能對內存性能有著顯著的影響,而操作系統的改進(如分頁)能導致硬件的改進并反過來受其影響。

TLB 是一個硬件功能,因此操作系統及其設計師似乎不必關心。但是設計師需要了解TLB的功能和特性,它們因硬件平臺的不同而不同。為了優化運行,給定平臺的操作系統設計應根據平臺的 TLB 設計來實現分頁。同樣,TLB 設計的改變(例如,在多代 Intel CPU 之間)可能需要調整操作系統的分頁實現。

保護

分頁環境下的內存保護是通過與每個幀關聯的保護位來實現的。通常,這些位保存在頁表中。

用一個位可以定義一個頁是可讀可寫或只可讀。每次內存引用都要通過頁表,來查找正確的幀碼;在計算物理地址的同時,可以通過檢查保護位來驗證有沒有對只可讀頁進行寫操作。對只讀頁進行寫操作會向操作系統產生硬件陷阱或內存保護沖突。

我們可輕松擴展這種方法,以提供更好的保護級別。我們可以創建硬件來提供只讀、讀寫或只執行保護;或者,通過為每種類型的訪問提供單獨的保護位,我們可以允許這些訪問的任何組合。非法訪問會陷入操作系統。

還有一個位通常與頁表中的每一條目相關聯:有效-無效位:
通過使用有效-無效位,非法地址會被捕捉到。操作系統通過對該位的設置,可以允許或不允許對某頁的訪問。

例如,對于 14 位地址空間(0?16383)的系統,假設有一個程序,它的有效地址空間為 0?10468。如果頁的大小為 2KB,那么頁表如圖 6 所示。

頁表的有效位(v)或無效位(i)
圖 6 頁表的有效位(v)或無效位(i)

頁 0、1、2、3、4 和 5 的地址可以通過頁表正常映射。然而,如果試圖產生頁表 6 或 7 內的地址時,則會發現有效-無效位為無效,這樣操作系統就會捕捉到這一非法操作(無效頁引用)。

注意,這種方法也產生了一個問題。由于程序的地址只到 10468,所以任何超過該地址的引用都是非法的。不過,由于對頁5的訪問是有效的,因此到 12287 為止的地址都是有效的。只有 12288?16383 的地址才是無效的。這個問題是由于頁大小為 2KB 的原因,也反映了分頁的內部碎片。

一個進程很少會使用它的所有地址空間。事實上,許多進程只用到地址空間的小部分。對這些情況,如果為地址范圍內的所有頁都在頁表中建立一個條目,這將是非常浪費的。表中的大多數并不會被使用,卻占用可用的地址空間。有的系統提供硬件,如頁表長度寄存器來表示頁表的大小,該寄存器的值可用于檢查每個邏輯地址以驗證其是否位于進程的有效范圍內。如果檢測無法通過,則會被操作系統捕捉到。

共享頁

分頁的優點之一是可以共享公共代碼。對于分時環境,這種考慮特別重要。

假設一個支持 40 個用戶的系統,每個都執行一個文本編輯器。如果該文本編輯器包括 150KB 的代碼及 50KB 的數據空間,則需要 8000KB 來支持這 40 個用戶。如果代碼是可重入代碼或純代碼,則可以共享,如圖 7 所示。這里有 3 個進程,它們共享 3 頁的編輯器,這里每頁大小為 50KB,每個進程都有它自己的數據頁。

分頁環境的代碼共享
圖 7 分頁環境的代碼共享

可重入代碼是不能自我修改的代碼:它在執行期間不會改變。因此,兩個或更多個進程可以同時執行相同代碼。每個進程都有它自己的寄存器副本和數據存儲,以便保存進程執行的數據。當然,兩個不同進程的數據不同。

在物理內存中,只需保存一個編輯器的副本。每個用戶的頁表映射到編輯器的同一物理副本,但是數據頁映射到不同的幀。因此,為支持 40 個用戶,只需一個編輯器副本(150KB),再加上 40 個用戶數據空間 50KB,總的需求空間為 2150KB 而非 8000KB,這個節省還是很大的。

其他大量使用的程序也可以共享,如編譯器、窗口系統、運行時庫、數據庫系統等。為了共享,代碼應可重入。共享代碼的只讀屬性不應由代碼的正確性來保證;而應由操作系統來強制實現。

系統內進程之間的內存共享,類似于通過線程共享同一任務的地址空間。此外,回想一下,我們將共享內存用于進程間的通信,有的操作系統通過共享頁來實現共享內存。

所有教程

優秀文章

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

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

底部Logo