頁面置換算法

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

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

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

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

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

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