第5章 虛擬存儲(chǔ)器管理

1、 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理1第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理5.1 5.1 虛擬存儲(chǔ)器概述虛擬存儲(chǔ)器概述5.2 5.2 請求分頁存儲(chǔ)管理方式請求分頁存儲(chǔ)管理方式5.3 5.3 頁面置換算法頁面置換算法 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理25.1 5.1 虛擬存儲(chǔ)器概述虛擬存儲(chǔ)器概述 一、常規(guī)存儲(chǔ)管理方式的特征和局部性原理一、常規(guī)存儲(chǔ)管理方式的特征和局部性原理 常規(guī)存儲(chǔ)器管理方式的特征常規(guī)存儲(chǔ)器管理方式的特征 我們把前一章中所介紹的各種存儲(chǔ)器管理我們把前一章中所介紹的各種存儲(chǔ)器管理方式統(tǒng)稱為傳統(tǒng)存儲(chǔ)器管理方式，它們?nèi)季叻绞?/p>

2、統(tǒng)稱為傳統(tǒng)存儲(chǔ)器管理方式，它們?nèi)季哂腥缦聝蓚€(gè)共同的特征：有如下兩個(gè)共同的特征： (1) (1) 一次性一次性(2) (2) 駐留性駐留性 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理32. 2. 局部性原理局部性原理 在一較短的時(shí)間內(nèi)，程序的執(zhí)行總是集中地訪問程序在一較短的時(shí)間內(nèi)，程序的執(zhí)行總是集中地訪問程序中的某一部分而不是均勻地對程序所有部分進(jìn)行訪問。中的某一部分而不是均勻地對程序所有部分進(jìn)行訪問。表現(xiàn)形式表現(xiàn)形式空間局部性空間局部性時(shí)間局部性時(shí)間局部性結(jié)論：結(jié)論：作業(yè)運(yùn)行時(shí)其整個(gè)虛擬空間中的信息不必全部調(diào)入作業(yè)運(yùn)行時(shí)其整個(gè)虛擬空間中的信息不必全部調(diào)入主存中，而可以只將其

3、最近要執(zhí)行的主存中，而可以只將其最近要執(zhí)行的部分裝入主存部分裝入主存，其余，其余部分到要用到時(shí)再調(diào)入主存，而這時(shí)又可以把暫時(shí)不用的部分到要用到時(shí)再調(diào)入主存，而這時(shí)又可以把暫時(shí)不用的部分調(diào)出主存，這使得虛擬存儲(chǔ)技術(shù)的實(shí)現(xiàn)成為可能。部分調(diào)出主存，這使得虛擬存儲(chǔ)技術(shù)的實(shí)現(xiàn)成為可能。 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理43. 3. 虛擬存儲(chǔ)的基本思想虛擬存儲(chǔ)的基本思想 系統(tǒng)將主、輔存系統(tǒng)將主、輔存實(shí)施統(tǒng)一管理實(shí)施統(tǒng)一管理，將程序的整，將程序的整個(gè)副本放在輔存，只將程序的一個(gè)副本放在輔存，只將程序的一部分裝入主部分裝入主存存便開始執(zhí)行，在執(zhí)行的過程中，如果要訪便開始執(zhí)行，在執(zhí)行

4、的過程中，如果要訪問的信息不在主存再通過問的信息不在主存再通過換進(jìn)換出換進(jìn)換出使程序繼使程序繼續(xù)執(zhí)行下去。續(xù)執(zhí)行下去。 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理5二、虛擬存儲(chǔ)器的定義和特征二、虛擬存儲(chǔ)器的定義和特征虛擬存儲(chǔ)器的定義虛擬存儲(chǔ)器的定義 指具有請求調(diào)入功能和置換功能，能從邏輯上對主存指具有請求調(diào)入功能和置換功能，能從邏輯上對主存容量加以擴(kuò)充的一種存儲(chǔ)系統(tǒng)。容量加以擴(kuò)充的一種存儲(chǔ)系統(tǒng)。 虛擬存儲(chǔ)器不考慮物理存儲(chǔ)器的大小和信息存放的實(shí)虛擬存儲(chǔ)器不考慮物理存儲(chǔ)器的大小和信息存放的實(shí)際位置，只規(guī)定每個(gè)進(jìn)程中互相關(guān)聯(lián)的信息的相對位置。際位置，只規(guī)定每個(gè)進(jìn)程中互相關(guān)聯(lián)的信息的

