1、第五章第五章 虛擬存儲器虛擬存儲器5.1 5.1 虛擬存儲器概述虛擬存儲器概述5.2 5.2 請求分頁存儲管理方式請求分頁存儲管理方式5.3 5.3 頁面置換算法頁面置換算法5.4 5.4 請求分段存儲管理方式請求分段存儲管理方式5.1 5.1 虛擬存儲器概述虛擬存儲器概述q常規(guī)存儲管理方式的共同點常規(guī)存儲管理方式的共同點： 要求一個作業(yè)全部裝入內(nèi)存后方能運行。要求一個作業(yè)全部裝入內(nèi)存后方能運行。q問題：問題： (1) (1) 有的作業(yè)很大有的作業(yè)很大, ,所需內(nèi)存空間大于內(nèi)存總?cè)萘克鑳?nèi)存空間大于內(nèi)存總?cè)萘? ,使作業(yè)無法使作業(yè)無法運行。運行。 (2) (2) 有大量作業(yè)要求運行，但內(nèi)存容量

2、不足以容納下所有作業(yè)，有大量作業(yè)要求運行，但內(nèi)存容量不足以容納下所有作業(yè)，只能讓一部分先運行，其它在外存等待。只能讓一部分先運行，其它在外存等待。q解決方法解決方法 （1 1）增加內(nèi)存容量。）增加內(nèi)存容量。 （2 2）從邏輯上擴充內(nèi)存容量）從邏輯上擴充內(nèi)存容量 -虛擬存儲器虛擬存儲器( (對換對換) )一、虛擬存儲器的引入一、虛擬存儲器的引入v 常規(guī)存儲器管理方式的特征常規(guī)存儲器管理方式的特征 （1 1）一次性：）一次性：作業(yè)在運行前需一次性地作業(yè)在運行前需一次性地全部裝入全部裝入內(nèi)存。將導致上述兩問題。內(nèi)存。將導致上述兩問題。 （2 2）駐留性：）駐留性：作業(yè)作業(yè)裝入內(nèi)存后，便一直駐留內(nèi)存，

3、直至作業(yè)運行結(jié)束。裝入內(nèi)存后，便一直駐留內(nèi)存，直至作業(yè)運行結(jié)束。v 局部性原理局部性原理- -虛擬存儲器實現(xiàn)的理論依據(jù)虛擬存儲器實現(xiàn)的理論依據(jù) 指程序在執(zhí)行時呈現(xiàn)出指程序在執(zhí)行時呈現(xiàn)出局部性規(guī)律局部性規(guī)律，即在一較短時間內(nèi)，程序的執(zhí)行僅限即在一較短時間內(nèi)，程序的執(zhí)行僅限于某個部分，相應地，它所訪問的存儲空間也局限于某個區(qū)域。于某個部分，相應地，它所訪問的存儲空間也局限于某個區(qū)域。 局部性又表現(xiàn)為局部性又表現(xiàn)為時間局部性時間局部性( (由于大量的循環(huán)操作，某指令或數(shù)據(jù)被訪問由于大量的循環(huán)操作，某指令或數(shù)據(jù)被訪問后，則不久可能會被再次訪問后，則不久可能會被再次訪問) )和和空間局部性空間局部性（如

4、順序執(zhí)行，指程序在一段時（如順序執(zhí)行，指程序在一段時間內(nèi)訪問的地址，可能集中在一定的范圍之內(nèi)）。間內(nèi)訪問的地址，可能集中在一定的范圍之內(nèi)）。虛擬存儲器的概念虛擬存儲器的概念u 基于局部性原理，程序在運行之前，基于局部性原理，程序在運行之前，沒有必要沒有必要全部裝入內(nèi)存，僅須將當前要全部裝入內(nèi)存，僅須將當前要運行的頁（段）裝入內(nèi)存即可。運行的頁（段）裝入內(nèi)存即可。u 運行時，如訪問的頁（段）在內(nèi)存中，則繼續(xù)執(zhí)行，如訪問的頁未在內(nèi)存中運行時，如訪問的頁（段）在內(nèi)存中，則繼續(xù)執(zhí)行，如訪問的頁未在內(nèi)存中（缺頁或缺段），則利用（缺頁或缺段），則利用OSOS的的請求調(diào)頁（段）功能請求調(diào)頁（段）功能，將該頁

