第5章(2)虛存管理技術(shù)+

1、操作系統(tǒng)講義之五第五（第五（2）章）章 虛存管理技術(shù)虛存管理技術(shù)5.1 基本概念基本概念5.2 頁(yè)式管理頁(yè)式管理 補(bǔ)充：多級(jí)頁(yè)表補(bǔ)充：多級(jí)頁(yè)表 十六進(jìn)制地址轉(zhuǎn)換十六進(jìn)制地址轉(zhuǎn)換 時(shí)鐘時(shí)鐘( (Clock)置換算法置換算法5.3 段式管理段式管理5.4 段頁(yè)式管理段頁(yè)式管理5.5 局部性原理和抖動(dòng)問(wèn)題局部性原理和抖動(dòng)問(wèn)題操作系統(tǒng)講義之五v前面所述的各種管理技術(shù)統(tǒng)稱(chēng)為實(shí)存管理技術(shù)，其特前面所述的各種管理技術(shù)統(tǒng)稱(chēng)為實(shí)存管理技術(shù)，其特點(diǎn)是在作業(yè)運(yùn)行時(shí)，必須將整個(gè)作業(yè)的邏輯地址空間點(diǎn)是在作業(yè)運(yùn)行時(shí)，必須將整個(gè)作業(yè)的邏輯地址空間全部裝入主存全部裝入主存(除覆蓋外除覆蓋外)，當(dāng)作業(yè)尺寸大于主存可用空，當(dāng)作業(yè)

2、尺寸大于主存可用空間時(shí)，該作業(yè)就無(wú)法運(yùn)行。間時(shí)，該作業(yè)就無(wú)法運(yùn)行。v同實(shí)存相對(duì)的另一類(lèi)存儲(chǔ)管理技術(shù)稱(chēng)為虛存管理技術(shù)同實(shí)存相對(duì)的另一類(lèi)存儲(chǔ)管理技術(shù)稱(chēng)為虛存管理技術(shù)。同實(shí)存管理的主要區(qū)別是：同實(shí)存管理的主要區(qū)別是：不用將整個(gè)作業(yè)裝入主存不用將整個(gè)作業(yè)裝入主存就可以投入運(yùn)行。就可以投入運(yùn)行。v引入如下一些概念引入如下一些概念： 1. 虛擬存儲(chǔ)器：是指一種實(shí)際上并不存在的虛假的存儲(chǔ)虛擬存儲(chǔ)器：是指一種實(shí)際上并不存在的虛假的存儲(chǔ)器。器。 2. 虛擬地址：把一個(gè)運(yùn)行進(jìn)程訪(fǎng)問(wèn)的地址稱(chēng)為虛擬地址。虛擬地址：把一個(gè)運(yùn)行進(jìn)程訪(fǎng)問(wèn)的地址稱(chēng)為虛擬地址。5.1 基本概念基本概念操作系統(tǒng)講義之五 3. 實(shí)地址：把處理機(jī)可

3、直接訪(fǎng)問(wèn)的地址稱(chēng)為實(shí)地址。實(shí)地址：把處理機(jī)可直接訪(fǎng)問(wèn)的地址稱(chēng)為實(shí)地址。相應(yīng)的有：虛地址空間、實(shí)地址空間的概念。相應(yīng)的有：虛地址空間、實(shí)地址空間的概念。 問(wèn)題：?jiǎn)栴}： v把把虛地址空間和實(shí)地址空間分開(kāi)后，這樣虛地址空虛地址空間和實(shí)地址空間分開(kāi)后，這樣虛地址空間可以遠(yuǎn)遠(yuǎn)大于實(shí)地址空間，亦即作業(yè)的大小可以間可以遠(yuǎn)遠(yuǎn)大于實(shí)地址空間，亦即作業(yè)的大小可以遠(yuǎn)遠(yuǎn)大于主存空間的大小。遠(yuǎn)遠(yuǎn)大于主存空間的大小。v另一個(gè)相關(guān)問(wèn)題是：作業(yè)運(yùn)行時(shí)，其整個(gè)虛地址空另一個(gè)相關(guān)問(wèn)題是：作業(yè)運(yùn)行時(shí)，其整個(gè)虛地址空間間(邏輯地址空間邏輯地址空間)是否必須全部裝入主存？如果必是否必須全部裝入主存？如果必須的話(huà)，那么虛地址空間仍然不能

4、大于實(shí)地址空間。須的話(huà)，那么虛地址空間仍然不能大于實(shí)地址空間。操作系統(tǒng)講義之五v一個(gè)程序的某次運(yùn)行，常有些部分是不用的一個(gè)程序的某次運(yùn)行，常有些部分是不用的(如：無(wú)錯(cuò)如：無(wú)錯(cuò)誤發(fā)生時(shí)就不會(huì)調(diào)用出錯(cuò)處理程序誤發(fā)生時(shí)就不會(huì)調(diào)用出錯(cuò)處理程序)。所以，只讓最近。所以，只讓最近要用到的那部分程序和數(shù)據(jù)裝入主存，以后用到哪部分要用到的那部分程序和數(shù)據(jù)裝入主存，以后用到哪部分再把哪部分調(diào)入，而把不用部分調(diào)出再把哪部分調(diào)入，而把不用部分調(diào)出(暫存外存暫存外存)。v為了完成上述功能，操作系統(tǒng)應(yīng)負(fù)責(zé)下面三個(gè)方面的任為了完成上述功能，操作系統(tǒng)應(yīng)負(fù)責(zé)下面三個(gè)方面的任務(wù)：務(wù)： （1）把哪部分調(diào)入主存；）把哪部分調(diào)入主存

5、； （2）放在主存什么位置；）放在主存什么位置； （3）主存空間不足時(shí)，把哪部分淘汰出去。）主存空間不足時(shí)，把哪部分淘汰出去。v本章主要介紹目前廣泛使用的三種虛存管理技術(shù)：本章主要介紹目前廣泛使用的三種虛存管理技術(shù)： 頁(yè)式管理頁(yè)式管理(靜態(tài)頁(yè)式管理和動(dòng)態(tài)頁(yè)式管理靜態(tài)頁(yè)式管理和動(dòng)態(tài)頁(yè)式管理) 段式管理段式管理 段頁(yè)式存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理操作系統(tǒng)講義之五5.2 頁(yè)式管理頁(yè)式管理 實(shí)現(xiàn)原理實(shí)現(xiàn)原理 1. 等分主存等分主存 把主存劃分成大小相同的存儲(chǔ)塊，稱(chēng)為頁(yè)面把主存劃分成大小相同的存儲(chǔ)塊，稱(chēng)為頁(yè)面(或或塊塊)，并給各頁(yè)面從零開(kāi)始編上序號(hào)：，并給各頁(yè)面從零開(kāi)始編上序號(hào)：0，1，2，。 2. 等分作業(yè)

6、的邏輯地址空間等分作業(yè)的邏輯地址空間 將程序的邏輯地址空間也劃分若干個(gè)與頁(yè)面大小將程序的邏輯地址空間也劃分若干個(gè)與頁(yè)面大小相同的塊相同的塊,稱(chēng)為頁(yè)。也編上序號(hào)稱(chēng)為頁(yè)。也編上序號(hào)0，1，2，。 主存分配原則主存分配原則 系統(tǒng)以系統(tǒng)以頁(yè)面頁(yè)面(塊塊)為單位把主存分給作業(yè)，每頁(yè)對(duì)為單位把主存分給作業(yè)，每頁(yè)對(duì)應(yīng)內(nèi)存中一個(gè)頁(yè)面，這些頁(yè)面可以是不相臨的或應(yīng)內(nèi)存中一個(gè)頁(yè)面，這些頁(yè)面可以是不相臨的或連續(xù)的。連續(xù)的。 操作系統(tǒng)講義之五 頁(yè)式存儲(chǔ)管理根據(jù)進(jìn)程的頁(yè)是否一次全部裝入頁(yè)式存儲(chǔ)管理根據(jù)進(jìn)程的頁(yè)是否一次全部裝入還是部分裝入而分為：還是部分裝入而分為：靜態(tài)頁(yè)式管理實(shí)存管理靜態(tài)頁(yè)式管理實(shí)存管理動(dòng)態(tài)頁(yè)式管理虛存管

7、理動(dòng)態(tài)頁(yè)式管理虛存管理操作系統(tǒng)講義之五一、靜態(tài)頁(yè)式管理一、靜態(tài)頁(yè)式管理v基本原理：要求程序執(zhí)行前，基本原理：要求程序執(zhí)行前，分配其所需的所分配其所需的所有頁(yè)面，這些頁(yè)面可以是不相鄰的有頁(yè)面，這些頁(yè)面可以是不相鄰的。這意味著。這意味著內(nèi)存中有足夠的空閑頁(yè)面才能執(zhí)行某個(gè)程序。內(nèi)存中有足夠的空閑頁(yè)面才能執(zhí)行某個(gè)程序。需要需要CPU的硬件支持的硬件支持。 下面圖顯示靜態(tài)頁(yè)式內(nèi)存使用情況：下面圖顯示靜態(tài)頁(yè)式內(nèi)存使用情況：操作系統(tǒng)講義之五靜態(tài)頁(yè)式管理主存分配情況靜態(tài)頁(yè)式管理主存分配情況FrameNumber0123456789101112131401234567891011121314A.0A.1A.2A

8、.3 01234567891011121314A.0A.1A.2A.3B.0B.1B.2操作系統(tǒng)講義之五在頁(yè)式儲(chǔ)存管理中，是以頁(yè)面為單位分給用戶(hù)使在頁(yè)式儲(chǔ)存管理中，是以頁(yè)面為單位分給用戶(hù)使用，為了記錄主存的使用情況，系統(tǒng)為用，為了記錄主存的使用情況，系統(tǒng)為每個(gè)進(jìn)程每個(gè)進(jìn)程建立一個(gè)頁(yè)表建立一個(gè)頁(yè)表，最簡(jiǎn)單的頁(yè)表包括如下信息：，最簡(jiǎn)單的頁(yè)表包括如下信息： （1）頁(yè)號(hào)：作業(yè)的各頁(yè)的頁(yè)號(hào)；）頁(yè)號(hào)：作業(yè)的各頁(yè)的頁(yè)號(hào)； （2）塊號(hào)：指該頁(yè)裝入主存的第幾）塊號(hào)：指該頁(yè)裝入主存的第幾 個(gè)頁(yè)面上。個(gè)頁(yè)面上。1. 頁(yè)表與頁(yè)表地址寄存器頁(yè)表與頁(yè)表地址寄存器操作系統(tǒng)講義之五頁(yè)的大小帶來(lái)的影響頁(yè)的大小帶來(lái)的影響頁(yè)?。喉?yè)

