設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)-編程序演示下述算法的具體實(shí)現(xiàn)過程-并計(jì)算訪問命中率：剖析

1、齊齊哈爾大學(xué)操作系統(tǒng)課程綜合實(shí)踐題目：主界面以靈活選擇某算法班級(jí)：計(jì)本093姓名：趙明秋學(xué)號(hào)：2009021114指導(dǎo)教師：韓金庫(kù)2008年12月主界面以靈活選擇某算法實(shí)驗(yàn)摘要：計(jì)算機(jī)應(yīng)用專業(yè)的學(xué)生全面了解和掌握系統(tǒng)軟件,一般軟件設(shè)計(jì)方法和技術(shù)的必不可少的綜合課程,也是了解計(jì)算機(jī)硬件和軟件如何銜接的必經(jīng)之路。我覺得此次實(shí)驗(yàn)最大的亮點(diǎn)以及不同于別人的地方就是將三種頁(yè)面置換算法按照課本上老師講的方式直觀簡(jiǎn)便的輸出，在采用輸出算法時(shí)，我摒棄了常人所用的一維數(shù)組輸出法，而別出心裁的采用了二維數(shù)組的輸出算法，模擬了內(nèi)存的物理塊，清晰直觀的表達(dá)了頁(yè)面是如何在外存中被調(diào)入內(nèi)存中的，以及各頁(yè)面在調(diào)入過程中是否

2、命中或在置換時(shí)又置換了內(nèi)存中哪個(gè)頁(yè)面。在軟件工程的角度來看，我的系統(tǒng)具有高內(nèi)聚低耦合的優(yōu)點(diǎn)，即各種算法之間，并不影響彼此的函數(shù)調(diào)用，而在各算法的內(nèi)部，內(nèi)聚度很高。關(guān)鍵詞：設(shè)計(jì)原理,設(shè)計(jì)方案,流程圖,源代碼，測(cè)試結(jié)果，結(jié)束語，參考文獻(xiàn)課題運(yùn)行環(huán)境操作系統(tǒng)：WindowsXP編程環(huán)境：MicrosoftVisualC+6.01.1實(shí)驗(yàn)內(nèi)容：通過模擬實(shí)現(xiàn)請(qǐng)求頁(yè)式存儲(chǔ)管理的幾種基本頁(yè)面置換算法，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握虛擬存儲(chǔ)請(qǐng)求頁(yè)式存儲(chǔ)管理中幾種基本頁(yè)面置換算法的基本思想和實(shí)現(xiàn)過程，并比較它們的效率。熟悉虛擬存儲(chǔ)管理的各種液面置換算法，并辨析惡魔你程序?qū)崿F(xiàn)請(qǐng)求頁(yè)式存儲(chǔ)管理的頁(yè)面置換算法。設(shè)計(jì)一個(gè)

3、虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū),編程序演示下述算法的具體實(shí)現(xiàn)過程,并計(jì)算訪問命中率。設(shè)計(jì)要求：主界面以靈活選擇某算法，且以下算法都要實(shí)現(xiàn)1、先進(jìn)先出算法（FIFO）2、最近最久未使用算法（LRU）3、最佳置換算法（OPT）2.1運(yùn)行環(huán)境1）操作系統(tǒng)：WindowsXP2）編程環(huán)境：MicrosoftVisualC+6.03.1 設(shè)計(jì)原理：3.1.1 先進(jìn)先出算法（FIFO）最簡(jiǎn)單的頁(yè)面置換算法是先入先出（FIFO）法。這種算法的實(shí)質(zhì)是，總是選擇在主存中停留時(shí)間最長(zhǎng)（即最老）的一頁(yè)置換，即先進(jìn)入內(nèi)存的頁(yè)，先退出內(nèi)存。理由是：最早調(diào)入內(nèi)存的頁(yè)，其不再被使用的可能性比剛調(diào)入內(nèi)存的可能性大。建立一個(gè)FIFO隊(duì)