5、（段）調(diào)入內(nèi)存。，將該頁（段）調(diào)入內(nèi)存。 u 如內(nèi)存已滿，則利用如內(nèi)存已滿，則利用OSOS的的頁（段）置換頁（段）置換功能，按某種置換算法將內(nèi)存中的某功能，按某種置換算法將內(nèi)存中的某頁（段）調(diào)至外存，從而調(diào)入需訪問的頁。頁（段）調(diào)至外存，從而調(diào)入需訪問的頁。 虛擬存儲器虛擬存儲器是指僅把作業(yè)的一部分裝入內(nèi)存便可運行作業(yè)的存儲管理是指僅把作業(yè)的一部分裝入內(nèi)存便可運行作業(yè)的存儲管理系統(tǒng)，它具有系統(tǒng)，它具有請求頁請求頁( (段段) )調(diào)入功能調(diào)入功能和和頁（段）置換功能頁（段）置換功能，能從邏輯上對，能從邏輯上對內(nèi)存容量進行擴充，其邏輯容量由外存容量和內(nèi)存容量之和決定，其內(nèi)存容量進行擴充，其邏輯容量

6、由外存容量和內(nèi)存容量之和決定，其運行速運行速度度接近于內(nèi)存，接近于內(nèi)存，成本成本接近于外存。接近于外存。二、虛擬存儲器的實現(xiàn)方法二、虛擬存儲器的實現(xiàn)方法1 1、分頁請求系統(tǒng)、分頁請求系統(tǒng) 在分頁系統(tǒng)的基礎上，增加了在分頁系統(tǒng)的基礎上，增加了請求調(diào)頁功能請求調(diào)頁功能、頁面置換功能頁面置換功能所形成的頁式虛擬存儲器系統(tǒng)。所形成的頁式虛擬存儲器系統(tǒng)。 它允許只裝入若干頁的它允許只裝入若干頁的用戶程序和數(shù)據(jù)用戶程序和數(shù)據(jù)，便可啟動運行，便可啟動運行，以后再以后再硬件支持下硬件支持下通過調(diào)頁功能和置換頁功能，陸續(xù)將要運行的通過調(diào)頁功能和置換頁功能，陸續(xù)將要運行的頁面調(diào)入內(nèi)存，同時把暫不運行的頁面換到外存

7、上，頁面調(diào)入內(nèi)存，同時把暫不運行的頁面換到外存上，置換時以頁置換時以頁面為單位面為單位。 二、虛擬存儲器的實現(xiàn)方法二、虛擬存儲器的實現(xiàn)方法 2 2、分段請求系統(tǒng)、分段請求系統(tǒng) 在分段系統(tǒng)的基礎上，增加了在分段系統(tǒng)的基礎上，增加了請求調(diào)段功能請求調(diào)段功能及及分段置換分段置換功能，所形成的段式虛擬存儲器系統(tǒng)。功能，所形成的段式虛擬存儲器系統(tǒng)。 它允許只裝入若干段的它允許只裝入若干段的用戶程序和數(shù)據(jù)用戶程序和數(shù)據(jù)，便可啟動運行，便可啟動運行，以后再以后再硬件支持下硬件支持下通過通過請求調(diào)段請求調(diào)段功能和功能和分段置換分段置換功能，陸續(xù)功能，陸續(xù)將要運行的段調(diào)入內(nèi)存，同時把暫不運行的段換到外存上，將要

8、運行的段調(diào)入內(nèi)存，同時把暫不運行的段換到外存上，置換時以段為單位置換時以段為單位。 三、虛擬存儲器的特征三、虛擬存儲器的特征1 1、多次性（最基本特征）、多次性（最基本特征） 多次次是虛擬存儲器多次次是虛擬存儲器最重要最重要的特征。指一個作業(yè)被分成多次調(diào)入內(nèi)存運的特征。指一個作業(yè)被分成多次調(diào)入內(nèi)存運行。行。2 2、對換性、對換性 對換性指允許在作業(yè)運行過程中進行換進、換出。換進、換出可提高內(nèi)存對換性指允許在作業(yè)運行過程中進行換進、換出。換進、換出可提高內(nèi)存利用率。利用率。3 3、虛擬性、虛擬性( (最本質(zhì)特征最本質(zhì)特征) ) 虛擬性虛擬性是指能夠從邏輯上擴充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠大

