面置換算法的模擬實(shí)現(xiàn)及命中率對(duì)比試驗(yàn)報(bào)告

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

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

3、put(p);dofor( i=O;ivN;i+)初試化頁面基本情況(pagei.num=-1;pagei.time=2-i;)printf("系統(tǒng)產(chǎn)生的隨機(jī)數(shù)為：”)；for(int e=O;e<M;e+)cout«pe.num«" cout«endl;i=0;coutvv'fFIFO 頁面置換"«endl;coutvv'tLRU 頁面置換"«endl;coutvv”o:OPT頁面置換"«endl;coutvv”按其它鍵結(jié)束"«endl;ci

4、n»c;if(c='f)/FIFO 頁面置換(n=0;coutvv'頁面置換情況："«endl;while( i< totaljnstruction) .if(Search(pi.num,page)>=0)i+; 找到相同的頁面else( if(t=N)t=O; else ( n+;/ paget.num=pi.num; print(page);t+；)coutvv'缺頁次數(shù)："«n«"命中率："«1-n/total_instruction«endl;)if(

5、c=T)/LRU 頁面置換(n=0;cout<<"頁面置換情況："<<endl;while(i<total_instruction)(int k;k=t=Search(pi.num,page);if(t>=0)paget.time=0;elsen+;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+;page

6、0.time+; if(t=2)page1.time+;page0.time+;*/ if(k=-1) print(page); i+;cout<<”缺頁次數(shù)："<<n<<" 命中率："<<1-n/total_instruction<<endl;if(c='o')/OPT 頁面置換n=0;while(i<total_instruction)if(Search(pi.num,page)>=0)i+;elseif(pageN-1.num=-1) for(int g=0;g<N

7、;g+) if(pageg.num=-1)pageg.num=pi.num;i+;n+;print(page);break;elseint 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ù)："<<n<<"命中率："<<1-n/total_instruction<<endl;while(c='f&#

8、39;|c='l'|c='o');return 0;三、詳細(xì)設(shè)計(jì)程序代碼如下：#include<stdlib.h>#include<iostream>#include<time.h>#include<stdio.h>using namespace std;# define total_instruction 100/* 指令流長(zhǎng)*/# define M 100/* 實(shí)際頁數(shù)*/# define N 5/可用頁面數(shù)struct Proint num,time;int atotal_instruction;int pa

9、geN;void Input(Pro ptotal_instruction)int m,i,m1,m2;srand( (unsigned int )time(NULL);m=rand( )%400; /for(i=0;i<total_instruction;) /* 產(chǎn)生指令隊(duì)列*/if(m<0|m>399)printf("When i=%d,Error,m=%dn",i,m);exit(0);ai=m;/* 任選一指令訪問點(diǎn)m*/ai+1=ai+1;ai+2=ai+2;/* 順序執(zhí)行兩條指令*/int m1=rand( )%m; /*執(zhí)行前地址指令m1

10、*/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)+m1+3;ai+6=m2;if( (m2+2) > 159 )ai+7 = m2+1;1 +=8;elseai+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(P

11、ro *page1)/ 打印當(dāng)前的頁面Pro *page=new ProN;page=page1;for(int i=0;i<N;i+)printf("%-4d",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

12、(Pro *page1)Pro *page=new ProN;page=page1;int e=page0.time,i=0;while(i<N)找出離現(xiàn)在時(shí)間最長(zhǎng)的頁面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.nu

13、m )break;else count+; return count;int main()Pro ptotal_instruction;Pro *page=new ProN;char c;int t=0,i;float n=0;Input(p);dofor( i=0;i<N;i+)/初試化頁面基本情況pagei.num=-1;pagei.time=2-i;printf(" 系統(tǒng)產(chǎn)生的隨機(jī)數(shù)為：");for(int e=0;e<M;e+) cout<<pe.num<<" "cout<<endl;i=0;cou

14、t<<"f:FIFO頁面置換"<<endl;cout<<"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(Sea

15、rch(pi.num,page)>=0)i+;找到相同的頁面elseif(t=N)t=0;elsen+;/paget.num=pi.num;print(page);t+;cout<<”缺頁次數(shù)："<<n<<" 命中率："<<1-n/total_instruction<<endlif(c=T)/LRU 頁面置換n=0;cout<<"頁面置換情況："<<endl;while(i<total_instruction)int k;k=t=Search(pi.

16、num,page);if(t>=0)paget.time=0;elsen+;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<<" 命中

17、率："<<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;)elseint 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ù)："<