《页面置换算法.pptx》由会员分享，可在线阅读，更多相关《页面置换算法.pptx（15页珍藏版）》请在三一文库上搜索。
1、页面置换算法,组长：祖琪玮组员：要笑娟、徐朝阳 藤真久、金少鹏,项目设计思路,界面：MFC后台语言：C+工具：vs2010流程：分析问题设计算法设计界面分工合作注：现在处于设计算法的位置，算法已经理解，下一步进行界面的设计，以下为算法分析。,OPT最佳置换算法,淘汰页面标准：以后用不使用或在最长（未来）时间内不再被访问。优点：缺页率低缺点：理想状况、不实用作用：对可实现算法的性能进行衡量比较，即越接近越好。,实例（opt置换算法）,问题描述主流页面内存数：3内存存取时间：8us缺页中断时间：20us访问快表时间：1us页号序列：7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1
2、、7、0、1,实例（opt置换算法）,页面置换次数：9次 所需时间：9*（20+8*3）+11*（1+8）=495us,18 19 20,1 2 3 4 5 6 7 8 9 10 11 12 13,14 15 16 17,OPT算法思想：选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。,FIFO先进先出置换算法,淘汰页面标准：选择在内存中驻留时间最久的淘汰。优点：实现逻辑
3、简单队列+指针缺点：缺页率高，页面调入顺序不能反映页面使用情况实例：页面置换次数：15 所需时间：15*（20+8*3）+9*（1+8）=741us,算法思想：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。,LRU最近最久未使用算法,淘汰页面标准：页面调入内存后的使用频率。优点：内存页面数越多，命中率越高缺点：硬件支持、寄存器或栈,LRU最近最久未使用算法,页面置换次数：12 所需时间：12*（20+8*3）+8*（1+8）=600us,L
4、RU最近最久未使用算法_寄存器,LRU最近最久未使用算法_栈,算法思想：最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。,LFU最少使用置换算法,页面淘汰标准：最近时期、使用最少缺点：页面访问频率不准确、硬件支持（寄存器）特点：在内存中的每个页面上设置移位寄存器，记录该页面被访的 频率。LFU&LRU：LRU比较寄存器内数字大小 LFU比较寄存器内R1+Ri+Rj+Rn备注：LFU页面访问图与LRU页面访问图完全一样，在此不再赘述,THANK YOU! -制作人：要笑娟,