操作系統(tǒng)頁式存儲管理

6.4頁式存儲管理

6.4.1基本原理6.4.2管理6.4.3硬件支持6.4.4靜態(tài)頁式管理6.4.5請求頁式管理6.4.6頁式管理的優(yōu)缺點(diǎn)2021/6/2716.4.1基本思想（工作原理）用戶程序劃分

把用戶程序按邏輯頁劃分成大小相等的部分，稱為頁。從0開始編制頁號，頁內(nèi)地址是相對于0編址邏輯地址頁號頁內(nèi)地址2021/6/272內(nèi)存空間按頁的大小劃分為大小相等的區(qū)域，稱為內(nèi)存塊（物理頁面）內(nèi)存分配以頁為單位進(jìn)行分配，并按作業(yè)的頁數(shù)多少來分配。邏輯上相鄰的頁，物理上不一定相鄰2021/6/2732021/6/2746.4.2管理頁表：系統(tǒng)為每個進(jìn)程建立一個頁表，頁表給出邏輯頁號和具體內(nèi)存塊號相應(yīng)的關(guān)系。頁號頁面號0213282021/6/2756.4.3硬件支持p’頁表地址越界

l比較P>=l

b+頁號p頁內(nèi)地址dP’d物理地址頁表地址寄存器頁表長度寄存器邏輯地址地址映射機(jī)制二次訪問內(nèi)存第一次取地址第二次存取數(shù)據(jù)效率較低2021/6/276p’頁表地址越界

l比較P>=lpp’...快表

b+頁號p頁內(nèi)地址dP’d物理地址頁表地址寄存器頁表長度寄存器邏輯地址地址映射機(jī)制高速緩存2021/6/2776.4.4靜態(tài)頁式管理將程序的邏輯地址空間和物理內(nèi)存劃分為固定大小的頁或頁面(pageorpageframe)，程序加載時，分配其所需的所有頁，這些頁不必連續(xù)。2021/6/2782021/6/2792021/6/27101.簡單頁式管理的數(shù)據(jù)結(jié)構(gòu)頁表：每個進(jìn)程有一個頁表，描述該進(jìn)程占用的物理頁面及邏輯排列順序；邏輯頁號（本進(jìn)程的地址空間）－>物理頁面號（實(shí)際內(nèi)存空間）；存儲頁面表：整個系統(tǒng)有一個存儲頁面表，描述物理內(nèi)存空間的分配使用狀況。數(shù)據(jù)結(jié)構(gòu)：位示圖，空閑頁面鏈表；請求表：整個系統(tǒng)有一個請求表，描述系統(tǒng)內(nèi)各個進(jìn)程頁表的位置和大小，用于地址轉(zhuǎn)換，也可以結(jié)合到各進(jìn)程的PCB里；2021/6/27112.分配算法請求n個頁面存儲頁面表中有n個空閑頁面嗎無法分配返回設(shè)置請求表，將頁表始址，頁表長度置入請求表中，置狀態(tài)已分配搜索存儲頁面表，分配n個頁面，并將頁面號填入頁表中2021/6/27123.簡單頁式管理的地址變換指令所給出地址分為兩部分：邏輯頁號，頁內(nèi)偏移地址－>查進(jìn)程頁表，得物理頁號－>物理地址為縮短查找時間，引入快表，按內(nèi)容查找(associativemapping)，即邏輯頁號－>物理頁號2021/6/27132021/6/2714頁號頁面號021328設(shè)每個頁面長度為1k，指令LOAD1,2500的虛地址為100，依據(jù)左圖進(jìn)行地址變換。首先，需要有一個頁表地址寄存器和頁表長度寄存器。系統(tǒng)把所調(diào)度執(zhí)行的進(jìn)程頁表始址和長度從請求表中取出置入寄存器然后，找到頁表。由虛地址100可知，指令在第0頁的第100單元中，對應(yīng)內(nèi)存地址為1024*2+100=2148當(dāng)CPU執(zhí)行到第2148單元時，需要從虛地址2500中取數(shù)據(jù)，地址變換機(jī)構(gòu)首先將2500的頁號和頁內(nèi)位移求出：2；452由頁表可知，對應(yīng)內(nèi)存8號，內(nèi)存地址為1024*8+452=8644以上由硬件地址變換機(jī)構(gòu)自動完成。2021/6/2715優(yōu)點(diǎn)：沒有外碎片，每個內(nèi)碎片不超過頁大小。一個程序不必連續(xù)存放。便于改變程序占用空間的大小。即隨著程序運(yùn)行而動態(tài)生成的數(shù)據(jù)增多，地址空間可相應(yīng)增長。缺點(diǎn)：程序全部裝入內(nèi)存，受到內(nèi)存可用頁面數(shù)的限制。2021/6/27166.4.5動態(tài)（請求）頁式管理在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝入部分頁面，之后根據(jù)進(jìn)程運(yùn)行的需要，動態(tài)裝入其它頁面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面。2021/6/2717請求頁式的地址變換與靜態(tài)頁式的相同。但是，由于只讓部分頁面駐留內(nèi)存，如何發(fā)現(xiàn)那些不在內(nèi)存的虛頁以及如何處理是請求頁式必須處理的問題。第一個問題可以通過擴(kuò)充頁表的方法解決；第二個問題當(dāng)內(nèi)存沒有空閑頁面時即是頁面置換算法的問題。2021/6/2718※

