15存儲管理4虛擬存儲請求頁式管理1ppt課件

1、1內(nèi)存的物理組織物理地址：把內(nèi)存分成假設(shè)干個大小相等的存儲單元，每個單元給一個編號，這個編號稱為內(nèi)存地址物理地址,絕對地址,實地址,存儲單元占8位，稱作字節(jié)byte。物理地址空間：物理地址的集合稱為物理地址空間主存地址空間，它是一個一維的線性空間。.2程序的邏輯構(gòu)造程序地址：用戶編程序時所用的地址或稱邏輯地址 、虛地址 ，根本單位可與內(nèi)存的根本單位一樣，也可以不一樣。程序地址空間邏輯地址空間、虛地址空間:用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從0開場的，可以是一維線性空間，也可以是多維空間。.34.6虛擬存儲器的根本概念4.6.1 虛擬存儲器的引入4.6.2 虛擬存儲器的實現(xiàn)方法4

2、.6.1 虛擬存儲器的特征.4.6.1虛擬存儲器引入1.常規(guī)存儲器管理方式的特征2.部分性原理3.虛擬存儲器定義.51.前面討論的各種存儲管理方法雖各有專長，但有一些共同的特點: 首先是“一次性分配。 其次是“駐留性。 作業(yè)全部信息，必需一次性裝入內(nèi)存 作業(yè)信息一旦裝入內(nèi)存便不斷駐留到作業(yè)運轉(zhuǎn)終了 一方面使大作業(yè)的運轉(zhuǎn)遭到限制，另一方面又影響了多道程序的實現(xiàn)。 .62、部分性原理 程序的部分性規(guī)律，程序往往會不均勻地高度部分化地訪問內(nèi)存。 .7 1程序在執(zhí)行時，在大多數(shù)情況下仍是順序執(zhí)行的。 這種特性使得程序的執(zhí)行在一段時間內(nèi)被限制在作業(yè)的某一部分范圍。 P.Denning有以下一些論點： 2

3、過程調(diào)用將會使程序的執(zhí)行軌跡由一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域。但在大多數(shù)情況下，過程調(diào)用的深度都不超越5。 在一段時間內(nèi)，程序?qū)痪窒抻谶@些過程的范圍內(nèi)運轉(zhuǎn)。.8 3程序中存在許多循環(huán)構(gòu)造，它們可以多次反復(fù)執(zhí)行。 for i:=1 to n ai:=ai+1;4程序中還包括許多對數(shù)據(jù)構(gòu)造的處置，它們往往都局限于很小的范圍內(nèi)。.9局限性的表現(xiàn)：時間，空間1時間局限性 時間局限性是指最近被訪問的存儲位置，很能夠不久的未來還要被訪問。 支持這種景象的是： (a) 循環(huán)； (b) 子程序； (c) 棧； (d) 用于計數(shù)和總計的變量。 .102空間局限性 空間局限性是指存儲訪問有集成一組的傾向，以致

4、一旦某個位置被訪問到，很有能夠它附近的位置也要被訪問。 支持這種景象的是： a、數(shù)組遍歷； b、代碼的順序執(zhí)行； c、程序員傾向于將相關(guān)的變量定義相互接近存放。 .11 基于部分性原理，作業(yè)沒有必要全部裝入內(nèi)存。 假設(shè)計算機系統(tǒng)把輔助存儲器當(dāng)做主存儲器的擴展，當(dāng)作業(yè)運轉(zhuǎn)時，不是將其全部信息裝入內(nèi)存，而是將必需部分先裝入內(nèi)存，其它部分仍存于輔存中。作業(yè)運轉(zhuǎn)過程中隨時把需求但又不在內(nèi)存的信息裝入內(nèi)存，把暫時不用的信息淘汰出去，以確保作業(yè)的正確運轉(zhuǎn)。 好象這個計算機系統(tǒng)向他們提供了一個容量很大的主存.123、虛擬存儲器的定義 所謂虛擬存儲器是指具有懇求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進展擴展

