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

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

3、未使用置換算法的替換規(guī)則，是根據頁面調入內存后的使用情況來進 行決策的。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問 以來所經歷的時間，當需淘汰一個頁面的時候選擇現有頁面中其時間值最大的進 行淘汰。2.3最佳（OPT置換算法的思路其所選擇的被淘汰的頁面，是以后不使用的，或者是在未來時間內不再被訪 問的頁面，采用最佳算法，通?？杀ＷC獲得最低的缺頁率。三、實驗流程3.1系統功能圖圖3-1系統功能圖3.2算法流程圖1）先進先出（FIFO ）頁面置換算法流程圖開始R頁熬度當前英面在內存中結束i 2麗七主斗討麗石丙存GY緒克圖3-2先進先出頁面置換算法流程圖2)最近久未使用(LRU)置換

4、算法輸出N國輸岀當葡頁囲輸出缺頁信息輸出不訣頁箍岀航頁信息籀出不缺頁遲打替抉圖3-3最近久未使用置換算法流程圖3）最佳（OPT ）置換算法圖3-4最佳置換算法流程圖四、源程序#i nclude<iostream.h>#i nclude <stdlib.h>#in elude <time.h>#i nclude <stdio.h>#define L 20 /頁面長度最大為20int M; / 內存塊struct Pro/定義一個結構體int num,time;Input(int m,Pro pL)/ 打印頁面走向狀態(tài)coutvv"請輸入頁

5、面長度(1020):"do cin>>m;if(m>20|m<10) cout<<endl;cout<<" 頁面長度必須在 10 20 之間 "<<endl<<endl;cout<<" 請重新輸入 L: "else break;while(1);int i,j;j=time(NULL);/ 取時鐘時間srand(j);/ 以時鐘時間 j 為種子，初始化隨機數發(fā)生器cout<<endl;cout<<" 輸出隨機數 : "

6、<<endl;cout<<endl;for(i=0;i<m;i+)pi.num=rand( )%10;/ 產生 0 到 9 之間的隨機數放到數組 p 中 pi.time=0;cout<<pi.num<<" "cout<<endl<<endl;return m;void print(Pro *page1)/ 打印當前的頁面Pro *page=new ProM; page=page1;for(int i=0;i<M;i+)cout<<pagei.num<<" &

7、quot;cout<<endl;int Search(int e,Pro *page1 )/尋找內存塊中與 e 相同的塊號Pro *page=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) / 找出離現在時間最長的頁面if(e<pagei.time) e=page

8、i.time;i+;找到離現在時間最長for( i=0;i<M;i+)if(e=pagei.time)return i;/ 的頁面返回其塊號return -1;int Count(Pro *page1,int i,int t,Pro pL)/ 記錄當前內存塊中頁面離下次 使用間隔長度Pro *page=new ProM;page=page1;int count=0;for(int j=i;j<L;j+)if(paget.num=pj.num )break;/ 當前頁面再次被訪問時循環(huán)結束 else count+;/ 否則 count+1return count;/ 返回 count

9、 的值int main()int c;int m=0,t=0;float n=0;Pro pL;m=I nput(m,p); 調用in put函數，返回 m值coutvv"請輸入分配的物理塊 m(26):"cout<<endl<<endl;docin>>M;if(M>6|M<2) cout<<endl;cout«"物理塊m必須在26之間"<<endl«endl; cout<<" 請重新輸入 m： "else break;while(

10、1);Pro *page=new ProM;dofor(int i=0;i<M;i+)/ 初始化頁面基本情況 pagei.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;co

11、ut<<" FIFO 算法頁面置換情況如下 : "<<endl; cout<<endl;while(i<m)if(Search(pi.num,page)>=0) / 當前頁面在內存中cout<<pi.num<<" " / 輸出當前頁 pi.numcout<<" 不缺頁 "<<endl;i+; /i 加 1else / 當前頁不在內存中if(t=M)t=0;elsen+; / 缺頁次數加 1paget.num=pi.num; /把當前頁面放入

