操作系统课程设计任务书--页面置换算法.docVIP

课程设计任务书 学 院 信息学院 专 业 计算机科学与技术 学 生 姓 名 学 号 题 目 页面置换算法 内容及要求： 内容： 读者与写者问题（进程同步问题） 实验目的：深入掌握内存调度算法的概念原理和实现方法。 设计要求：编写程序实现： 1）先进先出页面置换算法（FIFO） 2）最近最久未使用页面置换算法（LRU） 3）最佳置换页面置换算法（OPT） 专题：设计一个虚拟存储区和内存工作区,编程序演示以上三种算法的具体实 现过程,并计算访问命中率。 演示页面置换的三种算法。 任务交付：1.程序源代码； 2课程设计论文及电子文档。 进度安排：16周——确定题目，查找资料，上机编程； 20周——上机编程调试，验收答辩,提交课程序设计报告书。 指导教师（签字）： 年 月 日 学院院长（签字）： 年 月 日 目录 一、 课程设计目的及要求 2 二、相关知识 2 三、题目分析 3 四、概要设计 3 五、代码及流程 4 六、运行结果 9 七、设计心得 10 参考文献 11 课程设计目的及要求 页面置换算法 实验目的：深入掌握内存调度算法的概念原理和实现方法。 设计要求：编写程序实现： 1）先进先出页面置换算法（FIFO） 2）最近最久未使用页面置换算法（LRU） 3）最佳置换页面置换算法（OPT） 专题：设计一个虚拟存储区和内存工作区,编程序演示以上三种算法的具体实 现过程,并计算访问命中率。 演示页面置换的三种算法。 相关知识 1 先进先出（FIFO）算法 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。 2 最近最久未使用（LRU）算法 FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。 3 最佳（Optimal）算法 最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰的页面，将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是将来最长时间内不再访问的，因而该算法时无法实现的，但可以利用该算法评价其他算法。 三、题目分析 熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。页面置换算法是虚拟存储管理实现的关键，通过本次课程设计理解内存页面调度的机制，在模拟实现FIFO、LRU和OPT几种经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。 四、概要设计 4.1进入系统模块。进入登陆界面，输入内存页面数和实际页数。 int Input(int x,Pro p[X]) { cout请输入实际页数：; do { cin; if(xX)cout数目太多，请重试endl; else break; } while(1); void print(Pro* page1) { Pro*page=new Pro[Y];//定义一个指针 page=page1; for(int i=0;i;i++) if(page[i].num==-1) cout ; else coutpage[i].num ; coutendl; } 4.3菜单选择模块。选择相应的页面的置换方式，选择相应的字母，进入相应的功能。 4.4算法模块。选择相应的页面置换算法。 4.5显示输出模块。显示页面被置换的情况。 4.6缺页次数和缺页率模块。计算页面号输入的结果。 4.7退出系统模块。退出置换页面。 五、代码及流程 #includeiostream.h #define X 40 int Y; struct Pro//内存页的结构体 { int num,time; }; int Inpu