Appearance
页面置换算法对比模拟器使用指南
手算逐步替换表时，很多人会在某一步"踢错页"，导致后面全错——因为脑子里没有清晰的"每一步内存里住着谁"的画面。
这个模拟器让你用同一引用串同时跑多种算法，逐步表格并排展示，缺页高亮标红，差异一目了然：
| 关注点 | 你会在模拟器哪里看到 |
|---|---|
| 逐步页框状态 | 逐步表格 |
| 缺页次数 / 缺页率计算 | 表头统计 |
| 不同算法缺页次数对比 | 汇总对比表 |
| 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这组数据是汤小丹《计算机操作系统》讲页面置换算法时用的引用串（见文末教材出处），OPT 篇用的也是它。
本站用到的两套引用串，别混
| 名称 | 引用串 | 3 页框下的缺页次数 | 出现在 |
|---|---|---|---|
| 串甲 | 3,2,1,0,3,2,4,3,2,1,0,4 | FIFO 9 / LRU 10 / OPT 7 / CLOCK 9 | FIFO 篇、LRU 篇 |
| 串乙 | 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 | FIFO 15 / LRU 12 / OPT 9 / CLOCK 14 | OPT 篇、本页 |
两处数字对不上不是笔误——缺页次数是"算法 + 引用串 + 页框数"三者共同的函数。换一个串，连算法之间的相对优劣都可能翻转：串甲上 FIFO（9）反而比 LRU（10）少缺一次，原因见 LRU 篇 §四。
物理帧数
默认 3 个页框，范围 1-10。页框数直接影响缺页次数——后面的实验会让你验证这一点。
对照验算
手算完一组引用串后，把引用串和页框数原样输入模拟器，选对应算法跑一遍——逐步表格和你手画的表对不上的地方，就是你算错的地方。
第二步：选择算法并运行
勾选你要对比的算法（可以多选），然后点击蓝色「运行对比」按钮：
| 算法 | 淘汰策略 | 一句话记忆 |
|---|---|---|
| FIFO | 最先进入内存的页面 | 谁先来谁先走（不管用没用过） |
| LRU | 最近最久没用的页面 | 谁最久没被访问谁走 |
| OPT | 未来最久不用的页面 | 谁将来最晚被需要谁走（需要预知未来，不可实现） |
| CLOCK | 访问位为 0 的页面 | 时钟指针转一圈，找第一个没被访问过的 |
建议第一次全选
四种算法全勾上，一次跑完。逐步表格上下排列，每一步的差异直接对照——你会发现 OPT 总是做出"最聪明"的选择，而 FIFO 经常"踢错人"。
第三步：看懂输出
逐步表格（核心）
每种算法一张表。这就是手算页面置换时要画的那张表的精确格式：
- 列 = 引用序列中的每个页面
- 行 = 每个页框（帧 0、帧 1、帧 2...）
- 红色背景行 = 该步发生了缺页（页面不在内存中，需要调入）
- 表头 = 显示缺页次数和缺页率
你应该重点看的三件事：
1. 红色行出现的位置
前几步一定全红（内存为空，每个页面都是第一次进入）。后面红色行出现得越少，说明算法性能越好。对比 OPT 和 FIFO 的红色行数量——差距通常很大。
2. 发生缺页时哪个页面被踢出去了
这是手算时最容易出错的地方。缺页时，仔细看表格里哪个页框的内容变了——被替换的就是"被踢的页"。
- FIFO：被踢的永远是最早进来的（不管它最近有没有被访问）
- LRU：被踢的是最近最久没被访问的
- OPT：被踢的是未来最晚被需要的（或者再也不需要的）
3. 关键分歧点
同一步，FIFO 踢了页 A，LRU 踢了页 B——从这一步开始，两个算法的内存状态完全不同，后续的缺页次数也会不同。找到这些分歧点，理解"为什么踢的不一样"，就是真正掌握了算法差异。
逐步替换表的标准格式
手算时要画的就是模拟器展示的这张表：
| 7 | 0 | 1 | 2 | 0 | 3 | ... | |
|---|---|---|---|---|---|---|---|
| 帧 0 | 7 | 7 | 7 | 2 | 2 | 2 | ... |
| 帧 1 | 0 | 0 | 0 | 0 | 3 | ... | |
| 帧 2 | 1 | 1 | 1 | 1 | ... | ||
| 缺页 | ✓ | ✓ | ✓ | ✓ | ✓ | ... |
在模拟器里跑一遍，和你手画的表逐列对照。某一列不一样 = 你在那一步踢错了页面。
汇总对比表
最底部的汇总表把所有算法的缺页次数和缺页率放在一起：
以串乙 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1（20 个引用，3 个页框）为例：
| 算法 | 缺页次数 | 缺页率 |
|---|---|---|
| OPT | 9 | 45% |
| LRU | 12 | 60% |
| CLOCK | 14 | 70% |
| FIFO | 15 | 75% |
OPT 永远最优（但不可实现），LRU 是实际最优，FIFO 通常最差。
这四个数只属于串乙
换一个引用串，数字全都会变，连相对次序都可能变——串甲 3,2,1,0,3,2,4,3,2,1,0,4 在 3 个页框下就是 FIFO 9、LRU 10，FIFO 反而更少。所以对照本站其他篇的数字时，先看清用的是哪一串。
关键实验：调参数看差异
实验 1：验证 Belady 异常（FIFO 专属 bug）
增加页框数，FIFO 的缺页次数反而增加。
操作步骤：
- 输入引用串：
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5（它就是串甲换了页号：把 3、2、1、0、4 依次改名为 1、2、3、4、5 即得，两串逐位相同） - 只勾选 FIFO
- 页框数设为 3 → 运行 → 记录缺页次数（应该是 9）
- 页框数改为 4 → 运行 → 记录缺页次数（应该是 10）
4 个页框比 3 个页框缺页更多！
增加了内存，性能反而下降——这就是 Belady 异常。它出现在非栈算法上，也就是 FIFO 及其变体 CLOCK；OPT 和 LRU 绝对不会出现（因为它们是栈算法）。
验证方法：同样的引用串，勾选 OPT + LRU，页框 3→4，缺页次数一定减少或不变。
顺手把 CLOCK 也勾上：同一串下 CLOCK 3 个页框缺页 9 次、4 个页框缺页 10 次——CLOCK 一样会出 Belady 异常。原因见 CLOCK 篇：它的骨架仍是"环形队列 + 装入时刻"，排不出与页框数无关的顺序。
实验 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 逐步增加
- 观察缺页次数的下降趋势
串乙跑 LRU 的实际结果是：2 框 17 → 3 框 12 → 4 框 8 → 5 框 7 → 6 框 6，每一档的降幅依次是 5、4、1、1。
你会发现：页框数越多，缺页次数越少——但递减速度明显变慢，前两档各省 4～5 次，后两档各只省 1 次。这就是为什么实际系统中不会无限增加物理内存——边际收益递减。降幅塌下来的那一档，正是驻留集刚刚覆盖住工作集的地方（见页框分配与回收）。
算法速查表
| 算法 | 淘汰策略 | 可实现性 | Belady 异常 | 性能排名 |
|---|---|---|---|---|
| OPT | 未来最久不用的页面 | 不可实现 | 无 | 1（最优） |
| LRU | 最近最久没用的页面 | 计数器/栈 | 无 | 2 |
| CLOCK | 访问位为 0 的页面 | 循环链表 | 可能有 | 3 |
| FIFO | 最先进入内存的页面 | 队列 | 有 | 4（最差） |
关键对比维度
栈算法 vs 非栈算法
栈算法：n 个页框时驻留在内存中的页面集合，一定是 n+1 个页框时的子集。
| 栈算法 | 非栈算法 |
|---|---|
| OPT、LRU | FIFO、CLOCK（含改进 CLOCK） |
| 排序依据（下次访问位置 / 最后访问时刻）与页框数无关 | 排序依据（装入时刻）随页框数变动 |
| 不会出现 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 与 CLOCK；OPT/LRU（栈算法）不会 |
| 各算法性能排序 | 平均而言 OPT ≤ LRU ≤ CLOCK ≤ FIFO（缺页次数）；逐串只有 OPT 最少这一条恒成立，LRU 与 FIFO 的先后会随引用串翻转 |
| 栈算法的定义 | n 页框的驻留集 ⊆ n+1 页框的驻留集 |
| CLOCK 算法工作过程 | 时钟指针扫描，访问位=1 清零跳过，访问位=0 淘汰 |
置换算法决定了"淘汰谁"，但还有一个问题：每个进程该分多少页框？分配策略和置换范围怎么搭配？下篇来看页框分配与回收。
教材出处
- 本页推荐的引用串
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1与 3 个物理块的设定，出自汤小丹《计算机操作系统》5.3.1 节「最佳(Optimal)置换算法」及图 5-3，p163。教材记的是置换次数——最佳置换算法"发生了 6 次页面置换"，加上最初装入 7、0、1 的 3 次，即缺页 9 次，与上面汇总表一致。 - 同一引用串下 FIFO"进行了 12 次页面置换，比最佳置换算法正好多一倍"（即缺页 15 次）：同书 5.3.1 节及图 5-4，p164。
- 注意教材与模拟器的计数口径不同：教材数的是置换次数，模拟器数的是缺页次数，两者相差一个页框数（在页框被装满的前提下）。