操作系統(tǒng)第5章存儲管理3虛擬存儲

5.6虛存的引入第5章之三

虛擬存儲器（一）程序一次性裝入內(nèi)存帶來的問題1.單一連續(xù)分配、多道分區(qū)分配、分頁和分段存儲管理的共同特點(diǎn)是：

都需要將程序一次性全部裝入內(nèi)存。2.程序一次性裝入帶來一些問題(1)內(nèi)存總是有限的，當(dāng)作業(yè)很大，內(nèi)存不足時？OS內(nèi)存用戶作業(yè)帶來的問題是：內(nèi)存空間連一個作業(yè)也無法全部裝入！(2)當(dāng)使用固定分區(qū)管理，分頁分段管理需要裝入多個作業(yè)時，每個作業(yè)只能占用內(nèi)存的一部份，但分給作業(yè)的內(nèi)存不足時？OS40K內(nèi)存80K120K作業(yè)一130K作業(yè)二180K作業(yè)三250K帶來的問題是：沒有哪一個分區(qū)能完全裝入一個用戶作業(yè)?。ǘ┏绦蚓植啃栽?.時間局部性：一條指令被執(zhí)行后，那么它可能很快會再次執(zhí)行。如循環(huán)、子程序、堆棧、計(jì)數(shù)或累計(jì)變量等。2.空間局部性：若某一存儲單元被訪問，那么與該存儲單元相鄰的單元可能也會很快被訪問。如程序代碼的順序執(zhí)行，對線性數(shù)據(jù)結(jié)構(gòu)的訪問或處理、常用變量等。問題：能否將部分程序裝入內(nèi)存后就開始運(yùn)行作業(yè)？為什么？（三）程序局部性原理的應(yīng)用一個程序特別是一個大型程序的一部份裝入內(nèi)存是可以運(yùn)行的。理由是：1.程序中的某些部份在程序整個運(yùn)行過程中可能根本不用。如：出錯處理程序。2.許多表格占用固定數(shù)量的內(nèi)存空間，而實(shí)際上只用到其中的一部份。3.許多程序段是順序執(zhí)行的，還有一些程序段是互斥執(zhí)行的。如菜單選擇功能。4.在程序的一次執(zhí)行過程中，有些程序執(zhí)行之后，從某個時刻起不再用到。（四）虛擬存儲器的定義與特性1.虛擬存儲器是指僅把作業(yè)的一部份裝入內(nèi)存便可以運(yùn)行作業(yè)的存儲器系統(tǒng)。也即，指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲器系統(tǒng)。2.虛擬存儲器的新特性虛擬擴(kuò)充。不是物理上擴(kuò)大內(nèi)存空間，而是邏輯上擴(kuò)充了內(nèi)存。也即是把大的邏輯地址空間映射到較小的物理內(nèi)存上。部分裝入。每個作業(yè)不是全部一次裝入內(nèi)存。只將當(dāng)前要運(yùn)行的裝入內(nèi)存就開始運(yùn)行。離散分配。裝入內(nèi)存的部份作業(yè)不必占用連續(xù)的內(nèi)存空間，而是“見縫插針”。多次對換。一個作業(yè)運(yùn)行時，它所需要的程序和數(shù)據(jù)分成多次調(diào)入內(nèi)存。而在內(nèi)存中那些暫時不用的程序和數(shù)據(jù)可換出到外存對換區(qū)，以騰出盡量多的內(nèi)存空間供運(yùn)行進(jìn)程使用。交換區(qū)（SWAP）：進(jìn)程剛建立時，頁表記錄頁面所在輔存位置，即程序文件所在的外存位置。但程序文件中一般包含有程序的二進(jìn)制目標(biāo)碼及數(shù)據(jù)初始值和初值為0的工作區(qū)。后兩者在回寫時不能寫入程序文件所在輔存區(qū)，因此引入了交換區(qū)—臨時存儲區(qū)。（就緒掛起、阻塞掛起的進(jìn)程）23222625272326222527212423242526272421外存交換區(qū)外存202122換出21，換入25換出24，換入27內(nèi)存頁表例：內(nèi)存原存放外存的21塊和24塊（存放數(shù)據(jù)和初始值），現(xiàn)需調(diào)入25和27塊，因內(nèi)存不足，需對換。3.虛擬存儲器的容量不是無限大的。