9、?。簝?nèi)碎片小，頁(yè)表長(zhǎng)，管理復(fù)雜，存內(nèi)碎片小，頁(yè)表長(zhǎng)，管理復(fù)雜，存儲(chǔ)信息少，可能頻繁調(diào)頁(yè)；儲(chǔ)信息少，可能頻繁調(diào)頁(yè)；頁(yè)大：頁(yè)大：頁(yè)表短，管理開(kāi)銷(xiāo)小，交換時(shí)對(duì)外頁(yè)表短，管理開(kāi)銷(xiāo)小，交換時(shí)對(duì)外存存I/O效率高，但內(nèi)碎片大，會(huì)多浪費(fèi)內(nèi)效率高，但內(nèi)碎片大，會(huì)多浪費(fèi)內(nèi)存存操作系統(tǒng)講義之五LOAD 1LOAD 1，11201120 ADD 1ADD 1，241024100 010010010210210001000680268021120112020002000400040006251625124102410300030000 0頁(yè)頁(yè)1 1頁(yè)頁(yè)2 2頁(yè)頁(yè)3 3頁(yè)頁(yè)0 010001000200020003000

10、3000頁(yè)號(hào)頁(yè)號(hào) 塊號(hào)塊號(hào)0 30 31 91 92 -2 -3 -3 -0 20 2頁(yè)號(hào)頁(yè)號(hào) 塊號(hào)塊號(hào)1 41 42 72 70 0100010002000200030003000LOAD 1LOAD 1，11201120 ADD 1ADD 1，24102410310031003102310240004000500050006000600070007000100001000090009000800080002 2塊塊3 3塊塊4 4塊塊5 5塊塊6 6塊塊7 7塊塊8 8塊塊9 9塊塊0 0塊塊1 1塊塊9120912068026802操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)1 1作業(yè)作業(yè)2 2頁(yè)表頁(yè)表操作

11、系統(tǒng)講義之五2. 靜態(tài)頁(yè)式管理的特點(diǎn)靜態(tài)頁(yè)式管理的特點(diǎn)優(yōu)點(diǎn)：優(yōu)點(diǎn)： 沒(méi)有外碎片，每個(gè)內(nèi)碎片不超過(guò)頁(yè)的大小沒(méi)有外碎片，每個(gè)內(nèi)碎片不超過(guò)頁(yè)的大小 一個(gè)程序不必連續(xù)存放。一個(gè)程序不必連續(xù)存放。 由于頁(yè)的大小相等，內(nèi)存的分配、回收簡(jiǎn)單，由于頁(yè)的大小相等，內(nèi)存的分配、回收簡(jiǎn)單，易于管理。易于管理。缺點(diǎn)：缺點(diǎn)：程序要求全部裝入內(nèi)存才能執(zhí)行。程序要求全部裝入內(nèi)存才能執(zhí)行。操作系統(tǒng)講義之五3. 邏輯地址的表示邏輯地址的表示v用戶(hù)的邏輯地址一般是從基址用戶(hù)的邏輯地址一般是從基址“0”開(kāi)始連續(xù)開(kāi)始連續(xù)編址。在分頁(yè)系統(tǒng)中，每個(gè)虛地址編址。在分頁(yè)系統(tǒng)中，每個(gè)虛地址(相對(duì)地址相對(duì)地址)用一個(gè)數(shù)對(duì)用一個(gè)數(shù)對(duì)(p，d)來(lái)表

12、示，其中來(lái)表示，其中p表示頁(yè)號(hào)，表示頁(yè)號(hào)，d表示頁(yè)內(nèi)地址表示頁(yè)內(nèi)地址(頁(yè)內(nèi)偏移量頁(yè)內(nèi)偏移量)。v令令A(yù)是一個(gè)虛地址，頁(yè)面大小為是一個(gè)虛地址，頁(yè)面大小為L(zhǎng),則：則： p=INTA/L，d=AmodL 例如：設(shè)頁(yè)面大小例如：設(shè)頁(yè)面大小 L=1000字節(jié)字節(jié), A=3456,則則: p=INT3456/1000=3 L=3456mod1000=456 操作系統(tǒng)講義之五v在內(nèi)存中的表示：在內(nèi)存中的表示： 若頁(yè)面大小為若頁(yè)面大小為2的冪，邏輯地址轉(zhuǎn)換為頁(yè)號(hào)的冪，邏輯地址轉(zhuǎn)換為頁(yè)號(hào)p和位移量和位移量d就非就非常簡(jiǎn)單常簡(jiǎn)單(由地址變換機(jī)構(gòu)自動(dòng)完成由地址變換機(jī)構(gòu)自動(dòng)完成)。頁(yè)號(hào)頁(yè)號(hào)頁(yè)內(nèi)地址頁(yè)內(nèi)地址( (頁(yè)內(nèi)偏

13、移量頁(yè)內(nèi)偏移量) )p pd d例如：一個(gè)頁(yè)長(zhǎng)為例如：一個(gè)頁(yè)長(zhǎng)為1 K，擁有，擁有64頁(yè)的虛擬空間地址結(jié)構(gòu)如圖下頁(yè)的虛擬空間地址結(jié)構(gòu)如圖下圖所示。圖所示。15 10 9 0pd26=64(頁(yè)頁(yè))，頁(yè)的長(zhǎng)度，頁(yè)的長(zhǎng)度= 210=1024(字節(jié)字節(jié))=1K操作系統(tǒng)講義之五舉例：舉例：采用頁(yè)式存儲(chǔ)管理的系統(tǒng)中，若邏輯地址中的頁(yè)采用頁(yè)式存儲(chǔ)管理的系統(tǒng)中，若邏輯地址中的頁(yè)號(hào)用號(hào)用8位表示，頁(yè)內(nèi)地址用位表示，頁(yè)內(nèi)地址用16位表示。問(wèn)：位表示。問(wèn)：（1）用戶(hù)程序的最大長(zhǎng)度是多少兆字節(jié)？）用戶(hù)程序的最大長(zhǎng)度是多少兆字節(jié)？（2）主存分塊為多少）主存分塊為多少K字節(jié)？（字節(jié)？（KB） 解：邏輯地址中的頁(yè)號(hào)用解：邏

14、輯地址中的頁(yè)號(hào)用8位表示，就是說(shuō)邏輯地址位表示，就是說(shuō)邏輯地址中最大頁(yè)數(shù)是中最大頁(yè)數(shù)是28=256(頁(yè)頁(yè))；頁(yè)內(nèi)地址用；頁(yè)內(nèi)地址用16位表示，即位表示，即一個(gè)一個(gè)(邏輯邏輯)頁(yè)大小為頁(yè)大小為216=65536(字節(jié)字節(jié)) / 1024=64K。（1）用戶(hù)程序的最大長(zhǎng)度就是）用戶(hù)程序的最大長(zhǎng)度就是256頁(yè)全部使用的情況頁(yè)全部使用的情況了，即了，即 256 * 64K=16384K =16384K/1024=16MB。（2）主存分塊大小應(yīng)該和邏輯頁(yè)大小相同，即頁(yè)面）主存分塊大小應(yīng)該和邏輯頁(yè)大小相同，即頁(yè)面=64KB操作系統(tǒng)講義之五4. 分頁(yè)管理中的地址轉(zhuǎn)換分頁(yè)管理中的地址轉(zhuǎn)換 靜態(tài)頁(yè)式管理的另一個(gè)

15、關(guān)鍵問(wèn)題是地址變換。靜態(tài)頁(yè)式管理的另一個(gè)關(guān)鍵問(wèn)題是地址變換。即怎樣由頁(yè)號(hào)和頁(yè)內(nèi)相對(duì)地址變換到內(nèi)存物即怎樣由頁(yè)號(hào)和頁(yè)內(nèi)相對(duì)地址變換到內(nèi)存物理地址的問(wèn)題。理地址的問(wèn)題。在頁(yè)式管理中，地址變換的在頁(yè)式管理中，地址變換的速度也是設(shè)計(jì)地址變換機(jī)構(gòu)時(shí)必須考慮的問(wèn)速度也是設(shè)計(jì)地址變換機(jī)構(gòu)時(shí)必須考慮的問(wèn)題之一。題之一。v現(xiàn)以上圖的指令現(xiàn)以上圖的指令 LOAD 1, 1120 為例說(shuō)明分頁(yè)為例說(shuō)明分頁(yè)管理中的地址變換過(guò)程。管理中的地址變換過(guò)程。v當(dāng)當(dāng)CPU執(zhí)行執(zhí)行LOAD1, 1120時(shí)，該指令給出的時(shí)，該指令給出的虛地址為虛地址為1120，首先由地址變換機(jī)構(gòu)自動(dòng)將，首先由地址變換機(jī)構(gòu)自動(dòng)將該地址分為頁(yè)號(hào)該地址

16、分為頁(yè)號(hào)p=1和位移量和位移量d=120，其轉(zhuǎn)換，其轉(zhuǎn)換過(guò)程如下圖所示：過(guò)程如下圖所示：操作系統(tǒng)講義之五頁(yè)號(hào)頁(yè)號(hào) 塊號(hào)塊號(hào)0 30 31 91 92 -2 -3 -3 -頁(yè)表長(zhǎng)度頁(yè)表長(zhǎng)度 頁(yè)表起址頁(yè)表起址 1 120 1 1209 1209 1209 91000+1201000+120912091206802680231003100LOAD 1,120LOAD 1,120頁(yè)式管理地址轉(zhuǎn)換示意圖頁(yè)式管理地址轉(zhuǎn)換示意圖p pd d控制寄存器控制寄存器內(nèi)存內(nèi)存地址越界比較地址越界比較操作系統(tǒng)講義之五 注：注： 實(shí)際的地址轉(zhuǎn)換工作是計(jì)算機(jī)系統(tǒng)內(nèi)部采用硬件實(shí)際的地址轉(zhuǎn)換工作是計(jì)算機(jī)系統(tǒng)內(nèi)部采用硬件機(jī)制完

