操作系統(tǒng)頁(yè)式存儲(chǔ)管理

1、6.4 頁(yè)式存儲(chǔ)管理6.4.1 基本原理6.4.2 管理6.4.3 硬件支持6.4.4 靜態(tài)頁(yè)式管理6.4.5 請(qǐng)求頁(yè)式管理6.4.6 頁(yè)式管理的優(yōu)缺點(diǎn)6.4.1 基本思想（工作原理）用戶程序劃分 把用戶程序按邏輯頁(yè)劃分成大小相等的部分，稱為頁(yè)。從0開始編制頁(yè)號(hào)，頁(yè)內(nèi)地址是相對(duì)于0編址邏輯地址頁(yè)號(hào)頁(yè)號(hào) 頁(yè)內(nèi)地址頁(yè)內(nèi)地址 內(nèi)存空間 按頁(yè)的大小劃分為大小相等的區(qū)域，稱為內(nèi)存塊（物理頁(yè)面） 內(nèi)存分配 以頁(yè)為單位進(jìn)行分配，并按作業(yè)的頁(yè)數(shù)多少來(lái)分配。邏輯上相鄰的頁(yè)，物理上不一定相鄰.01234560123456作業(yè)的作業(yè)的地址空間地址空間頁(yè)框頁(yè)框（物理塊）（物理塊）頁(yè)號(hào)頁(yè)號(hào)頁(yè)表頁(yè)表主存中頁(yè)框主存中頁(yè)框（

2、物理塊）（物理塊）.6.4.2 管理 頁(yè)表：系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)頁(yè)表，頁(yè)表給出邏輯頁(yè)號(hào)和具體內(nèi)存塊號(hào)相應(yīng)的關(guān)系。頁(yè)號(hào)頁(yè)面號(hào)0213286.4.3 硬件支持p頁(yè)表頁(yè)表地址越界地址越界 l比較P=l b+頁(yè)號(hào)p 頁(yè)內(nèi)地址dPd物理地址物理地址頁(yè)表地址寄存器頁(yè)表地址寄存器頁(yè)表長(zhǎng)度寄存器頁(yè)表長(zhǎng)度寄存器邏輯地址邏輯地址地址映射機(jī)制二次訪問(wèn)內(nèi)存第一次取地址第二次存取數(shù)據(jù)效率較低p頁(yè)表頁(yè)表地址越界地址越界 l比較P=lpp. . .快表快表 b+頁(yè)號(hào)p 頁(yè)內(nèi)地址dPd物理地址物理地址頁(yè)表地址寄存器頁(yè)表地址寄存器頁(yè)表長(zhǎng)度寄存器頁(yè)表長(zhǎng)度寄存器邏輯地址邏輯地址地址映射機(jī)制高速緩存6.4.4 靜態(tài)頁(yè)式管理 將程序

3、的邏輯地址空間和物理內(nèi)存劃分為固定大小的頁(yè)或頁(yè)面(page or page frame)，程序加載時(shí)，分配其所需的所有頁(yè)，這些頁(yè)不必連續(xù)。FrameNumber0123456789101112131401234567891011121314A.0A.1A.2A.301234567891011121314 A.0 A.1 A.2 A.3B.0B.1B.201234567891011121314 A.0 A.1 A.2 A.3B.0B.1B.2 C.0 C.1 C.2 C.301234567891011121314A.0A.1A.2A.3C.0C.1C.2C.3012345678910111213

4、14 A.0 A.1 A.2 A.3 C.0 C.1 C.2 C.3D.0D.1D.2D.3D.41. 簡(jiǎn)單頁(yè)式管理的數(shù)據(jù)結(jié)構(gòu) 頁(yè)表：每個(gè)進(jìn)程有一個(gè)頁(yè)表，描述該進(jìn)程占用的物理頁(yè)面及邏輯排列順序； 邏輯頁(yè)號(hào)（本進(jìn)程的地址空間）物理頁(yè)面號(hào)（實(shí)際內(nèi)存空間）； 存儲(chǔ)頁(yè)面表：整個(gè)系統(tǒng)有一個(gè)存儲(chǔ)頁(yè)面表，描述物理內(nèi)存空間的分配使用狀況。 數(shù)據(jù)結(jié)構(gòu)：位示圖，空閑頁(yè)面鏈表； 請(qǐng)求表：整個(gè)系統(tǒng)有一個(gè)請(qǐng)求表，描述系統(tǒng)內(nèi)各個(gè)進(jìn)程頁(yè)表的位置和大小，用于地址轉(zhuǎn)換，也可以結(jié)合到各進(jìn)程的PCB里；2. 分配算法請(qǐng)求n個(gè)頁(yè)面存儲(chǔ)頁(yè)面表中有n個(gè)空閑頁(yè)面嗎無(wú)法分配返回設(shè)置請(qǐng)求表，將頁(yè)表始址，頁(yè)表長(zhǎng)度置入請(qǐng)求表中，置狀態(tài)已分配搜索存