它受兩方面的限制。一個是指令中表示的地址長度。假設(shè)地址長度為32字節(jié)，按字節(jié)尋址，則邏輯空間（虛存空間）大小為232個字節(jié)。（４Ｇ個字節(jié)） 另一個是外存容量。用戶的虛擬空間不能超過硬盤中作業(yè)的存放空間。（四）虛擬存儲器的定義與特性（五）實(shí)現(xiàn)虛擬存儲的基本方法 可采用頁式虛存管理、段式虛存管理和段頁式虛存管理。如：

頁式虛存管理。在頁式管理的基礎(chǔ)上，僅將進(jìn)程的一部分頁放于主存。頁表項(xiàng)中注明該頁是否在主存。程序執(zhí)行時，如果訪問的頁不在主存，根據(jù)頁表項(xiàng)的指示，將其從外存調(diào)入主存，如果此時無可用的內(nèi)存空間，則先淘汰若干頁幀。（其他方法基本相同）一、基本原理頁式虛擬存儲管理方式是在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能、頁面置換功能所形成的虛擬存儲器系統(tǒng)。5.7頁式虛存管理狀態(tài)位：表示該頁是否已經(jīng)調(diào)入內(nèi)存。訪問位：表示該頁在內(nèi)存間是否被訪問過修改位：表示該頁在內(nèi)存是否被修改過。頁號內(nèi)存塊號狀態(tài)位訪問位修改位外存地址

二、頁表項(xiàng)結(jié)構(gòu) 對頁表增加了一些項(xiàng)目，具體如下：

三、地址變換機(jī)構(gòu) 與頁式管理基本相同，只是缺頁時產(chǎn)生缺頁中斷，先將該頁調(diào)入內(nèi)存，再訪問。見下圖示。指令執(zhí)行步驟與缺頁中斷處理過程★5.8頁面置換算法一、目的與要求：

1、掌握頁面替換策略中的基本概念

2、掌握駐留集固定的三種頁面替換策略。

3、掌握影響缺頁中斷率的主要因素

4、了解動態(tài)駐留集的頁面替換策略。二、重點(diǎn)與難點(diǎn)

1、固定駐留集算法

2、SWS等實(shí)用動態(tài)駐留集算法。三、課時：2(90分鐘)四、教法：講授法五、教具六、教學(xué)過程

1、介紹有關(guān)概念及替換策略分類

2、詳細(xì)介紹駐留集固定的頁面替換策略

3、簡略介紹可變駐留集替換策略本節(jié)主要講述的內(nèi)容

一、頁面替換策略中的基本概念 二、頁面替換策略的分類 三、駐留集大小固定的替換策略 四、頁面替換算法解題舉例 五、影響缺頁中斷率的主要因素 六、頁面替換策略應(yīng)用實(shí)例 七、駐留集可變的替換策略 八、替換策略選擇一、頁面替換(策略)策略中的基本概念

頁面置換算法：地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中，則產(chǎn)生缺頁中斷。當(dāng)發(fā)生缺頁中斷時操作系統(tǒng)必須在內(nèi)存選擇一個頁面將其移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法(策略)。一、頁面替換(策略)策略中的基本概念駐留集(工作集)：進(jìn)程的合法頁集合；也即系統(tǒng)分給一個進(jìn)程的內(nèi)存可用塊數(shù)。訪問串（頁面走向）：進(jìn)程的存儲訪問序列或進(jìn)程訪問虛空間的地址蹤跡。頁式虛存管理以頁為基本單位，只需頁號即可。頁面走向可合理簡化。頁面走向可合理簡化原則：（1）對于給定的頁面大小，僅考慮其頁號，不關(guān)心完整的地址。（2）如果當(dāng)前對頁面P進(jìn)行了訪問，那么，馬上又對該頁訪問就不會缺頁。這樣連續(xù)出現(xiàn)的頁號就簡化為一個頁號。舉例：某進(jìn)程依次訪問如下地址：0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105。若頁面大小為100，上述訪問串可簡化為：1，4，1，6，1，6，1，6，1，6，1二、頁面替換策略分成兩類：