5、的一種存儲器系統(tǒng)。 虛擬存儲器的大小受計算機系統(tǒng)地址構(gòu)造和可用外存數(shù)量的限制，與實踐內(nèi)存單元的數(shù)量無關(guān)。.134.6.2 虛擬存儲器的實現(xiàn)方式 離散分配存儲管理方式是實現(xiàn)虛擬存儲器的根底。 1.分頁懇求系統(tǒng) 2.分段懇求系統(tǒng).141、頁式虛擬存儲系統(tǒng) 是在分頁系統(tǒng)的根底上，添加了懇求調(diào)頁功能、頁面置換功能所構(gòu)成的分頁懇求系統(tǒng)。 .15硬件支持： (1) 懇求分頁的頁表機制。 (2) 缺頁中斷機構(gòu)。 (3) 地址變換機構(gòu)。 軟件支持： (1) 實現(xiàn)懇求調(diào)頁的軟件。 (2) 實現(xiàn)頁面置換的軟件。 .162、懇求分段系統(tǒng) 這是在分段系統(tǒng)的根底上，添加了懇求調(diào)段及分段置換功能后，所構(gòu)成的段式虛擬存儲系

6、統(tǒng)。 .17為了實現(xiàn)懇求分段，系統(tǒng)要提供硬件支持： (1) 懇求分段的段表機制。 (2) 缺段中斷機構(gòu)。 (3) 地址變換機構(gòu)。 同樣地，懇求調(diào)段和段的置換功能的實現(xiàn)也需求得到OS的支持。 .184.6.3 虛擬存儲器的特征 離散性是虛擬存儲器最根本的要求，虛擬性是它的最重要特征，另外虛擬存儲器還具有多次性和對換性。 .191、離散性 離散性是指在內(nèi)存分配時采用離散分配方式。2、多次性 作業(yè)分多次裝入內(nèi)存 3、對換性運轉(zhuǎn)時換進換出 4、虛擬性邏輯上擴展內(nèi)存容量 最根本特性.204.7 懇求分頁存儲管理方式 懇求分頁存儲管理方式是建立在純分頁根底上的. 其根本思想:在進程開場運轉(zhuǎn)之前，不是裝入全

7、部頁面，而是裝入一個或零個頁面，之后根據(jù)進程運轉(zhuǎn)的需求，動態(tài)裝入其它頁面；當(dāng)內(nèi)存空間已滿，而又需求裝入新的頁面時，那么根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面.214.7.1 懇求分頁中的硬件支持 一、頁表機制 二、缺頁中斷機構(gòu)三、地址變換機構(gòu) 頁表的作用是實現(xiàn)從用戶地址空間中的邏輯地址到內(nèi)存空間的物理地址的轉(zhuǎn)換。.22 懇求頁式管理中對地址空間分頁，內(nèi)存分塊與根本分頁管理一樣，但對虛頁的管理是不同的。 要訪問的頁面不在內(nèi)存中，如何發(fā)現(xiàn)和處置這種情況？這是懇求分頁存儲管理要處理的兩個根本問題.23 在純分頁系統(tǒng)中，頁表的內(nèi)容為：頁號物理塊號針對第一個問題：如何發(fā)現(xiàn)要訪問的頁面不在內(nèi)存？擴展頁

8、表：頁號物理塊號形狀位P外存地址.24針對第二個問題：怎樣調(diào)入頁面？ 由地址變換機構(gòu)產(chǎn)生一個缺頁中斷信號，OS進展中斷處置后，根據(jù)該頁的外存地址把它從外存調(diào)入內(nèi)存。 引進修正位和訪問字段。.25懇求分頁系統(tǒng)中，頁表項如下： 頁號物理塊號形狀位P訪問字段A 修正位M外存地址(1)形狀位駐留位P:該頁是在內(nèi)存還是在外存(2)訪問字段位A：記錄本頁在一段時間內(nèi)被訪問的次數(shù);根據(jù)訪問位來決議淘汰哪頁由不同的算法決議 (3)修正位M :該頁調(diào)入內(nèi)存后能否在被修正正(4)外存地址:該頁在外存上的地址,通常為外存物理塊號.26 在虛擬存儲系統(tǒng)中，當(dāng)一個作業(yè)被編譯或經(jīng)鏈接裝配后得到的地址空間，通常存在磁盤上。