5、相對位置。2.2.虛擬存儲(chǔ)器的特征虛擬存儲(chǔ)器的特征(1) (1) 多次性多次性基礎(chǔ)：程序部分裝入基礎(chǔ)：程序部分裝入(2) (2) 對換性對換性關(guān)鍵：換進(jìn)換出關(guān)鍵：換進(jìn)換出(3) (3) 虛擬性虛擬性效果：效果：從邏輯上擴(kuò)充了主存從邏輯上擴(kuò)充了主存前提：邏輯空間與物理空間分離前提：邏輯空間與物理空間分離離散分配離散分配 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理63. 制約虛擬存儲(chǔ)器容量的條件：制約虛擬存儲(chǔ)器容量的條件： 每個(gè)程序的虛擬存儲(chǔ)器的最大容量由計(jì)算機(jī)的地址結(jié)構(gòu)每個(gè)程序的虛擬存儲(chǔ)器的最大容量由計(jì)算機(jī)的地址結(jié)構(gòu)確定，受輔助存儲(chǔ)器容量的限制。確定，受輔助存儲(chǔ)器容量的限制。5

6、. 虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的實(shí)現(xiàn)方法 請求分頁存儲(chǔ)管理請求分頁存儲(chǔ)管理 請求分段存儲(chǔ)管理請求分段存儲(chǔ)管理 請求段頁式存儲(chǔ)管理請求段頁式存儲(chǔ)管理4. 實(shí)現(xiàn)虛擬存儲(chǔ)技術(shù)需要解決的問題：實(shí)現(xiàn)虛擬存儲(chǔ)技術(shù)需要解決的問題： 程序裝入主存的時(shí)機(jī)程序裝入主存的時(shí)機(jī)請求調(diào)入、預(yù)調(diào)入請求調(diào)入、預(yù)調(diào)入 存儲(chǔ)的位置存儲(chǔ)的位置 選擇淘汰出主存的信息選擇淘汰出主存的信息置換算法置換算法 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理75.2 請求分頁存儲(chǔ)管理一、請求分頁技術(shù)基本思想一、請求分頁技術(shù)基本思想 當(dāng)一個(gè)用戶當(dāng)一個(gè)用戶( (或進(jìn)程或進(jìn)程) )的程序調(diào)入系統(tǒng)運(yùn)行時(shí)，只裝入這的程序調(diào)入系統(tǒng)運(yùn)行

7、時(shí)，只裝入這個(gè)用戶程序的一部分頁就啟動(dòng)運(yùn)行。在運(yùn)行的過程中，若發(fā)個(gè)用戶程序的一部分頁就啟動(dòng)運(yùn)行。在運(yùn)行的過程中，若發(fā)現(xiàn)要訪問的頁不在內(nèi)存，就向系統(tǒng)發(fā)出現(xiàn)要訪問的頁不在內(nèi)存，就向系統(tǒng)發(fā)出缺頁中斷請求缺頁中斷請求，系統(tǒng)，系統(tǒng)處理中斷時(shí)，把要求訪問的頁調(diào)入內(nèi)存，然后繼續(xù)運(yùn)行。處理中斷時(shí)，把要求訪問的頁調(diào)入內(nèi)存，然后繼續(xù)運(yùn)行。系統(tǒng)必須解決兩個(gè)問題：1 1、如何檢測所訪問的頁在不在主存？、如何檢測所訪問的頁在不在主存？2 2、系統(tǒng)如何處理缺頁中斷調(diào)入缺頁？、系統(tǒng)如何處理缺頁中斷調(diào)入缺頁？ 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理8頁號頁號塊號塊號狀態(tài)位狀態(tài)位P 外存始址外存始址三、缺