駐留集大小固定的替換策略；駐留集大小可變的替換策略。三、駐留集大小固定的替換策略(一)先進(jìn)先出置換算法(FIFO)(二)最佳置換算法(OPT)(三)最近最少使用算法(LRU)(四)時鐘置換算法(CLOCK)(一)FIFO替換算法置換策略：優(yōu)先淘汰最早進(jìn)入內(nèi)存的頁面，亦即在內(nèi)存中駐留時間最久的頁面1.FIFO算法舉例：駐留集大小為3，訪問串為：7,0,1,2,0,3,0,4,2,3,0,3,2…設(shè)開始三頁內(nèi)存為空，每調(diào)入一頁均缺頁。試列表求出FIFO算法的面頁淘汰過程，淘汰的頁序和缺頁次數(shù)？FIFO算法頁面替換過程如下表表示：次序7012030423032頁面分配情況是否缺頁換出的頁7012030423032是次序7012030423032頁面分配情況是否缺頁換出的頁012030423032是是77次序7012030423032頁面分配情況是否缺頁換出的頁12030423032是是77700是次序7012030423032頁面分配情況是否缺頁換出的頁2030423032是是77700是1是017次序7012030423032頁面分配情況是否缺頁換出的頁7030423032是是77700是1是0202否是11次序7012030423032頁面分配情況是否缺頁換出的頁7000423032是是77700是1是0202否是111233是次序7012030423032頁面分配情況是否缺頁換出的頁7010423032是是77700是1是0202否是111233是2300是次序7012030423032頁面分配情況是否缺頁換出的頁7012023032是是77700是1是0202否是111233是2300是3044是次序7012030423032頁面分配情況是否缺頁換出的頁7012303032是是77700是1是0202否是111233是2300是3044是004422是次序7012030423032頁面分配情況是否缺頁換出的頁7012300032是是77700是1是0202否是111233是2300是3044是004422是4233是次序7012030423032頁面分配情況032是否缺頁換出的頁7012304032是是77700是1是0202否是111233是2300是3044是004422是4233是否否次序7012030423032頁面分配情況123042300012304237770123042是否缺頁是是是是否是是是是是是否否換出的頁7012304結(jié)果：缺頁次數(shù)共10次。（1）FIFO方法的特點(diǎn)：

實(shí)現(xiàn)方便。不需要額外硬件。效果不好，有Belady奇異。（2）FIFO存在Belady奇異：指替換策略不滿足隨著駐留集的增大，頁故障數(shù)（缺頁中斷次數(shù)）一定減少的規(guī)律。這一規(guī)律由Belady于1969年發(fā)現(xiàn)，故稱為Belady異常2.對FIFO替換算法的進(jìn)一步認(rèn)識（3）FIFO算法的Belady奇異現(xiàn)象舉例對于如下的頁面訪問序列：1，2，3，4，1，2，5，1，2，3，4，5當(dāng)內(nèi)存塊數(shù)量分別為3和4時，試問：使用FIFO置換算法產(chǎn)生的缺頁中斷是多少？（所有內(nèi)存開始時都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷）內(nèi)存塊為3時，缺頁中斷次數(shù)為9次。內(nèi)存塊為4時，缺頁中斷次數(shù)為10次。內(nèi)存塊為3時，缺頁中斷次數(shù)為9次。次序123412512345頁面分配情況341253422341253111234125是否缺頁是是是是是是是否否是是否換出的頁123412內(nèi)存塊為4時，缺頁中斷次數(shù)為10次。次序123412512345頁面分配情況4512345334512342223451231111234512是否缺頁是是是是否否是是是是是是換出的頁123451(二)OPT替換算法置換策略：當(dāng)要調(diào)入一頁而必須淘汰舊頁時，應(yīng)該淘汰以后不再訪問的頁，或距現(xiàn)在最長時間后要訪問的頁面。

