定义

LRU（最近最少使用）算法就是：每次需要淘汰页面时，选那个“最长时间没被访问”的页面换出去。

它是一种典型的缓存置换算法，用来决定内存不够时应该把哪一页踢掉。

LRU 的核心思想：过去访问行为预测未来访问行为。

举例

设有 3 个物理块，访问序列：
1, 2, 3, 2, 4, 1, 2

我们模拟 LRU：

步骤 访问 内存状态 淘汰
1 1 1 -
2 2 1 2 -
3 3 1 2 3 -
4 2 1 3 2 2刚被访问，放到最新
5 4 3 2 4 淘汰1，最久没用
6 1 2 4 1 淘汰3
7 2 4 1 2 -

思想：每次访问都把页面放到“最新”位置。淘汰最久没用的。

实现LRU

  1. 链表（或双端队列）实现:

最新访问的页放队尾
最久未访问的页放队头
缺页时：淘汰队头
每次命中：把该页移动到队尾

缺点：需要频繁移动节点，时间 O(1)，但真实硬件上开销仍然不小。

  1. 硬件支持的“访问位 + 时钟”近似 LRU:

因为真正 LRU 实现太重，所以 CPU 给每个页表项提供：

Referenced bit（访问位，R bit）
Dirty bit（修改位）

系统周期性：

将所有页的访问位复制到一个计数器中
得到一个“老化值”（aging）

更像是“用计数器模拟访问时间先后”。