页面置换算法模拟程序课程设计报告

1、*学院计算机科学系课程设计报告设计名称：软件课程设计设计题目：页面置换算法模拟程序学生学号：*专业班级：学生姓名:学生成绩:指导教师（职称）：课题工作时间：2010.5.31至2010.6.11说明：1、报告中的任务书、进度表由指导教师在课程设计开始前填写并发给每个学生；四、五两项（中英文摘要）由学生在完成综合设计后填写。2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。3、指导教师评语一栏由指导教师就学生在整个设计期间的平时表现、设计完成情况、报告的质量及答辩情况，给出客观、全面的评价。4、所有学生必须参加课程设计的答辩环节，凡不参加答辩者，其成绩一律按不及格处理。答辩小组成员

2、应由2人及以上教师组成。5、报告正文字数一般应不少于3000字，也可由指导教师根据本门综合设计的情况另行规定。6、平时表现成绩低于6分的学生，取消答辩资格，其本项综合设计成绩按不及格处理。计算机科学系课程设计任务书学生姓名学专业*口*厶计算机科学与技术08级2班号班级设计题目页面置换算法模拟程序内容概要：编制页面置换算法的模拟程序，并测试。文献资料：王渊博哈夫曼编码的另一种实现算法J安徽教育学院学报2009(6)严蔚敏吴伟民数据结构M高等教育2004设计要求：1任意性：用户输入任意的字符串，系统自动给出每个字符的哈夫曼编码和对应的哈夫曼树2.友好性：界面要友好，输入有提示，尽量展示人性化3可读

3、性：源程序代码清晰、有层次4健壮性：用户输入非法数据时，系统要及时给出警告信息工作期限：设计工作自2010年5月31日至2010年6月11日止。指导教师：系主任：日期：2010年5月28日计算机科学系课程设计进度安排表专业：姓名：学号：日期内容备注5月31日6月1日分析题目，查阅相关资料6月2日6月3日拟定整体方案，编写程序6月4日6月6日程序编写6月7日6月8日调试程序6月9日6月10日整理报告6月11日6月11日答辩月日月日月日月日月日月日月日月日月日月日月日月日月日月日月日月日月日月日指导教师签名：2010年5月28日指导教师评语答辩记录表学生姓名：学号：班级：答辩地点：答辩内容记录：答

4、辩成绩合计分值各项分值评分标准实际得分合计得分备注2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。答辩小组成员（签字）：2010年6月11日成绩评定表学生姓名：学号：班级：类别合计分值各项分值评分标准实际得分合计得分备注平时表现1010按时参加设计指导，无违反纪律情况。完成情况3020按设计任务书的要求完成了全部任务，能完整演示其设计内容，符合要求。10能对其设计内容进行详细、完整的介绍，并能就指导教师提出的问题进行正确的回答。报告质量3510报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严

5、谨合理；报告字数符合相关要求，工整规范，整齐划一。5课题背景介绍清楚，综述分析充分。5设计方案合理、可行，论证严谨，逻辑性强，具有说服力。5符号统；图表完备、符合规范要求。5能对整个设计过程进行全面的总结，得出有价值的结论或结果。5参考文献数量在2篇以上，格式付合要求，在正文中正确引用。答辩情况2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。总评成绩：分指导教师：（签字）日期：2010年6月15日摘要操作系统(英语；OperatingSystem,简称OS)是一管理电脑硬件与软件资源的程序，同时也是

6、计算机系统的内核与基石。操作系统身负诸如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统是管理计算机系统的全部硬件资源包括软件资源及数据资源;控制程序运行;改善人机界面;为其它应用软件提供支持等,使计算机系统所有资源最大限度地发挥作用,为用户提供方便的、有效的、友善的服务界面。操作系统是一个庞大的管理控制程序,大致包括5个方面的管理功能:进程与处理机管理、作业管理、存储管理、设备管理、文件管理。在地址映射过程中,若在页面中发现所要访问的页面不再内存中,则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存,以便为即将

7、调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法(ReplacementAlgorithms)。A.关键词：操作系统；OPT页面置换算法；FIFO先进先出的算法；LRR最近最少使用算；LFR最少访问页面算法;NUR最近最不经常使用算法AbstractOperatingsystem(inEnglish;OperatingSystem,referredtoasOS)isacomputerhardwareandsoftwareresourcesmanagementprocedures,butalsothecoreandfoundationofthecomputersystem.Whoa