5、儲(chǔ)頁(yè)面表，分配n個(gè)頁(yè)面，并將頁(yè)面號(hào)填入頁(yè)表中3. 簡(jiǎn)單頁(yè)式管理的地址變換 指令所給出地址分為兩部分：邏輯頁(yè)號(hào)，頁(yè)內(nèi)偏移地址查進(jìn)程頁(yè)表，得物理頁(yè)號(hào)物理地址 為縮短查找時(shí)間，引入快表，按內(nèi)容查找(associative mapping)，即邏輯頁(yè)號(hào)物理頁(yè)號(hào)ProgramPagingMain MemoryVirtual AddressRegisterPage TablePageFrameOffsetP#Frame #Page Table PtrPage #OffsetFrame #Offset+頁(yè)號(hào)頁(yè)面號(hào)021328 設(shè)每個(gè)頁(yè)面長(zhǎng)度為1k，指令LOAD 1,2500 的虛地址為100，依據(jù)左圖進(jìn)行地

6、址變換。 首先，需要有一個(gè)頁(yè)表地址寄存器和頁(yè)表長(zhǎng)度寄存器。系統(tǒng)把所調(diào)度執(zhí)行的進(jìn)程頁(yè)表始址和長(zhǎng)度從請(qǐng)求表中取出置入寄存器 然后，找到頁(yè)表。由虛地址100可知，指令在第0頁(yè)的第100單元中，對(duì)應(yīng)內(nèi)存地址為1024*2+100=2148 當(dāng)CPU執(zhí)行到第2148單元時(shí)，需要從虛地址2500中取數(shù)據(jù)，地址變換機(jī)構(gòu)首先將2500的頁(yè)號(hào)和頁(yè)內(nèi)位移求出：2；452 由頁(yè)表可知，對(duì)應(yīng)內(nèi)存8號(hào)，內(nèi)存地址為1024*8+452=8644 以上由硬件地址變換機(jī)構(gòu)自動(dòng)完成。 優(yōu)點(diǎn)： 沒有外碎片，每個(gè)內(nèi)碎片不超過(guò)頁(yè)大小。 一個(gè)程序不必連續(xù)存放。 便于改變程序占用空間的大小。即隨著程序運(yùn)行而動(dòng)態(tài)生成的數(shù)據(jù)增多，地址空間可

7、相應(yīng)增長(zhǎng)。 缺點(diǎn)：程序全部裝入內(nèi)存，受到內(nèi)存可用頁(yè)面數(shù)的限制。6.4.5 動(dòng)態(tài)（請(qǐng)求）頁(yè)式管理 在進(jìn)程開始運(yùn)行之前，不是裝入全部頁(yè)面，而是裝入部分頁(yè)面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁(yè)面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁(yè)面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁(yè)面，以便裝入新的頁(yè)面。 請(qǐng)求頁(yè)式的地址變換與靜態(tài)頁(yè)式的相同。 但是，由于只讓部分頁(yè)面駐留內(nèi)存，如何發(fā)現(xiàn)那些不在內(nèi)存的虛頁(yè)以及如何處理是請(qǐng)求頁(yè)式必須處理的問(wèn)題。 第一個(gè)問(wèn)題可以通過(guò)擴(kuò)充頁(yè)表的方法解決；第二個(gè)問(wèn)題當(dāng)內(nèi)存沒有空閑頁(yè)面時(shí)即是頁(yè)面置換算法的問(wèn)題。 頁(yè)表表項(xiàng) 頁(yè)號(hào)、駐留位、內(nèi)存塊號(hào)、外存始址、訪問(wèn)位、修改位 駐留位（中斷位）：表示該頁(yè)是

