1、精選優(yōu)質(zhì)文檔-傾情為你奉上頁面置換算法的模擬實現(xiàn)及命中率對比實驗報告一、問題描述課程設(shè)計目的（1）、通過請求頁式管理方式中頁面置換算法的模擬設(shè)計，了解虛擬存儲 術(shù)的特點，掌握請求頁式存儲管理中的頁面置換算法。 （2）、課程設(shè)計內(nèi)容模擬實現(xiàn)OPT（最佳置換）、FIFO和LRU算法，并計算命中率。（3） 、課程設(shè)計要求：a) 首先用隨機數(shù)生成函數(shù)產(chǎn)生“指令”序列，然后將指令序列變換成相應(yīng)的頁地址流，再計算不同算法下的命中率。b) 通過隨機數(shù)產(chǎn)生一個指令序列，共產(chǎn)生400條。其中50%的指令是順序執(zhí)行的（靈位50%就是非順序），且25%的指令分布在前半部分地址空間，25%的指令分布在后半部分地址空間

2、。c) 將指令地址流變換成頁地址流d) 循環(huán)運行，使用戶內(nèi)存容量從4到40,。計算每個內(nèi)存容量下不同頁面置換算法的命中率。二、概要設(shè)計 1.程序的數(shù)據(jù)結(jié)構(gòu)： #define total_instruction 100 /*指令流長*/#define M 100 /*實際頁數(shù)*/#define N 5 /可用頁面數(shù)struct Pro int num,time;int atotal_instruction;int pageN;2.程序的主函數(shù)：int main() Pro ptotal_instruction; Pro *page=new ProN; char c; int t=0,i; flo

3、at n=0; Input(p); do for( i=0;i<N;i+)/初試化頁面基本情況 pagei.num=-1; pagei.time=2-i; printf("系統(tǒng)產(chǎn)生的隨機數(shù)為："); for(int e=0;e<M;e+) cout<<pe.num<<" " cout<<endl; i=0; cout<<"f:FIFO頁面置換"<<endl; cout<<"l:LRU頁面置換"<<endl; cout&l

4、t;<"o:OPT頁面置換"<<endl; cout<<"按其它鍵結(jié)束"<<endl; cin>>c; if(c='f')/FIFO頁面置換 n=0; cout<<"頁面置換情況: "<<endl; while( i< total_instruction) if(Search(pi.num,page)>=0) i+;/找到相同的頁面 else if(t=N)t=0; else n+;/ paget.num=pi.num; prin

5、t(page); t+; cout<<"缺頁次數(shù)："<<n<<" 命中率："<<1-n/total_instruction<<endl; if(c='l')/LRU頁面置換 n=0; cout<<"頁面置換情況: "<<endl; while(i<total_instruction) int k; k=t=Search(pi.num,page); if(t>=0) paget.time=0; else n+; t=Max(p

6、age); paget.num=pi.num; paget.time=0; for(int j=0;j<N;j+) if(j!=t)pagej.time+; /*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<<"缺頁次數(shù)："<<n<<" 命中率："<<1-n/total_instruc

7、tion<<endl; if(c='o')/OPT頁面置換 n=0; while(i<total_instruction) if(Search(pi.num,page)>=0)i+; else if(pageN-1.num=-1) for(int g=0;g<N;g+) if(pageg.num=-1) pageg.num=pi.num; i+; n+; print(page); break; else int temp=-1,cn; for(t=0;t<N;t+) if(temp<Compfu(page,i,t,p) temp=Com

8、pfu(page,i,t,p); cn=t; pagecn=pi; n+; print(page); i+; cout<<"缺頁次數(shù)："<<n<<" 命中率："<<1-n/total_instruction<<endl; while(c='f'|c='l'|c='o'); return 0;三、詳細設(shè)計程序代碼如下：#include<stdlib.h>#include<iostream>#include<time.h&

9、gt;#include<stdio.h>using namespace std;#define total_instruction 100 /*指令流長*/#define M 100 /*實際頁數(shù)*/#define N 5 /可用頁面數(shù)struct Pro int num,time;int atotal_instruction;int pageN;void Input(Pro ptotal_instruction) int m,i,m1,m2; srand( (unsigned int )time(NULL); m=rand( )%400; / for(i=0;i<total

