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

1、目录TOC o 1-5 h z HYPERLINK l bookmark6 o Current Document 1问题的提出2 HYPERLINK l bookmark8 o Current Document 关于页面置换算法模拟程序问题的产生2 HYPERLINK l bookmark10 o Current Document 任务分析2 HYPERLINK l bookmark12 o Current Document 2需求分析2 HYPERLINK l bookmark14 o Current Document 3方案设计3 HYPERLINK l bookmark16 o Curr

2、ent Document 4总体设计4 HYPERLINK l bookmark18 o Current Document 4.1程序N-S图4 HYPERLINK l bookmark20 o Current Document 主要的函数4 HYPERLINK l bookmark22 o Current Document 主要流程图及代码5FIFO（先进先岀）5LRU（最近最久未使用）6OPT（最佳置换算法）9 HYPERLINK l bookmark24 o Current Document 实现结果11 HYPERLINK l bookmark52 o Current Document

3、 5程序测试15 HYPERLINK l bookmark54 o Current Document 设计测试数据15 HYPERLINK l bookmark56 o Current Document 测试结果及分析16摘要随着计算机的普及人们的物质生活得到了极大的满足，人们在精神生活方面同样也需要提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠

4、性。由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果.本课程设计是学生学习完操作系统教程课程后，进行的一次全面的综合训练通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。关键词：编制页面置换算法模拟程序、打印页面、FIF0页面算法、LRU页面置换算法、OPT页面置换算法。引言1问题的提出关于页面置换算法模拟程序问题的产生在各种存储器管理方式中，有一个共同的特点，即它们都要求

5、将一个作业全部装入内存方能运行，但是有两种情况：（1）有的作业很大，不能全部装入内存，致使作业无法运行；（2）有大量作业要求运行，但内存容量不足以容纳所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两个问题。从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法（ReplacementAlgorithms）。进而页面置换算法模拟程序能客观的将其工作原理展现在我们面前。任务分析首先，定义宏变量，设置所占最大内存长度。编辑以时间为种子，初始化随即发生器。进行相关页面输入程序的编写以及页面的打印。尔后，寻找最近最近最久未使用的页面、记录当前内存块中

6、页面离下次使用间隔长度等相关程序的代码编写。最后，进行）FIFO、LRU、OPT三种算法的编写。2需求分析用随机数方法产生页面走向，页面走向长度为L。根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率；为简化操作，在淘汰一页时，只将该页在页表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。假定可用内存块和页表长度（作业的页面数）分别为m和k，初始时，作业页面都不在内存。随机数产生程序：inti,j;j二time(NULL);/取时钟时间srand(j);/以时钟时间x为种子，初始化随机数发生器cout输出随机数：;for(i=0;im;i+)pi.num=rand()%1

7、0+1;/产生1到10之间的随即数放到数组p中pi.time=0;coutpi.num;上述随机数发生函数产生的随机数为0.01.0,稍另变化就可得到0n1之间的随机数。程序开始时，应对变量Seed(实型)赋初值。根据页面置换算法的理论操作及要求，首先要进行页面长度的确定，定义结构体用以储存数据，进行主界面代码及FIFO、LRU、OPT页面置换算法代码的编写。3方案设计首先，定义宏变量，设置所占最大内存长度。编辑以时间为种子，初始化随即发生器。进行相关页面输入程序的编写以及页面的打印。其次，寻找最近最近最久未使用的页面、记录当前内存块中页面离下次使用间隔长度等相关程序的代码编写。最后，进行FI

8、FO、LRU、OPT三种算法的编写。.程序运行平台VC+6.0具体操作如下：在VC+6.0的环境下准备用时钟函数调用库函数(#include)、取时钟时间并存入t调用库函数(t二time(NULL)、用时间t初始化随机数发生器调用库函数(srand(t)返回一个110之间的随机数(x=rand()%10+1)。编写三种算法。4总体设计4.1程序N-S图程序开始输入选择项(进行判断)页面存在进入下一部操作此项不存在输入要输出的结果输出结果结束主要的函数Input(intm,PropL)(打印页面走向状态);voidprint(Pro*pagel)(打印当前的页面);intSearch(inte,

9、Pro*page1)(寻找内存块中与e相同的块号)；intMax(Pro*page1)(寻找最近最长未使用的页面)；intCount(Pro*page1,inti,intt,PropL)(记录当前内存块中页面离下次使用间隔长度)；intmain()(主函数)；.随机数发生器#include#include/准备用时钟函数调用库函数t=time(NULL);/取时钟时间并存入t调用库函数srand(t);/用时间t初始化随机数发生器调用库函数x=rand()%10+1;/返回一个110之间的随机数4.3主要流程图及代码FIFO（先进先出）设计原理：需要进行页面置换，即把内存中装入最早的那个页面淘

