第6章 虛擬存儲管理VIP

第6章虛擬存儲器,6.3頁面置換算法,當(dāng)發(fā)生缺頁,而主存中已沒有空閑頁面時，需要選一頁淘汰，這時把選取淘汰頁的方法叫頁的置換算法。,1。頁面替換算法要解決的問題,2。評價頁面替換算法的標(biāo)準,命中率,實現(xiàn)的難易程度,正確反映程序的局部性預(yù)測主存中將發(fā)生的頁面調(diào)度情況,按照什么樣的規(guī)則替換主存儲器中的頁面,第6章虛擬存儲器頁面置換算法,一、概述,3。頁面替換算法的應(yīng)用,Cache中的塊替換,虛擬存儲器中，主存頁面（或程序段）的替換,虛擬存儲器的快慢表中，快表存儲字（行）的替換,虛擬存儲器中，用戶基地址寄存器的替換,某些存儲器中，目錄表的替換,第6章虛擬存儲器頁面置換算法,1隨機算法（RAND算法）,2先進先出算法（FIFO算法）,3最近最久未使用頁面置換算法（LRU算法）,4LRU近似算法,5最少使用置換算法（LFU算法）,二、頁面置換算法,第6章虛擬存儲器頁面置換算法,6頁面緩沖算法,7最佳置換算法（OPT算法）,基本思想：利用軟件或硬件的隨機數(shù)發(fā)生器來確定主存儲器中被替換的頁面。,特點：,最簡單,易實現(xiàn),命中率低,未利用頁面調(diào)度情況的歷史信息,沒有反映程序的局部性,第6章虛擬存儲器頁面置換算法,1隨機算法（RAND算法）,特點：實現(xiàn)簡單替換指針能利用主存儲器中頁面調(diào)度的歷史信息沒有反映程序的局部性,第6章虛擬存儲器頁面置換算法,2先進先出算法（FIFO算法）,基本思想：選擇最先調(diào)入主存儲器的頁面作為被替換的頁面。,圖先進先出算法存儲分塊表構(gòu)造,第6章虛擬存儲器頁面置換算法,第6章虛擬存儲器頁面置換算法,例：在一個請求分頁存儲管理系統(tǒng)中，一個作業(yè)的頁面走向為：P4、P3、P2、P1、P4、P3、P5、P4、P3、P2、P1、P5當(dāng)分配給該作業(yè)的物理塊數(shù)為3時，試計算采用FIFO置換算法時的缺頁率（假設(shè)開始執(zhí)行時主存中沒有頁面）。,缺頁率為：9/12,硬件支持：寄存器堆棧,特點：充分利用主存中頁面調(diào)度的歷史信息正確反映了程序的局部性實現(xiàn)困難,第6章虛擬存儲器頁面置換算法,基本思想：選擇最近最久未使用的頁面進行置換。,3最近最久未使用頁面置換算法（LRU算法）,第6章虛擬存儲器頁面置換算法,例：在一個請求分頁存儲管理系統(tǒng)中，一個作業(yè)的頁面走向為：P4、P3、P2、P1、P4、P3、P5、P4、P3、P2、P1、P5當(dāng)分配給該作業(yè)的物理塊數(shù)為3時，試計算采用LRU置換算法時的缺頁率（假設(shè)開始執(zhí)行時主存中沒有頁面）。,缺頁率為：10/12,第6章虛擬存儲器頁面置換算法,4LRU近似算法,這種算法，只要在存儲分塊表（或頁表）中設(shè)一個“訪問位”，當(dāng)存儲分塊表中的某一頁被訪問時，該位由硬件自動置1，并由頁面管理軟件周期性把所有引用位置0。這樣，在一個時間周期T內(nèi)，某些被訪問過的頁面其引用位為1，而未被訪問過的頁面其引用位為0。因此，可根據(jù)引用位的狀態(tài)來判別各頁面最近的使用情況。當(dāng)需要置換一頁面時，選擇其引用位為0的頁。,4.1LRU近似算法簡單的Clock置換算法,第6章虛擬存儲器頁面置換算法,LRU近似算法Clock算法舉例,第6章虛擬存儲器頁面置換算法,4.2LRU近似算法改進型Clock置換算法,頁面類型：,A=0，M=0最佳淘汰頁,A=0，M=1不是很好的淘汰頁,A=1，M=0該頁有可能被再次訪問,A=1，M=1該頁有可能被再次訪問，最壞淘汰頁,第6章虛擬存儲器頁面置換算法,4.2LRU近似算法改進型Clock置換算法,從指針指示的當(dāng)前位置開始，掃描循環(huán)隊列，尋找A=0&M=0的頁面，將所遇到的第一個頁面作為替換頁，不改變A的值。,第一步失敗，則開始第二輪掃描，尋找A=0&M=1頁面，將所遇到的第一個頁面作為替換頁，將所有經(jīng)過的頁面的A置0。,第二步失敗，則返回第一步，開始第三輪掃描，如果仍然沒找到所需淘汰頁面，則重復(fù)第二步，必然可找到合適的頁面。,第6章虛擬存儲器頁面置換算法,算法流程：,5最少使用置換算法（LFU算法）,基本思想：選擇到當(dāng)前時間為止被訪問次數(shù)最少的頁面被置換,實現(xiàn)方式：,第6章虛擬存儲器頁面置換算法,每頁設(shè)置訪問計數(shù)器，每當(dāng)頁面被訪問時，該頁面的訪問計數(shù)器加1；發(fā)生缺頁中斷時，淘汰計數(shù)值最小的頁面，并將所有計數(shù)清零。,例：一個程序有5個頁面，分別為P1P5。程序執(zhí)行過程中的頁地址流如下：,第6章虛擬存儲器頁面置換算法,P1,P2,P1,P5,P4,P1,P3,P4,P2,P4,設(shè)分配給這個程序的主存有三個頁面，試給出使用LFU頁面替換算法時的主存使用情況。,6頁面緩沖算法,第6章虛擬存儲器頁面置換算法,它是對FIFO算法的發(fā)展，通過被置換頁面的緩沖，有機會找回剛被置換的頁面。,被置換頁面的選擇和處理：,用FIFO算法選擇被置換頁,把被置換的頁面放入兩個鏈表之一,需要調(diào)入新的物理頁面時，將新頁面內(nèi)容讀入到空閑頁面鏈表的第一項所指的頁面，然后將第一項刪除?？臻e頁面和已修改頁面，仍停留在內(nèi)存中一段時間，若這些頁面被再次訪問，只需較小開銷，而被訪問的頁面可以返還作為進程的內(nèi)存頁。當(dāng)已修改頁面達到一定數(shù)目后，將它們一起調(diào)出到外存，然后將它們歸入空閑頁面鏈表，這樣能大大減少I/O操作的次數(shù)。,第6章虛擬存儲器頁面置換算法,7最佳置換算法（OPT算法）,基本思想：選擇不被使用的或?qū)碜罹貌槐辉L問的頁面作為被替換的頁面。,特點：,缺頁率低,無法實現(xiàn),評價其他頁面置換算法好壞的標(biāo)準,第6章虛擬存儲器頁面置換算法,例：在一個請求分頁存儲管理系統(tǒng)中，一個作業(yè)的頁面走向為：P4、P3、P2、P1、P4、P3、P5、P4、P3、P2、P1、P5當(dāng)分配給該作業(yè)的物理塊數(shù)為3時，試計算采用OPT置換算法時的缺頁率（假設(shè)開始執(zhí)行時主存中沒有頁面）。,缺頁率為：7/12,三、堆棧型替換算法,1?；舅枷耄?隨著分配給程序的主存頁面數(shù)的增加，主存的命中率也提高，至少不下降。,第6章虛擬存儲器頁面置換算法,2。堆棧型替換算法,對任意一個程序的頁地址作兩次主存頁面數(shù)分配，分別分配m個主存頁面和n個主存頁面，并且有m=n。如果在任何時刻t，主存頁面數(shù)集合Bt都滿足關(guān)系Bt（m）Bt（n）則這類算法稱為堆棧型算法。,第6章虛擬存儲器頁面置換算法,設(shè)頁地址流為：P1、P2、P3、P4、P1、P2、P5、P1、P2、P3、P4、P5試給出其主存訪問情況。,在下頁圖中，P行表示頁面走向，M行表示在主存中的頁面號，在M行的各列按調(diào)入的順序排列，帶有“*”的數(shù)字表示下一時刻將被淘汰頁面，F(xiàn)行表示主存訪問情況。,【例】主存塊數(shù)m=3，置換算法采用FIFO算法。,第6章虛擬存儲器頁面置換算法,圖FIFO算法主存訪問（M=3）,缺頁率f=9/12=75%,第6章虛擬存儲器頁面置換算法,【例】主存塊數(shù)m=4，置換算法采用FIFO算法。,設(shè)頁地址流為：P1、P2、P3、P4、P1、P2、P5、P1、P2、P3、P4、P5試給出其主存訪問情況。,在下頁圖中，P行表示頁面走向，M行表示在主存中的頁面號，在M行的各列按調(diào)入的順序排列，帶有“*”的數(shù)字表示下一時刻將被淘汰頁面，F(xiàn)行表示主存訪問情況。,第6章虛擬存儲器頁面置換算法,圖FIFO算法主存訪問（m=4）,缺頁率f=10/12=83%,第6章虛擬存儲器頁面置換算法,FIFO算法主存訪問分析,內(nèi)存塊數(shù)缺頁中斷命中次數(shù)缺頁率39375%410283%,隨著分配的主存塊數(shù)的增加，缺頁中斷次數(shù)不但沒有降低，反而增加了。這與該算法完全不考慮程序的動態(tài)特征有關(guān)。,第6章虛擬存儲器頁面置換算法,這種異?，F(xiàn)象稱為Belady現(xiàn)象。,LRU算法和LFU算法是不是堆棧型算法？,對于LFU和LRU算法，由于在主存中保留的是最近使用過的頁面，如果先給某一個程序分配N個主存頁面，那么在T時刻，這N個主存頁面都是最近使用過的頁面。,如果再給這個程序多分配一個主存頁面，那么在T時刻，這N+1個主存頁面也都是最近使用過的頁面。,因此，在這N+1個主存頁面中必然包含了前面的N個主存頁面。,所以，LFU算法和LRU算法都是堆棧型算法。,第6章虛擬存儲器頁面置換算法,【例】主存塊數(shù)m=3，置換算法采用LRU算法。,設(shè)頁地址流為：P1、P2、P3、P4、P1、P2、P5、P1、P2、P3、P4、P5,缺頁率f=10/12=83%,第6章虛擬存儲器頁面置換算法,【例】主存塊數(shù)m=4，置換算法采用LRU算法。,設(shè)頁地址流為：P1、P2、P3、P4、P1、P2、P5、P1、P2、P3、P4、P5,缺頁率f=8/12=67%,第6章虛擬存儲器頁面置換算法,第6章虛擬存儲器頁面置換算法,例：有一矩陣：,VARA：ARRAY1.100,1.100OFINTEGER,按先行后列的次序存儲。,在一頁式虛擬存儲系統(tǒng)中，采用LRU淘汰算法，一個進程有3頁內(nèi)存空間，每頁可以存放200個整數(shù)，其中第一頁存放程序，且假定程序已在內(nèi)存。,程序A：FORI:=1TO100DOFORJ:=1TO100DOAI,J:=0,程序B：FORJ:=1TO100DOFORI:=1TO100DOAI,J:=0,分別就程序A和程序B的執(zhí)行過程計算缺頁次數(shù)。,第6章虛擬存儲器頁面置換算法,三、提高主存命中率的方法,1。程序在執(zhí)行過程中的頁地址流分步情況；,2。所采用的頁面替換算法；,3。頁面大?。?4。主存儲器的容量；,5。所采用的頁面調(diào)度方法。,6.4請求分頁系統(tǒng)性能分析,第6章虛擬存儲器,第6章虛擬存儲器請求分頁系統(tǒng)的性能分析,一、缺頁率對有效訪問時間的影響,有效訪問時間=(1-p)ma+p缺頁中斷時間其中：ma-存儲器的訪問時間p-出現(xiàn)缺頁的概率缺頁中斷時間：缺頁中斷服務(wù)時間1ms將缺頁讀入的時間：尋道時間、旋轉(zhuǎn)時間、數(shù)據(jù)傳送時間進程重新執(zhí)行時間1ms,第6章虛擬存儲器請求分頁系統(tǒng)的性能分析,二、工作集,進程在某段時間里實際上要訪問的頁的集合,常駐集(residentset)常駐集指虛擬頁式管理中給進程分配的物理頁面數(shù)目。常駐集與缺頁率的關(guān)系：每個進程的常駐集越小，則同時駐留內(nèi)存的進程就越多，可以提高并行度和處理器利用率；另一方面，進程的缺頁率上升，使調(diào)頁的開銷增大。進程的常駐集達到某個數(shù)目之后，再給它分配更多頁面，缺頁率不再明顯下降。該數(shù)目是“缺頁率常駐集大小”曲線上的拐彎點(curve).,工作集,第6章虛擬存儲器請求分頁系統(tǒng)的性能分析,例：,一個循環(huán)程序，依次使用P1，P2，P3，P4四個頁面，分配給這個程序的主存頁面數(shù)為3個。試給出分別使用FIFO、LRU和OPT三種頁面替換算法對主存頁面的調(diào)度情況。,第6章虛擬存儲器請求分頁系統(tǒng)的性能分析,三、頁面調(diào)度中的抖動現(xiàn)象,第6章虛擬存儲器請求分頁系統(tǒng)的性能分析,什么是抖動？,從主存中剛剛移走某頁面后，根據(jù)請求馬上又調(diào)入該頁。這種反復(fù)進行入頁和出頁的現(xiàn)象稱為抖動，也叫系統(tǒng)顛簸。它會浪費大量的處理機時間，應(yīng)盡可能避免。,產(chǎn)生抖動的原因,產(chǎn)生抖動的直接原因是頁面置換算法選取不當(dāng)。,第6章虛擬存儲器請求分頁系統(tǒng)的性能分析,抖動的預(yù)防,采用局部置換策略,在CPU調(diào)度程序中引入工作集算法,L=S準則,掛起若干進程,第6章虛擬存儲器請求分頁系統(tǒng)的性能分析,請求分頁存儲管理保留了分頁存儲管理的全部優(yōu)點，特別是它解決了消除碎片的問題。另外，提供了大容量的虛擬存儲器；作業(yè)地址空間不再受實存容量的限制；更有效的利用主存；有利于運行多道程序；提高了系統(tǒng)效率，方便了用戶，特別是大作業(yè)用戶。,缺點是：缺頁中斷增加了處理機時間的開銷，會造成抖動；為防止抖動，會增加系統(tǒng)的復(fù)雜性。,四、請求分頁系統(tǒng)的評價,第6章虛擬存儲器請求分段存儲管理,6.5請求分段存儲管理,為了能實現(xiàn)虛擬存儲，段式邏輯地址空間中的程序段在運行時并不全部裝入內(nèi)存，而是如同請求式分頁存儲管理，首先調(diào)入一個或若干個程序段運行，在運行過程中調(diào)用到哪段時，就根據(jù)該段長度在內(nèi)存分配一個連續(xù)的分區(qū)給它使用。若內(nèi)存中沒有足夠大的空閑分區(qū)，則考慮進行段的緊湊或?qū)⒛扯位蚰承┒翁蕴鋈?。相?yīng)于請求式分頁存儲管理，這種存儲管理技術(shù)稱為請求式分段存儲管理。,圖分段的邏輯地址空間,第6章虛擬存儲器請求分段存儲管理,1段表機制2缺頁中斷機構(gòu)3地址變換機構(gòu),一、請求式分段存儲管理的硬件支持,第6章虛擬存儲器請求分段存儲管理,1段表,類似于請求式分頁存儲管理的頁表，為了實現(xiàn)動態(tài)地址變換和存儲保護，系統(tǒng)要為每一個作業(yè)建立一張段表。段表中的每一個表目對應(yīng)著作業(yè)地址空間的一個程序段，其一般格式為：,第6章虛擬存儲器請求分段存儲管理,2缺段中斷機構(gòu),第6章虛擬存儲器請