Linux内存管理（二十一）：LRU 第二次机会法

源码基于：Linux5.4

0. 前言

在经典 LRU 链表算法中，新产生的页面被添加到 LRU 链表的开头，将 LRU 链表中存在的页面向后移动一个位置。当系统内存短缺时，LRU 链表尾部的页面将会离开并被换出。当系统再需要这些页面时，这些页面会被重新置于 LRU 链表的开头。显然这个设计不是很巧妙，在换出页面时，没有考虑页面是否频繁使用。也就是说，频繁使用的页面依然会因为在 LRU 链表末尾而被换出。

第二次机会法的改进是为了避免把经常使用的页面置换出去。本文将结合代码分析下第二次机会法的确认过程。

1. 经典的LRU 链表算法

在经典 LRU 链表算法中，新产生的页面被添加到 LRU 链表的开头，将 LRU 链表中存在的页面向后移动一个位置。当系统内存短缺时，LRU 链表尾部的页面将会离开并被换出。

不管是 active list 还是 inactive list，都是采用的FIFO 的流动形式，新的元素从链表的头部加入，中间的元素逐渐向尾部移动。在需要进行内存回收时，内核总是选择 inactive list 尾部的页面进行回收。<