4、列，收容所有在內(nèi)存中的頁(yè)。被置換頁(yè)面總是在隊(duì)列頭上進(jìn)行。當(dāng)一個(gè)頁(yè)面被放入內(nèi)存時(shí)，就把它插在隊(duì)尾上。這種算法只是在按線性順序訪問地址空間時(shí)才是理想的，否則效率不高。因?yàn)槟切┏１辉L問的頁(yè)，往往在主存中也停留得最久，結(jié)果它們因變“老”而不得不被置換出去。FIFO的另一個(gè)缺點(diǎn)是，它有一種異?，F(xiàn)象，即在增加存儲(chǔ)塊的情況下，反而使缺頁(yè)中斷率增加了。當(dāng)然，導(dǎo)致這種異?，F(xiàn)象的頁(yè)面走向?qū)嶋H上是很少見的。該算法將所有使用的內(nèi)存頁(yè)面構(gòu)成一個(gè)循環(huán)列隊(duì)，每次置換時(shí)將隊(duì)列中的隊(duì)首喚出，隊(duì)首指針后移一位即可，算法容易實(shí)現(xiàn)牡丹石最先進(jìn)入內(nèi)存的野末必將來就不用再到，甚至可能很快就會(huì)用到，所以不能保證有效的缺頁(yè)率，算法性能八、.

5、、.r.較差。3.2.2最近最久未使用算法（LRU）FIFO算法和OPT算法之間的主要差別是，F(xiàn)IFO算法利用頁(yè)面進(jìn)入內(nèi)存后的時(shí)間長(zhǎng)短作為置換依據(jù)，而OPTT法的依據(jù)是將來使用頁(yè)面的時(shí)間。如果以最近的過去作為不久將來的近似，那么就可以把過去最長(zhǎng)一段時(shí)間里不曾被使用的頁(yè)面置換掉。它的實(shí)質(zhì)是，當(dāng)需要置換一頁(yè)時(shí)，選擇在最近一段時(shí)間里最久沒有使用過的頁(yè)面予以置換。這種算法就稱為最久未使用算法（LeastRecentlyUsed，LRU）。LRU算法是與每個(gè)頁(yè)面最后使用的時(shí)間有關(guān)的。當(dāng)必須置換一個(gè)頁(yè)面時(shí)，LRU算法選擇過去一段時(shí)間里最久未被使用的頁(yè)面。LRU算法是經(jīng)常采用的頁(yè)面置換算法，并被認(rèn)為是相當(dāng)好

6、的，但是存在如何實(shí)現(xiàn)它的問題。LRU算法需要實(shí)際硬件的支持。其問題是怎么確定最后使用時(shí)間的順序，對(duì)此有兩種可行的辦法：（1）計(jì)數(shù)器。最簡(jiǎn)單的情況是使每個(gè)頁(yè)表項(xiàng)對(duì)應(yīng)一個(gè)使用時(shí)間字段，并給CPU增加一個(gè)邏輯時(shí)鐘或計(jì)數(shù)器。每次存儲(chǔ)訪問，該時(shí)鐘都加1。每當(dāng)訪問一個(gè)頁(yè)面時(shí)，時(shí)鐘寄存器的內(nèi)容就被復(fù)制到相應(yīng)頁(yè)表項(xiàng)的使用時(shí)間字段中。這樣我們就可以始終保留著每個(gè)頁(yè)面最后訪問的“時(shí)間”。在置換頁(yè)面時(shí)，選擇該時(shí)間值最小的頁(yè)面。這樣做，不僅要查頁(yè)表，而且當(dāng)頁(yè)表改變時(shí)（因CPUS度）要維護(hù)這個(gè)頁(yè)表中的時(shí)間，還要考慮到時(shí)鐘值溢出的問題。（2）棧。用一個(gè)棧保留頁(yè)號(hào)。每當(dāng)訪問一個(gè)頁(yè)面時(shí)，就把它從棧中取出放在棧頂上。這樣一來，

