资源描述
页面置换算法的模拟实现及命中率对比实验报告一、问题描述课程设计目的（1）、通过请求页式管理方式中页面置换算法的模拟设计，了解虚拟存储 术的特点，掌握请求页式存储管理中的页面置换算法。 （2）、课程设计内容模拟实现OPT（最佳置换）、FIFO和LRU算法，并计算命中率。（3） 、课程设计要求：a) 首先用随机数生成函数产生“指令”序列，然后将指令序列变换成相应的页地址流，再计算不同算法下的命中率。b) 通过随机数产生一个指令序列，共产生400条。其中50%的指令是顺序执行的（灵位50%就是非顺序），且25%的指令分布在前半部分地址空间，25%的指令分布在后半部分地址空间。c) 将指令地址流变换成页地址流d) 循环运行，使用户内存容量从4到40,。计算每个内存容量下不同页面置换算法的命中率。二、概要设计 1.程序的数据结构： #define total_instruction 100 /*指令流长*/#define M 100 /*实际页数*/#define N 5 /可用页面数struct Pro int num,time;int atotal_instruction;int pageN;2.程序的主函数：int main() Pro ptotal_instruction; Pro *page=new ProN; char c; int t=0,i; float n=0; Input(p); do for( i=0;iN;i+)/初试化页面基本情况 pagei.num=-1; pagei.time=2-i; printf(系统产生的随机数为：); for(int e=0;eM;e+) coutpe.num ; coutendl; 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+;/找到相同的页面 else if(t=N)t=0; else n+;/ paget.num=pi.num; print(page); t+; cout缺页次数：n 命中率：1-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; for(int j=0;jN;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缺页次数：n 命中率：1-n/total_instructionendl; if(c=o)/OPT页面置换 n=0; while(i=0)i+; else if(pageN-1.num=-1) for(int g=0;gN;g+) if(pageg.num=-1) pageg.num=pi.num; i+; n+; print(page); break; else int temp=-1,cn; for(t=0;tN;t+) if(tempCompfu(page,i,t,p) temp=Compfu(page,i,t,p); cn=t; pagecn=pi; n+; print(page); i+; cout缺页次数：n 命中率：1-n/total_instructionendl; while(c=f|c=l|c=o); return 0;三、详细设计程序代码如下：#include#include#include#includeusing namespace std;#define total_instruction 100 /*指令流长*/#define M 100 /*实际页数*/#define N 5 /可用页面数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;itotal_instruction;) /*产生指令队列*/ if(m399) printf(When i=%d,Error,m=%dn,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; else ai+7 = m2+1; ai+8 = m2+2; i = i+9; m = rand()%m2; 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+) printf(%-4d,pagei.num); /coutpagei.num ; coutendl; /free(page);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(Pro *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 count+; return count;int main() Pro ptotal_instruction; Pro *page=new ProN; char c; int t=0,i; float n=0; Input(p); do for( i=0;iN;i+)/初试化页面基本情况 pagei.num=-1; pagei.time=2-i; printf(系统产生的随机数为：); for(int e=0;eM;e+) coutpe.num ; coutendl; 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+;/找到相同的页面 else if(t=N)t=0; else n+;/ paget.num=pi.num; print(page); t+; cout缺页次数：n 命中率：1-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; for(int j=0;jN;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缺页次数：n 命中率：1-n/total_instructionendl; if(c=o)/OPT页面置换 n=0; while(i=0)i+; else if(pageN-1.num=-1) for(int g=0;gN;g+) if(pageg.num=-1) pageg.num=pi.num; i+; n+; print(page); break; else int temp=-1,cn; for(t=0;tN;t+) if(tempCompfu(page,i,t,p) temp=Compfu(page,i,t,p); cn=t; pagecn=pi; n+; print(page); i+; cout缺页次数：n 命中率：1-n/total_instructionendl; while(c=f|c=l|c=o); return 0;四、调试与分析程序的主界面：这里测试用的数据是M=40，N=5，三种算法置换结果如以下的图：FIFO算法：LRU算法：OPT算法：多运行几次，产生不同的随机数组，查看对比结果。在某一次实验中，可能FIFO算法的命中率比LRU算法要高，但经过多组测试数据及总体的结果表明：LRU的平均性能比FIFO的平均性能好。
展开阅读全文