9、頁號物理塊號維護信息外頁面表 當(dāng)一個作業(yè)被調(diào)度到而裝入內(nèi)存時，系統(tǒng)為它在內(nèi)存建立一張頁表。.272、缺頁中斷機構(gòu) 在懇求分頁系統(tǒng)中，當(dāng)要訪問的頁面不在內(nèi)存時，硬件發(fā)一個缺頁中斷，轉(zhuǎn)交OS處置。.28(1)在指令執(zhí)行期間產(chǎn)生和處置中斷信號。 (2)一條指令在執(zhí)行期間，能夠產(chǎn)生多次缺頁中斷。 它跟普通的中斷有著明顯的區(qū)別：.29頁面654321Copy ATo BB：A：.303、地址變換機構(gòu) 懇求分頁系統(tǒng)中的地址變換機構(gòu)是以分頁系統(tǒng)的地址變換機構(gòu)為根底的，還添加了產(chǎn)生缺頁中斷、處置缺頁中斷，置換等功能。 .31 在進展地址變換時，首先去檢索快表； 假設(shè)快表中沒有這一頁的頁表項，再到內(nèi)存中找頁表，

10、根據(jù)形狀位P來判別該頁能否在內(nèi)存中。在內(nèi)存，將該頁的頁表寫入快表；快表滿時，調(diào)出某頁表項，再寫入該頁的頁表項不在內(nèi)存，那么產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷處置程序，根據(jù)頁表中給出的外存地址，將該頁調(diào)入內(nèi)存，使作業(yè)繼續(xù)運轉(zhuǎn)下去假設(shè)內(nèi)存中有空閑塊，那么分配一頁，將新調(diào)入頁裝入內(nèi)存，并修正頁表中相應(yīng)頁表工程的駐留位及相應(yīng)的內(nèi)存塊號假設(shè)此時內(nèi)存中沒有空閑塊，那么要淘汰某頁，假設(shè)該頁在內(nèi)存期間被修正正，那么要將其寫回外存,否那么不寫.32圖4-25 這里僅僅給出一個很粗略的框圖，詳細的過程是很復(fù)雜的。由于作業(yè)的副本是以文件方式存于外存上，因此要求頁面?zhèn)鬏敃r，必然要涉及到文件系統(tǒng)，此

11、外，還得調(diào)用輸入輸出進程。在多道程序環(huán)境下，一個作業(yè)在等待傳輸頁時，它處于被阻塞的形狀。此時，由系統(tǒng)調(diào)度另一作業(yè)運轉(zhuǎn)。當(dāng)頁面?zhèn)鬏斖瓿珊?，才把原先被阻塞的那個作業(yè)重新置成就緒形狀，但要等到再次調(diào)度到它時，才干恢復(fù)到原先中斷的地方繼續(xù)運轉(zhuǎn)下去。 .334.7.2 內(nèi)存分配戰(zhàn)略和分配算法 在為進程分配物理塊時，又要處理三個問題：1、保證進程正常運轉(zhuǎn)而需求的最少物理塊數(shù)；2、進展分配時，物理塊數(shù)目是固定的還是可變的；分配戰(zhàn)略3、是采取平均分配算法還是根據(jù)進程的大小按比例分配物理塊。.341、最小物理塊數(shù)確實定 最小的物理塊數(shù)，是指保證進程正常運轉(zhuǎn)所需的最少物理塊數(shù)。 最少物理塊數(shù)與指令的格式、功能和尋

12、址方式有關(guān)，也就是說與計算機的硬件構(gòu)造有關(guān)。 如:單地址指令且直接尋址系統(tǒng),至少2塊指令塊/數(shù)據(jù)塊.352、物理塊的分配戰(zhàn)略1)、固定分配部分置換Fixed Allocation, Local Replacement基于進程的類型,為每個進程分配一定數(shù)目的物理塊(n塊),在整個運轉(zhuǎn)其間不變;如缺頁: n塊中置換一頁,以保證該進程在內(nèi)存中的頁面數(shù)不變;問題: 多少個物理塊適宜?物理塊太多:資源空閑.物理塊太少:頻繁中斷 采取固定和可變分配戰(zhàn)略 .362)、可變分配全局置換空閑物理塊隊列先為每個進程分配一定數(shù)目的物理塊,OS也堅持一個空閑物理塊隊列,當(dāng)進程缺頁時,由系統(tǒng)從空閑物理塊隊列取出一個物理