9、于是指能夠從邏輯上擴充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠大于實際內(nèi)存容量。虛擬性是虛擬存儲器所表現(xiàn)出來的重要的特征，也是實現(xiàn)虛擬實際內(nèi)存容量。虛擬性是虛擬存儲器所表現(xiàn)出來的重要的特征，也是實現(xiàn)虛擬存儲器最重要的目標。存儲器最重要的目標。 注注：虛擬性以多次性和對換性為基礎，而多次性和對換性又是虛擬性以多次性和對換性為基礎，而多次性和對換性又是離散離散分配分配為基礎。為基礎。5.2 5.2 請求分頁存儲管理方式請求分頁存儲管理方式v 虛擬存儲器的實現(xiàn)方式虛擬存儲器的實現(xiàn)方式v原理原理地址空間的劃分同基本分頁式；地址空間的劃分同基本分頁式；裝入頁時，可裝入裝入頁時，可裝入作業(yè)的一部分作業(yè)的一部分(

10、 (運行所需運行所需) )頁即可運行。頁即可運行。n請求分頁中的硬件支持請求分頁中的硬件支持分頁請求系統(tǒng)分頁請求系統(tǒng)分段請求系統(tǒng)分段請求系統(tǒng)基本單位基本單位頁頁段段長度長度固定固定可變可變 分配方式分配方式固定分配固定分配動態(tài)動態(tài)復雜性復雜性簡單簡單較復雜較復雜一、請求分頁中的一、請求分頁中的硬件支持硬件支持1 1、頁表機制、頁表機制( (擴充擴充) ) （1 1）狀態(tài)位）狀態(tài)位P(P(存在位存在位) )：指示該頁是否已調(diào)入內(nèi)存。判斷是否缺頁。指示該頁是否已調(diào)入內(nèi)存。判斷是否缺頁。 （2 2）訪問字段）訪問字段A A：記錄本頁在一段時間內(nèi)被訪問的次數(shù)或最近未被記錄本頁在一段時間內(nèi)被訪問的次數(shù)或

11、最近未被訪問的時間。訪問的時間。根據(jù)訪問位來決定淘汰哪頁。根據(jù)訪問位來決定淘汰哪頁。 （3 3）修改位）修改位M M：表示該頁在調(diào)入內(nèi)存后是否被修改過。若修改過，則表示該頁在調(diào)入內(nèi)存后是否被修改過。若修改過，則換出時需重寫至外存。換出時需重寫至外存。供置換頁面時參考。供置換頁面時參考。 （4 4）外存地址）外存地址：指出該頁在外存上的地址。指出該頁在外存上的地址。頁號頁號塊號塊號狀態(tài)位狀態(tài)位訪問字段訪問字段修改位修改位外存地址外存地址一、請求分頁中的一、請求分頁中的硬件支持硬件支持2 2、缺頁中斷機構、缺頁中斷機構 在請求分頁系統(tǒng)中，當訪問的頁不在內(nèi)存，在請求分頁系統(tǒng)中，當訪問的頁不在內(nèi)存，便

12、產(chǎn)生一便產(chǎn)生一缺頁中斷缺頁中斷，請求，請求OSOS將所缺頁調(diào)入內(nèi)存將所缺頁調(diào)入內(nèi)存空閑塊，若無空閑塊，則需置換某一頁，同時空閑塊，若無空閑塊，則需置換某一頁，同時修改相應頁表表目。修改相應頁表表目。 缺頁中斷與一般中斷的區(qū)別：缺頁中斷與一般中斷的區(qū)別：（1 1）在指令執(zhí)行期間產(chǎn)生和處理中斷信）在指令執(zhí)行期間產(chǎn)生和處理中斷信號。號。缺頁中斷要立即處理。缺頁中斷要立即處理。 （2 2）一條指令在執(zhí)行期間，可能產(chǎn)生多）一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。次缺頁中斷。圖圖4-24 涉及涉及6次缺頁中斷的指令次缺頁中斷的指令 頁面B：A：654321指令COPY ATO B數(shù)據(jù)跨越兩頁數(shù)據(jù)跨越兩頁