17、成的，即由機(jī)制完成的，即由地址轉(zhuǎn)換機(jī)構(gòu)地址轉(zhuǎn)換機(jī)構(gòu)MMU(Memory Management Unit)自動(dòng)完成的，自動(dòng)完成的，MMU是內(nèi)存管是內(nèi)存管理單元的意思，它是由中央處理器理單元的意思，它是由中央處理器CPU用來(lái)管用來(lái)管理虛擬存儲(chǔ)器、物理存儲(chǔ)器的控制線(xiàn)路，同時(shí)理虛擬存儲(chǔ)器、物理存儲(chǔ)器的控制線(xiàn)路，同時(shí)也負(fù)責(zé)虛地址映射到物理地址的映射。也負(fù)責(zé)虛地址映射到物理地址的映射。操作系統(tǒng)講義之五1. 虛地址以十進(jìn)制數(shù)給出虛地址以十進(jìn)制數(shù)給出v頁(yè)號(hào)：頁(yè)號(hào)： PINT(虛地址虛地址 / 頁(yè)大小頁(yè)大小) 取整數(shù)取整數(shù)部分部分v位移量：位移量： W虛地址虛地址MOD 頁(yè)大小頁(yè)大小 或或 W虛地址虛地址 %

18、頁(yè)大小頁(yè)大小 取余數(shù)取余數(shù)v根據(jù)題意產(chǎn)生頁(yè)表；根據(jù)題意產(chǎn)生頁(yè)表；v以頁(yè)號(hào)查頁(yè)表，得到對(duì)應(yīng)頁(yè)裝入內(nèi)存的塊號(hào)以頁(yè)號(hào)查頁(yè)表，得到對(duì)應(yīng)頁(yè)裝入內(nèi)存的塊號(hào)v計(jì)算機(jī)公式內(nèi)存地址塊號(hào)計(jì)算機(jī)公式內(nèi)存地址塊號(hào)頁(yè)大小位移量頁(yè)大小位移量頁(yè)式地址映射小結(jié)頁(yè)式地址映射小結(jié)操作系統(tǒng)講義之五2. 虛地址虛地址(邏輯地址、相對(duì)地址邏輯地址、相對(duì)地址)以十六進(jìn)制以十六進(jìn)制、八進(jìn)、八進(jìn)制、二進(jìn)制的形式給出制、二進(jìn)制的形式給出v將虛地址轉(zhuǎn)換成二進(jìn)制的數(shù)；將虛地址轉(zhuǎn)換成二進(jìn)制的數(shù)；v按頁(yè)的大小分離出按頁(yè)的大小分離出頁(yè)號(hào)頁(yè)號(hào)和和位移量位移量(高位部分是頁(yè)高位部分是頁(yè)號(hào)，低位部分是位移量號(hào)，低位部分是位移量)；v將低位部分將低位部分位移量

19、直接復(fù)制到位移量直接復(fù)制到內(nèi)存地址寄內(nèi)存地址寄存器存器的低位部分；的低位部分；v根據(jù)頁(yè)號(hào)查頁(yè)表，得到該頁(yè)裝入內(nèi)存的物理塊根據(jù)頁(yè)號(hào)查頁(yè)表，得到該頁(yè)裝入內(nèi)存的物理塊號(hào)，號(hào)，并將塊號(hào)轉(zhuǎn)換成二進(jìn)制數(shù)填入地址寄存器并將塊號(hào)轉(zhuǎn)換成二進(jìn)制數(shù)填入地址寄存器的高位部分的高位部分，從而形成內(nèi)存地址。從而形成內(nèi)存地址。操作系統(tǒng)講義之五十六進(jìn)制十六進(jìn)制(參考參考)：0000 = 00001 = 10010 = 20011 = 30100 = 40101 = 50110 = 60111 = 71000 = 8 1001 = 91010 = A1011 = B1100 = C1101 = D1110 = E1111 =

20、F記憶：記憶：210=1K 211=2K 212=4K 213=8K 214=16K 215=32K 216=64K .操作系統(tǒng)講義之五例例1：有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大?。河幸幌到y(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大小是是8KB，頁(yè)大小為，頁(yè)大小為2KB，依次裝入內(nèi)存的第，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地轉(zhuǎn)換成內(nèi)存地址。址。解答解答: （1）虛地址）虛地址 7145PINT(7145/2048) 3 (對(duì)應(yīng)對(duì)應(yīng)物理塊物理塊5)W7145 mod 2048 1001MR=5*2048+1001=11241虛地址虛地址7145的內(nèi)存地址

21、是：的內(nèi)存地址是：11241操作系統(tǒng)講義之五（2）虛地址）虛地址 3412 PINT(3412/2048) 1 (對(duì)應(yīng)物對(duì)應(yīng)物理塊理塊9) W3412mod 2048 1364 MR=9*2048+1364=19796 虛地址虛地址3412的內(nèi)存地址是：的內(nèi)存地址是：19796操作系統(tǒng)講義之五例例2：某虛擬存儲(chǔ)器的用戶(hù)空間共：某虛擬存儲(chǔ)器的用戶(hù)空間共32個(gè)頁(yè)面?zhèn)€頁(yè)面，每頁(yè)每頁(yè)1KB，主存，主存16KB，假設(shè)某時(shí)刻系統(tǒng)為用，假設(shè)某時(shí)刻系統(tǒng)為用戶(hù)的戶(hù)的0、1、2、3頁(yè)分配的物理塊為頁(yè)分配的物理塊為5、10、4、7，而該用戶(hù)作業(yè)的長(zhǎng)度為而該用戶(hù)作業(yè)的長(zhǎng)度為6頁(yè)頁(yè)，試將十六進(jìn)，試將十六進(jìn)制的虛地址制的

22、虛地址0A5C、103C、1A5C轉(zhuǎn)換成物理轉(zhuǎn)換成物理地址。地址。解答：解答： 用戶(hù)空間用戶(hù)空間(邏輯地址空間邏輯地址空間)為為32*1KB=32KB，因因 215=32KB，故邏輯地址編碼為，故邏輯地址編碼為15位，頁(yè)面位，頁(yè)面為為1KB(210KB)，所以頁(yè)號(hào)用，所以頁(yè)號(hào)用5位，頁(yè)內(nèi)地址位，頁(yè)內(nèi)地址用用10位。位。操作系統(tǒng)講義之五（1） 0A5C 0A5C=000 1010 0101 1100 P=2，W= 10 0101 1100 MR = 001 0010 0101 1100 = 125CH（2） 103C 103C=001 0000 0011 1100 P=4, W=00 0011

23、1100 頁(yè)號(hào)為頁(yè)號(hào)為4，合法，但該頁(yè)未裝入主存，故產(chǎn)生，合法，但該頁(yè)未裝入主存，故產(chǎn)生缺頁(yè)中斷；缺頁(yè)中斷；（3） 1A5C 1A5C=001 1010 0101 1100 P=6，因，因該用戶(hù)該用戶(hù)作業(yè)的長(zhǎng)度為作業(yè)的長(zhǎng)度為6頁(yè)頁(yè)(05)，故產(chǎn)生地址越界中斷。，故產(chǎn)生地址越界中斷。操作系統(tǒng)講義之五一道考研題一道考研題 西北工業(yè)大學(xué)（西北工業(yè)大學(xué)（20022002）v設(shè)有設(shè)有8頁(yè)的邏輯空間，每頁(yè)有頁(yè)的邏輯空間，每頁(yè)有1024字節(jié)字節(jié)(1KB)，它們被映射到，它們被映射到32塊的物理存儲(chǔ)區(qū)中，那么邏輯地址的有效位是（）位，物理地塊的物理存儲(chǔ)區(qū)中，那么邏輯地址的有效位是（）位，物理地址至少是（）位。

24、址至少是（）位。分析：分析：v邏輯地址有兩個(gè)部分組成：頁(yè)號(hào)和頁(yè)內(nèi)偏移地址。邏輯空間有邏輯地址有兩個(gè)部分組成：頁(yè)號(hào)和頁(yè)內(nèi)偏移地址。邏輯空間有8 （23）頁(yè)，說(shuō)明頁(yè)號(hào)需要）頁(yè)，說(shuō)明頁(yè)號(hào)需要3位二進(jìn)制位編碼，而每頁(yè)有位二進(jìn)制位編碼，而每頁(yè)有1024（210）字節(jié)，說(shuō)明頁(yè)內(nèi)偏移地址需要）字節(jié)，說(shuō)明頁(yè)內(nèi)偏移地址需要10位二進(jìn)制位編碼，因此位二進(jìn)制位編碼，因此邏輯地址的有效位為邏輯地址的有效位為3+10=13位。位。v因?yàn)槲锢淼刂放c邏輯地址的頁(yè)面大小相同，而物理存儲(chǔ)塊為因?yàn)槲锢淼刂放c邏輯地址的頁(yè)面大小相同，而物理存儲(chǔ)塊為32（25）占）占5位，所以物理地址至少為位，所以物理地址至少為5+10=15位位內(nèi)存

25、有內(nèi)存有32個(gè)物理塊，物理塊大小與邏輯塊大小相同，故物理地址個(gè)物理塊，物理塊大小與邏輯塊大小相同，故物理地址空間為空間為32*1KB=32KB。因?yàn)?。因?yàn)?15=32768B=32768/1024=32KB，故，故物理地址至少為物理地址至少為15位。位。操作系統(tǒng)講義之五4. 4. 聯(lián)想寄存器和快表聯(lián)想寄存器和快表v聯(lián)想寄存器：可按內(nèi)容聯(lián)想寄存器：可按內(nèi)容并行查找并行查找的快速寄存器。的快速寄存器。比內(nèi)存貴、容量小。比內(nèi)存貴、容量小。v引入原因：頁(yè)表駐留內(nèi)存，執(zhí)行訪(fǎng)內(nèi)指令要先引入原因：頁(yè)表駐留內(nèi)存，執(zhí)行訪(fǎng)內(nèi)指令要先到內(nèi)存查頁(yè)表，進(jìn)行地址轉(zhuǎn)換后才能進(jìn)行訪(fǎng)內(nèi)到內(nèi)存查頁(yè)表，進(jìn)行地址轉(zhuǎn)換后才能進(jìn)行訪(fǎng)內(nèi)操

