操作系统课程设计报告页面置换算法

计算机科学与技术学院《操作系统》课程设计报告（2013/2014学年第一学期）学生姓名：学生专业：网络工程学生班级：网络工程112001学生学号：指导教师：2013年12月20日计算机科学与技术学院课程设计任务书课程设计名称《操作系统》课程设计课程设计题目页面置换算法学生姓名贾正正专业班级网络工程112001班学号201120030109课程设计任务内容[问题描述]设计一个虚拟存储区和内存工作区，并使用最佳淘汰算法（OPT）、先进先出算法（FIFO）、最近最久未使用算法（LRU）计算访问命中率。[基本要求]（1）分析设计要求，给出解决方案（2）设计合适的测试用例，对得到的运行结果要有分析。指导教师：赵建时间：2013年12月10日目录第一章问题的提出..................................................81.1关于页面置换算法模拟程序问题的产生...........................81.2任务分析....................................................8第二章需求分析...................................................92.1需求说明.....................................................92.2操作界面和操作方法...........................................9第三章设计描述...................................................103.1方案设计....................................................103.2主要的函数..................................................10第四章算法描述...................................................114.1主函数流程图................................................114.2FIFO（先进先出）页面置换算法.................................74.3LRU(最近最久未使用)页面置换算法..............................84.4OPT（最佳置换算法）..........................................64.5实现结果....................................................10第五章程序测试....................................................135.1设计测试数据...............................................135.2测试结果及分析.............................................13结论.............................................................14参考文献...........................................................15代码：.............................................................16第一章问题的提出1.1关于页面置换算法模拟程序问题的产生在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业全部装入内存方能运行，但是有两种情况：（1）有的作业很大，不能全部装入内存，致使作业无法运行；（2）有大量作业要求运行，但内存容量不足以容纳所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两个问题。从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法（Page-ReplacementAlgorithms）。进而页面置换算法模拟程序能客观的将其工作原理展现在我们面前。1.2任务分析首先，定义宏变量，设置所占最大内存长度。编辑以时间为种子，初始化随即发生器。进行相关页面输入程序的编写以及页面的打印。尔后，寻找最近最近最久未使用的页面、记录当前内存块中页面离下次使用间隔长度等相关程序的代码编写。最后，进行)FIFO、LRU、OPT三种算法的编写。第二章需求分析2.1需求说明1.用随机数方法产生页面走向，页面走向长度为L。2.根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率；为简化操作，在淘汰一页时，只将该页在页表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。3.假定可用内存块和页表长度(作业的页面数)分别为m和k，初始时，作业页面都不在内存。2.2操作界面和操作方法*************页面置换算法算法演示****************请首先输入页面走向长度L:请首先输入页面数:根据提示进入算法界面：在如上的操作界面中分别按照提示进行输入，按回车键表示当前输入完毕，然后进行下个步骤的输入或者得到最终结果。第三章设计描述3.1方案设计首先，定义宏变量，设置所占最大内存长度。编辑以时间为种子，初始化随即发生器。进行相关页面输入程序的编写以及页面的打印。其次，寻找最近最近最久未使用的页面、记录当前内存块中页面离下次使用间隔长度等相关程序的代码编写。最后，进行FIFO、LRU、OPT三种算法的编写。3.2主要的函数Input(intm,Prop[L])（打印页面走向状态）；voidprint(Pro*page1)（打印当前的页面）；intSearch(inte,Pro*page1)（寻找内存块中与e相同的块号）；intMax(Pro*page1)（寻找最近最长未使用的页面）；intCount(Pro*page1,inti,intt,Prop[L])（记录当前内存块中页面离下次使用间隔长度）；intmain()（主函数）；随机数发生器#includestdlib.h#includetime.h//准备用时钟函数调用库函数t=time(NULL);//取时钟时间并存入t调用库函数srand(t);//用时间t初始化随机数发生器调用库函数x=rand()%10+1;//返回一个1~10之间的随机数第四章算法描述4.1主函数流程图输入页面走向长度L随机产生L个数字输入当前页面数L是否在范围页面数是否在范围输入1—3结束始YNYN是否为1FIFO页面置换算法是否为3是否为2LRU页面置换算法OPT页面置换算法YYYNNN开始结束4.2FIFO（先进先出）页面置换算法设计原理：需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当前的页面。iLNY输出当前页面信息NY输出当前内存块状结束代码：if(c==1)//FIFO页面置换{n=0;cout******************************************endl;coutendl;coutFIFO算法页面置换情况如下:endl;coutendl;cout******************************************endl;while(im){if(Search(p[i].num,page)=0)//当前页面在内存中{coutp[i].num;//输出当前页p[i].numcout不缺页endl;i++;//i加1}else//当前页不在内存中{if(t==M)t=0;else{n++;//缺页次数加1page[t].num=p[i].num;//把当前页面放入内存中coutp[i].num;print(page);//打印当前页面t++;//下一个内存块i++;//指向下一个页面}}}cout缺页次数：n缺页率：n/mendl;}84.3LRU(最近最久未使用)页面置换算法设计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最近一段时间页面走向存入数组p[]中，内存块用page[]表示初始化为0当前p[]中第i个元素是否已在内存Page[]是否有空把page[]中最近最久未使用的页面置换出去.i++i++把p[i]的内容直接装入最上面一个空内存块，i++输出当前页面信息结束开始开始开始开始开始NYiL输出当前内存块状NYNY9也不会被访问。代码：if(c==2)//LRU页面置换{n=0;cout******************************************endl;coutendl;coutLRU算法页面置换情况如下:endl;coutendl;cout******************************************endl;while(im){inta;t=Search(p[i].num,page);if(t=0)//如果已在内存块中{page[t].time=0;//把与它相同的内存块的时间置0for(a=0;aM;a++)if(a!=t)page[a].time++;//其它的时间加1coutp[i].num;cout不缺页endl;}else//如果不在内存块中{n++;//缺页次数加1t=Max(page);//返回最近最久未使用的块号赋值给tpage[t].num=p[i].num;//进行替换page[t].time=0;//替换后时间置为0coutp[i].num;print(page);for(a=0;aM;a++)if(a!=t)page[a].time++;//其它的时间加1}i++;}cout缺页次数：n缺页率：n/mendl;}104.4OPT（最佳置换算法）设计原理：需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现在最远的页面换出。把page[]中以后一段时间都不使用或是使用时间离现在最远的换出.i++把p[i]的内容直接装入最上面一个空内存块，i++输出当前页面信息结束开始开始开始NYiL输出当前内存块状NY页面走向存入数组p[]中，内存块用page[]表示初始化为0当前p[]中第i个元素是否已在内存Page[]是否有空i++YNN11代码：if(c==3)//OPT页面置换{n=0;cout******************************************endl;coutendl;coutOPT算法置换情况如下:endl;coutendl;cout******************************************endl;while(im){if(Search(p[i].num,page)=0)//如果已在内存块中{coutp[i].num;cout不缺页endl;i++;}else//如果不在内存块中{inta=0;for(t=0;tM;t++)if(page[t].num==0)a++;//记录空的内存块数if(a!=0)//有空内存块{intq=M;for(t=0;tM;t++)if(page[t].num==0&&qt)q=t;//把空内存块中块号最小的找出来page[q].num=p[i].num;n++;coutp[i].num;print(page);i++