LRU 替换算法

是什么

• 定义：最近最少使用算法（Least Recently Used, LRU），其核心思想是当空间已满需要置换时，选择在最近一段时间里最久未被访问过的表项/页面予以淘汰。

• 大白话：谁最长时间没被翻牌子，就淘汰谁。只要某项被访问到了（哪怕是原本就在里面的“命中”），它的新鲜度就会立刻刷新，重新变成“最新被使用的”。

核心内容

1. 双向链表 / 栈视角理解 LRU

每一组（Set）内部可以维护一个按时间排序的队列或栈：

• 新进入 / 命中的元素：直接移到队列最前端（表示最新访问）。

• 淘汰的目标：永远从队列尾部踢出（表示最久未被访问）。

2. 组相联映射中的解题步骤

在组相联 Cache 或 TLB 中，各组之间相互独立，互不干扰：

1. 算组号：计算每个访问项对应的组号 $\text{组号}=\text{地址/页号}(\mathrm{mod}\text{组数})$。

2. 分流追踪：只关注发生冲突的那一组，其他组的访问完全不影响该组的 LRU 顺序。

3. 状态刷新（关键）：

   • 若元素不在组内且组未满 $\to$ 直接放入，标记为最新。

   • 若元素不在组内且组已满 $\to$ 淘汰最久未访问者，放入新元素并标记为最新。

   • 若元素已在组内（命中） $\to$ 空间不增加，但必须将该元素刷新为“最新访问”，其余元素相对“变旧”。

例题

• 题目（2021统考408真题节选）：

  TLB 采用 2 路组相联映射方式和 LRU 算法，共 8 组。TLB 初始为空，访问的虚页号依次为：10, 12, 16, 7, 26, 4, 12, 20。在此过程中，哪一个虚页号对应的 TLB 表项被替换？说明理由。

• 分析：

  • 映射公式：$\text{TLB 组号}=\text{虚页号}(\mathrm{mod}8)$。

  • 容量限制：2 路组相联表示每组最多只能装 2 个表项。

  • 只有映射到同一组的元素个数超过 2 个时才会发生替换。

  • 统计各虚页号所属组号：

    • $10(\mathrm{mod}8)=2$ （组 2）

    • $12(\mathrm{mod}8)=4$ （组 4）

    • $16(\mathrm{mod}8)=0$ （组 0）

    • $7(\mathrm{mod}8)=7$ （组 7）

    • $26(\mathrm{mod}8)=2$ （组 2）

    • $4(\mathrm{mod}8)=4$ （组 4）

    • $12(\mathrm{mod}8)=4$ （组 4）

    • $20(\mathrm{mod}8)=4$ （组 4）

  • 显然，只有 组 4（涉及 12, 4, 12, 20）发生了连续多次访问并超过了容量上限 2。

• 答案：

  聚焦组 4 的动态变化过程（括号左侧为最久未访问，右侧为最新访问）：

  1. 访问虚页号 12：放入组 4 $\to$ 状态为 [12(最新)]

  2. 访问虚页号 4：放入组 4 $\to$ 状态为 [12(旧), 4(最新)]（此时组 4 已满 2 路）

  3. 再次访问虚页号 12：命中！ $12$ 被重新访问，新鲜度刷新 $\to$ 状态变为 [4(旧), 12(最新)]（注意：4 变成了最久未访问的表项）

  4. 访问虚页号 20：组 4 已满，必须替换最久未访问的项，此时队尾最旧的是 4，故淘汰 4，载入 20 $\to$ 状态变为 [12(旧), 20(最新)]。

  被替换的虚页号是 4。

“哪一个虚页号对应的 TLB 表项被替换？说明理由。”

这问本质上就是在找两样东西的变化：

1. 组内装入的“虚页号”在变化（谁挤进来了，谁被踢出去了）

2. 组内每个表项的“时间新鲜度（LRU 状态）”在变化

总结

第 3 问让你找的就是：在同一个组（组 4）里面，经过反复访问和命中后，谁的新鲜度掉到了最后一名，从而在新人（20）进来时被踢掉。(不是组号，是虚页号)

答案正是：虚页号 4。

⚠️ 易错点

Warning

• 命中时忘记更新访问时间 $\to$ 很多同学误以为“只有新加入的才排在最前面，原有的不动”。如果第 7 步访问 12 命中后不更新顺序，队列仍是 [12(旧), 4(最新)]，就会错误地认为淘汰的是 12。

• 把全部序列混在一起做全局 LRU $\to$ 必须先按 mod 组数 分流到具体的“组”里，只有落到同一个组内的表项才互相竞争。

• 误以为 12 被替换了 $\to$ 12 虽然进入得最早，但因为中途被“再次访问（命中）”了一次，它的寿命被重置延长了，因此活了下来，被淘汰的反而是后进来的 4。