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

齊齊哈爾大學(xué)操作系統(tǒng)課程綜合實踐題目：主界面以靈活選擇某算法班級：計本093姓名：趙明秋學(xué)號：指導(dǎo)教師：韓金庫2023年12月

主界面以靈活選擇某算法實驗摘要：計算機應(yīng)用專業(yè)的學(xué)生全面了解和掌握系統(tǒng)軟件,一般軟件設(shè)計方法和技術(shù)的必不可少的綜合課程,也是了解計算機硬件和軟件如何銜接的必經(jīng)之路。我覺得本次實驗最大的亮點以及不同于別人的地方就是將三種頁面置換算法按照課本上老師講的方式直觀簡便的輸出，在采用輸出算法時，我摒棄了常人所用的一維數(shù)組輸出法，而別出心裁的采用了二維數(shù)組的輸出算法，模擬了內(nèi)存的物理塊，清楚直觀的表達了頁面是如何在外存中被調(diào)入內(nèi)存中的，以及各頁面在調(diào)入過程中是否命中或在置換時又置換了內(nèi)存中哪個頁面。在軟件工程的角度來看，我的系統(tǒng)具有高內(nèi)聚低耦合的優(yōu)點，即各種算法之間，并不影響彼此的函數(shù)調(diào)用，而在各算法的內(nèi)部，內(nèi)聚度很高。關(guān)鍵詞：設(shè)計原理,設(shè)計方案,流程圖,源代碼，測試結(jié)果，結(jié)束語，參考文獻課題運營環(huán)境操作系統(tǒng)：WindowsXP編程環(huán)境：MicrosoftVisualC++6.01.1實驗內(nèi)容：通過模擬實現(xiàn)請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬存儲技術(shù)的特點，掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現(xiàn)過程，并比較它們的效率。熟悉虛擬存儲管理的各種液面置換算法，并辨析惡魔你程序?qū)崿F(xiàn)請求頁式存儲管理的頁面置換算法。設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū),編程序演示下述算法的具體實現(xiàn)過程,并計算訪問命中率。設(shè)計規(guī)定：主界面以靈活選擇某算法，且以下算法都要實現(xiàn)1、先進先出算法（FIFO）2、最近最久未使用算法（LRU）3、最佳置換算法（OPT）2.1運營環(huán)境1）操作系統(tǒng)：WindowsXP2）編程環(huán)境：MicrosoftVisualC++6.03.1設(shè)計原理：3.1.1先進先出算法（FIFO）最簡樸的頁面置換算法是先入先出（FIFO）法。這種算法的實質(zhì)是，總是選擇在主存中停留時間最長（即最老）的一頁置換，即先進入內(nèi)存的頁，先退出內(nèi)存。理由是：最早調(diào)入內(nèi)存的頁，其不再被使用的也許性比剛調(diào)入內(nèi)存的也許性大。建立一個FIFO隊列，收容所有在內(nèi)存中的頁。被置換頁面總是在隊列頭上進行。當一個頁面被放入內(nèi)存時，就把它插在隊尾上。這種算法只是在按線性順序訪問地址空間時才是抱負的，否則效率不高。由于那些常被訪問的頁，往往在主存中也停留得最久，結(jié)果它們因變“老”而不得不被置換出去。

FIFO的另一個缺陷是，它有一種異?，F(xiàn)象，即在增長存儲塊的情況下，反而使缺頁中斷率增長了。當然，導(dǎo)致這種異?，F(xiàn)象的頁面走向事實上是很少見的。該算法將所有使用的內(nèi)存頁面構(gòu)成一個循環(huán)列隊，每次置換時將隊列中的隊首喚出，隊首指針后移一位即可，算法容易實現(xiàn)牡丹石最先進入內(nèi)存的野末必將來就不用再到，甚至也許不久就會用到，所以不能保證有效的缺頁率，算法性能較差。3.2.2最近最久未使用算法（LRU）FIFO算法和OPT算法之間的重要差別是，F(xiàn)IFO算法運用頁面進入內(nèi)存后的時間長短作為置換依據(jù)，而OPT算法的依據(jù)是將來使用頁面的時間。假如以最近的過去作為不久將來的近似，那么就可以把過去最長一段時間里不曾被使用的頁面置換掉。它的實質(zhì)是，當需要置換一頁時，選擇在最近一段時間里最久沒有使用過的頁面予以置換。這種算法就稱為最久未使用算法（LeastRecentlyUsed，LRU）。

