頁面置換算法

1、頁面置換算法課題：頁面置換算法 教學目的：通過本節(jié)內(nèi)容的學習，掌握三種頁面置換算法教學重點：三種頁面置換算法的算法過程教學難點：區(qū)分每種算法的算法過程，比較算法的的好壞，選用合理的算法教學方法：講授法、討論法教學對象：高中學生教學內(nèi)容：一、復習舊知識問1：上節(jié)課我們學習了內(nèi)存分配策略和分配算法，請同學們回顧一下，當我 們在為進程分配內(nèi)存時，會涉及到哪三個問題？答1：最小物理塊數(shù)的確定、物理塊的分配策略、物理塊的分配算法問2：那么在請求分頁系統(tǒng)中，我們知道可以采用兩種內(nèi)存分配策略，分別是？答2：固定和可變分配策略問3：在進行置換時，也可采取兩種策略，它們是？答3：全局置換和局部置換結論：因此物理

2、塊的分配策略有三種：固定分配局部置換、可變分配全局置換、 可變分配局部置換二、新知識1、頁面置換算法的概念我們知道，在進程運行過程中，若其所要訪問的頁面不在內(nèi)存，需要把它們 調(diào)入內(nèi)存。但是如果內(nèi)存中已無空閑空間，我們?yōu)榱吮ＷC該進程能正常運行，系 統(tǒng)就必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送磁盤的對換區(qū)中。但是請同學們思考一 下，我們應該將哪個頁面調(diào)出呢？同學們注意了，確定將哪個頁面調(diào)出，并不是憑空想象的，而是須要根據(jù)一 定的算法來確定。通常把選擇換出頁面的算法稱為頁面置換算法置換算法的好壞，將直接影響到系統(tǒng)的性能，因此置換算法很重要那么什么樣的置換算法，才是好的頁面置換算法呢？這里，我們將具有較低的頁

3、面更換頻率的算法稱為好的頁面置換算法。我們用缺頁率來衡量。缺頁率=缺頁次數(shù)訪問次數(shù)100%2、常用的頁面置換算法目前存在著許多種置換算法，下面介紹我們來學習三種常見的置換算法: 最佳置換算法、先進先出置換算法、最近最久未使用置換算法（1）最佳（Optimal）置換算法首先我們來看第一種，最佳置換算法。請同學們記住這樣一句口訣：往后看選擇永遠不再使用的頁面或者最后使用的頁面加以淘汰怎樣理解這句話的含義，我們來看一個例子：假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁面號引用串:7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1進程運行，先時將7、0、1三個頁面裝入

4、內(nèi)存7一個頁框代表一個物理塊01接下來，當進程要訪問頁面2時，將會產(chǎn)生缺頁中斷。頁面0將作為第5個被訪 問的頁面，頁面1最為第14個被訪問的頁面，頁面7作為第18個被訪問的頁面， 根據(jù)我們的口訣，永遠不再使用的頁面或者最后使用的頁面加以淘汰，因此我們 應該選擇頁面7予以淘汰。注意了，這里的最后使用的頁面，并不是最后一個頁 面。同理，我們看下一個頁面。當要訪問頁面0時，因為它已在內(nèi)存而不必產(chǎn)生缺頁 中斷。我們將會產(chǎn)生缺頁中斷的頁框下畫一個勾，不產(chǎn)生缺頁中斷的頁框下畫一個叉。 最開始裝入的三個頁面視為不產(chǎn)生缺頁中斷 問：當訪問頁面3時，同學們思考，我們應該置換出哪個頁面?答：頁面1利用最佳頁面置換

5、算法的置換圖701203042303212017222222 00.0011131701701由圖可看出采用最佳置換算法發(fā)生了 6次頁面置換，缺頁率為6/20*100%=30 請同學們用2分鐘的時間熟悉該算法（2）先進先出（FIFO）頁面置換算法下面我們來看第二種，先進先出頁面置換算法，由該算法的名字可知道，最先進 入的頁面，最先被置換出。請同學們再記住一個口訣：由最老頁面至最新頁面排序，淘汰最老頁面還是同一個例子，我們用先進先出置換算法來做7003042722244003332111000我們將最老的頁面放在最上面，新頁面放在最下面。當訪問頁面2時，根據(jù)頁面 的新老，將置換頁面7,訪問頁面3

6、時，將置換頁面0.剩下的請同學們按照口訣，畫出置換圖問：由圖可看出采用最佳置換算法發(fā)生了幾次頁面置換？答：12次因此缺頁率為：12/20*100%=60%同樣請同學們快速的回憶下該算法 （3）最近最久未使用（LRU）置換算法下面我們來看最后一種算法，最近最久未使用置換算法。口訣：最老頁面排上面，淘汰最老頁面，但是頁面每使用一次刷新一次。細心的同學發(fā)現(xiàn)了，我們這種算法與剛剛的先進先出置換算法有相通的地方，就 是淘汰最老的頁面，但是我們這種算法，每使用一次都會刷新一次。那么怎樣 理解這個“刷新”，我們還是用同樣的例子當訪問頁面2時，置換頁面7淘汰，因為頁面2是新頁面，因此將它放在最下面， 接著訪問頁面0，因為內(nèi)存中有該頁面，雖然不會發(fā)生缺頁中斷，但是根據(jù)口訣， 頁面每使用一次，就要刷新一次，因此，將頁面0放在最下面。請同學們動手，完成接下來的置換圖，熟悉該置換算法并計算出缺頁率。（45%）問：我們已經(jīng)學習了三種置換算法，根據(jù)上述例子比較缺頁率的大小，你有什 么發(fā)現(xiàn)？可以同桌之間討論。答：物理塊數(shù)相同時，最佳置換算法最好，其次是最近最久未使用算法，先進先 出算法最次。3、總結今天我們學習了三種頁面置換算法，他們分別是最佳置換算法，先進先出置換 算法以及最近