1、页面淘汰算法课程设计*学院 计算机科学系课程设计报告设计名称： 软件课程设计 设计题目： 页面置换算法模拟程序 学生学号： * 专业班级： 学生姓名： 学生成绩： 指导教师（职称）： 课题工作时间： 摘 要操作系统（英语；Operating System，简称OS）是一管理电脑硬件与软件资源的程序，同时也是计算机系统的内核与基石。操作系统身负诸如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统是管理计算机系统的全部硬件资源包括软件资源及数据资源;控制程序运行;改善人机界面;为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用
2、，为用户提供方便的、有效的、友善的服务界面。操作系统是一个庞大的管理控制程序，大致包括5个方面的管理功能:进程与处理机管理、作业管理、存储管理、设备管理、文件管理。在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内 存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法（Page-Replacement Algorithms）。 A. 关键词：操作系统；OPT页面置换算法; FIFO先进先出的算法；LRR最近最少使用算;LFR最少访问页面算法;NUR最近最不经常使用算法AbstractOper
3、ating 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 th
4、e 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
5、 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 g
6、eneral 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 th
7、e 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 Recent
8、ly 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页面置换算法及其分类在地址映射过程中，若在页面中发现所要访问的页面
9、不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内 存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。 常见的置换算法有： 1最佳置换算法（OPT）（理想置换算法） 2先进现出置换算法（FIFO）： 3最近最久未使用（LRU）算法 4Clock置换算法（LRU算法的近似实现） 5最少使用（LFU）置换算法 6页面缓冲置换算法1.1.2关于页面置换算法模拟程序问题的产生在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业全部装入内存方能运行，但是有两种情况：（1） 有的作业很大，不能全部装入内存，致使作业无法运行；（2）
10、有大量作业要求运行，但内存容量不足以容纳所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两个问题。从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法（Page-Replacement Algorithms）。进而页面置换算法模拟程序能客观的将其工作原理展现在我们面前。第二章 设计简介及设计方案论述2.1程序运行平台VC+6.0具体操作如下：在VC+6.0的环境下准备用时钟函数调用库函数（#include ）、 取时钟时间并存入t调用库函数（t=time(NULL)）、 用时间t初始化随机数发生器调用 库函数（srand(t)返回一个110
11、之间的随机数（x=rand( )%10+1） 。编写三种算法。2.2程序的主要功能2.2.1随机产生页面用随机数方法产生页面走向，页面走向长度为L。2.2.2 FIFO算法 该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。2.2.3 LRU算法在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很有可能在未来较长的一段时间内不会被用到。这个思想提示了一个可以实现的算法：在缺页发生时，淘汰掉最久未使用的页。2.2.4LFR算法在缺页中断发生时，置换未使用时间最长的页面。这个策略称为LRU（Least Recently Use
12、d，最近最少使用）页面置换算法2.2.5NUR算法NRU在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。只要在页表中增设一个访问位即可实现。当某页被访问时，访问位置1。否则， 访问位置0。系统周期性地对所有引用位清零。当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰。如果引用位全0或全1，NRU算法退化为FIFO算 法。2.3总体设计2.31结构图输出命中率4.2 主要的函数Input(int m,Pro pL)（打印页面走向状态）；void print(Pro *page1)（打印当前的页面）；int Search(int e,Pro *page1 )（寻找内存块中与
13、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.1 FIFO（先进先出）设计原理：需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入
14、当前的页面。算法流程图开始页面走向存入数组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; coutendl; cout FIFO算法页面置换情况如下: endl; coutendl; cout * endl; while(i=0)/当前页面在内存中 coutpi.num ;/输出当前页pi.num cout不缺页endl; i
15、+;/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; 4.2 LRU（最近最久未使用）设计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最近一段时间也不会被访问。 开始算法流程图：页面走
16、向存入数组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; coutendl; cout LRU算法页面置换情况如下: endl; coutendl; cout * endl; while(i=0) /如果已在内存块中 paget.time=0; /把与它相同的内存块的时间置0 for(a=0;aM;a+) if(a!=t)page
17、a.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/mendl; 4.3 OPT（最佳置换算法）设计原理：需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现
18、在最远的页面换出。流程图： 开始页面走向存入数组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; coutendl; cout OPT算法置换情况如下:endl; coutendl; cout * endl; while(i=0) /如果已在内存块中 coutpi.num ; cout不缺页endl; i+;
19、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+; else int temp=0,s; for(t=0;tM;t+) /寻找内存块中下次使用离现在最久的页面 if(tempCount(page,i,t,p) temp=Count(page,i,t,p); s=t; /把找到的块号赋给s page
20、s.num=pi.num; n+; coutpi.num ; print(page); i+; cout缺页次数：n 缺页率：n/mendl; 第四章 设计结果及分析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的输出图总 结通过对页面置换算法模拟程序的程序设计，让我对虚拟页式
21、存储管理有了更深的了解。刚开始拿到这个题目觉得很难，不知道该怎么下手，因为是自己第一次用C语言编写操作系统程序。但是搞懂了页面置换的思想以后，对编程就有了一定的思路。经过几天的编写，程序也终于写出来啊。但是却遇到了许多困难，程序的调试也出现了许多的错误。但是经过几次上机操作，在老师的指导和帮助下，程序最终还是完成了。通过这次的程序设计，让我对C语言有了更深一步的了解和认识，编程能力也有了提高，我认到学好计算机要重视实践操作，只有真正动手了才知道自己还有那些不足之处。致 谢本次课程设计能顺利完成，感谢学校的大力支持,感谢计算机科学系为我们提供实练的机会,感谢老师的细心教导。在这次课程设计中，我学
22、到了很多东西，对C语言编写操作系统有了一定的认识，自己的编程能力也有了提高。虽然在课程设计中我遇到了很多的困难， 但是也得到了很多人的帮助，在他们的帮助下，我才能顺利完成自己的课程设计。我要感谢我的老师和同学们，感谢他们的帮助，在我迷茫的时候给了我许多好的建议，有了他们的帮助，我的程序才能顺利的完成。 参考文献参考文献采用顺序编码制格式著录。主要责任者，三名以内的，全部列出；超过三名时，后面加“等.”字样。参考文献类型及标识：参考文献类型专著论文集报纸文章期刊文章学位论文报告标准专利文献类型标识MCNJDRSP其他未作说明的文献，建议采用单字母“Z”。参考文献编排格式（注意严格使用格式中的符号
23、，特别注意区分“，”与“.”）：（1）对于专著、论文集、学位论文、报告，格式如下：序号 主要责任者文献题名X出版地：出版者，出版年起止页码其中X代表文献类型标识。（2）对于期刊文章，格式如下：序号 主要责任者文献题名J刊名，年，卷（期）：起止页码（3）对于报纸文章，格式如下：序号 主要责任者文献题名N报纸名，出版日期（版次）（4）对于国际、国家标准，格式如下：序号 标准编号，标准名称S （5）对于专利，格式如下：序号 专利所有者专利题名P专利国别：专利号，出版日期（6）对于未定义类型的文献序号 主要责任者文献题名Z出版地：出版者，出版年课程设计资料的组成 资料组成及装订按如下标准：封面 课程设计任务书 课程设计进度表指导教师评语答辩记录表成绩评定表摘要 目录 正文 结束语 谢辞 参考文献。注意：页码从第一章开始编且居中
