操作系統(tǒng)原理課程設(shè)計(jì)-頁(yè)面置換算法模擬程序

頁(yè)面置換算法模擬程序頁(yè)面置換算法模擬程序PAGE數(shù)學(xué)與計(jì)算機(jī)學(xué)院課程設(shè)計(jì)說(shuō)明書課程名稱:操作系統(tǒng)原理-課程設(shè)計(jì)課程代碼:題目:頁(yè)面置換算法模擬程序年級(jí)/專業(yè)/班:學(xué)生姓名:學(xué)號(hào):開(kāi)始時(shí)間:完成時(shí)間:課程設(shè)計(jì)成績(jī)：學(xué)習(xí)態(tài)度及平時(shí)成績(jī)（30）技術(shù)水平與實(shí)際能力（20）創(chuàng)新（5）說(shuō)明書撰寫質(zhì)量（45）總分（100）指導(dǎo)教師簽名：年月日目錄TOC\o"1-2"\h\z1引言 11.1問(wèn)題的提出 11.2國(guó)內(nèi)外研究的現(xiàn)狀 11.3任務(wù)與分析 22需求分析 23開(kāi)發(fā)平臺(tái) 23.1開(kāi)發(fā)工具 23.1開(kāi)發(fā)語(yǔ)言 24概要設(shè)計(jì) 34.1總體設(shè)計(jì)框圖 35詳細(xì)設(shè)計(jì) 45.1代碼分析結(jié)果 65.11數(shù)據(jù)結(jié)構(gòu) 65.12FIFO具體函數(shù)及設(shè)計(jì)實(shí)現(xiàn) 65.13LRU具體函數(shù)及設(shè)計(jì)實(shí)現(xiàn) 95.14調(diào)用關(guān)系圖 146測(cè)試 146.1進(jìn)入界面及產(chǎn)生頁(yè)面走向 146.2FIFO算法及查看結(jié)果 156.3LRU算法及查看結(jié)果 166.4繼續(xù)進(jìn)入主界面及產(chǎn)生頁(yè)面走向 166.5調(diào)度算法及結(jié)果 177總結(jié)與體會(huì) 18參考文獻(xiàn) 19

