第五講存儲管理3虛擬存儲

5.6.1虛存的引入5.6虛擬存儲器〔一〕程序一次性裝入內(nèi)存帶來的問題1.單一延續(xù)分配、多道分區(qū)分配、分頁和分段存儲管理的共同特點是： 都需求將程序一次性全部裝入內(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è)！〔二〕程序部分性原理1.時間部分性：一條指令被執(zhí)行后，那么它能夠很快會再次執(zhí)行。如循環(huán)、子程序、堆棧、計數(shù)或累計變量等。2.空間部分性：假設(shè)某一存儲單元被訪問，那么與該存儲單元相鄰的單元能夠也會很快被訪問。如程序代碼的順序執(zhí)行，對線性數(shù)據(jù)構(gòu)造的訪問或處置、常用變量等。問題：能否將部分程序裝入內(nèi)存后就開場運轉(zhuǎn)作業(yè)？為什么？〔三〕程序部分性原理的運用一個程序特別是一個大型程序的一部份裝入內(nèi)存是可以運轉(zhuǎn)的。理由是：1.程序中的某些部份在程序整個運轉(zhuǎn)過程中能夠根本不用。如：出錯處置程序。2.許多表格占用固定數(shù)量的內(nèi)存空間，而實踐上只用到其中的一部份。3.許多程序段是順序執(zhí)行的，還有一些程序段是互斥執(zhí)行的。如菜單項選擇擇功能。4.在程序的一次執(zhí)行過程中，有些程序執(zhí)行之后，從某個時辰起不再用到。〔四〕虛擬存儲器的定義與特性1.虛擬存儲器是指僅把作業(yè)的一部份裝入內(nèi)存便可以運轉(zhuǎn)作業(yè)的存儲器系統(tǒng)。也即，指具有懇求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進展擴展的一種存儲器系統(tǒng)。2.虛擬存儲器的新特性虛擬擴展。不是物理上擴展內(nèi)存空間，而是邏輯上擴展了內(nèi)存。也即是把大的邏輯地址空間映射到較小的物理內(nèi)存上。部分裝入。每個作業(yè)不是全部一次裝入內(nèi)存。只將當(dāng)前要運轉(zhuǎn)的裝入內(nèi)存就開場運轉(zhuǎn)。離散分配。裝入內(nèi)存的部份作業(yè)不用占用延續(xù)的內(nèi)存空間，而是“見縫插針〞。多次對換。一個作業(yè)運轉(zhuǎn)時，它所需求的程序和數(shù)據(jù)分成多次調(diào)入內(nèi)存。而在內(nèi)存中那些暫時不用的程序和數(shù)據(jù)可換出到外存對換區(qū)，以騰出盡量多的內(nèi)存空間供運轉(zhuǎn)進程運用。交換區(qū)〔SWAP〕：進程剛建立時，頁表記錄頁面所在輔存位置，即程序文件所在的外存位置。但程序文件中普通包含有程序的二進制目的碼及數(shù)據(jù)初始值和初值為0的任務(wù)區(qū)。后兩者在回寫時不能寫入程序文件所在輔存區(qū)，因此引入了交換區(qū)—暫時存儲區(qū)。〔就緒掛起、阻塞掛起的進程〕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è)的存放空間?！菜摹程摂M存儲器的定義與特性〔五〕實現(xiàn)虛擬存儲的根本方法 可采用頁式虛存管理、段式虛存管理和段頁式虛存管理。如：頁式虛存管理。在頁式管理的根底上，僅將進程的一部分頁放于主存。頁表項中注明該頁能否在主存。程序執(zhí)行時，假設(shè)訪問的頁不在主存，根據(jù)頁表項的指示，將其從外存調(diào)入主存，假設(shè)此時無可用的內(nèi)存空間，那么先淘汰假設(shè)干頁幀?！财渌椒ǜ疽粯印骋?、根本原理頁式虛擬存儲管理方式是在分頁系統(tǒng)的根底上，添加了懇求調(diào)頁功能、頁面置換功能所構(gòu)成的虛擬存儲器系統(tǒng)。5.7頁式虛存管理形狀位：表示該頁能否曾經(jīng)調(diào)入內(nèi)存。訪問位：表示該頁在內(nèi)存間能否被訪問過修正位：表示該頁在內(nèi)存能否被修正正。頁號內(nèi)存塊號形狀位訪問位修正位外存地址二、頁表項構(gòu)造 對頁表添加了一些工程，詳細(xì)如下：三、地址變換機構(gòu) 與頁式管理根本一樣，只是缺頁時產(chǎn)生缺頁中斷，先將該頁調(diào)入內(nèi)存，再訪問。見以下圖示。指令執(zhí)行步驟與缺頁中斷處置過程★5.8頁面置換算法一、目的與要求： 1、掌握頁面交換戰(zhàn)略中的根本概念 2、掌握駐留集固定的三種頁面交換戰(zhàn)略。 3、掌握影響缺頁中斷率的主要要素 4、了解動態(tài)駐留集的頁面交換戰(zhàn)略。二、重點與難點 1、固定駐留集算法 2、SWS等適用動態(tài)駐留集算法。三、課時：2(90分鐘)四、教法：講授法五、教具六、教學(xué)過程 1、引見有關(guān)概念及交換戰(zhàn)略分類 2、詳細(xì)引見駐留集固定的頁面交換戰(zhàn)略 3、簡單引見可變駐留集交換戰(zhàn)略本節(jié)主要講述的內(nèi)容 一、頁面交換戰(zhàn)略中的根本概念 二、頁面交換戰(zhàn)略的分類 三、駐留集大小固定的交換戰(zhàn)略 四、頁面交換算法解題舉例 五、影響缺頁中斷率的主要要素 六、頁面交換戰(zhàn)略運用實例 七、駐留集可變的交換戰(zhàn)略 八、交換戰(zhàn)略選擇一、頁面交換(戰(zhàn)略)戰(zhàn)略中的根本概念