7、棧頂總是放有目前使用最多的頁(yè)，而棧底放著目前最少使用的頁(yè)。由于要從棧的中間移走一項(xiàng)，所以要用具有頭尾指針的雙向鏈連起來。在最壞的情況下，移走一頁(yè)并把它放在棧頂上需要改動(dòng)6個(gè)指針。每次修改都要有開銷，但需要置換哪個(gè)頁(yè)面卻可直接得到，用不著查找，因?yàn)槲仓羔樦赶驐５祝渲杏斜恢脫Q頁(yè)。因?qū)崿F(xiàn)LRU算法必須有大量硬件支持，還需要一定的軟件開銷。所以實(shí)際實(shí)現(xiàn)的都是一種簡(jiǎn)單有效的LRU近似算法。一種LRU近似算法是最近未使用算法（NotRecentlyUsed,NUR。它在存儲(chǔ)分塊表的每一表項(xiàng)中增加一個(gè)引用位，操作系統(tǒng)定期地將它們置為0。當(dāng)某一頁(yè)被訪問時(shí)，由硬件將該位置1。過一段時(shí)間后，通過檢查這些位可以確

8、定哪些頁(yè)使用過，哪些頁(yè)自上次置0后還未使用過。就可把該位是0的頁(yè)淘汰出去，因?yàn)樵谧罱欢螘r(shí)間里它未被訪問過。3.3.3最佳置換算法（OPT）最優(yōu)置換（OptimalReplacement）是在理論上提出的一種算法。其實(shí)質(zhì)是:當(dāng)調(diào)入新的一頁(yè)而必須預(yù)先置換某個(gè)老頁(yè)時(shí)，所選擇的老頁(yè)應(yīng)是將來不再被使用，或者是在最遠(yuǎn)的將來才被訪問。采用這種頁(yè)面置換算法，保證有最少的缺頁(yè)率。但是最優(yōu)頁(yè)面置換算法的實(shí)現(xiàn)是困難的，因?yàn)樗枰藗冾A(yù)先就知道一個(gè)進(jìn)程整個(gè)運(yùn)行過程中頁(yè)面走向的全部情況。不過，這個(gè)算法可用來衡量（如通過模擬實(shí)驗(yàn)分析或理論分析）其他算法的優(yōu)劣。該算法能保證有最低的缺頁(yè)率，所以稱為最佳置換算法，但是該算法

9、緊緊是一種理想狀況下的算法，因?yàn)樵谶M(jìn)程實(shí)際運(yùn)行過程中，將來會(huì)執(zhí)行到那兒頁(yè)是不可預(yù)知的，所以無法選擇該置換那個(gè)頁(yè)出去。因此，本算法在實(shí)際中無法使用，只能作為一種標(biāo)準(zhǔn)來衡量其他算法的性能4.1設(shè)計(jì)方案1）主界面：設(shè)置頁(yè)面產(chǎn)生算法選擇界面和頁(yè)面置換算法選擇界面；2）子界面：頁(yè)面產(chǎn)生算法分為兩個(gè)界面，分別是隨機(jī)產(chǎn)生算法和自己輸入產(chǎn)生算法。頁(yè)面置換算法分為三個(gè)子界面，分別是先進(jìn)先出算法界面、最近最久未使用算法界面、最佳置換算法界面。5.1 流程圖5.1.1 主流程圖圖（1）5.1.2FIFO函數(shù)流程圖:StartfindExist(i)findSpace()findReplace()圖（2）5.1.3L

10、RU函數(shù)流程圖:5.1.4OPT6.源代碼圖（4）函數(shù)流程圖：圖（5）Getmax()6.1程序代碼#include#include#include#defineBsize3#definePsize12#includeusingnamespacestd;intQStringPsize;intNum=0;structpageInforintcontent;inttimer;classYZ_replacepublic:YZ_replace();YZ_replace();intfindSpace();intfindExist(intcurpage);intfindReplace();voidFIFO

