操作系統(tǒng) Operating System課件

1、操作系統(tǒng) Operating System第第4 4章章 存儲管理存儲管理4.1 4.1 存儲管理的原理存儲管理的原理 4.2 4.2 連續(xù)分配存儲管理連續(xù)分配存儲管理 4.3 4.3 離散分配存儲管理離散分配存儲管理4.4 4.4 內(nèi)核主存管理內(nèi)核主存管理4.5 4.5 虛擬存儲技術(shù)虛擬存儲技術(shù)4.6 4.6 虛擬頁式存儲管理虛擬頁式存儲管理 4.7 4.7 虛擬段式存儲管理虛擬段式存儲管理4.8 4.8 存儲管理實(shí)例存儲管理實(shí)例4.5 4.5 虛擬存儲技術(shù)虛擬存儲技術(shù)4.5.1 4.5.1 程序局部性原理程序局部性原理 4.5.2 4.5.2 虛擬存儲的實(shí)現(xiàn)虛擬存儲的實(shí)現(xiàn)&虛擬內(nèi)存

2、技術(shù)(Virtual Memory)(Virtual Memory)誕生于1961年。&廣泛使用是從上個世紀(jì)70年代初以后，今天幾乎所有的操作系統(tǒng)都采用虛擬內(nèi)存技術(shù)來管理內(nèi)存。&這是一種利用虛擬存儲器來邏輯擴(kuò)充物理內(nèi)存的技術(shù)。其基本思想是用軟硬件技術(shù)把內(nèi)存與外存這兩級存儲器當(dāng)成一級用軟硬件技術(shù)把內(nèi)存與外存這兩級存儲器當(dāng)成一級存儲器來用，從而給用戶提供了一個比內(nèi)存也比任何應(yīng)用程存儲器來用，從而給用戶提供了一個比內(nèi)存也比任何應(yīng)用程序大得多的虛擬存儲器，使得用戶編程時再也不用考慮內(nèi)存序大得多的虛擬存儲器，使得用戶編程時再也不用考慮內(nèi)存大小的限制了，給用戶編程帶來極大的方便。大小的限制

3、了，給用戶編程帶來極大的方便。&虛擬內(nèi)存技術(shù)的實(shí)現(xiàn)也利用了自動覆蓋和交換技術(shù)。 4.5.1 4.5.1 程序局部性原理程序局部性原理&1.1.局部性原理局部性原理(principle of locality)： 指程序在執(zhí)行過程中的一個較短時期內(nèi)，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。&2.2.局部性主要表現(xiàn)：局部性主要表現(xiàn)：F時間局部性：時間局部性：是指一段指令在某一時間段內(nèi)會被反是指一段指令在某一時間段內(nèi)會被反復(fù)執(zhí)行。即程序某一部分的數(shù)據(jù)或指令被重復(fù)性地復(fù)執(zhí)行。即程序某一部分的數(shù)據(jù)或指令被重復(fù)性地訪問，它們對應(yīng)于程序結(jié)構(gòu)中的循環(huán)、子程序、常訪問，它

4、們對應(yīng)于程序結(jié)構(gòu)中的循環(huán)、子程序、常用到的變量及數(shù)據(jù)等用到的變量及數(shù)據(jù)等 ；F空間局部性空間局部性：是指一旦某一個存儲單元被訪問，那是指一旦某一個存儲單元被訪問，那么它附近的單元也將很快被訪問。這對應(yīng)于程序結(jié)么它附近的單元也將很快被訪問。這對應(yīng)于程序結(jié)構(gòu)中的順序執(zhí)行的指令、線性數(shù)據(jù)結(jié)構(gòu)以及在相鄰構(gòu)中的順序執(zhí)行的指令、線性數(shù)據(jù)結(jié)構(gòu)以及在相鄰位置存放的數(shù)據(jù)或變量等。而程序中的分支和調(diào)用位置存放的數(shù)據(jù)或變量等。而程序中的分支和調(diào)用子程序只是將程序的訪問空間從一處移到另外一處，子程序只是將程序的訪問空間從一處移到另外一處，仍具有局部性。仍具有局部性。F排他性：排他性：程序運(yùn)行不但體現(xiàn)在時間、空間的局部

5、性，還體現(xiàn)在某些程序段執(zhí)行的排他性。即程序設(shè)計(jì)者編程時要考慮程序執(zhí)行時所能遇到的各種情況，但具體到一次程序的執(zhí)行，并不會發(fā)生所有的狀況。因而某些程序段在進(jìn)程整個運(yùn)行期間，可能因而某些程序段在進(jìn)程整個運(yùn)行期間，可能根本不使用，如出錯處理、分支語句等。根本不使用，如出錯處理、分支語句等。因而，沒有用到的程序段就不必調(diào)入內(nèi)存。另外，有些程序段僅執(zhí)行一次，以后就再也不會用到，這樣的程序段也沒有必要一直占用內(nèi)存空間。 &綜上所述：綜上所述：程序只要裝入內(nèi)存一部分就可以運(yùn)行，程序只要裝入內(nèi)存一部分就可以運(yùn)行，當(dāng)用到不在內(nèi)存的部分時，再將其裝入內(nèi)存。當(dāng)用到不在內(nèi)存的部分時，再將其裝入內(nèi)存。換句換句話

6、就是說程序全部裝入內(nèi)存并不是程序運(yùn)行的必要話就是說程序全部裝入內(nèi)存并不是程序運(yùn)行的必要條件。條件。 4.5.2 4.5.2 虛擬存儲的實(shí)現(xiàn)虛擬存儲的實(shí)現(xiàn)1.1.虛擬存儲技術(shù)虛擬存儲技術(shù)如果把程序部分裝入內(nèi)存，其余大部分放在外存，而程序又能運(yùn)如果把程序部分裝入內(nèi)存，其余大部分放在外存，而程序又能運(yùn)行，這樣我們就擁有了一個比有限的實(shí)際內(nèi)存空間大得多的、邏行，這樣我們就擁有了一個比有限的實(shí)際內(nèi)存空間大得多的、邏輯的虛擬內(nèi)存空間。輯的虛擬內(nèi)存空間。即用大容量的外存來模擬內(nèi)存，這種存儲模即用大容量的外存來模擬內(nèi)存，這種存儲模式就稱之為虛擬存儲技術(shù)。式就稱之為虛擬存儲技術(shù)。 2.2.虛擬技術(shù)實(shí)現(xiàn)的關(guān)鍵虛擬

7、技術(shù)實(shí)現(xiàn)的關(guān)鍵(1)怎樣才能發(fā)現(xiàn)欲執(zhí)行的指令或數(shù)據(jù)不在內(nèi)存怎樣才能發(fā)現(xiàn)欲執(zhí)行的指令或數(shù)據(jù)不在內(nèi)存? 簡單有效方法就是進(jìn)行標(biāo)識簡單有效方法就是進(jìn)行標(biāo)識(2)怎樣將不在內(nèi)存的部分調(diào)入進(jìn)來怎樣將不在內(nèi)存的部分調(diào)入進(jìn)來。 通常系統(tǒng)采用中斷技術(shù)完成調(diào)入工作。通常系統(tǒng)采用中斷技術(shù)完成調(diào)入工作。(3)在內(nèi)存中的作業(yè)如何組織？在內(nèi)存中的作業(yè)如何組織？一個進(jìn)程可被分為多次調(diào)入內(nèi)存，這樣很難保證進(jìn)程在內(nèi)存中占一個進(jìn)程可被分為多次調(diào)入內(nèi)存，這樣很難保證進(jìn)程在內(nèi)存中占據(jù)一個連續(xù)的空間，實(shí)際上進(jìn)程在內(nèi)存中是離散存儲的。據(jù)一個連續(xù)的空間，實(shí)際上進(jìn)程在內(nèi)存中是離散存儲的。 虛擬技術(shù)進(jìn)一步說明虛擬技術(shù)進(jìn)一步說明因而因而系統(tǒng)要