13、塊分配給該進程,并將要調(diào)入的(缺)頁裝入內(nèi)存.僅當(dāng)空閑物理塊隊列中的物理塊用完時,OS才從內(nèi)存中任一進程的一頁調(diào)出.問題: 會使被調(diào)出頁的進程缺頁,進而使缺頁率添加,影響其它進程的執(zhí)行.373)、可變分配部分置換要求堅持適當(dāng)?shù)娜表撀?基于進程的類型,為每個進程分配一定數(shù)目的物理塊, 進程如缺頁: 只從該進程在內(nèi)存中的頁面中換出一頁,這樣不會影響其它進程;假設(shè)進程在運轉(zhuǎn)其間頻繁發(fā)生缺頁中斷,那么系統(tǒng)再為該進程分配假設(shè)干個附加物理塊,直至進程的缺頁率減少到適宜為止;假設(shè)進程的缺頁率特別低,可適當(dāng)減少已分配該進程的物理塊數(shù)目.383、物理塊分配算法 在固定分配戰(zhàn)略中，系統(tǒng)在為各個進程分配物理塊時，可

14、采?。?1)、平均分配算法 .39 系統(tǒng)中多進程頁面數(shù)的總和為： 每個進程所能分到的物理塊數(shù)bi=Si/S m，m為可用的物理總數(shù)。 3)、思索優(yōu)先權(quán)的分配算法 2)、按比例分配算法 ，Si為某個進程的頁面數(shù)。 .404.7.3 調(diào)頁戰(zhàn)略1、何時調(diào)入頁面2、從何處調(diào)入頁面3、頁面調(diào)入過程1預(yù)調(diào)頁戰(zhàn)略2懇求調(diào)頁戰(zhàn)略用于初次調(diào)入.412、從何處調(diào)入頁面 (1)系統(tǒng)擁有足夠的對換區(qū)空間。 當(dāng)缺頁時，全部從對換區(qū)把所需的頁面調(diào)入內(nèi)存，使調(diào)頁速度提高。 要求: 進程運轉(zhuǎn)前,把進程相關(guān)文件拷入對換區(qū)在懇求分頁系統(tǒng)中,外存分為兩部分:文件區(qū)和對換區(qū).42剛開場時，都放在文件區(qū) 文件區(qū)對換區(qū)不改改外存能夠被修

15、正 不會被修正內(nèi)存(2)系統(tǒng)短少足夠的對換區(qū)空間。 .43(3) UNIX方式 與進程有關(guān)的文件都放在文件區(qū)。沒有運轉(zhuǎn)過的頁面，從文件區(qū)調(diào)入內(nèi)存；曾經(jīng)運轉(zhuǎn)過又被換出的頁面，放在對換區(qū)，下次調(diào)入時，從對換區(qū)調(diào)入。文件區(qū)對換區(qū)第一次內(nèi)存外存.44外存物理塊號內(nèi)存有空：調(diào)入內(nèi)存不空：換出一頁修正位為1，重新寫入外存修正位為0，不用寫入外存將缺頁調(diào)入內(nèi)存修正頁表，寫入快表物理地址訪問數(shù)據(jù)3、頁面調(diào)入過程 .454.8.1最正確置換算法和先進先出算法4.8 頁面置換算法4.8.2最近最久未用置換算法4.8.3CLOCK置換算法4.8.4其他置換算法.464.8.1最正確置換算法和先進先出算法4.8 頁面

16、置換算法 假定作業(yè)p合計n頁，而系統(tǒng)分配給它的主存塊只需m塊m,n均為正整數(shù)，mn，即最多只能包容m頁。假設(shè)程序p在運轉(zhuǎn)中勝利的訪問次數(shù)為s,不勝利的訪問次數(shù)為f,那么，其總的訪問次數(shù)a=s+f，假設(shè)定義f =f/a，稱f 為缺頁中斷率。缺頁中斷率:.47影響缺頁中斷次數(shù)的要素1分配給進程的物理頁面數(shù)物理頁面數(shù)多，缺頁中斷少，反之，那么缺頁中斷多物理頁面數(shù)多，進程數(shù)少影響系統(tǒng)效率，反之，那么進程數(shù)多缺頁中斷多根據(jù)實驗分析：對一共有n頁的進程來說，只需能分到n/2塊內(nèi)存空間，就可使系統(tǒng)獲得最高效率；2頁面本身的大小頁面大，進程的頁數(shù)少，一頁的信息就大，缺頁中斷次數(shù)減少；不同的計算機系統(tǒng)，有不同頁