13、指令指令跨越跨越兩頁兩頁3 3、地址變換機構、地址變換機構開始頁號頁表長度？CPU檢索快表NNY頁表項在快表中？訪問頁表頁在內(nèi)存？修改訪問位和修改位修改快表形成物理地址地址變換結(jié)束越界中斷程序請求訪問一頁YN缺頁中斷處理Y保留CPU現(xiàn)場內(nèi)存滿嗎？將一頁從外存換入內(nèi)存OS命令CPU從外存讀缺頁啟動I/O硬件Y從外存中找到缺頁選擇一頁換出該頁被修改否？將該頁寫回外存修改頁表NYN硬件硬件軟件軟件地址變換例題地址變換例題返回v 某虛擬存儲器的用戶空間共有某虛擬存儲器的用戶空間共有3232個頁面，每頁個頁面，每頁1KB1KB，主存，主存16KB16KB。假定。假定某時刻系統(tǒng)為用戶的第某時刻系統(tǒng)為用戶的

14、第0 0、1 1、2 2、3 3頁分別分配的物理塊號為頁分別分配的物理塊號為5 5、1010、4 4、7 7，試將虛擬地址試將虛擬地址0A5C0A5C和和093C093C變換為物理地址。變換為物理地址。解：虛擬地址為：頁號（解：虛擬地址為：頁號（2 25 5=32=32）5 5位位 頁內(nèi)位移（頁內(nèi)位移（2 21010=1024=1024）1010位位 物理地址為：物理塊號（物理地址為：物理塊號（2 24 4=16=16）4 4位位 塊內(nèi)位移（塊內(nèi)位移（1 11010=1024=1024）1010位位虛擬地址虛擬地址OA5COA5C對應的二進制為：對應的二進制為： 00000010 1010 1

15、00101010111001100 即虛擬地址即虛擬地址OA5COA5C的頁號為的頁號為2 2，頁內(nèi)位移為，頁內(nèi)位移為10010111001001011100，由題意知對，由題意知對應的物理地址為：應的物理地址為：010100 1000 100101010111001100即即125C125C同理求同理求093C093C。略。略15四、請求分頁中的內(nèi)存分配四、請求分頁中的內(nèi)存分配2. 2. 內(nèi)存分配策略內(nèi)存分配策略1) 1) 固定分配局部置換固定分配局部置換2) 2) 可變分配全局置換可變分配全局置換3) 3) 可變分配局部置換可變分配局部置換1.1.最小物理塊數(shù)的確定最小物理塊數(shù)的確定 最小

16、物理塊數(shù)是指能保證進程正常運行所需的最小物最小物理塊數(shù)是指能保證進程正常運行所需的最小物理塊數(shù)。理塊數(shù)。3. 3. 物理塊分配算法物理塊分配算法1) 1) 平均分配算法平均分配算法 2) 2) 按比例分配算法按比例分配算法3) 3) 考慮優(yōu)先權的分配算法考慮優(yōu)先權的分配算法5.3 5.3 請求分頁中的請求分頁中的頁面置換算法頁面置換算法 頁面置換算法頁面置換算法也稱為頁面淘汰算法，是用來選擇換出也稱為頁面淘汰算法，是用來選擇換出頁面的算法。頁面置換算法的優(yōu)劣直接影響到系統(tǒng)的效率，頁面的算法。頁面置換算法的優(yōu)劣直接影響到系統(tǒng)的效率，若選擇不合適，可能會出現(xiàn)以下現(xiàn)象：若選擇不合適，可能會出現(xiàn)以下現(xiàn)

