1、實驗五 虛擬內存頁面置換算法一、 需求分析11.輸入的形式和輸入值的范圍22.輸出的形式23.程序所能達到的功能34.測試數據4二、 概要設計51.抽象數據類型的定義52.主程序的流程63.程序各模塊之間的層次(調用)關系7三、 詳細設計71.void FIFO()72.void OPI()83.void LRU()10四、 調試分析111.發現的問題112.算法的性能分析(包括基本操作和其它算法的時間復雜度和空間復雜度的分析)及其改進設想；113.解決方法114.經驗和體會12五、用戶使用說明12六、測試結果12七附錄14一、 需求分析l 需求在進程運行過程中，若其所訪問的頁面不在內存而需把

2、它們調入內存，但內存已無空閑空間時，為了保證該進程能正常運行，系統必須從內存調出一頁程序或數據送磁盤的對換區中。但應將哪個頁面調出，需根據一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法。置換算法的好壞，將直接影響到系統的性能。一個好的頁面置換算法，應具有較低的更好頻率。從理論上講，應將那些以后不再訪問的頁面換出，或把那些在較長時間內不再訪問的頁面調出。l 實驗目的通過這次實驗，加深對虛擬內存頁面置換概念的理解，進一步掌握先進先出FIFO、最佳置換OPI和最近最久未使用LRU頁面置換算法的實現方法。l 實驗內容設計程序模擬先進先出FIFO、最佳置換OPI和最近最久未使用LRU頁面置

3、換算法的工作過程。假設內存中分配給每個進程的最小物理塊數為m，在進程運行過程中要訪問的頁面個數為n，頁面訪問序列為P1, ,Pn，分別利用不同的頁面置換算法調度進程的頁面訪問序列，給出頁面訪問序列的置換過程，計算每種算法缺頁次數和缺頁率。l 程序要求1）利用先進先出FIFO、最佳置換OPI和最近最久未使用LRU三種頁面置換算法模擬頁面訪問過程。2）模擬三種算法的頁面置換過程，給出每個頁面訪問時的內存分配情況。3）輸入：最小物理塊數m，頁面個數n，頁面訪問序列P1, ,Pn，算法選擇1-FIFO，2-OPI，3-LRU。4）輸出：每種算法的缺頁次數和缺頁率。1.輸入的形式和輸入值的范圍從dos控

4、制臺界面按照輸入提示輸入數據（紅色的數字即為輸入的內容）：物理塊(LackNum)：3頁號數（PageNum）：20頁面序列(PageOrder)：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1進程的最大頁號數為100，物理塊、頁面序列的值為int類型的范圍。2.輸出的形式輸入數據后，按ENTER鍵就可在dos控制臺界面得到結果。按照實驗要求分別輸出程序模擬先進先出FIFO、最佳置換OPI和最近最久未使用LRU頁面置換算法的工作過程。結果如下：首行是算法的名稱，第二行是頁號序列，接下來的3行數字是模仿物理塊的情況，豎著看才是正確的結果，此圖顯示的是3塊物理塊時內

5、存占用情況。之后顯示缺頁次數和缺頁率。3.程序所能達到的功能程序模擬先進先出FIFO、最佳置換OPI和最近最久未使用LRU頁面置換算法的工作過程。假設內存中分配給每個進程的最小物理塊數為m，在進程運行過程中要訪問的頁面個數為n，頁面訪問序列為P1, ,Pn，分別利用不同的頁面置換算法調度進程的頁面訪問序列，給出頁面訪問序列的置換過程，計算每種算法缺頁次數和缺頁率。4.測試數據二、 概要設計1.抽象數據類型的定義 程序中進程調度時間變量描述如下： const int MaxNumber=100; int PageOrderMaxNumber; int SimulateMaxNumberMaxNu

6、mber;int PageCountMaxNumber;int PageNum,LackNum;double LackPageRate;bool found;主要函數：void print();void init();void original();void FIFO();void OPI();void LRU();2.主程序的流程 3.程序各模塊之間的層次(調用)關系三、 詳細設計1.void FIFO()original();Simulate00=PageOrder0;int temp=0,flag=0;for(i=1;i<PageNum;i+) /判斷該頁面是否存在內存中for(j

7、=0;j<BlockNum;j+)if(PageOrderi=Simulateflagj)break; if(j=BlockNum)/該頁面不在內存中for(k=0;k<BlockNum;k+)/模擬置換過程 if(Simulateflagk=NULL) break; else Simulateik=Simulateflagk;/淘汰最先進入內存的頁面temp+;temp=temp%BlockNum;Simulateitemp=PageOrderi;LackNum+;flag=i;/該頁面在內存中elsecontinue;2.void OPI()original();Simulat

