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

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

2、存中哪個(gè)頁 各種算法之間，并不中被調(diào)入內(nèi)存中的，以及各頁面在調(diào)入過面。在軟件工程的角度來看，我的系統(tǒng)具影響彼此的函數(shù)調(diào)用，而在各算法的內(nèi)部的物理塊，清晰直觀的表達(dá)程中是否命中或在置換時(shí)又有高內(nèi)聚低耦合的優(yōu)點(diǎn)，即,內(nèi)聚度很高。關(guān)鍵詞 ：設(shè)計(jì)原理, 設(shè)計(jì)方案 , 流程圖 , 源代碼，測試結(jié)果，結(jié)束語，參考文獻(xiàn)課題 運(yùn) 行環(huán) 境操作系統(tǒng)：Windows XP編程環(huán)境：Microsoft Visual C+6.0實(shí) 驗(yàn)內(nèi)容 ：通過模擬實(shí)現(xiàn)請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬存儲 TOC o 1-5 h z 技術(shù)的特點(diǎn)，掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實(shí)現(xiàn)過程，

3、并比較它們的效率。熟悉虛擬存儲管理的各種液面置換算法 ，并辨析惡魔你程序?qū)崿F(xiàn)請求頁式存儲管理的頁面置換算法。設(shè)計(jì)一個(gè)虛擬存儲區(qū)和內(nèi)存工作區(qū) , 編 程序演示下述算法的具體實(shí)現(xiàn)過程,并計(jì)算訪問命中率。設(shè)計(jì)要求：主界面以靈活選擇某算法，且以下算法都要實(shí)現(xiàn)1、先進(jìn)先出算法（FIFO）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）最簡單的頁面置換算法是先入先出（ FIFO） 法。 這種算法的實(shí)質(zhì)是，總是 TOC o 1-5 h z 選擇在主存中停留時(shí)間最長

4、（即最老）的一頁置換，即先進(jìn)入內(nèi)存的頁，先退出內(nèi)存。理由是：最早調(diào)入內(nèi)存的頁，其不再被使用的可能性比剛調(diào)入內(nèi)存的可能性大。建立一個(gè)FIFO 隊(duì)列，收容 所有在內(nèi)存中的頁。被置換頁面總是在隊(duì)列頭上進(jìn)行。當(dāng)一個(gè)頁面被放入內(nèi)存時(shí)，就把它插在隊(duì)尾上。這種算法只是在按線性順序訪問地址空間時(shí)才是理想的，否則效率不高。因?yàn)槟切┏１辉L問的頁，往往在主存中也停留得最久，結(jié)果它們因變“老”而不得不被置換出去。FIFO 的另一個(gè)缺點(diǎn) 是 ，它有一種異?，F(xiàn)象，即在增加存儲塊的情況下，反而使缺頁中斷率增加了。當(dāng)然，導(dǎo)致這種異?，F(xiàn)象的頁面走向?qū)嶋H上是很少見的 。該算法將所有使用的內(nèi)存頁面構(gòu)成一個(gè)循環(huán)列隊(duì)，每次置換時(shí)將隊(duì)列

5、中的隊(duì)首喚出，隊(duì)首指針后移一位即可，算法容易實(shí)現(xiàn)牡丹石最先進(jìn)入內(nèi)存的野末必將來就不用再到，甚至可能很快就會(huì)用到，所以不能保證有效的缺頁率，算法性能較差。3.2.2 最近最久未使用算法（LRU）FIFO算法和OPT法之間的主要差別是，F(xiàn)IFO算法利用頁面進(jìn)入內(nèi)存后的 時(shí)間長短作為置換依據(jù)，而 OPTT法的依據(jù)是將來使用頁面的時(shí)間。如果以 最近的過去作為不久將來的近似，那么就可以把過去最長一段時(shí)間里不曾被使用的頁面置換掉。它的實(shí)質(zhì)是，當(dāng)需要置換一頁時(shí)，選擇在最近一段時(shí)間里最久沒有使用過的頁面予以置換。這種算法就稱為最久未使用算法（ Least Recently Used ， LRU）。lruB法是

6、與每個(gè)頁面最后使用的時(shí)間有關(guān)的。當(dāng)必須置換一個(gè)頁面時(shí)，LRU算法選擇過去一段時(shí)間里最久未被使用的頁面。LRU算法是經(jīng)常采用的頁面置換算法，并被認(rèn)為是相當(dāng)好的，但是存在如何實(shí)現(xiàn)它的問題。LRU算法需要實(shí)際硬件的支持。其問題是怎 么確定最后使用時(shí)間 的順序，對此有兩種可行的辦法：1）計(jì)數(shù)器。最簡單的情況是使每個(gè)頁表項(xiàng)對應(yīng)一個(gè)使用時(shí)間字段，并給CPU曾加一個(gè)邏輯時(shí)鐘或計(jì)數(shù)器。每次存儲訪問，該時(shí)鐘都加1。每當(dāng)訪問一個(gè)頁面時(shí)，時(shí)鐘寄存器的內(nèi)容就被復(fù)制到相應(yīng)頁表項(xiàng)的使用時(shí)間字段中。這樣我們就可以始終保留著每個(gè)頁面最后訪問的“時(shí)間 ”。在 置換頁面時(shí)，選擇該時(shí)間值最小的頁面。這樣做，不僅要查頁表，而且當(dāng)頁表

