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

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

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

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

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

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

習總是靜不下心來，效率一直不高。而且我覺得自己對本專業(yè)不是很感興趣，害

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

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

起這幾年，感覺自己真的學到的太少了。今天和一個老同學聊天，他也這么說，

感覺自己在大學又白混了三年。暑假快要到了，我想在學校學點東西，可是具體

的又不知道學什么。又怕武漢的天氣太熱，學不了什么。不過怎么來說，我一定

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