8、rechargedwithoperatingsystemssuchasmemorymanagementandallocation,supplyanddemanddeterminethepriorityofsystemresources,controlinputandoutputdevices,operationandmanagementofnetworkfilesystemsandotherbasicservices.Theoperatingsystemismanagingallthehardwareresourcesofcomputersystemsincludingsoftwarereso

9、urcesanddataresources;controlprogramisrunning;toimprovehuman-machineinterface;providesupportforotherapplications,sothatcomputersystemsplayaroleinmaximizingallresourcestoprovideuserswithconvenienteffective,friendlyserviceinterface.Operatingsystemisahugemanagementcontrolprocedures,includingthefiveaspe

10、ctsofgeneralmanagementfunctions:processandprocessormanagement,operationsmanagement,storagemanagement,devicemanagement,documentmanagement.Intheaddressmappingprocess,iffoundtobeinthepagetoaccessthepagenolongerinmemory,thengenerateapagefault.Whenapagefaultoccurstheoperatingsystemmustselectapageinmemory

11、oftheiroutofmemoryinordertobetransferredtothepagetomakeroom.Thepageusedtoselectoutwhattherulesarecalledpagereplacementalgorithm(ReplacementAlgorithms).Keywords：Operatingsystem;FirstInputFirstOutput;LeastRecentlyUsed;OPT;LeastFrequentlyUsed;NUR西安文理学院计算机科学系课程设计报告- I-目录第一章课题背景.x关于页面置换算法.x第二章设计简介及设计方案论述

12、.x程序运行平台.xTOC o 1-5 h z程序的主要功能xXXXXx第三章详细设计.xXXXXxXXXXx第四章设计结果及分析.xXXXXxXXXXxXXXXx总结x HYPERLINK l bookmark26 o Current Document 致谢x HYPERLINK l bookmark28 o Current Document 参考文献x附录主要程序代码x西安文理学院计算机科学系课程设计报告- -第一章课题背景关于页面置换算法页面置换算法及其分类在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存

13、，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。常见的置换算法有：1.最佳置换算法(OPT)(理想置换算法)2先进现出置换算法(FIFO)：最近最久未使用(LRU)算法Clock置换算法(LRU算法的近似实现)5最少使用(LFU)置换算法6.页面缓冲置换算法关于页面置换算法模拟程序问题的产生在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业全部装入内存方能运行，但是有两种情况：(1)有的作业很大，不能全部装入内存，致使作业无法运行；(2)有大量作业要求运行，但内存容量不足以容纳所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两个问题。

14、从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法(ReplacementAlgorithms)。进而页面置换算法模拟程序能客观的将其工作原理展现在我们面前。第二章设计简介及设计方案论述2.1程序运行平台VC+6.0具体操作如下：在VC+6.0的环境下准备用时钟函数调用库函数(#include)、取时钟时间并存入t调用库函数(t二time(NULL)、用时间t初始化随机数发生器调用库函数(srand(t)返回一个110之间的随机数(x=rand()%10+1)。编写三种算法。2.2程序的主要功能随机产生页面用随机数方法产生页面走向，页面走向长度为L。FIF

15、O算法该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。LRU算法在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很有可能在未来较长的一段时间内不会被用到。这个思想提示了一个可以实现的算法：在缺页发生时，淘汰掉最久未使用的页。2.2.4LFR算法在缺页中断发生时，置换未使用时间最长的页面。这个策略称为LRU（LeastRecentlyUsed，最近最少使用）页面置换算法2.2.5NUR算法NRU在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。只要在页表中增设一个访问位即可实现。当某页被访问时，访问位置

16、1。否则，访问位置0。系统周期性地对所有引用位清零。当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰。如果引用位全0或全1,NRU算法退化为FIFO算法。2.3总体设计2.31结构图入口输入页面数输入算法产生随机数J丿FIFO先进ALRR最近最OPT最佳淘LFR最少访NUR最近最先出算法V丿少使用算VJ%Ztr/rS_l汰算法算L)问页面算)不经常使输出命中率4.2主要的函数k)Input(intm,PropL)(打印页面走向状态);voidprint(Pro*page1)(打印当前的页面)；intSearch(inte,Pro*page1)(寻找内存块中与e相同的块号)；intMax(P

17、ro*pagel)(寻找最近最长未使用的页面)；intCount(Pro*page1,inti,intt,PropL)(记录当前内存块中页面离下次使用间隔长度)；intmain()(主函数)；.随机数发生器#include#include/准备用时钟函数调用库函数t=time(NULL);/取时钟时间并存入t调用库函数srand(t);/用时间t初始化随机数发生器调用库函数x=rand()%10+1;/返回一个110之间的随机数第三章详细设计FIFO（先进先出）设计原理：需要进行页面置换，即把内存中装入最早的那个页面淘汰换入当前的页面。算法流程图开始示Yi+页面走向存入数组p中，内存块用pag