11、();voidOPT();voidBlockClear();voidinitia1(intstring);pageInfor*block;pageInfor*page;intmemory_stateBsizePsize;ints;private:;voidP_String(intQString)inti;srand(unsigned)time(NULL);for(i=0;iPsize;i+)QStringi=rand()*9/RAND_MAX+1;cout頁(yè)面走向：;for(i=0;iPsize;i+)coutQStringicoutendl;YZ_replace:YZ_replace()s=

12、0;block=newpageInforBsize;for(inti=0;iBsize;i+)blocki.content=-1;blocki.timer=0;voidYZ_replace:initia1(intQString)intj;page=newpageInforPsize;for(inti=0;iPsize;i+)pagei.content=QStringi;pagei.timer=0;for(i=0;iPsize;i+)for(j=0;jBsize;j+)memory_stateji=0;YZ_replace:YZ_replace()s=0;intYZ_replace:findSp

13、ace()for(inti=0;iBsize;i+)if(blocki.content=-1)returni;return-1;intYZ_replace:findExist(intcurpage)for(inti=0;iBsize;i+)if(blocki.content=pagecurpage.content)returni;return-1;intYZ_replace:findReplace()intpos=0;for(inti=0;i=blockpos.timer)pos=i;returnpos;voidYZ_replace:FIFO()intexist,space,position;

14、for(inti=0;iPsize;i+)exist=findExist(i);if(exist!=-1)for(intb=0;bBsize;b+)memory_statebi=memory_statebi-1;s+;elsespace=findSpace();if(space!=-1)for(intb=0;bBsize;b+)memory_statebi=memory_statebi-1;blockspace=pagei;memory_statespacei=blockspace.content;elsefor(intb=0;bBsize;b+)memory_statebi=memory_s

15、tatebi-1;position=findReplace();blockposition=pagei;memory_statepositioni=blockposition.content;for(intj=0;jBsize;j+)blockj.timer+;voidYZ_replace:BlockClear()for(inti=0;iBsize;i+)blocki.content=-1;blocki.timer=0;typedefstructpageintnum;inttime;Page;PagebBsize;PagecallBsize;intcBsizePsize;intqueue100

16、;intK;voidInitL(Page*b,intcBsizePsize)inti,j;for(i=0;iBsize;i+)bi.num=-1;bi.time=Psize-i-1;for(i=0;iBsize;i+)for(j=0;jPsize;j+)cij=-1;intGetMax(Page*b)inti;intmax=-1;inttag=0;for(i=0;imax)max=bi.time;tag=i;returntag;intEquation(intfold,Page*b)inti;for(i=0;i=0)bval.time=0;for(i=0;iBsize;i+)if(i!=val)

17、bi.time+;elsequeue+K=fold;val=GetMax(b);bval.num=fold;bval.time=0;for(i=0;iBsize;i+)if(i!=val)bi.time+;voidYZ_replace:OPT()intexist,space,position;for(inti=0;iPsize;i+)exist=findExist(i);if(exist!=-1)for(intb=0;bBsize;b+)memory_statebi=memory_statebi-1;s+;elsespace=findSpace();if(space!=-1)for(intb=

18、0;bBsize;b+)memory_statebi=memory_statebi-1;blockspace=pagei;memory_statespacei=blockspace.content;elsefor(intk=0;kBsize;k+)memory_stateki=memory_stateki-1;for(intj=i;jPsize;j+)!=if(blockk.contentpagej.content)blockk.timer=1000;elseblockk.timer=j;break;position=findReplace();blockposition=pagei;memo

