LRU页面置换详解 · 融合风（象牙 + Obsidian 入口）

速查

LRU（Least Recently Used）：置换时淘汰最近最长时间未被访问的页面——用历史近似未来，是 OPT 的可实现版本；不会出现 Belady 异常（满足 stack property）。

速查 ▾

项目	值
核心概念	LRU（最近最久未使用）：置换时选择最近最长时间没有被访问的页面淘汰
关键性质	不会出现 Belady 异常（满足 stack property）
实现方式	计数器法、栈法、双向链表 + 哈希表（O(1)）
考试技巧	手算用栈法模拟最快（栈顶 = 最近访问）

核心概念 ▾

算法思想

LRU（Least Recently Used，最近最久未使用）：当需要置换页面时，选择最近最长时间没有被访问的页面淘汰。

核心假设：如果一个页面最近被访问过，那么它很可能在不久的将来再次被访问（局部性原理）。

与 FIFO 和 OPT 的关系

算法	选择标准	依据
OPT	将来最长时间不被使用	未来信息（不可实现）
LRU	过去最长时间未被使用	历史信息（可实现）
FIFO	最早进入内存	进入时间

LRU 是 OPT 的「可实现版本」，用历史使用情况近似未来访问模式。

实现方式

计数器法：为每个页面维护计数器记录上次访问时间；置换时淘汰计数器值最小（最久未访问）的页面
栈法：维护访问顺序栈，访问页面 P 时把 P 取出放到栈顶；置换时淘汰栈底页面
双向链表 + 哈希表（实际工程实现）：访问时把节点移到链表头部，淘汰时删除链表尾部节点，O(1) 时间复杂度

关键性质

不会出现 Belady 异常：LRU 满足 stack property（包含 k 个物理块的页面集合，一定包含在 k+1 个物理块的页面集合中）
时间复杂度：朴素实现 O(n)（n 为物理块数），需要扫描所有页面找最久未使用的
空间开销：需要为每个页面存储额外的访问时间或链表指针

栈法模拟手算技巧

维护一个栈，栈顶是最近访问的页面：

访问页面 P：若 P 在栈中 → 将 P 移到栈顶
若 P 不在栈中（缺页）：栈未满 → P 入栈到栈顶；栈已满 → 淘汰栈底页面，P 入栈到栈顶

手算示例 ▾

例1：基本 LRU 置换

页面访问序列：7, 0, 1, 2, 0, 3, 0, 4, 2, 3，物理块数 $= 3$，用栈表示（栈顶在右，栈底在左）：

访问	栈状态（左=栈底）	是否缺页	说明
7	[7]	✅ 缺页	入栈
0	[7, 0]	✅ 缺页	入栈
1	[7, 0, 1]	✅ 缺页	入栈，栈满
2	[0, 1, 2]	✅ 缺页	7 在栈底（最久未用），淘汰 7
0	[1, 2, 0]	❌ 命中	0 移到栈顶
3	[2, 0, 3]	✅ 缺页	1 在栈底，淘汰 1
0	[2, 3, 0]	❌ 命中	0 移到栈顶
4	[3, 0, 4]	✅ 缺页	2 在栈底，淘汰 2
2	[0, 4, 2]	✅ 缺页	3 在栈底，淘汰 3
3	[4, 2, 3]	✅ 缺页	0 在栈底，淘汰 0

缺页次数：8 次（对比同序列 FIFO 的 9 次，LRU 更优）
缺页率：$\frac{8}{10} = 80\%$

例2：LRU 与 FIFO 对比

页面访问序列：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，物理块数 $= 3$。FIFO 结果缺页 9 次。

访问	栈状态	缺页	说明
1	[1]	✅	入栈
2	[1, 2]	✅	入栈
3	[1, 2, 3]	✅	入栈
4	[2, 3, 4]	✅	淘汰最久未用的 1
1	[3, 4, 1]	✅	淘汰最久未用的 2
2	[4, 1, 2]	✅	淘汰最久未用的 3
5	[1, 2, 5]	✅	淘汰最久未用的 4
1	[2, 5, 1]	❌	命中，移到栈顶
2	[5, 1, 2]	❌	命中，移到栈顶
3	[1, 2, 3]	✅	淘汰最久未用的 5
4	[2, 3, 4]	✅	淘汰最久未用的 1
5	[3, 4, 5]	✅	淘汰最久未用的 2

Belady 异常此序列中 LRU 缺页 10 次、FIFO 缺页 9 次；但增加物理块到 4 时，FIFO 出现 Belady 异常（缺页 9→10），而 LRU 不会（满足 stack property）。

记忆卡片 ▾

LRU 的核心思想？

淘汰最近最长时间未被访问的页面，依据局部性原理。

LRU 为什么不出 Belady 异常？

满足 stack property：k 桶页面集合是 k+1 桶的子集。

LRU 的实现难点？

朴素实现 O(n) 扫描；实际用 Clock 近似 LRU。

LRU 与 OPT 的关系？

OPT 淘汰将来最久的（不可实现）；LRU 淘汰过去最久的，是 OPT 的最佳近似。

手算 LRU 最快技巧？

用栈模拟：栈顶=最近访问，访问即移顶，缺页且满时淘汰栈底。

交互动画 · LRU 栈演化（例1） ▾

点击「下一步」逐次访问页面，观察 LRU 栈演化与淘汰过程

橙色流动虚线指向被淘汰（最久未使用）的栈底页面；缺页计随演示累计。

速查 ▾

核心概念 ▾

算法思想

与 FIFO 和 OPT 的关系

实现方式

关键性质

栈法模拟手算技巧

手算示例 ▾

例1：基本 LRU 置换

例2：LRU 与 FIFO 对比

记忆卡片 ▾

交互动画 · LRU 栈演化（例1） ▾

相关知识点