頁面置換 操作系統(tǒng)實驗報告

...wd......wd......wd...實驗二頁面置換算法實現(xiàn)一、實驗目的〔1〕了解內存分頁管理策略〔2〕掌握調頁策略〔3〕掌握一般常用的調度算法〔4〕學會各種存儲分配算法的實現(xiàn)方法?！?〕了解頁面大小和內存實際容量對命中率的影響。二、實驗內容采用頁式分配存儲方案，通過分別計算不同算法的命中率來比擬算法的優(yōu)劣，同時也考慮頁面大小及內存實際容量對命中率的影響，設計一個虛擬存儲區(qū)和內存工作區(qū)，并使用下述算法來模擬實現(xiàn)頁面的置換：1.先進先出的算法〔FIFO〕2.最近最久未使用算法〔LRU〕3.最正確置換算法〔OPT〕實驗分析在進程運行過程中，假設其所訪問的頁面不存在內存而需要把它們調入內存，但內存已無空閑時，為了保證該進程能夠正常運行，系統(tǒng)必須從內存中調出一頁程序或數(shù)據(jù)送磁盤的對換區(qū)中。但應調出哪個頁面，需根據(jù)一定的算法來確定，算法的好壞，直接影響到系統(tǒng)的性能。一個好的頁面置換算法，應該有較低的頁面更換頻率。2.1先進先出〔FIFO〕頁面置換算法當需要訪問一個新的頁面時，首先查看物理塊中是否就有這個頁面，假設要查看的頁面物理塊中就有，則直接顯示，不需要替換頁面；如果要查看的頁面物理塊中沒有，就需要尋找空閑物理塊放入，假設存在有空閑物理塊，則將頁面放入；假設沒有空閑物理塊，則替換頁面。并將物理塊中所有頁面timer++。2.2最近久未使用(LRU)置換算法的思路最近久未使用置換算法的替換規(guī)則，是根據(jù)頁面調入內存后的使用情況來進行決策的。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經歷的時間，當需淘汰一個頁面的時候選擇現(xiàn)有頁面中其時間值最大的進行淘汰。2.3最正確〔OPT〕置換算法的思路其所選擇的被淘汰的頁面，是以后不使用的，或者是在未來時間內不再被訪問的頁面，采用最正確算法，通?？杀ＷC獲得最低的缺頁率。實驗流程3.1系統(tǒng)功能圖圖3-1系統(tǒng)功能圖3.2算法流程圖先進先出〔FIFO〕頁面置換算法流程圖圖3-2先進先出頁面置換算法流程圖最近久未使用(LRU)置換算法圖3-3最近久未使用置換算法流程圖最正確〔OPT〕置換算法圖3-4最正確置換算法流程圖源程序#include<iostream.h>#include<stdlib.h>#include<time.h>#include<stdio.h>#defineL20//頁面長度最大為20intM;//內存塊structPro//定義一個構造體{intnum,time;};Input(intm,Prop[L])//打印頁面走向狀態(tài){ cout<<"請輸入頁面長度(10～20)："; do { cin>>m; if(m>20||m<10) {cout<<endl; cout<<"頁面長度必須在10～20之間"<<endl<<endl; cout<<"請重新輸入L："; } elsebreak; }while(1); inti,j; j=time(NULL);//取時鐘時間 srand(j);//以時鐘時間j為種子，初始化隨機數(shù)發(fā)生器 cout<<endl; cout<<"輸出隨機數(shù):"<<endl; cout<<endl; for(i=0;i<m;i++) { p[i].num=rand()%10;//產生0到9之間的隨機數(shù)放到數(shù)組p中 p[i].time=0; cout<<p[i].num<<""; } cout<<endl<<endl; returnm;}voidprint(Pro*page1)//打印當前的頁面{ Pro*page=newPro[M]; page=page1; for(inti=0;i<M;i++) cout<<page[i].num<<""; cout<<endl;}intSearch(inte,Pro*page1)//尋找內存塊中與e一樣的塊號{ Pro*page=newPro[M]; page=page1; for(inti=0;i<M;i++)if(e==page[i].num)returni;//返回i值 return-1;}intMax(Pro*page1)//尋找最近最長未使用的頁面{ Pro*page=newPro[M]; page=page1; inte=page[0].time,i=0; while(i<M)//找出離現(xiàn)在時間最長的頁面 { if(e<page[i].time)e=page[i].time; i++; } for(i=0;i<M;i++)if(e==page[i].time)returni;//找到離現(xiàn)在時間最長的頁面返回其塊號 return-1;}intCount(Pro*page1,inti,intt,Prop[L])//記錄當前內存塊中頁面離下次使用間隔長度{ Pro*page=newPro[M]; page=page1; intcount=0; for(intj=i;j<L;j++) { if(page[t].num==p[j].num)break;//當前頁面再次被訪問時循環(huán)完畢 elsecount++;//否則count+1 } returncount;//返回count的值}intmain(){ intc; intm=0,t=0; floatn=0; Prop[L]; m=Input(m,p);//調用input函數(shù)，返回m值 cout<<"請輸入分配的物理塊m(2～6):"; cout<<endl<<endl; do{ cin>>M; if(M>6||M<2) {cout<<endl; cout<<"物理塊m必須在2～6之間"<<endl<<endl; cout<<"請重新輸入m：";} elsebreak; }while(1); Pro*page=newPro[M]; do{ for(inti=0;i<M;i++)//初始化頁面根本情況 {page[i].num=0; page[i].time=m-1-i; } i=0; cout<<endl; cout<<"1:FIFO頁面置換 2:LRU頁面置換"<<endl; cout<<"3:OPT頁面置換 4:退出"<<endl; cout<<"請選擇頁面置換算法："<<endl; cin>>c; if(c==1)//FIFO頁面置換 { n=0; cout<<"FIFO算法頁面置換情況如下:"<<endl; cout<<endl; while(i<m) { if(Search(p[i].num,page)>=0)//當前頁面在內存中 { cout<<p[i].num<<"";//輸出當前頁p[i].num cout<<"不缺頁"<<endl; i++;//i加1 } else//當前頁不在內存中 { if(t==M)t=0; else { n++;//缺頁次數(shù)加1 page[t].num=p[i].num;//把當前頁面放入內存中 cout<<p[i].num<<""; print(page);//打印當前頁面 t++;//下一個內存塊 i++;//指向下一個頁面 } } } cout<<endl; cout<<"缺頁次數(shù)："<<n<<"缺頁率："<<n/m<<endl<<endl; } if(c==2)//LRU頁面置換 { n=0; cout<<"LRU算法頁面置換情況如下:"<<endl; cout<<endl; while(i<m) { inta; t=Search(p[i].num,page); if(t>=0)//如果已在內存塊中 {page[t].time=0;//把與它一樣的內存塊的時間置0 for(a=0;a<M;a++) if(a!=t)page[a].time++;//其它的時間加1 cout<<p[i].num<<""; cout<<"不缺頁"<<endl; } else//如果不在內存塊中 { n++;//缺頁次數(shù)加1 t=Max(page);//返回最近最久未使用的塊號賦值給t page[t].num=p[i].num;//進展替換 page[t].time=0;//替換后時間置為0 cout<<p[i].num<<""; print(page); for(a=0;a<M;a++) if(a!=t)page[a].time++;//其它的時間加1 } i++; } cout<<endl; cout<<"缺頁次數(shù)："<<n<<"缺頁率："<<n/m<<endl<<endl; } if(c==3)//OPT頁面置換 { n=0; cout<<"OPT算法置換情況如下:"<<endl; cout<<endl; while(i<m) { if(Search(p[i].num,page)>=0)//如果已在內存塊中 { cout<<p[i].num<<""; cout<<"不缺頁"<<endl; i++; } else//如果不在內存塊中 { inta=0; for(t=0;t<M;t++) if(page[t].num==0)a++;//記錄空的內存塊數(shù) if(a!=0)//有空內存 { intq=M; for(t=0;t<M;t++) if(page[t].num==0&&q>t)q=t;//把空內存塊中塊號最小的找出來 page[q].num=p[i].num; n++; cout<<p[i].num<<""; print(page); i++; } else { inttemp=0,s; for(t=0;t<M;t++)//尋找內存塊中下次使用離現(xiàn)在最久的頁面 if(temp<Count(page,i,t,p)) { temp=Count(page,i,t,p); s=t;}//把找到的塊號賦給s page[s].num=p[i].num; n++; cout<<p[i].num<<""; print(page); i++; } } } cout<<endl; cout<<"缺頁次數(shù)："<<n<<"缺頁率："<<n/m<<endl<<endl; } if(c==4)break;}while(c==1||c==2||c==3);return0;}五、實驗結果5.1程序主界面運行程序后，將會提示用戶輸入頁面長度，長度在10到20之間。當用戶輸入長度〔以12為例〕后，系統(tǒng)將會顯示隨機數(shù)。系統(tǒng)提示用戶輸入分配的物理塊，用戶輸入數(shù)據(jù)〔以3為例〕。程序主界面運行圖如圖5-1所示。圖5-1程序主界面5.2先進先出(FIFO)頁面置換算法運行結果選擇算法1之后，進入算法1的操作。系統(tǒng)會顯示算法的頁面置換情況。先來先服務算法的運行圖如圖5-2所示。圖5-2先進先出頁面置換算法運行結果圖5.3最近久未使用(LRU)置換算法運行結果選擇算法2之后，進入算法2的操作。系統(tǒng)會顯示算法的頁面置換情況。最近久未使用的運行圖如圖5-3所示。圖5-3最近久未使