8、頁中斷處理過程三、缺頁中斷處理過程0 0 頁在主存頁在主存1 1 頁不在主存頁不在主存狀態(tài)位狀態(tài)位P P 對頁表進(jìn)行擴(kuò)充，擴(kuò)充后的頁表結(jié)構(gòu)為：對頁表進(jìn)行擴(kuò)充，擴(kuò)充后的頁表結(jié)構(gòu)為：二、擴(kuò)充頁表二、擴(kuò)充頁表 當(dāng)缺頁中斷發(fā)生時(shí)，中斷用戶程序的執(zhí)行，控制轉(zhuǎn)到當(dāng)缺頁中斷發(fā)生時(shí)，中斷用戶程序的執(zhí)行，控制轉(zhuǎn)到操作系統(tǒng)的調(diào)頁程序，由調(diào)頁程序把所需的頁面從輔存調(diào)操作系統(tǒng)的調(diào)頁程序，由調(diào)頁程序把所需的頁面從輔存調(diào)入主存，修改該頁表面的存在位，然后繼續(xù)執(zhí)行被中斷的入主存，修改該頁表面的存在位，然后繼續(xù)執(zhí)行被中斷的程序。程序。 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理9 邏輯地址邏輯地址 d P控

9、制寄存器控制寄存器 頁表始址頁表始址 頁表長度頁表長度 操作系統(tǒng)操作系統(tǒng) 物理地址物理地址 P d 頁頁 表表 存在位存在位塊號塊號頁號頁號 P 1+四、地址轉(zhuǎn)換過程四、地址轉(zhuǎn)換過程 通常當(dāng)作業(yè)被調(diào)入運(yùn)行時(shí)，將相應(yīng)進(jìn)程的第一頁裝入主通常當(dāng)作業(yè)被調(diào)入運(yùn)行時(shí)，將相應(yīng)進(jìn)程的第一頁裝入主存，所需的其它各頁，將按要求依次裝入。存，所需的其它各頁，將按要求依次裝入。 主存主存 P0 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理10將當(dāng)前指令中的邏輯地址分解為頁號將當(dāng)前指令中的邏輯地址分解為頁號P和頁內(nèi)地址和頁內(nèi)地址d。根據(jù)頁號根據(jù)頁號P查頁表，判斷該頁是否在主存（該頁查頁表，判斷該頁是否在

10、主存（該頁“存在位存在位”是否為是否為“0” ）若該頁若該頁“存在位存在位”為為“1”（ 該頁不在主存），則產(chǎn)生缺該頁不在主存），則產(chǎn)生缺頁中斷，否則執(zhí)行步驟頁中斷，否則執(zhí)行步驟 。 操作系統(tǒng)處理缺頁中斷，將該頁從磁盤中調(diào)入主存，并操作系統(tǒng)處理缺頁中斷，將該頁從磁盤中調(diào)入主存，并修改頁表中對應(yīng)表目的修改頁表中對應(yīng)表目的“存在位存在位”信息為信息為“0”，表示該頁已，表示該頁已在主存，然后繼續(xù)執(zhí)行被中斷的指令。在主存，然后繼續(xù)執(zhí)行被中斷的指令。將塊號將塊號P與頁內(nèi)地址與頁內(nèi)地址d 拼接為物理地址。拼接為物理地址。 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理11啟動(dòng)要處理的指令啟

11、動(dòng)要處理的指令給出虛地址給出虛地址得到頁號得到頁號該頁在主存？該頁在主存？軟件軟件硬件硬件有空閑塊？有空閑塊？調(diào)整存儲(chǔ)分塊表和頁表調(diào)整存儲(chǔ)分塊表和頁表重新啟動(dòng)被中斷的指令重新啟動(dòng)被中斷的指令調(diào)整存儲(chǔ)分塊表和頁表調(diào)整存儲(chǔ)分塊表和頁表要重寫入？要重寫入？準(zhǔn)備執(zhí)行下條指令準(zhǔn)備執(zhí)行下條指令執(zhí)行完該指令執(zhí)行完該指令Y缺頁中斷缺頁中斷N從輔存讀入所需的頁從輔存讀入所需的頁Y選一頁淘汰選一頁淘汰NN該頁寫入外存該頁寫入外存Y 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理12作業(yè)作業(yè)1地址空間地址空間0 01KB1KB2KB2KB3KB-13KB-1作業(yè)作業(yè)3地址空間地址空間0 01KB1KB

12、2KB2KB3KB-13KB-1 OS主主 存存0 01KB1KB2KB2KB3KB3KB4KB4KB5KB5KB6KB6KB7KB7KB8KB8KB9KB-19KB-1 OS盤區(qū)地址盤區(qū)地址盤區(qū)地址盤區(qū)地址盤區(qū)地址盤區(qū)地址0 01 12 20 00 01 15 56 6頁號頁號輔存地址輔存地址 存在位存在位 塊號塊號作業(yè)作業(yè)1頁表頁表盤區(qū)地址盤區(qū)地址盤區(qū)地址盤區(qū)地址盤區(qū)地址盤區(qū)地址0 01 12 20 00 01 18 83 3作業(yè)作業(yè)3頁表頁表作業(yè)作業(yè)2地址空間地址空間0 01KB1KB2KB2KB3KB3KB4KB-14KB-1mov r1,2120mov r1,2120add r1,3