12、內存中cout<<pi.num<<" "print(page); / 打印當前頁面t+; / 下一個內存塊i+; / 指向下一個頁面cout<<endl;cout<<" 缺頁次數： "<<n<<" 缺頁率： "<<n/m<<endl<<endl;if(c=2)/LRU 頁面置換n=0;cout<<" LRU 算法頁面置換情況如下 : "<<endl; cout<<endl;

13、while(i<m)int a;t=Search(pi.num,page);if(t>=0)/ 如果已在內存塊中 paget.time=0;/ 把與它相同的內存塊的時間置 0 for(a=0;a<M;a+)if(a!=t)pagea.time+;/ 其它的時間加 1 cout<<pi.num<<" "cout<<" 不缺頁 "<<endl;else / 如果不在內存塊中n+; / 缺頁次數加 1t=Max(page); / 返回最近最久未使用的塊號賦值給 t paget.num=pi.nu

14、m ; /進行替換paget.time=0; / 替換后時間置為 0 cout<<pi.num<<" "print(page);for(a=0;a<M;a+)if(a!=t) pagea.time+; /其它的時間加 1i+;cout<<endl;cout<<" 缺頁次數： "<<n<<" 缺頁率： "<<n/m<<endl<<endl;if(c=3)/OPT 頁面置換n=0;cout<<" OPT

15、算法置換情況如下 :"<<endl;cout<<endl;while(i<m)if(Search(pi.num,page)>=0)/ 如果已在內存塊中 cout<<pi.num<<" "cout<<" 不缺頁 "<<endl;i+;else/ 如果不在內存塊中int a=0;for(t=0;t<M;t+)if(paget.num=0)a+;/ 記錄空的內存塊數 if(a!=0) / 有空內存int q=M;for(t=0;t<M;t+)if(page

16、t.num=0&&q>t)q=t;/ 把空內存塊中塊號最小的找出來pageq.num=pi.num;n+; cout<<pi.num<<" " print(page);i+; else最久的頁面int temp=0,s;for(t=0;t<M;t+)/ 尋找內存塊中下次使用離現在if(temp<Count(page,i,t,p) temp=Count(page,i,t,p);s=t; / 把找到的塊號賦給 spages.num=pi.num;n+;cout<<pi.num<<" &q

17、uot; print(page);i+;cout<<endl;cout<<" 缺頁次數： "<<n<<" 缺頁率： "<<n/m<<endl<<endl; if(c = 4) break;while(c=1|c=2|c=3);return 0;五、實驗結果5.1 程序主界面運行程序后，將會提示用戶輸入頁面長度，長度在10到20之間。當用戶輸 入長度（以12為例）后，系統將會顯示隨機數。系統提示用戶輸入分配的物理 塊，用戶輸入數據（以3為例）。程序主界面運行圖如圖5-1所示

18、。請輸入頁面長度1020： 12輸出隨機數：請輸入分配的物理塊26?:圖5-1程序主界面5.2先進先出（FIFO）頁面置換算法運行結果選擇算法1之后，進入算法1的操作。系統會顯示算法的頁面置換情況 先來先服務算法的運行圖如圖5-2所示。"FIFO頁面真換 2：LRU頁面置換 ©RPT頁宙置拉心退出 字選擇頁面議算袪.F FIFO算法頁面宜換情況如下：2 0 92 10不缺頁2 159 159 8 &? e e6 E 06 106 13不缺頁2 13晴頁次數：l四缺帀率：0.833333圖5-2先進先出頁面置換算法運行結果圖5.3最近久未使用（LRU）置換算法運行結果選擇算法2之后，進入算法2的操作。系統會顯示算法的頁面置換情況最近久未使用的運行圖如圖5-3所示。1 z 卩2頁面軍換 2 : LRU頁面直換 22PT頁面置桶 4：退岀請選擇頁面HW袪 刖算迭頁面置換情況如下22 2 0 012 100不缺頁5 5 109 5 9 08 S ? Sa a ? s6 9 6 910 6 13 3 6 1不缺頁2 3 2 1朕頁次數=10缺頁率：0-833333圖5-3最近久未