7、改變時(shí)（因 CPUS度）要 維護(hù)這個(gè)頁表中的時(shí)間，還要考慮到時(shí)鐘值溢出的問題。2）棧。用一個(gè)棧保留頁號。每當(dāng)訪問一個(gè)頁面時(shí)，就把它從棧中取出放 TOC o 1-5 h z 在棧頂上。這樣一來，棧頂總是放有目前使用最多的頁，而棧底放著目前最少使用的頁。由于要從棧的中間移走一項(xiàng)，所以要用具有頭尾指針的雙向鏈連起來。在最壞的情況下，移走一頁并把它放在棧頂上需要改動(dòng)6個(gè)指針。每次修改都要有開銷，但需要置換哪個(gè)頁面卻可直接得到，用不著查找，因?yàn)槲仓羔樦赶驐５?，其中有被置換頁。 因?qū)崿F(xiàn)LRUB法必須有大量硬件支持，還需要一定的軟件開銷。所以實(shí)際實(shí) 現(xiàn) 的都是一種簡單有效的LRU近似算法。一種LRU近似算法

8、是最近未使用算法（Not Recently Used , NUR。佗在存儲分塊表的每一表項(xiàng)中增加一個(gè)引用位，操作系統(tǒng)定期地將它們置為0。當(dāng)某一頁被訪問時(shí)，由硬件將該位置1 。過一段時(shí)間 后，通過檢查這些位可以確定哪些頁使用過，哪些頁自上次置0后還未使用過。 就可把該位是0 的頁淘汰出去，因?yàn)樵谧罱欢螘r(shí)間里它未被訪問過。3.3.3 最佳置換算法（OPT）最優(yōu)置換（ Optimal Replacement ）是 在理論上提出的一種算法。其實(shí)質(zhì)是：使 TOC o 1-5 h z 用，或者是在最遠(yuǎn)的將來才被訪問。采用這種頁面置換算法，保證有最少的缺頁率。但是最優(yōu)頁面置換算法的實(shí)現(xiàn)是困難的，因?yàn)樗枰?/p>

9、人們預(yù)先就知道一個(gè)進(jìn)程整個(gè)運(yùn)行過程中頁面走向的全部情況。不過，這個(gè)算法可用來衡量（如通過模擬實(shí)驗(yàn)分析或理論分析）其他算法的優(yōu)劣。該算法能保證有最低的缺頁率，所以稱為最佳置換算法，但是該算法緊緊是一種理想狀況下的算法，因?yàn)樵谶M(jìn)程實(shí)際運(yùn)行過程中，將來會(huì)執(zhí)行到那兒頁是不可預(yù)知的，所以無法選擇該置換那個(gè)頁出去。因此，本算法在實(shí)際中無法使用，只能作為一種標(biāo)準(zhǔn)來衡量其他算法的性能4.1 設(shè)計(jì)方案1）主界面：設(shè)置頁面產(chǎn)生算法選擇界面和頁面置換算法選擇界面；2）子界面：頁面產(chǎn)生算法分為兩個(gè)界面，分別是隨機(jī)產(chǎn)生算法和自己輸入產(chǎn)生算法。頁面置換算法分為三個(gè)子界面，分別是先進(jìn)先出算法界面、最近最久未使用算法界面、最

10、佳置換算法界面。流程圖主流程圖圖（1）5.1.2 FIFO函數(shù)流程圖:圖（2）Start5.1.3 LRU函數(shù)流程圖:5.1.4 OPT8數(shù)流程圖:圖（5）6.源代碼6.1 程序代碼#include #include #include#define Bsize3#define Psize12#includeusing namespace std;int QStringPsize;int Num=0;struct pageInforint content;int timer;class YZ_replacepublic:YZ_replace();YZ_replace();int findSpac

11、e();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

12、頁面走向： ;for(i=0;iPsize;i+)coutQStringiII.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;

13、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

14、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+; elsespace = findSpace();if(space !=-1)for(int

15、b=0; bBsize; b+)memory_statebi=memory_statebi-1;blockspace = pagei;memory_statespacei=blockspace.content; elsefor(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+;voi

16、d YZ_replace:BlockClear() for(int i=0; iBsize; i+) blocki.content = -1; blocki.timer = 0;typedef struct pageint 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+)f