26、作，操作，因此執(zhí)行一條指令至少要訪(fǎng)問(wèn)內(nèi)存兩次因此執(zhí)行一條指令至少要訪(fǎng)問(wèn)內(nèi)存兩次v為提高速度，將內(nèi)存頁(yè)表為提高速度，將內(nèi)存頁(yè)表( (也稱(chēng)慢表也稱(chēng)慢表) )中一部分中一部分經(jīng)常使用頁(yè)的頁(yè)號(hào)和頁(yè)面號(hào)等內(nèi)容放在聯(lián)想寄經(jīng)常使用頁(yè)的頁(yè)號(hào)和頁(yè)面號(hào)等內(nèi)容放在聯(lián)想寄存器中存器中( (稱(chēng)為快表稱(chēng)為快表) )。操作系統(tǒng)講義之五具有快表的地址轉(zhuǎn)換：具有快表的地址轉(zhuǎn)換：v每次訪(fǎng)問(wèn)主存時(shí)，首先查找每次訪(fǎng)問(wèn)主存時(shí)，首先查找快表快表，若找到所需，若找到所需的頁(yè)，則快速形成物理地址。的頁(yè)，則快速形成物理地址。v否則從否則從頁(yè)表頁(yè)表(慢表慢表)中查找后形成物理地址，同時(shí)中查找后形成物理地址，同時(shí)把該頁(yè)寫(xiě)入快表中。如果設(shè)計(jì)得當(dāng)，快

27、表的命把該頁(yè)寫(xiě)入快表中。如果設(shè)計(jì)得當(dāng)，快表的命中率可以很高。中率可以很高。操作系統(tǒng)講義之五具有快表的地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu)頁(yè)表寄存器頁(yè)表寄存器頁(yè)表始址頁(yè)表始址頁(yè)表長(zhǎng)度頁(yè)表長(zhǎng)度頁(yè)號(hào)頁(yè)號(hào)頁(yè)內(nèi)地址頁(yè)內(nèi)地址邏輯地址邏輯地址L L越界中斷越界中斷塊號(hào)塊號(hào)b頁(yè)表頁(yè)表頁(yè)號(hào)頁(yè)號(hào)頁(yè)號(hào)頁(yè)號(hào)輸輸入入寄寄存存器器塊號(hào)塊號(hào)bb快表快表d物理地址物理地址操作系統(tǒng)講義之五這就意味著，在為一個(gè)進(jìn)程分配內(nèi)存空間時(shí)，除了給進(jìn)程本身這就意味著，在為一個(gè)進(jìn)程分配內(nèi)存空間時(shí)，除了給進(jìn)程本身分配內(nèi)存空間外，還需要另外提供分配內(nèi)存空間外，還需要另外提供4MB的一塊連續(xù)內(nèi)存空間存的一塊連續(xù)內(nèi)存空間存放對(duì)應(yīng)的頁(yè)表。因?yàn)槊總€(gè)進(jìn)程都要

28、有自己的頁(yè)表，這就需要更放對(duì)應(yīng)的頁(yè)表。因?yàn)槊總€(gè)進(jìn)程都要有自己的頁(yè)表，這就需要更大存儲(chǔ)空間來(lái)存放頁(yè)表。大存儲(chǔ)空間來(lái)存放頁(yè)表。5. 兩級(jí)和多級(jí)頁(yè)表兩級(jí)和多級(jí)頁(yè)表-補(bǔ)充補(bǔ)充 CPU具有具有32位地址時(shí)，使用位地址時(shí)，使用232邏輯地址空間的分頁(yè)系統(tǒng)，規(guī)定邏輯地址空間的分頁(yè)系統(tǒng)，規(guī)定頁(yè)面頁(yè)面4KB時(shí)，時(shí)，每個(gè)進(jìn)程頁(yè)表的表項(xiàng)最多有每個(gè)進(jìn)程頁(yè)表的表項(xiàng)最多有1M個(gè)，即頁(yè)表最多個(gè)，即頁(yè)表最多有有1M行行（？）（？），若每個(gè)頁(yè)表項(xiàng)占用，若每個(gè)頁(yè)表項(xiàng)占用4個(gè)字節(jié)，則每個(gè)進(jìn)程需要個(gè)字節(jié)，則每個(gè)進(jìn)程需要占用占用4MB連續(xù)內(nèi)存空間存放頁(yè)表連續(xù)內(nèi)存空間存放頁(yè)表(即需要即需要1024個(gè)連續(xù)的內(nèi)存物個(gè)連續(xù)的內(nèi)存物理塊理塊)。

29、 解釋?zhuān)航忉專(zhuān)喉?yè)面大小為頁(yè)面大小為4KB(212KB)，故頁(yè)內(nèi)編址，故頁(yè)內(nèi)編址12位，頁(yè)號(hào)編址為位，頁(yè)號(hào)編址為: 32 12 = 20位，位，220=1048576(個(gè)個(gè))=1048576/1024=1024K(個(gè)個(gè))=1M(個(gè)個(gè)), 所以所以共有共有1M個(gè)頁(yè)表項(xiàng)。個(gè)頁(yè)表項(xiàng)。每個(gè)頁(yè)表項(xiàng)占每個(gè)頁(yè)表項(xiàng)占4個(gè)字節(jié)，故：個(gè)字節(jié)，故：1048576* *4=4194304B=4096KB=4MB操作系統(tǒng)講義之五 可以采用兩種方法來(lái)解決頁(yè)表存放問(wèn)題：可以采用兩種方法來(lái)解決頁(yè)表存放問(wèn)題： 采用離散分配方式來(lái)解決難以找到一塊連續(xù)的內(nèi)存空間的采用離散分配方式來(lái)解決難以找到一塊連續(xù)的內(nèi)存空間的 問(wèn)題問(wèn)題; 只將當(dāng)

30、前需要的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存，其余的頁(yè)表項(xiàng)駐留只將當(dāng)前需要的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存，其余的頁(yè)表項(xiàng)駐留 在磁盤(pán)上，需要時(shí)再調(diào)入。在磁盤(pán)上，需要時(shí)再調(diào)入。 采用此方法解決采用此方法解決操作系統(tǒng)講義之五1）兩級(jí)頁(yè)表）兩級(jí)頁(yè)表(Two-Level Page Table)兩級(jí)頁(yè)表機(jī)制的做法是：兩級(jí)頁(yè)表機(jī)制的做法是：把整個(gè)頁(yè)表進(jìn)行分頁(yè)，即將整個(gè)頁(yè)表拆分成一把整個(gè)頁(yè)表進(jìn)行分頁(yè)，即將整個(gè)頁(yè)表拆分成一張張小頁(yè)表張張小頁(yè)表(稱(chēng)為頁(yè)表頁(yè)稱(chēng)為頁(yè)表頁(yè)) ,小頁(yè)表小頁(yè)表的大小與的大小與頁(yè)框頁(yè)框大大小相同小相同，然后再為這些小頁(yè)表再建一張表，稱(chēng)為，然后再為這些小頁(yè)表再建一張表，稱(chēng)為外層頁(yè)表外層頁(yè)表( (也稱(chēng)也稱(chēng)頁(yè)目錄表頁(yè)目錄表)

31、 )，外層頁(yè)表存放每個(gè)小，外層頁(yè)表存放每個(gè)小頁(yè)表對(duì)應(yīng)的頁(yè)表對(duì)應(yīng)的內(nèi)存物理塊號(hào)內(nèi)存物理塊號(hào)。操作系統(tǒng)講義之五1011107801217421023第第0頁(yè)頁(yè)表頁(yè)頁(yè)表1460121023第第 1 頁(yè)頁(yè)表頁(yè)頁(yè)表114115011023012345671141151468第第1023 頁(yè)頁(yè)表頁(yè)頁(yè)存空間內(nèi)存空間兩級(jí)頁(yè)表結(jié)構(gòu)兩級(jí)頁(yè)表結(jié)構(gòu)一個(gè)內(nèi)存物理塊為一個(gè)內(nèi)存物理塊為1KB。本例將頁(yè)表。本例將頁(yè)表拆分成拆分成1024個(gè)小頁(yè)個(gè)小頁(yè)表。表。頁(yè)目錄表頁(yè)目錄表操作系統(tǒng)講義之五v由上圖可知，在頁(yè)表的每個(gè)表項(xiàng)中存放的是進(jìn)由上圖可知，在頁(yè)表的每個(gè)表項(xiàng)中存放的是進(jìn)程的某頁(yè)在內(nèi)存的物理塊號(hào)，如第程

32、的某頁(yè)在內(nèi)存的物理塊號(hào)，如第0頁(yè)存放在第頁(yè)存放在第1個(gè)物理塊中，第個(gè)物理塊中，第1頁(yè)存放在第頁(yè)存放在第4個(gè)物理塊中。而個(gè)物理塊中。而在在外層頁(yè)表的每個(gè)表項(xiàng)中外層頁(yè)表的每個(gè)表項(xiàng)中，所存放的是某頁(yè)表，所存放的是某頁(yè)表分頁(yè)的首址，如分頁(yè)的首址，如第第0號(hào)小頁(yè)表號(hào)小頁(yè)表是存放在第是存放在第1011物物理塊中，理塊中，第第1號(hào)小頁(yè)表號(hào)小頁(yè)表是存放在第是存放在第1078物理塊中物理塊中等。等。操作系統(tǒng)講義之五在兩級(jí)頁(yè)表時(shí)，指令所給出的地址分為三部分：在兩級(jí)頁(yè)表時(shí)，指令所給出的地址分為三部分：（ 外層頁(yè)號(hào)，外層頁(yè)內(nèi)地址，頁(yè)內(nèi)地址）外層頁(yè)號(hào)，外層頁(yè)內(nèi)地址，頁(yè)內(nèi)地址）邏輯地址結(jié)構(gòu)可描述如下邏輯地址結(jié)構(gòu)可描述如下