8、提供必要的硬件支持系統(tǒng)要提供必要的硬件支持，如虛擬頁式，如虛擬頁式存儲中的頁表機(jī)制、缺頁中斷機(jī)構(gòu)以及相應(yīng)存儲中的頁表機(jī)制、缺頁中斷機(jī)構(gòu)以及相應(yīng)的地址變換機(jī)構(gòu)。的地址變換機(jī)構(gòu)。虛擬存儲技術(shù)是虛擬存儲技術(shù)是將內(nèi)存與外存有機(jī)地結(jié)合在一將內(nèi)存與外存有機(jī)地結(jié)合在一起，從而得到一個容量很大的虛擬空間。起，從而得到一個容量很大的虛擬空間。使使用戶感到有一個很大的內(nèi)存，不用再考慮內(nèi)用戶感到有一個很大的內(nèi)存，不用再考慮內(nèi)存的容量限制。存的容量限制。虛存雖然比內(nèi)存要大得多，但不可能無限大，虛存雖然比內(nèi)存要大得多，但不可能無限大，其大小要受到外存空間的限制以及其大小要受到外存空間的限制以及CPU地址地址所能表示范圍

9、的限制。所能表示范圍的限制。&大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序；&大的用戶空間：提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存(real memory)&并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；&易于開發(fā)：與覆蓋技術(shù)比較，不必影響編程時的程序結(jié)構(gòu)3.3.引入虛擬存儲技術(shù)的好處引入虛擬存儲技術(shù)的好處總?cè)萘坎怀^物理內(nèi)存和外存交換區(qū)容量之和。其總?cè)萘坎怀^物理內(nèi)存和外存交換區(qū)容量之和。其運(yùn)行速度接近于內(nèi)存，每位的成本又接近于外存，運(yùn)行速度接近于內(nèi)存，每位的成本又接近于外存，是一種性能非常優(yōu)越的存儲管理技術(shù)是一種性能非常優(yōu)越的存儲管理技術(shù) 4. 4. 虛擬存

10、儲技術(shù)的特征虛擬存儲技術(shù)的特征&不連續(xù)性不連續(xù)性：物理內(nèi)存分配的不連續(xù)，虛擬地址空間使用的不連續(xù)（數(shù)據(jù)段和棧段之間的空閑空間，共享段和動態(tài)鏈接庫占用的空間）&部分交換：部分交換：與交換技術(shù)相比較，虛擬存儲的調(diào)入和調(diào)出是對部分虛擬地址空間進(jìn)行的；&大空間：大空間：通過物理內(nèi)存和快速外存相結(jié)合，提供大范圍的虛擬地址空間虛擬存儲技術(shù)的種類：虛擬存儲技術(shù)的種類：虛擬頁式虛擬段式虛擬段頁式4.6 4.6 虛擬頁式存儲管理虛擬頁式存儲管理 4.6.1 4.6.1 虛擬頁式存儲的實(shí)現(xiàn)虛擬頁式存儲的實(shí)現(xiàn) 4.6.2 4.6.2 頁面分配策略頁面分配策略 4.6.3 4.6.3 頁面置換

11、方法頁面置換方法4.6.4 4.6.4 虛擬頁式存儲的優(yōu)缺點(diǎn)虛擬頁式存儲的優(yōu)缺點(diǎn)返回&系統(tǒng)自動地將作業(yè)的地址空間分頁，將系統(tǒng)的主存空間分塊，頁與塊等大小，在作業(yè)運(yùn)行前，只把初始需要的一部分頁面裝入內(nèi)存塊里，運(yùn)行中需要訪問自己地址空間中的但當(dāng)前不在內(nèi)存的頁面時產(chǎn)生缺頁中斷，由缺頁中斷服務(wù)程序?qū)⑺璧捻撁嬲{(diào)入內(nèi)存，若此時內(nèi)存中沒有空閑物理塊安置請求調(diào)入的新頁面，則系統(tǒng)按預(yù)定的置換策略自動選擇一個或一些在內(nèi)存的頁面，把它們換出到外存。&這里的請求調(diào)入和置換功能請求調(diào)入和置換功能都是比實(shí)分頁存儲管理增加的內(nèi)容，是實(shí)現(xiàn)虛擬存儲的主要功能。 4.6.1 4.6.1 虛擬頁式存儲的實(shí)現(xiàn)虛擬頁

12、式存儲的實(shí)現(xiàn) &標(biāo)記某頁是否在內(nèi)存，用于查詢標(biāo)記某頁是否在內(nèi)存，用于查詢要訪問的要訪問的頁在不在內(nèi)存。頁表如下：頁在不在內(nèi)存。頁表如下：頁號頁號 物理塊號物理塊號 狀態(tài)位狀態(tài)位P P 訪問位訪問位A A 修改位修改位M M外存地址外存地址2.2.頁表機(jī)制頁表機(jī)制其中：外存地址指出該頁在外存的地址，供調(diào)入該頁時用；狀態(tài)為指示該頁是否在內(nèi)存，供程序訪問時用，也是檢查是否缺頁的標(biāo)志位，如置1表示在內(nèi)存 ；訪問位或訪問字段則是該頁被訪問過的標(biāo)志或該頁被訪問過的次數(shù)；修改位表示該頁是否被修改過；存取控制字段則是用來限制頁面被安全共享的。 3.3.動態(tài)地址變換動態(tài)地址變換&在虛擬頁式存儲中

13、，應(yīng)采用動態(tài)地址變換方式，因?yàn)槟骋挥谔摂M頁式存儲中，應(yīng)采用動態(tài)地址變換方式，因?yàn)槟骋挥麍?zhí)行的指令可能不在內(nèi)存，只能在指令執(zhí)行之前完成地址變執(zhí)行的指令可能不在內(nèi)存，只能在指令執(zhí)行之前完成地址變換。換。任一作業(yè)都應(yīng)在自己的虛擬地址空間中執(zhí)行，任一作業(yè)都應(yīng)在自己的虛擬地址空間中執(zhí)行，所以要為所以要為用戶作業(yè)設(shè)置一個虛擬地址指針用戶作業(yè)設(shè)置一個虛擬地址指針VP，虛擬地址依然是由頁號，虛擬地址依然是由頁號和頁內(nèi)偏移地址組成的。和頁內(nèi)偏移地址組成的。&系統(tǒng)總是執(zhí)行系統(tǒng)總是執(zhí)行VP虛指針?biāo)赶虻闹噶睿瑸榱藢⑻摂M地址虛指針?biāo)赶虻闹噶?，為了將虛擬地址VP變換為對應(yīng)的實(shí)存地址，因此變換為對應(yīng)的實(shí)存地址

14、，因此先要查找頁表。若從頁表中查先要查找頁表。若從頁表中查出此頁不在內(nèi)存（狀態(tài)位為出此頁不在內(nèi)存（狀態(tài)位為0），則產(chǎn)生一個缺頁中斷。），則產(chǎn)生一個缺頁中斷。此時，此時，進(jìn)程暫停當(dāng)前指令執(zhí)行，進(jìn)程暫停當(dāng)前指令執(zhí)行，CPU轉(zhuǎn)去執(zhí)行缺頁中斷處理程序。轉(zhuǎn)去執(zhí)行缺頁中斷處理程序。若該頁已在內(nèi)存，若該頁已在內(nèi)存，則指令的地址映射過程與頁式存儲是一樣則指令的地址映射過程與頁式存儲是一樣的。即將塊號和頁內(nèi)地址相并接形成物理地址的。即將塊號和頁內(nèi)地址相并接形成物理地址IP，處理器再，處理器再從從IP中取指令執(zhí)行。中取指令執(zhí)行。4.4.缺頁中斷缺頁中斷 no yes no yes yes no 硬 件 部 分 軟

15、 件 部 分 圖 3 24 缺 頁 中 斷 處 理 流 程 進(jìn) 程 被 創(chuàng) 建后 ， 進(jìn) 入 就 緒隊(duì) 列 進(jìn) 程 被 調(diào) 度 執(zhí)啟 動 待 執(zhí) 行 指 令計(jì) 算 虛 頁號 與 頁 內(nèi)地 址 該 頁 在 內(nèi) 存 ？ 地 址 映 射 執(zhí) 行 下 一 條 指 令 訪 問 內(nèi) 存 完 成 該 指令 保 留 當(dāng) 前 進(jìn) 程 現(xiàn) 場 按 某 算 法選 一 頁 淘汰 調(diào) 入 所 需 頁 面 該 頁 已改 過 調(diào) 整 頁 表及 空 閑 頁面 表 恢 復(fù) 被 中斷 進(jìn) 程 現(xiàn)場 把把 該該 頁頁寫寫 回回 外外存存 有 空 閑頁面嗎 ？ 5.5.缺頁率缺頁率&雖然通過缺頁中斷將所需要的頁調(diào)入內(nèi)存，但缺

