页面置换算法模拟程序-附代码

《页面置换算法模拟程序-附代码》由会员分享，可在线阅读，更多相关《页面置换算法模拟程序-附代码（23页珍藏版）》请在装配图网上搜索。

1、1 问题的提出21.1关于页面置换算法模拟程序问题的产生21.2任务分析2需求分析23.方案设计34总体设计44.1 程序N-S图44.2主要的函数44.3.1 4.3主要流程图及代码5FIFO（先进先出）54.3.2 LRU（最近最久未使用）64.3.3 OPT（最佳置换算法）94.4实现结果115.程序测试155.1设计测试数据155.2测试结果及分析16随着计算机的普及人们的物质生活得到了极大的满足，人们在精神生活方面同样也需要提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机

2、系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果本课程设计是学生学习完操作系统教程课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。关键词：编制页面置换算法模拟程序、打印页面、FIFO页面算法、LRU页

3、面置换算法、OPTM面置换算法。引言1. 问题的提出1.1关于页面置换算法模拟程序问题的产生在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业全部装入内存方能运行，但是有两种情况：（1）有的作业很大，不能全部装入内存，致使作业无法运行；（2）有大量作业要求运行，但内存容量不足以容纳所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两个问题。从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法（Page-ReplacementAlgorithms）进而页面置换算法模拟程序能客观的将其工作原理展现在我们面前。1.2任务分析首先，定义

4、宏变量，设置所占最大内存长度。编辑以时间为种子，初始化随即发生器。进行相关页面输入程序的编写以及页面的打印。尔后，寻找最近最近最久未使用的页面、记录当前内存块中页面离下次使用间隔长度等相关程序的代码编写。最后，进行）FIFO、LRUOPT三种算法的编写。2. 需求分析1. 用随机数方法产生页面走向，页面走向长度为L。2. 根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率；为简化操作，在淘汰一页时，只将该页在页表中抹去，而不再判断它是否被改写过，也不将它写回到辅存。3. 假定可用内存块和页表长度（作业的页面数）分别为m和k，初始时，作业页面都不在内存。随机数产生程序:inti,

5、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上述随机数发生函数产生的随机数为0.01.0，稍另变化就可得到0n-1之间的随机数。程序开始时，应对变量Seed(实型)赋初值。根据页面置换算法的理论操作及要求，首先要进行页面长度的确定，定义结构体用以储存数据，进行主界面代码及FIFO、LRUOPT页面置换算法代码的编写。3. 方案设计首先，定义宏变量，设置所占最大内存长度。编辑以时间为种

6、子，初始化随即发生器。进行相关页面输入程序的编写以及页面的打印。其次，寻找最近最近最久未使用的页面、记录当前内存块中页面离下次使用间隔长度等相关程序的代码编写。最后，进行FIFO、LRUOPT三种算法的编写。.程序运行平台VC+6.0具体操作如下：在VC+6.0的环境下准备用时钟函数调用库函数(#include)、取时钟时间并存入t调用库函数(t=time(NULL)、用时间t初始化随机数发生器调用库函数(srand(t)返回一个110之间的随机数(x=rand()%10+1)。编写三种算法。4. 总体设计4.1程序N-S图程序开始输入选择项(进行判断)页面存在进入下一部操作此项不存在输入要输

7、出的结果输出结果结束4.2主要的函数Input(intm,PropL)(打印页面走向状态)；voidprint(Pro*page1)(打印当前的页面)；intSearch(inte,Pro*page1)(寻找内存块中与e相同的块号)；intMax(Pro*page1)(寻找最近最长未使用的页面)；intCount(Pro*page1,inti,intt,PropL)(记录当前内存块中页面离下次使用间隔长度)；intmain()(主函数)；随机数发生器#include#include/准备用时钟函数调用库函数t=time(NULL);取时钟时间并存入t调用库函数srand(t);用时间t初始化随

8、机数发生器调用库函数x=rand()%10+1;返回一个110之间的随机数4.3主要流程图及代码(先进先出)设计原理：需要进行页面置换，即把内存中装入最早的那个页面淘汰,换入当前的页面。算法流程图图4-仆IFO算法流程图代码：if(c=1)/FIFO页面置换n=0;coutendl;coutendl;coutendl;coutendl;cout*FIFO算法页面置换情况如下:*=0)当前页面在内存中coutpi.numvv;/输出当前页pi.numcout不缺页endl;i+;/i加1else/当刖页不在内存中if(t=M)t=0;elsen+;/缺页次数加1把当前页面放入内打印当前页面下一个