13、410add r1,3410盤區(qū)地址盤區(qū)地址盤區(qū)地址盤區(qū)地址盤區(qū)地址盤區(qū)地址0 01 12 20 00 01 14 4盤區(qū)地址盤區(qū)地址3 3 2 2作業(yè)作業(yè)2頁表頁表1 1mov r1,2120mov r1,2120add r1,3410add r1,341021202120分解為：分解為： p=2 , d=72p=2 , d=7234103410分解為：分解為： p=3, d=308p=3, d=3080 07 7 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理13 當(dāng)作業(yè)當(dāng)作業(yè)2 2相應(yīng)進(jìn)程運(yùn)行時(shí)，當(dāng)程序執(zhí)行到相應(yīng)進(jìn)程運(yùn)行時(shí)，當(dāng)程序執(zhí)行到“mov mov r1,2120r1,

14、2120”這條指令，虛地址為這條指令，虛地址為21202120，由分頁機(jī)構(gòu)得，由分頁機(jī)構(gòu)得p=2,d=72,p=2,d=72,查頁表中該頁的存在位為查頁表中該頁的存在位為1 1，該頁不在主存，發(fā)生，該頁不在主存，發(fā)生缺頁中斷，因此時(shí)主存中有空白區(qū)，故直接調(diào)入，放到第缺頁中斷，因此時(shí)主存中有空白區(qū)，故直接調(diào)入，放到第7 7塊塊上，修改頁表后上，修改頁表后, , 程序從斷點(diǎn)處繼續(xù)執(zhí)行。程序從斷點(diǎn)處繼續(xù)執(zhí)行。 當(dāng)執(zhí)行到當(dāng)執(zhí)行到“add r1,3410add r1,3410”這條指令虛地址為這條指令虛地址為34103410，由分，由分頁機(jī)構(gòu)得頁機(jī)構(gòu)得p=3,p=3,需要訪問第需要訪問第3 3頁，查頁表

15、中該頁的存在位為頁，查頁表中該頁的存在位為1 1，該，該頁也不在主存，發(fā)生缺頁中斷。但是頁也不在主存，發(fā)生缺頁中斷。但是, , 此時(shí)主存中沒有空白塊，此時(shí)主存中沒有空白塊，故需要淘汰一個(gè)頁面信息故需要淘汰一個(gè)頁面信息, 選擇淘汰的頁面需要確定淘汰的原選擇淘汰的頁面需要確定淘汰的原則。則。 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理14五、請求分頁中的內(nèi)存分配五、請求分頁中的內(nèi)存分配2. 2. 內(nèi)存分配策略內(nèi)存分配策略1) 1) 固定分配局部置換固定分配局部置換2) 2) 可變分配全局置換可變分配全局置換3) 3) 可變分配局部置換可變分配局部置換 最小物理塊數(shù)的確定最小物理塊

16、數(shù)的確定最小物理塊數(shù)是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。最小物理塊數(shù)是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。3. 3. 物理塊分配算法物理塊分配算法1) 1) 平均分配算法平均分配算法 2) 2) 按比例分配算法按比例分配算法3) 3) 考慮優(yōu)先權(quán)的分配算法考慮優(yōu)先權(quán)的分配算法 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理155.3 5.3 頁面置換頁面置換 ( (淘汰淘汰) )算法算法 頁面置換算法性能的優(yōu)劣直接影響到系頁面置換算法性能的優(yōu)劣直接影響到系統(tǒng)的效率，若選用不當(dāng)會(huì)導(dǎo)致剛淘汰出內(nèi)存統(tǒng)的效率，若選用不當(dāng)會(huì)導(dǎo)致剛淘汰出內(nèi)存的頁面又要再次調(diào)入內(nèi)存，這樣使處理器大的