8、e00=PageOrder0;int temp,flag=0;/flag表示上一個模擬內存的下標for(i=1;i<PageNum;i+) /判斷該頁面是否存在內存中for(j=0;j<BlockNum;j+)if(PageOrderi=Simulateflagj)break; /j!=BlockNum表示該頁面已經在內存中if(j!=BlockNum)continue;/模擬置換過程for(k=0;k<BlockNum;k+) if(Simulateflagk=NULL) break; else Simulateik=Simulateflagk;/內存中頁面進行選擇/兩種情

9、況：內存已滿和內存未滿for(j=0;j<BlockNum;j+)if(Simulateij=NULL)Simulateij=PageOrderi;LackNum+; flag=i;break;if(j!=BlockNum)/內存未滿continue;/內存已滿temp=0;/temp表示要置換的頁面內存下標 for(j=0;j<BlockNum;j+)/選取要置換的頁面內存下標for(k=i+1;k<PageNum;k+)/最長時間內不被訪問的頁面 if(Simulateij=PageOrderk) PageCountj=k;break; if(k=PageNum)/之后沒

10、有進行對該頁面的訪問PageCountj=PageNum;if(PageCounttemp<PageCountj)temp=j;Simulateitemp=PageOrderi;LackNum+;flag=i; 3.void LRU()original();Simulate00=PageOrder0;int temp,flag=0;/flag表示上一個模擬內存的下標PageCount0=0;/最近的頁面下標for(i=1;i<PageNum;i+) /判斷該頁面是否存在內存中for(j=0;j<BlockNum;j+)if(PageOrderi=Simulateflagj)P

11、ageCountj=i;break; /j!=BlockNum表示該頁面已經在內存中if(j!=BlockNum)continue;/模擬置換過程for(k=0;k<BlockNum;k+) if(Simulateflagk=NULL) break; else Simulateik=Simulateflagk;/內存中頁面進行選擇/兩種情況：內存已滿和內存未滿for(j=0;j<BlockNum;j+)if(Simulateij=NULL)/內存未滿Simulateij=PageOrderi;PageCountj=i;LackNum+; flag=i;break;if(j!=Blo

12、ckNum)continue;/內存已滿temp=0;/temp表示要置換的頁面內存下標 for(j=0;j<BlockNum;j+)/最近最久時間內不被訪問的頁面if(PageCounttemp>PageCountj)temp=j; Simulateitemp=PageOrderi;PageCounttemp=i;LackNum+;flag=i;四、 調試分析1.發現的問題在編寫程序的最初，界面不是很好，看著很亂。最后求的缺頁率也不是用百分數表示。2.算法的性能分析(包括基本操作和其它算法的時間復雜度和空間復雜度的分析)及其改進設想；該程序的的時間復雜度還算理想，是O(m*n),

13、空間復雜度也是一樣，復雜度為O(m*n),均不需要再改進了。 3.解決方法界面使用空格填充，使各行各列對齊。對于輸出百分數，將缺頁率乘以100，后加%輸出。4.經驗和體會通過二次編程，又一次加深了對先進先出（FIFO）頁面置換算法，最佳（OPI）置換算法，最近最久未使用（LRU）置換算法的理解。同時，也掌握了一些使界面輸出看起來更工整的辦法。還有，在平時做作業的時候，總是默認為物理塊數是3，其實只是比較常用而已，并不是每次都是3.這個在編程中有體現，在今后做題中會更注意。五、用戶使用說明(1)用戶根據提示輸入物理塊數(2)輸入頁面個數(3)依次輸入頁面訪問個數(4)根據提示選擇算法，輸入對應的

14、數字。六、測試結果列出測試結果，包括輸入和輸出。七附錄#include<iostream>#include<iomanip>using namespace std;const int MaxNumber=100;int PageOrderMaxNumber;/頁面序列P1, ,Pn，int SimulateMaxNumberMaxNumber;/模擬頁面置換過程int PageCountMaxNumber;/int PageNum,LackNum;/頁面數，缺頁數double LackPageRate;/缺頁率bool found;int BlockNum;int i,

