第4章+存儲器管理(4-6).ppt

1、學(xué)習(xí)目標(biāo),掌握請求分頁存儲管理系統(tǒng)實(shí)現(xiàn)原理和方法； 理解請求分頁存儲管理系統(tǒng)中的內(nèi)存分配策略和分配算法； 掌握主要頁面置換算法；,4.6 請求分頁存儲管理方式,請求分頁存儲管理的基本思想 請求分頁存儲管理方式是在基本分頁存儲管理方式的基礎(chǔ)上而形成的一種常用的虛擬存儲管理技術(shù)； 基本思想：在進(jìn)程開始運(yùn)行之前，僅裝入當(dāng)前要執(zhí)行的部分頁面即可運(yùn)行；在執(zhí)行過程中，可使用請求調(diào)入中斷動態(tài)裝入要訪問但又不在內(nèi)存的頁面；當(dāng)內(nèi)存空間已滿而又需要裝入新的頁面時(shí)，將根據(jù)置換功能適當(dāng)換出某個(gè)頁面，以便騰出空間而裝入新的頁面。,4.6 請求分頁存儲管理方式,請求分頁存儲管理的基本思想 為了實(shí)現(xiàn)頁式虛擬存儲器，系統(tǒng)需要

2、解決下面三個(gè)問題： 系統(tǒng)如何感知進(jìn)程當(dāng)前所需頁面不在主存（頁表機(jī)制）； 當(dāng)發(fā)現(xiàn)缺頁時(shí)，如何把所缺頁面調(diào)入主存（缺頁中斷機(jī)構(gòu)）； 在置換頁面時(shí)，根據(jù)什么策略選擇欲淘汰的頁面（置換算法）。,4.6.1 請求分頁的硬件支持,狀態(tài)位（中斷位）：標(biāo)識該頁是否在內(nèi)存（0或1）； 訪問位：標(biāo)識該頁面的近來的訪問次數(shù)或時(shí)間（換出）； 修改位：標(biāo)識此頁是否在內(nèi)存中被修改過； 外存地址：記錄該頁面在外存上的地址，即物理塊號。,1、頁表機(jī)制,程序在執(zhí)行時(shí)，首先檢查頁表，當(dāng)狀態(tài)位指示該頁不在主存時(shí)，則引起一個(gè)缺頁中斷發(fā)生，其中斷處理程序負(fù)責(zé)調(diào)入新頁面，中斷過程為： 保護(hù)現(xiàn)場（CPU環(huán)境）； 中斷處理（中斷處理程序裝入

3、頁面）； 恢復(fù)現(xiàn)場，返回?cái)帱c(diǎn)繼續(xù)執(zhí)行。,缺頁中斷機(jī)構(gòu),缺頁中斷與一般中斷的不同點(diǎn)： 一般中斷是一條指令完成后檢查是否有中斷；缺頁中斷是在指令執(zhí)行期間產(chǎn)生和處理中斷； 一條指令執(zhí)行時(shí)可能產(chǎn)生多個(gè)缺頁中斷。例如，指令copy A to B,將可能產(chǎn)生6次缺頁中斷，下頁圖示。,缺頁中斷機(jī)構(gòu),指令引發(fā)的連續(xù)中斷示意圖,3. 地址變換機(jī)構(gòu),請求分頁中的地址變換過程,請求分頁系統(tǒng)是在基本分頁系統(tǒng)的基礎(chǔ)上增加進(jìn)了缺頁中斷和置換功能而形成的。地址變換過程如右圖所示。,4.6.2 內(nèi)存分配策略和分配算法,在請求分頁虛擬存儲管理系統(tǒng)中，內(nèi)存分配要解決三個(gè)問題：最小物理塊數(shù)的確定、物理塊的分配策略和物理塊的分配算法

4、 1. 最小物理塊數(shù)的確定,最小物理塊數(shù)是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無法運(yùn)行。 進(jìn)程應(yīng)獲得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。例如：對于某些簡單的機(jī)器，若是單地址指令且采用直接尋址方式，則所需的最少物理塊數(shù)為2（一塊用于存放指令的頁面，一塊用于存放數(shù)據(jù)的頁面）；如果該機(jī)器允許間接尋址時(shí)，則至少要求有三個(gè)物理塊。等等。,2. 物理塊的分配策略,在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略：固定分配和可變分配。在進(jìn)行置換時(shí)，也可采取兩種策略：全局置換和局部置換。于是可組合出以下三種適用的策略。 固定分配局部置