17、頁面又要再次調(diào)入內(nèi)存，這樣使處理器大部分時(shí)間都用于頁面調(diào)度上。部分時(shí)間都用于頁面調(diào)度上。 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理16一、常用的頁面置換一、常用的頁面置換 ( (淘汰淘汰) )算法算法1 1、最佳置換算法（、最佳置換算法（OPTOPT）基本思想：基本思想：從主存移出永遠(yuǎn)不再需要的頁面，若無這樣從主存移出永遠(yuǎn)不再需要的頁面，若無這樣的頁面存在，則應(yīng)選擇最長時(shí)間不再需要訪問的頁面。的頁面存在，則應(yīng)選擇最長時(shí)間不再需要訪問的頁面。 這種最佳策略本身不是一種實(shí)際的方法，因?yàn)轫撁孢@種最佳策略本身不是一種實(shí)際的方法，因?yàn)轫撁嬖L問的未來順序是不知道的。但是，可將其它的實(shí)用

18、方訪問的未來順序是不知道的。但是，可將其它的實(shí)用方法與之比較來評價(jià)這些方法的優(yōu)劣。所以，這種最佳策法與之比較來評價(jià)這些方法的優(yōu)劣。所以，這種最佳策略具有理論上的意義。略具有理論上的意義。 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理17432143543215443432432143251325+=缺頁次數(shù)為缺頁次數(shù)為: 6次次缺頁中斷率缺頁中斷率:f = 6 / 12 = 50 %4321435432154 4343243143523 5215+=缺頁次數(shù)為缺頁次數(shù)為: 7次次缺頁中斷率缺頁中斷率:f = 7 / 12 = 58 %當(dāng)分配的頁面數(shù)為當(dāng)分配的頁面數(shù)為3時(shí)時(shí): 當(dāng)

19、分配的頁面數(shù)為當(dāng)分配的頁面數(shù)為4時(shí)時(shí): 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理18 2 2、先進(jìn)先出頁面置換算法（、先進(jìn)先出頁面置換算法（FIFOFIFO） 基本思想：基本思想：最先進(jìn)入內(nèi)存的頁面不再被使用的可能性最大。最先進(jìn)入內(nèi)存的頁面不再被使用的可能性最大。 算法實(shí)現(xiàn)：算法實(shí)現(xiàn)：分配給一個(gè)作業(yè)的存儲(chǔ)塊數(shù)為分配給一個(gè)作業(yè)的存儲(chǔ)塊數(shù)為m m，建立一張，建立一張m m個(gè)個(gè)元素的隊(duì)列表元素的隊(duì)列表Q(0)Q(0)，Q(1)Q(1)，Q(MQ(M1)1)和一個(gè)替換指針，和一個(gè)替換指針，這個(gè)隊(duì)列是按頁面調(diào)入主存的先后順序排列的，而這個(gè)指這個(gè)隊(duì)列是按頁面調(diào)入主存的先后順序排列的，而

20、這個(gè)指針始終指向最早調(diào)入主存的一頁。針始終指向最早調(diào)入主存的一頁。 頁號頁號先進(jìn)先出算法圖例先進(jìn)先出算法圖例替換指針替換指針（指向最老的一頁）（指向最老的一頁） 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理1943214354321544343243215 321542154315432143215 32+=缺頁次數(shù)為缺頁次數(shù)為: 10次次缺頁中斷率缺頁中斷率:f = 10 / 12 = 83 %4321435432154 4343213 21 421435 435 235 21+=缺頁次數(shù)為缺頁次數(shù)為: 9次次缺頁中斷率缺頁中斷率:f = 9 / 12 = 75 %當(dāng)分配的頁

21、面數(shù)為當(dāng)分配的頁面數(shù)為3時(shí)時(shí): 當(dāng)分配的頁面數(shù)為當(dāng)分配的頁面數(shù)為4時(shí)時(shí): 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理20特點(diǎn)：1）這種算法實(shí)現(xiàn)）這種算法實(shí)現(xiàn)簡單簡單，只是在按線性順序訪問地址，只是在按線性順序訪問地址空間時(shí)才是理想的，否則效率不高。特別是遇到循空間時(shí)才是理想的，否則效率不高。特別是遇到循環(huán)執(zhí)行的程序段，往往把頻繁重復(fù)訪問的頁面被周環(huán)執(zhí)行的程序段，往往把頻繁重復(fù)訪問的頁面被周期地選擇為淘汰的對象。期地選擇為淘汰的對象。2 2）存在）存在BeladyBelady現(xiàn)象（缺頁中斷率隨著被分配的頁架現(xiàn)象（缺頁中斷率隨著被分配的頁架數(shù)的增加反而上升）。產(chǎn)生數(shù)的增加反而上升