33、( (上述例子的邏輯地址結(jié)構(gòu)上述例子的邏輯地址結(jié)構(gòu)) )：1）外層頁(yè)號(hào)用）外層頁(yè)號(hào)用10位，位， 210=1024B (將頁(yè)表拆分為將頁(yè)表拆分為1024個(gè)個(gè) 小頁(yè)小頁(yè))2）外層頁(yè)內(nèi)地址用）外層頁(yè)內(nèi)地址用10位，位， 210=1024B （每個(gè)小頁(yè)表為（每個(gè)小頁(yè)表為1024B）3）頁(yè)內(nèi)地址用）頁(yè)內(nèi)地址用12位，位， 212=4096B=4KB操作系統(tǒng)講義之五具有兩級(jí)頁(yè)表的地址變換機(jī)構(gòu)具有兩級(jí)頁(yè)表的地址變換機(jī)構(gòu)頁(yè)目錄號(hào)頁(yè)目錄號(hào)頁(yè)號(hào)頁(yè)號(hào)頁(yè)內(nèi)地址頁(yè)內(nèi)地址p1p2d邏輯地址邏輯地址+外部頁(yè)表寄存器外部頁(yè)表寄存器頁(yè)目錄號(hào)頁(yè)目錄號(hào)+db頁(yè)表頁(yè)表物理地址物理地址b二級(jí)頁(yè)表地址變換需三次訪(fǎng)問(wèn)主存二級(jí)頁(yè)表地址變換

34、需三次訪(fǎng)問(wèn)主存：一次訪(fǎng)問(wèn)頁(yè)目錄、一次：一次訪(fǎng)問(wèn)頁(yè)目錄、一次訪(fǎng)問(wèn)頁(yè)表頁(yè)、一次訪(fǎng)問(wèn)指令或數(shù)據(jù)。訪(fǎng)問(wèn)頁(yè)表頁(yè)、一次訪(fǎng)問(wèn)指令或數(shù)據(jù)。操作系統(tǒng)講義之五虛擬地址虛擬地址二級(jí)頁(yè)表結(jié)構(gòu)及地址映射二級(jí)頁(yè)表結(jié)構(gòu)及地址映射頁(yè)表地址頁(yè)表地址.頁(yè)目錄頁(yè)目錄(每進(jìn)程一個(gè)每進(jìn)程一個(gè))塊號(hào)塊號(hào).頁(yè)表頁(yè)表代碼或數(shù)據(jù)代碼或數(shù)據(jù).內(nèi)存塊內(nèi)存塊+頁(yè)目錄地址頁(yè)目錄地址外層頁(yè)號(hào)外層頁(yè)號(hào)頁(yè)表位移頁(yè)表位移頁(yè)位移頁(yè)位移操作系統(tǒng)講義之五2) 多級(jí)頁(yè)表（多級(jí)頁(yè)表（略略） 對(duì)于對(duì)于32位的機(jī)器，采用兩級(jí)頁(yè)表結(jié)構(gòu)是合適位的機(jī)器，采用兩級(jí)頁(yè)表結(jié)構(gòu)是合適的；的； 對(duì)于對(duì)于64位的機(jī)器，如果頁(yè)面大小仍采用位的機(jī)器，如果頁(yè)面大小仍采用4KB(即即212KB)，

35、那么還剩下那么還剩下52位，位， 假定仍按物假定仍按物理塊的大小理塊的大小(212位位)來(lái)劃分頁(yè)表，則將余下的來(lái)劃分頁(yè)表，則將余下的42位位用于頁(yè)號(hào)。此時(shí)在頁(yè)表中可能有用于頁(yè)號(hào)。此時(shí)在頁(yè)表中可能有4096 G個(gè)頁(yè)表個(gè)頁(yè)表項(xiàng)項(xiàng)(242= 4096 G)， 要占用要占用16384 GB的連續(xù)內(nèi)存的連續(xù)內(nèi)存空間?？臻g。 操作系統(tǒng)講義之五 必須采用多級(jí)頁(yè)表，將頁(yè)目錄號(hào)表表再為頁(yè)目錄必須采用多級(jí)頁(yè)表，將頁(yè)目錄號(hào)表表再為頁(yè)目錄號(hào)表，也是將各分頁(yè)離散地裝入到不相鄰接的號(hào)表，也是將各分頁(yè)離散地裝入到不相鄰接的物理塊中，再利用第物理塊中，再利用第2級(jí)的外層頁(yè)表來(lái)映射它們級(jí)的外層頁(yè)表來(lái)映射它們之間的關(guān)系。之間的關(guān)

36、系。操作系統(tǒng)講義之五一道考研題一道考研題 （東南大學(xué)（東南大學(xué)2001)2001)v判斷題：虛擬存儲(chǔ)器是一個(gè)虛假的地址空間，因而這個(gè)地判斷題：虛擬存儲(chǔ)器是一個(gè)虛假的地址空間，因而這個(gè)地址空間的大小是沒(méi)有限制的（址空間的大小是沒(méi)有限制的（ ）v分析：在虛擬存儲(chǔ)器中，用戶(hù)的地址空間仍然受到地址字分析：在虛擬存儲(chǔ)器中，用戶(hù)的地址空間仍然受到地址字長(zhǎng)和外存容量的限制。虛擬存儲(chǔ)器的長(zhǎng)和外存容量的限制。虛擬存儲(chǔ)器的最大容量受地址長(zhǎng)度最大容量受地址長(zhǎng)度（地址總線(xiàn)位數(shù)）決定，一個(gè)（地址總線(xiàn)位數(shù)）決定，一個(gè)擁有擁有32位地址長(zhǎng)度的系統(tǒng)位地址長(zhǎng)度的系統(tǒng)，其虛擬內(nèi)存最大為其虛擬內(nèi)存最大為232字節(jié)。當(dāng)然，一個(gè)字節(jié)。

37、當(dāng)然，一個(gè)實(shí)際的虛擬存儲(chǔ)器實(shí)際的虛擬存儲(chǔ)器的大小還會(huì)受到輔助存儲(chǔ)器大小的限制。的大小還會(huì)受到輔助存儲(chǔ)器大小的限制。v答案答案 錯(cuò)錯(cuò)操作系統(tǒng)講義之五選擇題選擇題v一個(gè)計(jì)算機(jī)系統(tǒng)的虛擬存儲(chǔ)器的最大容量是由（）確定的，一個(gè)計(jì)算機(jī)系統(tǒng)的虛擬存儲(chǔ)器的最大容量是由（）確定的，其實(shí)際容量是由（其實(shí)際容量是由（B）確定的。）確定的。vA、：、： 計(jì)算機(jī)字長(zhǎng)；計(jì)算機(jī)字長(zhǎng)； 內(nèi)存容量；內(nèi)存容量； 硬盤(pán)容量；硬盤(pán)容量； 內(nèi)存和硬盤(pán)容量之和；內(nèi)存和硬盤(pán)容量之和； 計(jì)算機(jī)的地址結(jié)構(gòu)。計(jì)算機(jī)的地址結(jié)構(gòu)。v答案：答案： 、操作系統(tǒng)講義之五v2010考研題考研題：某計(jì)算機(jī)采用二級(jí)頁(yè)表的分頁(yè)存儲(chǔ)管理方式，：某計(jì)算機(jī)采用二級(jí)頁(yè)表

38、的分頁(yè)存儲(chǔ)管理方式，按字節(jié)編址，頁(yè)大小為按字節(jié)編址，頁(yè)大小為210字節(jié)（字節(jié)（1K），頁(yè)表項(xiàng)大小為），頁(yè)表項(xiàng)大小為2字節(jié)，字節(jié)，邏輯地址結(jié)構(gòu)為：邏輯地址結(jié)構(gòu)為： , 邏輯地址邏輯地址空間大小為空間大小為216頁(yè)，則表示整個(gè)邏輯地址空間的頁(yè)目錄表中包頁(yè)，則表示整個(gè)邏輯地址空間的頁(yè)目錄表中包含表項(xiàng)的個(gè)數(shù)至少是含表項(xiàng)的個(gè)數(shù)至少是 A. 64 B. 128C. 256 D. 512解：邏輯地址空間為解：邏輯地址空間為216頁(yè)，頁(yè)表項(xiàng)為頁(yè)，頁(yè)表項(xiàng)為2個(gè)字節(jié)，故頁(yè)表長(zhǎng)度為個(gè)字節(jié)，故頁(yè)表長(zhǎng)度為 216 2=128KB，一個(gè)內(nèi)存物理塊存放，一個(gè)內(nèi)存物理塊存放1KB，故，故 128KB/1KB=128，即得頁(yè)目

39、錄表，即得頁(yè)目錄表(外層頁(yè)表外層頁(yè)表)至少包含至少包含 128個(gè)表項(xiàng)。個(gè)表項(xiàng)。 頁(yè)目錄號(hào)頁(yè)目錄號(hào) 頁(yè)號(hào)頁(yè)號(hào) 頁(yè)內(nèi)偏移量頁(yè)內(nèi)偏移量操作系統(tǒng)講義之五6. 6. 信息的共享和保護(hù)信息的共享和保護(hù)v信息共享：允許進(jìn)程的地址空間在內(nèi)存中非連續(xù)信息共享：允許進(jìn)程的地址空間在內(nèi)存中非連續(xù)存放，使得多個(gè)進(jìn)程可共享某些頁(yè)面。存放，使得多個(gè)進(jìn)程可共享某些頁(yè)面。但共享代但共享代碼頁(yè)面受限制碼頁(yè)面受限制。為什么？為什么？v信息保護(hù)：信息保護(hù)：進(jìn)行地址轉(zhuǎn)換時(shí)，檢查是否超頁(yè)進(jìn)行地址轉(zhuǎn)換時(shí)，檢查是否超頁(yè)（邏輯頁(yè)和（邏輯頁(yè)和頁(yè)表控制寄存器中頁(yè)表長(zhǎng)度相比頁(yè)表控制寄存器中頁(yè)表長(zhǎng)度相比)；在頁(yè)表中設(shè)置存取權(quán)限項(xiàng)。在頁(yè)表中設(shè)置存取權(quán)