17、象： 剛被剛被淘汰出內(nèi)存淘汰出內(nèi)存的頁面，過后不久又要訪問它，需要的頁面，過后不久又要訪問它，需要再次將其調(diào)入，而該頁調(diào)入內(nèi)存后不入又再次被淘汰出內(nèi)再次將其調(diào)入，而該頁調(diào)入內(nèi)存后不入又再次被淘汰出內(nèi)存，然后又要訪問它，如此反復，使得系統(tǒng)把大部分時間存，然后又要訪問它，如此反復，使得系統(tǒng)把大部分時間用在了用在了頁面的調(diào)進換出頁面的調(diào)進換出上，而幾乎不能完成任何有效的工上，而幾乎不能完成任何有效的工作，這種現(xiàn)象稱為作，這種現(xiàn)象稱為抖動（又稱顛簸）抖動（又稱顛簸）。 頁面置換帶來的問題頁面置換帶來的問題n抖動問題抖動問題5.3 5.3 請求分頁中的請求分頁中的頁面置換算法頁面置換算法 常用的頁面置換

18、算法：常用的頁面置換算法： v 最佳置換算法最佳置換算法(OPT)(OPT)：選擇選擇永遠不再需要永遠不再需要的頁面或的頁面或最長時間最長時間以以后才需要訪問的頁面予以淘汰。后才需要訪問的頁面予以淘汰。v 先進先出置換算法先進先出置換算法(FIFO)(FIFO)：選擇選擇先進入內(nèi)存的頁面先進入內(nèi)存的頁面予以淘汰。予以淘汰。v 最近最久未使用置換算法最近最久未使用置換算法(LRU(LRU) )：選擇最近一段時間選擇最近一段時間最長時最長時間沒有被訪問過間沒有被訪問過的頁面予以淘汰。的頁面予以淘汰。v 淘汰算法的性能評價淘汰算法的性能評價v 影響中斷缺頁率的因素影響中斷缺頁率的因素最佳置換算法例最

19、佳置換算法例假定系統(tǒng)為某進程分配了假定系統(tǒng)為某進程分配了3 3個物理塊，進程運行時的頁面走向為個物理塊，進程運行時的頁面走向為 1,2,3,4,1,2,5,1,2,3,4,51,2,3,4,1,2,5,1,2,3,4,5，開始時，開始時3 3個物理塊均為空，計算采用個物理塊均為空，計算采用最佳置換最佳置換頁面淘汰算法時的缺頁率？（頁面淘汰算法時的缺頁率？（7/12)7/12)返回注：注：實際上這種算法無法實現(xiàn)，實際上這種算法無法實現(xiàn)，因頁面訪問的未來順序很難精確預測，但可因頁面訪問的未來順序很難精確預測，但可用該算法評價其它算法的優(yōu)劣。用該算法評價其它算法的優(yōu)劣。頁面走向12341251234

20、5物理塊1111111111333物理塊222222222244物理塊33444555555缺頁缺缺缺缺HH缺HH缺缺H先進先出置換算法例題先進先出置換算法例題1 1、假定系統(tǒng)為某進程分配了、假定系統(tǒng)為某進程分配了3 3個物理塊，進程運行時的頁面走向個物理塊，進程運行時的頁面走向為為 1,2,3,4,1,2,5,1,2,3,4,51,2,3,4,1,2,5,1,2,3,4,5，開始時，開始時3 3個物理塊均為空，計算個物理塊均為空，計算采用采用先進先出先進先出頁面淘汰算法時的缺頁率？（頁面淘汰算法時的缺頁率？（9/12)9/12)頁面走向頁面走向123412512345物理塊物理塊1111*4

21、44*555*物理塊物理塊2222*111*33物理塊物理塊3333*222*4缺頁缺頁缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺先進先出置換算法例題先進先出置換算法例題2 2、假定系統(tǒng)為某進程分配了、假定系統(tǒng)為某進程分配了4 4個物理塊，進程運行時的頁面走向個物理塊，進程運行時的頁面走向為為 1,2,3,4,1,2,5,1,2,3,4,51,2,3,4,1,2,5,1,2,3,4,5，開始時，開始時4 4個物理塊均為空，計算個物理塊均為空，計算采用采用先進先出先進先出頁面淘汰算法時的缺頁率？（頁面淘汰算法時的缺頁率？（10/12)10/12)頁面走向123412512345物理塊11111*555