LRU算法是與每個頁面最后使用的時間有關(guān)的。當必須置換一個頁面時，LRU算法選擇過去一段時間里最久未被使用的頁面。

LRU算法是經(jīng)常采用的頁面置換算法，并被認為是相稱好的，但是存在如何實現(xiàn)它的問題。LRU算法需要實際硬件的支持。其問題是怎么擬定最后使用時間的順序，對此有兩種可行的辦法：

（1）計數(shù)器。最簡樸的情況是使每個頁表項相應(yīng)一個使用時間字段，并給CPU增長一個邏輯時鐘或計數(shù)器。每次存儲訪問，該時鐘都加1。每當訪問一個頁面時，時鐘寄存器的內(nèi)容就被復(fù)制到相應(yīng)頁表項的使用時間字段中。這樣我們就可以始終保存著每個頁面最后訪問的“時間”。在置換頁面時，選擇該時間值最小的頁面。這樣做，不僅要查頁表，并且當頁表改變時（因CPU調(diào)度）要維護這個頁表中的時間，還要考慮屆時鐘值溢出的問題。

（2）棧。用一個棧保存頁號。每當訪問一個頁面時，就把它從棧中取出放在棧頂上。這樣一來，棧頂總是放有目前使用最多的頁，而棧底放著目前最少使用的頁。由于要從棧的中間移走一項，所以要用品有頭尾指針的雙向鏈連起來。在最壞的情況下，移走一頁并把它放在棧頂上需要改動6個指針。每次修改都要有開銷，但需要置換哪個頁面卻可直接得到，用不著查找，由于尾指針指向棧底，其中有被置換頁。

因?qū)崿F(xiàn)LRU算法必須有大量硬件支持，還需要一定的軟件開銷。所以實際實現(xiàn)的都是一種簡樸有效的LRU近似算法。

