Appearance
FIFO 页面置换算法
考情分析
页面置换算法是虚拟内存管理的计算题重点（106分中的大头），FIFO 常作为对比算法出现，Belady 异常是选择题高频考点。🔥🔥🔥 。
内存满了要换出谁？最直觉的想法是"谁来得最早就换谁"，就像排队——先来的先走。FIFO 就是这个思路，简单但代价不小。
算法规则
FIFO（First In First Out）：淘汰最先进入内存的页面。
用一个队列维护页面进入内存的顺序，队头是最早进入的页面。
置换示例
页面引用串：3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4，分配 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 次，缺页率
交互可视化
Belady 异常 🔥🔥🔥
Belady 异常：增加分配的页框数，缺页次数反而增加。这就像给书架多加一层隔板，结果你要翻找的书反而更难找到——反直觉，但确实会发生。
这是 FIFO 独有的现象（LRU 和 OPT 不会出现）。
经典反例：页面引用串 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
| 页框数 | 缺页次数 |
|---|---|
| 3 | 9 |
| 4 | 10（反而增加了！） |
原因：FIFO 只考虑进入时间，不考虑使用频率。增加页框数并不能保证保留的是有用的页面。
易错
选择题常见干扰项："增加页框数一定能减少缺页次数"——错，FIFO 存在 Belady 异常。但 LRU 和 OPT 属于栈算法，增加页框数一定不会增加缺页次数。注意"不会增加"≠"一定减少"，缺页次数也可能不变。
FIFO 的优缺点
| 优点 | 缺点 |
|---|---|
| 实现最简单（队列） | 性能差（可能淘汰常用页面） |
| 存在 Belady 异常 | |
| 不是栈算法 |
考研高频考点
- 🔥🔥🔥 给定引用串和页框数，手算 FIFO 的缺页次数
- 🔥🔥🔥 Belady 异常的概念和经典反例
- 🔥🔥 FIFO 是唯一可能出现 Belady 异常的常考算法
- 🔥 FIFO 可能淘汰常用页面的原因
FIFO 只看"谁来得早"，完全不管页面是否还在被频繁使用。下篇来看 LRU——根据"最近使用情况"来决策，性能好得多。