简介操作系统实验七页面置换实验资源包面向计算机专业操作系统课程学习者针对页面置换算法模拟与性能对比这一核心实验需求。压缩包内共五个文件包含实验报告文档、源代码、头文件及可执行文件等整体约31KB结构精简既可直接运行可执行程序查看效果也能打开源码研读算法逻辑便于二次修改与扩展。已有四百七十二人学习。资源在示例实验程序基础上补充了增强二次机会置换算法的模拟同时支持手动输入内存页面引用串和实存帧数也可随机产生引用串从而动态观测缺页情况及置换次数并与LRU、FIFO算法在同条件下进行对照分析。通过实际运行与参数调整学习者能够直观理解各置换算法的淘汰规则、性能差异及适用场景并获得实验报告撰写与算法代码实现的可参考范例有效提升操作系统实验环节的完成质量与学习效率。1. 页面置换实验在问什么缺页那一刻谁该被请出内存页面置换实验大概是操作系统课程里最容易被低估的实验代码量不大、逻辑不绕但如果你只是把 FIFO 和 LRU 的函数抄下来、跑通样例就收工等于亲手放掉了这个实验最有价值的部分。它真正在问的问题是当物理内存装满、新页面又必须调入时操作系统靠什么规则决定牺牲谁。这个决策直接决定缺页率高低也就决定了进程实际能用到多少内存带宽。模拟器和真实内核在这件事上的逻辑完全一致一条页面引用串、若干页框、三四种替换算法就能把缺页率曲线、Belady 异常和局部性原理全部摊在桌面上。这个实验适合三类人正在做课程实验的学生、准备面试想讲清楚 LRU 和 Clock 差别的人、以及写内存敏感型应用的嵌入式开发者。花一个晚上把四个算法写齐、扫描页框数画曲线你对虚拟内存的理解会比背十遍课本都扎实。2. 动手前先定三个实验参数参考串、页框数和统计口径很多同学拿到实验 7 的第一反应是上网找现成代码这可以理解但页面置换模拟器的代码量通常不超过 200 行真正决定报告质量的是你输入的参数和统计口径。参数一旦定错算法写得再对报告也没法自圆其说。我一般会把实验拆成三个可控变量参考串怎么来、页框数扫多大范围、缺页相关指标怎么算。这三个问题想清楚再写代码后面基本不会返工。2.1 参考串不是随便一个数组随机生成和局部性生成差在哪参考串是实验的唯一输入它的质量决定了结果有没有说服力。常见的来源有三种教科书固定串、均匀随机串、局部性模型串。教科书串能对照标准答案适合验证代码正确性均匀随机串模拟的是页面访问毫无规律的情况命中率整体偏低算法差异容易被噪声淹没局部性模型串模拟了进程在代码段、数据段之间来回切换的行为最接近真实负载。我建议代码正确性用教科书串验证正式实验用局部性模型串。#include stdio.h #include stdlib.h #define MAX_REF 512 #define MAX_FRAME 16 /* 均匀随机参考串max_page 控制页面总数seed 固定保证可复现 */ void gen_random_ref(int ref[], int n, int max_page, int seed) { srand(seed); for (int i 0; i n; i) { ref[i] rand() % max_page; } } /* 局部性模型参考串70% 概率在当前页附近游走30% 概率跳远 */ void gen_locality_ref(int ref[], int n, int max_page, int seed) { srand(seed); int cur 0; for (int i 0; i n; i) { if (rand() % 100 70) { cur (cur rand() % 5 - 2 max_page) % max_page; } else { cur rand() % max_page; } ref[i] cur; } }这两个生成器的差异就是局部性原理的体现rand() % 5 - 2让下一个页面大概率落在当前页前后两个页面内模拟循环代码反复访问同一小段地址空间30% 的跳远模拟函数调用和上下文切换。如果不固定seed两次运行结果不同报告数据完全没法复现这是后面避坑章的第一个大坑。max_page建议取 20 到 32页面总数太少会把算法差异抹平太多又看不出页框数增长带来的曲线变化。2.2 页框数从 1 扫到最大单点对比看不出算法差异只找一个页框数做对比那不叫实验叫跑样例。页面置换算法对比的标准做法是把页框数从 1 逐步扫到参考串中不同页面的总数 N每个页框数下算出四个算法的缺页次数最后得到一组曲线。页框数等于 1 时无论哪个算法每次引用都缺页缺页次数等于参考串长度页框数大于等于 N 时所有页面能常驻内存每个页面只在第一次出现时缺页一次四个算法的结果完全相同。中间这段区间才是算法分胜负的地方尤其是当页框数落在工作集大小附近时FIFO 和 LRU 的差距会被拉得最大。把这一段曲线写进报告比单独贴一个函数的输出有说服力得多。2.3 统计口径统一缺页次数、缺页率、置换次数别混着用实验数据里有三个概念长得像但含义完全不同混用是报告翻车的高发点。缺页次数是引用过程中页面不在内存的次数是最主要的输出指标缺页率是缺页次数除以引用总次数页框数为 1 时缺页率恰好 100%置换次数只统计内存已满时发生的缺页。注意置换次数恒小于等于缺页次数因为页框填满之前每次缺页都只是装入不涉及淘汰。指标计算方式典型误区缺页次数页面不在内存时计数加一把命中也算进去缺页率缺页次数 ÷ 引用总次数分子分母颠倒或乘 100 后超过 100%置换次数仅在内存满时发生的缺页把装入阶段的缺页也算成置换统计时建议在替换分支里单独维护一个置换计数器而不是事后从缺页次数里反推。很多教材给出的 FIFO、LRU 缺页次数是包含初始装入阶段的所以你的缺页次数应该和教材一致但置换次数要小一些这个细节写进报告能体现你真的理解替换和装入的区别。3. 先用 C 把 FIFO 和 OPT 写出来逻辑最直白的两把尺子代码实现顺序建议从简单的来先写 FIFO 热身再写 OPT 理解什么是理论最优之后写 LRU 和 Clock 才有对比的基准。只要跑通 FIFO 和 OPT主程序框架就算立住了后面两个算法只是往框架里填函数。3.1 最小模拟框架参考串、页框数组和统一函数签名所有替换算法共用同一个函数签名返回缺页次数这样主程序可以用函数指针数组统一调用后面加算法只需要加一行。#define MAX_FRAME 16 typedef int (*replace_func)(int ref[], int n, int frame_count); int fifo(int ref[], int n, int frame_count); int opt(int ref[], int n, int frame_count); int lru(int ref[], int n, int frame_count); int clock_algo(int ref[], int n, int frame_count); int main(void) { /* 教科书经典串验证代码正确性用 */ int ref[] {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1}; int n sizeof(ref) / sizeof(ref[0]); replace_func algos[] {fifo, opt, lru, clock_algo}; const char *names[] {FIFO, OPT, LRU, Clock}; printf(页框数 FIFO OPT LRU Clock\n); for (int fc 1; fc 8; fc) { printf(%3d , fc); for (int a 0; a 4; a) { printf(%4d , algos[a](ref, n, fc)); } printf(\n); } return 0; }页框数扫到 8 是因为这条经典串里不同的页面只有 6 个0、1、2、3、4、78 已经覆盖了「页框数大于等于不同页面数」的边界场景。如果换成局部性生成串扫描范围要按max_page来定。typedef那一行把函数指针封装成replace_func类型让四个算法保持完全一致的输入输出主程序才能用循环统一调用。3.2 FIFO环形队列头指针就是下一刀FIFO 是所有算法里对数据结构要求最低的一个数组加一个头指针就能实现。核心思想是「先来先走」进入内存最早的页面在缺页时第一个被淘汰完全不看这个页面最近被访问了多少次。int fifo(int ref[], int n, int frame_count) { int frames[MAX_FRAME]; int head 0; /* 下一次被替换的槽位 */ int used 0; /* 当前已占用的页框数 */ int faults 0; for (int i 0; i n; i) { int page ref[i]; int hit 0; for (int j 0; j used; j) { if (frames[j] page) { hit 1; break; } } if (!hit) { faults; if (used frame_count) { frames[used] page; /* 有空框直接装入 */ } else { frames[head] page; /* 淘汰最老页面 */ head (head 1) % frame_count; } } } return faults; }这里frames数组本身模拟页框head指向的槽位就是下一个牺牲者。命中时什么都不做未命中且有空框时顺序填入used自增满框时直接覆盖head指向的位置然后head环形前移。注意head不是淘汰次数它只是环形队列的写指针每次替换移动一位转一圈又回到起点正好实现先进先出。这个实现的查找复杂度是 O(frame_count)对几百条参考串完全够用不需要拿哈希表优化。3.3 OPT向后扫描未来参考串替罪羊一目了然OPT 是理论上的最优算法淘汰「未来最长时间不会被使用」的页面。它需要预知整个参考串真实系统做不到但模拟器里可以由代码直接实现作为其他算法的性能下界。int opt(int ref[], int n, int frame_count) { int frames[MAX_FRAME]; int used 0; int faults 0; for (int i 0; i n; i) { int page ref[i]; int hit 0; for (int j 0; j used; j) { if (frames[j] page) { hit 1; break; } } if (!hit) { faults; if (used frame_count) { frames[used] page; } else { int victim 0; int farthest -1; for (int j 0; j used; j) { int next_use n; /* 默认以后再也不出现 */ for (int k i 1; k n; k) { if (ref[k] frames[j]) { next_use k; break; } } if (next_use farthest) { farthest next_use; victim j; } } frames[victim] page; } } } return faults; }关键在next_use初始化为n这一行它表示「从这个位置往后扫描整个参考串都找不到这个页面」也就是未来不会再被使用。farthest求的是最大值所以「再也不用的页」天然排在最前面会被优先淘汰。这里的时间复杂度是 O(frame_count × 剩余串长度)参考串一长就会变慢所以 OPT 只适合做对照实验不适合跑大规模随机串。4. LRU 和 Clock从理论标尺到能落地的近似OPT 是理论下界但没法落地真实系统需要的是不需要未来知识、成本可控的算法。LRU 是 OPT 最直接的近似——用「最近的过去」推测「最近的未来」而 Clock 是 LRU 的工程简化用一个访问位模拟访问的远近程度。这两层递进关系正是实验报告想让你看到的。4.1 LRU 时间戳实现每次命中都更新年龄LRU 淘汰最久没有被访问的页面。最简单的实现是时间戳法每个页框记录最近一次被引用的串下标淘汰时找下标最小的那个。int lru(int ref[], int n, int frame_count) { int frames[MAX_FRAME]; int last[MAX_FRAME]; /* 每个页框内页面的最近访问下标 */ int used 0; int faults 0; for (int i 0; i n; i) { int page ref[i]; int pos -1; for (int j 0; j used; j) { if (frames[j] page) { pos j; last[j] i; /* 命中必须更新年龄 */ break; } } if (pos -1) { faults; if (used frame_count) { frames[used] page; last[used] i; used; } else { int victim 0; for (int j 1; j used; j) { if (last[j] last[victim]) victim j; } frames[victim] page; last[victim] i; } } } return faults; }最容易错的一行是last[j] i很多初版实现只在缺页时更新时间戳命中时不更新结果 LRU 变成了「按进入顺序淘汰」退化成了 FIFO。时间戳用引用串下标i就够它天然单调递增不需要调用time()也不会有两个页面拿到相同时间戳的边界问题。淘汰时线性扫描last数组找最小值复杂度 O(frame_count)实验规模下够用。4.2 Clock 第二次机会扫描指针和访问位的配合Clock 算法也叫第二次机会算法每个页框维护一个访问位命中时置 1缺页时从指针位置开始扫描遇到访问位为 1 的页面就清零并把指针推进一步相当于给它第二次机会遇到访问位为 0 的页面就淘汰。int clock_algo(int ref[], int n, int frame_count) { int frames[MAX_FRAME]; int access[MAX_FRAME]; /* 访问位 */ int used 0; int hand 0; /* 时钟指针 */ int faults 0; for (int i 0; i n; i) { int page ref[i]; int pos -1; for (int j 0; j used; j) { if (frames[j] page) { pos j; access[j] 1; /* 命中置访问位 */ break; } } if (pos -1) { faults; if (used frame_count) { frames[used] page; access[used] 1; used; } else { while (access[hand] 1) { access[hand] 0; /* 清零给第二次机会 */ hand (hand 1) % frame_count; } frames[hand] page; access[hand] 1; hand (hand 1) % frame_count; } } } return faults; }hand指针的推进方向是整个实现最容易写错的地方。每次淘汰完成后hand要落在被替换槽位的下一个位置这样刚换入的新页不会被紧接着的扫描再次检查。如果hand留在原位置新页的访问位可能立刻被清零Clock 就退化成 FIFO 了。访问位的语义是「这个页面从上次扫描到现在有没有被访问过」所以命中时置 1、扫描时清零、淘汰时找 0三者缺一不可。4.3 三页框运行结果对比用经典串校验你的四个函数拿 2.3 节提到的教科书串页框数固定为 3四个算法的缺页次数如下表。这个结果可以作为你代码正确性的校验基准。算法缺页次数特点FIFO15实现最简单可能触发 Belady 异常OPT9理论最优需要未来知识LRU12接近 OPT无未来依赖Clock13LRU 的工程近似成本低如果跑出来的 LRU 不是 12最常见的两个原因是命中时没更新时间戳或者淘汰时把「最久未使用」选成了「最久进入」。如果 Clock 跑出来不是 13先检查hand指针在替换后是否前移了一位。这四个数字对不上教材答案时不要急着怀疑算法回到代码里逐行对照上面三节的逻辑说明。5. 页面置换实验避坑指南五个让调试翻车的具体现场这一章是血泪经验合集。我见过太多同学在同一个地方卡两三小时最后发现不是算法不会写而是统计、种子、状态同步这类细节问题。每一条都按「现象 → 原因 → 解决」写你按顺序排查即可。5.1 缺页率算出来超过 100%分子分母用反了现象报告里写着缺页率 120%或者缺页次数比引用总次数还大评审老师一眼看出数据有问题。原因统计口径混了。有人用「缺页次数 ÷ 命中次数」当缺页率有人把置换次数和缺页次数加在一起还有人把每次扫描中页面存在但访问位为 0 的情况也计了一次缺页。解决严格使用 缺页次数 ÷ 引用总次数并且加一个运行时断言缺页次数 ≤ 引用总次数、置换次数 ≤ 缺页次数。断言触发就说明替换分支的进入条件写错了——替换分支只有在「未命中且 page_count_full」时才能进入。5.2 换掉一个页面却没有清掉对应的状态位现象用页表项数组PTE而不是单纯的页框数组实现时淘汰页面后旧的 valid 位没有清零后续引用同一页面时被误判为命中缺页次数系统性偏小。原因替换操作只更新了页框数组没有同步 PTE 里的 valid 位、访问位和修改位。真实内核里淘汰一个页需要同时维护页表项和页框管理结构模拟器里也要做到这一点。解决把「淘汰」封装成一个独立函数统一做三件事清旧页的 valid 位、写入新页的页框号、置新页的 valid 和访问位。四个算法全部调用这个函数从根上杜绝漏清。5.3 同一份代码两次运行结果不同随机参考串没有固定种子现象代码没改前后两次运行的缺页率对不上两个同学用相同的参数和算法输出的表格不一样。原因参考串用rand()生成但没有在生成前固定srand()种子。默认情况下每次运行种子不同参考串不同结果自然不同。解决在生成参考串的代码前调用srand(固定常数)比如srand(20240)。把参考串本身也打印出来存在报告附件里这样别人可以拿着你的原始数据重新验证。可复现是实验报告的基本要求不可复现的实验等于没做。5.4 FIFO 缺页率随页框数增大反而上升这不是 bug是 Belady 异常现象页框数从 3 增加到 4FIFO 的缺页次数反而从 9 变成 10第一反应是代码写错了开始逐行 Debug。原因这是经典的 Belady 异常只有 FIFO 这类的非栈式算法才会出现。所谓栈式算法是指「页框数增加时驻留页面集合是旧集合的超集」OPT 和 LRU 满足这个性质FIFO 不满足所以偶尔会出现更多内存反而更差的怪象。解决用经典串1,2,3,4,1,2,5,1,2,3,4,5验证FIFO 在 3 页框时缺页 9 次4 页框时缺页 10 次。如果你的代码能稳定复现这个结果说明实现正确并且你捡到了一个绝佳的报告素材——把这条非单调曲线单独画出来结合理论解释为什么 FIFO 会违反直觉。5.5 页框数大于等于不同页面数时算法全等先做这个边界检查现象页框数从 6 扫到 8四个算法的缺页次数完全一样怀疑主程序的循环变量或者函数指针数组有问题。原因参考串里不同的页面一共就 6 个6 个页框已经能把它们全部常驻之后的引用全部命中。页框数继续增加只是浪费内存结果当然不变。解决实验开始时先数一下参考串里不同的页面数 N扫描范围定为 1 到 N 就够。每到页框数等于 N 时所有算法的缺页次数都应该等于 N也就是每个页面恰好缺页一次。如果这个边界值对不上说明某个算法的命中判定或者淘汰逻辑有 bug这是最有效的 sanity check。6. 让数据自己说话缺页率曲线、Belady 复现和可复现存档四个算法都跑通之后实验才做了一半。剩下的一半是把数据变成能说服人的结果并且让这套代码能继续用来做更深入的分析。我一般会再补三件事成本不高但收益很大。第一件事把页框数扫描的结果导出成结构化的数据文件而不是停留在控制台打印。每一行输出页框数、四个算法的缺页次数和缺页率存成 CSV。之后用任意脚本画图横轴是页框数纵轴是缺页率四条曲线一条图报告里直接放这张图。曲线的形状比任何文字都有说服力页框数小的时候四条线挤在一起中间区域散开尾部又收拢到同一水平线这张图本身就是对局部性和工作集模型最好的注解。第二件事显式验证 Belady 异常。把这个测试函数放在主程序里输出固定格式的结果void belady_demo(void) { int ref[] {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}; int n sizeof(ref) / sizeof(ref[0]); printf(FIFO: 3 框%d 缺页, 4 框%d 缺页\n, fifo(ref, n, 3), fifo(ref, n, 4)); /* 期望输出 9 和 103 框反而更少即出现 Belady 异常 */ }这段代码把理论课上的反直觉结论变成了一次可复现的实测。报告里写「FIFO 不是栈式算法所以可能发生 Belady 异常」是套话配上你自己的输出结果就是实验证据。第三件事测量算法真实耗时。参考串加长到十万条用clock()测每个算法总耗时你会发现 OPT 慢得离谱因为它的内层循环要反复扫描未来串而 FIFO 和 Clock 都是线性扫描差距不大。做测量时记得关掉 printf、开编译器优化-O2否则打印开销会淹没算法本身的差异。这个数据放进报告能说明「LRU 效果好但硬件实现成本高所以真实系统常用 Clock」这句话不是空谈。我做这类实验的习惯是先用教科书串加三个已知答案验证正确性再用固定种子跑全量扫描出曲线最后把参考串、种子、原始输出一起存档。不要小看存档这个动作——两周后你回看代码如果没有原始数据你根本说不清当时那张表是怎么跑出来的。实验数据可复现是工程师和只交作业的人之间的分界线。希望帮到你。本文还有配套的精品资源点击获取