16、頁中雖然通過缺頁中斷將所需要的頁調(diào)入內(nèi)存，但缺頁中斷的頻繁發(fā)生會嚴(yán)重影響程序執(zhí)行的效率。為了標(biāo)識斷的頻繁發(fā)生會嚴(yán)重影響程序執(zhí)行的效率。為了標(biāo)識缺頁中斷發(fā)生的頻度，可以引入缺頁率來表示。缺頁中斷發(fā)生的頻度，可以引入缺頁率來表示。 &設(shè)進(jìn)程在其執(zhí)行期間共進(jìn)行了設(shè)進(jìn)程在其執(zhí)行期間共進(jìn)行了S S次訪頁操作，其中成次訪頁操作，其中成功訪頁次數(shù)為功訪頁次數(shù)為A A（訪問時該頁在主存），不成功的訪頁（訪問時該頁在主存），不成功的訪頁次數(shù)為次數(shù)為B B（即發(fā)生了缺頁中斷），顯然有：（即發(fā)生了缺頁中斷），顯然有：S=A+BS=A+B，&則該進(jìn)程的缺頁率則該進(jìn)程的缺頁率f f定義為：定義為：f f

17、B/SB/S。&顯然缺頁率越低越好。顯然缺頁率越低越好。4.6.2 4.6.2 頁面分配策略頁面分配策略&虛擬存儲管理在進(jìn)行頁面分配時，要考慮這虛擬存儲管理在進(jìn)行頁面分配時，要考慮這樣的問題：空閑頁面如何管理；采用什么樣樣的問題：空閑頁面如何管理；采用什么樣的分配策略；為進(jìn)程分配多少物理塊比較合的分配策略；為進(jìn)程分配多少物理塊比較合適；在什么時間進(jìn)行頁面分配等。適；在什么時間進(jìn)行頁面分配等。 1.1.空閑頁面管理空閑頁面管理&同頁式存儲管理相似，虛擬存儲方式下的空閑頁面的管理也可同頁式存儲管理相似，虛擬存儲方式下的空閑頁面的管理也可以采用位示圖或空閑頁面鏈的形式。以采用

18、位示圖或空閑頁面鏈的形式。&由于主存中所有進(jìn)程的虛擬地址空間之和遠(yuǎn)大于主存空間，因由于主存中所有進(jìn)程的虛擬地址空間之和遠(yuǎn)大于主存空間，因此進(jìn)程執(zhí)行時常發(fā)生缺頁中斷，這樣不斷地調(diào)入新頁，很快就此進(jìn)程執(zhí)行時常發(fā)生缺頁中斷，這樣不斷地調(diào)入新頁，很快就使主存空間飽和。以后再發(fā)生缺頁時，要先淘汰一頁才能裝入使主存空間飽和。以后再發(fā)生缺頁時，要先淘汰一頁才能裝入新頁，這使得新頁，這使得缺頁處理時間過長，減緩了進(jìn)程的執(zhí)行速度，從缺頁處理時間過長，減緩了進(jìn)程的執(zhí)行速度，從而影響到系統(tǒng)的性能。而影響到系統(tǒng)的性能。&在實(shí)際的系統(tǒng)中，總是維持一定數(shù)量的空閑塊，而不是耗盡所在實(shí)際的系統(tǒng)中，總是維持一定

19、數(shù)量的空閑塊，而不是耗盡所有的空閑塊。即有的空閑塊。即空閑塊數(shù)可以在某一區(qū)間浮動空閑塊數(shù)可以在某一區(qū)間浮動，一旦空閑塊數(shù)，一旦空閑塊數(shù)小于下限值，系統(tǒng)就進(jìn)行頁面置換，以釋放出一些空閑塊，使小于下限值，系統(tǒng)就進(jìn)行頁面置換，以釋放出一些空閑塊，使得總的空閑塊數(shù)不超過系統(tǒng)規(guī)定的上限值即可。即系統(tǒng)設(shè)置專得總的空閑塊數(shù)不超過系統(tǒng)規(guī)定的上限值即可。即系統(tǒng)設(shè)置專門的獨(dú)立進(jìn)程負(fù)責(zé)頁面置換，以保證鏈表的適當(dāng)規(guī)模。門的獨(dú)立進(jìn)程負(fù)責(zé)頁面置換，以保證鏈表的適當(dāng)規(guī)模。2 2 分配策略分配策略&可變分配：可變分配：是指一個進(jìn)程所擁有的物理塊數(shù)是不定的，這種是指一個進(jìn)程所擁有的物理塊數(shù)是不定的，這種分配方式稱之為可

20、變分配。分配方式稱之為可變分配。&固定分配固定分配是指為每個進(jìn)程分配一固定頁數(shù)的內(nèi)存空間，在整是指為每個進(jìn)程分配一固定頁數(shù)的內(nèi)存空間，在整個運(yùn)行期間都不再改變。個運(yùn)行期間都不再改變。& 平均分配算法，平均分配算法，是將系統(tǒng)中所有可供分配的物理塊，平均是將系統(tǒng)中所有可供分配的物理塊，平均分配給每一個進(jìn)程。例如，當(dāng)系統(tǒng)中有分配給每一個進(jìn)程。例如，當(dāng)系統(tǒng)中有80個空閑塊，個空閑塊，4個進(jìn)個進(jìn)程時，每個進(jìn)程可分得程時，每個進(jìn)程可分得20個物理塊。這種平均分配方式因其個物理塊。這種平均分配方式因其未考慮各進(jìn)程本身的大小，會造成事實(shí)上的不公平。如有一未考慮各進(jìn)程本身的大小，會造成事實(shí)上的不

21、公平。如有一個進(jìn)程其大小為個進(jìn)程其大小為100頁，只分配給它頁，只分配給它20個塊，這樣它必將會個塊，這樣它必將會有很高的缺頁率；而另一個進(jìn)程只有有很高的缺頁率；而另一個進(jìn)程只有10頁，卻有頁，卻有10個塊在閑個塊在閑置未用。所以在平均的思想下，還要考慮進(jìn)程的大小。置未用。所以在平均的思想下，還要考慮進(jìn)程的大小。& 按比例分配算法，按比例分配算法，根據(jù)進(jìn)程的大小按比例分配空閑塊。設(shè)根據(jù)進(jìn)程的大小按比例分配空閑塊。設(shè)系統(tǒng)中現(xiàn)有系統(tǒng)中現(xiàn)有m個進(jìn)程、個進(jìn)程、n個空閑塊，每個進(jìn)程擁有的頁數(shù)為個空閑塊，每個進(jìn)程擁有的頁數(shù)為Si，則系統(tǒng)中所有進(jìn)程頁數(shù)之和為：則系統(tǒng)中所有進(jìn)程頁數(shù)之和為： S = S

22、1 + S2 + S3 + + Sm 則為每個進(jìn)程分配的物理塊數(shù)為：則為每個進(jìn)程分配的物理塊數(shù)為： Bi = （Si / S） n ，Bi應(yīng)向下取整。應(yīng)向下取整。& 優(yōu)先權(quán)分配算法，優(yōu)先權(quán)分配算法，為優(yōu)先權(quán)高的作業(yè)分配較多的內(nèi)存空間，為優(yōu)先權(quán)高的作業(yè)分配較多的內(nèi)存空間，這樣可以使重要或緊迫的任務(wù)盡快完成。這時可以將內(nèi)存中這樣可以使重要或緊迫的任務(wù)盡快完成。這時可以將內(nèi)存中的空閑塊分成兩部分：一部分按比例分配給各進(jìn)程，另一部的空閑塊分成兩部分：一部分按比例分配給各進(jìn)程，另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)貫槠湓黾酉鄳?yīng)份額。分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)貫槠湓黾酉鄳?yīng)份額。3.3.工作集工作

