存储管理的模拟实现实验报告

南昌大学实验报告---（2）存储管理的模拟实现学生姓名：陈帅学号：8000111078专业班级：东软111班实验类型：□验证□综合■设计□创新实验日期：2013-0520实验成绩：一、实验目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。二、实验内容1．过随机数产生一个指令序列，共320条指令。其地址按下述原则生成：①50%的指令是顺序执行的；②25%的指令是均匀分布在前地址部分；③25%的指令是均匀分布在后地址部分；#具体的实施方法是：A.在[0，319]的指令地址之间随机选区一起点M;B.顺序执行一条指令，即执行地址为M+1的指令；C.在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’;D.顺序执行一条指令，其地址为M’+1；E.在后地址[M’+2，319]中随机选取一条指令并执行；F.重复A—E，直到执行320次指令。2．指令序列变换成页地址流设：（1）页面大小为1K；（1）用户内存容量为4页到32页；（2）用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条—第9条指令为第0页（对应虚存地址为[0，9]）；第10条—第19条指令为第1页（对应虚存地址为[10，19]）；。。。。。。。。。。。。。。。。。。。。。第310条—第319条指令为第31页（对应虚存地址为[310，319]）；按以上方式，用户指令可组成32页。3.计算并输出下述各种算法在不同内存容量下的命中率。A.FIFO先进先出的算法B.LRU最近最少使用算法C．LFU最少访问页面算法三、实验要求1、需写出设计说明；2、设计实现代码及说明3、运行结果；四、主要实验步骤1、分析算法结构；2、画出算法的流程图，即设计说明；3、根据画出的流程图使用C语言编写相应的代码（代码过长，放到最后）；程序主要由main函数和以下几个函数组成：voidinitialization();初始化内存数据voidFIFO();FIFO先进先出算法；voidLRU();LRU最久未使用算法；voidLFU();LFU最近最久未使用算法；4、检查代码，将编出的代码编译、链接，验证其正确性。开始按要求产生320个随机数将随机数转换成页面用户内存容量i=4i32?FIFO页面置换算法LRU页面置换算法LFU页面置换算法i=i+1结束NY页面置换算法整体结构开始内存数据初始化，物理块0mi中页面停留时间time[m]=m+1n=0用户内存中是否已存在要调用的页面用户内存中是否存在空物理块N将页面调入空物理块中，该物理块time[m]=0比较所有物理块的time[m]，找到最大值，将页面调入最大值所在物理块，该物理块time[m]=0所有已经存入页面的内存time[m]++，n++NYYn320?结束将页面p[n]调入内存YNFIFO页面置换算法开始内存数据初始化，物理块0mi中页面停留时间time[m]=m+1n=0用户内存中是否已存在要调用的页面用户内存中是否存在空物理块N将页面调入空物理块中，该物理块time[m]=0比较所有物理块的time[m]，找到最大值，将页面调入最大值所在物理块，该物理块time[m]=0所有已经存入页面的内存time[m]++，n++NYYn320?结束将页面p[n]调入内存YN存在该页面的物理块timg[m]=0LRU页面置换算法开始内存数据初始化，物理块0mi中页面停留时间time[m]=m+1n=0n50?将页面p[n]调入内存比较物理块中页面在之前的50次调用中出现的次数，将页面p[n]调入使用最少的页面占用的物理块n320?结束按照LRU页面置换算法调入页面n++YNYNLFU页面置换算法五、实验数据及处理结果六、实验体会或对改进实验的建议我做实验的时候，主要的难度是在几个特殊情况的处理上，如LRU内存中的页面都是之前没有调用过的，那怎么办，还有就是LFU中还没有达到“一定时间间隔”的条件时怎么办？另外就是由于实验使用的是系统产生的随机数，所以难以验证实验结果的正确性。七、参考资料《计算机操作系统》《计算机操作系统实验指导书》《C程序设计》《C语言程序设计_现代方法》《计算机操作系统教程习题解答与实验指导(第二版)》八、实验代码#includestdio.h#includestdlib.h#includetime.hints,i;//s表示产生的随机数，i表示物理块数intm,n,h;//循环专用intk,g,f;//临时数据intsum;//缺页次数floatr;//rate命中率intp[320];//page页数inta[320];//执行的指令intpb[32];//physicalblock用户内存容量（物理块）voidinitialization();voidFIFO();voidLRU();voidLFU();voidline();voidstart();voidend();voidmain(){start();srand((int)time(NULL));//以计算机当前时间作为随机数种子for(n=0;n320;n+=3){s=rand()%320+0;//随机产生一条指令a[n]=s+1;//顺序执行一条指令s=rand()%(a[n]+1);//执行前地址指令M`a[n+1]=s+1;s=rand()%(319-a[n+1])+(a[n+1]+1);a[n+2]=s;}for(n=0;n320;n++)p[n]=a[n]/10;//得到指令相对的页数printf(物理块数\tFIFO\t\tLRU\t\tLFU\n);line();for(i=4;i=32;i++){printf(\n%2d：,i);FIFO();LRU();LFU();}end();}voidinitialization()//用户内存及相关数据初始化{for(n=0;n32;n++)pb[n]=-1;sum=0;r=0;k=0;g=-1;f=-1;}voidFIFO()//先进先出置换算法{inttime[32];//定义进入内存时间长度数组intmax;//max表示进入内存时间最久的，即最先进去的initialization();for(m=0;mi;m++)time[m]=m+1;for(n=0;n320;n++){k=0;for(m=0;mi;m++)if(pb[m]==p[n])//表示内存中已有当前要调入的页面{g=m;break;}for(m=0;mi;m++)if(pb[m]==-1)//用户内存中存在空的物理块{f=m;break;}if(g!=-1)g=-1;else{if(f==-1)//找到最先进入内存的页面{max=time[0];for(m=0;mi;m++)if(time[m]max){max=time[m];k=m;}pb[k]=p[n];time[k]=0;//该物理块中页面停留时间置零sum++;//缺页数+1}else{pb[f]=p[n];time[f]=0;sum++;f=-1;}}for(m=0;mi&&pb[m]!=-1;m++)time[m]++;//物理块中现有页面停留时间+1}r=1-(float)sum/320;printf(\t\t%6.4f,r);}voidLRU()//最近最少使用算法{inttime[32];intmax;initialization();for(m=0;mi;m++)time[m]=m+1;for(n=0;n320;n++){k=0;for(m=0;mi;m++)if(pb[m]==p[n]){g=m;break;}for(m=0;mi;m++)if(pb[m]==-1){f=m;break;}if(g!=-1){time[g]=0;g=-1;}else{if(f==-1){max=time[0];for(m=0;mi;m++)if(time[m]max){k=m;max=time[m];}pb[k]=p[n];time[k]=0;sum++;}else{pb[f]=p[n];time[f]=0;sum++;f=-1;}}for(m=0;mi&&pb[m]!=-1;m++)time[m]++;}r=1-(float)sum/320;printf(\t\t%6.4f,r);}voidLFU()//最少访问页面算法{inttime_lru[32],time[32],min,max_lru,t;initialization();for(m=0;mi;m++){time[m]=0;time_lru[m]=m+1;}for(n=0;n320;n++){k=0;t=1;for(m=0;mi;m++)if(pb[m]==p[n]){g=m;break;}for(m=0;mi;m++)if(pb[m]==-1){f=m;break;}if(g!=-1){time_lru[g]=0;g=-1;}else{if(f==-1){if(n=20)//将最少使用的间隔时间定位个单位{max_lru=time_lru[0];//在未达到“一定时间”的要求时，先采用LRU进行页面置换for(m=0;mi;m++)if(time_lru[m]max_lru){k=m;max_lru=time_lru[m];}pb[k]=p[n];time_lru[k]=0;sum++;}else{for(m=0;mi;m++)//计算一定时间间隔内物理块中的页面使用次数for(h=n-1;h=n-51;h--)if(pb[m]==p[h])time[m]++;min=time[0];for(m=0;mi;m++)if(time[m]min){min=time[m];k=m;}for(m=0;mi;m++)//应对出现页面使用次数同样少的情况if(time[m]==min)t++;if(t1)//若使用次数同样少，将次数相同的页面按照LRU进行页面置换{max_lru=time_lru[k];for(m=0;mi&&time[m]==min;m++)if(time_lru[m]max_lru){k=m;max_lru=time_lru[m];}}pb[k]=p[n];time_lru[k]=0;sum++;}}else{pb[f]=p[n];time_lru[f]=0;sum++;f=-1;}}for(m=0;mi&&pb[m]!=-1;m++)time_lru[m]++;}r=1-(float)sum/320;printf(\t\t%6.4f,r);}voidline()//美化程序，使程序运行时更加明朗美观{printf(------------------------------------------------------------------);}voidstart()//表示算法开始{line();printf(\n页面置换算法开始\n);printf(——DesignedbyGGY\n);line();printf(\n\n);}voidend()//表示算法结束{printf(\n);line();printf(\n页面置换算法结束,谢谢使用\n);line();}