|
【例】在一个请求分页存储管理系统中进程P共有页访问串为OO时试采用LRU置换算法和LFU算法计算当分配给该进程的页面数分别为和时访问过程中发生的缺页次数和缺页率比较所得的结果分析原因（北方名校经典试题） 【分析】最近最久未使用（LRU）算法的基本思想是用最近的过去估计最近的将来假定在内存中的某个页面在最近的一段时间内未被使用的时间最长那么在最近的将来也可能不再被使用 最近最少使用LFU算法把在最近的一段时间内使用次数最少的页面置换掉 一般来说页框数目越多缺页率也会相应降低 【解答】LRU算法如表所示页框 表 LRU算法（页框）的缺页情况
缺页
LRU算法缺页缺页率为/=% LRU算法如表所示页框 表 LRU算法（页框）的缺页情况
缺页
LRU算法缺页缺页率为/=% LFU算法如表所示页框 LFU算法的缺页情况
缺页
LFU算法缺页缺页率为/=% LFU算法如表所示页框 表 LFU算法的缺页情况
缺页
LFU算法缺页缺页率为/=% 由上表可以得知内存分配的页框越多缺页中断率就越低在这个例子中LFU甚至比LRU的缺页中断率还要低但实际上LFU并不能真正反映页面的使用情况 在采用LFU算法时应为在内存中的每个页面设置都有一个移位寄存器用来记录该页面被访问的频率该置换算法选择在最近时期使用最少的页面作为淘汰页由于存储器具有较高的访问速度例如ns在ms时间内可能对某页面连续访问成千上万次因此通常不能直接利用计数器来记录对某页的访问次数而是采用移位寄存器方式每次访问某页时便对该页移位寄存器的最高位置再每隔一定时间（例如ms）右移一次这样在最近一段时间使用最少的页面将是∑Ri最小的页LFU置换算法的页面的访问图与LRU置换算法的图完全相同或者说是利用这样一套硬件既可实现LRU算法也可实现LFU算法应该指出这种算法并不能真正反映出页面的使用情况因为在每一时间间隔内只是用寄存器的一位来记录页的使用情况因此访问一次和访问次是等效的 返回《操作系统考研辅导教程》 [] [] [] [] [] [] |