22、）。產(chǎn)生BeladyBelady現(xiàn)象的原因在于現(xiàn)象的原因在于該算法根本沒有考慮程序執(zhí)行的動(dòng)態(tài)特征。該算法根本沒有考慮程序執(zhí)行的動(dòng)態(tài)特征。 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理213 3、最近最久未用算法（、最近最久未用算法（LRULRU）基本思想：基本思想：選擇最近一段時(shí)間內(nèi)最長時(shí)間沒有被訪問選擇最近一段時(shí)間內(nèi)最長時(shí)間沒有被訪問過的頁淘汰。過的頁淘汰。 這種算法認(rèn)為某一頁被訪問過，它很可能馬上還這種算法認(rèn)為某一頁被訪問過，它很可能馬上還要被訪問，相反若某頁長期未被使用，則它可能在最要被訪問，相反若某頁長期未被使用，則它可能在最近的將來一段時(shí)間也不會(huì)被使用。近的將來一段時(shí)

23、間也不會(huì)被使用。 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理2243214354321544343243214 351435243125321+=缺頁次數(shù)為缺頁次數(shù)為: 8次次缺頁中斷率缺頁中斷率:f = 8 / 12 = 67%4321435432154 4343213 21 421435 432 43213215+=缺頁次數(shù)為缺頁次數(shù)為: 10次次缺頁中斷率缺頁中斷率:f = 10 / 12 = 83 %當(dāng)分配的頁面數(shù)為當(dāng)分配的頁面數(shù)為3時(shí)時(shí): 當(dāng)分配的頁面數(shù)為當(dāng)分配的頁面數(shù)為4時(shí)時(shí): 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理234 4、最近最少用算法

24、（、最近最少用算法（LFULFU）基本思想：基本思想：在需要淘汰某一頁時(shí)，首先淘汰到當(dāng)前時(shí)在需要淘汰某一頁時(shí)，首先淘汰到當(dāng)前時(shí)間為止，被訪問次數(shù)最少的那一頁。間為止，被訪問次數(shù)最少的那一頁。特點(diǎn)：特點(diǎn)：通過設(shè)置訪問計(jì)數(shù)器實(shí)現(xiàn)。通過設(shè)置訪問計(jì)數(shù)器實(shí)現(xiàn)。 這類算法比較普遍地適用于各種類型的程序。但這類算法比較普遍地適用于各種類型的程序。但是，實(shí)現(xiàn)起來比較困難，因?yàn)橐獙ο惹暗脑L問歷史時(shí)是，實(shí)現(xiàn)起來比較困難，因?yàn)橐獙ο惹暗脑L問歷史時(shí)時(shí)加以記錄和更新。由軟件實(shí)現(xiàn)，系統(tǒng)開銷太大；如時(shí)加以記錄和更新。由軟件實(shí)現(xiàn)，系統(tǒng)開銷太大；如由硬件執(zhí)行，則會(huì)增加機(jī)器成本。由硬件執(zhí)行，則會(huì)增加機(jī)器成本。 操作系統(tǒng)操作系統(tǒng)

25、第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理24LRU的近似算法:5、最近不用算法（NRU）基本思想：基本思想：在需要淘汰某一頁時(shí)，從那些最近一段時(shí)間在需要淘汰某一頁時(shí)，從那些最近一段時(shí)間內(nèi)未被訪問的頁中任選一頁淘汰。內(nèi)未被訪問的頁中任選一頁淘汰。特點(diǎn)：特點(diǎn)：只要在頁表中增設(shè)一個(gè)頁面訪問位即可實(shí)現(xiàn)。只要在頁表中增設(shè)一個(gè)頁面訪問位即可實(shí)現(xiàn)。為了表示淘汰置換狀態(tài)，頁表的表目還需要擴(kuò)充。為了表示淘汰置換狀態(tài)，頁表的表目還需要擴(kuò)充。頁號頁號塊號塊號存在位存在位外存始址外存始址訪問位訪問位 修改位修改位 訪問位訪問位0該頁未被訪問過。該頁未被訪問過。1該頁已被訪問過。該頁已被訪問過。 修改位修改位0該頁未

