1、从理论上讲,应将那些以后不再会访问的页面换出,或将那些在较长时间内不会再访问的页面调出。 31 FIFO(先进先出)页面置换算法:这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应,因为在进程中,有些页面经常被访问,比如,含有全局变量、常用函数、例程等的页面,FIFO算法并不能保证这些页面不被淘汰。32 LRU(最近最久未使用)置换算法: FIFO置换算法性能之所以较差,是因为它所依据
2、的条件是各个页面调入内存的时间,而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)置换算法,是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,因此,LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t,,当须淘汰一个页面时,选择现有页面中其t值最大的,即最近最久未使用的页面予以淘汰。33 OPT(最优页)置换算法最优页置换算法是所有算法中产生页错误率最低的,而且绝对没有Belady异常的问题。它会置换最长时间不会使用的页。最优页(
3、OPT)置换算法,是根据最长时间不会使用的页来决策的。这就意味着,需要注意内存中的页面和页面的距离了。因此OPT算法是选择最久未使用的页面进行淘汰的。该算法赋予内存中每个页面一个访问字段,用来记录距离此处的最近页面的距离,这样通过比较,就能把最久未使用的页面淘汰掉。4 测试程序在设计过程中,曾经出过这样或者那样的问题,最让我纠结的问题是在设计OPT算法时出现的,当我认为没有问题的时候程序一运行就没有想要的结果,很明显不是语法上的错误,由于在程序编写过程中没有截图,此处没有图片说明了。都是逻辑上的错误,最让人难以接受的是,不是程序的逻辑,还是思维的逻辑,也就是从一开始编写程序时,自己的想法的错误
4、了,我说怎么老是显示不出正确的结果,后来改正后结果就显示正常了。5 运行结果5.1 主界面5.2 输入错误的选择5.3 选择4的时候自己输入新的页面号引用串,此处输入书上的例子5.4 确认后首部分的页面号引用串改变5.5 选择FIFO算法,相关设置之后5.6 选择LRU算法之后5.7 选择OPT算法之后5.8 如果你选择的物理模块是其他的数量,此处用4个模块,OPT算法为例6 课程设计总结1、通过完成该课程设计,使我了解了什么是缺页中断,以及处理缺页中断的调度算法。通过自己编程,加深了对理论学习的理解。自己动手的编写对缺页终端的调度算法了解加深了不少了解,使我也明白了,真理是在实践中证明的。程
5、序中也出现过这样或者那样的问题,我也曾经颓废过,为了一个简单的逻辑问题纠结了好久,真正弄明白之后才发现自己是那么的蠢,一种豁然开朗的感觉涌上心头。2、程序执行是稳定的,高效的。在LRU算法中,要找出最近最久未使用的页面的话,就必须设置有关的访问记录项,且每一次访问这些记录项,页面都必须更新这些记录项。这个记录项在此程序中为 typedef struct page int yemian;/页面号 int biaoji;/被访问标记page; /* 页面逻辑结构,结构为方便算法实现设计*/ 如此显然要花费较大的系统开销(包括时间和空间上的),这也是实际系统中不直接采用LRU算法作为页面置换算法的直
6、接原因,但由于其在页面置换的优越性,实际系统常使用LRU的近似算法。7 参考文献操作系统概念第七版8 附录:源程序清单#includestdlib.h/7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1书上的例子const int Nsize=10;const int Psize=20;page blockNsize;/物理块page pagePsize;/页面号串void Init(int QString,int Nsize)/初始化内存单元、缓冲区 for(int i=0; i= blocka.biaoji) a = i;/找到应予置换页面,返回BLOCK中位置
7、 return a;void display(int Nsize)/显示 if(blocki.yemian != -1)/非空闲内存 coutblocki.yemian ; coutendl;/*FIFO核心部分*/ void FIFO(int Nsize)/先进先出页面置换算法 int exist,space,aition ; float score=0; exist = findExist(i,Nsize); if(exist != -1)/内存中有该页面 cout不缺页 score+=1;/统计不缺页次数 else space = findSpace(Nsize); if(space !
8、= -1)/找到空闲内存 blockspace = pagei; display(Nsize); else aition = findReplace(Nsize);/找到应予置换页面 blockaition = pagei; for(int j=0; j j+) blockj.biaoji+;/BLOCK中所有页面biaoji+缺页次数为:20-score缺页率为:(20-score)*100/20%/*LRU核心部分*/ void LRU(int Nsize)/最近最久未使用置换算法= -1) blockexist.biaoji=0;/*OPT算法核心部分*/void OPT(int Nsi
9、ze)/最优页置换算法 int exist,space,aition; blockspace = pagei; display(Nsize); for(int j=0; for(int l =i;ll+) if(blockj.yemian=pagel.yemian)/计算谁是最长时间没使用的 blockj.biaoji=l-i; break; else blockj.biaoji=Psize-i; aition = findReplace(Nsize); blockaition = pagei;void BlockClear(int Nsize)/块清除 blocki.yemian = -1;
10、 blocki.biaoji = 0;/*主程序*/ void main(void) int i,select,Nsize,QStringPsize=0; while(select)cout页面号引用串:i20;i+)QStringi+*+-欢迎-+-页面置换算法-+-选择应用FIFO算法-+2应用LRU算法-+3应用OPT算法-+-选择插入新的页面号引用串+-选择退出-+请选择: cinselect; switch(select) case 0: break; case 1:请输入分配的物理块数的大小:while(1) if(Nsize0&Nsize=10) Init(QString,Nsize); for(i=0;FIFO算法结果如下: FIFO(Nsize); BlockClear(Nsize);- system(pause);cls else -输入有误,物理块数请选择1-10的数-endl case 2: while(1)LRU算法结果如下: LRU(Nsize); break; cin case 3:OPT算法结果如下: OPT(Nsize); case 4:请输入20个数:n QStringi; system ( default:提示:功能号错误! system(
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2