23、集&(1)(1)為保證進(jìn)程能正常運(yùn)行最少需要多少物理塊。為保證進(jìn)程能正常運(yùn)行最少需要多少物理塊。從理論上講，進(jìn)程只要獲得一個物理塊就可以運(yùn)行。但是進(jìn)程從理論上講，進(jìn)程只要獲得一個物理塊就可以運(yùn)行。但是進(jìn)程正常運(yùn)行所需的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取正常運(yùn)行所需的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。決于指令的格式、功能和尋址方式。由于分頁是系統(tǒng)的行為由于分頁是系統(tǒng)的行為，可能會出現(xiàn)下面的情景：可能會出現(xiàn)下面的情景：由此可見，由此可見，系統(tǒng)應(yīng)保證任一條指令執(zhí)系統(tǒng)應(yīng)保證任一條指令執(zhí)行時，其所涉及的虛擬地址所在行時，其所涉及的虛擬地址所在的頁都應(yīng)在內(nèi)存

24、中。這個頁數(shù)就的頁都應(yīng)在內(nèi)存中。這個頁數(shù)就是進(jìn)程所需要的最小塊數(shù)是進(jìn)程所需要的最小塊數(shù)，若系，若系統(tǒng)為進(jìn)程所分配的物理塊數(shù)少于統(tǒng)為進(jìn)程所分配的物理塊數(shù)少于此值時，進(jìn)程將無法運(yùn)行。此值時，進(jìn)程將無法運(yùn)行。 123456涉及涉及6 6次缺頁中斷的指令次缺頁中斷的指令指令指令copy A to B數(shù)據(jù)數(shù)據(jù)A：數(shù)據(jù)數(shù)據(jù)B：工作集定義工作集定義&(2)(2)為使進(jìn)程能有效地工作，應(yīng)為它分配多少物理塊合適為使進(jìn)程能有效地工作，應(yīng)為它分配多少物理塊合適&隨著為每個進(jìn)程所分配物理塊數(shù)目的減少，將使進(jìn)程執(zhí)行中隨著為每個進(jìn)程所分配物理塊數(shù)目的減少，將使進(jìn)程執(zhí)行中的缺頁率提高，導(dǎo)致非生產(chǎn)性開銷過大，

25、從而降低了進(jìn)程的的缺頁率提高，導(dǎo)致非生產(chǎn)性開銷過大，從而降低了進(jìn)程的執(zhí)行速度，嚴(yán)重時導(dǎo)致進(jìn)程不能向前推進(jìn)。最少物理塊數(shù)只執(zhí)行速度，嚴(yán)重時導(dǎo)致進(jìn)程不能向前推進(jìn)。最少物理塊數(shù)只能保證程序能執(zhí)行下去，而不是最合適的塊數(shù)。能保證程序能執(zhí)行下去，而不是最合適的塊數(shù)。&在在19681968年，年，DenningDenning提出了工作集理論。提出了工作集理論。所謂工作集就是進(jìn)程所謂工作集就是進(jìn)程在某段時間里實(shí)際上要訪問的頁的集合。在某段時間里實(shí)際上要訪問的頁的集合。依據(jù)程序執(zhí)行時的依據(jù)程序執(zhí)行時的局部特性，可以利用程序過去的行為來估計(jì)它未來的行為。局部特性，可以利用程序過去的行為來估計(jì)它未來的行為

26、。故故定義運(yùn)行進(jìn)程在定義運(yùn)行進(jìn)程在t tw w到到t t這個時間間隔內(nèi)所訪問的頁的集合這個時間間隔內(nèi)所訪問的頁的集合為該進(jìn)程在時間為該進(jìn)程在時間t t的工作集，記為的工作集，記為W W（t t，w w）。）。并把變量并把變量w w稱之稱之為為“工作集窗口尺寸工作集窗口尺寸”，工作集中所包含的頁面數(shù)稱為，工作集中所包含的頁面數(shù)稱為“工工作集尺寸作集尺寸”，記為，記為|W(t,w)|W(t,w)|。(3)(3)工作集的應(yīng)用工作集的應(yīng)用&工作集工作集W W（t t，w w）是二元函數(shù)，隨）是二元函數(shù)，隨t t、w w的值而改變。的值而改變。首先工作首先工作集與時間有關(guān)，即不同時間的工作集其所

27、包含的頁面可能不集與時間有關(guān)，即不同時間的工作集其所包含的頁面可能不同，其所包含的頁面?zhèn)€數(shù)也可能不同；同，其所包含的頁面?zhèn)€數(shù)也可能不同；其次工作集也是工作其次工作集也是工作集窗口尺寸集窗口尺寸w w的函數(shù)，體現(xiàn)在工作集尺寸的函數(shù)，體現(xiàn)在工作集尺寸|W(t,w)|W(t,w)|隨隨w w的增加的增加而變大，即滿足而變大，即滿足|W(t,w)|W(t,w+a)|W(t,w)|W(t,w+a)|，a0a0。&工作集窗口尺寸與缺頁率關(guān)系密切，工作集窗口尺寸與缺頁率關(guān)系密切，若若w w增大，工作集尺寸增大，工作集尺寸|W|W|隨之增加（即所含的頁面數(shù)增多），缺頁率就會下降。隨之增加（即所含的頁面

28、數(shù)增多），缺頁率就會下降。倘倘若若w w含蓋了整個作業(yè)虛擬空間，缺頁率降為含蓋了整個作業(yè)虛擬空間，缺頁率降為0 0，也就失去了虛，也就失去了虛存意義；存意義；反之若反之若w w選取過小，將引起頻繁缺頁，導(dǎo)致系統(tǒng)性能選取過小，將引起頻繁缺頁，導(dǎo)致系統(tǒng)性能下降。下降。二者之間的關(guān)系可以如圖所示。二者之間的關(guān)系可以如圖所示。&虛存中并不是要取消缺頁率，而是要使缺頁率維持在一個虛存中并不是要取消缺頁率，而是要使缺頁率維持在一個較低的水平上。因此可以取拐點(diǎn)所對應(yīng)的工作集尺寸作為較低的水平上。因此可以取拐點(diǎn)所對應(yīng)的工作集尺寸作為分給進(jìn)程的物理塊數(shù)，實(shí)驗(yàn)分析表明，這個數(shù)應(yīng)是進(jìn)程總分給進(jìn)程的物理塊數(shù)，

29、實(shí)驗(yàn)分析表明，這個數(shù)應(yīng)是進(jìn)程總頁面數(shù)的一半。頁面數(shù)的一半。即一個進(jìn)程應(yīng)獲得其所需頁數(shù)一半的空間即一個進(jìn)程應(yīng)獲得其所需頁數(shù)一半的空間時，再進(jìn)入內(nèi)存執(zhí)行時，再進(jìn)入內(nèi)存執(zhí)行。 缺 頁 率 f 拐 點(diǎn) 工 作 集 尺 寸 |W | 圖 3 25 缺 頁 率 與 工 作 集 尺 寸 之 間 的 關(guān) 系 4.4.頁面調(diào)入時機(jī)頁面調(diào)入時機(jī) & 預(yù)調(diào)頁策略預(yù)調(diào)頁策略 &也稱先行調(diào)度，即一頁面被訪問前就已經(jīng)預(yù)先置入也稱先行調(diào)度，即一頁面被訪問前就已經(jīng)預(yù)先置入內(nèi)存，以減少今后的缺頁率。內(nèi)存，以減少今后的缺頁率。&主要適于進(jìn)程的許多頁存放在外存的連續(xù)區(qū)域中的主要適于進(jìn)程的許多頁存放在外存的連

