操作系统页面置换算法

哈尔滨理工大学 课程设计（操作系统）题目： 页式虚拟存储管理FIFO、LRU和OPT页面置换算法班级： 计算机科学与技术学院 计13-9班姓名： 刘骐郡-1304010910指导教师： 孙冬璞系主任： 林克正2016年03月10日 目 录1 需求分析. 2 1.1 目的和要求. 2 1.2 研究内容. 2 2 概要设计. 2 21 FIFO算法. 3 22 LRU算法. 3 23 OPT算法. 3 24 输入新的页面引用串. 3 3 详细设计. 4 31 FIFO（先进先出）页面置换算法：. 432 LRU（最近最久未使用）置换算法：. 4 33 OPT（最优页）置换算法. 4 4 测试. 5 5 运行结果. 56 课程设计总结. 10第1章- 19-哈尔滨理工大学课程设计报告页式虚拟存储管理FIFO、LRU和OPT页面置换算法1需求分析1.1目的和要求在熟练掌握计算机虚拟存储技术的原理的基础上，利用一种程序设计语言模拟实现几种置换算法，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。1.2研究内容 模拟实现页式虚拟存储管理的三种页面置换算法（FIFO(先进先出)、LRU（最近最久未使用）和OPT（最长时间不使用），并通过比较性能得出结论。前提：（1）页面分配采用固定分配局部置换。（2）作业的页面走向和分得的物理块数预先指定。可以从键盘输入也可以从文件读入。（3）置换算法的置换过程输出可以在显示器上也可以存放在文件中，但必须清晰可读，便于检验。2概要设计本程序主要划分为4个功能模块，分别是应用FIFO算法、应用LRU算法、应用OPT算法和页面引用串的插入。21FIFO算法该模块的主要功能是对相应页面引用串进行处理，输出经过FIFO算法处理之后的结果。22LRU算法该模块的主要功功能是对相应的页面引用串进行处理，输出经过LRU算法处理之后的结果。23OPT算法该模块的主要功功能是对相应的页面引用串进行处理，输出经过OPT算法处理之后的结果。24输入新的页面引用串该模块的主要功能是用户自己输入新的页面引用串，系统默认的字符串是00000000000000000000，用户可以自定义全新的20个数字页面引用串。3详细设计在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。33OPT（最优页）置换算法最优页置换算法是所有算法中产生页错误率最低的，而且绝对没有Belady异常的问题。它会置换最长时间不会使用的页。最优页（OPT）置换算法，是根据最长时间不会使用的页来决策的。这就意味着，需要注意内存中的页面和页面的距离了。因此OPT算法是选择最久未使用的页面进行淘汰的。该算法赋予内存中每个页面一个访问字段，用来记录距离此处的最近页面的距离，这样通过比较，就能把最久未使用的页面淘汰掉。代码：#include#includeconstintNsize=10;constintPsize=20;typedefstructpageintyemian;/页面号intbiaoji;/被访问标记page;/*页面逻辑结构，结构为方便算法实现设计*/pageblockNsize;/物理块pagepagePsize;/页面号串voidInit(intQString,intNsize)/初始化内存单元、缓冲区for(inti=0;iNsize;i+)blocki.yemian=-1;/找到空闲内存blocki.biaoji=0;for(i=0;iPsize;i+)pagei.yemian=QStringi;pagei.biaoji=0;intfindSpace(intNsize)/查找是否有空闲内存for(inti=0;iNsize;i+)if(blocki.yemian=-1)returni;/找到空闲内存，返回BLOCK中位置return-1;intfindExist(intcurpage,intNsize)/查找内存中是否有该页面for(inti=0;iNsize;i+)if(blocki.yemian=pagecurpage.yemian)returni;/找到内存中有该页面，返回BLOCK中位置return-1;intfindReplace(intNsize)/查找应予置换的页面inta=0;for(inti=0;i=blocka.biaoji)a=i;/找到应予置换页面，返回BLOCK中位置returna;voiddisplay(intNsize)/显示for(inti=0;iNsize;i+)if(blocki.yemian!=-1)/非空闲内存coutblocki.yemian;coutendl;/*OPT算法核心部分*/voidOPT(intNsize)/最优页置换算法intexist,space,aition;floatscore=0;for(inti=0;iPsize;i+)exist=findExist(i,Nsize);if(exist!=-1)/内存中有该页面cout不缺页endl;score+=1;/统计不缺页次数Elsespace=findSpace(Nsize);if(space!=-1)/找到空闲内存blockspace=pagei;display(Nsize);elsefor(intj=0;jNsize;j+)for(intl=i;lPsize;l+)if(blockj.yemian=pagel.yemian)/计算谁是最长时间没使用的blockj.biaoji=l-i;break;elseblockj.biaoji=Psize-i;aition=findReplace(Nsize);/找到应予置换页面blockaition=pagei;display(Nsize);cout缺页次数为：20-scoreendl;cout缺页率为：(20-score)*100/20%endl;voidBlockClear(intNsize)/块清除for(inti=0;iNsize;i+)blocki.yemian=-1;blocki.biaoji=0;/*主程序*/voidmain(void)inti,select,Nsize,QStringPsize=0;while(select)cout页面号引用串:;for(i=0;i20;i+)coutQStringi;coutendl;cout+*+endl;cout+-欢迎-+endl;cout+-页面置换算法-+endl;cout+-选择应用FIFO算法-+endl;cout+-选择应用LRU算法-+endl;cout+-选择应用OPT算法-+endl;cout+-选择插入新的页面号引用串+endl;cout+-选择退出-+endl;cout+*+endl;coutselect;switch(select)case0:break;case1:coutNsize;while(1)if(Nsize0&Nsize=10)Init(QString,Nsize);cout页面号引用串:;for(i=0;iPsize;i+)coutQStringi;coutendl;coutFIFO算法结果如下:endl;FIFO(Nsize);BlockClear(Nsize);cout-endl;system(pause);system(cls);break;elsecout-输入有误，物理块数请选择1-10的数-endlNsize;break;case2:coutNsize;while(1)if(Nsize0&Nsize=10)Init(QString,Nsize);cout页面号引用串:;for(i=0;iPsize;i+)coutQStringi;coutendl;coutLRU算法结果如下:endl;LRU(Nsize);BlockClear(Nsize);cout-endl;system(pause);system(cls);break;elsecout-输入有误，物理块数请选择1-10的数-endlNsize;break;case3:coutNsize;while(1)if(Nsize0&Nsize=10)Init(QString,Nsize);cout页面号引用串:;for(i=0;iPsize;i+)coutQStringi;coutendl;coutOPT算法结果如下:endl;OPT(Nsize);BlockClear(Nsize);cout-endl;system(pause);system(cls);break;elsecout-输入有误，物理块数请选择1-10的数-endlNsize;break;case4:cout请输入20个数：n;for(i=0;iQStringi;system(cls);break;default:cout提示:功能号错误!endl;cout-endl;system(pause);system(cls);break;4测试程序在设计过程中，曾经出过这样或者那样的问题，最让我纠结的问题是在设计OPT算法时出现的，当我认为没有问题的时候程序一运行就没有想要的结果，很明显不是语法上的错误，由于在程序编写过程中没有截图，此处没有图片说明了。都是逻辑上的错误，最让人难以接受的是，不是程序的逻辑，还是思维的逻辑，也就是从一开始编写程序时，自己的想法的错误了，我说怎么老是显示不出正确的结果，后来改正后结果就显示正常了。5 运行结果 5.1 主界面5.2输入错误的选择5.3选择4的时候自己输入新的页面号引用串，此处输入书上的例子5.4确认后首部分的页面号引用串改变5.5选择OPT算法，相关设置之后6课程设计总结1、通过完成该课程设计，使我了解了什么是缺页中断，以及处理缺页中断的调度算法。通过自己编程，加深了对理论学习的理解。自己动手的编写对缺页终端的调度算法了解加深了不少了解，使我也明白了，真理是在实践中证明的。程序中也出现过这样或者那样的问题，我也曾经颓废过，为了一个简单的逻辑问题纠结了好久，真正弄明白之后才发现自己是那么的蠢，一种豁然开朗的感觉涌上心头。2、程序执行是稳定的，高效的。在LRU算