17、面大?。?48例：程序要把128128的數(shù)組初值置“0，數(shù)組中每一個元素為一個字，假定頁面大小為128個字，數(shù)組中的每一行元素存放一頁，能供該程序運用的主存塊只需1塊。初始時第一頁在內(nèi)存；程序編制方法1： For j:=1 to 128 For i:=1 to 128 Aij:=0;按列：缺頁中斷次數(shù)：1281281程序編制方法2： For i:=1 to 128 For j:=1 to 128 Aij:=0;按行：缺頁中斷次數(shù) 128-13程序的編制方法可見：缺頁中斷率與程序的部分化程度親密相關(guān)。希望編制的程序能經(jīng)常集中在幾個頁面上；.491,11,21,31,41,51,61,71,81,

18、91,102,13,14,15,16,17,18,19,110,1.50 (4) 頁面淘汰算法實際的頁面淘汰算法應(yīng)該選擇的被淘汰頁面將是以后永不運用的，或在最長(未來)時間內(nèi)不再被訪問的頁面。OPT算法。實踐上，可以用實際的頁面淘汰算法作規(guī)范，選擇其它較好的頁面淘汰算法頁面淘汰算法選擇不適宜，會使系統(tǒng)“抖動.51 剛被換出的頁很快又被訪問，需求重新調(diào)入，為此又需再選出一頁調(diào)出；而剛被換出的頁，很快又要被訪問，又需把它調(diào)入，如此頻繁地改換頁面，以致一個進程在運轉(zhuǎn)中，把大部分時間破費在完成頁面的置換任務(wù)上，使得調(diào)度頁面所需時間比進程實踐運轉(zhuǎn)的時間還多. 我們稱該進程發(fā)生了“抖動。 抖動.52 最正

19、確置換算法是由Relady在1966年提出的，這種算法選擇的被淘汰頁面，將是永不運用的，或在最長時間內(nèi)不再被訪問的頁面。 最正確置換算法是指對于恣意的內(nèi)存固定空間m和程序 p,有缺頁中斷率最小。它是一個實際上的算法。1、最正確置換算法OPT .53 假定系統(tǒng)為某進程分配了三個物理塊，并思索有以下的頁面號援用串。 123456789101112131415161718192021701203042303122011710770071701423423021200230321021201170170130302 采用最正確置換算法，只發(fā)生了6次頁面置換，發(fā)生了9次缺頁中斷。缺頁率=9/21.542

20、、先進先出頁面置換算法FIFO 這是最早出現(xiàn)的置換算法，這種算法總是淘汰最先進入內(nèi)存的頁面，選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。.55 我們來看看采用FIFO算法進展頁面置換時的情況。 7170217031024512360237430842094231002311-130131401215-18712197022070121一共發(fā)生了12次頁面置換，比最正確置換算法多了1倍。缺頁率15/21=3/4，15次頁面中斷。 123456789101112131415161718192021701203042303122011710.56FIFO的兩個實現(xiàn)方法：1.在主存中建立一個有m(m是分配

21、給該作業(yè)的存貯塊數(shù))個元素的頁號表和一個交換指針。Pi(i=0,1,2,m-1)指示在一個內(nèi)存中的頁面的頁號。交換指針K指向進入主存最老的那一頁。每當(dāng)一頁新頁調(diào)入后，執(zhí)行語句： pk=新的頁號； k=(k+1) mod m;交換指針指向最老的一頁2451頁 號.572.把進入內(nèi)存的次序建立在存貯分塊表中該表以塊號為序，依次登記各塊的分配情況。 0 1 2 4 6 3 4 2 5 6 5 7 7 1 4塊號 頁號 指針2交換指針 0 1 2 6 3 4 2 2 5 6 5 7 7 1 4塊號 頁號 指針6交換指針(a) 交換之前(b) 交換之后.58 FIFO是根據(jù)各個頁面調(diào)入內(nèi)存的時間來選擇被

