原创
上一篇博客写了先进先出算法 (FIFO)-- 页面置换: http://www.cnblogs.com/chiweiming/p/9058438.html
此篇介绍最近最少使用算法 (LRU)-- 页面置换, 与上一篇的代码大同小异, 只是用了不同的方法从页面队列
中选出需要淘汰出的页面.
还是辣个栗子:
现内存页面为: 15 31 24 17 18 5 9 26 4 21
部分地址流为: 4 31 24 17 18 26 17 5 5 9 31 18 18 21 15 8
页面 8 为下一个需要调入进去的页面, 由于内存页面已满, 需要使用 LRU 调出一个最近未被使用页面.
寻找淘汰页面的方式如下:
从页面 8 往前看, 遇到与内存页面中相同的页面即把它移除 (即不淘汰它), 等到移除了 max_page-1 个页面之
后, 剩下最后一个未被移除的页面即是需要淘汰出去的.
在上面例子中, 依次将 15 21 18 31 9 5 17 26 24 (已经 9 个), 剩下最后一个 4 即是需要淘汰出去的页面.
可以用这样的代码去实现: 用一个数组 flag 来备份内存页块号中的页面, 从 8 往前看, 依次将之前的数和数组里
面的数比较, 若匹配成功, 则将数组里面此位置 -1 , 等到置了 max_page-1 个 -1 后跳出; 再从 flag 中筛选出不
是 -1 的值 (即要淘汰出的页面), 再拿此值和当前内存页面队列中的值比较, 匹配成功则将此页面调出去, 将页
面 8 调入.
来源: http://www.bubuko.com/infodetail-2611722.html