1、操作系統原理實驗報告實驗三 頁面置換算法實驗專業：計算機科學與技術學號： 030840204姓名：簡鄲 實驗日期： 2010-5-22一、實驗目的通過模擬實現請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬存儲技術的特點，掌握虛擬存儲請求 頁式存儲管理中幾種基本頁面置換算法的基本思想和實現過程，并比較它們的效率。二、實驗要求設計一個虛擬存儲區和內存工作區，并使用下述算法計算訪問命中率O1 .最佳淘汰算法(OPT )2 .先進先出的算法(FIFO)3 .最近最久未使用算法(LRU)三、實驗方法內容1.算法設計思路1 .假設分給一作業白內存塊數為4 ,每條指令占一個存儲單元， 每個頁面中可存放 1

2、0條指令；160條指令，即它的地址空間2 .設計一個程序，模擬一作業的執行過程。設該作業共有為16頁，最初作業的所有頁面都還未調入內存。在模擬過程中，如果所訪問的指令已經在內存，則顯示其物理地址，并轉下一條指令。如果所訪問的指令尚未裝入內存，則發生缺頁,此時需記錄缺頁的次數，并將相應頁調入內存。如果4個內存塊中均已裝入該作業的虛頁面，則需進行頁面置換；在所有 160條指令執行完畢后，請計算并顯示作業運行過程中發 生的缺頁率。3 .作業中指令的訪問次序要求按下述原則生成：具體的實施辦法是：(1)在0, 159之間隨機選取一條起始執行指令，其序號為m ;(2)順序執行兩條指令，即序號為(3)通過隨

3、機數，跳轉到前地址部分(4)順序執行兩條指令，即序號為(5)通過隨機數，跳轉到后地址部分(6)順序執行兩條指令，即序號為m+1、m+2的指令；0, m-1中的某條指令處，其序號為m1 ;m1+1 , m1+2 的指令；m1+3 ,159中的某條指令處，其序號為 m2 ;m2+1 , m2+2的指令；若 m2+2159只執行一條指令;”的過程，直至執行(7)重復跳轉到前地址部分、順序執行、跳轉到后地址部分、順序執行 完全部160條指令4 .算法流程圖5 .算法中用到的數據結構6 .主要的常量變量7 .主要模塊四、實驗代碼#include#include#include#include#defin

4、e total_instruction 200/*指令流長 */#define M 16/* 實際頁數*/#define N 4/可用頁面數struct Proint num,time;int atotal_instruction;int pageN;void Input(Pro ptotal_instruction)int m,i,m1,m2;srand( (unsigned int )time(NULL);m=rand( )%160;/for(i=0;itotal_instruction;) /* 產生指令隊列 */if(m159)printf(When i=%d,Error,m=%dn,

5、i,m);exit(0);ai=m;/*任選一指令訪問點 m*/ai+1=ai+1;ai+2=ai+2;/*順序執行兩條指令*/int m1=rand( )%m; /* 執行前地址指令m1 */ai+3=m1;ai+4=m1+1;ai+5=m1 + 2;/* 順序執行兩條指令*/ s=(158-ai+5)*rand( )/32767/32767/2+ai+5+2;m2 = rand()%(157-m1)+m1+3;ai+6=m2;if( (m2+2) 159 )ai+7 = m2+1;i +=8;elseai+7 = m2+1;ai+8 = m2+2;i = i+9;m = rand()%m2

6、;for (i=0;itotal_instruction;i+) /* 將指令序列變換成頁地址流*/pi.num=ai/10;pi.time = 0;void print(Pro *page1)/ 打印當前的頁面Pro *page=new ProN;page=page1;for(int i=0;iN;i+) coutpagei.num ;coutendl;int Search(int e,Pro *page1 )Pro *page=new ProN;page=page1;for(int i=0;iN;i+)if(e=pagei.num)return i;return -1;int Max(Pr

7、o *page1)Pro *page=new ProN;page=page1;int e=page0.time,i=0;while(iN)/ 找出離現在時間最長的頁面if(epagei.time)e=pagei.time;i+;for( i=0;iN;i+)if(e=pagei.time)return i;return -1;int Compfu(Pro *page1,int i,int t,Pro pM)Pro *page=new ProN;page=page1;int count=0;for(int j=i;jM;j+)if(paget.num=pj.num )break;else cou

8、nt+;return count;int main()Pro ptotal_instruction;Pro *page=new ProN;char c;int t=0;float n=0;Input(p);dofor(int i=0;iN;i+)/ 初試化頁面基本情況pagei.num=0;pagei.time=2-i;i=0;coutf:FIFO 頁面置換 endl;coutl:LRU 頁面置換endl;couto:OPT 頁面置換endl;cout 按其它鍵結束c;if(c=f)/FIFO 頁面置換n=0;cout 頁面置換情況: endl;while( i=0)i+;/ 找到相同的頁面e

9、lseif(t=N)t=0;elsen+;/paget.num=pi.num;print(page);t+;cout 缺頁次數： n 缺頁率： n/total_instructionendl;if(c=l)/LRU 頁面置換n=0;cout頁面置換情況：endl; while(i=0)paget.time=0; else ( n+;t=Max(page);paget.num=pi.num;paget.time=0;if(t=0)paget+1.time+;paget+2.time+;if(t=1)page2.time+;page0.time+; if(t=2)page1.time+;page0.time+; if(k=-1) print(page);i+;cout缺頁次數：n 缺頁率：n/total_instructionendl; if(c=o)OPT 頁面置換 n=0;while(i=0)i+; else int temp=0,cn;for(t=0;tN;t+) if(tempCompfu(page,i,t,p) temp=Compfu(page,i,t,p); cn=t; page