Appearance
LRU 页面置换算法
2026 大纲 三（二）4 页置换算法的 LRU 部分，含它的实现方式与栈算法性质（另三种见 OPT、FIFO、CLOCK）。
既然记不住未来，就多记一点过去
FIFO 的病根很清楚：命中时什么都不记，所以它分不出热点页和冷门页。
想修这个毛病，就得在命中时也留下痕迹。留什么？ 上一章讲虚拟内存时用过的那条经验事实在这里再次派上用场——时间局部性： 刚被访问过的位置，很快还会被访问。
把它反过来读就是一条可用的淘汰规则：很久没被访问，就意味着接下来大概也不会被访问。 于是 LRU 记的信息是"每一页最后一次被访问是什么时候"，淘汰时刻最早的那一页。
整条推理链是：程序有时间局部性 ⇒ "最近访问过"是"马上还会访问"的可观测信号 ⇒ "很久没访问"就是"接下来也不会访问"的信号 ⇒ 淘汰最后访问时刻最早者，期望损失最小。
但这条链是概率性的，不是必然的。 LRU 押的注是"过去的访问分布 ≈ 未来的访问分布"。 局部性一旦失效，它可以输得比 FIFO 还惨——这一节第一部分就要给出这样一个具体的串。
另一个代价更实在：要在每次访存（含命中）时更新信息，而访存次数比缺页多好几个数量级。 这笔开销压在最热的路径上，精确 LRU 因此几乎无法在页置换里落地。 第二部分沿"精度换开销"这条轴把三级实现排开， 终点正好接上下下一篇的 CLOCK——它是这条轴上最省的一档， 不是另起炉灶。
交互可视化
一、平均更优不等于每个串都更优
这是本篇唯一需要正面回答的反差：串甲上 LRU 缺页 10 次，同一串、同样 3 个页框，FIFO 只缺页 9 次。两组数都可以逐行复核，不是哪一边算错了。
把规模缩到最小，5 次访问就能看清病灶。2 个页框，引用串 1, 2, 1, 3, 2：
| 访问 | FIFO 队列（队头在左） | FIFO 结果 | LRU 栈（栈顶在左=最近） | LRU 结果 |
|---|---|---|---|---|
| 1 | [1] | 缺页 | [1] | 缺页 |
| 2 | [1,2] | 缺页 | [2,1] | 缺页 |
| 1 | [1,2] | 命中（队列不动） | [1,2] | 命中（页 1 移到栈顶） |
| 3 | [2,3] | 缺页，淘汰队头 1 | [3,1] | 缺页，淘汰栈底 2 |
| 2 | [2,3] | 命中 | [2,3] | 缺页，淘汰栈底 1 |
FIFO 3 次、LRU 4 次、OPT 3 次。差别全部出在第 3 次那个命中：它给了 LRU 一条信息，而这条信息恰好是误导性的。FIFO 命中不更新队列，页 1 仍排在队头，第 4 步被淘汰——而页 1 此后确实不再出现，淘汰它完全正确；LRU 把页 1 提到栈顶，于是第 4 步"最久未用"变成了页 2，可页 2 恰恰是第 5 步要访问的。
串甲 3 个页框跑 LRU 的完整淘汰走查（想核对"10 次"这个数字的每一步时展开）
页面引用串 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4（串甲，FIFO 篇用的也是它），分配 3 个页框。
| 访问 | 页框状态 | 缺页? | 淘汰 |
|---|---|---|---|
| 3 | 缺页 | ||
| 2 | 缺页 | ||
| 1 | 缺页 | ||
| 0 | 缺页 | 3（最久未用） | |
| 3 | 缺页 | 2（最久未用） | |
| 2 | 缺页 | 1（最久未用） | |
| 4 | 缺页 | 0（最久未用） | |
| 3 | 命中 | ||
| 2 | 命中 | ||
| 1 | 缺页 | 4（最久未用） | |
| 0 | 缺页 | 3（最久未用） | |
| 4 | 缺页 | 2（最久未用） |
缺页 10 次，缺页率
二、三级实现：沿"精度换开销"排开
精确 LRU 要的信息是"每一页最后一次被访问的相对次序"，而访存每秒发生上亿次，信息越精确，访存路径上的开销越大。三个台阶就是这条轴上的三个取值：
| 方案 | 每次访存做什么 | 淘汰时做什么 | 每次访存的软件开销 | 时间分辨率 |
|---|---|---|---|---|
| 计数器（精确） | 逻辑时钟加一，把时钟值写进该页表项 | 扫描全部页表项取时间戳最小者， | 一次写内存 | 单次访存 |
| 栈（精确） | 把该页号从双向链表中间摘下、接到栈顶 | 直接取栈底， | 一次链表操作 | 单次访存 |
| 附加引用位（近似） | 硬件把访问位 A 置 1 | 把 | 0 | 一个周期（如 100 ms） |
| CLOCK（近似） | 硬件把访问位 A 置 1 | 指针扫，A=0 就淘汰 | 0 | 只区分"本轮扫描前有没有访问过" |
附加引用位法的动作是：每页配一个
"数值最小 ≈ 最久未用"的道理只有一句：高位代表更近的时间片。只要某页在最近一个周期里被访问过，它的最高位就是 1，数值必然大于所有最近一个周期没被访问过的页——二进制的位权顺序天然编码了"越近的历史越重要"，这就是这套硬件的全部巧思。计数器法还有一个附带麻烦：时间戳字段会溢出，需要定期整体归一化。
栈式实现的逐步演示，看清"命中也会改写排序"（想弄明白 LRU 与 FIFO 的分野在哪一步时展开）
5 个页框，访问序列 4, 7, 0, 7, 1, 0, 1, 2（栈顶在左）：
| 访问 | 栈内容（顶 → 底） | 说明 |
|---|---|---|
| 4 | 4 | 压栈 |
| 7 | 7, 4 | 压栈 |
| 0 | 0, 7, 4 | 压栈 |
| 7 | 7, 0, 4 | 7 已在栈中，从中间抽出移到栈顶 |
| 1 | 1, 7, 0, 4 | 压栈 |
| 0 | 0, 1, 7, 4 | 0 从中间抽出移到栈顶 |
| 1 | 1, 0, 7, 4 | 1 从中间抽出移到栈顶 |
| 2 | 2, 1, 0, 7, 4 | 五块装满；栈底 4 即最近最久未使用，下次淘汰它 |
注意第 4、6、7 行——这三次都是命中，栈却都动了。这正是 §一 那个最小反例的机理，也正是"LRU 栈"这个数据结构与它的栈算法性质是同一件事的两面：实现要维护的那个序列，就是理论上那个与页框数无关的排序。
Cache 块替换的 LRU 与页面置换的 LRU 逐项对照（想搞清"同名不同物"差在哪时展开）
| 维度 | Cache 块替换的 LRU | 页面置换的 LRU |
|---|---|---|
| 候选集合 | 一个组内的几路（通常 2～8 路） | 内存中全部页框（成千上万） |
| 谁来执行 | 纯硬件，每次访问都要在纳秒内完成 | 软件（OS），只在缺页时执行 |
| 精确性 | 路数少，可以做精确 LRU（如 4 路只需 6 位比较位） | 页框太多，精确实现开销不可接受，实际用近似 LRU |
| 未命中代价 | 几十个时钟周期 | 一次磁盘 I/O，毫秒级，差 5 个数量级 |
判据是候选集合的规模：几路之间排全序，硬件用几个比较位就够；几千个页框之间排全序，就必须每次访存都写内存——这才是页面置换退而求其次用 CLOCK 的根本原因。未命中代价差 5 个数量级则解释了另一件事：页面置换舍得花软件时间选得更准，Cache 却一个周期都不能多花。
考点速记
- 规则：淘汰最近最久没有被使用的页面，即最后一次访问时刻最早者。依据是"时间局部性 ⇒ 最近访问过是马上还会访问的可观测信号"这条概率性推理链，押的注是"过去的访问分布 ≈ 未来的访问分布"。
- 它是栈算法，不会出现 Belady 异常：按"最后访问时刻"排出的序列完全由引用串决定、与页框数无关，驻留集永远恰好是序列的前
名 ⇒ 前 名必是前 名的子集。 - 平均更优 ≠ 逐串更优："LRU 比 FIFO 好"只在真实程序的访问模式上按平均缺页率成立，不是对每个引用串都成立的定理。串甲配 3 页框：FIFO 9 次、LRU 10 次、OPT 7 次。
- LRU 输在哪个模式：某页刚被访问却从此不再出现，同时另一页久未访问却马上要用——赌注反向兑现。规模化的典型情形是循环扫描
个页面而只有 个页框，命中率可降到 0。 - 三级实现沿"精度换开销"排开：① 计数器法（每次访存写时间戳，淘汰时
扫描）② 栈法（双向链表，访存时摘链接链，淘汰 ）③ 附加引用位法／老化算法（ 位移位寄存器，每周期右移并把访问位 A 移入最高位，淘汰时选数值最小者）。 - 精确 LRU 的代价压在访存路径上：前两者每次访存（含命中）都要写内存或改链表，而访存次数比缺页多好几个数量级。把附加引用位法的
位砍成 1 位，就是 CLOCK。 - LFU 与 LRU 共用同一套寄存器：不比
的数值而统计 中 1 的个数，选最少者淘汰。LFU 看频率，LRU 看最后一次的时间。 - 访问位 A 不是时间戳：A 只有 1 位，只能回答"从上次清零到现在有没有被访问过"，给不出任何次序。
- Cache 的 LRU 与页置换的 LRU 淘汰规则同一条，实现层次完全不同。判据是候选集合的规模：Cache 组内只有 2～8 路，纯硬件几个比较位就能做精确 LRU；页框以千计，只能由 OS 在缺页时用近似 LRU。
这一节在真题里被考过的形式：
LRU 是四种算法里手算题最多的一个——三道选择题全是给引用串手算， 问法有三种变体，但走的是同一套流程。
- 给已访问序列和页框数，问下一次访问某页时该淘汰谁（2015-27）。4 个页框，已访问
2,0,2,9,3,4,2,8,2,4,8,4,5，下一页是 7。⚠️ 做法不是从头模拟，而是从序列末尾往前倒着看：当前驻留的 4 页里，谁的最后一次出现位置最靠前，谁就被淘汰。倒着数，5(最后)、4、8、2依次出现，其中 2 的最后一次最靠前 ⇒ 淘汰 2。这个倒读法比正向模拟快得多也不易错。 - 给引用串和页框数，问产生页置换的总次数（2019-29）。4 页框、串
0,1,2,7,0,5,3,5,0,2,7,6，答 5。⚠️ 问的是置换次数不是缺页次数——前 4 次缺页只调入不淘汰，置换次数 = 缺页次数 − 页框数（前提是页框最终被装满）。 - 给引用串和已在内存的页，问缺页次数（2025-26）。3 页框、串
{0,1,2,0,5,1,4,3,0,2,3,2,0}，且 0,1,2 已调入内存，答 6。⚠️ 这道题的坑在"已调入内存"四个字——开头三次访问 0、1、2 不算缺页，一上来就算成缺页会多算 3 次。这一类题必须先看清初始状态。
复习优先级：必须拿满，且必须练到手算不出错。 三道题分别对应三种问法， 把"倒着数最后一次出现位置"这个技巧练熟，绝大多数 LRU 题可以秒答。 另外两处一定要看清题面：问的是缺页次数还是置换次数、初始时页框是空的还是已装了几页。 速记第二条（不会 Belady）和第三条（平均优不等于逐串优）是选择题的性质考点。
易错：把"缺页次数"和"置换次数"当成一回事。置换次数 = 缺页次数 − 页框数（页框被装满的前提下）。
易错：题目说"某几页已调入内存"时仍把开头几次访问算成缺页。先看清初始状态。
易错：认为 LRU 在任何引用串上都优于 FIFO。那只是平均意义；串甲上 FIFO 9 次、LRU 10 次。
易错：认为 LRU 可能出现 Belady 异常。它是栈算法，不会。
易错：把访问位 A 当成时间戳用。A 只有 1 位，给不出任何次序。
易错：认为 Cache 里的 LRU 和页置换的 LRU 实现方式相同。前者候选只有几路可做精确 LRU，后者只能用近似。
易错：把 LFU 和 LRU 搞混。LFU 看访问频率，LRU 看最后一次访问的时间。
教材出处
- LRU 用"最近的过去"作为"最近的将来"的近似、访问字段记录未被访问的时间
：汤小丹《计算机操作系统》5.3.2 节「LRU 置换算法的描述」，p164 - LRU 的两类硬件支持——移位寄存器
（每 100 ms 右移一位、数值最小者为最近最久未使用）与栈（访问即移到栈顶、栈底为最近最久未使用）：同书 5.3.2 节「LRU 置换算法的硬件支持」，p165 - LFU 与 LRU 共用同一套移位寄存器硬件、以及"一个时间间隔内访问 1 次与 1000 次完全等效"的缺陷：同书 5.3.2 节「最少使用(LFU)置换算法」，p166
相关知识
FIFO 页面置换算法｜OPT 最佳置换算法｜CLOCK 与改进 CLOCK 算法｜页框分配与回收｜页面置换模拟器