頁面置換算法教案

1、實 習 生 試 教 教 案計算機科學 學院(系) 計算機科學與技術 專業(yè) 2009 年級 班實習生 試教課程 頁面置換算法實習學校 實習班級 七年級二班 實習課時 3 月 19 日 (星期 二 ) 第 3 節(jié) 中學指導教師 _ _ 3 月 18 日 批準系指導教師 3 月 18 日 批準課題頁面置換算法教學目的使學生了解實現(xiàn)請求分頁系統(tǒng)時，為解決內(nèi)存空間不足的問題所采用的幾種頁面置換算法的各自的原理及實現(xiàn)的技術。教學重點和難點教學重點：最佳置換算法和LRU置換算法的實現(xiàn)原理及技術，以及不同頁面置換算法性能的比較和評價。教學難點：理解并掌握LRU算法的原理及性能評價。課的類型傳授知識課教學方法說

2、教法、啟發(fā)提問法等教學用具多媒體演示，黑板等教學過程6.3.1 最佳置換算法和先進先出算法 兩種極端的算法，前者具有最好的性能，卻難于實現(xiàn)，后者是性能最差的算法，卻是最直觀的算法，實際應用很少。一、最佳置換算法最佳置換算法是有Belady于1966年提出的算法。其所選擇的被淘汰的頁面將是以后永不使用的，或許是在最長（未來）時間內(nèi)不再被訪問的頁面。對于固定分配方式，該算法可獲得最低的缺頁率。由于無法預知一個進程在內(nèi)存的若干個頁面中，哪個頁面是未來最長時間內(nèi)不再被訪問的，所以，該算法是無法實現(xiàn)的。但可用它去評價其它算法。 例：假定系統(tǒng)為某進程分配了三個物理塊，并有以下的頁面號引用串： 7,0,1,

3、2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1進程運行時先將7,0，1三個頁面裝入內(nèi)存，以后，當訪問頁面2時，產(chǎn)生缺頁中斷，OS根據(jù)最佳置換算法，選擇頁面7予以淘汰，因為頁面0在第5次時被再訪問，頁面1在第14次再被訪問，而頁面7要在第18次時被再訪問時才需調(diào)入。再訪問0頁面時，則不會產(chǎn)生缺頁中斷，而當進程訪問頁面3時，又引發(fā)頁面1被淘汰，以此類推，直至進程完成，其運行過程中只發(fā)生了6次頁面置換。二、先進先出頁面置換算法這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進入內(nèi)存的頁面，即教學過程選擇內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單，只需把一個進程已調(diào)入內(nèi)存的頁面，按

4、先后次序鏈接成一個隊列，并設置一個指向最老頁面的替換指針即可。例：假定系統(tǒng)為某進程分配了三個物理塊，并有以下的頁面號引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 若采用先進先出置換算法，共發(fā)生12次置換。Belady現(xiàn)象陷阱現(xiàn)象：分配的頁面數(shù)增多，缺頁次數(shù)反而增加。正常情況，例：一進程分配3個頁框，頁面訪問次序：7,0，1,2，0,3，0,4，2,3，0,3，2,1，2,0，1缺頁12次，若分配4個頁面，發(fā)生9次缺頁；另一情況，例：一進程分配3個頁框，訪問串：1,2，3,4，1，,2，5,1，2,3，4,5缺頁9次，若分配4個頁框，發(fā)生10次缺頁。原因

5、：沒有考慮程序執(zhí)行的動態(tài)特征。6.3.2 最近最久未使用LRU置換算法一、LRU算法的描述最近最久未使用（LRU）的頁面置換算法，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進行決策的。由于無法預測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。 例：對頁面號引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1利用LRU算法進行頁面置換，其結果如圖：教學過程二、LRU算法的硬件支持LRU對各種類型的程序都能適用，但實現(xiàn)復雜，須利用一些硬件支持解決一些問題：(1)一個進程在內(nèi)存中的各個頁面各有多久時

6、間未被進程訪問(2)如何快速地知道哪一頁是最近最久未使用的頁面。1、寄存器 用于記錄某進程在內(nèi)存中各頁的使用情況，需為每個在內(nèi)存中的頁面配置一個移位寄存器，表示為：R= Rn-1 Rn-2 Rn-3 R2 R1 R0 2、堆棧利用一個特殊的棧來保存當前使用的各個頁面的頁面號。當進程訪問某頁面時，將該頁面的頁面號從棧中移出，將它壓入棧頂，所以，棧頂始終是最新被訪問的頁面的編號，而棧底則是最近最久未使用頁面的頁面號。6.3.3 Clock置換算法一、簡單的Clock置換算法（最近未用算法NUR ）該算法只須為每頁設置 一位訪問位表示是否已使用過，再將內(nèi)存中的所有頁面都通過鏈接指針鏈成一個循環(huán)隊列。

7、當某頁被訪問時，其訪問位被置為1。置換算法在選擇一頁淘汰時，只須檢查其訪問位，若是0，就選擇該頁換出，若為1 ，則重新將它復為0，暫不換出而給該頁第二次駐留內(nèi)存的機會，再按照FIFO算法檢查下一個頁面。當檢查到隊列中的最后一個頁面時，若其訪問位仍為1，則返回隊首再去檢查第一個頁面。該算法：只有一位訪問位，表示是否已經(jīng)使用過，置換時是將未使用過的頁面換出去，所以，又稱為最近未用算法NUR(not used recently)，系統(tǒng)周期性地對引用位清零。二、改進型Clock置換算法將一個頁面換出時，若該頁已被修改過，則須將它重新寫到磁盤上，若未被修改過，則不必寫回磁盤。改進型Clock算法中，增加

8、了一個置換代價，利用一個修改位實現(xiàn)之。選擇換出頁面時，既要是最近未訪問過的頁面，又要是未被修改過的頁面。教學過程6.3.4 其他置換算法一、最少使用置換算法LFU(Least Frequently Used)該算法，為在內(nèi)存中的每個頁面設置一移位寄存器，每次訪問時，對該頁移位寄存器的最高位置為1，每隔一定時間T右移一次，用于記錄該頁面被訪問的頻率。二、頁面緩沖算法PBA(Page Buffering Algorithm)該算法采用的可變分配和局部置換方式，置換算法采用FIFO，規(guī)定將一個被淘汰的頁放入兩個鏈表中的一個。即：若頁面未被修改，就將它直接放入空閑鏈表中，否則，便放入已修改頁面的鏈表中。此時，頁面在內(nèi)存并不做物理上的移動，而只是將頁表中的表項移到上述兩個鏈表之一中。另外，（1）隨機淘汰算法。隨機選擇某個用戶的頁面進行置換。（2）輪轉法，循環(huán)換出內(nèi)存空間中的頁，無論該頁是否剛被換進或已換進內(nèi)存很長時間。課后作業(yè)：1.了解各種頁面置換算法的工作原理；2.熟練掌握最佳置換算法、先進先出置換算法、LRU置換算法、CLOCK置換算法等常用置換算法；3.思考影響缺頁中斷率的因素有哪些？(1)分配給作業(yè)的主存塊數(shù)。成反比。(2)頁面的大小。反比。(3)作業(yè)本身的程序編制方法。(4)調(diào)度算法