9、内存块指向下一个页面缺页率：n/mendl;paget.num=pi.num;/存中coutpi.numprint(page);/t+;/i+;/cout缺页次数：*V432LRU（最近最久未使用）设计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最近一段时间也不会被访问。算法流程图:*代码：n=0;coutendl;coutendl;coutendl;coutendl;cout如果已在内存块中LRU算法页面置换情况如下：*=0)/paget.time=

10、O;置0for(a=0;aM;a+)if(a!=t)pagea.time+;coutpi.num;cout不缺页endl;else/n+;/缺页次数加t=Max(page);/赋值给tpaget.num=pi.num;/paget.time=0;/coutpi.num;print(page);for(a=0;aM;a+)if(a!=t)pagea.time+;i+;cout缺页次数：*V/把与它相同的内存块的时间/其它的时间加1如果不在内存块中1返回最近最久未使用的块号进行替换替换后时间置为0/其它的时间加1缺页率：n/mendl;433OPT（最佳置换算法）设计原理：需要进行页面置换，把内存

11、中以后一段时间都不使用或是使用时间离现在最远的页面换出。流程图:i+开始N页面走向存入数组p中，内存块用page表示初始化为0当前p中第i个元素是否已在内存Page是否有空把page中以后一段时间都不使用或是使用时间离现在最远的换出.i+把pi的内容直接装入最上面一个空内存块，i+结束图4-3OPT流程图代码：if(c=3)/OPTn=0;coutendl;coutendl;coutcoutendl;coutendl;while(ivm)页面置换*OPT算法置换情况如下:=0)coutpi.num;cout不缺页endl;i+;else/inta=0;for(t=0;tM;t+)/如果已在内存

12、块中如果不在内存块中块号最小的找出来if(paget.num=0)a+;/记录空的内存块数if(a!=0)/有空内存块intq=M;for(t=0;tt)q=t;/把空内存块中n+;coutpi.num;print(page);i+；elseinttemp=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缺页率：entsandSettin

13、sAdBinistratort直e图4-5输入14后的输出图输入25：cC:DocuentsandSettingsAdBinistratar桌面Debugos-exe*厂亠更圭向长图5-6输入数据25后输出图输入数据18:*C:DocuAentsandSettingsAdinistratorfiiDebugos.exe*410235821154LL611A1A8207=重重0凡请请丄Ll在在9页面须须7存页度度二内际用实E-E-机可入霄随入输际留输图5-7输入数据18后的输出图:14$入S输入数据:2518132104实际匹面卡度须在1520tT0；请重左“装怀贡面去度须在丄5如之周；请重耕输

14、入S输由随机數：内存块尬须在3石之间，:FIFO贝闻置换HRU里面sOPT面其它犍结束程序；图5-8输出图图5-9FIFO的输出图CAt:DocmentsandbettmgsAd*inistratorXjlfiDebugosLRU算法页面置换情况如下:1079IB09卞鎳贡379103tL19103U011023TOCo1-5hz不缺贝5658?图5-10LRU的输出图5. 图5-11OPT的输出图程序测试5.1设计测试数据A142518;264B1C25.2测试结果及分析1）测试A结果及分析进入主菜单后输入14、25,显示输入不满足要求。输入18显示相关信息；输入2、6不满足要求，输入4显示

15、出相关信息。2）测试结果及分析显示出FIFO页面置换算法的缺页信息及缺页率。3）测试C结果及分析显示出LRU页面置换算法的缺页信息及缺页率。4）测试D结果及分析显示出OPTK面置换算法的缺页信息及缺页率结论通过这次课程设计，不仅让我了解了页面置换算法，开始我一味的进行调试，急切的想侥幸调试出来，但由于没有进行深入的考虑，我调试了很久都没没有成功，我仔细的分析题目，分析材料，在原由的基础上我进行了改正，我最后还是调试成功了，还是经过了一翻努力，这次操作系统实习，不仅让我对操作系统这门课程有了更深入的研究、对很多重要的概念有了巩固和掌握。通过努力，三个页面置换算法程序都已经完成，此时此刻，我心里多

16、了些成就感。虽然自己所做的很少也不够完善，但毕竟也是努力的结果。主要有以下几点收获：1. 通过对上网和看书查阅相关资料，使自己对VC+语言的基本框架有新的了解，加深了对可视化程序的认识。2. 在使用VC+语言来实现功能时，不像以往用的其他语言，它比较简练，更容易理解，实用性很强。3. 先进先出页面置换和LRU以及OPT算法各有特点，但是实践起来却很大，使自己对页面置换算法有了新的认识。一周半的课程设计就要结束了，不但对专业知识有了更深的理解，更使的自己认识到实践的重要性，理论、实践相结合才能达到很好的学习效果，特别是程序语言的学习。致谢本次课程设计能顺利完成，感谢学校的大力支持，感谢数学与计算