1966年，Belady提出最佳(優(yōu))頁面替換算法(OPTimalreplacement，OPT)。是操作系統(tǒng)存儲管理中的一種全局頁面替換策略。1.OPT算法舉例：駐留集大小為3，訪問串為：7,0,1,2,0,3,0,4,2,3,0,3,2…設(shè)開始三頁內(nèi)存為空，每調(diào)入一頁均缺頁。試列表求出FIFO算法的面頁淘汰過程，淘汰的頁序和缺頁次數(shù)？次序7012030423032頁面分配情況是否缺頁換出的頁7012030423032是次序7012030423032頁面分配情況是否缺頁換出的頁7012030423032是是7OPT算法置換過程次序7012030423032頁面分配情況是否缺頁換出的頁712030423032是是70是70OPT算法置換過程次序7012030423032頁面分配情況是否缺頁換出的頁712030423032是是70是70701是OPT算法置換過程次序7012030423032頁面分配情況是否缺頁換出的頁71030423032是是70是70701是7011022否是OPT算法置換過程次序7012030423032頁面分配情況是否缺頁換出的頁171030423032是是70是70701是7011022否是22003否是OPT算法置換過程次序7012030423032頁面分配情況是否缺頁換出的頁1071030423032是是70是70701是7011022否是22003否是2233否否是4OPT算法置換過程次序7012030423032頁面分配情況302是否缺頁換出的頁1047103042332是是70是70701是7011022否是22003否是2233否否是4否否OPT算法置換過程次序7012030423032頁面分配情況113330000407772222是否缺頁是是是是否是否是否否是否否換出的頁7104結(jié)果：缺頁次數(shù)共7次2.對OPT替換算法的進(jìn)一步認(rèn)識(1)是最優(yōu)的頁面替換策略O(shè)PT策略對任意一個訪問串的控制均有最小的時空積（進(jìn)程所占空間與時間的乘積）。(2)是不可實(shí)現(xiàn)的策略由于需要預(yù)先得知整個訪問串的序，故不能用于實(shí)踐,僅作為一種標(biāo)準(zhǔn)，用以測量其他可行策略的性能。(三)LRU替換算法置換策略：淘汰上次使用距當(dāng)前最遠(yuǎn)的頁或最近很少使用的頁。LRU是LeastRecentlyUsed的縮寫，即最近最少使用。1.LRU算法舉例：駐留集大小為3，訪問串為：7,0,1,2,0,3,0,4,2,3,0,3,2…設(shè)開始三頁內(nèi)存為空，每調(diào)入一頁均缺頁。試列表求出FIFO算法的面頁淘汰過程，淘汰的頁序和缺頁次數(shù)？次序7012030423032頁面分配情況是否缺頁換出的頁7012030423032是LRU算法置換過程次序7012030423032頁面分配情況是否缺頁換出的頁7012030423032是是7LRU算法置換過程次序7012030423032頁面分配情況是否缺頁換出的頁712030423032是是70是70LRU算法置換過程次序7012030423032頁面分配情況是否缺頁換出的頁712030423032是是70是70701是LRU算法置換過程次序7012030423032頁面分配情況是否缺頁換出的頁71030423032是是70是70701是7011022否是LRU算法置換過程次序7012030423032頁面分配情況是否缺頁換出的頁171030423032是是70是70701是7011022否是22003否是LRU算法置換過程次序7012030423032頁面分配情況是否缺頁換出的頁1271030423032是是70是70701是7011022否是22003否是LRU算法置換過程40033是次序7012030423032頁面分配情況是否缺頁換出的頁12371030423032是是70是70701是7011022否是22003否是LRU算法置換過程40033是20044是次序7012030423032頁面分配情況是否缺頁換出的頁123071030423032是是70是70701是7011022否是22003否是LRU算法置換過程40033是20044是32244是次序7012030423032頁面分配情況230是否缺頁換出的頁123047103042332是是70是70701是7011022否是22003否是LRU算法置換過程40033是20044是32244是否否次序7012030423032頁面分配情況113322200000033777224440是否缺頁是是是是否是否是否否是否否換出的頁712304結(jié)果：缺頁次數(shù)共9次2.對LRU算法的進(jìn)一步認(rèn)識到