頁面置換算法：地址映射過程中，假設(shè)在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中，那么產(chǎn)生缺頁中斷。當(dāng)發(fā)生缺頁中斷時操作系統(tǒng)必需在內(nèi)存選擇一個頁面將其移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)那么叫做頁面置換算法(戰(zhàn)略)。一、頁面交換(戰(zhàn)略)戰(zhàn)略中的根本概念駐留集(任務(wù)集)：進程的合法頁集合；也即系統(tǒng)分給一個進程的內(nèi)存可用塊數(shù)。訪問串〔頁面走向〕：進程的存儲訪問序列或進程訪問虛空間的地址蹤跡。頁式虛存管理以頁為根本單位，只需頁號即可。頁面走向可合理簡化。頁面走向可合理簡化原那么：〔1〕對于給定的頁面大小，僅思索其頁號，不關(guān)懷完好的地址?！?〕假設(shè)當(dāng)前對頁面P進展了訪問，那么，馬上又對該頁訪問就不會缺頁。這樣延續(xù)出現(xiàn)的頁號就簡化為一個頁號。舉例：某進程依次訪問如下地址：0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105。假設(shè)頁面大小為100，上述訪問串可簡化為：1，4，1，6，1，6，1，6，1，6，1二、頁面交換戰(zhàn)略分成兩類：駐留集大小固定的交換戰(zhàn)略；駐留集大小可變的交換戰(zhàn)略。三、駐留集大小固定的交換戰(zhàn)略(一)先進先出置換算法(FIFO)(二)最正確置換算法(OPT)(三)最近最少運用算法(LRU)(四)時鐘置換算法(CLOCK)(一)FIFO交換算法置換戰(zhàn)略：優(yōu)先淘汰最早進入內(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方法的特點：實現(xiàn)方便。不需求額外硬件。效果不好，有Belady奇特。〔2〕FIFO存在Belady奇特：指交換戰(zhàn)略不滿足隨著駐留集的增大，頁缺點數(shù)〔缺頁中斷次數(shù)〕一定減少的規(guī)律。這一規(guī)律由Belady于1969年發(fā)現(xiàn)，故稱為Belady異常2.對FIFO交換算法的進一步認(rèn)識〔3〕FIFO算法的Belady奇特景象舉例對于如下的頁面訪問序列：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交換算法置換戰(zhàn)略：當(dāng)要調(diào)入一頁而必需淘汰舊頁時，應(yīng)該淘汰以后不再訪問的頁，或距如今最長時間后要訪問的頁面。1966年，Belady提出最正確(優(yōu))頁面交換算法(OPTimalreplacement，OPT)。是操作系統(tǒng)存儲管理中的一種全局頁面交換戰(zhàn)略。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交換算法的進一步認(rèn)識(1)是最優(yōu)的頁面交換戰(zhàn)略O(shè)PT戰(zhàn)略對恣意一個訪問串的控制均有最小的時空積〔進程所占空間與時間的乘積〕。(2)是不可實現(xiàn)的戰(zhàn)略由于需求預(yù)先得知整個訪問串的序，故不能用于實際,僅作為一種規(guī)范，用以丈量其他可行戰(zhàn)略的性能。(三)LRU交換算法置換戰(zhàn)略：淘汰上次運用距當(dāng)前最遠的頁或最近很少運用的頁。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算法的進一步認(rèn)識到(1)LRU沒有Belady奇特。即隨著駐留集的增大,頁缺點一定減少。(2)需求硬件配合，實現(xiàn)費用高，但效果適中。〔3〕LRU交換算法無Belady奇特景象舉例：對于如下的頁面訪問序列：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算法的實現(xiàn)方法實現(xiàn)方法1：用計數(shù)器實現(xiàn)LRU。實現(xiàn)方法2：用棧實現(xiàn)LRU。實現(xiàn)方法3：用矩陣實現(xiàn)LRU。實現(xiàn)方法4：用存放器實現(xiàn)LRU。實現(xiàn)方法1—用計數(shù)器實現(xiàn)LRU每頁添加一個計數(shù)器，用計數(shù)器方法記錄情況。命中時，剛訪問到的頁計數(shù)器清0，其他頁計數(shù)器加1；淘汰時選擇頁計數(shù)器值最大的頁面，新?lián)Q入的頁計數(shù)器清0，其他頁計數(shù)器加1。例如：舉例：假設(shè)駐留集大小為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次實現(xiàn)方法2—用棧實現(xiàn)LRU可用一個特殊的棧來保管當(dāng)前運用的各個頁面的頁面號。每當(dāng)進程訪問某頁面時便將該面頁從棧中移出，然后將它壓入棧頂。因此，棧頂一直是最新的頁號，而棧底那么是最近最久未運用的頁號。例如:舉例：駐留集大小為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)存中的一切頁面經(jīng)過一個指針鏈接成一個循環(huán)隊列。其算法流程圖如以下圖所示。開場該頁命中？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/-初始留意:假設(shè)循環(huán)鏈表存在當(dāng)前訪問頁(命中)時，直接將其訪問位改為1．指針不挪動〔命中后指針不挪動〕；否那么，假設(shè)當(dāng)前P指針指向頁面的訪問位為0，那么淘汰該頁，調(diào)入新頁．將其訪問位改為1，指針移到下一個物理塊；假設(shè)當(dāng)前P指針指向頁面的訪問位為1．那么將其訪問位改為0,并挪動指針到下一個物理塊。CLOCK算法的優(yōu)點是:比LRU算法少了很多硬件的支持，實現(xiàn)比較簡單，但和FIFO算法相比，仍需求較多的硬件支持。四、頁面交換算法解題舉例例1:在頁式管理中，設(shè)給定的主存塊數(shù)為三塊，知頁面走向為：4，3，2，1，4，3，5，4，3，2，l，5。調(diào)頁時分別采用FIFO算法、OPT算法、棧構(gòu)造實現(xiàn)的LRU算法和計數(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、棧構(gòu)造實現(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時，試問：運用棧構(gòu)造實現(xiàn)LRU置換算法產(chǎn)生的缺頁中斷是多少？寫出依次淘汰的頁號?！惨磺袃?nèi)存開場時都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷。要求寫出計算步驟?！炒涡?1203042303270頁面分配情況0304303270220304303271112230440327777112222403是否缺頁是是是是是否是否否否否否是否淘汰的頁714缺頁次數(shù)為7次，缺頁中斷率：f=7/14=50%。課堂練習(xí)答案次序432143543215頁面分配情況是否缺頁是是是是是是是否否是是是淘汰的頁43215434、頁計數(shù)器構(gòu)造實現(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計數(shù)器置換算法產(chǎn)生的缺頁中斷是多少？寫出依次淘汰的頁號?！惨磺袃?nèi)存開場時都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷。要求寫出計算步驟?！炒涡?1203042303270頁面分配情況是否缺頁是是是是是否是否否否否否是淘汰的頁7143727070121020300410010044214022012243000223444321012305400221717111231221032132333031303200213072333課堂練習(xí)答案缺頁次數(shù)為7次，缺頁中斷率：f=7/14=50%。五、關(guān)于缺頁中斷率的討論〔一〕概念。假定一個作業(yè)共有n頁，系統(tǒng)分配給它的主存塊是m塊〔m,n均是正整數(shù)，且1<=m<=n〕.因此，該作業(yè)最多有m頁可同時裝入主存。假設(shè)作業(yè)執(zhí)行中訪問頁面的總次數(shù)為A，其中有F次訪問的頁面未裝入主存，故產(chǎn)生了F次缺頁中斷?，F(xiàn)定義：f=F/A把f稱為“缺頁中斷率〞?！捕秤绊懭表撝袛嗦实囊?、分配給作業(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)存塊為空。假設(shè)程序編制如下：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〕次中斷。假設(shè)重新編制這個程序如下：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個頁塊，運用下面的頁面交換算法時，各會出現(xiàn)多少次缺頁中斷？〔1〕LRU；〔2〕FIFO；〔3〕Optimal。頁塊號LRUFIFOOptimal12020202171815315161141016115812767977777由上可知：〔1〕不同的調(diào)度算法，缺頁中斷次數(shù)有差別，其中OPT算法最優(yōu)，但無法實現(xiàn)，由于誰也不能對程序的執(zhí)行中要運用的頁面作出準(zhǔn)確的斷言。然而，它可以作為一個衡量各種詳細(xì)算法的規(guī)范。〔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(基于棧構(gòu)造算法)、FIFO、OPT這三種置換算法的缺頁次數(shù)各是多少〔假設(shè)一切內(nèi)存塊起初為空〕？次序432143543215頁面分配情況214354321533214354321444321435432是否缺頁是是是是是是是否否是是是淘汰的頁4321543當(dāng)給定的內(nèi)存塊=3時，LRU棧構(gòu)造算法的置換過程如下：次序432143543215頁面分配情況143543215221435432133321435432444432111543是否缺頁是是是是是是是否否是是是淘汰的頁2154當(dāng)給定的內(nèi)存塊=4時，LRU棧構(gòu)造算法的置換過程如下：六、一個頁面交換戰(zhàn)略的適用方法〔兼顧FIFO和LRU戰(zhàn)略〕為頁幀在頁表項中添加一位運用位，硬件每訪存