17、or(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+;elsequeue+K=fold; val=GetMax(b); bval.num=fold; bval.time=0;for(i=0;iBsize;i+) if (i!=

18、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+; elsespace = findSpace();if(space !=-1)for(int b=0; bBsize; b+)memory_statebi=memory_statebi-1; blockspace = pagei;mem

19、ory_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

20、 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ò)誤 , 請重新輸入！ str;a=decide(str);d=trans(str);return d;void Put()cout 請選擇產(chǎn)生頁面的方法a: 隨機(jī)產(chǎn)生b: 輸入產(chǎn)生 endl;coutF;while(F!=a&F!=b)coutF;if(F=a)P_String(Q

21、String) ;if(F=b)cout 請輸入各頁面號:endl;for(int i=0;iPsize;i+)QStringi=put();coutendl;cout|endl;void main()cout| 頁 面 置 換 算 法|endl;cout|endl;int t=1;while(t) Put();YZ_replace test1;YZ_replace test3;char select;OPTJdocout請選擇要應(yīng)用的算法：FIFO算法LRUM法法 退出 endl;int p,q;coutselect;while(select!=0&select!=1&select!=2&s

22、elect!=3)(cout您的輸入無效,請重新輸入：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命中率:te

23、st1.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;coutendl;for(i=0;iBsize;i+) (for(j=0;jPsize;j+) ( if(cij=-1) cout 0; else cout cij; cout endl

24、; coutendl;cout命中率：(Psize-(K+1)/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(); c

25、outendl;while(select=1|select=2|select=3); 7.測試結(jié)果7.1頁面選擇測試:C sDocment3= and SOPH 算,上 R Hj送R產(chǎn)三五間式萬T - = PETH1匕節(jié)；=上 生遺中的素甲星工面在間e 367Z75732 I 3一貝鶯置換算法“應(yīng)菜是憂 費(fèi)的法圖（7.2）分析：頁面產(chǎn)生的方法有兩種選擇，分別是隨機(jī)產(chǎn)生和自己輸入產(chǎn)生，選擇菜單的時(shí)候有對異常輸入的處理，如果輸入錯(cuò)誤，有錯(cuò)誤提示，當(dāng)輸入正確菜單的時(shí)候，選擇a,自動(dòng)產(chǎn)生頁面走向，如果選擇 b,自己可以任意輸入，如 果輸入錯(cuò)誤，有錯(cuò)誤提示。6.2應(yīng)用算法選擇測試c * C: Docme

26、 nt s and Set t mMMAdiinrL3上工七 ni: 泉畫、壽 明敝.q01 OzbnjgM.ql91 . exe-圖（7.3）分析：選擇算法時(shí)，有異常處理，即如果輸入錯(cuò)誤，有錯(cuò)誤提示。如果選 擇菜單1,即選擇了 FIFO算法，展示此算法的置換狀態(tài)并顯示命中率。置換狀 態(tài)以二維數(shù)組的形式輸出，既直觀又清晰。4八L小耳至宣法 出且在 仃MJPI罩法 6A艮山請跖施九餐單目：2 您造的是菜單O 而堂法狀號C : fiE3cuaent s and Setii iirtgXAdMxnL s t bt a r超明軾Ax,qu一 3u.UJI ) 算ilt 的號單,一 鬻定 應(yīng)菜是世 要人

27、的法 軍地胃圖(7.4)分析：算法一進(jìn)行完以后，界面自動(dòng)跳到應(yīng)用算法的選擇界面，即可以再 次選擇置換算法，選擇菜單 2,即選擇了 LRU算法，展示此算法的置換狀態(tài)并 顯示命中率，可以和第一個(gè)算法進(jìn)行對比，找出兩種算法的不同。愉中率：I；!艇瘁聚應(yīng)用的算擊 8FIP0算法1WWJ 腦管指五菜基號:一J33Z2Z?f?222077777777 1 1-P +gE+oril：./5.ori .注zJR青鼠A在11-話哂草：4 電單 八應(yīng)林重於 ; 1口的匕TLRUt圖(7.5)分析：算法二進(jìn)行完以后，界面自動(dòng)跳到應(yīng)用算法的選擇界面，即可以再次選擇置換算法，選擇菜單3,即選擇了 OPTT法，展示此算法的置換狀態(tài)并顯示命中率，可以和第二個(gè)算法進(jìn)行對比，找出兩種算法的不同flfi7?777777| 1，中率hZt?愁擇要應(yīng)用的算法EL *1陽式往 OLRU算/ CMJFI葬柱 屈出ST加7遑空5 32.昭陣，申率b12選淬要應(yīng)用的算往XCF1F0目.注G?L用I甲去