26、被修改過。該頁未被修改過。1該頁已被修改過。該頁已被修改過。 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理25 優(yōu)點(diǎn)：優(yōu)點(diǎn)：算法實(shí)現(xiàn)比較簡單。算法實(shí)現(xiàn)比較簡單。缺點(diǎn)：缺點(diǎn)：1）將所有存儲(chǔ)塊的訪問位置）將所有存儲(chǔ)塊的訪問位置0的周期的周期T的大小的大小選擇不易確定。選擇不易確定。 T太大，所有塊的訪問位可能都為太大，所有塊的訪問位可能都為1，確定不了哪個(gè)是最近最久末用的頁；若確定不了哪個(gè)是最近最久末用的頁；若T太小，訪問太小，訪問位為位為0的塊可能相當(dāng)多，因而所選擇的不一定是最近的塊可能相當(dāng)多，因而所選擇的不一定是最近最久未用的頁。最久未用的頁。 2）如缺頁中斷剛巧發(fā)生在系統(tǒng)對所

27、有引用位）如缺頁中斷剛巧發(fā)生在系統(tǒng)對所有引用位重置重置0之后，則幾乎所有塊的引用位為之后，則幾乎所有塊的引用位為0，因而也有，因而也有可能把常用的頁不適當(dāng)?shù)靥蕴鋈?。可能把常用的頁不適當(dāng)?shù)靥蕴鋈ァ?操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理26 2. 缺頁中斷率（頁面失效率）缺頁中斷率（頁面失效率）: 欲訪問的頁面不在主存欲訪問的頁面不在主存稱為缺頁故障（或頁面失效）。缺頁故障的次數(shù)占全部稱為缺頁故障（或頁面失效）。缺頁故障的次數(shù)占全部訪問頁數(shù)的百分比即為缺頁中斷率（頁面失效率）。訪問頁數(shù)的百分比即為缺頁中斷率（頁面失效率）。 f = （缺頁次數(shù)）（缺頁次數(shù)）/（訪問頁面總

28、數(shù)）（訪問頁面總數(shù)） 100 % 二、淘汰算法的性能評價(jià)二、淘汰算法的性能評價(jià)1. 頁面走向（頁地址流）頁面走向（頁地址流）: 一個(gè)程序在其運(yùn)行過程中所訪一個(gè)程序在其運(yùn)行過程中所訪問的頁號的序列稱為頁面走向。問的頁號的序列稱為頁面走向。3. 抖動(dòng)：抖動(dòng)：導(dǎo)致系統(tǒng)效率急劇下降的主輔存之間的頻繁的導(dǎo)致系統(tǒng)效率急劇下降的主輔存之間的頻繁的頁面置換現(xiàn)象稱為抖動(dòng)（頁面置換現(xiàn)象稱為抖動(dòng)（ 顛簸）顛簸） 。 抖動(dòng)現(xiàn)象花費(fèi)了系統(tǒng)的大量開銷，但收效甚微。抖動(dòng)現(xiàn)象花費(fèi)了系統(tǒng)的大量開銷，但收效甚微。 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理27 1. 頁面的大小頁面的大小 頁面增大，可減少缺頁中

29、斷的次數(shù)，但頁內(nèi)的浪費(fèi)增大。頁面增大，可減少缺頁中斷的次數(shù)，但頁內(nèi)的浪費(fèi)增大。 三、影響缺頁中斷率的因素三、影響缺頁中斷率的因素缺頁次數(shù)缺頁次數(shù)主存容量主存容量工作集工作集 任何程序在局部性放入任何程序在局部性放入主存時(shí)都有一個(gè)臨界值的要主存時(shí)都有一個(gè)臨界值的要求，這個(gè)主存要求的臨界值求，這個(gè)主存要求的臨界值被稱為被稱為工作集工作集 2. 分配給作業(yè)的主存容量分配給作業(yè)的主存容量 分配給作業(yè)的頁面數(shù)增多可減少缺頁中斷的次數(shù)。分配給作業(yè)的頁面數(shù)增多可減少缺頁中斷的次數(shù)。 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理28 3. 頁面調(diào)度算法的性能頁面調(diào)度算法的性能 好的調(diào)度算法應(yīng)盡