(1)LRU沒有Belady奇異。即隨著駐留集的增大,頁故障一定減少。(2)需要硬件配合，實(shí)現(xiàn)費(fèi)用高，但效果適中。（3）LRU替換算法無Belady奇異現(xiàn)象舉例：對于如下的頁面訪問序列：1，2，3，5，2，4，5，2，1，3，2，5當(dāng)內(nèi)存塊數(shù)量分別為3和4時，試問：使用LRU置換算法產(chǎn)生的缺頁中斷是多少？（所有內(nèi)存開始時都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷）LRU算法，內(nèi)存塊為3時，缺頁中斷次數(shù)為8次。次序123524521325頁面分配情況334115222222211155533是否缺頁是是是是否是否否是是否是換出的頁13451LRU算法，內(nèi)存塊為4時，缺頁中斷次數(shù)為7次。次序123524521325頁面分配情況5555333112222221111443是否缺頁是是是是否是否否是是否否換出的頁134（4）LRU算法的實(shí)現(xiàn)方法實(shí)現(xiàn)方法1：用計(jì)數(shù)器實(shí)現(xiàn)LRU。實(shí)現(xiàn)方法2：用棧實(shí)現(xiàn)LRU。實(shí)現(xiàn)方法3：用矩陣實(shí)現(xiàn)LRU。實(shí)現(xiàn)方法4：用寄存器實(shí)現(xiàn)LRU。實(shí)現(xiàn)方法1—用計(jì)數(shù)器實(shí)現(xiàn)LRU

每頁增加一個計(jì)數(shù)器，用計(jì)數(shù)器方法記錄情況。命中時，剛訪問到的頁計(jì)數(shù)器清0，其余頁計(jì)數(shù)器加1；淘汰時選擇頁計(jì)數(shù)器值最大的頁面，新?lián)Q入的頁計(jì)數(shù)器清0，其余頁計(jì)數(shù)器加1。例如：舉例：若駐留集大小為3，訪問串為7,0,1,2,0,3,0,4,2,3,0,3,20/71/70/02/71/00/10/22/01/11/20/02/12/21/00/33/20/01/30/41/02/31/42/00/22/40/31/20/01/32/21/00/33/22/01/30/2淘汰的頁序：712304缺頁次數(shù)：9次實(shí)現(xiàn)方法2—用棧實(shí)現(xiàn)LRU

可用一個特殊的棧來保存當(dāng)前使用的各個頁面的頁面號。每當(dāng)進(jìn)程訪問某頁面時便將該面頁從棧中移出，然后將它壓入棧頂。因此，棧頂始終是最新的頁號，而棧底則是最近最久未使用的頁號。例如:舉例：駐留集大小為3，訪問串為7,0,1,2,0,3,0,4,2,3,0,3,2707107210021302032403240324032302230淘汰的頁：712304缺頁次數(shù)：9次棧頂棧底(四)時鐘置換算法(CLOCK)

CLOCK算法是LRU算法的近似算法。CLOCK算法給每個頁面設(shè)置一個訪問位，標(biāo)識該頁最近有沒有被訪問過，再將內(nèi)存中的所有頁面通過一個指針鏈接成一個循環(huán)隊(duì)列。其算法流程圖如下圖所示。開始該頁命中？P指針不動，將命中頁的頁面訪問位置為1P指針?biāo)疙撁嬖L問位=0？淘汰該頁，換入新頁，該頁頁面訪問位置為1P指針下移一個頁面置該頁頁面訪問位為0P指針下移一個頁面YESNOYESNOCLOCK算法的流程圖讀取要訪問的頁號讀取要訪問的頁號CLOCK算法舉例：駐留集大小為3，訪問串為7,0,1,2,0,3,0,4,2,3,0,3,2淘汰頁序:OOO7120341/70/-0/-1/71/01/71/01/10/70/00/11/20/00/11/21/00/11/21/01/30/20/00/31/40/00/31/41/20/31/41/21/30/40/21/01/30/21/01/31/21/00/40/20/31/20/00/11/20/01/30/-0/-0/-初始注意:

若循環(huán)鏈表存在當(dāng)前訪問頁(命中)時，直接將其訪問位改為1．指針不移動（命中后指針不移動）；否則，若當(dāng)前P指針指向頁面的訪問位為0，則淘汰該頁，調(diào)入新頁．將其訪問位改為1，指針移到下一個物理塊；若當(dāng)前P指針指向頁面的訪問位為1．則將其訪問位改為0,并移動指針到下一個物理塊。

CLOCK算法的優(yōu)點(diǎn)是:比LRU算法少了很多硬件的支持，實(shí)現(xiàn)比較簡單，但和FIFO算法相比，仍需要較多的硬件支持。四、頁面替換算法解題舉例例1:在頁式管理中，設(shè)給定的主存塊數(shù)為三塊，已知頁面走向?yàn)椋?，3，2，1，4，3，5，4，3，2，l，5。調(diào)頁時分別采用FIFO算法、OPT算法、棧結(jié)構(gòu)實(shí)現(xiàn)的LRU算法和計(jì)數(shù)器實(shí)現(xiàn)的LRU時，問：寫出淘汰頁序，淘汰次數(shù)和缺頁率各是多少？要求寫出算法過程

次序432143543215頁面分配情況432143521432143524321435是否缺頁是是是是是是是否否是是否淘汰的頁4321431、FIFO頁面置換算法缺頁次數(shù)為9次；缺頁中斷率f=9/12＝75%.

次序432143543215頁面分配情況432155543333144422是否缺頁是是是是否否是否否是是否淘汰的頁21432、OPT頁面置換算法缺頁次數(shù)為7次，缺頁中斷率：f=7/12=58.3%。次序432143543215頁面分配情況155222233333444441是否缺頁是是是是否否是否否否是否淘汰的頁14上題OPT頁面置換算法，當(dāng)內(nèi)存塊為4塊時，結(jié)果又是多少？缺頁次數(shù)為6次，缺頁中斷率：f=6/12=50%。課堂練習(xí)次序432143543215頁面分配情況214354321533214354321444321435432是否缺頁是是是是是是是否否是是是淘汰的頁43215433、棧結(jié)構(gòu)實(shí)現(xiàn)LRU頁面置換算法缺頁次數(shù)為10次，缺頁中斷率：f=10/12=83.3%。課堂練習(xí)對于如下的頁面訪問序列：7，1，2，0，3，0，4，2，3，0，3，2，7，0。當(dāng)內(nèi)存塊數(shù)量為4時，試問：使用棧結(jié)構(gòu)實(shí)現(xiàn)LRU置換算法產(chǎn)生的缺頁中斷是多少？寫出依次淘汰的頁號。（所有內(nèi)存開始時都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷。要求寫出計(jì)算步驟。）次序71203042303270頁面分配情況0304303270220304303271112230440327777112222403是否缺頁是是是是是否是否否否否否是否淘汰的頁714缺頁次數(shù)為7次，缺頁中斷率：f=7/14=50%。課堂練習(xí)答案次序432143543215頁面分配情況是否缺頁是是是是是是是否否是是是淘汰的頁43215434、頁計(jì)數(shù)器結(jié)構(gòu)實(shí)現(xiàn)LRU頁面置換算法240304141302012312041122032114052413041523031425022413012312051122課堂練習(xí)對于如下的頁面訪問序列：7，1，2，0，3，0，4，2，3，0，3，2，7，0。當(dāng)內(nèi)存塊數(shù)量為4時，試問：使用LRU計(jì)數(shù)器置換算法產(chǎn)生的缺頁中斷是多少？寫出依次淘汰的頁號。（所有內(nèi)存開始時都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷。要求寫出計(jì)算步驟。）次序71203042303270頁面分配情況是否缺頁是是是是是否是否否否否否是淘汰的頁7143727070121020300410010044214022012243000223444321012305400221717111231221032132333031303200213072333課堂練習(xí)答案缺頁次數(shù)為7次，缺頁中斷率：f=7/14=50%。五、關(guān)于缺頁中斷率的討論（一）概念。假定一個作業(yè)共有n頁，系統(tǒng)分配給它的主存塊是m塊（m,n均是正整數(shù)，且1<=m<=n）.因此，該作業(yè)最多有m頁可同時裝入主存。如果作業(yè)執(zhí)行中訪問頁面的總次數(shù)為A，其中有F次訪問的頁面未裝入主存，故產(chǎn)生了F次缺頁中斷?，F(xiàn)定義：f=F/A把f稱為“缺頁中斷率”。（二）影響缺頁中斷率的因素1、分配給作業(yè)的主存塊數(shù) 分配給作業(yè)的主存塊數(shù)越多，則同時裝入主存的頁面數(shù)就越多，缺頁中斷的次數(shù)就越少。反之，就越高。2、頁面的大小 頁面的大小取決于主存分塊的大小，塊越大則頁面越大，頁面大則作業(yè)的頁數(shù)就越少，一頁內(nèi)裝入的信息量就越大，缺頁中斷的次數(shù)就越少。反之，就越高。3、編制程序的方法 程序編制的方法不同，對缺頁中斷的次數(shù)有很大影響。例如： 有一個程序要把128×128的數(shù)組置初值“0”，數(shù)組中的每一個元素為一個字?，F(xiàn)假定頁面的尺寸為每頁128個字，數(shù)組中的每一行元素存放在一頁。能供這個程序使用的主存塊只有一塊，開始時該內(nèi)存塊為空。若程序編制如下：intA[127,127];for(j=0;j<128;j++) {for(i=0;i<128;i++) {A[i,j]=0;} }由于程序是按列清“0”的，所以每執(zhí)行一次A[i,j]=0(清“0”)就會產(chǎn)生一次缺頁中斷，總共產(chǎn)生了（128*128）次中斷。若重新編制這個程序如下：IntA[127,127]; for(i=0;i<128;i++) { for(j=0;j<128;j++) {A[i,j]=0;} }那么，每裝入一頁后就對一行元素全部清“0”后才產(chǎn)生缺頁中斷，故總共只產(chǎn)生了128次缺頁中斷。4、與頁面調(diào)度算法有關(guān)頁面調(diào)度算法對缺頁中斷率的影響也很大，調(diào)度不好就會出現(xiàn)“抖動”。