頁表表項頁號、駐留位、內(nèi)存塊號、外存始址、訪問位、修改位 駐留位（中斷位）：表示該頁是在內(nèi)存還是在外存訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決定）修改位：查看此頁是否在內(nèi)存中被修改過頁號中斷位內(nèi)存塊號外存始址訪問位修改位2021/6/2719※缺頁中斷處理在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，將該頁調(diào)入內(nèi)存，使作業(yè)繼續(xù)運(yùn)行下去如果內(nèi)存中有空閑塊，則分配一頁，將新調(diào)入頁裝入內(nèi)存，并修改頁表中相應(yīng)表項若此時內(nèi)存中沒有空閑塊，則要淘汰某頁，若該頁在內(nèi)存期間被修改過，則要將其寫回外存2021/6/2720查快表有登記無登記查頁表登記入快表發(fā)缺頁中斷在主存在輔存形成絕對地址繼續(xù)執(zhí)行指令重新執(zhí)行被中斷指令恢復(fù)現(xiàn)場調(diào)整頁表和主存分配表裝入所需頁面主存有空閑塊保護(hù)現(xiàn)場有選擇調(diào)出頁面未修改已修改把該頁寫回輔存相應(yīng)位置硬件完成邏輯地址無該頁修改過？2021/6/2721※

頁面置換算法隨機(jī)置換算法

先進(jìn)先出算法(FIFO)最近最久未使用算法(LRU,LeastRecentlyUsed)時鐘頁面替換算法(ClockPolicy)最佳置換算法(OPT,optimal)2021/6/27221.先進(jìn)先出算法(FIFO)

選擇建立最早的頁面被置換?？梢酝ㄟ^鏈表來表示各頁的建立時間先后。性能較差。較早調(diào)入的頁往往是經(jīng)常被訪問的頁，這些頁在FIFO算法下被反復(fù)調(diào)入和調(diào)出。并且有Belady現(xiàn)象。2021/6/2723Belady現(xiàn)象：采用FIFO算法時，如果對一個進(jìn)程未分配它所要求的全部頁面，有時就會出現(xiàn)分配的頁面數(shù)增多，缺頁率反而提高的異?，F(xiàn)象。Belady現(xiàn)象的描述：一個進(jìn)程P要訪問M個頁，OS分配N個內(nèi)存頁面給進(jìn)程P；對一個訪問序列S，發(fā)生缺頁次數(shù)為PE（S,N）。當(dāng)N增大時，PE(S,N)時而增大，時而減小。Belady現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動態(tài)特征是矛盾的，即被置換的頁面并不是進(jìn)程不會訪問的。2021/6/2724Belady現(xiàn)象的例子進(jìn)程P有5頁程序訪問頁的順序?yàn)椋?,2,3,4,1,2,5,1,2,3,4,5；如果在內(nèi)存中分配3個頁面，則缺頁情況如下：12次訪問中有缺頁9次；123412512345111444555555222111113333332222244×××××××√√××√2021/6/2725如果在內(nèi)存中分配4個頁面，則缺頁情況如下：12次訪問中有缺頁10次；123412512345111111555544222222111153333332222444444333××××√√××××××2021/6/27262.最近最久未使用算法(LRU)

