Appearance
FIFO 页面置换算法
2026 大纲 三（二）4 页置换算法的 FIFO 部分，以及由它引出的 Belady 异常与栈算法（另三种见 OPT、LRU、CLOCK）。
页框满了，该踢谁
请求分页那一节留下了一个没答的问题：缺页时如果没有空闲页框，就得先淘汰一个。 淘汰哪一个？
接下来的四篇——FIFO、LRU、OPT、CLOCK——回答的都是这同一个问题， 它们不是四种并列的技术，而是沿着"用多少信息来做这个决定"排开的一条线。
信息从哪来是关键。理想的决定需要知道未来：踢掉那个最久都不会再用的。 可运行中的系统看不见未来，只看得见过去。于是每种算法实际上都在回答： 过去的哪一部分信息，值得花代价记下来？
FIFO 的答案是最省的一个：只记"谁先来的"。 这个信息本来就有——页面调入时天然有先后次序，把它们串成一个队列即可， 访存时什么都不用更新，不需要任何硬件支持。
代价也随之而来。既然命中时什么都不记，那么一个页被访问一万次和只被访问一次， 在队列里的地位完全一样。全局变量、常用函数、循环例程所在的热点页面， 照样会因为"进来得早"被排到队头淘汰掉。
这一节除了讲清这条代价，还要处理一件由它引出的怪事： 多分配几个页框，缺页反而更多——Belady 异常。它只会发生在 FIFO 这一类算法上， 而"为什么只发生在它这一类"正是理解全部四种算法的分类依据。
交互可视化
一、命中不更新，是代价与信息量的对应
FIFO 与 LRU 的差别不在规则复杂度，而在它们赌的东西不同：FIFO 赌"待得久的该走了"，这个量在页面装入那一刻就定死了，命中不提供新信息；LRU 赌"最近用过的还会再用"，命中恰恰是唯一的新信息来源，不更新它 LRU 就退化成 FIFO。
于是代价也对称：LRU 要在每次访存时更新时间戳或移动栈顶，CLOCK 要靠硬件在访问时自动置访问位，FIFO 什么都不用做——访存零开销换来的正是零信息。
队列归谁维护则由置换范围决定：局部置换时队列只含本进程的页面，随页表一起属于该进程的内存管理信息，进程切换时整个队列随 PCB 挂起，不需要任何清理动作；全局置换时队列是全系统一份、包含所有可换出页框，进程切换根本不影响它。无论哪种，队列都不随进程切换而重建——重建会把"驻留时间"信息清零，等于每次切换都退化成随机置换。
串甲 3 个页框的完整淘汰走查（想核对手算每一步、或想看清热点页怎么被误淘汰时展开）
页面引用串 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4（下称串甲，LRU 篇用的也是它），分配 3 个页框。
| 访问 | 页框1 | 页框2 | 页框3 | 缺页? |
|---|---|---|---|---|
| 3 | 3 | 缺页 | ||
| 2 | 3 | 2 | 缺页 | |
| 1 | 3 | 2 | 1 | 缺页 |
| 0 | 0 | 2 | 1 | 缺页（淘汰3） |
| 3 | 0 | 3 | 1 | 缺页（淘汰2） |
| 2 | 0 | 3 | 2 | 缺页（淘汰1） |
| 4 | 4 | 3 | 2 | 缺页（淘汰0） |
| 3 | 4 | 3 | 2 | 命中 |
| 2 | 4 | 3 | 2 | 命中 |
| 1 | 4 | 1 | 2 | 缺页（淘汰3） |
| 0 | 4 | 1 | 0 | 缺页（淘汰2） |
| 4 | 4 | 1 | 0 | 命中 |
缺页次数 9 次，缺页率
注意第 7 步：页面 0 在第 4 步才刚装进来，第 7 步就因为"进来得最早"被淘汰。FIFO 淘汰的是"住得最久"的，不是"最没用"的，这两件事在有热点页面的程序里几乎总是不一致。
二、Belady 异常
增加分配的页框数，缺页次数反而增加——反直觉，但确实会发生。经典反例：页面引用串 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5（它其实就是串甲换了页号，把 3、2、1、0、4 依次改名为 1、2、3、4、5，两串逐位相同）。
| 页框数 | 缺页次数 |
|---|---|
| 3 | 9 |
| 4 | 10（反而增加了） |
断裂点在位置 7（访问页 5）：
机理很清楚：3 个页框时，页 1 在位置 4 就被换出、位置 5 又被重新调入，于是它的"调入时刻"被刷新成了位置 5，排到队尾，位置 7 时轮不到它；4 个页框时，页 1 从位置 1 装入后一直没被换出，调入时刻仍停在位置 1，位置 7 时正排在队头，第一个就被淘汰。多给的那个页框反而让页 1 少了一次"刷新排队资格"的机会。 接下来位置 8 访问页 1，3 页框命中、4 页框缺页——多出来的那一次缺页就是这么来的。
经典反例 3 框与 4 框的两张逐步表（想逐行核对 9 次与 10 次这两个数字时展开）
3 个页框（缺页 9 次）
| 访问 | 框0 | 框1 | 框2 | 结果 |
|---|---|---|---|---|
| 1 | 1 | 缺页 | ||
| 2 | 1 | 2 | 缺页 | |
| 3 | 1 | 2 | 3 | 缺页 |
| 4 | 4 | 2 | 3 | 缺页（淘汰1） |
| 1 | 4 | 1 | 3 | 缺页（淘汰2） |
| 2 | 4 | 1 | 2 | 缺页（淘汰3） |
| 5 | 5 | 1 | 2 | 缺页（淘汰4） |
| 1 | 5 | 1 | 2 | 命中 |
| 2 | 5 | 1 | 2 | 命中 |
| 3 | 5 | 3 | 2 | 缺页（淘汰1） |
| 4 | 5 | 3 | 4 | 缺页（淘汰2） |
| 5 | 5 | 3 | 4 | 命中 |
4 个页框（缺页 10 次）
| 访问 | 框0 | 框1 | 框2 | 框3 | 结果 |
|---|---|---|---|---|---|
| 1 | 1 | 缺页 | |||
| 2 | 1 | 2 | 缺页 | ||
| 3 | 1 | 2 | 3 | 缺页 | |
| 4 | 1 | 2 | 3 | 4 | 缺页 |
| 1 | 1 | 2 | 3 | 4 | 命中 |
| 2 | 1 | 2 | 3 | 4 | 命中 |
| 5 | 5 | 2 | 3 | 4 | 缺页（淘汰1） |
| 1 | 5 | 1 | 3 | 4 | 缺页（淘汰2） |
| 2 | 5 | 1 | 2 | 4 | 缺页（淘汰3） |
| 3 | 5 | 1 | 2 | 3 | 缺页（淘汰4） |
| 4 | 4 | 1 | 2 | 3 | 缺页（淘汰5） |
| 5 | 4 | 5 | 2 | 3 | 缺页（淘汰1） |
按行对齐逐行比
三、给一个新引用串，怎么判断会不会出现
没有一眼看穿的闭式判据，但有一条可操作的路：
- 先看算法。若是 LRU 或 OPT，包含性质恒成立，直接判定不会出现，不必算。
- 若是 FIFO 或 CLOCK，把
与 两张逐步表都画出来，逐位比较两个驻留集：包含性质从头到尾成立 → 缺页次数一定不增；某一步断裂 → 有可能出现，但必须把整串的得失算成一笔总账才能定论。
按判据走一遍完整流程：断裂了、也兑现了，总数照样是降的（想把"必要非充分"落到具体数字上时展开）
引用串 1, 3, 4, 5, 1, 2, 4, 1, 3, 1（数据自造），FIFO，判断 3 → 4 个页框是否出现 Belady 异常。
第一步：3 个页框的逐步表。 判据要求逐位比较驻留集，所以表里必须把每一步之后的驻留集单独列一列——只记"缺不缺页"是不够的。
| 位置 | 访问 | 框0 | 框1 | 框2 | 结果 | 驻留集 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 缺页 | |||
| 2 | 3 | 1 | 3 | 缺页 | ||
| 3 | 4 | 1 | 3 | 4 | 缺页 | |
| 4 | 5 | 5 | 3 | 4 | 缺页（淘汰1） | |
| 5 | 1 | 5 | 1 | 4 | 缺页（淘汰3） | |
| 6 | 2 | 5 | 1 | 2 | 缺页（淘汰4） | |
| 7 | 4 | 4 | 1 | 2 | 缺页（淘汰5） | |
| 8 | 1 | 4 | 1 | 2 | 命中 | |
| 9 | 3 | 4 | 3 | 2 | 缺页（淘汰1） | |
| 10 | 1 | 4 | 3 | 1 | 缺页（淘汰2） |
3 个页框：缺页 9 次。
第二步：4 个页框的逐步表。
| 位置 | 访问 | 框0 | 框1 | 框2 | 框3 | 结果 | 驻留集 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 缺页 | ||||
| 2 | 3 | 1 | 3 | 缺页 | |||
| 3 | 4 | 1 | 3 | 4 | 缺页 | ||
| 4 | 5 | 1 | 3 | 4 | 5 | 缺页 | |
| 5 | 1 | 1 | 3 | 4 | 5 | 命中 | |
| 6 | 2 | 2 | 3 | 4 | 5 | 缺页（淘汰1） | |
| 7 | 4 | 2 | 3 | 4 | 5 | 命中 | |
| 8 | 1 | 2 | 1 | 4 | 5 | 缺页（淘汰3） | |
| 9 | 3 | 2 | 1 | 3 | 5 | 缺页（淘汰4） | |
| 10 | 1 | 2 | 1 | 3 | 5 | 命中 |
4 个页框：缺页 7 次。
第三步：逐位比较包含性质。 断裂点告诉你"哪一页被多丢了、从哪一步开始丢"。
| 位置 | |||
|---|---|---|---|
| 1～5 | 逐步 | 逐步 | 成立 |
| 6 | {1,2,5} | {2,3,4,5} | 断裂——页 1 被 4 框多丢了 |
| 7 | {1,2,4} | {2,3,4,5} | 断裂——页 1 仍缺 |
| 8 | 成立（页 1 已被重新调入，断裂愈合） | ||
| 9 | {2,3,4} | {1,2,3,5} | 断裂——这次轮到页 4 |
| 10 | {1,3,4} | {1,2,3,5} | 断裂——页 4 仍缺 |
位置 6 断裂的机理与经典反例完全一样：3 个页框时页 1 在位置 4 被换出、位置 5 又被重新调入，调入时刻被刷新到队尾；4 个页框时页 1 从位置 1 起一直没被换出，位置 6 时正排在队头，第一个就被淘汰。
第四步：算总账。 断裂已经出现，但这只说明"有可能"。把两张表逐位对照，只看结果不同的那几行：
| 位置 | 访问 | 3 框 | 4 框 | 谁占便宜 |
|---|---|---|---|---|
| 5 | 1 | 缺页 | 命中 | 4 框 赚 1 |
| 7 | 4 | 缺页 | 命中 | 4 框 赚 1 |
| 8 | 1 | 命中 | 缺页 | 4 框亏 1（位置 6 断裂在这里兑现） |
| 10 | 1 | 缺页 | 命中 | 4 框 赚 1 |
结论：不出现 Belady 异常（9 → 7，缺页反而减少）。位置 8 那一行证明断裂确实兑现成了一次额外缺页，但被位置 5、7、10 的三次额外命中盖过了。"断裂过、也兑现过"，总数照样是降的——这就是"必要条件不是充分条件"最准确的样子。只有当亏的次数多于赚的次数时，才真的出现 Belady 异常。
四、FIFO 为什么没消失
| 维度 | FIFO |
|---|---|
| 实现代价 | 最低：一个队列， |
| 性能 | 最差：命中不改变队列位置，热点页面照样被淘汰 |
| Belady 异常 | 会出现（非栈算法） |
| 每次访存的额外开销 | 0 |
看起来一无是处，但注意最后一行——FIFO 是唯一一个"访存路径上零开销"的算法。而访存每秒发生上亿次，置换只在缺页时发生。于是真实系统走的是这条路：保留 FIFO 的循环队列骨架，只在上面补最小的一点信息——加一个访问位、队头页 A=1 就清零后放回队尾"再给一次机会"，是二次机会算法；把队列换成环形、指针原地扫描而不真的搬动页面，就是 CLOCK；再补一个修改位区分脏页与干净页，就是改进 CLOCK（见 CLOCK 篇）。
所以 FIFO 不是被淘汰了，而是被当成了骨架。后面三种算法都是在"命中不留痕"这一处病根上打补丁。
考点速记
- 规则：淘汰最先进入内存的页面。已调入页按调入次序链成队列，替换指针始终指向队头；缺页有空框 → 新页挂队尾、指针不动；缺页无空框 → 淘汰队头、新页挂队尾、指针后移；命中时队列完全不动。
- "命中不留痕"是全部性能问题的病根：一个页被访问一万次和只被访问一次，在队列里地位完全一样 ⇒ 含全局变量、常用函数、循环例程的热点页面照样被排到队头淘汰。
- 它唯一真正的优点：循环队列实现、淘汰
，且不需要任何硬件支持（不用访问位、不用计数器、访存时什么都不更新）。开销全部集中在缺页那一刻——它因此被保留为二次机会 / CLOCK / 改进 CLOCK 的共同骨架。 - 队列归属：局部置换每进程一份、全局置换全系统一份，两种都不随进程切换重建。
- 栈算法判据只看一条：淘汰排序的依据依不依赖页框数
。 LRU 按"最后访问时刻"、OPT 按"下次访问位置"，都只由引用串决定 ⇒ 是；FIFO（及 CLOCK）按"调入时刻"，而调入时刻取决于哪几步缺页、缺页与否又取决于 ⇒ 不是。 - Belady 异常：增加页框数，缺页次数反而增加。只可能出现在非栈算法上，即 FIFO 与它的变体（二次机会、简单 CLOCK、改进 CLOCK）。⚠️LRU 和 OPT 都不会出现。
- 栈算法"不增"≠"一定减"：包含性质只保证缺页次数不会上升，完全可能持平（页框已大到装得下全部页面时再加就没用了）。
- 包含性质断裂是必要条件不是充分条件：断裂只说明"
框在这一段丢掉了 框还留着的页"，而 框在别处照样会多命中若干次。总缺页数是这两笔的代数和，必须算总账。
这一节在真题里被考过的形式：
FIFO 本身的手算至今没单独出过选择题（手算题都给了 LRU 或改进 CLOCK）， 它的考法集中在Belady 异常这个性质上，外加一道大题的分问。
- 问哪些算法可能出现 Belady 异常（2014-30）。答仅 FIFO。LRU 和 OPT 都是栈算法，加页框缺页次数不会增加。⚠️ 判据是速记第五条——看排序依据依不依赖页框数，不要凭"哪个算法更好"去猜。这是本节最稳定的考点。
- 给页表和 CLOCK 指针位置，分别按 FIFO 和 CLOCK 求物理地址（2010-46 第 1、2 问；第 3 问的 CLOCK 部分见 CLOCK 算法）。第 1 问拆页号：页大小 1 KB ⇒ 偏移 10 位，
17CAH的高位得页号 5。第 2 问按 FIFO 淘汰装入时刻最早的页——表中 0 号页装入时刻 130 最早，故淘汰它、新页装进 7 号页框，物理地址 = 页框号左移 10 位再拼偏移。⚠️ 这一问只看装入时刻那一列，访问位那一列在 FIFO 下完全无关——题目把访问位全给成 1 就是为了引你去看它。
复习优先级：性质必须记死，手算不必单练。 速记第五、六条（栈算法判据、谁会 Belady） 是必考且反复考的；手算 FIFO 极简单，跟着 LRU 一起练就够。 第八条那个"断裂只是必要条件"属于理解层面，不会直接设问，但它能防止你用错误的方法去判断异常。
易错：认为 LRU 也可能出现 Belady 异常。只有 FIFO 及其变体（含 CLOCK）会，LRU 和 OPT 是栈算法。
易错：用"哪个算法更好"去判断会不会 Belady。判据是排序依据依不依赖页框数，与优劣无关。
易错：FIFO 手算时去看访问位。FIFO 只看装入次序，访问位是 CLOCK 才用的。
易错：认为 FIFO 命中时要把该页移到队尾。命中时队列完全不动——这正是它的病根。
易错：认为进程切换时 FIFO 队列会重建。局部置换每进程一份、全局置换全系统一份，都不随切换重建。
易错：把"栈算法"理解成"加页框一定减少缺页"。它只保证不增，可能持平。
教材出处
- FIFO 的队列与替换指针、"含全局变量与常用函数的页面得不到保护"：汤小丹《计算机操作系统》5.3.1 节「先进先出(FIFO)页面置换算法」，p164
- Belady 于 1966 年提出最佳置换算法、并以此评价其他算法：同书 5.3.1 节，p163
相关知识
请求页式管理｜LRU 页面置换算法｜OPT 最佳置换算法｜CLOCK 与改进 CLOCK 算法｜页面置换模拟器