40、限項(xiàng)。操作系統(tǒng)講義之五7.存儲(chǔ)頁(yè)面表存儲(chǔ)頁(yè)面表 存儲(chǔ)頁(yè)面表是整個(gè)系統(tǒng)的一張表，存儲(chǔ)頁(yè)面表存儲(chǔ)頁(yè)面表是整個(gè)系統(tǒng)的一張表，存儲(chǔ)頁(yè)面表指出內(nèi)存各頁(yè)面是否已被分配出去指出內(nèi)存各頁(yè)面是否已被分配出去, 以及未分配以及未分配頁(yè)面的總數(shù)。存儲(chǔ)頁(yè)面表也有兩種構(gòu)成方法。頁(yè)面的總數(shù)。存儲(chǔ)頁(yè)面表也有兩種構(gòu)成方法。（1）位示圖）位示圖 一種是一種是在內(nèi)存中劃分一塊固定區(qū)域在內(nèi)存中劃分一塊固定區(qū)域，每個(gè)單元，每個(gè)單元的每個(gè)比特代表一個(gè)頁(yè)面。如果該頁(yè)面已被分的每個(gè)比特代表一個(gè)頁(yè)面。如果該頁(yè)面已被分配，則對(duì)應(yīng)比特位置配，則對(duì)應(yīng)比特位置1，否則置，否則置0。這種方法稱(chēng)。這種方法稱(chēng)為位示圖法。如下圖所示。為位示圖法。如下圖所示

41、。操作系統(tǒng)講義之五位示圖位示圖操作系統(tǒng)講義之五（2）空閑頁(yè)面鏈空閑頁(yè)面鏈 存儲(chǔ)頁(yè)面表的另一種構(gòu)成辦法是采用空閑頁(yè)存儲(chǔ)頁(yè)面表的另一種構(gòu)成辦法是采用空閑頁(yè)面鏈的方法。在空閑頁(yè)面鏈中，隊(duì)首頁(yè)面的第一面鏈的方法。在空閑頁(yè)面鏈中，隊(duì)首頁(yè)面的第一個(gè)單元和第二個(gè)單元分別放入空閑頁(yè)面總數(shù)與指?jìng)€(gè)單元和第二個(gè)單元分別放入空閑頁(yè)面總數(shù)與指向下一個(gè)空閑頁(yè)面的指針。其他頁(yè)面的第一個(gè)單向下一個(gè)空閑頁(yè)面的指針。其他頁(yè)面的第一個(gè)單元中則分別放入指向下一個(gè)頁(yè)面的指針?？臻e頁(yè)元中則分別放入指向下一個(gè)頁(yè)面的指針?？臻e頁(yè)面鏈的方法由于使用了空閑頁(yè)面本身的單元存放面鏈的方法由于使用了空閑頁(yè)面本身的單元存放指針，因此不占據(jù)額外的內(nèi)存空間

42、。指針，因此不占據(jù)額外的內(nèi)存空間。操作系統(tǒng)講義之五二、二、動(dòng)態(tài)頁(yè)式管理動(dòng)態(tài)頁(yè)式管理1. 引入原因引入原因 在靜態(tài)頁(yè)式存儲(chǔ)管理中，要求把進(jìn)程地址空間的全在靜態(tài)頁(yè)式存儲(chǔ)管理中，要求把進(jìn)程地址空間的全部頁(yè)都要裝入內(nèi)存才能運(yùn)行。部頁(yè)都要裝入內(nèi)存才能運(yùn)行。而在實(shí)際中一個(gè)作業(yè)而在實(shí)際中一個(gè)作業(yè)的某些部分可能在運(yùn)行過(guò)程中是用不到的，比如：的某些部分可能在運(yùn)行過(guò)程中是用不到的，比如：如果沒(méi)有錯(cuò)誤的發(fā)生，錯(cuò)誤處理模塊就不會(huì)被調(diào)用。如果沒(méi)有錯(cuò)誤的發(fā)生，錯(cuò)誤處理模塊就不會(huì)被調(diào)用。因此，在靜態(tài)頁(yè)式管理中會(huì)將一些不需要的頁(yè)也裝因此，在靜態(tài)頁(yè)式管理中會(huì)將一些不需要的頁(yè)也裝入內(nèi)存入內(nèi)存,而且內(nèi)存資源不足時(shí)而且內(nèi)存資源不足時(shí)

43、,該作業(yè)或進(jìn)程將無(wú)法運(yùn)該作業(yè)或進(jìn)程將無(wú)法運(yùn)行。行。2. 動(dòng)態(tài)頁(yè)式管理的主要思想動(dòng)態(tài)頁(yè)式管理的主要思想: 在作業(yè)或進(jìn)程開(kāi)始運(yùn)行前，在作業(yè)或進(jìn)程開(kāi)始運(yùn)行前，只將被認(rèn)為是經(jīng)常被反只將被認(rèn)為是經(jīng)常被反復(fù)執(zhí)行和調(diào)用的部分裝入內(nèi)存，而其它部分在執(zhí)行復(fù)執(zhí)行和調(diào)用的部分裝入內(nèi)存，而其它部分在執(zhí)行過(guò)程中動(dòng)態(tài)的調(diào)入。即：通過(guò)交換的技術(shù)以小的內(nèi)過(guò)程中動(dòng)態(tài)的調(diào)入。即：通過(guò)交換的技術(shù)以小的內(nèi)存運(yùn)行大的作業(yè)。存運(yùn)行大的作業(yè)。操作系統(tǒng)講義之五3. 有兩種動(dòng)態(tài)裝入方式有兩種動(dòng)態(tài)裝入方式 (1)(1) 請(qǐng)求頁(yè)式管理請(qǐng)求頁(yè)式管理 當(dāng)發(fā)現(xiàn)欲執(zhí)行的某條指令或數(shù)據(jù)不在內(nèi)存時(shí)，當(dāng)發(fā)現(xiàn)欲執(zhí)行的某條指令或數(shù)據(jù)不在內(nèi)存時(shí)，發(fā)生缺頁(yè)中斷，由系統(tǒng)

44、將外存的頁(yè)面調(diào)入內(nèi)發(fā)生缺頁(yè)中斷，由系統(tǒng)將外存的頁(yè)面調(diào)入內(nèi)存存(軟件實(shí)現(xiàn)軟件實(shí)現(xiàn))。 (2)(2) 預(yù)調(diào)入方管理預(yù)調(diào)入方管理 系統(tǒng)對(duì)那些在外存中的頁(yè)進(jìn)行調(diào)入順序計(jì)算，系統(tǒng)對(duì)那些在外存中的頁(yè)進(jìn)行調(diào)入順序計(jì)算，估計(jì)出這些頁(yè)中指令和數(shù)據(jù)的執(zhí)行和被訪(fǎng)問(wèn)估計(jì)出這些頁(yè)中指令和數(shù)據(jù)的執(zhí)行和被訪(fǎng)問(wèn)的順序，并按此順序事先將它們順序調(diào)入和的順序，并按此順序事先將它們順序調(diào)入和調(diào)出內(nèi)存。調(diào)出內(nèi)存。 4. 請(qǐng)求頁(yè)式管理需要解決的問(wèn)題請(qǐng)求頁(yè)式管理需要解決的問(wèn)題操作系統(tǒng)講義之五 (1) 如何發(fā)現(xiàn)頁(yè)是否在內(nèi)存如何發(fā)現(xiàn)頁(yè)是否在內(nèi)存 可以用擴(kuò)充頁(yè)表的方法解決，即除了頁(yè)號(hào)、頁(yè)面號(hào)外，再增可以用擴(kuò)充頁(yè)表的方法解決，即除了頁(yè)號(hào)、頁(yè)面號(hào)

45、外，再增加該頁(yè)是否在內(nèi)存的加該頁(yè)是否在內(nèi)存的標(biāo)志位標(biāo)志位及該頁(yè)在及該頁(yè)在外存的起始地址外存的起始地址。擴(kuò)充。擴(kuò)充后的頁(yè)表如下：后的頁(yè)表如下：頁(yè)號(hào)頁(yè)號(hào) 頁(yè)面號(hào)頁(yè)面號(hào) 標(biāo)志位標(biāo)志位 外存始址外存始址 0 8 0 8 Y 1 20 1 20 Y 2 - 2 - N 3 - 3 - N (2) (2) 如何處理缺頁(yè)問(wèn)題如何處理缺頁(yè)問(wèn)題 關(guān)于某頁(yè)不在內(nèi)存時(shí)的處理涉及兩個(gè)問(wèn)題：關(guān)于某頁(yè)不在內(nèi)存時(shí)的處理涉及兩個(gè)問(wèn)題： 采用何種方法把所缺的頁(yè)調(diào)入內(nèi)存；采用何種方法把所缺的頁(yè)調(diào)入內(nèi)存； 如果內(nèi)存沒(méi)有空閑頁(yè)面，把調(diào)進(jìn)來(lái)的頁(yè)放在什么地如果內(nèi)存沒(méi)有空閑頁(yè)面，把調(diào)進(jìn)來(lái)的頁(yè)放在什么地 方方( (如何淘汰頁(yè)的問(wèn)題如何淘汰頁(yè)

46、的問(wèn)題) )。操作系統(tǒng)講義之五v采用什么策略淘汰頁(yè)采用什么策略淘汰頁(yè)(后面詳細(xì)講后面詳細(xì)講)v如果內(nèi)存中的某頁(yè)被淘汰，有兩種情況：其一是該頁(yè)在程序如果內(nèi)存中的某頁(yè)被淘汰，有兩種情況：其一是該頁(yè)在程序運(yùn)行時(shí)被修改過(guò)；其二是沒(méi)被修改。如果被修改過(guò)，淘汰時(shí)運(yùn)行時(shí)被修改過(guò)；其二是沒(méi)被修改。如果被修改過(guò)，淘汰時(shí)應(yīng)重新寫(xiě)到外存，若未修改，則不必重新入外存應(yīng)重新寫(xiě)到外存，若未修改，則不必重新入外存( (因外存已因外存已有副本有副本) )。v問(wèn)題：如何知道被淘汰的頁(yè)是否被修改過(guò)？問(wèn)題：如何知道被淘汰的頁(yè)是否被修改過(guò)？ 可在頁(yè)表中再增加一項(xiàng)，以記錄該頁(yè)是否被修改過(guò)。增加可在頁(yè)表中再增加一項(xiàng)，以記錄該頁(yè)是否被修改

