操作系统 设计说明书

操作系统设计说明书学院名称：计算机与信息工程学院班级名称：计科112班学生姓名：夏宗斌、柴远亮、王辉、王周军、陈敏学号：2011211227、2011211173、2011211212、2011211222、2011211175题目：页面置换算法实现与分析指导教师：胡成祥起止日期：2013年6月3日~2013年6月30日目录1.选题背景....................................................................................................................32.方案论证....................................................................................................................32.1任务分析........................................................................................................32.2任务目的........................................................................................................32.3方案设计........................................................................................................33.过程论述....................................................................................................................43.1FIFO(先进先出)............................................................................................43.2LRU(最近最久未使用)..................................................................................53.3OPT(最佳置换算法)......................................................................................74.结果分析....................................................................................................................94.1实现结果.........................................................................................................94.2程序测试.......................................................................................................135.结论..........................................................................................................................14参考文献......................................................................................................................14代码..............................................................................................................................141.选题背景随着计算机的普及人们的物质生活得到了极大的满足，人们在精神生活方面同样也需要提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业全部装入内存方能运行，但是有两种情况：（1）有的作业很大，不能全部装入内存，致使作业无法运行；（2）有大量作业要求运行，但内存容量不足以容纳所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两个问题。从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法（Page-ReplacementAlgorithms）。进而页面置换算法模拟程序能客观的将其工作原理展现在我们面前。2.方案论证2.1任务分析首先，定义宏变量，设置所占最大内存长度。编辑以时间为种子，初始化随即发生器。进行相关页面输入程序的编写以及页面的打印。然后，寻找最近最久未使用的页面、记录当前内存块中页面离下次使用间隔长度等相关程序的代码编写。最后，进行FIFO、LRU、OPT三种算法的编写。2.2任务目的1.通过模拟实现请求页式存储管理的几种页面置换算法，了解虚拟存储技术的特点。2.通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。3.掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。2.3方案设计1.用随机数方法产生页面走向，页面走向长度为L。2.根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率；为简化操作，在淘汰一页时，只将该页在页表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。3.假定可用内存块和页表长度(作业的页面数)分别为m和k，初始时，作业页面都不在内存。随机数产生程序：inti,j;j=time(NULL);//取时钟时间srand(j);//以时钟时间x为种子，初始化随机数发生器cout输出随机数:;for(i=0;im;i++){p[i].num=rand()%10+1;//产生1到10之间的随即数放到数组p中p[i].time=0;coutp[i].num;}上述随机数发生函数产生的随机数为0.0～1.0，稍另变化就可得到0～n-1之间的随机数。程序开始时，应对变量Seed(实型)赋初值。根据页面置换算法的理论操作及要求，首先要进行页面长度的确定，定义结构体用以储存数据，进行主界面代码及OPT、FIFO、LRU页面置换算法代码的编写。3.过程论述3.1FIFO(先进先出)算法思想：需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当前的页面。算法流程图：图3.1FIFO算法流程图核心代码：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;}3.2LRU(最近最久未使用)算法思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最近一段时间也不会被访问。算法流程图：图3.2LRU算法流程图核心代码：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;}3.3OPT(最佳置换算法)算法思想：需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现在最远的页面换出。算法流程图：图3.3OPT算法流程图核心代码：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++;}else{inttemp=0,s;for(t=0;tM;t++)//寻找内存块中下次使用离现在最久的页面if(tempCount(page,i,t,p)){t