LRU置换算法,即最近最久未使用,常用于页面置换算法,是为虚拟页式存储管理服务的。关于操作系统的内存管理,如何节省利用容量不大的内存为最多的进程提供资源,一直是研究的重要方向。而内存的虚拟存储管理,是现在最通用,最成功的方式为在内存有限的情况下,扩展一部分外存作为虚拟内存,真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能,极大地提高了计算机的并发度。虚拟页式存储管理,则是将进程所需空间划分为多个页面,内存中只存放当前所需页面,其余页面放入外存的管理方式。

lru算法是什么?

LRU是Least Recently Used的缩写,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。

该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t,当须淘汰一个页面时,选择现有页面中其t值最大的,即最近最少使用的页面予以淘汰。

特点:

LRU 算法弊端是存在偶发性、周期性的批量操会降低缓存的命中率,对缓存造成污染,下面几个就是改进算法。

LRU-K会记录每条数据的访问历史,当达到 k 时,才将数据存放到缓存,在缓存内存回收时,缓存中越接近 k 的数据被优先删除。

Two queues(2Q)相当于 LRU-2,区别是访问历史(首次访问)数据缓存于 FIFO 队列,二次及以上的数据存放LRU缓存,FIFO 队列数据遵循该缓存的内存回收机制,LRU缓存数据遵循该缓存的内存回收机制。

lru算法是什么呢?

LRU算法是最少使用页面置换算法(Least Recently Used),首先置换近期最长时间以来没被访问的页面,是为虚拟页式存储管理服务的。

LRU算法的设计原则是:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。也就是说,当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。

LRU原理

该思想最初用于计算机操作系统中,内存中的容量较有限,为了能更加合理的利用内存中的性能,对用户的使用作出假设,最近最少使用的越不重要,最近使用的越有可能使用到,使得该元素更容易获取到。

如果元素当前容量超过了内存最大容量,则需要删除掉最近最少使用的元素。在其之后,许多缓存及许多分布式系统都采用才思想。

lru页面置换算法是什么?

用双向链表和哈希表来实现。

LRU算法的提出,是基于这样一个事实:在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。

反过来说,已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个,就是著名的局部性原理——比内存速度还要快的cache,也是基于同样的原理运行的。因此,只需要在每次调换时,找到最近最少使用的那个页面调出内存。这就是LRU算法的全部内容。

一种LRU近似算法是最近未使用算法。

它在存储分块表的每一表项中增加一个引用位,操作系统定期地将它们置为0。当某一页被访问时,由硬件将该位置1。过一段时间后,通过检查这些位可以确定哪些页使用过,哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去,因为在之前最近一段时间里它未被访问过。

百度百科-页面置换算法