技术杂谈--LRU算法

LRU 是 Least Recently Used 的缩写,也就是最近最少使用算法,它是内存管理的一种页面置换算法

下面我们用解决问题的方式来引入 LRU

第一个问题:怎么让有限的内存为更多的线程提供资源?

内存的虚拟存储管理,是现在最通用,最成功的解决第一个问题的方式,它是这样
解决的, 在内存有限的情况下,扩展一部分外存作为虚拟内存,真正的内存只存储当
前运行时所用的到的信息。当进程所需的资源不在内存中时,就把虚拟内存中的信息拉取到内存中,这样自然就可以为更多的线程提供资源,但是外存相比内存是低速的,这一步骤所花费的时间自然不可忽略,这就诞生了第二个问题

第二个问题:怎么尽可能少或者尽可能晚的进行内存置换(把外存中需要的信息放入内存,内存中的信息置换出去)

最理想的情况肯定是每次调换出的页面(内外存置换的基本单位)是所有内存页面中最迟将被使用的,这样就可以最大限度的推迟内外存页面的置换,自然在一段时间内的内外存置换次数就会最少,这个就是理想页面置换算法,大家都知道,一般理想的东西都是很难实现的或者是不太可能实现的,这个时候大家能做的只能是尽可能的靠近理想,减少和理想的差距,这个时候LRU就出现了。

LRU算法的提出,是基于这样一个事实:在前面几条指令中使用频繁的页面存储的信息很可能在后面的几条指令中也会频繁使用。反过来说,已经很久没有使用的页面存储的信息很可能在未来较长的一段时间内不会被用到。这个就是著名的局部性原理里面的时间局限性。因此,我们只需要在每次置换时,只需要找到最近(Recently)最少(least)使用的那个内存页面和进程所需的那个外存页面进行置换就可以了。这就是LRU算法的全部内容

下面用张图告诉大家使用LRU进行内存置换的过程

图片描述:假入内存有三页的空间

第一步:A,B,C被进程装载如内存后,内存可用空间满了,这时候需要D页上面的信息,此时根据LRU(最近最久(少)未使用),把A和D进行置换,A被换出到外存

第二步:B所存储的信息再次被进程调用

第三步:进程需要E所存储的信息,此时要把E调入内存,因为C是最近最久未使用的,所以被换出到外存

如有问题,欢迎指导
问题交流群:737184824

© 著作权归作者所有
这个作品真棒,我要支持一下!
机器学习、深度学习、大数据、数据科学爱好者集结地,分享 在各自领域里的工程实践经验和应用 让我们每天进步一点点...
0条评论
top Created with Sketch.