摘要在地址映射過(guò)程中，若在頁(yè)面中發(fā)現(xiàn)所要訪問(wèn)的頁(yè)面不再內(nèi)存中，則產(chǎn)生缺頁(yè)中斷。當(dāng)發(fā)生缺頁(yè)中斷時(shí)操作系統(tǒng)必須在內(nèi)存選擇一個(gè)頁(yè)面將其移出內(nèi)存，以便為即將調(diào)入的頁(yè)面讓出空間。而用來(lái)選擇淘汰哪一頁(yè)的規(guī)則叫做頁(yè)面置換算法。在進(jìn)程運(yùn)行過(guò)程中，若其所要訪問(wèn)的頁(yè)面不在內(nèi)存需把它們調(diào)入內(nèi)存，但內(nèi)存已無(wú)空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)，送磁盤的對(duì)換區(qū)中。但應(yīng)將哪個(gè)頁(yè)面調(diào)出，所以需要根據(jù)一定的算法來(lái)確定。常用的算法有先進(jìn)先出置換算法（FIFO）,最近最久未使用置換算法（LRU）和最佳置換算法（OPT），該設(shè)計(jì)是在VC++6.0環(huán)境下分別用LRU和FIFO來(lái)實(shí)現(xiàn)頁(yè)面置換算法的模擬程序，并測(cè)試。關(guān)鍵詞：操作系統(tǒng);頁(yè)面置換算法模擬;進(jìn)程調(diào)度;FIFO;LRU頁(yè)面置換算法模擬程序頁(yè)面置換算法模擬程序課程設(shè)計(jì)題目（改為黑色）課程設(shè)計(jì)題目（改為黑色）1引言1.1問(wèn)題的提出隨著硬件技術(shù)的發(fā)展，各式各樣的大容量存儲(chǔ)設(shè)備相繼出現(xiàn)，一臺(tái)計(jì)算機(jī)上可能存在多種外存儲(chǔ)設(shè)備。不同存儲(chǔ)設(shè)備有著不同的讀寫速度，同一種設(shè)備的讀寫速度有可能也會(huì)相差很大。因此在多種具有不同讀寫速度的外存儲(chǔ)設(shè)備的環(huán)境下，選擇一種合適的頁(yè)面淘汰算法，對(duì)整個(gè)系統(tǒng)的性能會(huì)有很大的提高。在進(jìn)程運(yùn)行過(guò)程中，若其所要訪問(wèn)的頁(yè)面不在內(nèi)存需把它們調(diào)入內(nèi)存，但內(nèi)存已無(wú)空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)，送磁盤的對(duì)換區(qū)中。但應(yīng)將哪個(gè)頁(yè)面調(diào)出，所以需要根據(jù)一定的算法來(lái)確定。如果能夠很好的使用頁(yè)面置換將大大節(jié)省內(nèi)存的額外開(kāi)銷。1.2國(guó)內(nèi)外研究的現(xiàn)狀1966年Belady在理論上提出最優(yōu)頁(yè)面置換算法（OPT）,此外還有先進(jìn)先出（FIFO），最少使用置換算法（LRU）。不同存儲(chǔ)設(shè)備有著不同的讀寫速度，同一種設(shè)備的讀寫速度有可能也會(huì)相差很大。因此在多種具有不同讀寫速度的外存儲(chǔ)設(shè)備的環(huán)境下，選擇一種合適的頁(yè)面淘汰算法，對(duì)整個(gè)系統(tǒng)的性能會(huì)有很大的提高。1.3任務(wù)與分析本課題主要的目的是編制頁(yè)面置換算法FIFO和LRU的模擬程序,并模擬其在內(nèi)存的分配過(guò)程。同時(shí)根據(jù)頁(yè)面走向，分別采用FIFO和LRU算法進(jìn)行頁(yè)面置換，統(tǒng)計(jì)缺頁(yè)率；為簡(jiǎn)化操作，在淘汰一頁(yè)時(shí)，只將該頁(yè)在頁(yè)表中抹去,而不再判斷它是否被改寫過(guò)，也不將它寫回到輔存。2需求分析本程序?qū)崿F(xiàn)了操作系統(tǒng)中頁(yè)式虛擬存儲(chǔ)管理中缺頁(yè)中斷理想型淘汰算法，該算法在訪問(wèn)串中將來(lái)再也不出現(xiàn)的或是在離當(dāng)前最遠(yuǎn)的位置上出現(xiàn)的頁(yè)淘汰掉。這樣，淘汰掉該頁(yè)將不會(huì)造成因需要訪問(wèn)該頁(yè)又立即把它調(diào)入的現(xiàn)象。該程序能按要求隨機(jī)確定內(nèi)存大小，隨機(jī)產(chǎn)生頁(yè)面數(shù)，進(jìn)程數(shù)，每個(gè)進(jìn)程的頁(yè)數(shù)，給進(jìn)程分配的頁(yè)數(shù)等，然后運(yùn)用理想型淘汰算法對(duì)每個(gè)進(jìn)程進(jìn)行計(jì)算缺頁(yè)數(shù)，缺頁(yè)率，被淘汰的序列等功能。3開(kāi)發(fā)平臺(tái)3.1開(kāi)發(fā)工具VC++6.03.1開(kāi)發(fā)語(yǔ)言VC++語(yǔ)言

4概要設(shè)計(jì)4.1總體設(shè)計(jì)框圖進(jìn)入程序進(jìn)入程序輸入頁(yè)面數(shù)輸入頁(yè)面數(shù)頁(yè)面走向最少使用置換先進(jìn)先出置換隨即產(chǎn)生用戶輸入

5詳細(xì)設(shè)計(jì)頁(yè)面走向最少使用置換先進(jìn)先出置換隨即產(chǎn)生用戶輸入開(kāi)始開(kāi)始輸入頁(yè)面數(shù)0手動(dòng)輸入1隨機(jī)產(chǎn)生(0)FIFO(1)OPT輸入數(shù)據(jù)輸入個(gè)數(shù)輸出FIFO結(jié)果輸出OPT結(jié)果是否輸入Y/y結(jié)束輸出另外一種結(jié)果是否繼續(xù)(N/n)圖5.1詳細(xì)設(shè)計(jì)框圖開(kāi)始開(kāi)始初始化數(shù)據(jù)，確定頁(yè)面走向判斷頁(yè)號(hào)是否等于頁(yè)面流號(hào)算出內(nèi)存中各個(gè)頁(yè)號(hào)相對(duì)于當(dāng)前位置，并置換了學(xué)校,也不免想到自己明年將要離開(kāi)的情景,心里也感覺(jué)到一種凄涼.原來(lái)一直都想著要考研的,經(jīng)過(guò)幾個(gè)月的考慮,發(fā)現(xiàn)自己或許不適合考研吧,

復(fù)習(xí)總是那么得不盡人意。離開(kāi)了老師的約束和同學(xué)的相互促進(jìn)，我發(fā)現(xiàn)自己學(xué)

習(xí)總是靜不下心來(lái)，效率一直不高。而且我覺(jué)得自己對(duì)本專業(yè)不是很感興趣，害

怕自己又浪費(fèi)掉三年，而學(xué)不到什么東西。一直就這樣猶豫著，從三月到六月，

現(xiàn)在終于決定放棄我的考研路。考研或許真的就不適合我吧！決定不考研之后，我就面臨著工作的問(wèn)題，可是我拿什么來(lái)面對(duì)工作呢？回想

