《操作系统课设页面置换算法.doc》由会员分享，可在线阅读，更多相关《操作系统课设页面置换算法.doc（10页珍藏版）》请在三一办公上搜索。
1、目录一、课程设计目的及要求1二、相关知识1三、题目分析2四、概要设计3五、代码及流程3六、运行结果7七、设计心得8八、参考文献9一、课程设计目的及要求页面置换算法实验目的：深入掌握内存调度算法的概念原理和实现方法。设计要求：编写程序实现：1）先进先出页面置换算法（FIFO）2）最近最久未使用页面置换算法（LRU）3）最佳置换页面置换算法（OPT）演示页面置换的三种算法。二、 相关知识2.1 先进先出（FIFO）算法这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序链接成一个队列，并设置
2、一个指针，称为替换指针，使它总指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。2.2 最近最久未使用（LRU）算法FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访
3、问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。2.3 最佳（Optimal）算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰的页面，将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是将来最长时间内不再访问的，因而该算法时无法实现的，但可以利用该算法评价其他算法。三、 题目分析熟悉页面置换算法及其实现。页面置换算法是虚拟存储管理实现的关键，通过本次课
4、程设计理解内存页面调度的机制，在模拟实现FIFO、LRU和OPT几种经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。四、概要设计4.1进入系统模块。进入登陆界面，输入内存页面数和实际页数。4.2页面号打印模块。打印输入的页面号。4.3菜单选择模块。选择相应的页面的置换方式，选择相应的字母，进入相应的功能。4.4算法模块。选择相应的页面置换算法。4.5显示输出模块。显示页面被置换的情况。4.6缺页次数和缺页率模块。计算页面号输入的结果。4.7退出系统模块。退出置换页面。五、代码及流程#include#define M 40int N;struct Pro/内
5、存页的结构体int num,time;int Input(int m,Pro pM) /输入函数，输入实际页号和实际页数coutm;if(mM)cout数目太多，请重试endl;else break;while(1);coutendl请输入各页面号endl;for(int i=0;ipi.num;/num页面号pi.time=0;return m;/m代表实际页面走向数void print(Pro* page1) /打印当前内存中存放的页面Pro*page=new ProN;/定义一个指针page=page1;for(int i=0;iN;i+)if(pagei.num=-1)cout ;el
6、secoutpagei.num ;coutendl;int Search(int e,Pro*page1) /查找内存中是否存在要调入的页面Pro*page=new ProN;page=page1;for(int i=0;iN;i+)if(e=pagei.num)return i;return -1;int Max(Pro*page1)/找出离现在时间最长的页面Pro*page=new ProN;page=page1;int e=page0.time,i=0;while(iN)if(epagei.time) e=pagei.time;/找最长时间i+;for(i=0;iN;i+)if(e=pa
7、gei.time) return i;/找最长时间的下标return -1;int Compfu(Pro*page1,int i,int t,Pro pM)/找到最久不使用的页面Pro*page=new ProN;page=page1;int count=0;for(int j=i;jM;j+)if(paget.num=pj.num) break;/当前页面开始往后查找在内存中的页帧号else count+;return count;int main()cout可用内存页面数N;Pro pM;Pro*page=new ProN;char c;int m=0,t=0;float n=0;m=In
8、put(m,p);dofor(int j=0;jN;j+)/初始化页面基本情况pagej.num=-1;pagej.time=2-j;int i=0;coutf:FIFO页面置换endl;coutl:LRU 页面置换endl;couto:OPT 页面置换endl;cout按其它键结束c;if(c=f) /FIFO页面置换n=0;/记录缺页数cout页面置换情况: endl;while(i=0) +i;/找到相同的页面elsen+;paget.num=pi.num;/如果没有找到相同的页，则进行页面替换，缺页数加一print(page);t=(+t)%N;cout缺页次数: n 缺页率：n/me
9、ndl;if(c=l) /LRU页面置换n=0;/记录缺页数cout页面置换情况：endl;while(i=0)paget.time=0;elsen+;t=Max(page);paget.num=pi.num;paget.time=0;if(t=0)paget+1.time+;paget+2.time+;if(t=1)page2.time+;page0.time+;if(t=2)page1.time+;page0.time+;if(k=-1) print(page);i+;cout缺页次数：n 缺页率：n/mendl;if(c=o)/OPT页面置换n=0;/记录缺页数while(i=0)i+;
10、elseint temp=0,cn;for(t=0;tN;t+)/查找下次访问距离最远的那个页面if(tempCompfu(page,i,t,p)temp=Compfu(page,i,t,p);cn=t;pagecn=pi;n+;print(page);i+;cout缺页次数：n 缺页率：n/mendl;while(c=f|c=l|c=o);return 0;六、运行结果图6.1运行结果图6.2运行结果图6.3运行结果七、设计心得 经过几个星期的上机实践学习，使我对操作系统这门课程有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，通过实践，我也发现我的好多不
11、足之处，首先是以前的C语言基础没打好，一些基本常识性东西都不知道，再有操作时有很多很生疏的东西，虽然在学习课本知识的时感觉什么东西都很简单，但真正操作起来确实如此之难，语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。通过实践的学习，我认到学好计算机要重视实践操作，不仅仅是学习操作系统，还是其它的课程，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使自己更好地学好计算机。回顾起此次课程设计，至今我仍感慨颇多，的确，从选题到定稿，从理论到实践，在整整几星期的日子里，可以说得是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以巩固了以前所
12、学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，不过设计终于顺利完成了，在设计中遇到了很多编程问题，最后在老师的辛勤指导下，终于游逆而解。同时，在老师的身上我学得到很多实用的知识，再次我表示感谢！同时，对给过我帮助的所有同学和各位指导老师再次表示忠心的感谢！八、 参考文献1刘振安、刘燕君著.C+程序设计课程设计.北京: 机械工业出版社，20042美Abraham Silberschatz, Peter Baer Galvin, Greg Gagne 著. 郑扣根 译. 操作系统概念（第六版）. 北京： 高等教育出版社，20043陈向群，向勇 等. Windows操作系统原理（第二版）. 北京：机械工业出版社，2004.
