操作系统课程设计-页面置换算法.doc

计算机科学与技术学院操作系统课程设计报告 （2013/2014学年 第一学期）学生姓名： 学生专业： 网络工程学生班级： 网络工程112001学生学号： 指导教师： 2013年12月20日 计算机科学与技术学院课程设计任务书课程设计名称操作系统课程设计课程设计题目页面置换算法学生姓名贾正正专业班级网络工程112001班学号201120030109课程设计任务内容问题描述 设计一个虚拟存储区和内存工作区，并使用最佳淘汰算法（OPT）、先进先出算法（FIFO）、最近最久未使用算法（LRU）计算访问命中率。基本要求 （1）分析设计要求，给出解决方案（2）设计合适的测试用例，对得到的运行结果要有分析。 指导教师：赵建 时 间： 2013年 12月 10日 目 录 第一章 问题的提出31.1关于页面置换算法模拟程序问题的产生31.2 任务分析3第二章 需求分析42.1需求说明42.2操作界面和操作方法4第三章 设计描述53.1方案设计53.2主要的函数5第四章 算法描述64.1主函数流程图64.2FIFO（先进先出）页面置换算法74.3LRU(最近最久未使用)页面置换算法94.4OPT（最佳置换算法）114.5实现结果14第五章 程序测试175.1 设计测试数据175.2 测试结果及分析17结 论18参考文献19代码：20 第一章 问题的提出1.1关于页面置换算法模拟程序问题的产生在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业全部装入内存方能运行，但是有两种情况：（1） 有的作业很大，不能全部装入内存，致使作业无法运行；（2） 有大量作业要求运行，但内存容量不足以容纳所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两个问题。从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法（Page-Replacement Algorithms）。进而页面置换算法模拟程序能客观的将其工作原理展现在我们面前。1.2 任务分析首先，定义宏变量，设置所占最大内存长度。编辑以时间为种子，初始化随即发生器。进行相关页面输入程序的编写以及页面的打印。尔后，寻找最近最近最久未使用的页面 、记录当前内存块中页面离下次使用间隔长度等相关程序的代码编写。最后，进行)FIFO 、LRU、 OPT三种算法的编写。 第二章 需求分析2.1需求说明1. 用随机数方法产生页面走向，页面走向长度为L。2. 根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率；为简化操作，在淘汰一页时，只将该页在页表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。3. 假定可用内存块和页表长度 (作业的页面数)分别为m和k，初始时，作业页面都不在内存。2.2操作界面和操作方法 *页面置换算法算法演示* 请首先输入页面走向长度L: 请首先输入页面数: 根据提示进入算法界面： 在如上的操作界面中分别按照提示进行输入，按回车键表示当前输入完毕，然后进行下个步骤的输入或者得到最终结果。第3章 设计描述3.1方案设计首先，定义宏变量，设置所占最大内存长度。编辑以时间为种子，初始化随即发生器。进行相关页面输入程序的编写以及页面的打印。其次，寻找最近最近最久未使用的页面 、记录当前内存块中页面离下次使用间隔长度等相关程序的代码编写。最后，进行FIFO 、LRU、 OPT三种算法的编写。3.2主要的函数Input(int m,Pro pL)（打印页面走向状态）；void print(Pro *page1)（打印当前的页面）；int Search(int e,Pro *page1 )（寻找内存块中与e相同的块号）； int Max(Pro *page1)（寻找最近最长未使用的页面）；int Count(Pro *page1,int i,int t,Pro pL)（记录当前内存块中页面离下次使用间隔长度）；int main()（主函数）；随机数发生器 #include #include /准备用时钟函数调用库函数t=time(NULL);/取时钟时间并存入t调用库函数srand(t);/用时间t初始化随机数发生器调用库函数x=rand( )%10+1;/返回一个110之间的随机数第4章 算法描述 开始4.1主函数流程图输入页面走向长度LNL是否在范围 结束YYYNNN 结束始 OPT页面置换算法是否为3 LRU页面置换算法是否为2 FIFO页面置换算法NY是否为1输入13页面数是否在范围输入当前页面数 随机产生L个数字Y564.2FIFO（先进先出）页面置换算法N iL输出当前页面信息YNY输出当前内存块状 结束 设计原理： 结束需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当前的页面。0 6代码：if(c=1)/FIFO页面置换 n=0;cout * endl;coutendl; cout FIFO算法页面置换情况如下: endl;coutendl; cout * endl; while(i=0)/当前页面在内存中 coutpi.num ;/输出当前页pi.numcout不缺页endl;i+;/i加1 else /当前页不在内存中 if(t=M)t=0; else n+;/缺页次数加1 paget.num=pi.num; /把当前页面放入内存中 coutpi.num ; print(page); /打印当前页面 t+; /下一个内存块i+; /指向下一个页面 cout缺页次数：n 缺页率：n/mL 结束Y输出当前内存块状 结束9 设计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最近一段时间6也不会被访问。代码：if(c=2)/LRU页面置换 n=0; cout * endl;coutendl; cout LRU算法页面置换情况如下: endl; coutendl;cout * endl; while(i=0) /如果已在内存块中 paget.time=0; /把与它相同的内存块的时间置0for(a=0;aM;a+)if(a!=t)pagea.time+; /其它的时间加1 coutpi.num ;cout不缺页endl; else /如果不在内存块中 n+; /缺页次数加1 t=Max(page); /返回最近最久未使用的块号赋值给t paget.num=pi.num; /进行替换 paget.time=0; /替换后时间置为0 coutpi.num ;print(page);for(a=0;aM;a+)if(a!=t)pagea.time+; /其它的时间加1 i+; cout缺页次数：n 缺页率：n/mLY输出当前内存块状 结束11 设计原理：需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现在最远的页面换出。 结束 代码： if(c=3) /OPT页面置换 n=0;cout * endl;coutendl;cout OPT算法置换情况如下:endl;coutendl;cout * endl; while(i=0) /如果已在内存块中 coutpi.num ;cout不缺页endl;i+;else /如果不在内存块中int a=0; for(t=0;tM;t+)if(paget.num=0)a+; /记录空的内存块数if(a!=0) /有空内存块int q=M;for(t=0;tt)q=t; /把空内存块中块号最小的找出来pageq.num=pi.num;n+; coutpi.num ;print(page);i+;elseint temp=0,s;for(t=0;tM;t+) /寻找内存块中下次使用离现在最久的页面if(tempCount(page,i,t,p)temp=Count(page,i,t,p);s=t; /把找到的块号赋给spages.num=pi.num; n+; coutpi.num ; print(page); i+;cout缺页次数：n 缺页率：n/mendl;4.5实现结果程序在运行的情况下，进入主界面输入菜单，如图3-3所示：输入10：图4-5 输入10后的输出图输入22：图5-6输入数据22后输出图输入数据16：图5-7 输入数据16后的输出图输入数据：图5-8输出图选1，进入FIFO页面置换：图5-9 FIFO的输出图选2，进入LRU页面置换：图5-10 LRU的输出图输入3，进入OPT页面置换： 第五章 程序测试5.1 设计测试数据A 10 22 16 ；1 6 5 ；B 1C 2 D 35.2 测试结果及分析1）测试A结果及分析 进入主菜单后输入10、22，显示输入不满足要求。输入16 显示相关信息;输入1 、6不满足要求，输入5 显示出相关信息。2）测试结果及分析显示出FIFO页面置换算法的缺页信息及缺页率。3）测试C结果及分析显示出LRU页面置换算法的缺页信息及缺页率。4）测试D结果及分析显示出OPT页面置换算法的缺页信息及缺页率结 论通过本次课程设计，让我深入的了解了页面置换算法。OPT算法总是选择被淘汰页面将是以后永远不使用的或者在最长时间内不再被访问的页面。先找出所需页面在磁盘的位置，再找出可用内存块，然后将所需页面装入内存，修改相应的数据结构。最佳页面置换算法可以先写一个结构体，包括编号和使用次数2个内容，然后动态生成一个数组。然后另外写2个函数。一个计算中断次数，一个进行页面置换。在检测是否中断的时候，可以循环遍历上面动态生成的数组。如果数组满了且有页面中断的时候，才调用页面置换的函数，否则只要把数据放入数组就可以，不用进行页面置换。此外还得写一个用于寻找内存块中下次使用离现在最久的页面和一个用于记录当前内存块中页面离下次使用时间间隔长度的函数。最佳淘汰算法是一种理想情况下的页面置换算法，但实际上是不可能实现的，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是可用于对可实现算法的性能进行衡量比较。参考文献面向对象程序设计与VisualC+6.0教程 陈天华编著C程序设计（第三版） 谭浩强编著C+入门经典面向对象程序设计与C+实现 刘晋萍编著计算机操作系统教程 徐甲同等编著 操作系统 罗宇等编著 操作系统实验教程 张丽芬, 刘利雄, 王全玉编著 计算机操作系统 梁红兵、哲风屏、汤子瀛 编著操作系统教程 陈向群、杨芙清 编著代码：#include#include #include #include #define L 20/页面走向长度最大为20int M; /内存块struct Pro/定义一个结构体 int num,time; Input(int m,Pro pL)/打印页面走向状态 cout请输入实际页面走向长度L(15=Lm; if(m20|m15)cout实际页面长度须在1520之间;请重新输入L： ; else break; while(1); int i,j; j=time(NULL);/取时钟时间 srand(j);/以时钟时间x为种子，初始化随机数发生器cout输出随机数: ; for(i=0;im;i+) pi.num=rand( )%10+1;/产生1到10之间的随即数放到数组p中 pi.time=0;coutpi.num ; coutendl; return m;void print(Pro *page1)/打印当前的页面 Pro *page=new ProM; page=page1; for(int i=0;iM;i+) coutpagei.num ; coutendl;int Search(int e,Pro *page1 )/寻找内存块中与e相同的块号 Pro *page=new ProM; page=page1; for(int i=0;iM;i+)if(e=pagei.num)return i;/返回i值 return -1;int Max(Pro *page1)/寻找最近最长未使用的页面 Pro *page=new ProM; page=page1; int e=page0.time,i=0; while(iM) /找出离现在时间最长的页面 if(epagei.time) e=pagei.time; i+; for( i=0;iM;i+)if(e=pagei.time)return i;/找到离现在时间最长的页面返回其块号 return -1;int Count(Pro *page1,int i,int t,Pro pL)/记录当前内存块中页面离下次使用间隔长度 Pro *page=new ProM; page=page1; int count=0; for(int j=i;jL;j+) if(paget.num=pj.num )break;/当前页面再次被访问时循环结束 else count+;/否则count+1 return count;/返回count的值 int main() int c; int m=0,t=0;float n=0;Pro pL; m=Input(m,p);/调用input函数，返回m值 coutM;if(M5|M3)cout内存块m须在35之间，请重新输入m： ;else break;while(1); Pro *page=new ProM; do for(int i=0;iM;i+)/初试化页面基本情况 pagei.num=0; pagei.time=m-1-i; i=0; cout1:FIFO页面置换endl; cout2:LRU页面置换endl; cout3:OPT页面置换endl; cout按其它键结束程序；c; system(cls); if(c=1)/FIFO页面置换 n=0;cout * endl;coutendl; cout FIFO算法页面置换情况如下: endl;coutendl; cout * endl; while(i=0) /当前页面在内存中 coutpi.num ; /输出当前页pi.numcout不缺页endl;i+; /i加1 else /当前页不在内存中 if(t=M)t=0; else n+; /缺页次数加1 paget.num=pi.num; /把当前页面放入内存中 coutpi.num ; print(page); /打印当前页面 t+; /下一个内存块i+; /指向下一个页面 cout缺页次数：n 缺页率：n/mendl; if(c=2)/LRU页面置换 n=0; cout * endl;coutendl; cout LRU算法页面置换情况如下: endl; coutendl;cout * endl; while(i=0)/如果已在内存块中 paget.time=0;/把与它相同的内存块的时间置0for(a=0;aM;a+)if(a!=t)pagea.time+;/其它的时间加1 coutpi.num ;cout不缺页endl; else /如果不在内存块中 n