起這幾年，感覺(jué)自己真的學(xué)到的太少了。今天和一個(gè)老同學(xué)聊天，他也這么說(shuō)，

感覺(jué)自己在大學(xué)又白混了三年。暑假快要到了，我想在學(xué)校學(xué)點(diǎn)東西，可是具體

的又不知道學(xué)什么。又怕武漢的天氣太熱，學(xué)不了什么。不過(guò)怎么來(lái)說(shuō)，我一定

要為工作好好準(zhǔn)備一下。的距離淘汰距離最大的那個(gè)頁(yè)號(hào)，并進(jìn)行換頁(yè)距離是否相等比較出現(xiàn)的次數(shù)淘汰出現(xiàn)次數(shù)少的頁(yè)號(hào)，并進(jìn)行換頁(yè)輸出淘汰的頁(yè)號(hào)模塊結(jié)束否是是否 圖5.2為置換方法的流程圖5.1代碼分析結(jié)果5.11數(shù)據(jù)結(jié)構(gòu)intm,intneed[],intn,result[10][20],intstate[],intcount1[];5.12FIFO具體函數(shù)及設(shè)計(jì)實(shí)現(xiàn)FIFO流程圖開(kāi)始開(kāi)始頁(yè)面大小m頁(yè)面大小m，頁(yè)面走向放在head[]結(jié)果表result[][]和狀態(tài)表count[]賦值為-1結(jié)果表result[][]和狀態(tài)表count[]賦值為-1RResult[][]是否為空 有是否在頁(yè)表內(nèi)裝入頁(yè)表中，缺頁(yè)次數(shù)count++ 是否在頁(yè)表內(nèi)裝入頁(yè)表中，缺頁(yè)次數(shù)count++ 不在 替換出先進(jìn)入結(jié)果表中的頁(yè)面 在替換出先進(jìn)入結(jié)果表中的頁(yè)面步數(shù)page++步數(shù)page++ 統(tǒng)計(jì)缺頁(yè)數(shù)和缺頁(yè)率統(tǒng)計(jì)缺頁(yè)數(shù)和缺頁(yè)率輸出過(guò)程及結(jié)果輸出過(guò)程及結(jié)果結(jié)束結(jié)束FIFO函數(shù)實(shí)現(xiàn)voidFIFO(intm,intneed[],intn)//m分配物理頁(yè)面大小，n需要頁(yè)面數(shù)組的最大值{ intp=0; //當(dāng)前請(qǐng)求的頁(yè)面 intdel=0;//步數(shù) intcount1[20]; doublecount=0; //缺頁(yè)數(shù) doubleque=0; //缺頁(yè)率 intresult[10][20]; //結(jié)果表 for(inti=0;i<=m;i++)for(intj=0;j<=n;j++) { result[i][j]=-1; count1[j]=-1; }while(n>=p){intk=need[p];if(p>0){ for(inti=0;i<=m;i++){ result[i][p]=result[i][p-1]; }}intf1=0;//首先看是否有空位置或者已經(jīng)存在請(qǐng)求的頁(yè)面for(inti=0;i<=m;i++){if(result[i][p]==-1) { result[i][p]=k; f1=1; i=m+1; count1[p]=k; count=count+1; p=p+1; } elseif(result[i][p]==k){f1=1;p=p+1;i=m+1;}}if(f1==1)continue;//這里發(fā)生替換result[del][p]=k; count1[p]=k; count=count+1;p=p+1; del=(del+1)%(m+1);}cout<<"*******************FIFO過(guò)程如下表************************"<<endl;for(intt3=0;t3<=n;t3++)//輸出原來(lái)的頁(yè)面 cout<<need[t3]<<"";cout<<endl;for(intt0=0;t0<=m;t0++)//判斷頁(yè)表是否填滿{for(intt1=0;t1<=n;t1++) { if(result[t0][t1]!=-1) cout<<result[t0][t1]<<""; elsecout<<""<<""; } cout<<endl;}for(intj1=0;j1<=n;j1++)//對(duì)于缺頁(yè)的打×，否則打√{ if(count1[j1]!=-1) cout<<"×"; elsecout<<"√";} cout<<endl; que=count/(n+1);//統(tǒng)計(jì)缺頁(yè)次數(shù)和缺頁(yè)率 cout<<"缺頁(yè)次數(shù)為:"<<count<<endl; cout<<"缺頁(yè)率"<<count<<"/"<<n+1<<"="<<que<<endl; cout<<"**************************************************"<<endl;}5.13LRU具體函數(shù)及設(shè)計(jì)實(shí)現(xiàn)LRU流程圖開(kāi)始開(kāi)始頁(yè)面大小m，頁(yè)面走向放在head[]頁(yè)面大小m，頁(yè)面走向放在head[]給表result[][]和狀態(tài)表state[]分配空間給表result[][]和狀態(tài)表state[]分配空間RResult[][]是否為空 有是否在頁(yè)表內(nèi)裝入頁(yè)表中，缺頁(yè)次數(shù)num++ 是否在頁(yè)表內(nèi)裝入頁(yè)表中，缺頁(yè)次數(shù)num++ 不在 替換出最久沒(méi)使用結(jié)果表中的頁(yè)面 在替換出最久沒(méi)使用結(jié)果表中的頁(yè)面賦值給賦值給hsive[k] 統(tǒng)計(jì)缺頁(yè)數(shù)和缺頁(yè)率統(tǒng)計(jì)缺頁(yè)數(shù)和缺頁(yè)率輸出過(guò)程及結(jié)果輸出過(guò)程及結(jié)果結(jié)束結(jié)束LRU函數(shù)實(shí)現(xiàn)voidLRU(intm,intneed[],intn){ m++; n++; inti,j,min,num=1,k,flag; intstate[10],count[20],hsive[10]; intresult[10][20]; memset(state,0,sizeof(state));//初始化內(nèi)存空間，給三個(gè)數(shù)組分配內(nèi)存 memset(count,-1,sizeof(count)); memset(hsive,-1,sizeof(hsive)); memset(result,-1,sizeof(result)); for(i=0;i<n;i++)//將need數(shù)組值賦給result result[0][i]=need[i]; cout<<"*****************LRU過(guò)程如下表*********************"<<endl; for(i=0;i<n;i++) { flag=0;//標(biāo)志位，如果頁(yè)面和頁(yè)表內(nèi)的熄燈則賦值 for(j=1;j<num;j++) { if(result[0][i]==hsive[j]) { flag=1; state[j]=-1; break; } } if(flag==0)//替換 { if(num<=m) hsive[num]=result[0][i]; else { min=-1; for(j=1;j<=m;j++) { if(state[j]>min) { k=j; min=state[j]; } } hsive[k]=result[0][i]; state[k]=-1; } count[i]=1; num++; } for(j=1;j<=m;j++) { result[j][i]=hsive[j]; state[j]++; } } for(j=0;j<=m;j++)//輸入個(gè)頁(yè)面替換情況 { for(i=0;i<n;i++) { if(result[j][i]==-1) cout<<""; else cout<<result[j][i]<<""; } cout<<endl; } for(i=0;i<n;i++) { if(count[i]!=-1) cout<<"×"; else cout<<"√"; } cout<<endl;//統(tǒng)計(jì)各頁(yè)面缺頁(yè)次數(shù)和缺頁(yè)率 cout<<"缺頁(yè)次數(shù)為:"<<num-1<<endl; cout<<"缺頁(yè)率"<<num-1<<"/"<<n<<"="<<double(num-1)/n<<endl; cout<<"**************************************************"<<endl;}主方法intmain(){ cout<<"*********************************************"<<endl; cout<<"*頁(yè)式存儲(chǔ)管理*"<<endl; cout<<"*********************************************"<<endl; intm; intn=0; intchoose=2; intneed[20]; charflag; while(1) { cout<<"指定內(nèi)存分配頁(yè)面數(shù):"; while(flag<'0'||flag>'9') { cin>>flag; } m=flag-'0'-1; flag=''; cout<<"請(qǐng)選擇頁(yè)面序列產(chǎn)生方式:"<<endl; cout<<"(0)手動(dòng)輸入"<<endl; cout<<"(1)隨機(jī)產(chǎn)生"<<endl; while(flag<'0'||flag>'1') { cin>>flag; }choose=flag-'0'; flag=''; if(choose==0){ cout<<"輸入頁(yè)面走向！以s結(jié)尾"<<endl; while(1) { while((flag<'0'||flag>'9')&&flag!='s') { cin>>flag; } if(flag=='s')break;need[n]=flag-'0'; flag=''; n=n+1; } flag=''; n=n-1; } else{ cout<<"隨機(jī)產(chǎn)生的頁(yè)面?zhèn)€數(shù):"; cin>>n; n=n-1;for(inti=0;i<=n;i++) { need[i]=rand()%10; } } system("cls"); cout<<"選擇頁(yè)面置換算法:"<<endl; cout<<"0-FIFO1-LRU"<<endl; while(flag<'0'||flag>'1') { cin>>flag; }choose=flag-'0'; flag=''; if(choose==0){ FIFO(m,need,n); } else{ LRU(m,need,n); } cout<<"輸入Y/y可以看另外一種置換算法的執(zhí)行過(guò)程"<<endl; cin>>flag;if(flag=='Y'||flag=='y') { system("cls");if(choose==0) LRU(m,need,n); else FI