首页 > 编程语言 > 详细

最近最少使用算法(LRU)——页面置换

时间:2018-05-22 00:45:43      阅读:271      评论:0      收藏:0      [点我收藏+]

原创


上一篇博客写了先进先出算法(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 调入。

最近最少使用算法(LRU)——页面置换

原文:https://www.cnblogs.com/chiweiming/p/9066722.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!