页面置换算法的模拟实现及命中率对比实验报告

页面置换算法的模拟实现及命中率对比实验报告一、问题描述课程设计目的（1）、通过请求页式管理方式中页面置换算法的模拟设计，了解虚拟存储术的特点，掌握请求页式存储管理中的页面置换算法。（2）、课程设计内容模拟实现OPT（最佳置换）、FIFO和LRU算法，并计算命中率。（3）、课程设计要求：a)首先用随机数生成函数产生“指令”序列，然后将指令序列变换成相应的页地址流，再计算不同算法下的命中率。b)通过随机数产生一个指令序列，共产生400条。其中50%的指令是顺序执行的（灵位50%就是非顺序），且25%的指令分布在前半部分地址空间，25%的指令分布在后半部分地址空间。c)将指令地址流变换成页地址流d)循环运行，使用户内存容量从4到40,。计算每个内存容量下不同页面置换算法的命中率。二、概要设计1.程序的数据结构：#definetotal_instruction100/*指令流长*/#defineM100/*实际页数*/#defineN5//可用页面数structPro{intnum,time;};inta[total_instruction];intpage[N];2.程序的主函数：intmain(){Prop[total_instruction];Pro*page=newPro[N];charc;intt=0,i;floatn=0;Input(p);do{for(i=0;iN;i++)//初试化页面基本情况{page[i].num=-1;page[i].time=2-i;}printf(系统产生的随机数为：);for(inte=0;eM;e++)coutp[e].num;coutendl;i=0;coutf:FIFO页面置换endl;coutl:LRU页面置换endl;couto:OPT页面置换endl;cout按其它键结束endl;cinc;if(c=='f')//FIFO页面置换{n=0;cout页面置换情况:endl;while(itotal_instruction){if(Search(p[i].num,page)=0)i++;//找到相同的页面else{if(t==N)t=0;else{n++;//page[t].num=p[i].num;print(page);t++;}}}cout缺页次数：n命中率：1-n/total_instructionendl;}if(c=='l')//LRU页面置换{n=0;cout页面置换情况:endl;while(itotal_instruction){intk;k=t=Search(p[i].num,page);if(t=0)page[t].time=0;else{n++;t=Max(page);page[t].num=p[i].num;page[t].time=0;}for(intj=0;jN;j++){if(j!=t)page[j].time++;}/*if(t==0){page[t+1].time++;page[t+2].time++;}if(t==1){page[2].time++;page[0].time++;}if(t==2){page[1].time++;page[0].time++;}*/if(k==-1)print(page);i++;}cout缺页次数：n命中率：1-n/total_instructionendl;}if(c=='o')//OPT页面置换{n=0;while(itotal_instruction){if(Search(p[i].num,page)=0)i++;else{if(page[N-1].num==-1){for(intg=0;gN;g++)if(page[g].num==-1){page[g].num=p[i].num;i++;n++;print(page);break;}}else{inttemp=-1,cn;for(t=0;tN;t++){if(tempCompfu(page,i,t,p)){temp=Compfu(page,i,t,p);cn=t;}}page[cn]=p[i];n++;print(page);i++;}}}cout缺页次数：n命中率：1-n/total_instructionendl;}}while(c=='f'||c=='l'||c=='o');return0;}三、详细设计程序代码如下：#includestdlib.h#includeiostream#includetime.h#includestdio.husingnamespacestd;#definetotal_instruction100/*指令流长*/#defineM100/*实际页数*/#defineN5//可用页面数structPro{intnum,time;};inta[total_instruction];intpage[N];voidInput(Prop[total_instruction]){intm,i,m1,m2;srand((unsignedint)time(NULL));m=rand()%400;//for(i=0;itotal_instruction;)/*产生指令队列*/{if(m0||m399){printf(Wheni==%d,Error,m==%d\n,i,m);exit(0);}a[i]=m;/*任选一指令访问点m*/a[i+1]=a[i]+1;a[i+2]=a[i]+2;/*顺序执行两条指令*/intm1=rand()%m;/*执行前地址指令m1*/a[i+3]=m1;a[i+4]=m1+1;a[i+5]=m1+2;/*顺序执行两条指令*///s=(158-a[i+5])*rand()/32767/32767/2+a[i+5]+2;m2=rand()%(157-m1)+m1+3;a[i+6]=m2;if((m2+2)159){a[i+7]=m2+1;i+=8;}else{a[i+7]=m2+1;a[i+8]=m2+2;i=i+9;}m=rand()%m2;}for(i=0;itotal_instruction;i++)/*将指令序列变换成页地址流*/{p[i].num=a[i]/10;p[i].time=0;}}voidprint(Pro*page1)//打印当前的页面{Pro*page=newPro[N];page=page1;for(inti=0;iN;i++)printf(%-4d,page[i].num);//coutpage[i].num;coutendl;//free(page);}intSearch(inte,Pro*page1){Pro*page=newPro[N];page=page1;for(inti=0;iN;i++)if(e==page[i].num)returni;return-1;}intMax(Pro*page1){Pro*page=newPro[N];page=page1;inte=page[0].time,i=0;while(iN)//找出离现在时间最长的页面{if(epage[i].time)e=page[i].time;i++;}for(i=0;iN;i++)if(e==page[i].time)returni;return-1;}intCompfu(Pro*page1,inti,intt,Prop[M]){Pro*page=newPro[N];page=page1;intcount=0;for(intj=i;jM;j++){if(page[t].num==p[j].num)break;elsecount++;}returncount;}intmain(){Prop[total_instruction];Pro*page=newPro[N];charc;intt=0,i;floatn=0;Input(p);do{for(i=0;iN;i++)//初试化页面基本情况{page[i].num=-1;page[i].time=2-i;}printf(系统产生的随机数为：);for(inte=0;eM;e++)coutp[e].num;coutendl;i=0;coutf:FIFO页面置换endl;coutl:LRU页面置换endl;couto:OPT页面置换endl;cout按其它键结束endl;cinc;if(c=='f')//FIFO页面置换{n=0;cout页面置换情况:endl;while(itotal_instruction){if(Search(p[i].num,page)=0)i++;//找到相同的页面else{if(t==N)t=0;else{n++;//page[t].num=p[i].num;print(page);t++;}}}cout缺页次数：n命中率：1-n/total_instructionendl”}if(c=='l')//LRU页面置换{n=0;cout页面置换情况:endl;while(itotal_instruction){intk;k=t=Search(p[i].num,page);if(t=0)page[t].time=0;else{n++;t=Max(page);page[t].num=p[i].num;page[t].time=0;}for(intj=0;jN;j++){if(j!=t)page[j].time++;}/*if(t==0){page[t+1].time++;page[t+2].time++;}if(t==1){page[2].time++;page[0].time++;}if(t==2){page[1].time++;page[0].time++;}*/if(k==-1)print(page);i++;}cout缺页次数：n命中率：1-n/total_instructionendl;}if(c=='o')//OPT页面置换{n=0;while(itotal_instruction){if(Search(p[i].num,page)=0)i++;else{if(page[N-1].num==-1){for(intg=0;gN;g++)if(page[g].num==-1){page[g].num=p[i].num;i++;n++;print(page);break;}}else{inttemp=-1,cn;for(t=0;tN;t++){if(tempCompfu(page,i,t,p)){temp=Compfu(page,i,t,p);cn=t;}}page[cn]=p[i];n++;print(page);i++;}}}cout缺页次数：n命中率：1-n/total_instructionendl;}}while(c=='f'||c=='l'||c=='o');return0;}四、调试与分析程序的主界面：这里测试用的数据是M=40，N=5，三种算法置换结果如以下的图：FIFO算法：LRU算法：OPT算法：多运行几次，产生不同的随机数组，查看对比结果。在某一次实验中，可能FIFO算法的命中率比LRU算法要高，但经过多组测试数据及总体的结果表明：LRU的平均性能比FIFO的平均性能好。