页面置换算法实验：从状态机到FIFO/LRU/OPT/CLOCK模拟器避坑

简介面向操作系统课程实验与页面置换算法学习的配套代码包围绕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 要在命中时把引用位置 1LRU 要在命中时刷新时间戳OPT 要在命中时把该页的下次使用位置更新掉。凡是把「更新元数据」写在未命中分支里的实现本质上都退化了——LRU 变 FIFOCLOCK 变 FIFOOPT 变「随机换一个未来还会用的页」。另一个能用来自检的恒等式是置换次数 缺页次数 − 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 增到 n1 时n1 帧下的驻留集并不包含 n 帧下的驻留集所以多给内存反而可能换出更该留的页。LRU 和 OPT 满足包含性质n 帧驻留集恒为 n1 帧驻留集的子集命中率随帧数单调不降这一点写进报告比抄定义有价值得多。2.3 报告里真正需要的三张表第一张是算法 × 帧数的缺页数矩阵行是算法、列是帧数单元格填缺页数或缺失率第二张是引用串前 20 步的回放日志包含访问序号、页面号、命中/缺页、换出页、换出后的帧内容这张表用来证明你的实现真的按判据走第三张是 Belady 反例验证表用一串固定的、能触发异常的引用串把 3 帧和 4 帧的缺页数并排放。三张表的数据全部来自同一份模拟器输出不要手工补数。手工补的数一旦和代码对不上答辩时被追问一句「这个 12 是怎么来的」就露馅了。3. 把模拟器写出来一套骨架跑通 FIFO/LRU/OPT/CLOCK3.1 数据结构选型队列、字典还是时间戳数组FIFO 用collections.deque队首就是最早进入的页出队即换出不需要额外的时间戳。LRU 用「页面 → 最近访问序号」的字典命中时改值换出时取min(d, keyd.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]恒等于 iOPT 会退化成换出当前页缺页数比 LRU 还难看而你还以为是算法写错了。def fifo(refs, n, traceNone): 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, traceNone): 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, keylast.get))) continue faults 1 if len(last) n: del last[min(last, keylast.get)] # 换出最久未使用 replace 1 last[p] i trace and trace.append((i, p, F, sorted(last, keylast.get))) return {faults: faults, replace: replace}命中的那一行last[p] i就是 LRU 的命门。删掉它LRU 的缺页数会和 FIFO 完全一致——这是本实验最高频的翻车点我在第 5 章单独展开。def opt(refs, n, traceNone): 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, keyfar.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, traceNone): 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−1hot_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单组参数说明不了问题报告要的是矩阵。下面这段把种子、局部性、帧数三个维度铺开四种算法各跑一遍直接落成 CSVif __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, pages20, hot5, hot_ratioratio, seedseed) 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, encodingutf-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拐点在工作集大小附近帧数是实验里唯一一个「改一下就能看出规律」的参数。下面这组数是pages20、hot5、hot_ratio0.8、length1000、seed7时的一次输出你自己跑会在同一量级附近浮动不必逐位对齐帧数FIFO 缺失率LRU 缺失率OPT 缺失率CLOCK 缺失率30.410.320.270.3540.340.240.190.2780.170.100.0750.13160.090.0450.0320.065320.0550.0220.0200.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 也开始逼近 LRUFIFO 反而最容易把热页顶出去。原因不复杂FIFO 的判据是「进入时间」与页面有多热完全无关。热页在帧里待得越久越容易被后来的一次冷访问挤掉而它下次马上又会被访问于是形成「换出—缺页—再装入—再被换出」的循环。局部性越强这个循环的代价越大。反过来有一类引用串是所有算法都救不了的n 帧、循环访问 n1 个页面。FIFO 命中率为 0LRU 也是 0OPT 依然是 0CLOCK 也好不到哪去。这不是实现 bug是工作集比物理内存大了一点点时必然发生的抖动。报告里把它单独拿出来讨论比堆十张漂亮曲线有分量。4.3 固定随机种子让对比变成成对比较不同种子生成的是不同的引用串跨种子比较算法毫无意义。正确做法是同一seed、同一hot_ratio下比四种算法这叫成对比较把「引用串本身的难易程度」这个变量消掉了。想在报告里写均值就跑 5 个种子取平均但要注意这几个种子生成的串并不独立同分布——它们只是随机数发生器不同起点方差会被低估。稳妥的写法是给出每档的均值和极差而不是只给一个平均值加一个标准差。4.4 帧数与页面数的关系要先对齐有个细节很容易忘当帧数大于等于虚拟页总数时任何算法的缺页数都等于不同页面数缺失率等于「不同页面数 / 引用串长度」此时四种算法结果完全相同。如果你在pages20的情况下扫到帧数 32表格里四列数字一模一样别以为是代码串了这就是理论值。同理帧数为 1 时四种算法也完全一致因为只有一个位置可换。扫描区间取 2 到pages之间比较有信息量超出这个范围的档位写进报告只会稀释结论。5. 避坑与排查五条踩过的坑每条都能让你重跑一遍实验5.1 现象LRU 的缺页数和 FIFO 一模一样原因命中分支里没有更新元数据。if p in last:之后直接continuelast[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 增到 4FIFO 缺页数反而变多怀疑代码写错原因这是 Belady 异常FIFO 不是栈算法帧数增加时驻留集不保证包含关系。解决用固定反例做回归引用串取1,2,3,4,1,2,5,1,2,3,4,53 帧缺页 9 次4 帧缺页 10 次。把这个用例写进测试文件以后每次改代码都跑一遍。同时验证 LRU 和 OPT 在这串上不会出现该异常这才说明你理解了两类算法的本文还有配套的精品资源点击获取