Java語言實現(xiàn)模擬頁面置換算法

1、前言 在存儲管理當(dāng)中，頁面置換算法通常可分為兩種：一種基于進(jìn)程駐留集大小不變；另一種基于駐留集大小可變。在駐留集大小不變的頁面置換算法當(dāng)中，常用的算法主要有：fifo、opt 、lru。本文討論的對象是fifo、lru算法。在進(jìn)程運(yùn)行過程中，若所要訪問的頁面不在內(nèi)存中，需要調(diào)入頁面時，選擇內(nèi)存中的那個物理頁面將其調(diào)出。通常只能在局部性原理指導(dǎo)下，把不再使用的頁面調(diào)出。如何選擇調(diào)度策略即頁面置換算法至關(guān)重要，置換算法的好壞，直接影響著系統(tǒng)的性能，因此我們有必要將常見的fifo和lru兩種算法進(jìn)行比較，分析性能。一、設(shè)計目的 了解頁面置換的概念；理解頁面置換的算法加深對頁面置換算法的理解。二、設(shè)計

2、內(nèi)容編程實現(xiàn)fifo和lru頁面算法。可以通過隨機(jī)數(shù)產(chǎn)生新的頁面，計算缺頁次數(shù)和缺頁率、置換次數(shù)和置換率。3、 頁面置換算法原理1) 先進(jìn)先出算法（first in first out），總選擇作業(yè)中最先進(jìn)入內(nèi)存的一頁淘汰。較早調(diào)入的頁往往是經(jīng)常被訪問的頁，這些頁在fifo算法下被反復(fù)調(diào)入和調(diào)出。只有在線性順序訪問地址空間時才是理想的，否則效率不高。在未給進(jìn)程或作業(yè)分配足夠的頁面數(shù)時，缺頁次數(shù)反而增加，從而產(chǎn)生belady現(xiàn)象，2) 最近最久不用的頁面置換算法（least recently used replacement），當(dāng)需要置換一頁面時，選擇在最近一段時間內(nèi)最久不使用的頁面予以淘汰。此

3、算法通過周期性的對“引用位”進(jìn)行檢測，并利用它來記錄一個頁面自上次訪問以來所經(jīng)歷的時間t；淘汰時，選擇t為最大的頁。選擇內(nèi)存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。但由于需要記錄頁面使用時間的先后關(guān)系，硬件開銷太大。四、 頁面置換算法設(shè)計1) fifo算法a. 算法簡述： 開始時，因為內(nèi)存中沒有放有頁面，所以先將insertpagenumber（存放要調(diào)入的頁面，數(shù)組大小為pagenumber(頁面數(shù)）中的一個頁面調(diào)入內(nèi)存并放入pagenumberm（存放調(diào)入內(nèi)存的頁面，數(shù)組大小為memblock(物理塊數(shù)）中； 如果insertpagenumber中的頁面還沒有

4、訪問完，則從insetpagenumber中調(diào)入新的頁面。否則進(jìn)入步驟。如果該頁面不在內(nèi)存中存在，則將pagenumbermmemblock中最先進(jìn)入內(nèi)存的那個頁面調(diào)出，然后將新頁面放入。進(jìn)入步驟。 返回到步驟。 結(jié)束，退出。b. 算法流程圖如下：fifo流程圖 開始 取一塊頁面頁面在內(nèi)存中是否存在y內(nèi)存塊是否填滿nnny內(nèi)存數(shù)組的下標(biāo)等于物理塊數(shù)n從第一個開始循環(huán)y 下標(biāo)置零 將頁面插入到下標(biāo)index處; 下標(biāo)增一 取下一塊頁面頁面是否全部訪問y n y 終止2) lru算法a. 原理簡述 開始時，因為內(nèi)存中沒有放有頁面，所以先將insertpagenumber（存放要調(diào)入的頁面，數(shù)組大小

5、為pagenumber(頁面數(shù)）中的一個頁面調(diào)入內(nèi)存并放入pagenumberm（存放調(diào)入內(nèi)存的頁面，數(shù)組大小為memblock(物理塊數(shù)）中； 如果insertpagenumber中的頁面還沒有訪問完，則從insetpagenumber中調(diào)入新的頁面。否則進(jìn)入步驟。如果該頁面不在內(nèi)存中存在，則通過訪問flagarray,獲得數(shù)組元素最大值對應(yīng)的數(shù)組下標(biāo)index1，然后將新頁面放入pagenumberindex1中。進(jìn)入步驟。 返回到步驟。 結(jié)束，退出。 開始 取一塊頁面 頁面在內(nèi)存中是否存在yn物理塊是否已滿ny遍歷標(biāo)志數(shù)組；獲得數(shù)組元素的最大值對應(yīng)的數(shù)組下標(biāo) 將頁面放入對應(yīng)數(shù)組下標(biāo)的內(nèi)存

6、數(shù)組中將標(biāo)志數(shù)組的其余元素值加一，對應(yīng)元素的值賦零，下標(biāo)加一 取下一塊頁面 頁面是否全部訪問n 結(jié)束y五、結(jié)果顯示七、 心得體會fifo算法當(dāng)需要置換頁面時，主要通過置換最早進(jìn)入內(nèi)存的頁面從而達(dá)到先進(jìn)先出的目的。lru算法當(dāng)需要置換頁面時，主要通過置換進(jìn)入內(nèi)存中最久沒有被訪問的頁面而達(dá)到最近最久未使用的目的。在這個程序中我只是通過一個標(biāo)志數(shù)組來存儲未被訪問的次數(shù)。在這個課程設(shè)計依據(jù)計算出的缺頁次數(shù)和缺頁率、置換次數(shù)和置換率，來論證fifo算法與lru算法的效果區(qū)別，通過測試可以看到對于調(diào)入頁面的一般情況下lru算法的置換次數(shù)明顯的比fifo算法的置換次數(shù)要少，但由于lru算法是“向前看”的，而

7、頁面過去和未來的走向之間并無必然的聯(lián)系。所以lru算法與fifo算法的缺頁次數(shù)之間并無區(qū)別。1. 通過本次課程設(shè)計,加深了對操作系統(tǒng)的頁面置換有了一定的了解,并能夠用高級語言進(jìn)行模擬演示。通過查閱相關(guān)資料基本掌握了java應(yīng)用程序編寫的基本方法。使用java編程極大的減少了代碼量，直觀的界面設(shè)計，不僅便于實現(xiàn)而且簡化了編碼，便于集中精力到主算法的編寫上。2. 兩種頁面置換算法fifo和lru理解起來相當(dāng)容易，但在實際編程實現(xiàn)的時候需要注意各種細(xì)節(jié)，需要耐心細(xì)致，實際編程中遇到一些細(xì)節(jié)上的小問題確實需要仔細(xì)考慮才行。3. 為了簡化編程的困難,采用隨即數(shù)的思想,使得程序易于實現(xiàn)。通過兩種頁面置換算法的比較，對頁面置換有更深一層的了解。使我對操作系統(tǒng)特別是頁面置換這一部分的認(rèn)識有了很大的加深。4. 使自己對java語言的基本框架有新的了解，加深了對可視化程序的認(rèn)識。在使用java語言來實