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

1、實驗二 頁面置換算法實現(xiàn)一、實驗?zāi)康模?）了解內(nèi)存分頁管理策略（2）掌握調(diào)頁策略（3）掌握一般常用的調(diào)度算法（4）學(xué)會各種存儲分配算法的實現(xiàn)方法。（5）了解頁面大小和內(nèi)存實際容量對命中率的影響。二、實驗內(nèi)容采用頁式分配存儲方案，通過分別計算不同算法的命中率來比較算法的優(yōu)劣，同時也考慮頁面大小及內(nèi)存實際容量對命中率的影響，設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，并使用下述算法來模擬實現(xiàn)頁面的置換：1. 先進(jìn)先出的算法（FIFO）2. 最近最久未使用算法（LRU）3. 最佳置換算法（OPT）實驗分析在進(jìn)程運行過程中，若其所訪問的頁面不存在內(nèi)存而需要把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑時，為了保證該進(jìn)程能夠正常運

2、行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送磁盤的對換區(qū)中。但應(yīng)調(diào)出哪個頁面，需根據(jù)一定的算法來確定，算法的好壞，直接影響到系統(tǒng)的性能。一個好的頁面置換算法，應(yīng)該有較低的頁面更換頻率。2.1 先進(jìn)先出（FIFO ）頁面置換算法當(dāng)需要訪問一個新的頁面時，首先查看物理塊中是否就有這個頁面，若要查1 / 16看的頁面物理塊中就有，則直接顯示，不需要替換頁面；如果要查看的頁面物理塊中沒有，就需要尋找空閑物理塊放入，若存在有空閑物理塊，則將頁面放入；若沒有空閑物理塊，則替換頁面。并將物理塊中所有頁面 timer+。2.2 最近久未使用 (LRU) 置換算法的思路最近久未使用置換算法的替換規(guī)則，是根據(jù)頁面調(diào)入

3、內(nèi)存后的使用情況來進(jìn)行決策的。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間，當(dāng)需淘汰一個頁面的時候選擇現(xiàn)有頁面中其時間值最大的進(jìn)行淘汰。2.3 最佳（OPT）置換算法的思路其所選擇的被淘汰的頁面，是以后不使用的，或者是在未來時間內(nèi)不再被訪問的頁面，采用最佳算法，通常可保證獲得最低的缺頁率。3、 實驗流程3.1 系統(tǒng)功能圖圖3-1 系統(tǒng)功能圖3.2 算法流程圖1） 先進(jìn)先出（FIFO ）頁面置換算法流程圖圖3-2 先進(jìn)先出頁面置換算法流程圖2） 最近久未使用 (LRU) 置換算法圖3-3 最近久未使用置換算法流程圖3） 最佳（ OPT ）置換算法圖3-4 最佳置換

4、算法流程圖4、 源程序#include<iostream.h> #include <stdlib.h> #include <time.h> #include <stdio.h> #define L 20 /頁面長度最大為20 int M; /內(nèi)存塊struct Pro/定義一個結(jié)構(gòu)體 int num,time; ; Input(int m,Pro pL)/打印頁面走向狀態(tài) cout<<"請輸入頁面長度(1020)：" do cin>>m; if(m>20|m<10) cout<<

5、endl;cout<<"頁面長度必須在1020之間"<<endl<<endl;cout<<"請重新輸入L：" else break; while(1); int i,j; j=time(NULL);/取時鐘時間srand(j);/以時鐘時間j為種子，初始化隨機(jī)數(shù)發(fā)生器cout<<endl;cout<<"輸出隨機(jī)數(shù): "<<endl; cout<<endl;for(i=0;i<m;i+) pi.num=rand( )%10;/產(chǎn)生0到9

6、之間的隨機(jī)數(shù)放到數(shù)組p中pi.time=0; cout<<pi.num<<" " cout<<endl<<endl; return m; void print(Pro *page1)/打印當(dāng)前的頁面 Pro *page=new ProM; page=page1; for(int i=0;i<M;i+) cout<<pagei.num<<" " cout<<endl; int Search(int e,Pro *page1 )/尋找內(nèi)存塊中與e相同的塊號 Pro *p

7、age=new ProM; page=page1; for(int i=0;i<M;i+)if(e=pagei.num)return i;/返回i值return -1; int Max(Pro *page1)/尋找最近最長未使用的頁面 Pro *page=new ProM; page=page1; int e=page0.time,i=0; while(i<M) /找出離現(xiàn)在時間最長的頁面 if(e<pagei.time) e=pagei.time; i+; for( i=0;i<M;i+)if(e=pagei.time)return i;/找到離現(xiàn)在時間最長的頁面返回