30、續(xù)區(qū)域中的情況。有的系統(tǒng)結(jié)合請求調(diào)入使用，即每次缺頁時情況。有的系統(tǒng)結(jié)合請求調(diào)入使用，即每次缺頁時裝入多個頁面。裝入多個頁面。&優(yōu)點(diǎn)：優(yōu)點(diǎn)：提高調(diào)頁的提高調(diào)頁的I/OI/O效率。效率。&缺點(diǎn)：缺點(diǎn)：基于預(yù)測，若調(diào)入的頁在以后很少被訪問，基于預(yù)測，若調(diào)入的頁在以后很少被訪問，則效率低。預(yù)調(diào)頁的成功率僅約則效率低。預(yù)調(diào)頁的成功率僅約50%50%，常用于程序裝，常用于程序裝入時的調(diào)頁。入時的調(diào)頁。& 請求調(diào)頁策略請求調(diào)頁策略&當(dāng)發(fā)生頁面故障時進(jìn)行調(diào)度，即當(dāng)進(jìn)程訪問不在當(dāng)發(fā)生頁面故障時進(jìn)行調(diào)度，即當(dāng)進(jìn)程訪問不在內(nèi)存的頁面引發(fā)缺頁中斷時，由系統(tǒng)根據(jù)這種訪內(nèi)存的頁面引發(fā)缺頁

31、中斷時，由系統(tǒng)根據(jù)這種訪問請求把所缺頁面裝入內(nèi)存。問請求把所缺頁面裝入內(nèi)存。&優(yōu)點(diǎn)：優(yōu)點(diǎn)：由請求調(diào)入策略裝入的頁一定會被訪問，由請求調(diào)入策略裝入的頁一定會被訪問，再加之比較容易實(shí)現(xiàn)，故在目前的虛擬存儲器中，再加之比較容易實(shí)現(xiàn)，故在目前的虛擬存儲器中，大多采用此策略。大多采用此策略。&缺點(diǎn)：缺點(diǎn)：每次僅調(diào)入一頁，增加了磁盤每次僅調(diào)入一頁，增加了磁盤I/OI/O的啟動的啟動頻率。頻率。&在請求分頁系統(tǒng)中，常把在請求分頁系統(tǒng)中，常把外存分為兩部分：一部分外存分為兩部分：一部分是文件區(qū)，用于存放文件；是文件區(qū)，用于存放文件；另一部分是對換區(qū)，用另一部分是對換區(qū)，用于存放對換頁面

32、。于存放對換頁面。通常，對換區(qū)的磁盤輸入輸出速通常，對換區(qū)的磁盤輸入輸出速度比文件區(qū)的高，這是因?yàn)閷Q區(qū)所規(guī)定的盤塊要度比文件區(qū)的高，這是因?yàn)閷Q區(qū)所規(guī)定的盤塊要比文件區(qū)的大得多。比文件區(qū)的大得多。& 從交換區(qū)調(diào)入從交換區(qū)調(diào)入&若系統(tǒng)擁有足夠的對換區(qū)空間，可在進(jìn)程運(yùn)行前，若系統(tǒng)擁有足夠的對換區(qū)空間，可在進(jìn)程運(yùn)行前，將與該進(jìn)程有關(guān)的文件拷貝到對換區(qū)。以后就從對將與該進(jìn)程有關(guān)的文件拷貝到對換區(qū)。以后就從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。 5.5.從何處調(diào)入頁面從何處調(diào)入頁面 & 從交換區(qū)及文件區(qū)調(diào)入從交換區(qū)及文件區(qū)調(diào)入&若系統(tǒng)缺少

33、足夠的對換區(qū)空間，則在交換區(qū)中只保存被修若系統(tǒng)缺少足夠的對換區(qū)空間，則在交換區(qū)中只保存被修改過的頁面。因?yàn)槲幢恍薷牡捻撁嬖谖募^(qū)中有副本。因改過的頁面。因?yàn)槲幢恍薷牡捻撁嬖谖募^(qū)中有副本。因此凡是沒被修改的頁，均從文件區(qū)調(diào)入；而已修改過的頁此凡是沒被修改的頁，均從文件區(qū)調(diào)入；而已修改過的頁面則從交換區(qū)調(diào)入。面則從交換區(qū)調(diào)入。& UNIX方式方式&與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁面，與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運(yùn)行過而又被換出的頁面，都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運(yùn)行過而又被換出的頁面，總是存放在對換區(qū)中。因此在下

34、次調(diào)入時，應(yīng)從對換區(qū)調(diào)總是存放在對換區(qū)中。因此在下次調(diào)入時，應(yīng)從對換區(qū)調(diào)入。由于在入。由于在UNIX系統(tǒng)中允許頁面共享，因此，某進(jìn)程所請系統(tǒng)中允許頁面共享，因此，某進(jìn)程所請求的頁面有可能已由其它進(jìn)程調(diào)入內(nèi)存，此時也就無須再求的頁面有可能已由其它進(jìn)程調(diào)入內(nèi)存，此時也就無須再從對換區(qū)調(diào)入。從對換區(qū)調(diào)入。&1.1.頁面置換方式頁面置換方式當(dāng)內(nèi)存空間已沒有空閑頁面而又要調(diào)入新頁時，必須當(dāng)內(nèi)存空間已沒有空閑頁面而又要調(diào)入新頁時，必須采用一定采用一定的算法在內(nèi)存中選擇某一頁面淘汰，所采用的算法稱之為頁的算法在內(nèi)存中選擇某一頁面淘汰，所采用的算法稱之為頁面置換算法。面置換算法。如果被淘汰的頁面在內(nèi)存

35、期間曾被修改過，還要將此頁重新寫如果被淘汰的頁面在內(nèi)存期間曾被修改過，還要將此頁重新寫回到外存，以便保留最新的副本。然后再換進(jìn)新的頁面?；氐酵獯妫员惚Ａ糇钚碌母北?。然后再換進(jìn)新的頁面。(1)頁面置換方式頁面置換方式頁面淘汰可以在整個內(nèi)存空間范圍內(nèi)進(jìn)行，稱之為全局置換。頁面淘汰可以在整個內(nèi)存空間范圍內(nèi)進(jìn)行，稱之為全局置換。也可以只在一個進(jìn)程空間范圍內(nèi)考慮，稱之為局部置換。也可以只在一個進(jìn)程空間范圍內(nèi)考慮，稱之為局部置換。即即當(dāng)某一進(jìn)程請求新頁時，而該進(jìn)程又沒有空閑塊，則只能淘當(dāng)某一進(jìn)程請求新頁時，而該進(jìn)程又沒有空閑塊，則只能淘汰自己的一個頁面而不能淘汰其它進(jìn)程的頁面。汰自己的一個頁面而不能淘汰

36、其它進(jìn)程的頁面。 4.6.3 4.6.3 頁面置換方法頁面置換方法& (2) (2) 空閑塊分配方式空閑塊分配方式&若為進(jìn)程分配固定的物理塊數(shù)，在其執(zhí)行期間再也不改變，若為進(jìn)程分配固定的物理塊數(shù)，在其執(zhí)行期間再也不改變，則稱為固定分配。則稱為固定分配。初始進(jìn)程塊數(shù)的多少難以確定。若太少，初始進(jìn)程塊數(shù)的多少難以確定。若太少，則缺頁頻繁，系統(tǒng)開銷大；若太多，則并發(fā)進(jìn)程數(shù)目少，則缺頁頻繁，系統(tǒng)開銷大；若太多，則并發(fā)進(jìn)程數(shù)目少，造成造成CPUCPU空閑或其它資源空閑的情況?？臻e或其它資源空閑的情況。&為進(jìn)程分配的物理塊數(shù)在其運(yùn)行期間是可變的，則稱為可為進(jìn)程分配的物理塊數(shù)在其運(yùn)行

37、期間是可變的，則稱為可變分配。變分配。進(jìn)程在運(yùn)行中，系統(tǒng)可調(diào)整為該進(jìn)程分配的物理進(jìn)程在運(yùn)行中，系統(tǒng)可調(diào)整為該進(jìn)程分配的物理塊，直至進(jìn)程的缺頁率達(dá)到適當(dāng)程度。塊，直至進(jìn)程的缺頁率達(dá)到適當(dāng)程度。在頁面置換算法討論中，為了比較各種方法的在頁面置換算法討論中，為了比較各種方法的優(yōu)劣，總是限定為固定分配局部置換。優(yōu)劣，總是限定為固定分配局部置換。固定分配局部置換：固定分配局部置換：固定分配全局置換：固定分配全局置換：可變分配局部置換可變分配局部置換可變分配全局置換可變分配全局置換(3) 內(nèi)存管理策略內(nèi)存管理策略不可能不可能&(1)(1)最佳淘汰算法最佳淘汰算法OPT(Optimal)OPT(Op

38、timal)&這是Belady于1966年提出的一種理論上的算法。該算法每次都淘汰以后永不使用的，或者過最長的時間后才會被訪問的頁面。&顯然，采用這種算法會保證最低的缺頁率，但它是無法實(shí)現(xiàn)的，因?yàn)樗仨氈理撁妗皩怼钡脑L問情況。不過，該算法仍有一定意義，可作為衡量其他算法優(yōu)劣的一個標(biāo)準(zhǔn)。 2.2.頁面置換算法頁面置換算法 假定系統(tǒng)為某個進(jìn)程分配了三個物理塊，進(jìn)程的訪問順假定系統(tǒng)為某個進(jìn)程分配了三個物理塊，進(jìn)程的訪問順序?yàn)樾驗(yàn)? 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2OPTOPT置換算法示例：置換算法示