22、5*44物理塊22222*1111*5物理塊33333*2222*物理塊44444*333缺頁缺缺缺缺缺缺缺缺缺缺先進先出置換算法例題先進先出置換算法例題3 3、假定系統(tǒng)為某進程分配了、假定系統(tǒng)為某進程分配了5 5個物理塊，進程運行時的頁面走向個物理塊，進程運行時的頁面走向為為 1,2,3,4,1,2,5,1,2,3,4,51,2,3,4,1,2,5,1,2,3,4,5，開始時，開始時3 3個物理塊均為空，計算個物理塊均為空，計算采用采用先進先出先進先出頁面淘汰算法時的缺頁率？（頁面淘汰算法時的缺頁率？（5/12)5/12)頁面走向123412512345物理塊111111物理塊22222物理

23、塊3333物理塊444物理塊55缺頁缺缺缺缺缺先進先出置換算法先進先出置換算法_注：注：返回物理塊數(shù)345缺頁次數(shù)9 10 5 1 1、該算法的該算法的出發(fā)點出發(fā)點是最早調(diào)入內(nèi)存的頁面，其不再被訪問的可能性會大一些。是最早調(diào)入內(nèi)存的頁面，其不再被訪問的可能性會大一些。2 2、該算法實現(xiàn)比較簡單，對具有線性順序訪問的程序比較合適，而對其他情、該算法實現(xiàn)比較簡單，對具有線性順序訪問的程序比較合適，而對其他情況效率低況效率低。因為經(jīng)常被訪問的頁面，往往在內(nèi)存中停留最久，結(jié)果這些常用的。因為經(jīng)常被訪問的頁面，往往在內(nèi)存中停留最久，結(jié)果這些常用的頁面卻因變老而被淘汰。頁面卻因變老而被淘汰。3 3、先進先

24、出算法存在一種異?，F(xiàn)象，即在某些情況下會出現(xiàn)分配給的進程物先進先出算法存在一種異?，F(xiàn)象，即在某些情況下會出現(xiàn)分配給的進程物理塊數(shù)增多，缺頁次數(shù)有時增加，有時減少的奇怪現(xiàn)象，這種現(xiàn)象稱為理塊數(shù)增多，缺頁次數(shù)有時增加，有時減少的奇怪現(xiàn)象，這種現(xiàn)象稱為BeladyBelady現(xiàn)象?，F(xiàn)象。如上幾例如上幾例：頁面走向123412512345物理塊1111*4 444*555*物理塊2222*1 111*33物理塊3333*222*4缺頁缺缺缺缺缺缺缺缺缺最近最久未使用算法例最近最久未使用算法例假定系統(tǒng)為某進程分配了假定系統(tǒng)為某進程分配了3 3個物理塊，進程運行時的頁面走向為個物理塊，進程運行時的頁面走向

25、為 1,2,3,4,1,2,5,1,2,3,4,51,2,3,4,1,2,5,1,2,3,4,5，開始時，開始時3 3個物理塊均為空，計算采用個物理塊均為空，計算采用最近最久未使用最近最久未使用頁面淘汰算法時的缺頁率？（頁面淘汰算法時的缺頁率？（10/12)10/12)頁面走向123412512345物理塊1111*444*555*333物理塊2222*111*111*44物理塊3333*222*222*5缺頁缺缺缺缺缺缺缺HH缺缺缺最近最久未使用算法最近最久未使用算法_注注v該算法的出發(fā)點該算法的出發(fā)點：如果某個頁面被訪問了，則它如果某個頁面被訪問了，則它可能馬上還要可能馬上還要訪問訪問。反

26、之，如果很長時間未被訪問，則它在最近一段時間也不。反之，如果很長時間未被訪問，則它在最近一段時間也不會被訪問。會被訪問。v該算法的性能接近于最佳算法，但該算法的性能接近于最佳算法，但實現(xiàn)起來較困難實現(xiàn)起來較困難。因為要找。因為要找出最近最久未使用的頁面，必須為每一頁設置相關記錄項，用于出最近最久未使用的頁面，必須為每一頁設置相關記錄項，用于記錄頁面的訪問情況記錄頁面的訪問情況，并且每訪問一次頁面都須更新該信息。這，并且每訪問一次頁面都須更新該信息。這將使系統(tǒng)的開銷加大，所以在實際系統(tǒng)中將使系統(tǒng)的開銷加大，所以在實際系統(tǒng)中往往使用該算法的近似往往使用該算法的近似算法算法。思考：理論依據(jù)？思考：理