10、汰换入当前的页面。算法流程图图4-1FIFO算法流程图代码：if(c=l)/FIFO页面置换n=0;页面置换算法模拟程序cout*endl;coutendl;coutFIFO算法页面置换情况如下:endl;coutendl;cout*endl;while(i=O)/当前页面在内存中coutpi.num;/输出当前页pi.numcout不缺页endl;i+;/i加1else/当前页不在内存中if(t=M)t=0;elsen+;/缺页次数加1paget.num=pi.num;/把当前页面放入内存中coutpi.num;print(page);/打印当前页面t+;/下一个内存块i+;/指向下一个页面

11、cout缺页次数：n缺页率：n/mendl;LRU(最近最久未使用)设计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最近一段时间也不会被访问。图4-2LRU算法流程图代码：if(c=2)/LRU页面置换n=0;cout*endl;coutendl;coutendl;coutendl;coutendl;while(im)/把与它相同的内存块的时间/其它的时间加1/如果不在内存块中/返回最近最久未使用的块号/进行替换/替换后时间置为0/其它的时间加1缺页率

12、：n/m=0)paget.time=0;置0for(a=0;aM;a+)if(a!=t)pagea.time+;coutpi.num;cout不缺页endl;elsen+;/缺页次数加1t=Max(page);赋值给tpaget.num=pi.num;paget.time=0;coutpi.numprint(page);for(a=0;aM;a+)if(a!=t)pagea.time+;i+;cout缺页次数：npageq.num=pi.num;OPT（最佳置换算法）设计原理：需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现在最远的页面换出。图4-3OPT流程图代码：if(c=3

13、)/OPT页面置换n=0;cout*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;/把空内存块中块号最小的找出来n+;coutpi.num;print(page);i+;elseinttemp=0,s;for(t=0;tM;t+)/寻找内存块中下次使用离

14、现在最久的页面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/miiiistratorzDc叭图5-9FIFO的输出图315置换7910不缺贡9109101210不缺更12731276276不缺贡85785185151210选2,进入LRU页面置换:页面置换算法模拟程序II7192ia102219210LRU算法页面置换情况如下;E&1027啓&1087卜不缺页565S?421034龈页次数：直E缺

15、页率：B-888889pFIFOffig换hLHUg面置模5：optMeo險其它键纟彝程序孑79J.00不缺贡791031910319231102365S17?00图5-10LRU的输出图输入3,进入OPT页面置换:页面置换算法模拟程序C:UDCUMentsandZLiig;吕ncu：Lii：Lsizi7aizciE：jmluOPT算法置换情抚如下：卩7000p7908ks?iaaP不缺贡TOC o 1-5 h z79103U.71103*71102P-B不缺页h不缺页”61102B6182*不缺页E5182P-不缺页B3182P不缺页4182h.010182缺页率=快贝次数：121：FIFO

16、西面e：lbuH|P：optXh1图5-11OPT的输出图5程序测试5.1设计测试数据A142518；264B1C2测试结果及分析1）测试A结果及分析进入主菜单后输入14、25，显示输入不满足要求。输入18显示相关信息;输入2、6不满足要求，输入4显示出相关信息。2）测试结果及分析显示出FIFO页面置换算法的缺页信息及缺页率。3）测试C结果及分析显示出LRU页面置换算法的缺页信息及缺页率。4）测试D结果及分析显示出OPT页面置换算法的缺页信息及缺页率结论通过这次课程设计，不仅让我了解了页面置换算法，开始我一味的进行调试，急切的想侥幸调试出来，但由于没有进行深入的考虑，我调试了很久都没没有成功，

17、我仔细的分析题目，分析材料，在原由的基础上我进行了改正，我最后还是调试成功了，还是经过了一翻努力，这次操作系统实习，不仅让我对操作系统这门课程有了更深入的研究、对很多重要的概念有了巩固和掌握。通过努力，三个页面置换算法程序都已经完成，此时此刻，我心里多了些成就感。虽然自己所做的很少也不够完善，但毕竟也是努力的结果。主要有以下几点收获：1.通过对上网和看书查阅相关资料，使自己对VC+语言的基本框架有新的了解，加深了对可视化程序的认识。2在使用VC+语言来实现功能时，不像以往用的其他语言，它比较简练，更容易理解，实用性很强。3.先进先出页面置换和LRU以及OPT算法各有特点，但是实践起来却很大，使