22、淘汰頁面，但頁面調(diào)入的先后并不能反映頁面的運用情況。 FIFO算法只是在按線性順序訪問地址空間才是理想的。 未思索到程序的動態(tài)特性。 能夠引起異常。.59先進先出置換算法的一個異常景象：對于一些特定的頁面訪問序列，先進先出置換算法有隨著分給的頁架數(shù)添加，缺頁頻率也添加的異常景象。A B C D A B E E E C D D A B C D A B B B E C C A B C D A A A B E E+ + + + + + + + + 頁面訪問序列 A B C D A B E A B C D E九次缺頁三個頁面A B C D D D E A B C D E A B C C C D E A

23、 B C D A B B B C D E A B C A A A B C D E A B+ + + + + + + + + + 頁面訪問序列 十次缺頁四個頁面.604.8.2 最近最久未運用LRU置換算法 1、LRULeast Recently Used算法的描畫 根本思想：基于程序的部分性原理，在前面幾條指令中運用頻繁的頁面很能夠在后面的幾條指令中頻繁運用，反之，曾經(jīng)很久沒有運用的頁面很有能夠在未來較長一段時間內(nèi)不會運用；因此，在缺頁發(fā)生時，淘汰掉最久未運用的頁；選擇淘汰的頁面是最近最久未運用.61 我們用“最近的過去來直接推斷“最近的未來。 770700711212003002340432

24、024324300322132132012011701017發(fā)生了9次頁面置換。 標(biāo)明訪問時間 123456789101112131415161718192021701203042303122011710.622、LRU算法的硬件支持為了實現(xiàn)LRU算法必需處理： 1一個進程在內(nèi)存中的各個頁面各有多久時間未被進程訪問； 2如何快速地知道哪一頁是最近最久未運用的頁面。 .631、存放器 為每個在內(nèi)存中的頁面配置一個移位存放器，表示為： R=Rn-1Rn-2Rn-3R1R2R0 當(dāng)進程訪問某物理塊時，要將相應(yīng)的存放器的Rn-1位置為1。 定時信號將每隔一定時間將存放器右移一次，把n位存放器的數(shù)看作是

25、一個無符號的整數(shù)，最近最久未運用的頁面就對應(yīng)著具有最小數(shù)值的存放器 。用于記錄某進程在內(nèi)存中各頁的運用情況。.642、棧 LRU置換算法可用堆棧的方法來實現(xiàn)。 棧中存放當(dāng)前內(nèi)存中的頁面號，每當(dāng)訪問一頁時就調(diào)整一次堆棧，總是使最近訪問的那頁的頁面號堅持在棧頂，然后根據(jù)當(dāng)前被訪問時間的近遠，依次陳列，棧底總是最近最久未運用的那頁的頁面號。 淘汰.651121231234214312431234215621237651241256125612561265126313276327作業(yè)固定占用4塊主存 例如，某作業(yè)按以下頁號訪問： .66 作 業(yè) 某程序在內(nèi)存中分配三個頁面，初始為空，頁面走向為4，3，

26、2，1，4，3，5，4，3，2，1，5。請分別用FIFO,LRU和OPT算法計算缺頁中斷次數(shù)。.674.8.3 CLock置換算法 CLock算法就是用得較多的一種LRU近似算法。 .681、簡單的CLock置換算法 這種算法的本質(zhì)是：當(dāng)需求置換一頁時，選擇在最近一段時間內(nèi)最久未用的頁予以淘汰，因此稱為最近未用的算法NRUNot Recently Used。.69 這種近似算法，要求為每一頁設(shè)置一位訪問位，再將內(nèi)存中的一切頁面都經(jīng)過指針按FIFO鏈成一個循環(huán)隊列。 當(dāng)某頁被訪問時，訪問位由硬件自動置“1。我們可以根據(jù)訪問位的形狀來判別各個頁面最近運用的情況。假設(shè)是“0，就選擇該頁換出；假設(shè)為1

27、，那么重新將它置為0，再按照FIFO算法檢查下一個頁面。 該算法是對FIFO算法的改良，思索到頁面能否被訪問。.70塊號頁號訪問位指針0124034215650711交換指針總是指向最近被交換的頁所在的存儲塊，缺頁時從其后一塊開場。.712、改良型CLock置換算法 1類 A=0，M=0，最近既未被訪問，又未被修正，是最正確淘汰頁。 2類 A=0，M=1，最近未被訪問，但已被修正，不是很好的淘汰頁。 3類 A=1，M=0，最近已被訪問，但未被修正，能夠再被訪問。 既要思索到頁面的運用情況，還要思索置換代價 4類 A=1，M=1，最近已被訪問且被修正，能夠再被訪問。 根據(jù)訪問位A和修正位M的組合