27、論依據(jù)？ LRU置換算法的硬件支持置換算法的硬件支持算法比較好，但要求有較多的支持硬件。算法比較好，但要求有較多的支持硬件。v寄存器寄存器為了記錄某進程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁為了記錄某進程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個面配置一個移位寄存器移位寄存器，可表示為：，可表示為： R=Rn-1Rn-2Rn-3 R2R1R0 R 實 頁 R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1

28、0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 圖圖4-29某進程具有某進程具有8個頁面時的個頁面時的LRU訪問情況訪問情況 1 1、訪問某物理塊時，、訪問某物理塊時，將相應寄存器的將相應寄存器的R Rn n1 1位位置成置成1 1。2 2、定時信號將每隔一、定時信號將每隔一定時間定時間( (如如100 ms)100 ms)將寄將寄存器右移一位。存器右移一位。3 3、視、視n n位寄存器的數(shù)為位寄存器的數(shù)為一個整數(shù)。一個整數(shù)。4 4、當發(fā)生缺頁時，首、當發(fā)生缺頁時，首先置換先置換R R值最小的頁。值最小的頁。 v棧棧利用一個特殊的

29、棧來保存當前使用的各個頁面的頁面號。利用一個特殊的棧來保存當前使用的各個頁面的頁面號。 棧頂棧頂始終是最新被訪問頁面的編號，而始終是最新被訪問頁面的編號，而棧底棧底則是最近最久未使用頁面則是最近最久未使用頁面的頁面號。（的頁面號。（分配主存分配主存5 5個塊個塊）圖圖4-30用棧保存當前使用頁面時棧的變化情況用棧保存當前使用頁面時棧的變化情況 4474707407047170410174010741210742120741210742621076頂頂?shù)椎酌校菏校菏?失失 失失 H 失失 H H 失失 H H 替替LRU置換算法的硬件支持置換算法的硬件支持命中命中命中命中命中命中命中命中命

30、中命中淘汰算法的性能評價淘汰算法的性能評價v頁面走向（頁地址流）頁面走向（頁地址流） 一個程序在其運行過程中所訪問的頁號的序列稱為頁面走向。一個程序在其運行過程中所訪問的頁號的序列稱為頁面走向。v缺頁中斷率（頁面失效率）缺頁中斷率（頁面失效率） 欲訪問的頁面不在主存稱為欲訪問的頁面不在主存稱為缺頁故障缺頁故障（或頁面失效）。缺頁故障的次數(shù)占（或頁面失效）。缺頁故障的次數(shù)占全部訪問頁數(shù)的百分比即為全部訪問頁數(shù)的百分比即為缺頁中斷率缺頁中斷率（頁面失效率）。（頁面失效率）。 f = f = （缺頁次數(shù)）（缺頁次數(shù)）/ /（訪問頁面總數(shù)）（訪問頁面總數(shù)） 100 % 100 % 命中率命中率 H=H

31、=（命中次數(shù)）（命中次數(shù)）/ /（訪問頁面總數(shù)）（訪問頁面總數(shù)） 100 % 100 % v抖動問題抖動問題 導致系統(tǒng)效率急劇下降的導致系統(tǒng)效率急劇下降的主輔存之間的頻繁的頁面置換主輔存之間的頻繁的頁面置換現(xiàn)象稱為抖動（顛現(xiàn)象稱為抖動（顛簸）。簸）。 抖動現(xiàn)象花費了系統(tǒng)的大量開銷。抖動現(xiàn)象花費了系統(tǒng)的大量開銷。返回v頁面的大小頁面的大小 頁面增大，可減少缺頁中斷的次數(shù)，但頁內(nèi)的浪費增大。頁面增大，可減少缺頁中斷的次數(shù)，但頁內(nèi)的浪費增大。 影響缺頁中斷率的因素影響缺頁中斷率的因素缺頁次數(shù)缺頁次數(shù)主存容量主存容量工作集工作集 任何程序在局部性放任何程序在局部性放入主存時都有一個臨界值入主存時都有一

