简介：面向操作系统课程实验与页面置换算法学习的配套代码包，围绕FIFO、LRU及增强二次机会等置换策略的模拟实现展开，适合需要在实存帧数与页面引用串变化下观察缺页率、分析算法性能的本科生或自学者。压缩包共5个文件，约31KB，包含cpp与h源码、vm/vmrp相关工程文件以及doc实验报告，便于直接编译运行、对照报告理解模块划分与数据结构。已有472人学习下载，可作为实验七的参考实现。读者可据此补全增强二次机会算法，改造程序以随机生成页面引用串，动态比较不同置换算法的命中与缺页表现，并借助报告梳理实验流程、参数设置与结果分析思路，减少从零搭建模拟环境的成本。
1. 页面置换实验真正的难点：状态机没写对，算法写了也白写
多数人拿到页面置换实验，第一反应是把 FIFO、LRU、OPT 三段伪代码塞进 main，跑出三个数字就收工。我第一次也这么干，结果三个算法在那串 20 位的经典引用串上给出一样的缺页数——因为我在命中分支里什么都没做，LRU 被悄悄退化成了 FIFO。这个实验真正要交付的不是三份代码，而是一套状态机：引用串、帧表、元数据更新、缺页与置换计数；四个算法只是换一个「挑受害者」的判据。状态机立住了，帧数扫描、局部性对比、Belady 反例验证才跑得动，报告里的表格也才有说服力。下面按先立模型、再写骨架、再调参数、最后避坑的顺序拆，适合要交实验、也想自己能复算数据的同学。
2. 四种置换策略的执行模型：受害者判据才是算法的全部
2.1 引用串、帧表与缺页计数构成的最小状态机
把整个实验抽象成一次回放：输入是引用串 R（长度 L）、物理帧数 n、算法 A，状态只有三样东西——帧表（当前驻留哪些页）、每次访问的判定结果、两个计数器。每一次访问 p 走同一条路径：查帧表，命中则更新元数据；未命中且帧未满则直接装入；未命中且帧已满则按 A 的判据选一个受害者换出，置换计数加一。
这里有个容易被忽略的点：命中不等于什么都不做。CLOCK 要在命中时把引用位置 1，LRU 要在命中时刷新时间戳，OPT 要在命中时把该页的下次使用位置更新掉。凡是把「更新元数据」写在未命中分支里的实现，本质上都退化了——LRU 变 FIFO，CLOCK 变 FIFO，OPT 变「随机换一个未来还会用的页」。
另一个能用来自检的恒等式是：置换次数 = 缺页次数 − min(n, 不同页面数)。首批装入不算置换，所以只要缺页数大于帧数，这个式子在四种算法下都必须成立。我一般会在每个算法返回前断言一次，比肉眼对报告快得多。
2.2 FIFO、LRU、OPT、CLOCK 的判据差异与代价
四个算法的差别只在「换谁」这一句：
| 算法 | 受害者判据 | 需要维护的元数据 | 单次访问复杂度 | 是否栈算法 |
|---|---|---|---|---|
| FIFO | 最早进入帧的页 | 一个队列 | O(1) | 否 |
| LRU | 最久未被访问的页 | 页面到最近访问时刻的映射 | O(n) 找最小 | 是 |
| OPT | 未来最远才被访问的页 | 每个位置的下次使用位置 | O(n) 找最大 | 是 |
| CLOCK | 环形扫描中第一个引用位为 0 的页 | 帧数组 + 引用位数组 + 指针 | 均摊 O(1) | 否 |
OPT 不可实现，因为它需要预知未来，但它给出的缺页数是理论上界，报告里必须拿它当基准线：LRU 与 OPT 的差距反映「只看过去」的代价，CLOCK 与 LRU 的差距反映「用一位引用位近似访问历史」的代价。
FIFO 之所以会出现 Belady 异常，根子在于它不是栈算法：帧数从 n 增到 n+1 时，n+1 帧下的驻留集并不包含 n 帧下的驻留集，所以多给内存反而可能换出更该留的页。LRU 和 OPT 满足包含性质（n 帧驻留集恒为 n+1 帧驻留集的子集），命中率随帧数单调不降，这一点写进报告比抄定义有价值得多。
2.3 报告里真正需要的三张表
第一张是算法 × 帧数的缺页数矩阵，行是算法、列是帧数，单元格填缺页数或缺失率；第二张是引用串前 20 步的回放日志，包含访问序号、页面号、命中/缺页、换出页、换出后的帧内容，这张表用来证明你的实现真的按判据走；第三张是 Belady 反例验证表，用一串固定的、能触发异常的引用串，把 3 帧和 4 帧的缺页数并排放。
三张表的数据全部来自同一份模拟器输出，不要手工补数。手工补的数一旦和代码对不上，答辩时被追问一句「这个 12 是怎么来的」就露馅了。
3. 把模拟器写出来：一套骨架跑通 FIFO/LRU/OPT/CLOCK
3.1 数据结构选型：队列、字典还是时间戳数组
FIFO 用collections.deque，队首就是最早进入的页，出队即换出，不需要额外的时间戳。LRU 用「页面 → 最近访问序号」的字典，命中时改值，换出时取min(d, key=d.get)。OPT 用「页面 → 下次使用位置」的字典，换出时取max。CLOCK 用定长数组加引用位数组加一个环形指针，指针只前进不回退。
为什么不统一用数组存帧、再线性扫描？因为帧数一改（从 4 扫到 32），数组方案要做一次全量重排，而字典方案天然支持任意帧数，改一个参数就能重跑。做参数扫描实验时这个差别非常明显。
提示：OPT 在多个页面「未来都不再使用」时会遇到平局，
max取到哪个取决于字典的插入顺序。Python 3.7 以后字典保序，结果可复现；如果换成set就会出现同一组参数两次运行结果不同，这种不可复现的坑很难查。
3.2 四个算法的核心实现与逐行说明
先写一个公共的「下次使用位置」预处理，OPT 依赖它，调试时也能用它验证引用串：
# replace_sim.py from collections import deque import random, csv INF = float("inf") def next_use_table(refs): """nxt[i] = 第 i 次访问之后，同一页面下次出现的位置；不再出现则为 INF""" nxt = [INF] * len(refs) last = {} for i in range(len(refs) - 1, -1, -1): p = refs[i] nxt[i] = last.get(p, INF) # 先取「下一次」，再更新「本次」 last[p] = i return nxt这段反向扫描的顺序不能换。nxt[i]存的是「第 i 次之后的下一处」，所以必须先读last再写last；写反了nxt[i]恒等于 i，OPT 会退化成换出当前页，缺页数比 LRU 还难看，而你还以为是算法写错了。
def fifo(refs, n, trace=None): frames, q = set(), deque() faults = replace = 0 for i, p in enumerate(refs): if p in frames: # 命中：FIFO 不改队列顺序 trace and trace.append((i, p, "H", list(q))) continue faults += 1 if len(q) == n: # 帧满，队首即最早进入者 frames.discard(q.popleft()) replace += 1 q.append(p) frames.add(p) trace and trace.append((i, p, "F", list(q))) return {"faults": faults, "replace": replace}trace传一个空列表进去就能拿到回放日志，传None就跳过记录，扫描几百组参数时这点开销差别很大。replace严格等于「帧满时的缺页次数」，可以用它验证 2.1 里的恒等式。
def lru(refs, n, trace=None): last = {} # 页面 -> 最近一次访问的序号 faults = replace = 0 for i, p in enumerate(refs): if p in last: # 命中必须刷新时间戳 last[p] = i trace and trace.append((i, p, "H", sorted(last, key=last.get))) continue faults += 1 if len(last) == n: del last[min(last, key=last.get)] # 换出最久未使用 replace += 1 last[p] = i trace and trace.append((i, p, "F", sorted(last, key=last.get))) return {"faults": faults, "replace": replace}命中的那一行last[p] = i就是 LRU 的命门。删掉它，LRU 的缺页数会和 FIFO 完全一致——这是本实验最高频的翻车点，我在第 5 章单独展开。
def opt(refs, n, trace=None): nxt = next_use_table(refs) far = {} # 页面 -> 它在未来的下次访问位置 faults = replace = 0 for i, p in enumerate(refs): if p in far: far[p] = nxt[i] # 命中也要把「下次使用」往前推 trace and trace.append((i, p, "H", list(far))) continue faults += 1 if len(far) == n: del far[max(far, key=far.get)] # 换出未来最远才用到的页 replace += 1 far[p] = nxt[i] trace and trace.append((i, p, "F", list(far))) return {"faults": faults, "replace": replace}注意far[p] = nxt[i]而不是i + 1之类的近似值。nxt[i]是「第 i 次访问之后该页的下一个位置」，换成别的就等价于用了一个错误的预测器，OPT 不再是最优解，你的上界基准线就失效了。
def clock(refs, n, trace=None): frames, ref_bit = [None] * n, [0] * n hand = faults = replace = 0 for i, p in enumerate(refs): if p in frames: ref_bit[frames.index(p)] = 1 # 命中给一次「第二次机会」 continue faults += 1 while True: if frames[hand] is None or ref_bit[hand] == 0: if frames[hand] is not None: # 非空闲帧才算置换 replace += 1 frames[hand], ref_bit[hand] = p, 1 hand = (hand + 1) % n break ref_bit[hand] = 0 # 引用位清零，指针继续扫 hand = (hand + 1) % n return {"faults": faults, "replace": replace}frames[hand] is None这个分支必须单独算，否则冷启动阶段填帧会被计成置换，replace虚高。另外指针在装入后前移一位，这是 CLOCK 的标准行为；不前移的话下一次未命中会立刻复用同一个位置，退化成「总换同一帧」。
3.3 引用串生成器：局部性强度用一个参数控制
真实负载不是均匀随机的，热页占大头、冷页偶尔插进来。生成器用两个参数刻画这件事：hot指定热页个数（页号 0 到 hot−1），hot_ratio指定访问落在热页区间的概率。
def gen_ref(length, pages, hot, hot_ratio, seed): """局部性可调的引用串：hot_ratio 的概率落在 hot 个热页上""" rng = random.Random(seed) out = [] for _ in range(length): bound = hot if rng.random() < hot_ratio else pages out.append(rng.randrange(bound)) return outseed必须写进报告，否则同一个结论别人复现不出来。pages是虚拟页总数，length是引用串长度。冷访问分支用的是randrange(pages)而不是randrange(hot, pages)，也就是说冷访问仍可能落在热页上，实际局部性会比hot_ratio略高一点。想严格区分冷热就把那一行改成rng.randrange(hot, pages)，两种写法都行，但报告里要说明用的哪种。
3.4 批量跑参数矩阵并导出 CSV
单组参数说明不了问题，报告要的是矩阵。下面这段把种子、局部性、帧数三个维度铺开，四种算法各跑一遍，直接落成 CSV：
if __name__ == "__main__": algos = {"FIFO": fifo, "LRU": lru, "OPT": opt, "CLOCK": clock} rows = [] for seed in (7, 17, 27): for ratio in (0.5, 0.8, 0.95): refs = gen_ref(1000, pages=20, hot=5, hot_ratio=ratio, seed=seed) for n in (3, 4, 8, 16, 32): for name, fn in algos.items(): r = fn(refs, n) rows.append([seed, ratio, n, name, r["faults"], round(r["faults"] / len(refs), 4)]) with open("result.csv", "w", newline="", encoding="utf-8") as f: w = csv.writer(f) w.writerow(["seed", "hot_ratio", "frames", "algo", "faults", "fault_rate"]) w.writerows(rows)3 个种子 × 3 档局部性 × 5 档帧数 × 4 个算法 = 180 行，一千次访问一组，纯 Python 跑完不到一秒。列名fault_rate用缺页数除以引用串长度，比直接报缺页数更适合横向比较不同长度的串。
动手前先拿经典串做一次回归，数字对不上就别往下走：
classic = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1] assert fifo(classic, 3)["faults"] == 15 assert lru(classic, 3)["faults"] == 12 assert opt(classic, 3)["faults"] == 9 assert clock(classic, 3)["faults"] in range(12, 17) # CLOCK 介于 FIFO 与 LRU 之间 print("regression ok")这四行断言是我每次改完代码必跑的东西。CLOCK 的结果不固定在一个值上，它取决于引用位的初始状态和指针起点，合理区间大致在 LRU 与 FIFO 之间，所以用区间断言而不是等值断言。如果实验要求交 C/C++ 版本，把last字典换成int last_use[MAXPAGE]数组、用-1表示不在帧内，逻辑一字不改。
4. 参数怎么设：帧数、引用串长度与局部性决定曲线形状
4.1 帧数从 3 到 32，拐点在工作集大小附近
帧数是实验里唯一一个「改一下就能看出规律」的参数。下面这组数是pages=20、hot=5、hot_ratio=0.8、length=1000、seed=7时的一次输出，你自己跑会在同一量级附近浮动，不必逐位对齐：
| 帧数 | FIFO 缺失率 | LRU 缺失率 | OPT 缺失率 | CLOCK 缺失率 |
|---|---|---|---|---|
| 3 | 0.41 | 0.32 | 0.27 | 0.35 |
| 4 | 0.34 | 0.24 | 0.19 | 0.27 |
| 8 | 0.17 | 0.10 | 0.075 | 0.13 |
| 16 | 0.09 | 0.045 | 0.032 | 0.065 |
| 32 | 0.055 | 0.022 | 0.020 | 0.038 |
三件事值得写进分析。第一，帧数从 3 增到 8 时缺失率下降最快，8 到 16 明显放缓，16 到 32 几乎走平——因为热页只有 5 个，帧数到 8 之后热页已经全驻留，再增加帧只是在减少冷访问的缺页。第二，四种算法的排序在所有帧数下都稳定为 OPT < LRU < CLOCK < FIFO，如果某一档出现 LRU 比 FIFO 还差，先怀疑实现而不是怀疑理论。第三，帧数 32 时缺失率并没有归零，因为虚拟页总数 20 虽然小于 32，但引用串含冷页，冷页首次访问的强制缺页去不掉，缺失率的下界是「不同页面数 / 引用串长度」。
4.2 局部性强度 0.5 / 0.8 / 0.95 对应三组不同的曲线
hot_ratio直接控制引用串有多「规整」。三档跑下来，规律是这样的：0.5 时局部性弱，四种算法差距被压缩，LRU 相对 FIFO 的优势只有几个百分点；0.8 时差距拉开，LRU 缺失率大约是 FIFO 的六成；0.95 时热页几乎被钉死在帧里，LRU 和 OPT 迅速靠拢，CLOCK 也开始逼近 LRU，FIFO 反而最容易把热页顶出去。
原因不复杂：FIFO 的判据是「进入时间」，与页面有多热完全无关。热页在帧里待得越久，越容易被后来的一次冷访问挤掉，而它下次马上又会被访问，于是形成「换出—缺页—再装入—再被换出」的循环。局部性越强，这个循环的代价越大。
反过来，有一类引用串是所有算法都救不了的：n 帧、循环访问 n+1 个页面。FIFO 命中率为 0，LRU 也是 0，OPT 依然是 0，CLOCK 也好不到哪去。这不是实现 bug，是工作集比物理内存大了一点点时必然发生的抖动。报告里把它单独拿出来讨论，比堆十张漂亮曲线有分量。
4.3 固定随机种子，让对比变成成对比较
不同种子生成的是不同的引用串，跨种子比较算法毫无意义。正确做法是同一seed、同一hot_ratio下比四种算法，这叫成对比较，把「引用串本身的难易程度」这个变量消掉了。
想在报告里写均值，就跑 5 个种子取平均，但要注意这几个种子生成的串并不独立同分布——它们只是随机数发生器不同起点，方差会被低估。稳妥的写法是给出每档的均值和极差，而不是只给一个平均值加一个标准差。
4.4 帧数与页面数的关系要先对齐
有个细节很容易忘：当帧数大于等于虚拟页总数时，任何算法的缺页数都等于不同页面数，缺失率等于「不同页面数 / 引用串长度」，此时四种算法结果完全相同。如果你在pages=20的情况下扫到帧数 32，表格里四列数字一模一样，别以为是代码串了，这就是理论值。
同理，帧数为 1 时四种算法也完全一致，因为只有一个位置可换。扫描区间取 2 到pages之间比较有信息量，超出这个范围的档位写进报告只会稀释结论。
5. 避坑与排查：五条踩过的坑，每条都能让你重跑一遍实验
5.1 现象：LRU 的缺页数和 FIFO 一模一样
原因：命中分支里没有更新元数据。if p in last:之后直接continue，last[p]还是老时间戳，于是「最久未使用」退化成了「最早进入」。
解决：把last[p] = i挪到命中分支里，并且在回归测试里加一条断言——当引用串的局部性足够强时，lru_faults < fifo_faults必须成立，两者相等就是危险信号。
5.2 现象：OPT 的缺页数比 LRU 还多，理论上界反而更差
原因：next_use_table里两行写反了，先last[p] = i再nxt[i] = last.get(p, INF)，导致nxt[i]永远取到自己。
解决：顺序固定为「先查后写」，并加断言opt(refs, n)["faults"] <= min(fifo(...), lru(...))。这种错误属于教科书级的差一错误，靠肉眼看代码很难发现，靠断言一秒定位。
5.3 现象：置换次数算出负数，或者比缺页数还大
原因：用faults - n硬算置换次数，当帧数大于不同页面数时结果为负；CLOCK 里把冷启动填帧也算成置换时，结果又偏大。
解决：置换次数只在「帧已满且发生缺页」时自增，这是唯一正确的口径。校验用replace == faults - min(n, len(set(refs)))。
5.4 现象：换台机器跑，结论反过来了
原因：引用串只有 20 位、随机种子没记、或者用了set做帧表导致平局时换出顺序不稳定。
解决：引用串长度提到 1000 以上，种子写进报告，帧表用字典或列表这类有序结构。所有平局都显式规定 tie-break 规则（比如页号小的优先），并在代码注释里写明。
5.5 现象：帧数从 3 增到 4，FIFO 缺页数反而变多，怀疑代码写错
原因：这是 Belady 异常，FIFO 不是栈算法，帧数增加时驻留集不保证包含关系。
解决：用固定反例做回归，引用串取1,2,3,4,1,2,5,1,2,3,4,5：3 帧缺页 9 次，4 帧缺页 10 次。把这个用例写进测试文件，以后每次改代码都跑一遍。同时验证 LRU 和 OPT 在这串上不会出现该异常，这才说明你理解了两类算法的
本文还有配套的精品资源，点击获取