30、量避免或減少抖動(dòng)現(xiàn)象的出現(xiàn)。好的調(diào)度算法應(yīng)盡量避免或減少抖動(dòng)現(xiàn)象的出現(xiàn)。例如：例如：如果有一個(gè)程序要把如果有一個(gè)程序要把5050的數(shù)組賦初值形成單的數(shù)組賦初值形成單位矩陣，每個(gè)主存塊為位矩陣，每個(gè)主存塊為200個(gè)字節(jié)，每個(gè)數(shù)組元素占個(gè)字節(jié)，每個(gè)數(shù)組元素占2個(gè)個(gè)字節(jié)，若已分配到字節(jié)，若已分配到2個(gè)主存塊可供使用，個(gè)主存塊可供使用，數(shù)組中的元素?cái)?shù)組中的元素按行編址按行編址，其初始狀態(tài)為空，程序編制如下：，其初始狀態(tài)為空，程序編制如下：問：各會(huì)產(chǎn)生多少次缺頁中斷？問：各會(huì)產(chǎn)生多少次缺頁中斷？4. 用戶程序編制的方法不合適用戶程序編制的方法不合適提高程序的局部性程度，可減少缺頁中斷的次數(shù)提高程序的局部

31、性程度，可減少缺頁中斷的次數(shù) 分析：分析：整個(gè)數(shù)組所占地址空間為（整個(gè)數(shù)組所占地址空間為（5050）2 = 5000字字節(jié)，分為節(jié)，分為5000/ 200 =25個(gè)頁。每個(gè)頁中有兩行、個(gè)頁。每個(gè)頁中有兩行、100個(gè)數(shù)個(gè)數(shù)組元素。組元素。 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理29（1） VAR A : ARRAY 1.50 , 1.50 of integer ; i , j : integer ; BEGIN FOR i : = 1 to 50 DO FOR j : = 1 to 50 DO IF i = j THEN A i , j : = 1 ELSE A i , j

32、 : = 0 ; END .（2） VAR A : ARRAY 1.50 , 1.50 of integer ; i , j : integer ; BEGIN FOR j : = 1 to 50 DO FOR i : = 1 to 50 DO IF i = j THEN A i , j : = 1 ELSE A i , j : = 0 ; END .缺頁中斷的次數(shù)為缺頁中斷的次數(shù)為: 25次次缺頁中斷的次數(shù)為缺頁中斷的次數(shù)為: 1250次次 操作系統(tǒng)操作系統(tǒng) 第五章第五章 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理30四、四、請求式分頁系統(tǒng)優(yōu)點(diǎn)請求式分頁系統(tǒng)優(yōu)點(diǎn) (1) (1)可提供大容量的多個(gè)虛擬存儲(chǔ)器

33、可提供大容量的多個(gè)虛擬存儲(chǔ)器。作業(yè)的地址空間不再。作業(yè)的地址空間不再受實(shí)際主存大小的限制。便于大、中、小計(jì)算機(jī)更好地兼容。受實(shí)際主存大小的限制。便于大、中、小計(jì)算機(jī)更好地兼容。 (2) (2)更有效地利用了主存更有效地利用了主存。作業(yè)中不常使用的頁不會(huì)長期駐。作業(yè)中不常使用的頁不會(huì)長期駐留在主存，而這次運(yùn)行用不到的信息則不會(huì)裝入主存。這樣，留在主存，而這次運(yùn)行用不到的信息則不會(huì)裝入主存。這樣，通常有通常有2525或更多一些的作業(yè)地址空間不被裝入主存，因?yàn)檫@或更多一些的作業(yè)地址空間不被裝入主存，因?yàn)檫@部分僅在特定的情況下才會(huì)被用到部分僅在特定的情況下才會(huì)被用到( (如出錯(cuò)處理例程如出錯(cuò)處理例程) )。 (3) (3)多道程序運(yùn)行的程度更高了多道程序運(yùn)行的程度更高了。采用前面討論的幾種存儲(chǔ)。采用前面討論的幾種存儲(chǔ)管理方案，程序的道數(shù)都受到主存大小的嚴(yán)格限制，而請求頁管理方案，程序的道數(shù)都受到主存大小的嚴(yán)格限制，而請求頁式系統(tǒng)中，這種限制大大放寬了。式系統(tǒng)中，這種限制大大放寬了。 (4) (4)更加方便了用戶，特別是大作業(yè)的用戶更加方便了用戶，特別