39、例：7，0，1， 2，0，3，0，4，2， 3，0 ，3， 2，1， 27 *7 0 *7 0 1 *2 0 1 *2 0 12 0 3 *2 0 32 4 3 *2 4 32 4 32 0 3 *2 0 32 0 32 1 3 *2 1 3缺頁次數(shù)缺頁次數(shù)8 8，成功訪問次數(shù)，成功訪問次數(shù)7 7次，次，缺頁率缺頁率f=8/15=53.33%f=8/15=53.33%（2 2）先進(jìn)先出淘汰算法）先進(jìn)先出淘汰算法FIFOFIFO&這是最早出現(xiàn)的淘汰算法。&總是淘汰最先進(jìn)入內(nèi)存的頁面?？偸翘蕴钕冗M(jìn)入內(nèi)存的頁面。它實(shí)現(xiàn)簡單實(shí)現(xiàn)簡單，只需把進(jìn)程中已調(diào)入內(nèi)存的頁面，按先后次序鏈成一個隊(duì)

40、列，并設(shè)置一個所謂的替換指針，使它總是指向內(nèi)存中最老的頁面。&缺點(diǎn)：效率不高，缺點(diǎn)：效率不高，因?yàn)樗c進(jìn)程實(shí)際的運(yùn)行規(guī)律不相適應(yīng)，比如常用的全局變量所在的頁面或者循環(huán)體所在頁面都可能被它選為淘汰對象。出現(xiàn)bleady現(xiàn)象。 &BeladyBelady現(xiàn)象：現(xiàn)象：采用FIFO算法時，如果對一個進(jìn)程未分配它所要求的全部頁面，有時就會出現(xiàn)分配的頁面數(shù)增多，缺頁率反而提高的異?，F(xiàn)象。&BeladyBelady現(xiàn)象的描述：現(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)時而增大，時而減小

41、。&BeladyBelady現(xiàn)象的原因：現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動態(tài)特征是矛盾的，即被置換的頁面并不是進(jìn)程不會訪問的。FIFOFIFO淘汰算法示例：淘汰算法示例：7，0，1， 2，0，3，0，4， 2， 3，0 ，3， 2，1， 27 *7 0 *7 0 1 *2 0 1 *2 0 12 3 1 *2 3 0 *4 3 0 *4 2 0 *4 2 3 *0 2 3 *0 2 30 2 30 1 3 *0 1 2 *3 3塊內(nèi)存時，缺頁率塊內(nèi)存時，缺頁率f=12/15=80%f=12/15=80%；4 4塊塊f=8/15=53.33%f=8/15=53.33%7

42、，0，1， 2，0，3，0，4， 2， 3，0 ，3， 2，1， 27 *7 0 *7 0 1 *7 0 1 2 *7 0 1 23 0 1 2 *3 0 1 2 3 4 1 2 *3 4 1 2 3 4 1 2 3 4 0 2 *3 4 0 23 4 0 23 4 0 1 *2 4 0 1 *(3)(3)最近最久未使用算法最近最久未使用算法(LRU, (LRU, Least Recently UsedLeast Recently Used） 根據(jù)頁面調(diào)入內(nèi)存后的使用情況，選擇內(nèi)存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。 OPT算法使用頁面將要被訪問的時間，LRU

43、算法使用頁面最后一次被訪問的時間。二者唯一的差別是：OPT是向前看的，而LRU是向后看的。 7，0，1， 2，0，3，0，4， 2， 3，0 ，3， 2，1， 27 *7 0 *7 0 1 *2 0 1 *2 0 12 0 3 *2 0 34 0 3 *4 0 2 *4 3 2 *0 3 2 *0 3 20 3 21 3 2 *1 3 2 10次，缺頁率次，缺頁率f=10/15=66.67%LRULRU的兩個實(shí)現(xiàn)算法：的兩個實(shí)現(xiàn)算法： &計(jì)時法：計(jì)時法：對于每一頁面增設(shè)一個訪問時間計(jì)時器，每當(dāng)一個頁面被訪問時，就將當(dāng)時的絕對時鐘拷貝到對應(yīng)的訪問時間計(jì)時器中，這樣系統(tǒng)記錄了內(nèi)存中所有頁面

44、最后一次被訪問的時間。淘汰時，選取訪問時間計(jì)時器的值最小的頁面。&堆棧法：堆棧法：每當(dāng)進(jìn)程訪問某頁面時，便將該頁面的頁號從棧中移出，將它壓入棧頂。棧頂始終是最新被訪問的頁面的編號。棧底則是最近最久未被使用的頁面的頁面號。 假定現(xiàn)有一進(jìn)程所訪問的頁面的頁面號序列為：假定現(xiàn)有一進(jìn)程所訪問的頁面的頁面號序列為：4 4，8 8，0 0，8 8，1 1，0 0，2 2，1 1，2 2，6 6&隨著進(jìn)程的訪問，棧中頁面號的變化情況隨著進(jìn)程的訪問，棧中頁面號的變化情況：4，8，0，8，1，0，1，2，1，2，6 2 1 2 6 1 0 1 1 2 1 2 0 8 8 1 0 0 0 0 1

45、8 8 0 0 8 8 8 8 8 0 4 4 4 4 4 4 4 4 4 4 8LRULRU的開銷是很大的，必須有硬件的支持，完全由軟件實(shí)的開銷是很大的，必須有硬件的支持，完全由軟件實(shí)現(xiàn)其速度至少會減少現(xiàn)其速度至少會減少1010倍，因此倍，因此LRULRU近似算法更實(shí)用些。近似算法更實(shí)用些。 &這是一種LRU的近似算法，是通過對FIFO算法進(jìn)行簡單改造，結(jié)合頁表中的訪問位而得來一種淘汰算法。&該算法首先檢查位于FIFO鏈鏈?zhǔn)椎捻?，如果它的訪問位為0，則選擇該頁淘汰；如果它的訪問位為1，則清除其訪問位，將它移至FIFO鏈的鏈尾，重復(fù)此算法的查找過程，直至遇到新鏈?zhǔn)醉撌且粋€訪問位

46、為0的較早進(jìn)入內(nèi)存的頁為止，把它選為被淘汰的頁。 (4)(4)二次機(jī)會淘汰算法二次機(jī)會淘汰算法SC(Second Chance)SC(Second Chance)（5 5）時鐘）時鐘(Clock)(Clock)淘汰算法淘汰算法 &該算法首先檢測指針?biāo)傅捻撁妫绻脑L問位為0，則淘汰該頁，新裝入的頁插入到此位置，然后指針前進(jìn)一個位置；如果它的訪問位為1，則清除為0，并將指針前進(jìn)一個位置，繼續(xù)檢查訪問位。重復(fù)此過程，直到找到訪問位為0的頁面為止。 &缺點(diǎn)：就是需要把訪問位為1的處于鏈?zhǔn)椎捻撘浦伶溛?，這需要一定的開銷。一種改進(jìn)的方法就是把進(jìn)程所訪問的頁面鏈成一個環(huán)形鏈表，再設(shè)一個