28、來確定.72改良型CLock算法，執(zhí)行過程可分為以下三步： 1從指針的當(dāng)前位置開場，掃描按先進先出循環(huán)隊列，尋覓A=0且M=0的第一類頁面，將符合條件的第一個頁面作為淘汰頁，在第一次掃描期間A不改動。 .732第一步失敗，開場第二輪掃描，尋覓A=0且M=1的第二類頁面，將符合條件的第一個頁面作為淘汰頁。將一切經(jīng)過的頁面的訪問位置0。3第二步也失敗，把指針前往到開場的位置，把一切的訪問位A置為0，然后反復(fù)第一步，如還是失敗，反復(fù)第二步，就一定能找到被淘汰的頁。.74改良型Clock算法的特點該算法與簡單 Clock算法比較，可減少磁盤的I/O操作次數(shù)，但為了找到要淘汰的頁面，能夠需求經(jīng)過幾輪掃描

29、，使該算法本身的開銷有所添加。.754.8.4 其它置換算法1、最少運用Least Frequently Used置換算法LFU 既可實現(xiàn)LRU，也可實現(xiàn)LFU 為內(nèi)存中的每個頁面設(shè)置一個移位存放器，用來記錄頁面被訪問的頻率，淘汰頁是最少運用或是訪問次數(shù)最少的頁面。 ri最小的頁就是最近一段時間運用最少的頁面。.762、頁面緩沖算法Page Buffering Algorithm PBA 淘汰頁面未修正修正正空閑頁面鏈表末尾已修正頁面的鏈表中末尾采用可變分配和部分置換方式，采用FIFO置換算法 實踐上,頁面在內(nèi)存中并不做物理上的挪動,只是將頁表中的表項移到上述鏈表;這種方法, 修正或未修正的頁

30、面還在內(nèi)存中,當(dāng)該進程需求再次訪問這些頁面時,破費很小就能使這些頁面前往到進程中; 當(dāng)被修正的頁面數(shù)目到達一定值時,一同寫回磁盤上,從而顯著減少磁盤I/O的操作次數(shù);.771、抖動產(chǎn)生的緣由和預(yù)防方法 不適當(dāng)?shù)靥岣叨嗟莱绦蚨?，不僅不會提高系統(tǒng)吞吐量，反而會出現(xiàn)“抖動景象，就是剛被換出頁很快要被訪問，需重新調(diào)入，因此在調(diào)入前要先選一頁調(diào)出；而這個剛被換出的頁，很快又要被訪問，又要將它調(diào)入，如此頻繁地改換頁面，以致一個進程在運轉(zhuǎn)時，把大部分時間破費在頁面置換的任務(wù)上，我們稱該進程發(fā)生了“抖動。性能問題分析.781、抖動產(chǎn)生的緣由 調(diào)度程序一旦發(fā)現(xiàn)CPU的利用率降低，就立刻提高多道程序度，引入新的進

31、程參與運轉(zhuǎn)，以提高CPU的利用率。當(dāng)新進程進入內(nèi)存時，由于空閑物理塊隊列中的物理塊都用完了，只能從其它運轉(zhuǎn)進程處去獲得物理塊，于是又將進一步加劇了另外一些進程的缺頁情況，又使等待頁面調(diào)入/調(diào)出的進程數(shù)目增多，這又降低了CPU的利用率。.79 那么為了提高CPU的利用率，調(diào)度程序又去引入新的進程，這就產(chǎn)生了惡性循環(huán)，使缺頁率急劇地上升。這時候，運轉(zhuǎn)進程的大部分時間都用于進展頁面的換入/換出，幾乎不能完成任何有效的任務(wù)，我們稱這時的進程是處于“抖動形狀。 .80CPU利用率多道程序度從圖中可看出CPU的利用率和多道程序度之間的關(guān)系。開場時，CPU的利用率隨著程序度的提高而提高，到達某一峰值后，假設(shè)繼續(xù)添加多道程序度，將產(chǎn)生抖動，從而導(dǎo)致CPU的利用率急劇下降。