19、ry_statepositioni=blockposition.content;intdecide(stringstr)for(inti=0;istr.size();i+)if(stri9)return0;break;returni;inttrans(stringstr)intsum=0;for(inti=0;istr;a=decide(str);while(a=0)cout輸入錯(cuò)誤,請(qǐng)重新輸入！str;a=decide(str);d=trans(str);returnd;voidPut()cout請(qǐng)選擇產(chǎn)生頁(yè)面的方法a:隨機(jī)產(chǎn)生b:輸入產(chǎn)生endl;coutF;while(F!=a&F!=b

20、)coutF;if(F=a)P_String(QString);if(F=b)cout請(qǐng)輸入各頁(yè)面號(hào):endl;for(inti=0;iPsize;i+)QStringi=put();coutendl;cout|-|endl;voidmain()cout|頁(yè)面置換算法|endl;cout|-|endl;intt=1;while(t)Put();YZ_replacetest1;YZ_replacetest3;charselect;docout”請(qǐng)選擇要應(yīng)用的算法：FIFO算法LRU算法OPT算法退出endl;intp,q;coutselect;while(select!=0&select!=1&

21、select!=2&select!=3)(cout您的輸入無效，請(qǐng)重新輸入:select;if(select=0)(cout”您選擇的是菜單endl;cout完成退出.endl;t=0;if(select=1)(cout”您選擇的是菜單endl;coutFIFO算法狀態(tài):endl;test1.initia1(QString);test1.FIFO();test1.BlockClear();coutendl;for(p=0;pBsize;p+)(for(q=0;qPsize;q+)couttest1.memory_statepq;coutendl;coutendl;cout命中率:test1.s

22、/Psizeendl;test1.YZ_replace();coutendl;if(select=2)(inti,j;K=-1;InitL(b,c);for(i=0;iPsize;i+)(Lru(QStringi,b);c0i=QStringi;for(j=0;jBsize;j+)cji=bj.num;)cout”您選擇的是菜單endl;coutLRU算法狀態(tài):endl;coutendl;for(i=0;iBsize;i+)for(j=0;jPsize;j+)if(cij=-1)cout0;elsecoutcij;)coutendl;)coutendl;cout命中率:(Psize-(K+1)

23、/Psize;coutt;coutendl;)if(select=3)cout”您選擇的是菜單endl;coutOPT算法狀態(tài):endl;test3.initia1(QString);test3.OPT();test3.BlockClear();coutendl;for(p=0;pBsize;p+)for(q=0;qPsize;q+)couttest3.memory_statepq;coutendl;)coutendl;cout命中率：test3.s/Psizeendl;test3.YZ_replace();cout 票:11的口蚤; 用單！來LRU算法 0PT算法 退出圖（7.3）分析：選擇

24、算法時(shí)，有異常處理，即如果輸入錯(cuò)誤，有錯(cuò)誤提示。如果選擇菜單1,即選擇了FIFO算法，展示此算法的置換狀態(tài)并顯示命中率。置換狀態(tài)以二維數(shù)組的形式輸出，既直觀又清晰。sC:DocuentsandSettingsAdinistrat1DebugzMqO1.exe要人的法 SIS 選您選Fo算:1a 的口章:H應(yīng)菜是狀LEU算法 OPT算法 退出由中率：2/12鬲選擇要應(yīng)用的算法:QFIFO算法2LRU算法30PT算法0退出腳輸菜萋營(yíng)：2幅選擇的是菜單2詢篇供態(tài)：圖（7.4）分析：算法一進(jìn)行完以后，界面自動(dòng)跳到應(yīng)用算法的選擇界面，即可以再次選擇置換算法，選擇菜單2,即選擇了LRU算法，展示此算法的置

25、換狀態(tài)并顯示命中率，可以和第一個(gè)算法進(jìn)行對(duì)比，找出兩種算法的不同。（C:XOocuaentsandSettingsAAdBimistrat口:桌面，趙明秋Tz-qOlDelmgTnqtJLexe請(qǐng)選茬要應(yīng)用的算法：1 FI F。算法 請(qǐng)您端入菜單號(hào)：2您送超的是菜靖2RU算注狀態(tài):LRU算法 0PT蕓法 退出2用單粟 Z1應(yīng)菜至、:3要人的.“節(jié) A 算:22 的口電23LRU算法DOPT算法 的退出33322299922206655533330Q7777777711命中率：3/12ife舞法乂法3算法IlMl0PT算法圖(7.5)分析：算法二進(jìn)行完以后，界面自動(dòng)跳到應(yīng)用算法的選擇界面，即可以再次選擇置換