5、換：分配固定數(shù)目的物理塊，運(yùn)行期間不變，若缺頁，則從該進(jìn)程內(nèi)選擇一頁置換。 可變分配全局置換：給進(jìn)程分配一定數(shù)目的物理塊，系統(tǒng)再保留一些空閑物理塊成隊(duì)，缺頁進(jìn)程從中取出分之，分完后全局選頁置換。 可變分配局部置換：分一些，保留一些，按照換入和換出頻率在追加空閑物理塊。,3. 物理塊分配算法,1）平均分配算法：將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。 例如，當(dāng)系統(tǒng)中有100個(gè)物理塊，有5個(gè)進(jìn)程在運(yùn)行時(shí)，每個(gè)進(jìn)程可分得20個(gè)物理塊。 算法缺陷：內(nèi)存資源利用率不高。沒有考慮進(jìn)程的大小，盲目分配。如有一個(gè)進(jìn)程其大小為200頁，只分配給它20個(gè)塊，這樣，它必然會有很高的缺頁率；而另一個(gè)進(jìn)程只有

6、10頁，卻有10個(gè)物理塊閑置未用。,2）按比例分配算法：根據(jù)進(jìn)程的大小按比例分配物理塊的算法。 如果系統(tǒng)中共有n個(gè)進(jìn)程，每個(gè)進(jìn)程的頁面數(shù)為Si，則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為： 若系統(tǒng)中可用的物理塊總數(shù)為m，則每個(gè)進(jìn)程所能分到的物理塊數(shù)為bi，將有： b應(yīng)該取整，它必須大于最小物理塊數(shù)。,3）考慮優(yōu)先權(quán)的分配算法：按照進(jìn)程的重要性和緊迫性為進(jìn)程分配內(nèi)存空間（物理塊數(shù)）。 具體方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)給優(yōu)先權(quán)高的進(jìn)程增加物理塊。在有的系統(tǒng)中，如重要的實(shí)時(shí)控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)來為各進(jìn)程分配其物理塊的。,4.

7、6.3 調(diào)頁策略,1. 何時(shí)調(diào)入頁面,預(yù)調(diào)頁策略： 將預(yù)測要執(zhí)行的頁面提前調(diào)入內(nèi)存，但往往效果不佳。主要用于進(jìn)程首次調(diào)入時(shí)，由程序員確定調(diào)入部分頁。 2) 請求調(diào)頁策略 ： 在執(zhí)行過程中，發(fā)現(xiàn)缺頁則產(chǎn)生缺頁中斷調(diào)入一頁，會增加磁盤I/O次數(shù),2. 從何處調(diào)入頁面,在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū)。由于對換區(qū)是采用連續(xù)分配方式，而文件是采用離散分配方式，故對換區(qū)的磁盤I/O速度比文件區(qū)的高。每當(dāng)發(fā)生缺頁請求時(shí)，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況： 1) 全部從對換區(qū)調(diào)入：系統(tǒng)擁有足夠的對換區(qū)空間，這時(shí)可以全部從對換區(qū)調(diào)入所需頁面，以提高

8、調(diào)頁速度。為此，在進(jìn)程運(yùn)行前，便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對換區(qū)。,2）未被修改頁面，從文件區(qū)調(diào)入（不用換出）；被修改的頁面，換入換出須到對換區(qū)。系統(tǒng)缺少足夠的對換區(qū)空間時(shí)，采用這種方法。 3） UNIX方式：凡未運(yùn)行過的頁面，都應(yīng)從文件區(qū)調(diào)入；而對于曾經(jīng)運(yùn)行過但又被換出的頁面，應(yīng)從對換區(qū)調(diào)入。,3. 頁面調(diào)入過程 1）每當(dāng)程序所要訪問的頁面未在內(nèi)存時(shí)，便向CPU發(fā)出一缺頁中斷； 2）中斷處理程序首先保留CPU環(huán)境，分析中斷原因后， 轉(zhuǎn)入缺頁中斷處理程序； 3）缺頁中斷處理程序通過查找頁表，得到該頁在外存的物理塊后，若內(nèi)存有空閑塊，則啟動磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。