8、在內(nèi)存還是在外存 訪問(wèn)位：根據(jù)訪問(wèn)位來(lái)決定淘汰哪頁(yè)（由不同的算法決定） 修改位：查看此頁(yè)是否在內(nèi)存中被修改過(guò)頁(yè)號(hào)頁(yè)號(hào)中斷位中斷位 內(nèi)存塊號(hào)內(nèi)存塊號(hào)外存始址外存始址訪問(wèn)位訪問(wèn)位 修改位修改位 缺頁(yè)中斷處理在地址映射過(guò)程中，在頁(yè)表中發(fā)現(xiàn)所要訪問(wèn)的頁(yè)不在內(nèi)存，則產(chǎn)生缺頁(yè)中斷。操作系統(tǒng)接到此中斷信號(hào)后，就調(diào)出缺頁(yè)中斷處理程序，根據(jù)頁(yè)表中給出的外存地址，將該頁(yè)調(diào)入內(nèi)存，使作業(yè)繼續(xù)運(yùn)行下去如果內(nèi)存中有空閑塊，則分配一頁(yè)，將新調(diào)入頁(yè)裝入內(nèi)存，并修改頁(yè)表中相應(yīng)表項(xiàng)若此時(shí)內(nèi)存中沒有空閑塊，則要淘汰某頁(yè)，若該頁(yè)在內(nèi)存期間被修改過(guò)，則要將其寫回外存查快表有登記無(wú)登記查頁(yè)表登記入快表發(fā)缺頁(yè)中斷在主存在輔存形成絕對(duì)地址

9、繼續(xù)執(zhí)行指令重新執(zhí)行被中斷指令恢復(fù)現(xiàn)場(chǎng)調(diào)整頁(yè)表和主存分配表裝入所需頁(yè)面主存有空閑塊保護(hù)現(xiàn)場(chǎng)有選擇調(diào)出頁(yè)面未修改已修改把該頁(yè)寫回輔存相應(yīng)位置硬件完成邏輯地址無(wú)該頁(yè)修改過(guò)？ 頁(yè)面置換算法 隨機(jī)置換算法 先進(jìn)先出算法(FIFO) 最近最久未使用算法(LRU, Least Recently Used) 時(shí)鐘頁(yè)面替換算法(Clock Policy) 最佳置換算法(OPT, optimal)1. 先進(jìn)先出算法(FIFO) 選擇建立最早的頁(yè)面被置換?？梢酝ㄟ^(guò)鏈表來(lái)表示各頁(yè)的建立時(shí)間先后。性能較差。較早調(diào)入的頁(yè)往往是經(jīng)常被訪問(wèn)的頁(yè)，這些頁(yè)在FIFO算法下被反復(fù)調(diào)入和調(diào)出。并且有Belady現(xiàn)象。 Belady

10、現(xiàn)象：采用FIFO算法時(shí)，如果對(duì)一個(gè)進(jìn)程未分配它所要求的全部頁(yè)面，有時(shí)就會(huì)出現(xiàn)分配的頁(yè)面數(shù)增多，缺頁(yè)率反而提高的異常現(xiàn)象。 Belady現(xiàn)象的描述：一個(gè)進(jìn)程P要訪問(wèn)M個(gè)頁(yè)，OS分配N個(gè)內(nèi)存頁(yè)面給進(jìn)程P；對(duì)一個(gè)訪問(wèn)序列S，發(fā)生缺頁(yè)次數(shù)為PE（S,N）。當(dāng)N增大時(shí)，PE(S, N)時(shí)而增大，時(shí)而減小。 Belady現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪問(wèn)內(nèi)存的動(dòng)態(tài)特征是矛盾的，即被置換的頁(yè)面并不是進(jìn)程不會(huì)訪問(wèn)的。Belady現(xiàn)象的例子進(jìn)程P有5頁(yè)程序訪問(wèn)頁(yè)的順序?yàn)椋?, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5；如果在內(nèi)存中分配3個(gè)頁(yè)面，則缺頁(yè)情況如下：12次訪問(wèn)中有缺頁(yè)

11、9次；123412512345111444555555222111113333332222244如果在內(nèi)存中分配4個(gè)頁(yè)面，則缺頁(yè)情況如下：12次訪問(wèn)中有缺頁(yè)10次；1234125123451111115555442222221111533333322224444443332.最近最久未使用算法(LRU) 該算法淘汰的頁(yè)面是在最近一段時(shí)間里較久未被訪問(wèn)的那一頁(yè)。它是根據(jù)程序執(zhí)行時(shí)所具有的局部性來(lái)考慮的，即那些剛被使用過(guò)的頁(yè)面，可能馬上還要被使用，而那些在較長(zhǎng)時(shí)間里未被使用的頁(yè)面，一般說(shuō)可能不會(huì)馬上使用到。 給某作業(yè)分配了三塊主存，該作業(yè)依次訪問(wèn)的頁(yè)號(hào)為：4，3，0，4，1，1，2，3，2。于是當(dāng)