47、指針指向最老的頁面，于是形成了一種簡單實(shí)用的LRU近似算法時鐘淘汰算法。(6)(6)最近未用淘汰算法最近未用淘汰算法NUR(NUR(Not Used RecentlyNot Used Recently) ) &它把FIFO算法的思想與頁面的訪問位和修改位結(jié)合起來確定一個接近LRU算法的淘汰對象。&該算法每次都盡量選擇最近最久未被寫過的頁面淘汰，這種干凈的頁面可以不被寫回到磁盤。在實(shí)現(xiàn)時，為每一個頁面設(shè)置初始值為0的訪問位和修改位。當(dāng)對某頁面執(zhí)行寫操作時，其修改位和訪問位均由硬件置成1；當(dāng)對某頁面執(zhí)行讀操作時，只有其訪問位被硬件置成1。系統(tǒng)每隔固定時間將所有訪問位都清0。按照下列

48、次序選擇被淘汰的頁面：按照下列次序選擇被淘汰的頁面：&訪問位，修改位；直接淘汰； &訪問位，修改位；淘汰后寫回；&訪問位，修改位；直接淘汰；&訪問位，修改位；寫回外存后淘汰； 最近未使用淘汰算法就是最近未使用淘汰算法就是LRULRU的一種近似算法，它總是淘汰最近的一種近似算法，它總是淘汰最近未使用的頁，如果被淘汰的頁在內(nèi)存期間沒有被修改過，該頁未使用的頁，如果被淘汰的頁在內(nèi)存期間沒有被修改過，該頁可不必重新寫入外存，將新頁覆蓋到被淘汰的頁上即可。可不必重新寫入外存，將新頁覆蓋到被淘汰的頁上即可。訪問位訪問位A A0 0 表示該頁未被訪問過；表示該頁未被訪問過；

49、1 1 表示該頁已被訪問過；表示該頁已被訪問過；修改位修改位M M 0 0 表示該頁未被修改過表示該頁未被修改過 1 1 表示該頁已被修改過表示該頁已被修改過(1)(1)分配給作業(yè)的內(nèi)存塊數(shù)分配給作業(yè)的內(nèi)存塊數(shù) &作業(yè)的缺頁中斷率與作業(yè)所占內(nèi)存塊數(shù)成反比。分配給作業(yè)的內(nèi)存塊數(shù)太少是導(dǎo)致抖動現(xiàn)象發(fā)生的最主要的原因，實(shí)驗(yàn)分析表明：對所有的程序來說，要使其有效地工作，它在內(nèi)存中的頁面數(shù)不應(yīng)少于它的總頁面數(shù)的一半。 3.3.影響缺頁中斷率的因素影響缺頁中斷率的因素 (2)(2)頁面大小的選擇頁面大小的選擇&雖然缺頁中斷率與頁面尺寸成反比，但頁面尺寸卻不能一味地求大，它一般在0.5KB4

50、KB之間，是個實(shí)驗(yàn)統(tǒng)計(jì)值。因?yàn)轫撁娲髸r，頁表較小，占空間少，查表速度快，缺頁中斷次數(shù)少，但頁面調(diào)度時間長，頁內(nèi)碎片較大。頁面小時，恰恰相反。 (3)(3)用戶程序編制的方法用戶程序編制的方法 作業(yè)的缺頁中斷率與程序的局部化（包括時間局部作業(yè)的缺頁中斷率與程序的局部化（包括時間局部化和空間局部化）程度成反比。用戶程序編制的方化和空間局部化）程度成反比。用戶程序編制的方法不合適可能導(dǎo)致程序運(yùn)行的時空復(fù)雜度高，缺頁法不合適可能導(dǎo)致程序運(yùn)行的時空復(fù)雜度高，缺頁次數(shù)多。次數(shù)多。 &(4)(4)頁面調(diào)度算法頁面調(diào)度算法 &抖動又叫顛簸，是指一段時間里，頁面在內(nèi)存與外存之間頻繁地調(diào)度或換入換

51、出，以至于系統(tǒng)用于調(diào)度頁面所需要的時間比進(jìn)程實(shí)際運(yùn)行所占用的時間還要多。&好的淘汰算法會維持一個較低的缺頁率。若頁面置換算法不好，會使系統(tǒng)出現(xiàn)抖動現(xiàn)象。 &顯然，抖動是由于缺頁中斷率很高而引起的一種壞現(xiàn)象，它將嚴(yán)重影響系統(tǒng)的效率，甚至可能使系統(tǒng)全面崩潰。 防止抖動現(xiàn)象的產(chǎn)生和擴(kuò)展，具體方法防止抖動現(xiàn)象的產(chǎn)生和擴(kuò)展，具體方法:&采取局部置換策略采取局部置換策略&這樣，即使有某個進(jìn)程發(fā)生了這樣，即使有某個進(jìn)程發(fā)生了“抖動抖動”，也不致引起其它進(jìn)，也不致引起其它進(jìn)程也產(chǎn)生抖動，從而把抖動局限于較小的范圍內(nèi)。程也產(chǎn)生抖動，從而把抖動局限于較小的范圍內(nèi)。&這種方法

52、并不很好，因?yàn)樗荒軓母旧戏乐苟秳拥陌l(fā)生；這種方法并不很好，因?yàn)樗荒軓母旧戏乐苟秳拥陌l(fā)生；而且在某進(jìn)程發(fā)生抖動后，還會長期地處于磁盤輸入輸出的而且在某進(jìn)程發(fā)生抖動后，還會長期地處于磁盤輸入輸出的等待隊(duì)列中，這又會使其它進(jìn)程缺頁中斷的處理時間增長，等待隊(duì)列中，這又會使其它進(jìn)程缺頁中斷的處理時間增長，從而延長了等效的訪問時間。從而延長了等效的訪問時間。& L=S準(zhǔn)則準(zhǔn)則&Denning于于1980年提出了年提出了“L=S準(zhǔn)則準(zhǔn)則”，用來調(diào)整多道程，用來調(diào)整多道程序度，以使產(chǎn)生缺頁的平均時間序度，以使產(chǎn)生缺頁的平均時間L等于系統(tǒng)處理進(jìn)程缺頁的平等于系統(tǒng)處理進(jìn)程缺頁的平均時間均時

53、間S。理論和實(shí)踐表明，此時的。理論和實(shí)踐表明，此時的CPU利用得最好。該準(zhǔn)利用得最好。該準(zhǔn)則也得到其它研究人員的證實(shí)。則也得到其它研究人員的證實(shí)。防止抖動現(xiàn)象的產(chǎn)生和擴(kuò)展，具體方法防止抖動現(xiàn)象的產(chǎn)生和擴(kuò)展，具體方法:&掛起若干進(jìn)程掛起若干進(jìn)程&當(dāng)多道程序度偏高時，為了防止發(fā)生當(dāng)多道程序度偏高時，為了防止發(fā)生“抖抖動動”，可用的一個簡單易行的辦法是掛起一可用的一個簡單易行的辦法是掛起一些進(jìn)程，以便騰出內(nèi)存空間來分配給抖動的些進(jìn)程，以便騰出內(nèi)存空間來分配給抖動的進(jìn)程。進(jìn)程。被掛起的進(jìn)程通常是選擇優(yōu)先權(quán)最低被掛起的進(jìn)程通常是選擇優(yōu)先權(quán)最低或較低的；當(dāng)內(nèi)存非常擁擠時，也可以選擇或較低的

54、；當(dāng)內(nèi)存非常擁擠時，也可以選擇一個并不很重要的、但確較大的進(jìn)程掛起，一個并不很重要的、但確較大的進(jìn)程掛起，以便能一次釋放出較大的內(nèi)存空間；或者是以便能一次釋放出較大的內(nèi)存空間；或者是將具有最多剩余執(zhí)行時間的進(jìn)程掛起。將具有最多剩余執(zhí)行時間的進(jìn)程掛起。 4.6.4 4.6.4 虛擬頁式存儲的優(yōu)缺點(diǎn)虛擬頁式存儲的優(yōu)缺點(diǎn)&1.1.優(yōu)點(diǎn)優(yōu)點(diǎn)& 主存利用率比較高。主存利用率比較高。平均每個用戶作業(yè)只浪費(fèi)一平均每個用戶作業(yè)只浪費(fèi)一半的頁空間，內(nèi)存規(guī)范易于管理。半的頁空間，內(nèi)存規(guī)范易于管理。& 對磁盤管理比較容易。對磁盤管理比較容易。因?yàn)轫摰拇笮∫话闳〈疟P因?yàn)轫摰拇笮∫话闳〈疟P物理塊

