頁(yè)面置換 操作系統(tǒng)實(shí)驗(yàn)報(bào)告

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