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

齊齊哈爾大學(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)之路。我覺(jué)得此次實(shí)驗(yàn)最大的亮點(diǎn)以及不同于別人的地方就是將三種頁(yè)面置換算法按照課本上老師講的方式直觀簡(jiǎn)便的輸出 ，在采用輸出算法時(shí)，我摒棄了常人所用的一維數(shù)組輸出法，而別出心裁的采用了二維數(shù)組的輸出算法，模擬了內(nèi)存的物理塊，清晰直觀的表達(dá)了頁(yè)面是如何在外存中被調(diào)入內(nèi)存中的，以及各頁(yè)面在調(diào)入過(guò)程中是否命中或在置換時(shí)又置換了內(nèi)存中哪個(gè)頁(yè)面。在軟件工程的角度來(lái)看，我的系統(tǒng)具有高內(nèi)聚低耦合的優(yōu)點(diǎn)，即各種算法之間，并不影響彼此的函數(shù)調(diào)用，而在各算法的內(nèi)部，內(nèi)聚度很高。關(guān)鍵詞：設(shè)計(jì)原理, 設(shè)計(jì)方案, 流程圖,源代碼，測(cè)試結(jié)果，結(jié)束語(yǔ)，參考文獻(xiàn)課題運(yùn)行環(huán)境操作系統(tǒng)：Windows XP編程環(huán)境：Microsoft Visual C+6.01.1 實(shí)驗(yàn)內(nèi)容： 通過(guò)模擬實(shí)現(xiàn)請(qǐng)求頁(yè)式存儲(chǔ)管理的幾種基本頁(yè)面置換算法，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握虛擬存儲(chǔ)請(qǐng)求頁(yè)式存儲(chǔ)管理中幾種基本頁(yè)面置換算法的基本思想和實(shí)現(xiàn)過(guò)程，并比較它們的效率。熟悉虛擬存儲(chǔ)管理的各種液面置換算法，并辨析惡魔你程序?qū)崿F(xiàn)請(qǐng)求頁(yè)式存儲(chǔ)管理的頁(yè)面置換算法。設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū),編程序演示下述算法的具體實(shí)現(xiàn)過(guò)程,并計(jì)算訪問(wèn)命中率。設(shè)計(jì)要求：主界面以靈活選擇某算法，且以下算法都要實(shí)現(xiàn)1、先進(jìn)先出算法（FIFO）2、最近最久未使用算法（LRU）3、最佳置換算法（OPT）2.1 運(yùn)行環(huán)境1）操作系統(tǒng)：Windows XP2）編程環(huán)境：Microsoft Visual C+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ì)列，收容所有在內(nèi)存中的頁(yè)。被置換頁(yè)面總是在隊(duì)列頭上進(jìn)行。當(dāng)一個(gè)頁(yè)面被放入內(nèi)存時(shí)，就把它插在隊(duì)尾上。這種算法只是在按線性順序訪問(wèn)地址空間時(shí)才是理想的，否則效率不高。因?yàn)槟切┏１辉L問(wèn)的頁(yè)，往往在主存中也停留得最久，結(jié)果它們因變“老”而不得不被置換出去。FIFO的另一個(gè)缺點(diǎn)是，它有一種異?，F(xiàn)象，即在增加存儲(chǔ)塊的情況下，反而使缺頁(yè)中斷率增加了。當(dāng)然，導(dǎo)致這種異?，F(xiàn)象的頁(yè)面走向?qū)嶋H上是很少見(jiàn)的。該算法將所有使用的內(nèi)存頁(yè)面構(gòu)成一個(gè)循環(huán)列隊(duì)，每次置換時(shí)將隊(duì)列中的隊(duì)首喚出，隊(duì)首指針后移一位即可，算法容易實(shí)現(xiàn)牡丹石最先進(jìn)入內(nèi)存的野末必將來(lái)就不用再到，甚至可能很快就會(huì)用到，所以不能保證有效的缺頁(yè)率，算法性能較差。3.2.2 最近最久未使用算法（LRU）FIFO算法和OPT算法之間的主要差別是，F(xiàn)IFO算法利用頁(yè)面進(jìn)入內(nèi)存后的時(shí)間長(zhǎng)短作為置換依據(jù)，而OPT算法的依據(jù)是將來(lái)使用頁(yè)面的時(shí)間。如果以最近的過(guò)去作為不久將來(lái)的近似，那么就可以把過(guò)去最長(zhǎng)一段時(shí)間里不曾被使用的頁(yè)面置換掉。它的實(shí)質(zhì)是，當(dāng)需要置換一頁(yè)時(shí)，選擇在最近一段時(shí)間里最久沒(méi)有使用過(guò)的頁(yè)面予以置換。這種算法就稱為最久未使用算法（Least Recently Used，LRU）。 LRU算法是與每個(gè)頁(yè)面最后使用的時(shí)間有關(guān)的。當(dāng)必須置換一個(gè)頁(yè)面時(shí)，LRU算法選擇過(guò)去一段時(shí)間里最久未被使用的頁(yè)面。LRU算法是經(jīng)常采用的頁(yè)面置換算法，并被認(rèn)為是相當(dāng)好的，但是存在如何實(shí)現(xiàn)它的問(wèn)題。LRU算法需要實(shí)際硬件的支持。其問(wèn)題是怎么確定最后使用時(shí)間的順序，對(duì)此有兩種可行的辦法： （1）計(jì)數(shù)器。最簡(jiǎn)單的情況是使每個(gè)頁(yè)表項(xiàng)對(duì)應(yīng)一個(gè)使用時(shí)間字段，并給CPU增加一個(gè)邏輯時(shí)鐘或計(jì)數(shù)器。每次存儲(chǔ)訪問(wèn)，該時(shí)鐘都加1。每當(dāng)訪問(wèn)一個(gè)頁(yè)面時(shí)，時(shí)鐘寄存器的內(nèi)容就被復(fù)制到相應(yīng)頁(yè)表項(xiàng)的使用時(shí)間字段中。這樣我們就可以始終保留著每個(gè)頁(yè)面最后訪問(wèn)的“時(shí)間”。在置換頁(yè)面時(shí)，選擇該時(shí)間值最小的頁(yè)面。這樣做，不僅要查頁(yè)表，而且當(dāng)頁(yè)表改變時(shí)（因CPU調(diào)度）要維護(hù)這個(gè)頁(yè)表中的時(shí)間，還要考慮到時(shí)鐘值溢出的問(wèn)題。 （2）棧。用一個(gè)棧保留頁(yè)號(hào)。每當(dāng)訪問(wèn)一個(gè)頁(yè)面時(shí)，就把它從棧中取出放在棧頂上。這樣一來(lái)，棧頂總是放有目前使用最多的頁(yè)，而棧底放著目前最少使用的頁(yè)。由于要從棧的中間移走一項(xiàng)，所以要用具有頭尾指針的雙向鏈連起來(lái)。在最壞的情況下，移走一頁(yè)并把它放在棧頂上需要改動(dòng)6個(gè)指針。每次修改都要有開(kāi)銷，但需要置換哪個(gè)頁(yè)面卻可直接得到，用不著查找，因?yàn)槲仓羔樦赶驐５?，其中有被置換頁(yè)。因?qū)崿F(xiàn)LRU算法必須有大量硬件支持，還需要一定的軟件開(kāi)銷。所以實(shí)際實(shí)現(xiàn)的都是一種簡(jiǎn)單有效的LRU近似算法。一種LRU近似算法是最近未使用算法（Not Recently Used，NUR）。它在存儲(chǔ)分塊表的每一表項(xiàng)中增加一個(gè)引用位，操作系統(tǒng)定期地將它們置為0。當(dāng)某一頁(yè)被訪問(wèn)時(shí)，由硬件將該位置1。過(guò)一段時(shí)間后，通過(guò)檢查這些位可以確定哪些頁(yè)使用過(guò)，哪些頁(yè)自上次置0后還未使用過(guò)。就可把該位是0的頁(yè)淘汰出去，因?yàn)樵谧罱欢螘r(shí)間里它未被訪問(wèn)過(guò)。3.3.3 最佳置換算法（OPT）最優(yōu)置換（Optimal Replacement）是在理論上提出的一種算法。其實(shí)質(zhì)是：當(dāng)調(diào)入新的一頁(yè)而必須預(yù)先置換某個(gè)老頁(yè)時(shí)，所選擇的老頁(yè)應(yīng)是將來(lái)不再被使用，或者是在最遠(yuǎn)的將來(lái)才被訪問(wèn)。采用這種頁(yè)面置換算法，保證有最少的缺頁(yè)率。但是最優(yōu)頁(yè)面置換算法的實(shí)現(xiàn)是困難的，因?yàn)樗枰藗冾A(yù)先就知道一個(gè)進(jìn)程整個(gè)運(yùn)行過(guò)程中頁(yè)面走向的全部情況。不過(guò)，這個(gè)算法可用來(lái)衡量（如通過(guò)模擬實(shí)驗(yàn)分析或理論分析）其他算法的優(yōu)劣。該算法能保證有最低的缺頁(yè)率，所以稱為最佳置換算法，但是該算法緊緊是一種理想狀況下的算法，因?yàn)樵谶M(jìn)程實(shí)際運(yùn)行過(guò)程中，將來(lái)會(huì)執(zhí)行到那兒頁(yè)是不可預(yù)知的，所以無(wú)法選擇該置換那個(gè)頁(yè)出去。因此，本算法在實(shí)際中無(wú)法使用，只能作為一種標(biāo)準(zhǔn)來(lái)衡量其他算法的性能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.2 FIFO函數(shù)流程圖： 圖（2）5.1.3 LRU函數(shù)流程圖： 圖（4）5.1.4 OPT函數(shù)流程圖： 圖（5）6.源代碼6.1 程序代碼#include #include #include#define Bsize 3#define Psize 12#includeusing namespace std;int QStringPsize;int Num=0;struct pageInfor int content; int timer;class YZ_replacepublic: YZ_replace(); YZ_replace(); int findSpace(); int findExist(int curpage); int findReplace(); void FIFO(); void OPT(); void BlockClear(); void initia1(int string); pageInfor *block; pageInfor *page; int memory_stateBsizePsize; int s;private:;void P_String(int QString) int i; srand(unsigned)time(NULL); for(i=0;iPsize;i+) QStringi=rand()*9/RAND_MAX+1; cout頁(yè)面走向：; for(i=0;iPsize;i+) coutQStringi ; coutendl;YZ_replace:YZ_replace()s=0; block = new pageInforBsize; for(int i=0; iBsize; i+) blocki.content = -1; blocki.timer = 0;void YZ_replace:initia1(int QString ) int j; page = new pageInforPsize; for(int i=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;int YZ_replace:findSpace() for(int i=0; iBsize; i+) if(blocki.content = -1) return i; return -1;int YZ_replace:findExist(int curpage) for(int i=0; iBsize; i+) if(blocki.content = pagecurpage.content) return i; return -1;int YZ_replace:findReplace() int pos = 0; for(int i=0; i= blockpos.timer) pos = i; return pos;void YZ_replace:FIFO() int exist,space,position ; for(int i=0; iPsize; i+) exist = findExist(i); if(exist != -1) for(int b=0; bBsize; b+) memory_statebi=memory_statebi-1; s+; else space = findSpace(); if(space != -1) for(int b=0; bBsize; b+) memory_statebi=memory_statebi-1; blockspace = pagei; memory_statespacei=blockspace.content; else for(int b=0; bBsize; b+) memory_statebi=memory_statebi-1; position = findReplace(); blockposition = pagei; memory_statepositioni=blockposition.content; for(int j=0; jBsize; j+) blockj.timer+; void YZ_replace:BlockClear() for(int i=0; iBsize; i+) blocki.content = -1; blocki.timer = 0; typedef struct page int num; int time; Page; Page bBsize;Page callBsize; int cBsizePsize; int queue100; int K; void InitL(Page *b,int cBsizePsize) int i,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;int GetMax(Page *b) int i; int max=-1; int tag=0; for(i=0;imax) max=bi.time; tag=i; return tag;int Equation(int fold,Page *b) int i; for(i=0;i=0) bval.time=0; for(i=0;iBsize;i+) if (i!=val) bi.time+; else queue+K=fold; val=GetMax(b); bval.num=fold; bval.time=0; for(i=0;iBsize;i+) if (i!=val) bi.time+; void YZ_replace:OPT()int exist,space,position ;for(int i=0; iPsize; i+)exist = findExist(i);if(exist != -1)for(int b=0; bBsize; b+)memory_statebi=memory_statebi-1;s+;else space = findSpace();if(space != -1)for(int b=0; bBsize; b+)memory_statebi=memory_statebi-1;blockspace = pagei;memory_statespacei=blockspace.content;elsefor(int k=0; kBsize; k+)memory_stateki=memory_stateki-1; for(int j=i; jPsize; j+) if(blockk.content != pagej.content) blockk.timer = 1000; else blockk.timer = j; break; position = findReplace(); blockposition = pagei; memory_statepositioni=blockposition.content;int decide(string str) for(int i=0;istr.size();i+) if(stri9)return 0;break;return i;int trans(string str) int sum=0;for(int i=0;istr;a=decide(str);while(a=0)cout輸入錯(cuò)誤,請(qǐng)重新輸入！str; a=decide(str); d=trans(str);return d;void Put() cout請(qǐng)選擇產(chǎn)生頁(yè)面的方法 a:隨機(jī)產(chǎn)生 b:輸入產(chǎn)生endl; coutF; while(F!=a&F!=b)coutF; if(F=a)P_String(QString) ; if(F=b) cout請(qǐng)輸入各頁(yè)面號(hào):endl;for(int i=0;iPsize;i+)QStringi=put(); coutendl; cout|-|endl;void main() cout|-頁(yè) 面 置 換 算 法-|endl; cout|-|endl; int t=1; while(t) Put(); YZ_replace test1; YZ_replace test3; char select; do cout請(qǐng)選擇要應(yīng)用的算法:FIFO算法 LRU算法 OPT算法 退出endl; int p,q; coutselect; while(select!=0&select!=1&select!=2&select!=3) cout您的輸入無(wú)效,請(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(); cout-endl; for(p=0;pBsize;p+) for(q=0;qPsize;q+) couttest1.memory_statepq ; coutendl; cout-endl; cout命中率:test1.s/Psizeendl; test1.YZ_replace(); coutendl; if(select=2) int i,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; cout-endl; for(i=0;iBsize;i+) for(j=0;jPsize;j+) if(cij=-1) cout 0; else cout cij; cout endl; cout-endl; cout命中率:(Psize-(K+1)/Psize; coutt; coutendl; if(select=3) cout您選擇的是菜單endl; coutOPT算法狀態(tài):endl; test3.initia1(QString); test3.OPT(); test3.BlockClear(); cout-endl; for(p=0;pBsize;p+) for(q=0;qPsize;q+) couttest3.memory_statepq ; coutendl; cout-endl; cout命中率:test3.s/Psizeendl; test3.YZ_replace(); coutendl; while(select=1|select=2|select=3); 7.測(cè)試結(jié)果7.1 頁(yè)面選擇測(cè)試： 圖（7.1） 圖（7.2）分析：頁(yè)面產(chǎn)生的方法有兩種選擇，分別是隨機(jī)產(chǎn)生和自己輸入產(chǎn)生，選擇菜單的時(shí)候有對(duì)異常輸入的處理，如果輸入錯(cuò)誤，有錯(cuò)誤提示，當(dāng)輸入正確菜單的時(shí)候，選擇a，自動(dòng)產(chǎn)生頁(yè)面走向，如果選擇b，自己可以任意輸入，如果輸入錯(cuò)誤，有錯(cuò)誤提示。6.2 應(yīng)用算法選擇測(cè)試 圖（7.3）分析：選擇算法時(shí)，有異常處理，即如果輸入錯(cuò)誤，有錯(cuò)誤提示。如果選擇菜單1，即選擇了FIFO算法，展示此算法的置換狀態(tài)并顯示命中率。置換狀態(tài)以二維數(shù)組的形式輸出，既直觀又清晰。 圖（7.4）分析：算法一進(jìn)行完以后，界面自動(dòng)跳到應(yīng)用算法的選擇界面，即可以再次選擇置換算法，選擇菜單2，即選擇了LRU算法，展示此算法的置換狀態(tài)并顯示命中率，可以和第一個(gè)算法進(jìn)行對(duì)比，找出兩種算法的不同。 圖（7.5）分析：算法二進(jìn)行完以后，界面自動(dòng)跳到應(yīng)用算法的選擇界面，