页面置换算法实验：FIFO、LRU、OPT与Belady异常解析

简介这份资源面向操作系统课程中学习虚拟存储与页面置换的学生围绕实验七的要求提供可运行的模拟程序与实验文档帮助理解不同置换策略的执行过程与性能差异。压缩包共5个文件约31KB包含cpp与h源文件置换算法与数据结构实现、vmrp程序及vmrp.h头文件页面引用串生成与运行支撑、vm可执行文件以及一份doc实验报告便于直接编译运行并对照撰写分析。资源在示例程序基础上补充了增强二次机会等置换算法的模拟支持输入不同内存页面引用串和实存帧数观察置换效果并与LRU、FIFO比较同时改进程序以随机产生引用串动态观测各算法命中率与缺页情况。目前已有472人学习适合作为实验参考与算法对比的现成模板。1. 页面置换为什么多加几个物理块缺页反而更多同一段引用串1 2 3 4 1 2 5 1 2 3 4 5物理块从 3 个加到 4 个FIFO 的缺页次数从 9 次涨到 10 次。这不是代码写错了而是被写进教材几十年的 Belady 异常。页面置换要解决的问题很朴素物理内存装不下所有页缺页时总得踢掉某一页腾出位置。真正值得搞懂的地方在于「踢谁」这个决定的依据只有页表里有限的几位标志不同算法就是在这几位上做不同的解读。把这套解读方式吃透缺页率那条曲线才不会变成玄学这也正是页面置换实验的价值所在——它把 FIFO、LRU、OPT、时钟这些策略压进同一个可运行的骨架里让你亲手把异常复现出来而不只是在纸上背结论。2. 缺页中断与置换决策一次缺页到底走完了哪些步骤很多实验报告只统计「缺页次数」这个数字却跳过了缺页发生到页框被填满之间的完整链路。这条链路决定了后面所有算法的可行边界哪些信息是硬件白送的哪些信息操作系统只能靠猜。先把这条链路走一遍再去看 FIFO 和 LRU 的差别会发现它们的差异其实早在「信息可获得性」这一层就注定了。2.1 触发链路MMU 查表失败之后发生了什么CPU 执行一条访存指令先把虚拟地址送进 MMU。MMU 拆出虚拟页号用页表基址寄存器加上页号去查页表项PTE读有效位。有效位为 1 就直接拼出物理地址整条路径在硬件里完成操作系统完全无感。有效位为 0 的那一刻MMU 抛出一个缺页异常控制权交给内核的缺页处理程序。注意这一步的关键词是「异常」而不是「函数调用」——异常意味着现场被精确保存处理完成后要回到同一条指令重新执行而不是执行下一条。内核拿到出错地址后按顺序做几件事。第一件是合法性检查这个地址是否落在进程已登记的某个虚拟内存区域里不在就是野指针直接给进程发信号。第二件是找页框空闲页框链表非空就直接摘一个为空才真正进入置换流程此时置换算法登场选出牺牲页。第三件是写回牺牲页的脏位为 1 说明被改过必须先落盘否则数据就丢了脏位为 0 说明它和磁盘上的副本一致可以直接丢弃这一次磁盘写就能省下来。第四件是读入新页、更新页表、清空 TLB 里对应的旧表项然后返回。# 缺页处理主干描述性伪代码非真实内核源码 def handle_page_fault(addr, proc): vma find_vma(proc, addr) if vma is None or not vma.permits(addr): raise SIGSEGV # 地址非法直接杀进程 frame free_list.pop() if free_list else pick_victim(proc) # pick_victim 内部才调用置换算法返回的页框此刻仍被旧页占用 if frame.dirty: # 脏页必须回写干净页直接丢弃 write_back(frame) load_page(vma.page_of(addr), frame) # 磁盘读通常阻塞 update_pte(proc, addr, frame) # 有效位置 1填入页框号 tlb_flush(addr) # 让旧的地址翻译失效 return RETRY_INSTRUCTION # 回到出错指令重新执行这段流程里有两个容易被忽略的点。第一pick_victim只在空闲页框耗尽时才会被调用也就是说缺页次数并不等于置换次数实验里如果统计口径混在一起数字对不上是必然的。第二脏页回写让「踢谁」的代价不再对称踢一个干净页近乎零成本踢一个脏页要付一次磁盘写。真实的置换策略里脏位往往被当作权重参与打分这不是优化技巧而是成本结构决定的。2.2 页表里那几位才是决策的全部依据置换算法想要的信息和硬件愿意提供的信息之间有一道鸿沟。理想情况下LRU 需要知道每一页「上一次被访问的时刻」这是一个精确的时间戳但硬件为了省成本只维护一个访问位页被读过或写过就把它置 1具体什么时候置的、置了几次一概不记录。操作系统拿到的只是一个布尔值这就是为什么工程上出现了时钟算法这类近似方案。信息硬件是否直接提供说明有效位 valid是页是否在内存缺页判定依据脏位 dirty是是否被写过决定要不要回写访问位 accessed是只记录「访问过」无时间精度页框号是物理位置精确访问时间戳否需软件模拟开销大全局访问频次否需额外计数器或采样看这张表就能明白为什么 OPT 只能做理论参照它要求知道未来而未来在页表里根本不存在。LRU 要求知道精确的过去而过去被压缩成了一个 bit。FIFO 最省——只看页是什么时候进来的这个信息甚至不用硬件提供操作系统自己在装入时记一笔就行。算法的复杂度差异本质上是它们对信息的要求不同。2.3 引用串从哪来模拟器与被模拟者的分界实验通常给定一个引用串比如7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1然后数缺页。这里有个认知分界必须先划清引用串是「指令访问的虚拟页号序列」它是一个抽象层把段、偏移、指令长度全都抹掉了。真实系统里同一页的连续多次访问在引用串里会表现为连续的重复数字但在硬件里第一次缺页之后后面的访问全是命中连异常都不会产生。因此模拟器的正确语义是按顺序扫描引用串每遇到一个页号就检查它在不在当前页框集合里在就命中不在就缺页并按策略置换。这个模型假设「页框集合」是一个纯逻辑集合忽略了页框分配、预读、页缓存这些真实因素。这不是缺陷而是刻意做的隔离——只有把变量控制住才能观察到 FIFO 在多给一个页框时反而变差这种纯粹由策略本身导致的现象。搞不清这层抽象就容易把模拟结果直接当成真机性能数据那是踩坑的开始。3. 三种经典算法的实现骨架FIFO 队列、LRU 栈与 OPT 的上帝视角把三种算法放在一起写是为了让差异变得可见。它们的代码量都不大几十行就能跑通但每一行的选择背后都对应着一个真实系统的约束。写模拟器最忌讳的是用「能跑出数就行」的态度因为缺页率这个指标对实现细节极度敏感一个初始化顺序写反就能让 LRU 退化成 FIFO。3.1 FIFO一个环形队列就能解释的 Belady 异常FIFO 的实现只需要一个队列缺页时把新页号压入队尾队列满了就弹出队头作为牺牲页。页号在队列里的位置与它被访问的频率完全无关只与它进入的先后有关。这种「无视使用情况」的态度恰好就是 Belady 异常的来源。from collections import deque def fifo(refs, n_frames): frames deque() # 队头是最早进入的页也就是下一个牺牲者 faults 0 for page in refs: if page in frames: continue # 命中时不调整顺序这是 FIFO 与 LRU 的根本区别 faults 1 if len(frames) n_frames: frames.popleft() # 淘汰最早进入的页 frames.append(page) return faults这段代码里最关键的一行是continue命中时什么都不做。LRU 在这里会把该页挪到队尾FIFO 不动。就这一行差异导致 FIFO 会淘汰掉一个刚刚还在被高频访问、只是进来得早的页。用前面那段 12 个引用的串跑一遍3 个页框得到 9 次缺页4 个页框得到 10 次。多给一个页框原本某次命中的访问被推迟成了缺页连锁反应让总数不降反升。这不是算法的「错误」而是「只看年龄不看热度」这个判据在多页框下更容易误伤活跃页的必然结果。3.2 LRU时间戳与栈式实现的性能差在哪LRU 的判据是「最久未被使用」翻译成实现就是两个流派。时间戳流派给每个页框记一个逻辑时钟值每次访问就更新淘汰时线性扫描找最小值时间复杂度 O(n)n 是页框数。栈式流派把页框维护成一个按最近使用排序的链表命中时把该页移到表头淘汰时取表尾移动操作 O(1)但需要哈希表做页号到链表节点的映射。from collections import OrderedDict def lru(refs, n_frames): frames OrderedDict() # 头部是最近使用尾部是最久未使用 faults 0 for page in refs: if page in frames: frames.move_to_end(page) # 命中也要动维护最近使用次序 continue faults 1 if len(frames) n_frames: frames.popitem(lastFalse) # 弹出尾部即最久未使用 frames[page] True return faults两个流派的差异在页框数小的时候几乎看不出来页框数上千时就是数量级差别——扫描 4096 个页框找最小值每次缺页都要走一遍这在真实内核里是不可接受的。所以真实系统用的是时钟算法这种 O(1) 的近似而不是教科书 LRU。另一个常被忽略的细节是move_to_end的位置它必须在命中分支里执行。写在缺页分支里算法就退化成了 FIFO 加一个无效更新缺页率会莫名其妙地和 FIFO 一致。这类错误在实验里太常见了。用同一段引用串跑3 个页框下 LRU 得到 10 次缺页比 FIFO 的 9 次还多。这个结果初看反直觉其实是引用串本身没有明显局部性造成的当访问模式接近循环扫描时LRU 会被反复穿透反而是 FIFO 偶尔撞对。这也说明「LRU 一定比 FIFO 好」是个错误命题好坏取决于访问模式而不是算法的名气。3.3 OPT为什么它只能做上界OPT 的做法是缺页时向后扫描剩余的引用串找出每一页下一次被访问的位置淘汰那个位置最靠后、或者永远不会再被访问的页。它是可证明的最优解因为每一步都淘汰了未来最不需要的页。实现上就是一个带前瞻的循环代价是每次缺页都要扫描剩余串最坏情况 O(剩余长度 × 页框数)。def opt(refs, n_frames): frames [] faults 0 for i, page in enumerate(refs): if page in frames: continue faults 1 if len(frames) n_frames: frames.append(page) continue # 为每个驻留页找它下一次出现的位置找不到就设成无穷远 farthest, victim -1, None for f in frames: try: nxt refs.index(f, i 1) except ValueError: nxt float(inf) if nxt farthest: farthest, victim nxt, f frames[frames.index(victim)] page return faults真机上永远拿不到未来的引用串所以 OPT 的作用不是拿来用而是当标尺。把 LRU 的缺页次数除以 OPT 的缺页次数得到的就是这个访问模式下的「算法效率比」。这个比值在评估一个新策略时非常有用如果新策略只比 LRU 好一点却离 OPT 很远说明还有优化空间如果已经逼近 OPT再投入就没有意义了。用前面那段串跑3 个页框下 OPT 是 7 次LRU 10 次FIFO 9 次。三个数字一摆各自的定位就清楚了。4. 时钟算法与工作集工程里为什么不用「完美 LRU」教科书讲完 LRU 就收尾真实系统却不这么干。原因很实在LRU 要求每次访问都更新数据结构而访存是 CPU 最热的路径一次额外的链表指针改写会直接吃掉性能。硬件的应对办法是把这件事交给 MMU——D 位和 A 位由硬件在地址翻译时顺手置位软件一个周期都不用花。时钟算法就是建立在这个硬件事实之上的。4.1 二次机会把访问位当成一颗后悔药时钟算法的结构是一个环形缓冲区加一个指针。缺页时指针从当前位置开始转遇到访问位为 1 的页就把它清零并跳过相当于给这一页一次「后悔药」遇到访问位为 0 的页就选中它作为牺牲页。最坏情况下指针会转满一整圈把所有访问位清空然后回到起点淘汰它。平均下来近似 O(1)而且完全依赖硬件自动维护的访问位软件不做任何记录。def clock(refs, n_frames): frames [None] * n_frames # 页框槽位 ref_bit [0] * n_frames # 硬件维护的访问位 hand 0 # 时钟指针 faults 0 for page in refs: if page in frames: ref_bit[frames.index(page)] 1 # 命中硬件置访问位 continue faults 1 while True: if frames[hand] is None: # 空槽位直接用 break if ref_bit[hand] 0: # 给过机会了淘汰 break ref_bit[hand] 0 # 第一次遇到给一次机会 hand (hand 1) % n_frames frames[hand] page ref_bit[hand] 1 hand (hand 1) % n_frames return faults指针hand的推进位置是这套实现的核心状态。它不能每次缺页都重置到 0否则就退化成了「按槽位顺序轮转」跟 FIFO 没什么本质区别。环形扫描的意义在于指针会把「最近没被访问过」的页逐渐扫到身边形成一种低成本的时间局部性近似。这也解释了为什么改进版时钟算法多级时钟会用多个访问位构成计数器——单个 bit 只能区分「访问过」和「没访问过」两级 bit 就能粗分出「刚访问过」和「很久没访问」代价是硬件要多一个位。4.2 工作集与抖动缺页率曲线的拐点在哪单个进程的缺页率和分给它的页框数之间不是线性关系。页框非常少的时候缺页率极高进程几乎在不停换页CPU 利用率贴着地板页框逐渐增加缺页率快速下降过了某个点之后曲线变平再加页框收益极小。那个拐点大致对应进程的工作集大小——也就是它在最近一段时间窗口内实际触碰到的不同页的数量。抖动就是页框总量低于所有活跃进程工作集之和时的状态。此时系统把页换出去进程立刻又要用又触发缺页再换回来磁盘队列越来越长CPU 反而空闲。判断抖动不能看单个进程的缺页率要看换页 I/O 的吞吐和 CPU 利用率的组合CPU 利用率低而磁盘繁忙基本就是抖动。处理办法也不是加内存那么简单通常是先降低多道程序度把某些进程整个换出让剩下的进程拿到足够的工作集。4.3 全局置换与局部置换的分岔置换的时候从哪个范围里挑牺牲页这件事在实验里经常被简化掉但它对结果影响很大。局部置换只在当前进程自己的页框里挑进程之间的缺页率互不干扰代价是一个进程即使内存紧张也抢不到别人的页。全局置换从所有进程的页框里挑内存利用率高但一个疯狂分配的进程会把别的进程的页全挤出去导致后者缺页率暴涨这种相互拖累就是常说的「置换污染」。实验里通常只模拟单进程所以这个问题不会暴露。但如果你在模拟器里加上多进程就要面对一个设计选择牺牲页的选取是否应该跨进程。常见的做法是按进程分配固定的页框配额配额内做局部置换配额本身再根据缺页率动态调整。这是把「公平」和「效率」拆成两层来妥协的思路理解了这一层再去看真实系统的页框回收就不会觉得那些参数是拍脑袋定的。5. 避坑与排查页面置换实验里最容易翻车的五处模拟器的代码短但每一步都可能埋雷而且错了之后往往还能跑出「看起来很合理」的数字让人以为做对了。下面这几条是我在实际写过几遍之后攒下的血泪经验每条都按现象、原因、解决三步写。5.1 缺页次数和置换次数被混成一个数现象报告里写的缺页次数和手工按引用串数出来的对不上差得不多但总是差几个。原因页框还没填满的那前 n 次访问确实发生了缺页但没有发生置换因为有空闲页框可用。如果计数器写在「淘汰牺牲页」那个分支里前 n 次就被漏掉了。解决缺页计数写在「判断该页不在页框集合里」之后立刻自增与是否发生淘汰解耦。另外单独记一个置换计数两者相减就是填满页框所消耗的次数这个差值在核对时很有用。5.2 命中时忘记更新 LRU 的使用次序现象LRU 跑出来的缺页率和 FIFO 一模一样改几个引用串还是完全一致。原因move_to_end之类的更新写在了缺页分支里命中分支只有一个continue。这样页框集合内部根本不存在「最近使用」的次序淘汰时拿到的就是进入顺序等价于 FIFO。解决命中分支必须显式更新次序。写完可以加一条断言命中后该页在有序结构里的位置必须是末尾再拿一段有明显局部性的引用串跑LRU 的缺页数应当明显低于 FIFO否则就是没生效。5.3 初始页框状态没做区分把空槽位当成有效页现象前几次访问的缺页数是对的但从第 n1 次开始淘汰出来的页号是None或者 0缺页率略微偏低。原因页框数组用固定长度预分配空缺位置填了 0。如果访存串里恰好有页号 0判定「在不在集合里」时就会误判为命中那一次缺页被吃掉了。解决用None或一个不可能出现的哨兵值表示空槽位判断命中时同时检查非空。这个坑极其隐蔽因为只要引用串里没有 0一切看起来都正常。5.4 引用串生成没控制局部性结论无法复现现象同一份代码两次运行跑出的缺页率差出十几个百分点报告里的分析前后矛盾。原因引用串用纯随机方式生成且没固定种子或者用random.shuffle打乱了本该体现时间局部性的序列。随机串下所有算法的表现都趋于一致看不出任何策略差异。解决固定随机种子并且刻意构造三类串——顺序扫描串、循环串、带明显局部性的串。顺序和循环串用来暴露 FIFO 的异常和 LRU 的穿透局部性串用来体现 LRU 的优势。三类串的结论放在一起看才有说服力。5.5 复现 Belady 异常失败以为结论有问题现象想验证「加页框反而更差」换了七八个引用串都复现不出来开始怀疑结论是不是错的。原因Belady 异常只在特定条件下出现——FIFO 策略、引用串存在特定的重复模式、页框数刚好跨过临界点。大多数随机串都不会触发。解决直接用经典串1 2 3 4 1 2 5 1 2 3 4 53 个页框 9 次、4 个页框 10 次这是可以手工验算的最小例子。先用它把模拟器本身的正确性钉死再去跑其他串。反过来说如果经典串都跑不出 9 和 10那一定是模拟器写错了不用往下查策略。6. 设计取舍什么时候该信缺页率这个数缺页率是这套实验里唯一的显式指标但它是个被高度简化的指标。它假设所有缺页的代价相同而真实系统里一次命中空闲页框的缺页可能只要几微秒一次需要回写脏页再读入新页的缺页可能要几毫秒两者差三个数量级。所以当你在模拟器里看到 LRU 只比 FIFO 少 2 次缺页时正确的判断不是「LRU 略微更好」而是「在这个引用串下两者的差距不足以覆盖 LRU 的实现开销」。算法需要的硬件信息单次缺页开销缺页率3 页框12 引用串OPT未来引用串扫描剩余串最高7LRU精确访问时间戳链表更新较高10FIFO进入顺序队列出队极低9时钟一个访问位环形扫描低介于 FIFO 与 LRU 之间这张表想说明的是选择置换策略从来不是单选缺页率。真实系统选时钟算法不是因为它缺页率最低而是因为它的开销结构和硬件能提供的信息刚好匹配。OPT 那一行的「扫描剩余串」放在真机上意味着每次缺页都要遍历未来的访问序列这需要预知程序行为物理上不成立。验证模拟器是否正确我一直用三个层次的检查。第一层是手工验算最小例子比如 3 个页框跑经典异常串必须得到 9第二层是交叉验证OPT 的缺页数在任何引用串和任何页框数下都不应该大于 LRU 和 FIFO一旦出现就说明前瞻逻辑写错了第三层是边界检查页框数等于引用串中不同页号的数量时所有算法的缺页数都应该等于不同页号数量因为此后再不会发生置换。搞清楚这三点再去跑大引用串、画缺页率随页框数变化的曲线得到的图才有解读价值。常见实现思路是固定引用串、让页框数从 1 递增到 20把四条曲线画在同一张图上观察它们的收敛位置和交叉点——交叉点往往比最终值更有信息量它告诉你从多少个页框开始算法的复杂度就不值得了。从那以后我每次写这类模拟器都会先把最小验算例子和断言写进代码里再动手实现算法而不是先跑通再补测试。因为缺页率这个数字太容易「看起来合理」错了也不会报错只会让你在错误的前提上分析半天。这份实验资源把这些算法放在同一个骨架里刚好适合拿来做这件事——先跑通再逐行改实现、看数字怎么变比读十遍伪代码管用。希望帮到你。本文还有配套的精品资源点击获取