8、其塊號return -1; int Count(Pro *page1,int i,int t,Pro pL)/記錄當(dāng)前內(nèi)存塊中頁面離下次使用間隔長度Pro *page=new ProM; page=page1;int count=0; for(int j=i;j<L;j+) if(paget.num=pj.num )break;/當(dāng)前頁面再次被訪問時循環(huán)結(jié)束else count+;/否則count+1 return count;/返回count的值 int main() int c;int m=0,t=0; float n=0;Pro pL; m=Input(m,p);/調(diào)用input函

9、數(shù)，返回m值cout<<"請輸入分配的物理塊m(26): " cout<<endl<<endl;do cin>>M; if(M>6|M<2) cout<<endl;cout<<"物理塊m必須在26之間"<<endl<<endl;cout<<"請重新輸入m： " else break; while(1); Pro *page=new ProM; do for(int i=0;i<M;i+)/初始化頁面基本情況 p

10、agei.num=0; pagei.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; co

11、ut<<endl; while(i<m) if(Search(pi.num,page)>=0) /當(dāng)前頁面在內(nèi)存中 cout<<pi.num<<" " /輸出當(dāng)前頁pi.num cout<<"不缺頁"<<endl; i+; /i加1 else /當(dāng)前頁不在內(nèi)存中 if(t=M)t=0; else n+; /缺頁次數(shù)加1 paget.num=pi.num; /把當(dāng)前頁面放入內(nèi)存中cout<<pi.num<<" " print(page); /

12、打印當(dāng)前頁面t+; /下一個內(nèi)存塊 i+; /指向下一個頁面 cout<<endl;cout<<"缺頁次數(shù)："<<n<<" 缺頁率："<<n/m<<endl<<endl; if(c=2)/LRU頁面置換 n=0; cout<<" LRU算法頁面置換情況如下: "<<endl; cout<<endl; while(i<m) int a; t=Search(pi.num,page); if(t>=0)/如果已

13、在內(nèi)存塊中 paget.time=0;/把與它相同的內(nèi)存塊的時間置0 for(a=0;a<M;a+) if(a!=t)pagea.time+;/其它的時間加1 cout<<pi.num<<" " cout<<"不缺頁"<<endl; else /如果不在內(nèi)存塊中 n+; /缺頁次數(shù)加1 t=Max(page); /返回最近最久未使用的塊號賦值給t paget.num=pi.num; /進(jìn)行替換paget.time=0; /替換后時間置為0 cout<<pi.num<<"

14、; " print(page); for(a=0;a<M;a+) if(a!=t) pagea.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(

15、Search(pi.num,page)>=0)/如果已在內(nèi)存塊中 cout<<pi.num<<" " cout<<"不缺頁"<<endl; i+; else/如果不在內(nèi)存塊中int a=0; for(t=0;t<M;t+) if(paget.num=0)a+;/記錄空的內(nèi)存塊數(shù)if(a!=0) /有空內(nèi)存 int q=M; for(t=0;t<M;t+) if(paget.num=0&&q>t)q=t;/把空內(nèi)存塊中塊號最小的找出來pageq.num=pi.num;

16、n+;cout<<pi.num<<" " print(page); i+;else int temp=0,s; for(t=0;t<M;t+)/尋找內(nèi)存塊中下次使用離現(xiàn)在最久的頁面if(temp<Count(page,i,t,p) temp=Count(page,i,t,p); s=t; /把找到的塊號賦給s pages.num=pi.num; n+; cout<<pi.num<<" " print(page); i+; cout<<endl;cout<<"缺頁

17、次數(shù)："<<n<<" 缺頁率："<<n/m<<endl<<endl; if(c = 4) break;while(c=1|c=2|c=3); return 0; 五、實驗結(jié)果5.1 程序主界面運行程序后，將會提示用戶輸入頁面長度，長度在10到20之間。當(dāng)用戶輸入長度（以12為例）后，系統(tǒng)將會顯示隨機(jī)數(shù)。系統(tǒng)提示用戶輸入分配的物理塊，用戶輸入數(shù)據(jù)（以3為例）。程序主界面運行圖如圖5-1所示。圖5-1 程序主界面5.2 先進(jìn)先出(FIFO) 頁面置換算法運行結(jié)果選擇算法1之后，進(jìn)入算法1 的操作。系統(tǒng)會顯示算法的頁面置換情況。先來先服務(wù)算法的運行圖如圖5-2所示。圖5-2 先進(jìn)先出頁面置換算法運行結(jié)果圖5.3 最近久未使用 (LRU) 置換算法運行結(jié)果選擇算法2之后，進(jìn)入算法2 的操作。系統(tǒng)會顯示算法的頁面置換情況。最近久未使用的運行圖如圖5-3所示。圖5-3 最近久未使用置換算法運行結(jié)果圖4