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

*学院 计算机科学系课程设计报告设计名称： 软件课程设计 设计题目： 页面置换算法模拟程序 学生学号： * 专业班级： 学生姓名： 学生成绩： 指导教师（职称）： 课题工作时间： 2010.5.31至 2010.6.11 说明：1、报告中的任务书、进度表由指导教师在课程设计开始前填写并发给每个学生；四、五两项（中英文摘要）由学生在完成综合设计后填写。2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。3、指导教师评语一栏由指导教师就学生在整个设计期间的平时表现、设计完成情况、报告的质量及答辩情况，给出客观、全面的评价。4、所有学生必须参加课程设计的答辩环节，凡不参加答辩者，其成绩一律按不及格处理。答辩小组成员应由2人及以上教师组成。5、报告正文字数一般应不少于3000字，也可由指导教师根据本门综合设计的情况另行规定。6、平时表现成绩低于6分的学生，取消答辩资格，其本项综合设计成绩按不及格处理。计算机科学系课程设计任务书学生姓 名*学 号*专业班级计算机科学与技术08级2班设计题目页面置换算法模拟程序内容概要：编制页面置换算法的模拟程序,并测试。文献资料：王渊博 哈夫曼编码的另一种实现算法 J 安徽教育学院学报2009(6) 严蔚敏.吴伟民 数据结构M 高等教育2004设计要求： 1.任意性：用户输入任意的字符串，系统自动给出每个字符的哈夫曼编码和对应的哈夫曼树2.友好性：界面要友好，输入有提示，尽量展示人性化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 日指导教师评语指导教师： （签字）日 期： 2010 年 6 月 10 日答辩记录表学生姓名： 学号： 班级： 答辩地点： 答辩内容记录：答辩成绩合计分值各项分值评分标准实际得分合计得分备注2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。答辩小组成员（签字）： 2010 年 6 月 11 日成绩评定表学生姓名： 学号： 班级： 类别合计分值各项分值评分标准实际得分合计得分备注平时表现1010按时参加设计指导，无违反纪律情况。完成情况3020按设计任务书的要求完成了全部任务，能完整演示其设计内容，符合要求。10能对其设计内容进行详细、完整的介绍，并能就指导教师提出的问题进行正确的回答。报告质量3510报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严谨合理；报告字数符合相关要求，工整规范，整齐划一。5课题背景介绍清楚，综述分析充分。5设计方案合理、可行，论证严谨，逻辑性强，具有说服力。5符号统一；图表完备、符合规范要求。5能对整个设计过程进行全面的总结，得出有价值的结论或结果。5参考文献数量在2篇以上，格式符合要求，在正文中正确引用。答辩情况2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。总评成绩： 分 指导教师： （签字）日 期： 2010 年 6 月 15 日摘 要操作系统（英语；Operating System，简称OS）是一管理电脑硬件与软件资源的程序，同时也是计算机系统的内核与基石。操作系统身负诸如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统是管理计算机系统的全部硬件资源包括软件资源及数据资源;控制程序运行;改善人机界面;为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用，为用户提供方便的、有效的、友善的服务界面。操作系统是一个庞大的管理控制程序，大致包括5个方面的管理功能:进程与处理机管理、作业管理、存储管理、设备管理、文件管理。在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内 存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法（Page-Replacement Algorithms）。 A. 关键词：操作系统；OPT页面置换算法; FIFO先进先出的算法；LRR最近最少使用算;LFR最少访问页面算法;NUR最近最不经常使用算法AbstractOperating system (in English; Operating System, referred to as OS) is a computer hardware and software resources management procedures, but also the core and foundation of the computer system. Who are charged with operating systems such as memory management and allocation, supply and demand determine the priority of system resources, control input and output devices, operation and management of network file systems and other basic services. The operating system is managing all the hardware resources of computer systems including software resources and data resources; control program is running; to improve human-machine interface; provide support for other applications, so that computer systems play a role in maximizing all resources to provide users with convenient effective, friendly service interface. Operating system is a huge management control procedures, including the five aspects of general management functions: process and processor management, operations management, storage management, device management, document management. In the address mapping process, if found to be in the page to access the page no longer in memory, then generate a page fault. When a page fault occurs the operating system must select a page in memory of their out of memory in order to be transferred to the page to make room. The page used to select out what the rules are called page replacement algorithm (Page-Replacement Algorithms).Keywords：Operating system; First Input First Output; Least Recently Used;OPT; Least Frequently Used;NUR目 录第一章 课题背景.x1.1关于页面置换算法.x第二章设计简介及设计方案论述 . x2.1 程序运行平台.x 2.2 程序的主要功能.x 2.3 XXXX .x 第三章详细设计. x3.1 XXXX .x 3.1 XXXX .x 第四章设计结果及分析. x4.1 XXXX .x 4.2 XXXX .x 4.3 XXXX .x 总 结 .x 致 谢 .x 参考文献 .x 附录 主要程序代码 .x 第一章 课题背景1.1 关于页面置换算法1.1.1页面置换算法及其分类在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内 存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。 常见的置换算法有： 1最佳置换算法（OPT）（理想置换算法） 2先进现出置换算法（FIFO）： 3最近最久未使用（LRU）算法 4Clock置换算法（LRU算法的近似实现） 5最少使用（LFU）置换算法 6页面缓冲置换算法1.1.2关于页面置换算法模拟程序问题的产生在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业全部装入内存方能运行，但是有两种情况：（1） 有的作业很大，不能全部装入内存，致使作业无法运行；（2） 有大量作业要求运行，但内存容量不足以容纳所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两个问题。从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法（Page-Replacement Algorithms）。进而页面置换算法模拟程序能客观的将其工作原理展现在我们面前。第二章 设计简介及设计方案论述2.1程序运行平台VC+6.0具体操作如下：在VC+6.0的环境下准备用时钟函数调用库函数（#include <time.h>）、 取时钟时间并存入t调用库函数（t=time(NULL)）、 用时间t初始化随机数发生器调用 库函数（srand(t)返回一个110之间的随机数（x=rand( )%10+1） 。编写三种算法。2.2程序的主要功能2.2.1随机产生页面用随机数方法产生页面走向，页面走向长度为L。2.2.2 FIFO算法 该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。2.2.3 LRU算法在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很有可能在未来较长的一段时间内不会被用到。这个思想提示了一个可以实现的算法：在缺页发生时，淘汰掉最久未使用的页。2.2.4LFR算法在缺页中断发生时，置换未使用时间最长的页面。这个策略称为LRU（Least Recently Used，最近最少使用）页面置换算法2.2.5NUR算法NRU在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。只要在页表中增设一个访问位即可实现。当某页被访问时，访问位置1。否则， 访问位置0。系统周期性地对所有引用位清零。当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰。如果引用位全0或全1，NRU算法退化为FIFO算 法。2.3总体设计2.31结构图入口输入页面数输入算法产生随机数FIFO先进先出算法LRR最近最少使用算法OPT最佳淘汰算法算法LFR最少访问页面算法算法NUR最近最不经常使用算法算法输出命中率4.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 <stdlib.h> #include <time.h> /准备用时钟函数调用库函数t=time(NULL);/取时钟时间并存入t调用库函数srand(t);/用时间t初始化随机数发生器调用库函数x=rand( )%10+1;/返回一个110之间的随机数第三章 详细设计4.1 FIFO（先进先出）设计原理：需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当前的页面。算法流程图开始页面走向存入数组p中，内存块用page表示初始化为0当前p中第i个元素是否已在内存中 i+ Y Page是否有空 N N把pi的内容直接装入最上面一个空内存块，i+把page中最先装入的页面置换出去.i+ Y 输出当前内存块状态 结束图4-1FIFO算法流程图代码：if(c=1)/FIFO页面置换 n=0;cout<<" * "<<endl;cout<<endl; cout<<" FIFO算法页面置换情况如下: "<<endl;cout<<endl; cout<<" * "<<endl; while(i<m) if(Search(pi.num,page)>=0)/当前页面在内存中 cout<<pi.num<<" "/输出当前页pi.numcout<<"不缺页"<<endl;i+;/i加1 else /当前页不在内存中 if(t=M)t=0; else n+;/缺页次数加1 paget.num=pi.num; /把当前页面放入内存中 cout<<pi.num<<" " print(page); /打印当前页面 t+; /下一个内存块i+; /指向下一个页面 cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl; 4.2 LRU（最近最久未使用）设计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最近一段时间也不会被访问。 开始算法流程图：页面走向存入数组p中，内存块用page表示初始化为0当前p中第i个元素是否已在内存i+ Y NPage是否有空 Y N把pi的内容直接装入最上面一个空内存块，i+把page中最近最久未使用的页面置换出去.i+输出当前内存块状态 结束图4-2 LRU算法流程图代码：if(c=2)/LRU页面置换 n=0; cout<<" * "<<endl;cout<<endl; cout<<" LRU算法页面置换情况如下: "<<endl; cout<<endl;cout<<" * "<<endl; while(i<m) int a; t=Search(pi.num,page); if(t>=0) /如果已在内存块中 paget.time=0; /把与它相同的内存块的时间置0for(a=0;a<M;a+)if(a!=t)pagea.time+; /其它的时间加1 cout<<pi.num<<" "cout<<"不缺页"<<endl; else /如果不在内存块中 n+; /缺页次数加1 t=Max(page); /返回最近最久未使用的块号赋值给t paget.num=pi.num; /进行替换 paget.time=0; /替换后时间置为0 cout<<pi.num<<" "print(page);for(a=0;a<M;a+)if(a!=t)pagea.time+; /其它的时间加1 i+; cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl; 4.3 OPT（最佳置换算法）设计原理：需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现在最远的页面换出。流程图： 开始页面走向存入数组p中，内存块用page表示初始化为0当前p中第i个元素是否已在内存i+ YPage是否有空 N Y N把pi的内容直接装入最上面一个空内存块，i+把page中以后一段时间都不使用或是使用时间离现在最远的换出.i+输出当前内存块状态 结束图4-3 OPT 流程图代码： if(c=3) /OPT页面置换 n=0;cout<<" * "<<endl;cout<<endl;cout<<" OPT算法置换情况如下:"<<endl;cout<<endl;cout<<" * "<<endl; while(i<m)if(Search(pi.num,page)>=0) /如果已在内存块中 cout<<pi.num<<" "cout<<"不缺页"<<endl;i+;else /如果不在内存块中int a=0; for(t=0;t<M;t+)if(paget.num=0)a+; /记录空的内存块数if(a!=0) /有空内存块int q=M;for(t=0;t<M;t+)if(paget.num=0&&q>t)q=t; /把空内存块中块号最小的找出来pageq.num=pi.num;n+; cout<<pi.num<<" "print(page);i+;elseint temp=0,s;for(t=0;t<M;t+) /寻找内存块中下次使用离现在最久的页面if(temp<Count(page,i,t,p)temp=Count(page,i,t,p);s=t; /把找到的块号赋给spages.num=pi.num; n+; cout<<pi.num<<" " print(page); i+;cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl;第四章 设计结果及分析4.1实现结果程序在运行的情况下，进入主界面输入菜单，如图3-3所示：输入14：图4-5 输入14后的输出图输入25：图5-6输入数据25后输出图输入数据18：图5-7 输入数据18后的输出图输入数据：图5-8输出图选1，进入FIFO页面置换：图5-9 FIFO的输出图选2，进入LRU页面置换：图5-10 LRU的输出图输入3，进入OPT页面置换：图5-11 OPT的输出图总 结通过对页面置换算法模拟程序的程序设计，让我对虚拟页式存储管理有了更深的了解。刚开始拿到这个题目觉得很难，不知道该怎么下手，因为是自己第一次用C语言编写操作系统程序。但是搞懂了页面置换的思想以后，对编程就有了一定的思路。经过几天的编写，程序也终于写出来啊。但是却遇到了许多困难，程序的调试也出现了许多的错误。但是经过几次上机操作，在老师的指导和帮助下，程序最终还是完成了。通过这次的程序设计，让我对C语言有了更深一步的了解和认识，编程能力也有了提高，我认到学好计算机要重视实践操作，只有真正动手了才知道自己还有那些不足之处。致 谢本次课程设计能顺利完成，感谢学校的大力支持,感谢计算机科学系为我们提供实练的机会,感谢老师的细心教导。在这次课程设计中，我学到了很多东西，对C语言编写操作系统有了一定的认识，自己的编程能力也有了提高。虽然在课程设计中我遇到了很多的困难， 但是也得到了很多人的帮助，在他们的帮助下，我才能顺利完成自己的课程设计。我要感谢我的老师和同学们，感谢他们的帮助，在我迷茫的时候给了我许多好的建议，有了他们的帮助，我的程序才能顺利的完成。 参考文献参考文献采用顺序编码制格式著录。主要责任者，三名以内的，全部列出；超过三名时，后面加“等.”字样。参考文献类型及标识：参考文献类型专著论文集报纸文章期刊文章学位论文报告标准专利文献类型标识MCNJDRSP其他未作说明的文献，建议采用单字母“Z”。参考文献编排格式（注意严格使用格式中的符号，特别注意区分“，”与“.”）：（1）对于专著、论文集、学位论文、报告，格式如下：序号 主要责任者文献题名X出版地：出版者，出版年起止页码其中X代表文献类型标识。（2）对于期刊文章，格式如下：序号 主要责任者文献题名J刊名，年，卷（期）：起止页码（3）对于报纸文章，格式如下：序号 主要责任者文献题名N报纸名，出版日期（版次）（4）对于国际、国家标准，格式如下：序号 标准编号，标准名称S （5）对于专利，格式如下：序号 专利所有者专利题名P专利国别：专利号，出版日期（6）对于未定义类型的文献序号 主要责任者文献题名Z出版地：出版者，出版年课程设计资料的组成 资料组成及装订按如下标准：封面 课程设计任务书 课程设计进度表指导教师评语答辩记录表成绩评定表摘要 目录 正文 结束语 谢辞 参考文献。注意：页码从第一章开始编且居中