15、j,k;void print();void init();void original();void FIFO();void OPI();void LRU();void main()/cout<<setw(2)<<" "init();bool d=true;while(d)cout<<"算法選擇n FIFO: 輸入'1'n OPI: 輸入'2'n LRU: 輸入'3'n exit: 輸入'4'n" int c; cin>>c; switch(c)

16、 case 1:cout<<endl<<"先進先出FIFO頁面置換算法：n" FIFO(); print(); break; case 2:cout<<endl<<"最佳頁面OPI置換算法：n" OPI(); print(); break; case 3:cout<<endl<<"最近最久未使用LRU置換算法：n" LRU(); print(); break; case 4: d=false; break; default: cout<<"你

17、的輸入有問題請重新輸入！n" break;void init()cout<<"物理塊數m: "cin>>BlockNum;cout<<"頁面個數n: "cin>>PageNum;cout<<"頁面訪問序列P1, ,Pnn"for(i=0;i<PageNum;i+)cin>>PageOrderi;void original()for(i=0;i<PageNum;i+)for(j=0;j<BlockNum;j+)Simulateij=NUL

18、L;LackNum=1;void print()/模擬三種算法的頁面置換過程，/給出每個頁面訪問時的內存分配情況/每種算法的缺頁次數和缺頁率。LackPageRate=(double)LackNum/PageNum;for(i=0;i<PageNum;i+)cout<<setw(4)<<"-"for(i=0;i<PageNum;i+)cout<<setw(4)<<PageOrderi;for(i=0;i<PageNum;i+)cout<<setw(4)<<"-"fo

19、r(j=0;j<BlockNum;j+) /for(i=0;i<PageNum;i+)/cout<<setw(4)<<"-"for(i=0;i<PageNum;i+)if(Simulateij=NULL)cout<<setw(4)<<' 'else cout<<setw(4)<<Simulateij; cout<<endl;/cout<<endl; cout<<"缺頁次數:"<<LackNum<&

20、lt;endl<<"缺頁率:"<<LackPageRate*100<<"%"<<endl<<endl;void FIFO()/先進先出:最早出現的置換算法，總是淘汰最先進入內存的頁面。original();Simulate00=PageOrder0;int temp=0,flag=0;for(i=1;i<PageNum;i+) /判斷該頁面是否存在內存中for(j=0;j<BlockNum;j+)if(PageOrderi=Simulateflagj)break; if(j=Bloc

21、kNum)/該頁面不在內存中for(k=0;k<BlockNum;k+)/模擬置換過程 if(Simulateflagk=NULL) break; else Simulateik=Simulateflagk;/淘汰最先進入內存的頁面temp+;temp=temp%BlockNum;Simulateitemp=PageOrderi;LackNum+;flag=i;/該頁面在內存中elsecontinue;void OPI()/最佳置換:選擇的被淘汰的頁面都是以后永不使用或者在最長（未來）時間內不被訪問的頁面。original();Simulate00=PageOrder0;int temp

22、,flag=0;/flag表示上一個模擬內存的下標for(i=1;i<PageNum;i+) /判斷該頁面是否存在內存中for(j=0;j<BlockNum;j+)if(PageOrderi=Simulateflagj)break; /j!=BlockNum表示該頁面已經在內存中if(j!=BlockNum)continue;/模擬置換過程for(k=0;k<BlockNum;k+) if(Simulateflagk=NULL) break; else Simulateik=Simulateflagk;/內存中頁面進行選擇/兩種情況：內存已滿和內存未滿for(j=0;j<

23、;BlockNum;j+)if(Simulateij=NULL)Simulateij=PageOrderi;LackNum+; flag=i;break;if(j!=BlockNum)/內存未滿continue;/內存已滿temp=0;/temp表示要置換的頁面內存下標 for(j=0;j<BlockNum;j+)/選取要置換的頁面內存下標for(k=i+1;k<PageNum;k+)/最長時間內不被訪問的頁面 if(Simulateij=PageOrderk) PageCountj=k;break; if(k=PageNum)/之后沒有進行對該頁面的訪問PageCountj=PageNum;if(PageCountt