南昌大学操作系统实验报告.doc

南昌大学实验报告 -（3）存储管理的模拟实现学生姓名： 张晨欣 学 号： 61004011132 专业班级： 电114班 实验类型： 验证 综合 设计 创新 实验日期： 实验成绩： 一、 实验目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。二、 实验内容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. 重复AE，直到执行320次指令。2 指令序列变换成页地址流，设：（1） 页面大小为1K；（2） 用户内存容量为4页到32页；（3） 用户虚存容量为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函数和以下几个函数组成：void initialization();初始化内存数据void FIFO();FIFO先进先出算法；void LRU();LRU最久未使用算法；void LFU();LFU最近最久未使用算法；4、 检查代码，将编出的代码编译、链接，验证其正确性。页面置换算法整体结构FIFO页面置换算法LRU页面置换算法LFU页面置换算法五、 实验数据及处理结果六、 实验体会或对改进实验的建议我做实验的时候，主要的难度是在几个特殊情况的处理上，如LRU内存中的页面都是之前没有调用过的，那怎么办，还有就是LFU中还没有达到“一定时间间隔”的条件时怎么办？另外就是由于实验使用的是系统产生的随机数，所以难以验证实验结果的正确性。七、 参考资料计算机操作系统计算机操作系统实验指导书C程序设计C语言程序设计_现代方法计算机操作系统教程习题解答与实验指导(第二版)八、 实验代码#include #include #include int s,i;/s表示产生的随机数，i表示物理块数int m,n,h;/循环专用int k,g,f;/临时数据int sum;/缺页次数float r;/rate命中率int p320;/page页数int a320;/执行的指令int pb32;/physical block用户内存容量（物理块）void initialization();void FIFO();void LRU();void LFU();void line();void start();void end();void main()start();srand(int) time (NULL);/以计算机当前时间作为随机数种子for (n=0;n320;n+=3)s=rand()%320+0;/随机产生一条指令an=s+1;/顺序执行一条指令s=rand()%(an+1);/执行前地址指令Man+1=s+1;s=rand()%(319-an+1)+(an+1+1);an+2=s;for (n=0;n320;n+)pn=an/10;/得到指令相对的页数printf(物理块数t FIFOtt LRUtt LFUn);line();for (i=4;i=32;i+)printf(n %2d：,i);FIFO();LRU();LFU();end();void initialization()/用户内存及相关数据初始化for (n=0;n32;n+)pbn=-1;sum=0;r=0;k=0;g=-1;f=-1;void FIFO()/先进先出置换算法int time32;/定义进入内存时间长度数组int max;/max表示进入内存时间最久的，即最先进去的initialization();for(m=0;mi;m+)timem=m+1;for (n=0;n320;n+)k=0;for (m=0;mi;m+)if (pbm=pn)/表示内存中已有当前要调入的页面g=m;break;for (m=0;mi;m+)if (pbm=-1)/用户内存中存在空的物理块f=m;break;if (g!=-1)g=-1;elseif (f=-1)/找到最先进入内存的页面max=time0;for(m=0;mmax)max=timem;k=m;pbk=pn;timek=0;/该物理块中页面停留时间置零sum+;/缺页数+1elsepbf=pn;timef=0;sum+;f=-1;for (m=0;mi & pbm!=-1;m+)timem+;/物理块中现有页面停留时间+1r=1-(float)sum/320;printf(tt%6.4f,r);void LRU()/最近最少使用算法int time32;int max;initialization();for (m=0;mi;m+)timem=m+1;for (n=0;n320;n+)k=0;for (m=0;mi;m+)if (pbm=pn)g=m;break;for (m=0;mi;m+)if (pbm=-1)f=m;break;if (g!=-1)timeg=0;g=-1;elseif (f=-1)max=time0;for (m=0;mmax)k=m;max=timem;pbk=pn;timek=0;sum+;elsepbf=pn;timef=0;sum+;f=-1;for (m=0;mi & pbm!=-1;m+)timem+;r=1-(float)sum/320;printf(tt%6.4f,r);void LFU()/最少访问页面算法initialization();int time_lru32,time32,min,max_lru,t;for (m=0;mi;m+)timem=0;time_lrum=m+1;for (n=0;n320;n+)k=0;t=1;for (m=0;mi;m+)if (pbm=pn)g=m;break;for (m=0;mi;m+)if (pbm=-1)f=m;break;if (g!=-1)time_lrug=0;g=-1;elseif (f=-1)if (n=20)/将最少使用的间隔时间定位个单位max_lru=time_lru0;/在未达到“一定时间”的要求时，先采用LRU进行页面置换for (m=0;mmax_lru)k=m;max_lru=time_lrum;pbk=pn;time_lruk=0;sum+;elsefor (m=0;m=n-51;h-)if (pbm=ph)timem+;min=time0;for (m=0;mi;m+)if (timemmin)min=timem;k=m;for (m=0;m1)/若使用次数同样少，将次数相同的页面按照LRU进行页面置换max_lru=time_lruk;for (m=0;mmax_lru)k=m;max_lru=time_lrum;pbk=pn;time_lruk=0;sum+;elsepbf=pn;time_lruf=0;sum+;f=-1;for (m=0;mi & pbm!=-1;m+)time_lrum+;r=1-(float)sum/320;printf(tt%6.4f,r);void line() /美化程序，使程序运行