操作系统虚存管理iii.pptx

Chapter9:VirtualMemory

partIII

9.4页面置换本讲将着重介绍几种页面置换算法择优标准：通常采用具有最小页错误率的算法评估方法：针对特定的页面引用序列，运行某个置换算法，并计算出页错误的数量ReferenceString(引用串)置换算法作用的对象：内存引用序列9.4.1基本页置换

=页置换算法下面，我们将围绕下述引用串来讨论页面置换算法只记录每次内存访问所访问页的逻辑页号

9.4页面置换一般情况下，当物理页帧的数量越大的时候，页错误率会越低，如下图所示9.4.1基本页置换

9.4页面置换为每个页记录其调入内存的时间Selecttheoldestpageasthevictimforeachpagereplacement每次进行置换，选择最旧的页（在内存里待的时间最久）淘汰在实现的时候实际上并不需要记录页面调入的确切时间只要创建一个FIFO队列来管理内存中的页，记住页面进入内存时间的相对早晚就可以了9.4.2FIFO页置换算法

9.4页面置换3个物理页帧的情况9.4.2FIFO页置换算法红色箭头表示缺页蓝色箭头表示命中

9.4页面置换FIFO页置换算法容易理解，并且容易实现缺点：性能不是很好被FIFO置换算法选中淘汰的页很可能是可能是比较久前初始化，但是近期又不断被使用的页9.4.2FIFO页置换算法上面标出来的页面0是个典型的例子。

9.4页面置换FIFO页置换算法中的Belady异常（BeladyAnomaly）9.4.2FIFO页置换算法Belady异常发生位置引用串：1,2,3,4,1,2,5,1,2,3,4,5

9.4页面置换OptimalAlgorithm(最优置换算法，OPT)Replacepagethatwillnotbeusedforlongestperiodoftime替换将来最长一段时间不会被使用的页面OptimalAlgorithmisnoteasytoimplementOPT算法是非常难实现的（因为将来页面使用情况不好预测）OnlyusedformeasuringhowwellyourotherPageReplacementalgorithmsperform通常OPT算法是作为一个理想算法，来检验你实际所采用的算法与OPT算法效果的接近程度，来比较其优劣

OPT算法示意

OPT算法示意这时候，已经达到过度分配的状态了下一个要访问的页面2没有被调入，产生缺页，需要进行页置换了页面7最长时间没被使用，所以被选中，作为victimpage

OPT算法示意

FIFOvs.OPTFIFO算法选择victim页面，用的是页面调入内存的时间最早被调入内存的页面被选择作为淘汰页（Victim页）OPT算法使用的是页面将来被使用的时间作为标准将来最长一段时间不会被使用的页面，被选择作为淘汰页

LRU算法LeastRecentlyUsed置换在内存中最长时间未被使用的页使用过去的情况，来作为不远将来的近似

LRU算法

LRU算法LRU实现LRU置换，为每个页关联该页上次使用的时间每次必须置换一页时，LRU选择离本次页面访问最久没有使用的页LRU被称为向后看的最优页置换算法真正的最优页置换算法使用的是向前看的页面置换算法如果用SR表示引用的串S的倒转，那么针对S的LRU算法的页出错率，与针对SR的OPT算法的页出错率是一样的类似地，针对S的LRU算法的页出错率，与针对SR的LRU算法的页出错率是一样的

LRU算法LRU实现，需要硬件支持为物理页帧确定一个排序，排序的标准是页面上次使用的时间LRU实现方式计数器栈

LRU算法LRU基于计数器的实现方式为每个页表项关联一个使用时间域为CPU增加一个逻辑时钟、或称计数器每次内存访问时，时钟寄存器的内容会复制到相应页对应页表项的使用时间域内置换具有最小时间的页方案需要搜索页表以找到具有最小最近使用时间的页面在页表改变时，需要保持物理页框的使用时间时钟的溢出问题也需要考虑寄存器所能表示的时间有一个范围如寄存器是32位的，那么时间可能达到2^32-1

LRU算法LRU基于栈的实现方式每次引用一个页，该页就从栈中删除并放在顶部保证栈（Stack）的顶部总是放着最近使用的页需要从栈的内部删除某个项，因此最好是将栈实现为具有头指针和尾指针的双向链表栈式LRU实现的特点每次命中时对栈的更新比较费时，但是置换的时候不需要搜索，每次替换选中的都是栈的底部的页面

近似页置换算法很少有计算机系统能提供足够的硬件来支持真正的LRU页置换算法真正实现的时候，往往是完成一些近似算法LRU近似页置换

近似页置换算法(1)