55、大小的整數(shù)倍。物理塊大小的整數(shù)倍。& 地址映射和變換的速度比較快。地址映射和變換的速度比較快。在把用戶程序裝在把用戶程序裝入到主存儲器的過程中，只要建立用戶程序的虛頁入到主存儲器的過程中，只要建立用戶程序的虛頁號與主存儲器的實(shí)頁號之間的對應(yīng)關(guān)系即可（拼接號與主存儲器的實(shí)頁號之間的對應(yīng)關(guān)系即可（拼接得到物理地址），不必使用整個主存的地址長度，得到物理地址），不必使用整個主存的地址長度，也不必考慮每頁的長度等。也不必考慮每頁的長度等。& 2. 2.缺點(diǎn)缺點(diǎn)& 程序的模塊化性能不好程序的模塊化性能不好。&由于用戶程序是強(qiáng)制按照固定大小的頁來劃分的，而程序段由于用戶程序

56、是強(qiáng)制按照固定大小的頁來劃分的，而程序段的實(shí)際長度一般是不固定的。因此，虛擬頁式存儲器中一頁的實(shí)際長度一般是不固定的。因此，虛擬頁式存儲器中一頁通常不能表示一個完整的程序功能。一頁可能只是一個程序通常不能表示一個完整的程序功能。一頁可能只是一個程序段中的一部分，也可能在一頁中包含了兩個或兩個以上程序段中的一部分，也可能在一頁中包含了兩個或兩個以上程序段。段。& 頁表很長，需要占用很大的存儲空間。頁表很長，需要占用很大的存儲空間。&通常，虛擬存儲器中的每一頁在頁表中都要占一個頁表項(xiàng)。通常，虛擬存儲器中的每一頁在頁表中都要占一個頁表項(xiàng)。假設(shè)有一個虛擬頁式存儲器，它的虛擬存儲空間大小

57、為假設(shè)有一個虛擬頁式存儲器，它的虛擬存儲空間大小為4GB，每一頁的大小為每一頁的大小為1KB，則頁表的容量為，則頁表的容量為4M（個頁表項(xiàng)）。如（個頁表項(xiàng)）。如果每個頁表項(xiàng)占用果每個頁表項(xiàng)占用4個字節(jié)，則頁表的存儲容量為個字節(jié)，則頁表的存儲容量為16MB。4.7 4.7 虛擬段式存儲管理虛擬段式存儲管理4.7.1 4.7.1 虛擬段式存儲的實(shí)現(xiàn)虛擬段式存儲的實(shí)現(xiàn) 4.7.2 4.7.2 段的共享和保護(hù)段的共享和保護(hù) 4.7.34.7.3虛擬段式存儲管理的優(yōu)缺點(diǎn)虛擬段式存儲管理的優(yōu)缺點(diǎn)4.7.4 4.7.4 虛擬段頁式存儲管理虛擬段頁式存儲管理 4.7.1 4.7.1 虛擬段式存儲的實(shí)現(xiàn)虛擬段式

58、存儲的實(shí)現(xiàn)&1.1.虛擬段式存儲原理虛擬段式存儲原理&為了能實(shí)現(xiàn)虛擬存儲，段式邏輯地址空間中為了能實(shí)現(xiàn)虛擬存儲，段式邏輯地址空間中的程序段在運(yùn)行時并不全部裝入內(nèi)存，而是的程序段在運(yùn)行時并不全部裝入內(nèi)存，而是如同請求式分頁存儲管理，首先調(diào)入一個或如同請求式分頁存儲管理，首先調(diào)入一個或若干個程序段運(yùn)行，在運(yùn)行過程中調(diào)用到哪若干個程序段運(yùn)行，在運(yùn)行過程中調(diào)用到哪段時，就根據(jù)該段長度在內(nèi)存分配一個連續(xù)段時，就根據(jù)該段長度在內(nèi)存分配一個連續(xù)的分區(qū)給它使用。若內(nèi)存中沒有足夠大的空的分區(qū)給它使用。若內(nèi)存中沒有足夠大的空閑分區(qū)，則考慮進(jìn)行段的緊湊或?qū)⒛扯位蚰抽e分區(qū)，則考慮進(jìn)行段的緊湊或?qū)⒛扯位?/p>

59、某些段淘汰出去。相應(yīng)于請求式分頁存儲管理，些段淘汰出去。相應(yīng)于請求式分頁存儲管理，這種存儲管理技術(shù)稱為請求式分段存儲管理。這種存儲管理技術(shù)稱為請求式分段存儲管理。2.2.段表段表 &類似于請求式分頁存儲管理的頁表，為了實(shí)現(xiàn)動態(tài)地址變類似于請求式分頁存儲管理的頁表，為了實(shí)現(xiàn)動態(tài)地址變換和存儲保護(hù)，系統(tǒng)要為每一個作業(yè)建立一張段表。段表換和存儲保護(hù)，系統(tǒng)要為每一個作業(yè)建立一張段表。段表中的每一個表目對應(yīng)著作業(yè)地址空間的一個程序段，其一中的每一個表目對應(yīng)著作業(yè)地址空間的一個程序段，其一般格式為：般格式為： 邏輯地址同前：邏輯地址同前：段段號號存在存在位位P P訪問訪問位位A A修改修改位位M

60、M存取存取方式方式增補(bǔ)增補(bǔ)位位段段長度長度段的段的基址基址外存外存地址地址存在位存在位P P表示該段是否在內(nèi)存，如為表示該段是否在內(nèi)存，如為0 0表示不在，為表示不在，為1 1表示在內(nèi)存；表示在內(nèi)存；存取方式表示可對該段施加的操作，如只讀、讀寫、還是執(zhí)行。存取方式表示可對該段施加的操作，如只讀、讀寫、還是執(zhí)行。增補(bǔ)位表示該段在運(yùn)行期間是否可以擴(kuò)展空間增補(bǔ)位表示該段在運(yùn)行期間是否可以擴(kuò)展空間 3.3.請求式分段動態(tài)地址變換過程請求式分段動態(tài)地址變換過程 4.4.缺段中斷缺段中斷&在虛擬段式存儲系統(tǒng)中，采用的是請求調(diào)段策略。即每當(dāng)進(jìn)在虛擬段式存儲系統(tǒng)中，采用的是請求調(diào)段策略。即每當(dāng)進(jìn)程所要

61、訪問的段尚未調(diào)入內(nèi)存時，便由缺段中斷機(jī)構(gòu)產(chǎn)生一程所要訪問的段尚未調(diào)入內(nèi)存時，便由缺段中斷機(jī)構(gòu)產(chǎn)生一缺段中斷信號，進(jìn)入缺段中斷信號，進(jìn)入OS后由缺斷中斷處理程序?qū)⑺璧亩握{(diào)后由缺斷中斷處理程序?qū)⑺璧亩握{(diào)入內(nèi)存。入內(nèi)存。&再調(diào)入新段時，也會有內(nèi)存空間不夠用的情況，也需要淘汰再調(diào)入新段時，也會有內(nèi)存空間不夠用的情況，也需要淘汰內(nèi)存中的一個或多個段。如果此程序段從裝入內(nèi)存起一直沒內(nèi)存中的一個或多個段。如果此程序段從裝入內(nèi)存起一直沒有被修改過，只要用新調(diào)入的程序段把它覆蓋掉即可。若這有被修改過，只要用新調(diào)入的程序段把它覆蓋掉即可。若這個程序段被修改過，則必須先把該程序段全部寫回到磁盤存?zhèn)€程序段被修改過，則必須先把該程序段全部寫回到磁盤存儲器中，才能占用被淘汰段原來存放的空間。儲器中，才能占用被淘汰段原來存放的空間。&因?yàn)槎我加眠B續(xù)的空間，因此當(dāng)內(nèi)存中沒有能夠滿足段長因?yàn)槎我加眠B續(xù)的空間，因此當(dāng)內(nèi)存中沒有能夠滿足段長需要的空閑區(qū)時，系統(tǒng)還要合并空閑區(qū)，以便滿足分段的需需要的空閑區(qū)時，系