1、操作系统课程设计全局页面替换算法操作系统课程设计（全局页面替换算法）长治学院 课程设计报告 课程名称: 操作系统课程设计 设计题目: 全局页面置换策略(FIFO算法) 系 别: 计算机系 专 业: 计算机科学与技术 组 别: 第六组 学生姓名: 李俊瑞 学 号: 08407112 起止日期: 2011年6月28日 2011年7月3日 指导教师: 王崇霞 1 、需求分析 . 1 1.1.课程设计题目. 1 1.2课程设计任务及要求 . 1 1.3课程设计思想. 1 1.4软、硬件运行环境及开发工具 . 1 2 、总体设计 . 2 2.1.系统总体结构流程图 . 2 2.2程序设计及模块介绍 .
2、2 3 、详细设计 . 3 3.1.数据结构设计. 3 3.2程序流程图 . 3 3.3具体代码设计. 3 4 、调试 . 7 5 、总结与体会 . 8 6、 参考文献 . 9 1、 需求分析 1.1课程设计题目 全局页面置换策略(先进先出算法) 1.2课程设计任务及要求 1、设计主界面以灵活选择某算法，实现先进先出算法(FIFO) 2、给出实现方案(包括数据结构和模块说明等) 3、画出程序的基本结构框图和流程图 4、分析说明每一部分程序的的设计思路 5、实现源代码 6、按期提交完整的程序代码和可执行程序 7、根据要求完成课程设计报告 8、总结 1.3课程设计思想 首先输入页面号，根据页面号的
3、次序采用FIFO算法来查看缺页状况和缺页率。先进先出算法(FIFO)总是先淘汰最先调入主存的页面。 设计目的:通过请求页式存储管理中页面置换算法模拟程序，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。 1.4软、硬件运行环境及开发环境 运行环境: a.CPU: Intel 575 2.00GHz b.20G以上硬盘空间 c.操作系统:Microsoft Windows XP 开发工具: Microsoft visual c+ 6.0 1 2(总体设计 2.1.系统总体结构流程图: 开始输入页面号主界面X=(1-4)X=0执行相应操作选择序号Xy是否输入页面号y/nn结束-1 系统
4、总体结构流程图 图22.2程序设计及模块介绍: 核心程序如下: for (j=1;jfront+j; if (ai=q-quek) coutai进入时已经命中!endl; hit+; f+; 模块介绍: 先进先出页面置换算法(FIFO)是基于程序局部性原理来考虑的，认为驻留时间最长的也不再使用得到可能性较大。FIFO算法的一种实现方法是系统设置一张具有n个元素的页面表，在程序中采用数组建立动态顺序表来进行代码的编写及模块的设计。 2 3、详细设计 3.1数据结构设计 #include #define MAX 100 #define flag typedef struct int front,r
5、ear; int queMAX; queue; int max(int a,int b) return (ab?a:b); 3.2程序流程图 先进先出页面置换算法(FIFO)的程序流程图如下: 开始输入页面号主界面X=1X=0执行FIFO算法选择序号Xy是否输入页面号y/nn结束图3-1程序流程图 3.3.具体代码设计 /先来先服务A void FIFO(queue *q,int a,int n) 3 int k,f=0,i,j,m; double hit=0; for (i=0;irear-q-front)3) for (j=1;jrear-q-front;j+)/未满时的命中判断 k=q-
6、front+j; if (ai=q-quek) coutai进入时已经命中!rear+; -queq-rear=ai; q else for (j=1;jfront+j; if (ai=q-quek) coutai进入时已经命中!front+; q-rear+; q-queq-rear=ai; for (m=q-front+1;mrear;m+) 4 coutquemt; coutendl; coutFIFO算法的命中率为(hit/n)*100%front=q-rear=-1; queue *p=new queue; p-front=p-rear=-1; queue *m=new queue;
7、 m-front=m-rear=-1; int data100; int i=0; int x; char y; cout请输入页面号(以结束):y; if(y57)&(y!=) cout请输入数字!endl; goto A; if(y=) break; x=y-48; datai=x; i+; while (1) cout *欢迎进行测试*endl; cout * *endl; cout * 1.先进先出算法(FIFO) *endl; cout * 2.最近最久未使用算法(LRU) *endl; cout * 3.最佳置换算法(OPT) *endl; 5 cout * 4.算法之间的对比分析
8、 *endl; cout * 5.结束本次算法 *endl; cout * *endl; cout *endl; char z; Y: cout请输入你需要的操作序号(1-5):z; switch (z) case 1: coutFIFO算法:endl; FIFO(q,data,i); break; case 2: coutLRU算法:endl; LRU(p,data,i); break; case 3: coutOPT算法:endl; OPT(m,data,i); break; case 4: cout1.先进先出置换算法(FIFO):选择最先进入内存的页面予以淘汰。 endl; cout2
9、.最近最久未使用算法(LRU):选择在最近一段时间内最久没有使用过的页，把它淘汰。 endl; cout3.最佳置换算法(OPT) :选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。endl; break; case 5:goto l; default:cout输入有误!endl; goto Y; l:cout是否重新输入页面号(y/n):ch; 6 4、调试 程序经编译链接后生成可执行文件，运行该程序进行调试，具体过程如下: 4.1输入页面号，如下图所示: 图4-1 输入页面号 4.2进入主界面，如下图所示: 图4-2 主界面 4.3输入序号1，选择FIFO置换算法，结果如下图所
10、示: 图4-3 FIFO置换算法 4.4输入序号0，退出程序，如下图所示: 7 图4-4 退出程序 5、总结与体会 FIFO的基本思想是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从对头删除一页，而从队尾加入缺页。或者借助辅助数组timemSIZE记录物理中对应页面的进入时间，每次需要置换时换出最小的页面。 通过这次课程设计，我对全局页面置换策略有了更深刻的认识，对于FIFO置换算法来讲，其淘汰的页面是最先调入主存的页面，它是基于程序局部性原理来考虑的。在课程设计的过程中也遇到不少困难，不过在同学和老师的帮助下勉强完成了自己的任务，不过自己在这方面的知
11、识和认识有了更进一步的了解。 最后，感谢王崇霞老师还有帮助过我的同学。在课程设计之初老师帮助我分析题目，以及实现方法，讲解整个软件的思路、过程，为以后的学习及考研打好了很好的基础。 6、参考文献 1 孙忠秀.操作系统教程 (第四版):高等教育出版社,2009. 2 马石安,魏文平.Visual C+程序设计与应用教程.北京:清华大学出版社,2007. 3 郑莉,张瑞丰.C+语言程序设计(第3版).北京:清华大学出版社,2004. 4.严蔚敏，吴伟民.数据结构.北京:清华大学出版社,2005. 8 指导教师评语: 指导教师签名: 年 月 日 权重 成绩 项 目 0.1 1、设计过程中出勤、学习态度等方面 成0.4 绩2、设计技术水平 评0.2 3、编程风格 定 0.3 4、设计报告书写及图纸规范程度 总 成 绩 9
