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

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

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

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

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

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

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

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

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

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

10、3000頁號頁號 塊號塊號0 30 31 91 92 -2 -3 -3 -0 20 2頁號頁號 塊號塊號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頁表頁表操作

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

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

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

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

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

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

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

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

19、直接復(fù)制到位移量直接復(fù)制到內(nèi)存地址寄內(nèi)存地址寄存器存器的低位部分；的低位部分；v根據(jù)頁號查頁表，得到該頁裝入內(nèi)存的物理塊根據(jù)頁號查頁表，得到該頁裝入內(nèi)存的物理塊號，號，并將塊號轉(zhuǎn)換成二進制數(shù)填入地址寄存器并將塊號轉(zhuǎn)換成二進制數(shù)填入地址寄存器的高位部分的高位部分，從而形成內(nèi)存地址。從而形成內(nèi)存地址。操作系統(tǒng)講義之五十六進制十六進制(參考參考)：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è)大?。河幸幌到y(tǒng)采用頁式存儲管理，有一作業(yè)大小是是8KB，頁大小為，頁大小為2KB，依次裝入內(nèi)存的第，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地轉(zhuǎn)換成內(nèi)存地址。址。解答解答: （1）虛地址）虛地址 7145PINT(7145/2048) 3 (對應(yīng)對應(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 (對應(yīng)物對應(yīng)物理塊理塊9) W3412mod 2048 1364 MR=9*2048+1364=19796 虛地址虛地址3412的內(nèi)存地址是：的內(nèi)存地址是：19796操作系統(tǒng)講義之五例例2：某虛擬存儲器的用戶空間共：某虛擬存儲器的用戶空間共32個頁面?zhèn)€頁面，每頁每頁1KB，主存，主存16KB，假設(shè)某時刻系統(tǒng)為用，假設(shè)某時刻系統(tǒng)為用戶的戶的0、1、2、3頁分配的物理塊為頁分配的物理塊為5、10、4、7，而該用戶作業(yè)的長度為而該用戶作業(yè)的長度為6頁頁，試將十六進，試將十六進制的虛地址制的

22、虛地址0A5C、103C、1A5C轉(zhuǎn)換成物理轉(zhuǎn)換成物理地址。地址。解答：解答： 用戶空間用戶空間(邏輯地址空間邏輯地址空間)為為32*1KB=32KB，因因 215=32KB，故邏輯地址編碼為，故邏輯地址編碼為15位，頁面位，頁面為為1KB(210KB)，所以頁號用，所以頁號用5位，頁內(nèi)地址位，頁內(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 頁號為頁號為4，合法，但該頁未裝入主存，故產(chǎn)生，合法，但該頁未裝入主存，故產(chǎn)生缺頁中斷；缺頁中斷；（3） 1A5C 1A5C=001 1010 0101 1100 P=6，因，因該用戶該用戶作業(yè)的長度為作業(yè)的長度為6頁頁(05)，故產(chǎn)生地址越界中斷。，故產(chǎn)生地址越界中斷。操作系統(tǒng)講義之五一道考研題一道考研題 西北工業(yè)大學(xué)（西北工業(yè)大學(xué)（20022002）v設(shè)有設(shè)有8頁的邏輯空間，每頁有頁的邏輯空間，每頁有1024字節(jié)字節(jié)(1KB)，它們被映射到，它們被映射到32塊的物理存儲區(qū)中，那么邏輯地址的有效位是（）位，物理地塊的物理存儲區(qū)中，那么邏輯地址的有效位是（）位，物理地址至少是（）位。

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

25、有內(nèi)存有32個物理塊，物理塊大小與邏輯塊大小相同，故物理地址個物理塊，物理塊大小與邏輯塊大小相同，故物理地址空間為空間為32*1KB=32KB。因為。因為215=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引入原因：頁表駐留內(nèi)存，執(zhí)行訪內(nèi)指令要先引入原因：頁表駐留內(nèi)存，執(zhí)行訪內(nèi)指令要先到內(nèi)存查頁表，進行地址轉(zhuǎn)換后才能進行訪內(nèi)到內(nèi)存查頁表，進行地址轉(zhuǎn)換后才能進行訪內(nèi)操

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

51、）最近最久未使用的頁面置換算法最近最久未使用的頁面置換算法(LRU) 該算法的基本思想是該算法的基本思想是: 當需要淘汰某一頁時，選擇當需要淘汰某一頁時，選擇離當前時間最近的一段時間內(nèi)最久沒有使用過的頁離當前時間最近的一段時間內(nèi)最久沒有使用過的頁先淘汰。該算法的主要出發(fā)點是，如果某頁被訪問先淘汰。該算法的主要出發(fā)點是，如果某頁被訪問了，則它可能馬上還要被訪問。或者反過來說，如了，則它可能馬上還要被訪問?；蛘叻催^來說，如果某頁很長時間未被訪問，則它在最近一段時間也果某頁很長時間未被訪問，則它在最近一段時間也不會被訪問。不會被訪問。 要完全實現(xiàn)要完全實現(xiàn)LRU算法是十分困難的算法是十分困難的。因為

52、要找出最近。因為要找出最近最久未被使用的頁面的話，就必須對每一個頁面都最久未被使用的頁面的話，就必須對每一個頁面都設(shè)置有關(guān)的訪問記錄項，而且每一次訪問都必須更設(shè)置有關(guān)的訪問記錄項，而且每一次訪問都必須更新這些記錄。這顯然要花費巨大的系統(tǒng)開銷。因此，新這些記錄。這顯然要花費巨大的系統(tǒng)開銷。因此，在實際系統(tǒng)中往往使用在實際系統(tǒng)中往往使用LRU的近似算法。的近似算法。 操作系統(tǒng)講義之五LRU頁面置換算法舉例：頁面置換算法舉例：例如：進程例如：進程P有有5個頁，進程訪問頁的順序為：個頁，進程訪問頁的順序為：4，3，2，1，4，3，5，4，3，2，1，5；如果在內(nèi)存中分配給該進程；如果在內(nèi)存中分配給該進

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

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

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

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

57、問，又未被修改，是最佳淘汰頁。最佳淘汰頁。 2類類(R=0, M=1)： 表示該頁最近未被訪問，但已被修改，并不表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。是很好的淘汰頁。 3類類(R=1, M=0)： 最近已被訪問，但未被修改，該頁有可能再最近已被訪問，但未被修改，該頁有可能再被訪問。被訪問。 4類類(R=1, M=1): 最近已被訪問且被修改，該頁可能再被訪問。最近已被訪問且被修改，該頁可能再被訪問。 2. 改進型改進型Clock置換算法置換算法 操作系統(tǒng)講義之五v其執(zhí)行過程可分成以下三步：其執(zhí)行過程可分成以下三步： (1) 從指針所指示的當前位置開始，從指針所指示的當前位置開始

58、， 掃描循環(huán)隊列，掃描循環(huán)隊列， 尋找尋找R=0且且M=0的的第一類第一類頁面，頁面， 將所遇到的第一個頁面作為所選中將所遇到的第一個頁面作為所選中的淘汰頁。的淘汰頁。 在第一次掃描期間不改變訪問位在第一次掃描期間不改變訪問位A。 (2) 如果第一步失敗，則開始第二輪掃描，尋找如果第一步失敗，則開始第二輪掃描，尋找R=0且且M=1的的第二類第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，二輪掃描期間，將所有掃描過的頁面的訪問位將所有掃描過的頁面的訪問位R都置為都置為0。 (3) 如果第二步也失敗，則將指針返回到開始的位置，并將所如

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

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