32、個臨界值的要求，這個主存要求的的要求，這個主存要求的臨界值被稱為臨界值被稱為工作集。工作集。v 分配給作業(yè)的主存容量分配給作業(yè)的主存容量 分配給作業(yè)的頁面數(shù)（分配給作業(yè)的頁面數(shù)（物理塊物理塊）增多可減少缺頁中斷的次數(shù)）增多可減少缺頁中斷的次數(shù)。v頁面調(diào)度算法的性能頁面調(diào)度算法的性能 好的調(diào)度算法應盡量避免或減少抖動現(xiàn)象的出現(xiàn)。好的調(diào)度算法應盡量避免或減少抖動現(xiàn)象的出現(xiàn)。v用戶程序編制的方法不合適用戶程序編制的方法不合適 提高程序的局部性程度，可減少缺頁中斷的次數(shù)。提高程序的局部性程度，可減少缺頁中斷的次數(shù)。 影響缺頁中斷率的因素影響缺頁中斷率的因素返回4.8 4.8 請求分段式存儲管理方式請求

33、分段式存儲管理方式v 請求分段存儲管理系統(tǒng)也與請求分頁存儲管理系統(tǒng)一樣，為請求分段存儲管理系統(tǒng)也與請求分頁存儲管理系統(tǒng)一樣，為用戶提供了一個比內(nèi)存空間大得多的用戶提供了一個比內(nèi)存空間大得多的虛擬存儲器虛擬存儲器。v 在請求分段存儲管理系統(tǒng)中，作業(yè)運行之前，只要求將當前在請求分段存儲管理系統(tǒng)中，作業(yè)運行之前，只要求將當前需要的若干個分段裝入內(nèi)存，便可啟動作業(yè)運行。在作業(yè)運需要的若干個分段裝入內(nèi)存，便可啟動作業(yè)運行。在作業(yè)運行過程中，如果要訪問的分段不在內(nèi)存中，則通過行過程中，如果要訪問的分段不在內(nèi)存中，則通過調(diào)段功能調(diào)段功能將其調(diào)入，同時還可以通過將其調(diào)入，同時還可以通過置換功能置換功能將暫時不

34、用的分段換出將暫時不用的分段換出到外存，以便騰出內(nèi)存空間。到外存，以便騰出內(nèi)存空間。4.4 4.4 請求分段式存儲管理方式請求分段式存儲管理方式v 請求分段中的硬件支持請求分段中的硬件支持n段表機制段表機制n缺段中斷機構缺段中斷機構n地址變換機構地址變換機構v 分段共享與保護分段共享與保護n共享段表共享段表n共享段的分配與回收共享段的分配與回收n分段保護分段保護（越界檢查、存取控制檢查、環(huán)保越界檢查、存取控制檢查、環(huán)保護機構護機構）段表機制（擴充）段表機制（擴充）v 存取方式：存取方式： 存取屬性（執(zhí)行、只讀、允許讀存取屬性（執(zhí)行、只讀、允許讀/ /寫）。寫）。v 訪問字段訪問字段A：記錄該段

35、被訪問的頻繁程度。記錄該段被訪問的頻繁程度。v 修改位修改位M： 表示該段在進入內(nèi)存后，是否被修改過。表示該段在進入內(nèi)存后，是否被修改過。v 存在位存在位P： 表示該段是否在內(nèi)存中。表示該段是否在內(nèi)存中。v 增補位：增補位： 表示在運行過程中，該段是否做過動態(tài)增長。表示在運行過程中，該段是否做過動態(tài)增長。v 外存地址：外存地址： 表示該段在外存中的起始地址。表示該段在外存中的起始地址。段名段長段的基址存取方式訪問字段A修改位M存在位P增補位外存地址缺段中斷機構缺段中斷機構v 當被訪問的段不在內(nèi)存中時，將產(chǎn)生一當被訪問的段不在內(nèi)存中時，將產(chǎn)生一缺段中斷信號缺段中斷信號。其缺段中。其缺段中斷的處理過程如圖：斷的處理過程如圖：虛段S不在內(nèi)存返回阻塞請求進程內(nèi)存中有合適的空閑區(qū)嗎？從外存讀入段S修改段表及內(nèi)存空區(qū)鏈喚醒請求進程空區(qū)容量總和能否滿足？空