17、机学院为我们提供实练的机会，感谢老师的细心教导。此次的课程设计收获很多，虽然经过了一段漫长而又痛苦的过程，但是自己还是完成了，这是与自己的努力是分不开的，但是自己在调试过程当中遇到的一些问题，自己仍然不懂，是在同学、老师的帮助下完成的，在这里还要再次对他们的付出表示崇高的敬意。参考文献面向对象程序设计与VisualC+6.0教程陈天华编著C程序设计(第三版)谭浩强编著C+入门经典面向对象程序设计与C+实现刘晋萍编者计算机操作系统教程徐甲同等编著操作系统罗宇等编著操作系统实验教程张丽分，刘利雄，土全玉编著计算机操作系统梁红兵、哲风屏、汤子瀛编著操作系统教程陈向群、杨芙清编著代码：#include

18、#inelude#inelude#inelude#defineL20页面走向长度最大为20intM;/内存块structPro/定义一个结构体intnum,time;Input(intm,PropL)打印页面走向状态cout请输入实际页面走向长度L(15=L20|m15)cout实际页面长度须在1520之间；请重新输入L:elsebreak;while(1);inti,j;j=time(NULL);取时钟时间srand(j);以时钟时间x为种子，初始化随机数发生器cout输出随机数：;for(i=0;im;i+)pi.num=rand()%10+1;产生1到10之间的随即数放到数组p中pi.t

19、ime=O;coutpi.num;coutendl;returnm;voidprint(Pro*page1)打印当前的页面Pro*page=newProM;page=page1;for(inti=0;iM;i+)coutpagei.num;coutendl;intSearch(inte,Pro*page1)/寻找内存块中与e相同的块号Pro*page=newProM;page=page1;for(inti=0;iM;i+)if(e=pagei.num)returni;/返回i值return-1;intMax(Pro*page1)寻找最近最长未使用的页面Pro*page=newProM;page

20、=page1;inte=page0.time,i=0;while(iM)/找出离现在时间最长的页面if(epagei.time)e=pagei.time;i+;for(i=O;iM;i+)if(e=pagei.time)returni;找到离现在时间最长的页面返回其块号return-1;intCount(Pro*page1,inti,intt,PropL)记录当前内存块中页面离下次使用间隔长度Pro*page=newProM;page=page1;intcount=0;for(intj=i;jL;j+)if(paget.num=pj.num)break;当前页面再次被访问时循环结束elseco

21、unt+;否贝Ucount+1returncount;返回count的值intmain()intc;intm=0,t=0;floatn=0;PropL;m=Input(m,p);调用input函数，返回m值cout5|M3)cout内存块m须在35之间，请重新输入m:elsebreak;while(1);Pro*page=newProM;dofor(inti=0;iM;i+)初试化页面基本情况pagei.num=O;pagei.time=m-1-i;i=0;cout1:FIFO页面置换endl;cout2:LRU页面置换endl;cout3:OPT页面置换endl;cout按其它键结束程序；c

22、;system(cls);if(c=1)/FIF0页面置换n=0;endl;endl;w*coutendl;coutendl;coutcoutFIFO算法页面置换情况如下*endl;while(i=0)coutpi.numcout不缺页endl;i+;/i加1else/当前页不在内存中if(t=M)t=0;elsen+;paget.num=pi.num;coutpi.numprint(page);t+;i+;/缺页次数加1/把当前页面放入内存中/打印当前页面/下一个内存块/指向下一个页面cout缺页次数：n缺页率：n/mendl;if(c=2)/LRU页面置换n=0;endl;endl;end

23、l;cout*coutendl;coutLRU算法页面置换情况如下coutendl;cout*while(i=0)/如果已在内存块中paget.time=O;把与它相同的内存块的时间置0for(a=0;aM;a+)if(a!=t)pagea.time+;其它的时间加1coutpi.numcout不缺页endl;else如果不在内存块中n+;/缺页次数加1t=Max(page);返回最近最久未使用的块号赋值给tpaget.num=pi.num;paget.time=0;coutpi.numprint(page);for(a=0;aM;a+)进行替换/替换后时间置为0其它的时间加1if(a!=t)

24、pagea.time+;i+;if(c=3)/0PT页面置换n=0;endl;:*coutendl;coutOPT算法置换情况如下:endl;coutendl;cout*endl;while(i=0)如果已在内存块中coutpi.num;cout不缺页endl;i+;else/如果不在内存块中inta=0;for(t=0;tM;t+)if(paget.num=0)a+;记录空的内存块数if(a!=0)/有空内存块intq=M;for(t=0;tt)q=t;把空内存块中块号最小的找出来pageq.num=pi.num;n+;coutpi.numprint(page);i+;elseinttemp=O,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;while(c=1|c=2|c=3);return0;