9、否則，執(zhí)行4）； 4）如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁換出；然后再把所缺的頁調(diào)入內(nèi)存，并修改頁表中的相應(yīng)表項(xiàng)，并寫入快表。 5）在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。,作業(yè)4-4,P143 16、18、19,4.7 頁面置換算法(重點(diǎn)),解決問題：需要調(diào)入頁面時(shí)，內(nèi)存沒有空閑空間，選擇內(nèi)存中哪個(gè)物理頁面被置換（稱為replacement policy）。 置換算法：把選擇換出頁面的算法稱為頁面置換算法。 算法目標(biāo)：把未來不再訪問或較長時(shí)間內(nèi)不再訪問的頁面調(diào)出，使得頁面的更換具有較低換出換入頻率。 假定：不適一般性，按照固定分配、

10、局部置換策略討論進(jìn)程的頁面置換算法。,1. 最佳算法(OPT, optimal),基本思想：選擇“以后永不再使用的”或“在最長未來時(shí)間內(nèi)不再被訪問的”頁面被置換。 算法評價(jià)：具有最低的置換率，但這是一種理想算法，因?yàn)閷?shí)際進(jìn)程執(zhí)行中無法預(yù)知換出的頁面，因而不能實(shí)現(xiàn)。 用途：通常使用這種算法作為衡量其它算法性能的評價(jià)依據(jù)。,最佳算法舉例：假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，且進(jìn)程頁面的引用串（即頁面的訪問序列）： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 試用最佳置換算法討論該進(jìn)程的頁面置換過程。 分析：進(jìn)程運(yùn)行時(shí)，先將7，0，1三個(gè)頁面裝入內(nèi)存便投入運(yùn)行，其后

11、，當(dāng)進(jìn)程要訪問頁面2時(shí)，將會產(chǎn)生缺頁中斷，此時(shí)OS根據(jù)最佳置換算法，將選擇頁面7予以淘汰； 。整個(gè)置換過程見下頁圖示。,最佳頁面置換算法置換圖,置換頁面6次,2. 先進(jìn)先出置換算法(FIFO),基本思想：選擇進(jìn)入內(nèi)存最早的頁面被置換。 算法評價(jià)：該算法實(shí)現(xiàn)簡單，但性能較差。較早調(diào)入的頁往往是經(jīng)常被訪問的頁，這些頁在FIFO算法下被反復(fù)調(diào)入和調(diào)出，容易產(chǎn)生抖動。并且可能有Belady現(xiàn)象發(fā)生。 抖動/顛簸：剛被淘汰的頁面馬上又要訪問，因而又要把它調(diào)入，即調(diào)入和調(diào)出頻繁發(fā)生。抖動發(fā)生將嚴(yán)重降低系統(tǒng)的處理效率。 舉例：試用FIFO置換算法，討論上例進(jìn)程執(zhí)行期間的頁面置換過程。,利用FIFO置換算法時(shí)

12、的頁面置換圖,置換頁面12次,Belady現(xiàn)象及其舉例,Belady現(xiàn)象：當(dāng)一個(gè)進(jìn)程需要的頁面不能全部分配時(shí)，盡管可能差一頁，將有可能導(dǎo)致進(jìn)程執(zhí)行過程中調(diào)入和調(diào)出頻繁發(fā)生，影響系統(tǒng)效率。 舉例：假設(shè)某進(jìn)程P有5頁，且訪問頁的順序?yàn)椋?1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5；如果該進(jìn)程固定分配3個(gè)物理塊，則缺頁情況如下：12次訪問中有缺頁9次；,如果在內(nèi)存中分配4個(gè)頁面，則缺頁情況如下：12次訪問中有缺頁10次；,思考：為什么FIFO算法會出現(xiàn)Belady現(xiàn)象？,FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動態(tài)特征是矛盾的,即被置換的頁面并不是進(jìn)程不會訪問的,3. 最近最

13、久未使用算法(LRU, Least Recently Used),基本思想：選擇最近最久未使用的頁面予以淘汰。因無法預(yù)測將來，所以用“最近的過去”作為“最近的將來”的近似，即如果某頁被訪問了，則它可能馬上還要被訪問。 算法評價(jià)：這是局部性原理的合理近似，性能接近最佳算法。但需要記錄頁面的最近使用時(shí)間，硬件開銷太大。,舉例分析：對以前用例進(jìn)程進(jìn)行LRU置換算法進(jìn)行分析,置換頁面次數(shù)=9,LRU置換算法的硬件支持,1) 寄存器：為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況，須為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，可表示為：,R=Rn-1Rn-2Rn-3 R2R1R0,移位寄存器記時(shí)功能：每當(dāng)某頁面被訪問

