Appearance
页面置换算法对比模拟器使用指南
考情分析
页面置换算法在 408 真题中累计考查约 40 分（2009-2026），属于 🔥🔥🔥 高频核心。最典型的题型：给一串页面引用序列和页框数，画出逐步替换表，数缺页次数。很多同学做这类题会在某一步"踢错页"，导致后面全错——因为脑子里没有清晰的"每一步内存里住着谁"的画面。
这个模拟器让你用同一引用串同时跑多种算法，逐步表格并排展示，缺页高亮标红，差异一目了然：
| 考点 | 你会在模拟器哪里看到 | 考频 |
|---|---|---|
| 逐步页框状态（考试原题格式） | 逐步表格 | 🔥🔥🔥 |
| 缺页次数 / 缺页率计算 | 表头统计 | 🔥🔥🔥 |
| 不同算法缺页次数对比 | 汇总对比表 | 🔥🔥🔥 |
| Belady 异常验证 | 改页框数对比 FIFO | 🔥🔥🔥 |
| 栈算法 vs 非栈算法 | OPT/LRU vs FIFO | 🔥🔥 |
跑完一轮对比大约 5 分钟。之后再做手算题，你会知道每一步该踢谁、为什么踢它。
第一步：输入数据
页面引用序列
在输入框输入一串页面号，用逗号或空格分隔。模拟器预置了经典引用串，你也可以直接输入真题的引用串。
推荐先用这组经典数据试跑：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1这组数据来自操作系统教材（Silberschatz），是所有教材和真题解析的标准示例。
物理帧数
默认 3 个页框，范围 1-10。页框数直接影响缺页次数——后面的实验会让你验证这一点。
真题验算
做完一道页面置换题后，把题目的引用串和页框数输入模拟器，选对应算法跑一遍——逐步表格和你的手画表对不上的地方，就是你出错的地方。
第二步：选择算法并运行
勾选你要对比的算法（可以多选），然后点击蓝色「运行对比」按钮：
| 算法 | 淘汰策略 | 一句话记忆 |
|---|---|---|
| FIFO | 最先进入内存的页面 | 谁先来谁先走（不管用没用过） |
| LRU | 最近最久没用的页面 | 谁最久没被访问谁走 |
| OPT | 未来最久不用的页面 | 谁将来最晚被需要谁走（需要预知未来，不可实现） |
| CLOCK | 访问位为 0 的页面 | 时钟指针转一圈，找第一个没被访问过的 |
建议第一次全选
四种算法全勾上，一次跑完。逐步表格上下排列，每一步的差异直接对照——你会发现 OPT 总是做出"最聪明"的选择，而 FIFO 经常"踢错人"。
第三步：看懂输出
逐步表格（核心）
每种算法一张表。这就是 408 考试要你画的那张表的精确格式：
- 列 = 引用序列中的每个页面
- 行 = 每个页框（帧 0、帧 1、帧 2...）
- 红色背景行 = 该步发生了缺页（页面不在内存中，需要调入）
- 表头 = 显示缺页次数和缺页率
你应该重点看的三件事：
1. 红色行出现的位置
前几步一定全红（内存为空，每个页面都是第一次进入）。后面红色行出现得越少，说明算法性能越好。对比 OPT 和 FIFO 的红色行数量——差距通常很大。
2. 发生缺页时哪个页面被踢出去了
这是手算时最容易出错的地方。缺页时，仔细看表格里哪个页框的内容变了——被替换的就是"被踢的页"。
- FIFO：被踢的永远是最早进来的（不管它最近有没有被访问）
- LRU：被踢的是最近最久没被访问的
- OPT：被踢的是未来最晚被需要的（或者再也不需要的）
3. 关键分歧点
同一步，FIFO 踢了页 A，LRU 踢了页 B——从这一步开始，两个算法的内存状态完全不同，后续的缺页次数也会不同。找到这些分歧点，理解"为什么踢的不一样"，就是真正掌握了算法差异。
408 手算题必看
考试的标准答题格式就是模拟器展示的这张表：
| 7 | 0 | 1 | 2 | 0 | 3 | ... | |
|---|---|---|---|---|---|---|---|
| 帧 0 | 7 | 7 | 7 | 2 | 2 | 2 | ... |
| 帧 1 | 0 | 0 | 0 | 0 | 3 | ... | |
| 帧 2 | 1 | 1 | 1 | 1 | ... | ||
| 缺页 | ✓ | ✓ | ✓ | ✓ | ✓ | ... |
在模拟器里跑一遍，和你手画的表逐列对照。某一列不一样 = 你在那一步踢错了页面。
汇总对比表
最底部的汇总表把所有算法的缺页次数和缺页率放在一起：
以经典引用串（20 个引用，3 个页框）为例：
| 算法 | 缺页次数 | 缺页率 |
|---|---|---|
| OPT | 9 | 45% |
| LRU | 12 | 60% |
| CLOCK | ~13 | ~65% |
| FIFO | 15 | 75% |
OPT 永远最优（但不可实现），LRU 是实际最优，FIFO 通常最差。
关键实验：调参数看差异
实验 1：验证 Belady 异常（FIFO 专属 bug）
这是 408 的高频考点——增加页框数，FIFO 的缺页次数反而增加。
操作步骤：
- 输入引用串：
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 - 只勾选 FIFO
- 页框数设为 3 → 运行 → 记录缺页次数（应该是 9）
- 页框数改为 4 → 运行 → 记录缺页次数（应该是 10）
4 个页框比 3 个页框缺页更多！
增加了内存，性能反而下降——这就是 Belady 异常。它只出现在 FIFO 中，OPT 和 LRU 绝对不会出现（因为它们是栈算法）。
验证方法：同样的引用串，勾选 OPT + LRU，页框 3→4，缺页次数一定减少或不变。
实验 2：OPT vs LRU——"预知未来"值多少
- 用经典引用串，3 个页框
- 勾选 OPT + LRU
- 找到两个算法第一个分歧点——某一步 OPT 踢了页 A，LRU 踢了页 B
- 思考：OPT 为什么选 A？因为 A 在未来最晚出现。LRU 为什么选 B？因为 B 过去最久没被访问
OPT 和 LRU 的思路其实是镜像的——OPT 看未来，LRU 看过去。LRU 是"用过去近似未来"，所以性能接近 OPT。
实验 3：页框数对缺页率的影响
- 用经典引用串，勾选 LRU
- 页框数从 2 → 3 → 4 → 5 → 6 逐步增加
- 观察缺页次数的下降趋势
你会发现：页框数越多，缺页次数越少——但递减速度会变慢。从 3→4 可能减少 3 次缺页，从 5→6 可能只减少 1 次。这就是为什么实际系统中不会无限增加物理内存——边际收益递减。
算法速查表
| 算法 | 淘汰策略 | 可实现性 | Belady 异常 | 性能排名 |
|---|---|---|---|---|
| OPT | 未来最久不用的页面 | 不可实现 | 无 | 1（最优） |
| LRU | 最近最久没用的页面 | 计数器/栈 | 无 | 2 |
| CLOCK | 访问位为 0 的页面 | 循环链表 | 可能有 | 3 |
| FIFO | 最先进入内存的页面 | 队列 | 有 | 4（最差） |
关键对比维度
栈算法 vs 非栈算法
栈算法：n 个页框时驻留在内存中的页面集合，一定是 n+1 个页框时的子集。
| 栈算法 | 非栈算法 |
|---|---|
| OPT、LRU | FIFO |
| 不会出现 Belady 异常 | 可能出现 Belady 异常 |
过去 vs 未来
| 算法 | 决策依据 |
|---|---|
| OPT | 看未来（不可实现） |
| LRU | 看过去（近似 OPT 的思路） |
| FIFO | 看进入时间（不关心使用情况） |
| CLOCK | 看近期是否访问过（近似 LRU，开销更低） |
推荐使用流程
第一轮：建立直觉（3 分钟）
- 用经典引用串，3 个页框，全选 4 种算法，点「运行对比」
- 从上到下扫四张逐步表格——数红色行的数量：OPT 最少，FIFO 最多
- 看汇总表的缺页次数排序，记住 OPT ≤ LRU ≤ CLOCK ≤ FIFO
第二轮：理解差异（5 分钟）
- 找 FIFO 和 LRU 的第一个分歧点——同一步踢的页不一样
- 想清楚：FIFO 踢的是最早进来的（可能最近刚用过），LRU 踢的是最久没用的（更合理）
- 做 Belady 异常实验——亲眼看到"增加页框缺页反而增多"
第三轮：验算真题（按需）
- 把真题的引用串和页框数输入模拟器
- 选对应算法跑出逐步表格
- 和你的手画表逐列对照——某一列不一样 = 你在那一步踢错了页面
- 回到那一步，想清楚为什么该踢这个页而不是另一个
考研高频考点速览
| 考点 | 考频 | 关键记忆 |
|---|---|---|
| 给定引用串画逐步表 | 🔥🔥🔥 | 逐步模拟，每步检查是否命中，不命中则按策略淘汰 |
| 缺页次数/缺页率计算 | 🔥🔥🔥 | 缺页率 = 缺页次数 / 引用串长度 |
| Belady 异常 | 🔥🔥🔥 | 只有 FIFO 会出现，OPT/LRU（栈算法）不会 |
| 各算法性能排序 | 🔥🔥🔥 | OPT ≤ LRU ≤ FIFO（缺页次数） |
| 栈算法的定义 | 🔥🔥 | n 页框的驻留集 ⊆ n+1 页框的驻留集 |
| CLOCK 算法工作过程 | 🔥🔥 | 时钟指针扫描，访问位=1 清零跳过，访问位=0 淘汰 |
置换算法决定了"淘汰谁"，但还有一个问题：每个进程该分多少页框？分配策略和置换范围怎么搭配？下篇来看页框分配与回收。