Appearance
LRU 页面置换算法
考情分析
LRU 是页面置换算法中考频最高的算法，计算题几乎必考。🔥🔥🔥 绝对核心。
FIFO 只看"谁来得早"，完全无视使用频率，性能自然差。LRU 换了一种思路：用过去的访问记录预测未来，淘汰最久没碰过的页面。
算法规则
LRU（Least Recently Used）：淘汰最近最久没有被使用的页面。
核心思想：根据过去的使用情况预测未来——如果一个页面很久没被访问，未来可能也不会被访问。就像书架满了要撤掉哪本书——撤掉最久没翻过的那本最划算。
置换示例
页面引用串：3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4，分配 3 个页框
| 访问 | 页框状态 | 缺页? | 淘汰 |
|---|---|---|---|
| 3 | 缺页 | ||
| 2 | 缺页 | ||
| 1 | 缺页 | ||
| 0 | 缺页 | 3（最久未用） | |
| 3 | 缺页 | 2（最久未用） | |
| 2 | 缺页 | 1（最久未用） | |
| 4 | 缺页 | 0（最久未用） | |
| 3 | 命中 | ||
| 2 | 命中 | ||
| 1 | 缺页 | 4（最久未用） | |
| 0 | 缺页 | 3（最久未用） | |
| 4 | 缺页 | 2（最久未用） |
缺页次数：10 次，缺页率
做 LRU 题目的技巧
每次访问一个页面后，把它标记为"最新使用"。淘汰时选择"最旧"的页面。可以想象页面按最后访问时间排序，每次淘汰排在最前面（最旧）的。
交互可视化
LRU 的实现
方法一：计数器
每个页表项维护一个时间戳，每次访问时更新。淘汰时选时间戳最小的。
缺点：每次访存都要更新计数器，淘汰时要扫描所有页表项。
方法二：栈
维护一个页面号栈。每次访问某页面时，将它从栈中取出放到栈顶。淘汰时取栈底页面。
缺点：需要用链表实现栈以支持中间元素的移动。
LRU 的性质
| 性质 | 说明 |
|---|---|
| 是栈算法 | 不会出现 Belady 异常 |
| 性能 | 在可实现的算法中性能最接近 OPT |
| 实现开销 | 硬件支持复杂，实际系统中通常使用近似 LRU（如 CLOCK 算法） |
考研高频考点
- 🔥🔥🔥 给定引用串和页框数，手算 LRU 的缺页次数
- 🔥🔥🔥 LRU 不会出现 Belady 异常
- 🔥🔥 LRU 是根据「过去」预测「未来」（与 OPT 对比）
- 🔥 LRU 的两种实现方式（计数器/栈）
- 🔥 LRU 实现开销大，实际中使用近似算法
LRU 基于"过去"来预测，那如果能看到"未来"呢？下篇来看 OPT 最佳置换算法——理论最优但无法实现，是衡量其他算法好坏的标尺。