14、時(shí)，將其寄存器的Rn-1位置為1，隨后每隔一定時(shí)周期（如100m s）右移一位。如果置換頁面時(shí)，若某頁面的移位寄存器的值最小，則即為最近最久的頁面。,下圖為一進(jìn)程具有8個(gè)頁面時(shí)的LRU訪問情況，當(dāng)前最近最久未使用頁面為哪一頁 ？（3）,2）棧：用一特殊棧保存當(dāng)前進(jìn)程內(nèi)存中的所有頁號，在運(yùn)行過程中每當(dāng)訪問哪一頁面，則從棧中移出并壓入棧頂。從而，當(dāng)置換頁面時(shí)，則棧底頁號對應(yīng)頁面為LRU算法選擇頁面。,舉例：某進(jìn)程運(yùn)行過程中訪問的頁面序列和使用棧實(shí)現(xiàn)的LRU置換算法如下圖（進(jìn)程分配5個(gè)物理塊）。,OPT、LRU和FIFO置換算法舉例比較分析：某進(jìn)程在內(nèi)存中分配三個(gè)頁面，初始為空，頁面訪問序列為4，3

15、，2，1，4，3，5，4，3，2，1，5。,缺頁中斷7次，缺頁率=7/12*100%=58.3%,缺頁中斷9次，缺頁率=9/12 * 100%=75%,缺頁中斷10次，缺頁率=10/12 * 100%=83.3%,補(bǔ)充作業(yè)：在上例中，如果分配4個(gè)內(nèi)存頁面(塊)時(shí)，計(jì)算三種算法的缺頁次數(shù)和缺頁率，并判斷有無Belady現(xiàn)象發(fā)生？,4.7.3 Clock置換算法（LRU近似算法）,要完全實(shí)現(xiàn)LRU算法是一件十分困難的事情。因?yàn)橐页鲎罱罹梦幢皇褂玫捻撁娴脑挘捅仨殞γ恳粋€(gè)頁面都設(shè)置有關(guān)的訪問記錄項(xiàng)，而且每一次訪問都必須更新這些記錄。這要花費(fèi)巨大的系統(tǒng)開銷（硬件開銷和時(shí)間開銷）。因此，在實(shí)際系統(tǒng)中

16、往往使用LRU的近似算法，包括NRU和LFU算法。,1、簡單Clock置換算法NRU算法,NRU（Not Recently Used）：最近沒有使用頁面淘汰算法 該算法只要在頁表中增設(shè)一個(gè)訪問位，并將內(nèi)存中所有頁面（物理塊）鏈接成一個(gè)循環(huán)隊(duì)列。每當(dāng)頁面被訪問時(shí)，其訪問位置為1。 當(dāng)需要置換頁面時(shí)，從當(dāng)前指針（替換指針）開始查找一訪問位為0的頁面（近期未被使用）被置換；查找過程若遇到訪問位為1的頁面，則復(fù)位為0，但暫不置換。若查找一輪后，沒有訪問位為0者，開始下一輪必有訪問位為0的頁面。,簡單的Clock置換算法流程圖,2. 改進(jìn)型Clock置換算法,算法思想：在頁面中再增加以修改字段，記錄頁面