47、過(guò)。增加后的頁(yè)表如下：后的頁(yè)表如下：頁(yè)號(hào)頁(yè)號(hào) 頁(yè)面號(hào)頁(yè)面號(hào) 標(biāo)志位標(biāo)志位 改變位改變位 外存始址外存始址 修改位修改位操作系統(tǒng)講義之五5. 請(qǐng)求頁(yè)式管理中的置換算法請(qǐng)求頁(yè)式管理中的置換算法 置換算法在內(nèi)存中沒(méi)有空閑頁(yè)面時(shí)被調(diào)用。它的目的是選置換算法在內(nèi)存中沒(méi)有空閑頁(yè)面時(shí)被調(diào)用。它的目的是選出一個(gè)被淘汰的頁(yè)面。如果內(nèi)存中有足夠的空閑頁(yè)面存放所出一個(gè)被淘汰的頁(yè)面。如果內(nèi)存中有足夠的空閑頁(yè)面存放所調(diào)入的頁(yè)，則不必使用置換算法。把內(nèi)存和外存統(tǒng)一管理的調(diào)入的頁(yè)，則不必使用置換算法。把內(nèi)存和外存統(tǒng)一管理的真正目的是真正目的是把那些被訪(fǎng)問(wèn)概率非常高的頁(yè)存放在內(nèi)存中把那些被訪(fǎng)問(wèn)概率非常高的頁(yè)存放在內(nèi)存中。因。

48、因此，置換算法應(yīng)該置換那些被訪(fǎng)問(wèn)概率最低的頁(yè)，將它們移此，置換算法應(yīng)該置換那些被訪(fǎng)問(wèn)概率最低的頁(yè)，將它們移出內(nèi)存。比較常用的置換算法有以下幾種出內(nèi)存。比較常用的置換算法有以下幾種: (1)(1) 隨機(jī)淘汰算法隨機(jī)淘汰算法(RG) 在系統(tǒng)無(wú)法確定哪些頁(yè)被訪(fǎng)問(wèn)的概率較低時(shí)，隨機(jī)地選擇某在系統(tǒng)無(wú)法確定哪些頁(yè)被訪(fǎng)問(wèn)的概率較低時(shí)，隨機(jī)地選擇某個(gè)用戶(hù)的頁(yè)面并將其換出。個(gè)用戶(hù)的頁(yè)面并將其換出。操作系統(tǒng)講義之五(2) 輪轉(zhuǎn)法輪轉(zhuǎn)法(RR) 循回?fù)Q出內(nèi)存可用區(qū)內(nèi)一個(gè)可以被換出的頁(yè)面，循回?fù)Q出內(nèi)存可用區(qū)內(nèi)一個(gè)可以被換出的頁(yè)面，無(wú)論該頁(yè)是否剛被換進(jìn)或以換進(jìn)很長(zhǎng)時(shí)間。無(wú)論該頁(yè)是否剛被換進(jìn)或以換進(jìn)很長(zhǎng)時(shí)間。(3) 先進(jìn)

49、先出先進(jìn)先出(FIFO) 總是選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的一頁(yè)被換出。總是選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的一頁(yè)被換出。FIFO算法認(rèn)為先調(diào)入內(nèi)存的頁(yè)不再被訪(fǎng)問(wèn)的可算法認(rèn)為先調(diào)入內(nèi)存的頁(yè)不再被訪(fǎng)問(wèn)的可能性大，因此選擇最先調(diào)入的換出。事實(shí)上，那能性大，因此選擇最先調(diào)入的換出。事實(shí)上，那些在內(nèi)存中停留時(shí)間最長(zhǎng)的頁(yè)往往也是經(jīng)常被訪(fǎng)些在內(nèi)存中停留時(shí)間最長(zhǎng)的頁(yè)往往也是經(jīng)常被訪(fǎng)問(wèn)的頁(yè)。問(wèn)的頁(yè)。操作系統(tǒng)講義之五v假設(shè)某作業(yè)有假設(shè)某作業(yè)有5個(gè)頁(yè)面，執(zhí)行時(shí)引用的頁(yè)序列為：個(gè)頁(yè)面，執(zhí)行時(shí)引用的頁(yè)序列為：0、1、2、3、0、1、4、0、1、2、3、4 共訪(fǎng)問(wèn)共訪(fǎng)問(wèn)12個(gè)頁(yè)面，當(dāng)系統(tǒng)給該進(jìn)程個(gè)頁(yè)面，當(dāng)系統(tǒng)給該進(jìn)程3個(gè)內(nèi)存塊時(shí)，

50、個(gè)內(nèi)存塊時(shí)，F(xiàn)IFO發(fā)生發(fā)生9次缺頁(yè)中斷：次缺頁(yè)中斷：操作系統(tǒng)講義之五(4) 最佳算法最佳算法(OPT) 選擇以后不再訪(fǎng)問(wèn)的頁(yè)或經(jīng)很長(zhǎng)時(shí)間之后才可能訪(fǎng)問(wèn)的頁(yè)進(jìn)選擇以后不再訪(fǎng)問(wèn)的頁(yè)或經(jīng)很長(zhǎng)時(shí)間之后才可能訪(fǎng)問(wèn)的頁(yè)進(jìn)行淘汰。行淘汰。 例如：例如：如果一個(gè)進(jìn)程對(duì)頁(yè)面的訪(fǎng)問(wèn)序列為：如果一個(gè)進(jìn)程對(duì)頁(yè)面的訪(fǎng)問(wèn)序列為：0、1、2、3、0、1、4、0、1、2、3、4，系統(tǒng)給該進(jìn)程，系統(tǒng)給該進(jìn)程3個(gè)物理頁(yè)塊，則按照最佳個(gè)物理頁(yè)塊，則按照最佳置換算法，會(huì)產(chǎn)生置換算法，會(huì)產(chǎn)生7次缺頁(yè)中斷，缺頁(yè)中斷率為次缺頁(yè)中斷，缺頁(yè)中斷率為f= 7/12。表示缺頁(yè)中斷，表示缺頁(yè)中斷，表示無(wú)缺頁(yè)中斷表示無(wú)缺頁(yè)中斷。操作系統(tǒng)講義之五（5

51、）最近最久未使用的頁(yè)面置換算法最近最久未使用的頁(yè)面置換算法(LRU) 該算法的基本思想是該算法的基本思想是: 當(dāng)需要淘汰某一頁(yè)時(shí)，選擇當(dāng)需要淘汰某一頁(yè)時(shí)，選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒(méi)有使用過(guò)的頁(yè)離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒(méi)有使用過(guò)的頁(yè)先淘汰。該算法的主要出發(fā)點(diǎn)是，如果某頁(yè)被訪(fǎng)問(wèn)先淘汰。該算法的主要出發(fā)點(diǎn)是，如果某頁(yè)被訪(fǎng)問(wèn)了，則它可能馬上還要被訪(fǎng)問(wèn)。或者反過(guò)來(lái)說(shuō)，如了，則它可能馬上還要被訪(fǎng)問(wèn)。或者反過(guò)來(lái)說(shuō)，如果某頁(yè)很長(zhǎng)時(shí)間未被訪(fǎng)問(wèn)，則它在最近一段時(shí)間也果某頁(yè)很長(zhǎng)時(shí)間未被訪(fǎng)問(wèn)，則它在最近一段時(shí)間也不會(huì)被訪(fǎng)問(wèn)。不會(huì)被訪(fǎng)問(wèn)。 要完全實(shí)現(xiàn)要完全實(shí)現(xiàn)LRU算法是十分困難的算法是十分困難的。因?yàn)?/p>

52、要找出最近。因?yàn)橐页鲎罱罹梦幢皇褂玫捻?yè)面的話(huà)，就必須對(duì)每一個(gè)頁(yè)面都最久未被使用的頁(yè)面的話(huà)，就必須對(duì)每一個(gè)頁(yè)面都設(shè)置有關(guān)的訪(fǎng)問(wèn)記錄項(xiàng)，而且每一次訪(fǎng)問(wèn)都必須更設(shè)置有關(guān)的訪(fǎng)問(wèn)記錄項(xiàng)，而且每一次訪(fǎng)問(wèn)都必須更新這些記錄。這顯然要花費(fèi)巨大的系統(tǒng)開(kāi)銷(xiāo)。因此，新這些記錄。這顯然要花費(fèi)巨大的系統(tǒng)開(kāi)銷(xiāo)。因此，在實(shí)際系統(tǒng)中往往使用在實(shí)際系統(tǒng)中往往使用LRU的近似算法。的近似算法。 操作系統(tǒng)講義之五LRU頁(yè)面置換算法舉例：頁(yè)面置換算法舉例：例如：進(jìn)程例如：進(jìn)程P有有5個(gè)頁(yè)，進(jìn)程訪(fǎng)問(wèn)頁(yè)的順序?yàn)椋簜€(gè)頁(yè)，進(jìn)程訪(fǎng)問(wèn)頁(yè)的順序?yàn)椋?，3，2，1，4，3，5，4，3，2，1，5；如果在內(nèi)存中分配給該進(jìn)程；如果在內(nèi)存中分配給該進(jìn)

53、程3個(gè)頁(yè)面?zhèn)€頁(yè)面，則缺頁(yè)情況如下：，則缺頁(yè)情況如下：頁(yè)面432143543215頁(yè)面1432143543215頁(yè)面243214354321頁(yè)面34321435432缺頁(yè)缺頁(yè)中斷次數(shù)：缺頁(yè)中斷次數(shù)：1010次次缺頁(yè)率缺頁(yè)率 = (10/12)= (10/12)* *100%=83.3%100%=83.3%頁(yè)面淘汰順序：頁(yè)面淘汰順序： 4，3，2，1，5，4，3操作系統(tǒng)講義之五LRU有兩個(gè)近似算法有兩個(gè)近似算法最不經(jīng)常使用的頁(yè)面淘汰算法最不經(jīng)常使用的頁(yè)面淘汰算法(LFU)1）最不經(jīng)常使用頁(yè)面淘汰算法）最不經(jīng)常使用頁(yè)面淘汰算法LFU(least frequently used) 該算法在需要淘汰某一

