内存管理-LRU

LRU算法是什么？什么是预读失效？什么是缓存污染？

1. LRU算法

1.1 传统LRU算法

• 当访问的页在内存里，就直接把该页对应的LRU链表节点移动到链表头部；
• 当访问的页不在内存里，除了要把该页放入到LRU链表的头部，还要淘汰LRU链表末尾的页；

传统LRU算法存在两个问题：

• 预读失效
• 缓存污染

2. 预读失效

2.1 预读失效是什么？

操作系统为了提高I/O性能，会预先加载可能被访问的数据到缓存中，但是如果预读的数据没有被实际访问，会占用缓存空间，可能导致热点数据被淘汰，从而降低缓存命中率。

2.2 预读失效会带来什么问题？

预读的数据不一定会被访问到，但是确占用了LRU链表前排的位置，而末尾淘汰的可能是热点数据，这样就会大大降低缓存命中率。

2.3 如何避免预读失效造成的影响？

• 让预读页停留在内存里的时间尽可能的短；
• 让真正被访问的页才移动到LRU链表的头部；

Linux操作系统实现了两个LRU链表：活跃LRU链表(active_list)和非活跃LRU链表(inactive_list)

• active_list：活跃内存链表存放的是最近被访问过的内存页；
• inactive_list：不活跃内存链表存放的是很少被访问的内存页；

预读页加入到inactive_list区域的头部，当页被真正访问的时候，才将页插入到active_list的头部。如果预读的页一直没有被访问，就会从inactive_list中移除。

3. 缓存污染

3.1 缓存污染是什么？

当批量访问大量数据时，这些数据被放入热区，挤占真正的热点数据，导致缓存命中率下降。也就是说，这些批量访问的数据只访问了一次，并且后续不再访问了，这些只访问一次的数据却被加载进热区，而热区真正被频繁访问的数据就会被挤占出去，热区被污染，从而导致后续缓存命中率下降。

3.2 缓存污染会带来什么问题？

缓存被污染之后，真正的热数据被挤占出了缓冲区，等这些热数据又被再次访问的时候，由于缓存未命中，就会产生大量的磁盘I/O，系统性能会急剧下降。

3.3 如何避免缓存污染造成的影响？

• 提高进入活跃LRU链表的门槛；

Linux操作系统在内存页被访问第二次的时候，才将页从inactive_list升级到active_list中。