12、訪問(wèn)這些頁(yè)時(shí)，頁(yè)面淘汰序列的變化情況如下： 4304112324444444333331111100002224304112324304112324304412343004113.時(shí)鐘頁(yè)面替換算法(Clock Policy) 一個(gè)頁(yè)面首次裝入主存時(shí)，其”引用位”置0。 在主存中的任何一個(gè)頁(yè)面被訪問(wèn)時(shí), 其”引用位”置1。 淘汰頁(yè)面時(shí),存儲(chǔ)管理從指針當(dāng)前指向的頁(yè)面開始掃描循環(huán)隊(duì)列，把所遷到的”引用位”是1的頁(yè)面的”引用位”清成0,并跳過(guò)這個(gè)頁(yè)面; 把所遷到的”引用位”是0的頁(yè)面淘汰掉,指針推進(jìn)一步。 它是LRU(最近最久未使用算法)和FIFO的折衷。P a g e 9 use=1Page19Us

13、e=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page33Use=1Page222Use=0下一個(gè)幀指針n012345678（a）一個(gè)頁(yè)替換前的緩沖區(qū)狀態(tài)P a g e 9 use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=0Page727Use=1Page13Use=0Page67Use=1Page33Use=1Page222Use=0n012345678（b）下一頁(yè)替換后的緩沖區(qū)狀態(tài)1第1頁(yè)框當(dāng)發(fā)生缺頁(yè)中斷時(shí)，將要進(jìn)入主存的頁(yè)面是page727,指針指

14、向的是page45(在頁(yè)框2中)。Clock頁(yè)面替換算法執(zhí)行如下：page45的”引用位”是1,故它不能被淘汰掉，僅把其”引用位”清0,指針推進(jìn)。同樣道理，page191(在頁(yè)框3中)也不能被替換, 把其”引用位”清0,指針繼續(xù)推進(jìn)。在下一頁(yè)即page556(在頁(yè)框4中),它的”引用位”是0,于是,page556被page727替換,并把page727的”引用位”置1,指針前進(jìn)到下一頁(yè)page13(在頁(yè)框5中)。算法執(zhí)行到此結(jié)束。4. 最佳算法(OPT, optimal)選擇“未來(lái)不再使用的”或“在離當(dāng)前最遠(yuǎn)位置上出現(xiàn)的”頁(yè)面被置換。這是一種理想情況，是實(shí)際執(zhí)行中無(wú)法預(yù)知的，因而不能實(shí)現(xiàn)?？捎?/p>

15、作性能評(píng)價(jià)的依據(jù)。430411232444411222333333330000000(1) 分配給進(jìn)程的物理頁(yè)面數(shù)(2) 頁(yè)面本身的大小(3) 程序的編制方法(4) 頁(yè)面淘汰算法 影響缺頁(yè)次數(shù)的因素例子3：內(nèi)存分配一頁(yè),初始時(shí)第一頁(yè)在內(nèi)存；頁(yè)面大小為128個(gè)整數(shù)；矩陣A128X128按行存放程序編制方法1： For j:=1 to 128 For i:=1 to 128 Ai,j:=0;程序編制方法2： For i:=1 to 128 For j:=1 to 128 Ai,j:=0;6.4.6 頁(yè)式管理的優(yōu)缺點(diǎn) 相對(duì)于分區(qū)管理而言，靜態(tài)頁(yè)式有效的解決了外部碎片的問(wèn)題（當(dāng)然有少量的內(nèi)部碎片）；

16、但是，靜態(tài)頁(yè)式要求全部裝入，不支持虛擬存儲(chǔ)，因而有了請(qǐng)求頁(yè)式，允許部分裝入； 顯然地，請(qǐng)求頁(yè)式更能有效利用有限的內(nèi)存頁(yè)面，不過(guò)，這種方式需要有效解決缺頁(yè)率的問(wèn)題，尤其是頁(yè)面置換的問(wèn)題； 不論是靜態(tài)還是請(qǐng)求方式，更多地是從物理頁(yè)面的角度考慮和解決問(wèn)題，有的時(shí)候，需要從邏輯角度考慮問(wèn)題，比如共享，這就引入了段式管理方法。 習(xí)題：某程序在內(nèi)存中分配三個(gè)頁(yè)面，初始為空，頁(yè)面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5，計(jì)算采用FIFO , LRU , OPT進(jìn)行頁(yè)面置換時(shí)相應(yīng)的缺頁(yè)次數(shù)。432143543215444111555555333444442222223333311 FIFO：缺頁(yè)9