54、頁(yè)時(shí)，首先淘汰到當(dāng)前該算法在需要淘汰某一頁(yè)時(shí)，首先淘汰到當(dāng)前時(shí)間為止，被訪(fǎng)問(wèn)次數(shù)最少的那一頁(yè)。這只要在時(shí)間為止，被訪(fǎng)問(wèn)次數(shù)最少的那一頁(yè)。這只要在頁(yè)表中給每一頁(yè)增設(shè)一個(gè)頁(yè)表中給每一頁(yè)增設(shè)一個(gè)訪(fǎng)問(wèn)計(jì)數(shù)器訪(fǎng)問(wèn)計(jì)數(shù)器即可實(shí)現(xiàn)。即可實(shí)現(xiàn)。每當(dāng)該頁(yè)被訪(fǎng)問(wèn)時(shí)，訪(fǎng)問(wèn)計(jì)數(shù)器加每當(dāng)該頁(yè)被訪(fǎng)問(wèn)時(shí)，訪(fǎng)問(wèn)計(jì)數(shù)器加1，而發(fā)生一，而發(fā)生一次缺頁(yè)中斷時(shí)，則淘汰計(jì)數(shù)值最小的那一頁(yè)，次缺頁(yè)中斷時(shí)，則淘汰計(jì)數(shù)值最小的那一頁(yè)，并并將所有的計(jì)數(shù)器清零將所有的計(jì)數(shù)器清零。最近沒(méi)使用的頁(yè)面淘汰算法最近沒(méi)使用的頁(yè)面淘汰算法(NUR)操作系統(tǒng)講義之五2）最近沒(méi)有使用頁(yè)面淘汰算法）最近沒(méi)有使用頁(yè)面淘汰算法NUR 該算法在需要淘汰某一頁(yè)時(shí)，從那些

55、最近一個(gè)該算法在需要淘汰某一頁(yè)時(shí)，從那些最近一個(gè)時(shí)期內(nèi)未被訪(fǎng)問(wèn)的頁(yè)中任選一頁(yè)淘汰。只要在時(shí)期內(nèi)未被訪(fǎng)問(wèn)的頁(yè)中任選一頁(yè)淘汰。只要在頁(yè)表中增設(shè)一個(gè)訪(fǎng)問(wèn)位即可實(shí)現(xiàn)。當(dāng)某頁(yè)被訪(fǎng)頁(yè)表中增設(shè)一個(gè)訪(fǎng)問(wèn)位即可實(shí)現(xiàn)。當(dāng)某頁(yè)被訪(fǎng)問(wèn)時(shí)，訪(fǎng)問(wèn)位置問(wèn)時(shí)，訪(fǎng)問(wèn)位置1。否則，訪(fǎng)問(wèn)位置。否則，訪(fǎng)問(wèn)位置0。系統(tǒng)周。系統(tǒng)周期性地對(duì)所有引用位清零。當(dāng)需淘汰一頁(yè)時(shí)，期性地對(duì)所有引用位清零。當(dāng)需淘汰一頁(yè)時(shí)，從那些訪(fǎng)問(wèn)位為零的頁(yè)中選一頁(yè)進(jìn)行淘汰。從那些訪(fǎng)問(wèn)位為零的頁(yè)中選一頁(yè)進(jìn)行淘汰。操作系統(tǒng)講義之五（6）Clock置換算法置換算法(時(shí)鐘置換算法時(shí)鐘置換算法)1） 簡(jiǎn)單的簡(jiǎn)單的Clock置換算法置換算法 為每頁(yè)設(shè)置一位訪(fǎng)問(wèn)位，為每頁(yè)設(shè)置一

56、位訪(fǎng)問(wèn)位，當(dāng)當(dāng)淘汰一個(gè)頁(yè)面時(shí)，如果指針指淘汰一個(gè)頁(yè)面時(shí)，如果指針指向頁(yè)面的訪(fǎng)問(wèn)位向頁(yè)面的訪(fǎng)問(wèn)位R為為0，就將其，就將其淘汰，并把新的頁(yè)面插入這個(gè)淘汰，并把新的頁(yè)面插入這個(gè)位置，指針向前移動(dòng)一個(gè)位置；位置，指針向前移動(dòng)一個(gè)位置； 如果訪(fǎng)問(wèn)位如果訪(fǎng)問(wèn)位R為為1，就清除，就清除R位位(置置0)，并把指針前移一個(gè)位，并把指針前移一個(gè)位置，直到找到一個(gè)置，直到找到一個(gè)R位為位為0的頁(yè)的頁(yè)面為止。面為止。操作系統(tǒng)講義之五 由由訪(fǎng)問(wèn)位訪(fǎng)問(wèn)位R和和修改位修改位M可以組合成下面四種類(lèi)型的頁(yè)面：可以組合成下面四種類(lèi)型的頁(yè)面： 1類(lèi)類(lèi)(R=0, M=0): 表示該頁(yè)最近既未被訪(fǎng)問(wèn)，又未被修改，是表示該頁(yè)最近既未被訪(fǎng)

57、問(wèn)，又未被修改，是最佳淘汰頁(yè)。最佳淘汰頁(yè)。 2類(lèi)類(lèi)(R=0, M=1)： 表示該頁(yè)最近未被訪(fǎng)問(wèn)，但已被修改，并不表示該頁(yè)最近未被訪(fǎng)問(wèn)，但已被修改，并不是很好的淘汰頁(yè)。是很好的淘汰頁(yè)。 3類(lèi)類(lèi)(R=1, M=0)： 最近已被訪(fǎng)問(wèn)，但未被修改，該頁(yè)有可能再最近已被訪(fǎng)問(wèn)，但未被修改，該頁(yè)有可能再被訪(fǎng)問(wèn)。被訪(fǎng)問(wèn)。 4類(lèi)類(lèi)(R=1, M=1): 最近已被訪(fǎng)問(wèn)且被修改，該頁(yè)可能再被訪(fǎng)問(wèn)。最近已被訪(fǎng)問(wèn)且被修改，該頁(yè)可能再被訪(fǎng)問(wèn)。 2. 改進(jìn)型改進(jìn)型Clock置換算法置換算法 操作系統(tǒng)講義之五v其執(zhí)行過(guò)程可分成以下三步：其執(zhí)行過(guò)程可分成以下三步： (1) 從指針?biāo)甘镜漠?dāng)前位置開(kāi)始，從指針?biāo)甘镜漠?dāng)前位置開(kāi)始

58、， 掃描循環(huán)隊(duì)列，掃描循環(huán)隊(duì)列， 尋找尋找R=0且且M=0的的第一類(lèi)第一類(lèi)頁(yè)面，頁(yè)面， 將所遇到的第一個(gè)頁(yè)面作為所選中將所遇到的第一個(gè)頁(yè)面作為所選中的淘汰頁(yè)。的淘汰頁(yè)。 在第一次掃描期間不改變?cè)L問(wèn)位在第一次掃描期間不改變?cè)L問(wèn)位A。 (2) 如果第一步失敗，則開(kāi)始第二輪掃描，尋找如果第一步失敗，則開(kāi)始第二輪掃描，尋找R=0且且M=1的的第二類(lèi)第二類(lèi)頁(yè)面，將所遇到的第一個(gè)這類(lèi)頁(yè)面作為淘汰頁(yè)。在第頁(yè)面，將所遇到的第一個(gè)這類(lèi)頁(yè)面作為淘汰頁(yè)。在第二輪掃描期間，二輪掃描期間，將所有掃描過(guò)的頁(yè)面的訪(fǎng)問(wèn)位將所有掃描過(guò)的頁(yè)面的訪(fǎng)問(wèn)位R都置為都置為0。 (3) 如果第二步也失敗，則將指針?lè)祷氐介_(kāi)始的位置，并將所如

59、果第二步也失敗，則將指針?lè)祷氐介_(kāi)始的位置，并將所有的訪(fǎng)問(wèn)位有的訪(fǎng)問(wèn)位R置為置為0。 然后重復(fù)第一步，如果仍失敗，必要然后重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁(yè)。時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁(yè)。 操作系統(tǒng)講義之五6. Belady現(xiàn)象現(xiàn)象(異常現(xiàn)象異?，F(xiàn)象)vBelady現(xiàn)象：先進(jìn)先出算法的一個(gè)缺點(diǎn)是它有一種陷阱現(xiàn)象。現(xiàn)象：先進(jìn)先出算法的一個(gè)缺點(diǎn)是它有一種陷阱現(xiàn)象。一般來(lái)說(shuō)，對(duì)于任何一作業(yè)或進(jìn)程，如果給它分配的內(nèi)存頁(yè)一般來(lái)說(shuō)，對(duì)于任何一作業(yè)或進(jìn)程，如果給它分配的內(nèi)存頁(yè)面數(shù)越接近于它所要求的頁(yè)面數(shù)，則發(fā)生缺頁(yè)的次數(shù)會(huì)越少。面數(shù)越接近于它所要求的頁(yè)面數(shù)，則

60、發(fā)生缺頁(yè)的次數(shù)會(huì)越少。在極限情況下，這個(gè)推論是成立的。因?yàn)槿绻o一個(gè)進(jìn)程分在極限情況下，這個(gè)推論是成立的。因?yàn)槿绻o一個(gè)進(jìn)程分配了它所要求的全部頁(yè)面，則不會(huì)發(fā)生缺頁(yè)現(xiàn)象。但是，配了它所要求的全部頁(yè)面，則不會(huì)發(fā)生缺頁(yè)現(xiàn)象。但是，使使用用FIFO算法時(shí)，在未給進(jìn)程或作業(yè)分配足夠的頁(yè)面數(shù)時(shí)，算法時(shí)，在未給進(jìn)程或作業(yè)分配足夠的頁(yè)面數(shù)時(shí)，有時(shí)會(huì)出現(xiàn)分配的頁(yè)面數(shù)增多，缺頁(yè)次數(shù)反而增加的奇怪現(xiàn)有時(shí)會(huì)出現(xiàn)分配的頁(yè)面數(shù)增多，缺頁(yè)次數(shù)反而增加的奇怪現(xiàn)象。這種現(xiàn)象稱(chēng)為象。這種現(xiàn)象稱(chēng)為Belady現(xiàn)象?，F(xiàn)象。如下圖所示。如下圖所示。vBelady現(xiàn)象的原因：現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪(fǎng)問(wèn)內(nèi)存算法的置換特