10、_instruction;) /*產(chǎn)生指令隊列*/ if(m<0|m>399) printf("When i=%d,Error,m=%dn",i,m); exit(0); ai=m; /*任選一指令訪問點m*/ ai+1=ai+1; ai+2=ai+2; /*順序執(zhí)行兩條指令*/ int m1=rand( )%m; /*執(zhí)行前地址指令m1 */ ai+3=m1; ai+4=m1+1; ai+5=m1 + 2;/*順序執(zhí)行兩條指令*/ / s=(158-ai+5)*rand( )/32767/32767/2+ai+5+2; m2 = rand()%(157-m1)

11、+m1+3; ai+6=m2; if( (m2+2) > 159 ) ai+7 = m2+1; i +=8; else ai+7 = m2+1; ai+8 = m2+2; i = i+9; m = rand()%m2; for (i=0;i<total_instruction;i+) /*將指令序列變換成頁地址流*/ pi.num=ai/10; pi.time = 0; void print(Pro *page1)/打印當(dāng)前的頁面 Pro *page=new ProN; page=page1; for(int i=0;i<N;i+) printf("%-4d&quo

12、t;,pagei.num); /cout<<pagei.num<<" " cout<<endl; /free(page);int Search(int e,Pro *page1 ) Pro *page=new ProN; page=page1; for(int i=0;i<N;i+)if(e=pagei.num)return i; return -1;int Max(Pro *page1) Pro *page=new ProN; page=page1; int e=page0.time,i=0; while(i<N)/找出離現(xiàn)

13、在時間最長的頁面 if(e<pagei.time)e=pagei.time; i+; for( i=0;i<N;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;j<M;j+) if(paget.num=pj.num )break; else count+; return count;int main() Pro ptotal_instruction;

14、Pro *page=new ProN; char c; int t=0,i; float n=0; Input(p); do for( i=0;i<N;i+)/初試化頁面基本情況 pagei.num=-1; pagei.time=2-i; printf("系統(tǒng)產(chǎn)生的隨機數(shù)為："); for(int e=0;e<M;e+) cout<<pe.num<<" " cout<<endl; i=0; cout<<"f:FIFO頁面置換"<<endl; cout<<

15、;"l:LRU頁面置換"<<endl; cout<<"o:OPT頁面置換"<<endl; cout<<"按其它鍵結(jié)束"<<endl; cin>>c; if(c='f')/FIFO頁面置換 n=0; cout<<"頁面置換情況: "<<endl; while( i< total_instruction) if(Search(pi.num,page)>=0) i+;/找到相同的頁面 else if

16、(t=N)t=0; else n+;/ paget.num=pi.num; print(page); t+; cout<<"缺頁次數(shù)："<<n<<" 命中率："<<1-n/total_instruction<<endl” if(c='l')/LRU頁面置換 n=0; cout<<"頁面置換情況: "<<endl; while(i<total_instruction) int k; k=t=Search(pi.num,page);

17、if(t>=0) paget.time=0; else n+; t=Max(page); paget.num=pi.num; paget.time=0; for(int j=0;j<N;j+) if(j!=t)pagej.time+; /*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<<"缺頁次數(shù)："<<n<<

18、" 命中率："<<1-n/total_instruction<<endl; if(c='o')/OPT頁面置換 n=0; while(i<total_instruction) if(Search(pi.num,page)>=0)i+; else if(pageN-1.num=-1) for(int g=0;g<N;g+) if(pageg.num=-1) pageg.num=pi.num; i+; n+; print(page); break; else int temp=-1,cn; for(t=0;t<N;t+) if(temp<Compfu(page,i,t,p) temp=Compfu(page,i,t,p); cn=t; pagecn=pi; n+; print(page); i+; cout<<"缺頁次數(shù)："<<