27-請求頁式管理缺頁中斷模擬設(shè)計(jì)--FIFO、OPT.doc

武漢理工大學(xué)計(jì)算機(jī)操作系統(tǒng)教程課程設(shè)計(jì)報(bào)告書課程設(shè)計(jì)任務(wù)書學(xué)生姓名： 周歡 專業(yè)班級： 計(jì)算機(jī)0903班 指導(dǎo)教師： 杜薇 工作單位： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題 目: 請求頁式管理缺頁中斷模擬設(shè)計(jì)-FIFO、OPT初始條件：1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的內(nèi)存管理章節(jié)內(nèi)容，了解有關(guān)虛擬存儲器、頁式存儲管理等概念，并體會和了解缺頁和頁面置換的具體實(shí)施方法。2實(shí)踐準(zhǔn)備：掌握一種計(jì)算機(jī)高級語言的使用。要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1實(shí)現(xiàn)指定淘汰算法。能夠處理以下的情形： 能夠輸入給作業(yè)分配的內(nèi)存塊數(shù)； 能夠輸入給定的頁面，并計(jì)算發(fā)生缺頁的次數(shù)以及缺頁率； 缺頁時(shí)，如果發(fā)生頁面置換，輸出淘汰的頁號。2設(shè)計(jì)報(bào)告內(nèi)容應(yīng)說明： 課程設(shè)計(jì)目的與功能； 需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明(功能與框圖)； 源程序的主要部分； 測試用例，運(yùn)行結(jié)果與運(yùn)行情況分析； 自我評價(jià)與總結(jié)：i）你認(rèn)為你完成的設(shè)計(jì)哪些地方做得比較好或比較出色；ii）什么地方做得不太好，以后如何改正；iii）從本設(shè)計(jì)得到的收獲（在編寫，調(diào)試，執(zhí)行過程中的經(jīng)驗(yàn)和教訓(xùn)）；iv）完成本題是否有其他的其他方法（如果有，簡要說明該方法）；v）對實(shí)驗(yàn)題的評價(jià)和改進(jìn)意見，請你推薦設(shè)計(jì)題目。時(shí)間安排：設(shè)計(jì)安排一周：周1、周2：完成程序分析及設(shè)計(jì)。周2、周3：完成程序調(diào)試及測試。周4、周5：驗(yàn)收，撰寫課程設(shè)計(jì)報(bào)告。（注意事項(xiàng)：嚴(yán)禁抄襲，一旦發(fā)現(xiàn)，抄與被抄的一律按0分記）指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日請求頁式管理缺頁中斷模擬設(shè)計(jì)FIFO、OPT1課程設(shè)計(jì)目的與功能 1.1設(shè)計(jì)目的 結(jié)合操作系統(tǒng)所學(xué)內(nèi)存頁式管理章節(jié)，掌握虛擬內(nèi)存設(shè)計(jì)的重要性，熟悉和掌握請求分頁式存儲管理的實(shí)現(xiàn)原理，通過分析、設(shè)計(jì)和實(shí)現(xiàn)頁式虛擬存儲管理缺頁中斷的模擬系統(tǒng)，重點(diǎn)掌握當(dāng)請求頁面不在內(nèi)存而內(nèi)存塊已經(jīng)全部被占用時(shí)的替換算法（主要通過FIFO和OPT實(shí)現(xiàn)），并考察替換算法的評價(jià)指標(biāo)缺頁次數(shù)和缺頁率，得到淘汰的頁面次序。高級語言設(shè)計(jì)并實(shí)現(xiàn)出的結(jié)果程序要能夠很好地顯示頁面調(diào)入和替換詳細(xì)信息。1.2初始條件及可發(fā)環(huán)境 1.2.1初始條件 1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的內(nèi)存管理章節(jié)內(nèi)容，了解有關(guān)虛擬存儲器、頁式存儲管理等概念，并體會和了解缺頁和頁面置換的具體實(shí)施方法。2實(shí)踐準(zhǔn)備：掌握一種計(jì)算機(jī)高級語言的使用。 1.2.2開發(fā)環(huán)境 （1）使用系統(tǒng)：Windows XP（2）使用語言：C+（3）開發(fā)工具：Visual C+ 6.01.3功能實(shí)現(xiàn) 設(shè)計(jì)的結(jié)果程序能實(shí)現(xiàn)FIFO、OPT算法模擬頁式存儲管理缺頁中斷，主要能夠處理以下的情形：(1) 用戶能夠輸入給定分配的內(nèi)存塊數(shù)；(2) 用戶輸入給定的頁面，并計(jì)算發(fā)生缺頁的次數(shù)、缺頁率及淘汰頁面次序；(3) 程序可隨機(jī)生成頁面序列，或用戶輸入；2需求分析及設(shè)計(jì)說明 2.1需求分析 由于純頁式存儲管理提高了內(nèi)存的利用效率，但并不為用戶提供虛存，并且會產(chǎn)生磁盤碎片問題。用戶程序?qū)⑹艿轿锢韮?nèi)存大小的限制。而虛存的存儲管理技術(shù)請求分頁存儲管理技術(shù)和請求分段技術(shù)，則很好的解決了這個(gè)問題。該設(shè)計(jì)虛擬實(shí)現(xiàn)請求分頁管理（只實(shí)現(xiàn)FIFO和OPT）。請求分頁系統(tǒng)是在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能和頁面置換功能所形成的頁式虛擬存儲系統(tǒng)。它允許只裝入部分頁面的程序和數(shù)據(jù)，便啟動運(yùn)行。以后，再通過調(diào)頁功能和頁面置換功能，陸續(xù)把即將要運(yùn)行的頁面調(diào)入內(nèi)存，同時(shí)把暫時(shí)不運(yùn)行的頁面換出到外存上，置換時(shí)以頁面為單位。實(shí)現(xiàn)將程序正在運(yùn)行時(shí)所需的但尚未在內(nèi)存的頁面調(diào)入內(nèi)存，再將內(nèi)存中暫時(shí)不用的頁面從內(nèi)存置換到外存磁盤上。為了實(shí)現(xiàn)請求分頁技術(shù)，頁表應(yīng)增加相應(yīng)的內(nèi)容，反映該頁是否在內(nèi)存，在外存的位置，和在內(nèi)存的時(shí)間的長短。請求分頁中的頁表如表1：表1虛擬頁號物理塊號狀態(tài)位輔存地址訪問字段修改位各字段說明如下：狀態(tài)位：指示該頁是否已調(diào)入內(nèi)存。訪問字段：記錄本頁在被訪問的次數(shù)，或記錄最近已有多長時(shí)間未被訪問。修改位：表示該頁面在調(diào)入內(nèi)存后是否被修改過。若未被修改，在替換該頁時(shí)就不需要再將該頁寫回到外存上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。外存地址：指出該頁在外存上的地址，通常是物理塊號。在本設(shè)計(jì)中模擬FIFO、OPT系統(tǒng)的實(shí)現(xiàn)中，只需要用到虛擬頁號，物理塊號和中斷位。頁表可用一個(gè)結(jié)構(gòu)體的數(shù)組實(shí)現(xiàn)。請求分頁的具體實(shí)現(xiàn)過程如圖1圖1請求分頁流程圖 2.2設(shè)計(jì)說明 2.2.1算法分析在進(jìn)程運(yùn)行過程中，若其所要訪問的頁面不在內(nèi)存，需要把它們調(diào)入內(nèi)存，但已無空閑已空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對換區(qū)。但應(yīng)將哪個(gè)頁面調(diào)出，必須根據(jù)替換算法來確定。該設(shè)計(jì)采用的是常見置換算法中的先進(jìn)先出(FIFO)、理想型淘汰算法OPT(Optimal Replacement Algorithm）。詳細(xì)算法原理如下：FIFO(先進(jìn)先出算法)基本思想：總是選擇在內(nèi)存駐留時(shí)間最長的一頁將其淘汰，因?yàn)樽钤缯{(diào)入內(nèi)存的頁，不再被使用的可能性比近期調(diào)入內(nèi)存的大。該算法實(shí)現(xiàn)簡單，只需要把一個(gè)進(jìn)程調(diào)入內(nèi)存的頁面，按先后次序連結(jié)成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁面。但是該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁面經(jīng)常被訪問，比如有全局變量、常用函數(shù)，例程等的頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。使用FIFO替換算法效率比較低，可能會比理想型算法要多出一倍。低的原因是：基于處理器按線性順序訪問地址空間這一假設(shè)。事實(shí)上，許多時(shí)候，處理器不是按線性順序訪問地址空間的。例如，執(zhí)行循環(huán)結(jié)構(gòu)的程序段。使用FIFO算法時(shí)，在未給進(jìn)程或作業(yè)分配足夠它所需要的頁面數(shù)時(shí)，有時(shí)會出現(xiàn)分配的頁面數(shù)增，缺頁次數(shù)反而增加的現(xiàn)象（Belady現(xiàn)象）。 例如針對請求序列：1 2 3 4 1 2 5 1 2 3 4 5，若分配3個(gè)可用內(nèi)存塊，使用FIFO算法，一共會缺頁9次，缺頁率：75%；而如果分配4個(gè)可用內(nèi)存塊，則一共會缺頁10次，缺頁率：83.3%。OPT(理想型淘汰算法)基本思想：當(dāng)要調(diào)入一新頁而必須淘汰一舊頁時(shí)，所淘汰的頁是以后不再使用的，或者是以后相當(dāng)長的時(shí)間內(nèi)不會使用的。采用理想型替換算法，通?？杀ＷC獲得最低的缺頁率。但是由于人們目前無法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁面中，哪個(gè)頁面是未來最長時(shí)間內(nèi)不再被訪問的，因而該算法是無法實(shí)現(xiàn)的，但是在模擬設(shè)計(jì)中，由于是事先給定一個(gè)頁面序列，即知道各個(gè)時(shí)刻以前和以后的頁面出現(xiàn)情況，所以可實(shí)現(xiàn)該算法。在實(shí)際系統(tǒng)中，雖無法實(shí)現(xiàn)理想型淘汰算法，但是可用它來評價(jià)其他替換算法。2.2.2數(shù)據(jù)結(jié)構(gòu) 主函數(shù)運(yùn)用兩個(gè)數(shù)組a、b,數(shù)組a用于存放輸入的待處理頁面號，b數(shù)組用于記錄內(nèi)存中頁面的置換情況。 FIFO（先來先出算法）：將每次進(jìn)入的頁面往數(shù)組b的最后添加，當(dāng)缺頁發(fā)生時(shí)，則淘汰b0即可。 OPT（理想型淘汰算法）：在調(diào)用主函數(shù)兩個(gè)數(shù)組的基礎(chǔ)上加數(shù)組c,數(shù)組c用于記錄b中每個(gè)頁面之后出現(xiàn)在數(shù)組a中的位置，初始值為0。當(dāng)c中有0時(shí)，直接淘汰掉b數(shù)組中與該項(xiàng)對應(yīng)的頁面，否則淘汰c數(shù)組中最大值所在位置與b對應(yīng)的頁面，即離所缺頁最遠(yuǎn)的頁面。3源程序的主要部分3.1主函數(shù)輸入輸出部分：輸入數(shù)組a:cout請輸入需要處理的頁面號：;for(i=0;iai; 選擇置換算法時(shí)，每循環(huán)一次，都對數(shù)組b進(jìn)行重新初始化。while(1)for(j=0;j10;j+) bj=-2; cout請選擇頁面處理的方式：f-FIFO；o-OPT;q-halt ch; j=0;if(ch=f) fifo(a,b,n,m);else if(ch=o) opt(a,b,n,m);else if(ch=q) break;else j=1;cout輸入錯(cuò)誤！請重新輸入： endl； 3.2 FIFO主要代碼： for(j=0;jm;j+)if(bj=ai) f=0;if(bj=-2) v=1;break;if(f=0) coutai不缺頁endl;else if(v=1) coutai發(fā)生缺頁！內(nèi)存有空余，可直接調(diào)入內(nèi)存endl;bj=ai;s+;elsecoutai發(fā)生缺頁! 淘汰頁面為：b0endl;for(j=0;jm;j+) bj=bj+1;bm-1=ai;s+;s=s/n;cout缺頁率為：sendl;當(dāng)缺頁發(fā)生且內(nèi)存無空余時(shí)，置換出b0頁面，然后將數(shù)組b中的頁面號依次前移，將新頁號存入最后，依次循環(huán)。3.3 OPT主要代碼：當(dāng)發(fā)生缺頁且內(nèi)存中無空余時(shí)，用數(shù)組c存放b中每個(gè)頁面在c中所對應(yīng)的位置，c的初始化值為0，對c中的每個(gè)值進(jìn)行比較，將其中最大的值所對應(yīng)的數(shù)組下標(biāo)賦給變量temp，則btemp即為之后最久都不會調(diào)用的狀態(tài)，淘汰該頁面，若遇到c中的某個(gè)值為0，結(jié)束循環(huán)，將該位置賦給temp，即以后都不會出現(xiàn)的頁面號，淘汰該頁面。elsefor(k=i;kn;k+)for(j=0;jm;j+)if(bj=ak) cj=k;temp=0;max=c0;for(j=1;jm;j+) if(cj=0)temp=j;break;else if(maxcj) temp=j;max=cj;4 測試用例，運(yùn)行結(jié)果與運(yùn)行情況分析主函數(shù)輸入部分： 調(diào)用FIFO置換算法所得結(jié)果：調(diào)用OPT算法所得結(jié)果：5 自我評價(jià)與總結(jié) 本周我們進(jìn)行了操作系統(tǒng)的課程設(shè)計(jì)，在拿到題目以后便著手準(zhǔn)備，通過查閱課本和相關(guān)的資料，對本次課程設(shè)計(jì)要實(shí)現(xiàn)的功能有了深刻的了解，在此基礎(chǔ)上寫起實(shí)驗(yàn)代碼變得心應(yīng)手。現(xiàn)將本次課程設(shè)計(jì)總結(jié)如下：本次課程設(shè)計(jì)順利的實(shí)現(xiàn)了對頁面置換算法FIFO和OPT的模擬演示。通過本次課程設(shè)計(jì),加深了對操作系統(tǒng)的認(rèn)識,了解了操作系統(tǒng)中各種資源分配算法的實(shí)現(xiàn),特別是對虛擬存儲,頁面置換有了深入的了解,并能夠用高級語言進(jìn)行模擬演示。頁面置換算法FIFO和 OPT理解起來相當(dāng)容易，但在實(shí)際編程實(shí)現(xiàn)的時(shí)候需要注意各種細(xì)節(jié)，需要耐心細(xì)致，實(shí)際編程中遇到一些細(xì)節(jié)上的小問題確實(shí)需要仔細(xì)考慮才行。從實(shí)驗(yàn)結(jié)果分析可知，OPT置換算法的效率要高于FIFO置換算法，這也符合理論分析。遺憾的是，OPT算法無法在操作系統(tǒng)中實(shí)現(xiàn)，因?yàn)樗蟊仨氼A(yù)先知道每一個(gè)進(jìn)程的訪問串。本次課程設(shè)計(jì)中的不足之處在于所采用的數(shù)據(jù)結(jié)構(gòu)不夠合理，輸入的頁面序列是保存在一個(gè)數(shù)組中，有最大長度的限制，應(yīng)該采用像動態(tài)鏈表等數(shù)據(jù)結(jié)構(gòu)，減少靜態(tài)方法的限制。通過一周緊張的課程設(shè)計(jì)，進(jìn)一步的加深了對課本上知識的理解和掌握，更深的體會到了操作系統(tǒng)的構(gòu)造性能在計(jì)算機(jī)系統(tǒng)中的重要性，更深貼的體會到了實(shí)踐的重要性，只有將在課堂上學(xué)到的知識融入于實(shí)踐中，才能鍛煉我們的思維能力、培養(yǎng)我們學(xué)以致用靈感，在以后的學(xué)習(xí)中，在學(xué)好理論知識的同時(shí)，我會更加重視每一次實(shí)驗(yàn)，使自己能更好的將知識用于實(shí)踐中。最后，感謝在課程設(shè)計(jì)過程中給予我?guī)椭耐瑢W(xué)和在檢查驗(yàn)收過程中提出本次課程設(shè)計(jì)中不足之處的老師，是你們的幫助和指正讓我明白的自己的不足，謝謝你們!附件：源代碼：#includeusing namespace std;void fifo(int a20,int b10,int n,int m)int i,j,f,v;double s;s=0;for(i=0;in;i+)f=1;v=0;for(j=0;jm;j+)if(bj=ai) f=0;if(bj=-2) v=1;break;if(f=0) coutai不缺頁endl;else if(v=1) coutai發(fā)生缺頁！內(nèi)存有空余，可直接調(diào)入內(nèi)存endl;bj=ai;s+;elsecoutai發(fā)生缺頁! 淘汰頁面為：b0endl;for(j=0;jm;j+)bj=bj+1;bm-1=ai;s+;s=s/n;cout缺頁率為：sendl;void opt(int a20,int b10,int n,int m)int i,j,f,v,k,temp,max,c10;double s;s=0;for(i=0;i10;i+) ci=0;for(i=0;in;i+)f=1;v=0;for(j=0;jm;j+)if(bj=ai) f=0;if(bj=-2) v=1;break;if(f=0) coutai不缺頁endl;else if(v=1) coutai發(fā)生缺頁！內(nèi)存有空余，可直接調(diào)入內(nèi)存endl;bj=ai;s+;elsefor(k=i;kn;k+)for(j=0;jm;j+)if(bj=ak) cj=k;temp=0;max=c0;for(j=1;jm;j+) if(cj=0)temp=j;break;else if(maxcj) temp=j;max=cj; coutai發(fā)生缺頁! 淘汰頁面為：btempendl;btemp=ai;s+;s=s/n;cout缺頁率為：sendl;in