該算法淘汰的頁面是在最近一段時間里較久未被訪問的那一頁。它是根據(jù)程序執(zhí)行時所具有的局部性來考慮的，即那些剛被使用過的頁面，可能馬上還要被使用，而那些在較長時間里未被使用的頁面，一般說可能不會馬上使用到。

2021/6/2727給某作業(yè)分配了三塊主存，該作業(yè)依次訪問的頁號為：4，3，0，4，1，1，2，3，2。于是當(dāng)訪問這些頁時，頁面淘汰序列的變化情況如下：430411232444444433333111110000222×××√×√××√430411232430411232430441234300411×××√×√××√2021/6/27283.時鐘頁面替換算法(ClockPolicy)＊一個頁面首次裝入主存時，其”引用位”置0。＊在主存中的任何一個頁面被訪問時,其”引用位”置1。＊淘汰頁面時,存儲管理從指針當(dāng)前指向的頁面開始掃描循環(huán)隊列，把所遷到的”引用位”是1的頁面的”引用位”清成0,并跳過這個頁面;把所遷到的”引用位”是0的頁面淘汰掉,指針推進(jìn)一步。＊它是LRU(最近最久未使用算法)和FIFO的折衷。2021/6/2729Page9use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page33Use=1Page222Use=0

下一個幀指針n012345678（a）一個頁替換前的緩沖區(qū)狀態(tài)Page9use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=0Page727Use=1Page13Use=0Page67Use=1Page33Use=1Page222Use=0

n012345678（b）下一頁替換后的緩沖區(qū)狀態(tài)1第1頁框當(dāng)發(fā)生缺頁中斷時，將要進(jìn)入主存的頁面是page727,指針指向的是page45(在頁框2中)。Clock頁面替換算法執(zhí)行如下：page45的”引用位”是1,故它不能被淘汰掉，僅把其”引用位”清0,指針推進(jìn)。同樣道理，page191(在頁框3中)也不能被替換,把其”引用位”清0,指針繼續(xù)推進(jìn)。在下一頁即page556(在頁框4中),它的”引用位”是0,于是,page556被page727替換,并把page727的”引用位”置1,指針前進(jìn)到下一頁page13(在頁框5中)。算法執(zhí)行到此結(jié)束。2021/6/27304.最佳算法(OPT,optimal)選擇“未來不再使用的”或“在離當(dāng)前最遠(yuǎn)位置上出現(xiàn)的”頁面被置換。這是一種理想情況，是實(shí)際執(zhí)行中無法預(yù)知的，因而不能實(shí)現(xiàn)?？捎米餍阅茉u價的依據(jù)。430411232444411222333333330000000×××√×√×√√2021/6/2731(1)分配給進(jìn)程的物理頁面數(shù)(2)頁面本身的大小(3)程序的編制方法(4)頁面淘汰算法※影響缺頁次數(shù)的因素2021/6/2732例子3：內(nèi)存分配一頁,初始時第一頁在內(nèi)存；頁面大小為128個整數(shù)；矩陣A128X128按行存放程序編制方法1：

Forj:=1to128Fori:=1to128A[i,j]:=0;程序編制方法2：

Fori:=1to128Forj:=1to128A[i,j]:=0;2021/6/27336.4.6頁式管理的優(yōu)缺點(diǎn)相對于分區(qū)管理而言，靜態(tài)頁式有效的解決了外部碎片的問題（當(dāng)然有少量的內(nèi)部碎片）；但是，靜態(tài)頁式要求全部裝入，不支持虛擬存儲，因而有了請求頁式，允許部分裝入；顯然地，請求頁式更能有效利用有限的內(nèi)存頁面，不過，這種方式需要有效解決缺頁率的問題，尤其是頁面置換的問題；不論是靜態(tài)還是請求方式，更多地是從物理頁面的角度考慮和解決問題，有的時候，需要從邏輯角度考慮問題，比如共享，這就引入了段式管理方法。2021/6/2734

習(xí)題：某程序在內(nèi)存中分配三個頁面，初始為空，頁面走向?yàn)?，3，2，1，4，3，5，4，3，2，