17、在一段時(shí)間內(nèi)是否被修改過。由訪問位A和修改位M可以組合成下面四種類型的頁面： 1類(A=0, M=0): 表示最近既未被訪問，又未被修改，是最佳淘汰頁； 2類(A=0, M=1)：表示最近未被訪問，但已被修改，不是很好的淘汰頁； 3類(A=1, M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問； 4類(A=1, M=1)：最近已被訪問且被修改， 該頁可能再被訪問。,其執(zhí)行過程可分成以下三步： 從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊(duì)列，尋找A=0且M=0的第一類頁面，將所遇到的第一個(gè)頁面作為所選中的淘汰頁。 如果第一步失敗，即查找一輪后未遇到第一類頁面，則開始第二輪掃描，尋找A=0且M=1

18、的第二類頁面，將所遇到的第一個(gè)這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。 如果第二步也失敗，重復(fù)第一步，如果仍失敗，再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁。,4.7.4 其它置換算法,最少使用(LFU： Least Frequently Used)置換算法： 基本思想：該算法在需要淘汰某一頁時(shí)，首先淘汰最近一段時(shí)間被訪問次數(shù)最少的那一頁。為此，系統(tǒng)必須為每一頁增設(shè)一個(gè)訪問次數(shù)計(jì)數(shù)器。每當(dāng)該頁被訪問時(shí)，訪問計(jì)數(shù)器加1，而發(fā)生一次缺頁中斷時(shí)，則淘汰計(jì)數(shù)值最小的那一頁，并將所有的計(jì)數(shù)器清零。在實(shí)際應(yīng)用中，與LRU算法類似，為每個(gè)頁面設(shè)置一個(gè)移位寄存器，記錄頁面在一段時(shí)

19、間內(nèi)被訪問的大約次數(shù)。 2. 頁面緩沖算法(PBA： Page Buffering Algorithm) （自學(xué)）,作業(yè)4-5,習(xí)題1：假設(shè)系統(tǒng)采用固定分配局部置換策略，若某進(jìn)程在內(nèi)存中分配三個(gè)物理塊（最多調(diào)入3個(gè)頁面），且初始為空；進(jìn)程頁面的訪問序列為：4，3，2，1，4，3，5，4，3，2，1，5。 若進(jìn)程執(zhí)行分別采用OPT、LRU、FIFO、LFU置換算法調(diào)入和置換頁面，則分別繪制各置換算法在進(jìn)程執(zhí)行過程中的頁面調(diào)入置換圖表，并計(jì)算各算法的缺頁率，比較各算法的優(yōu)劣。,4.8 請求分段存儲管理方式,4.8.1 請求分段中的硬件支持,1. 段表機(jī)制,請求分段虛擬存儲器是在基本分段存儲管理方式

20、的基礎(chǔ)上，增加了請求調(diào)段和分段置換功能而形成的。即允許運(yùn)行前裝入部分分段，然后開始運(yùn)行，并在運(yùn)行過程中按需要動態(tài)調(diào)入，若調(diào)入時(shí)無內(nèi)存空間，則置換某一分段后而調(diào)入。,在段表項(xiàng)中，除了段名(號)、段長、段在內(nèi)存中的起始地址外，還增加了以下諸項(xiàng)： 存取方式：標(biāo)識本段的讀寫控制屬性； 訪問字段A：記錄本段在一段時(shí)間內(nèi)被訪問的頻率； 修改位M：記錄該段進(jìn)入內(nèi)存后是否被修改過； 存在位P：標(biāo)識本段是否調(diào)入內(nèi)存，0為未調(diào)入，1為已調(diào)入； 增補(bǔ)位：標(biāo)識本段在運(yùn)行過程中是否做過動態(tài)增長； 外存始址：記錄本段在外存的起始地址，即盤塊號。,2、缺段中斷機(jī)構(gòu) 執(zhí)行過程發(fā)現(xiàn)缺段，產(chǎn)生缺段中斷，由缺段中斷處理程序調(diào)入所缺

21、段，然后繼續(xù)執(zhí)行。無內(nèi)存空間時(shí)要置換段,圖 4-31 請求分段系統(tǒng)中的中斷處理過程,3. 地址變換機(jī)構(gòu) 在基本分段地址變換中增加了調(diào)段功能。變換過程流程如圖所示。,請求分段系統(tǒng)的地址變換過程,4.8.2 分段的共享與保護(hù),1. 共享段表：系統(tǒng)設(shè)置以共享段表，用于記錄所有共享段，且每一共享段在共享段表中都對應(yīng)一表項(xiàng)；在共享段表中也記錄了共享某段的所有進(jìn)程信息。共享段表信息如下圖所示。,圖 4-33 共享段表項(xiàng),共享段表信息解釋,共享進(jìn)程計(jì)數(shù)器count：標(biāo)識當(dāng)前有多少個(gè)進(jìn)程在共享該段，非共享段只有一個(gè)進(jìn)程數(shù)，共享段則多于一個(gè)進(jìn)程數(shù)。當(dāng)count=1釋放該段時(shí)系統(tǒng)才能回收。 存取控制字段：標(biāo)識進(jìn)程對共享段的存取權(quán)限； 段號：標(biāo)識進(jìn)程共享該段所給予該段的段號，即不同進(jìn)程可以使用不同段號。,2. 共享段的分配與回收,共享段的分配：當(dāng)?shù)谝粋€(gè)請求使用該共享段的進(jìn)程調(diào)入該段時(shí)，由系統(tǒng)為該共享段分配一物理區(qū)，再將其調(diào)入該區(qū)，同時(shí)將該區(qū)的始址填入請求進(jìn)程的段表的相應(yīng)項(xiàng)中，還須在共享段表中增加一表項(xiàng)，填寫有關(guān)數(shù)據(jù)，把count置為1；其后，當(dāng)又有其它進(jìn)程需要調(diào)用該共享