一種LRU近似算法是最近未使用算法（NotRecentlyUsed，NUR）。它在存儲分塊表的每一表項中增長一個引用位，操作系統(tǒng)定期地將它們置為0。當某一頁被訪問時，由硬件將該位置1。過一段時間后，通過檢查這些位可以擬定哪些頁使用過，哪些頁自上次置0后尚未使用過。就可把該位是0的頁淘汰出去，由于在最近一段時間里它未被訪問過。3.3.3最佳置換算法（OPT）最優(yōu)置換（OptimalReplacement）是在理論上提出的一種算法。其實質(zhì)是：當調(diào)入新的一頁而必須預(yù)先置換某個老頁時，所選擇的老頁應(yīng)是將來不再被使用，或者是在最遠的將來才被訪問。采用這種頁面置換算法，保證有最少的缺頁率。但是最優(yōu)頁面置換算法的實現(xiàn)是困難的，由于它需要人們預(yù)先就知道一個進程整個運營過程中頁面走向的所有情況。但是，這個算法可用來衡量（如通過模擬實驗分析或理論分析）其他算法的優(yōu)劣。該算法能保證有最低的缺頁率，所以稱為最佳置換算法，但是該算法緊緊是一種抱負狀況下的算法，由于在進程實際運營過程中，將來會執(zhí)行到那兒頁是不可預(yù)知的，所以無法選擇該置換那個頁出去。因此，本算法在實際中無法使用，只能作為一種標準來衡量其他算法的性能4.1設(shè)計方案1）主界面：設(shè)立頁面產(chǎn)生算法選擇界面和頁面置換算法選擇界面；2）子界面：頁面產(chǎn)生算法分為兩個界面，分別是隨機產(chǎn)生算法和自己輸入產(chǎn)生算法。頁面置換算法分為三個子界面，分別是先進先出算法界面、最近最久未使用算法界面、最佳置換算法界面。5.1流程圖5.1.1主流程圖圖（1）5.1.2FIFO函數(shù)流程圖圖（2）5.1.3LRU函數(shù)流程圖：圖（4）5.1.4OPT函數(shù)流程圖：圖（5）6.源代碼6.1程序代碼#include<iostream>#include<time.h>#include<math.h>#defineBsize3#definePsize12#include<string>usingnamespacestd;intQString[Psize];intNum=0;structpageInfor{intcontent;inttimer;};classYZ_replace{public:YZ_replace();~YZ_replace();intfindSpace();intfindExist(intcurpage);intfindReplace();voidFIFO();voidOPT();voidBlockClear();voidinitia1(intstring[]);pageInfor*block;pageInfor*page;intmemory_state[Bsize][Psize];ints;private:};voidP_String(intQString[]){ inti;srand((unsigned)time(NULL));for(i=0;i<Psize;i++) {QString[i]=rand()*9/RAND_MAX+1; }cout<<"頁面走向：";for(i=0;i<Psize;i++) {cout<<QString[i]<<""; }cout<<endl;}YZ_replace::YZ_replace(){ s=0;block=newpageInfor[Bsize];for(inti=0;i<Bsize;i++) { block[i].content=-1;block[i].timer=0; }}voidYZ_replace::initia1(intQString[]){intj;page=newpageInfor[Psize];for(inti=0;i<Psize;i++){page[i].content=QString[i];page[i].timer=0;}for(i=0;i<Psize;i++)for(j=0;j<Bsize;j++)memory_state[j][i]=0;}YZ_replace::~YZ_replace(){s=0;}intYZ_replace::findSpace(){for(inti=0;i<Bsize;i++)if(block[i].content==-1)returni;return-1;}intYZ_replace::findExist(intcurpage){for(inti=0;i<Bsize;i++)if(block[i].content==page[curpage].content)returni;return-1;}intYZ_replace::findReplace(){intpos=0;for(inti=0;i<Bsize;i++)if(block[i].timer>=block[pos].timer)pos=i;returnpos;}voidYZ_replace::FIFO(){intexist,space,position;for(inti=0;i<Psize;i++){exist=findExist(i);if(exist!=-1){for(intb=0;b<Bsize;b++){memory_state[b][i]=memory_state[b][i-1];}s++;}else{space=findSpace();if(space!=-1){for(intb=0;b<Bsize;b++){memory_state[b][i]=memory_state[b][i-1];}block[space]=page[i];memory_state[space][i]=block[space].content;}else{for(intb=0;b<Bsize;b++){memory_state[b][i]=memory_state[b][i-1];}position=findReplace();block[position]=page[i];memory_state[position][i]=block[position].content;}}for(intj=0;j<Bsize;j++)block[j].timer++;}}voidYZ_replace::BlockClear(){for(inti=0;i<Bsize;i++){block[i].content=-1;block[i].timer=0;}}typedefstructpage{intnum;inttime;}Page;Pageb[Bsize];Pagecall[Bsize];intc[Bsize][Psize];intqueue[100];intK;voidInitL(Page*b,intc[Bsize][Psize]){inti,j;for(i=0;i<Bsize;i++){b[i].num=-1;b[i].time=Psize-i-1;}for(i=0;i<Bsize;i++)for(j=0;j<Psize;j++)c[i][j]=-1;}intGetMax(Page*b){inti;intmax=-1;inttag=0;for(i=0;i<Bsize;i++){if(b[i].time>max){max=b[i].time;tag=i;}}returntag;}intEquation(intfold,Page*b){inti;for(i=0;i<Bsize;i++){if(fold==b[i].num)returni;}return-1;}voidLru(intfold,Page*b){inti;intval;val=Equation(fold,b);if(val>=0){b[val].time=0;for(i=0;i<Bsize;i++)if(i!=val)b[i].time++;}else{queue[++K]=fold;val=GetMax(b);b[val].num=fold;b[val].time=0;for(i=0;i<Bsize;i++)if(i!=val)b[i].time++;}}voidYZ_replace::OPT(){ intexist,space,position; for(inti=0;i<Psize;i++) { exist=findExist(i); if(exist!=-1) { for(intb=0;b<Bsize;b++) { memory_state[b][i]=memory_state[b][i-1]; } s++; } else { space=findSpace(); if(space!=-1) { for(intb=0;b<Bsize;b++) { memory_state[b][i]=memory_state[b][i-1]; } block[space]=page[i]; memory_state[space][i]=block[space].content; } else { for(intk=0;k<Bsize;k++) { memory_state[k][i]=memory_state[k][i-1]; for(intj=i;j<Psize;j++) { if(block[k].content!=page[j].content) {block[k].timer=1000;} else {block[k].timer=j;break;} } } position=findReplace(); block[position]=page[i]; memory_state[position][i]=block[position].content; } } }}intdecide(stringstr){ for(inti=0;i<str.size();i++) { if(str[i]<'0'||str[i]>'9') { return0; break; } } returni;}inttrans(stringstr){ intsum=0; for(inti=0;i<str.size();i++) sum=sum+(str[i]-'0')*pow(10,str.size()-i-1); returnsum;}intput(){ inta,d; stringstr; cin>>str; a=decide(str); while(a==0) { cout<<"輸入錯誤,請重新輸入！"<<endl; cin>>str; a=decide(str); }d=trans(str); returnd;}voidPut(){cout<<"請選擇產(chǎn)生頁面的方法a:隨機產(chǎn)生b:輸入產(chǎn)生"<<endl;cout<<"您選擇的菜單是:";charF;cin>>F;while(F!='a'&&F!='b') { cout<<"輸入錯誤，請重新輸入:"; cin>>F; }if(F=='a') P_String(QString);if(F=='b') { cout<<"請輸入各頁面號:"<<endl; for(inti=0;i<Psize;i++) { QString[i]=put(); } }cout<<endl;cout<<"||"<<endl;}voidmain(){cout<<"|頁面置換算法|"<<endl;cout<<"||"<<endl;intt=1;while(t){ Put(); YZ_replacetest1;YZ_replacetest3; charselect; do{ cout<<"請選擇要應(yīng)用的算法:<1>FIFO算法<2>LRU算法<3>OPT算法<0>退出"<<endl;intp,q;cout<<"請您輸入菜單號:";cin>>select;while(select!='0'&&select!='1'&&select!='2'&&select!='3') { cout<<"您的輸入無效,請重新輸入:"<<endl; cin>>select; }if(select=='0') { cout<<"您選擇的是菜單<0>"<<endl;cout<<"完畢退出."<<endl; t=0; }if(select=='1') { cout<<"您選擇的是菜單<1>"<<endl;cout<<"FIFO算法狀態(tài):"<<endl; test1.initia1(QString);test1.FIFO();test1.BlockClear();cout<<""<<endl;for(p=0;p<Bsize;p++) {for(q=0;q<Psize;q++)cout<<test1.memory_state[p][q]<<"";cout<<endl; }cout<<""<<endl;cout<<"命中率:"<<test1.s<<"/"<<Psize<<endl;test1.~YZ_replace();cout<<endl; }if(select=='2') {inti,j;K=-1;InitL(b,c);for(i=0;i<Psize;i++) {Lru(QString[i],b);c[0][i]=QString[i];for(j=0;j<Bsize;j++)c[j][i]=b[j].num; } cout<<"您選擇的是菜單<2>"<<endl;cout<<"LRU算法狀態(tài):"<<endl;cout<<""<<endl;for(i=0;i<Bsize;i++) { for(j=0;j<Psize;j++) { if(c[i][j]==-1) cout<<"0"; else cout<<""<<c[i][j]; } cout<<""<<endl; }cout<<""<<endl;cout<<"命中率:"<<(Psize-(K+1))<<"/"<<Psize;cout<<'\t'; cout<<endl; }if(select=='3') { cout<<"您選擇的是菜單<3>"<<endl;cout<<"OPT算法狀態(tài):"<<endl; test3.initia1(QString); test3.OPT();test3.BlockClear();cout<<""<<endl;for(p=0;p<Bsize;p++) {for(q=0;q<Psize;q++)cout<<test3.memory_state[p][q]<<"";cout<<endl; } cout<<""<<endl; cout<<"命中率:"<<test3.s<<"/"<<Psize<<endl; test3.~YZ_replace(); cout<<endl; } }while(select=='1'||select=='2'||select=='3');}}7.測試結(jié)果7.1頁面選擇測試：圖（7.1）圖（7.2）分析：頁面產(chǎn)生的方法有兩種選擇，分別是隨機產(chǎn)生和自己輸入產(chǎn)生，選擇菜單的時候有對異常輸入的解決，假如輸入錯誤，有錯誤提醒，當輸入對的菜單的時候，選擇a，自動產(chǎn)生頁面走向，假如選擇b，自己可以任意輸入，假如輸入錯誤，有錯誤提醒。6.2應(yīng)用算法選擇測試圖（7.3）分析：選擇算法時，有異常解決，即假如輸入錯誤，有錯誤提醒。假如選擇菜單1，即選擇了FIFO算法，展示此算法的置換狀態(tài)并顯示命中率。置換狀態(tài)以二維數(shù)組的形式輸出，既直觀又清楚。