Java語(yǔ)言實(shí)現(xiàn)模擬頁(yè)面置換算法

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

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

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

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

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

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

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