例：考慮下面的頁訪問串：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。假定分別有1，2，3，4，5，6，7個頁塊，應(yīng)用下面的頁面替換算法時，各會出現(xiàn)多少次缺頁中斷？（1）LRU；（2）FIFO；（3）Optimal。頁塊號LRUFIFOOptimal12020202171815315161141016115812767977777由上可知：（1）不同的調(diào)度算法，缺頁中斷次數(shù)有差別，其中OPT算法最優(yōu)，但無法實(shí)現(xiàn)，因?yàn)檎l也不能對程序的執(zhí)行中要使用的頁面作出精確的斷言。然而，它可以作為一個衡量各種具體算法的標(biāo)準(zhǔn)。（2）當(dāng)駐留集增加到一定數(shù)量后，三種算法的缺頁中斷次數(shù)，差別不大。課堂練習(xí)：考慮下述頁面走向：4，3，2，1，4，3，5，4，3，2，1，5。當(dāng)內(nèi)存塊分別為3和4時，試問LRU(基于棧結(jié)構(gòu)算法)、FIFO、OPT這三種置換算法的缺頁次數(shù)各是多少（假設(shè)所有內(nèi)存塊起初為空）？次序432143543215頁面分配情況214354321533214354321444321435432是否缺頁是是是是是是是否否是是是淘汰的頁4321543當(dāng)給定的內(nèi)存塊=3時，LRU棧結(jié)構(gòu)算法的置換過程如下：次序432143543215頁面分配情況143543215221435432133321435432444432111543是否缺頁是是是是是是是否否是是是淘汰的頁2154當(dāng)給定的內(nèi)存塊=4時，LRU棧結(jié)構(gòu)算法的置換過程如下：六、一個頁面替換策略的實(shí)用方法（兼顧FIFO和LRU策略）

為頁幀在頁表項(xiàng)中增加一位使用位，硬件每訪存