18、e表初始化为0当刖p中弟i个元素是否已在内存NPage是否有空卄Y把page中取先装入的页面置换出去.i+把pi的内容直接装入最上面一个空内存块，i+N输出当前内存块状态结束图4-1FIFO算法流程图代码：if(c=l)/FIFO页面置换n=0;*coutendl;coutendl;coutFIFO算法页面置换情况如下:endl;coutendl;cout*endl;while(i=O)/当前页面在内存中coutpi.num;/输出当前页pi.num西安文理学院计算机科学系课程设计报告存中cout不缺页endl;i+；/i加1else/当前页不在内存中if(t=M)t=0;elsen+;/缺页

19、次数加1paget.num=pi.num;/把当前页面放入内coutpi.num;print(page);/打印当前页面t+;/下一个内存块i+;/指向下一个页面cout缺页次数：n缺页率：n/mendl;LRU（最近最久未使用）设计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最近一段时间也不会被访问。算法流程图：西安文理学院计算机科学系课程设计报告- -n=0;cout*endl;coutendl;coutLRU算法页面置换情况如下:endl;cou

20、tendl;cout*endl;while(i=0)/如果已在内存块中paget.time=0;/把与它相同的内存块的时间置0西安文理学院计算机科学系课程设计报告/其它的时间加1/如果不在内存块中/返回最近最久未使用的块号/进行替换/替换后时间置为0/其它的时间加1缺页率：n/mendl;for(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

21、(a!=t)pagea.time+;i+;cout缺页次数：nOPT（最佳置换算法）设计原理：需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现在最远的页面换出。西安文理学院计算机科学系课程设计报告- -代码：endl;endl;图4-3OPT流程图if(c=3)/OPT页面置换n=0;cout*coutendl;coutOPT算法置换情况如下：endl;coutendl;cout*while(i=0)/如果已在内存块中coutpi.num;cout不缺页endl;i+;else/如果不在内存块中inta=0;for(t=0;tM;t+)if(paget.num=0)a+;/记录空

22、的内存块数if(a!=0)/有空内存块intq=M;for(t=0;tt)q=t;/把空内存块中块号最小的找出来pageq.num=pi.num;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缺页率：n/mentsandSettIngsAdAinistra

23、tor桌面Debugos.eze输入实际页面走向长度L15entsandSettingsAdinistrator桌面Debugos.eze瞬|麟雅蹿邂典25实际就面長度须在1520;请重ffWAL：图5-6输入数据25后输出图输入数据18：c*C:DocuentsandSettingsAdinistrator桌面Debugos.eze面须须7存贝度度：内际用卖E-E-机可只賁随入W际留输走在在页両1515151L到；牙三00(医229m0麹4LL61I1AI1A820?=二B-二B-_:幫石0:27mm-二E-二E二聾7一一_33罷写15151黴可可55-序面须须7存换奂奂程际4用雜頁面面机可

24、血血页體键天贾随入块块FOUS诬它W际留聾存FILROP其塁岛两1:2:3:按图5-8输出图进入FIFO页面置换：*C:DocuentsandSettin.gsAdAn.istrator桌面ID71081010献贡次数：15l：FIFOEfLP=lru面胃幹OPT页面番險其它犍纟彝FIFO算法页面置换情況如下:3313缺贡率：0.8333337000790079100不缺贡9103191032103不缺页12731276276不缺贡8578518515121021043图5-9FIFO的输出图选2，进入LRU页面置换：710107810107000ocusentsamettingsAdMini

25、stratorXDebugXoP7900711131104缺页次数：1679100不缺页791031910319231102311027610276108?不缺页6586581：FIFO贝面e：lru面當按其它键纟害缺页率：0.888889LRU算法贡面置换情況如下:图5-10LRU的输出图输入3，进入OPT页面置换：图5-11OPT的输出图通过对页面置换算法模拟程序的程序设计，让我对虚拟页式存储管理有了更深的了解。刚开始拿到这个题目觉得很难，不知道该怎么下手，因为是自己第一次用C语言编写操作系统程序。但是搞懂了页面置换的思想以后，对编程就有了一定的思路。经过几天的编写，程序也终于写出来啊。但是却遇到了许多困难，程序的调试也出现了许多的错误。但是经过几次上机