18、自己对页面置换算法有了新的认识。一周半的课程设计就要结束了，不但对专业知识有了更深的理解，更使的自己认识到实践的重要性，理论、实践相结合才能达到很好的学习效果，特别是程序语言的学习。致谢本次课程设计能顺利完成，感谢学校的大力支持,感谢数学与计算机学院为我们提供实练的机会,感谢老师的细心教导。此次的课程设计收获很多，虽然经过了一段漫长而又痛苦的过程，但是自己还是完成了，这是与自己的努力是分不开的，但是自己在调试过程当中遇到的一些问题，自己仍然不懂，是在同学、老师的帮助下完成的，在这里还要再次对他们的付出表示崇高的敬意。陈天华编著谭浩强编著刘晋萍编著徐甲同等编著罗宇等编著张丽芬,刘利雄,王全玉编著

19、梁红兵、哲风屏、汤子瀛编著陈向群、杨芙清编著参考文献面向对象程序设计与VisualC+6.0教程C程序设计（第三版）C+入门经典面向对象程序设计与C+实现计算机操作系统教程操作系统操作系统实验教程计算机操作系统操作系统教程代码：#include#include#include#include#defineL20/页面走向长度最大为20intM;/内存块structPro/定义一个结构体intnum,time;Input(intm,PropL)打印页面走向状态coutvv请输入实际页面走向长度L(15v=Lv=20)：;docinm;if(m20llmvl5)coutvv实际页面长度须在1520

20、之间;请重新输入L：”;elsebreak;while(1);inti,j;j=time(NULL);取时钟时间srand(j);/以时钟时间x为种子，初始化随机数发生器coutvv输出随机数：;for(i=0;im;i+)pi.num=rand()%10+1;/产生1到10之间的随即数放到数组p中pi.time=0;coutpi.num;coutendl;returnm;voidprint(Pro*page1)打印当前的页面Pro*page=newProM;page=page1;for(inti=0;iM;i+)coutpagei.num;coutendl;intSearch(inte,Pr

21、o*page1)寻找内存块中与e相同的块号Pro*page=newProM;page=page1;for(inti=0;ivM;i+)if(e=pagei.num)returni;/返回i值return-1;intMax(Pro*page1)寻找最近最长未使用的页面Pro*page=newProM;page=page1;inte=page0.time,i=0;while(iM)/找出离现在时间最长的页面if(epagei.time)e=pagei.time;i+;for(i=O;ivM;i+)if(e=pagei.time)returni;/找到离现在时间最长的页面返回其块号return-1;

22、intCount(Pro*page1,inti,intt,PropL)/记录当前内存块中页面离下次使用间隔长度Pro*page=newProM;page=page1;intcount=0;for(intj=i;jM;if(M5|M3)coutvv内存块m须在35之间，请重新输入m：elsebreak;while(1);Pro*page=newProM;dofor(inti=0;ic;system(cls);if(c=1)/FIFO页面置换n=0;coutvv*vvendlcoutvvendl;coutvvFIFO算法页面置换情况如下:vvendl;coutvvcoutvvendl;*1*1*v

23、t*、t*、t*、t*1*i*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*i*i*i*!*Twvvendl;while(ivm)if(Search(pi.num,page)=0)/当前页面在内存中coutvvpi.numvvcoutvv不缺页vvendl;i+;/i加1/输出当前页pi.numelseif(t=M)t=0;elsen+;paget.num=pi.num;coutvvpi.numvvprint(page);t+;i+;/当前页不在内存中/缺页次数加1/把当前页面放入内存中/打印当前页面/下一个内存块/指向下一个页面coutvv缺页次数：vvnvv

24、缺页率：vvn/mvvendl;if(c=2)/LRU页面置换coutn=0;endl;endl;*Twcoutendl;coutLRU算法页面置换情况如下:coutendl;J一.tf*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*、t*、t*、t*、t*、t*、t*、t*、t*、t*vt*1*1*1*vT11rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*rr*while(i=0)如果已在内存块中paget.time=O;把与它相同的内存块的时间置0for(a=0;aM;a+)if(a!=t)pagea.time+;其它的时间加1coutpi.num;coutvv不缺页vvendl;else/如果不在内存块中n+;/缺页次数加1/进行替换/替换后时间置为0t=Max(page);返回最近最久未使用的块号赋值给tpaget.num=pi.num;paget.time=0;/其它的时间加1coutvvpi.numvvprint(page);for(a=0;avM;a+)i