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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、時，將其寄存器的Rn-1位置為1，隨后每隔一定時周期（如100m s）右移一位。如果置換頁面時，若某頁面的移位寄存器的值最小，則即為最近最久的頁面。,下圖為一進程具有8個頁面時的LRU訪問情況，當前最近最久未使用頁面為哪一頁 ？（3）,2）棧：用一特殊棧保存當前進程內存中的所有頁號，在運行過程中每當訪問哪一頁面，則從棧中移出并壓入棧頂。從而，當置換頁面時，則棧底頁號對應頁面為LRU算法選擇頁面。,舉例：某進程運行過程中訪問的頁面序列和使用棧實現(xiàn)的LRU置換算法如下圖（進程分配5個物理塊）。,OPT、LRU和FIFO置換算法舉例比較分析：某進程在內存中分配三個頁面，初始為空，頁面訪問序列為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%,補充作業(yè)：在上例中，如果分配4個內存頁面(塊)時，計算三種算法的缺頁次數(shù)和缺頁率，并判斷有無Belady現(xiàn)象發(fā)生？,4.7.3 Clock置換算法（LRU近似算法）,要完全實現(xiàn)LRU算法是一件十分困難的事情。因為要找出最近最久未被使用的頁面的話，就必須對每一個頁面都設置有關的訪問記錄項，而且每一次訪問都必須更新這些記錄。這要花費巨大的系統(tǒng)開銷（硬件開銷和時間開銷）。因此，在實際系統(tǒng)中

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

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

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

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

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

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