简介这份操作系统实验七配套材料面向正在学习虚拟存储与页面置换算法的本科生及课程实验者围绕页面置换模拟程序的补全、改进与性能对比展开。内容在示例程序基础上补充“增强二次机会”等置换算法的模拟实现并支持输入不同的内存页面引用串和实存帧数观察缺页与置换过程进而与LRU、FIFO算法的效果和性能进行比较。压缩包共5个文件约31KB包含doc实验文档、cpp源程序、h头文件以及vm、vmrp相关文件分别用于实验说明、算法实现与程序组织体量精简便于快速编译运行。已有472人学习适合课程实验复现、算法对照和实验报告撰写改进后的程序还能随机生成页面引用串便于动态观测各置换算法在不同负载下的性能差异为理解页面置换策略提供可操作的分析样本。1. 缺页率不是玄学一次页面置换实验要盯住的三组数字页框只给三个引用串却是一长串。跑完 FIFO 得到缺页 9 次换成 LRU 变 10 次再把页框加到四个FIFO 的缺页次数不降反升成了 10 次。很多人到这一步就开始翻代码怀疑淘汰逻辑写反了其实这是页面置换实验里最值得记录的一幕Belady 异常。这个实验真正要交出来的不是四份算法抄写而是「给定引用串 给定页框数」下的缺页次数、缺页率、置换次数三组数字以及它们随算法和页框数变化的解释。它适合正在做操作系统课程实验、既要代码跑通又要报告能对上参考结果的人也适合想搞清楚 LRU 和 CLOCK 到底差在哪、为什么 CLOCK 会被叫作 FIFO 的近似的人。2. 搭实验骨架引用串、页框表和缺页计数怎么落到代码页面置换实验的代码量其实很小四个算法加起来不到两百行但骨架没搭好后面每加一个算法就要重写一遍主循环。我一般把实验拆成三件固定不动的东西引用串输入、页框表状态、缺页计数与缺页位置序列输出。这三件定下来FIFO、LRU、OPT、CLOCK 只是「选哪个页框淘汰」这一个函数不一样其余全部复用。先把公共类型写出来别用裸的int frame[8]存页号。原因很直接FIFO 需要知道每个页框是什么时候装入的LRU 需要知道最近一次被访问是什么时候CLOCK 需要一个访问位。这些信息如果分散在三个平行数组里改一个算法就要同步改三处很容易出现「数组下标对上了但语义错位」的问题。/* page_replace.h —— 四个算法共用的页框结构 */ #define MAX_REF 256 #define MAX_FRAME 16 #define EMPTY_PAGE (-1) /* 空页框哨兵不要用 0 */ typedef struct { int page; /* 当前装入的页号EMPTY_PAGE 表示空闲 */ int load_time; /* 装入时刻逻辑时钟FIFO 找最老的用它 */ int last_use; /* 最近访问时刻LRU 找最久未用的用它 */ int ref_bit; /* 访问位CLOCK 做二次机会用它 */ } Frame;逻辑时钟用一个自增的t就够了不需要真实时间戳。每发生一次内存访问命中或缺页t加一这样load_time和last_use的大小关系就严格等价于「谁更早」。这里有个容易忽略的点命中时t要不要加要加。LRU 的语义是「最久未被访问」命中本身就是一次访问如果不推进时钟命中页的last_use就无法刷新LRU 会退化成 FIFO。这个细节后面在避坑章还会再提一次。2.1 引用串的两种来源手动给定与按局部性生成实验报告里通常要求两种数据一组手工给定的短串用来人工核对每一步一组随机生成的长串几百到上千次访问用来算稳定的缺页率。短串建议直接用教材上那个能触发 Belady 异常的经典序列长度 12页号 1 到 5它能让 FIFO 在页框数 3 和 4 时分别得到 9 和 10一眼就能验证算法实现是否正确。/* 手工引用串页框 3 时 FIFO 缺页 9 次页框 4 时 10 次 */ int ref_classic[] {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};随机串不要直接调rand() % npage。纯均匀随机会让工作集频繁抖动四个算法的缺页率挤在一起看不出差别报告里全是「LRU 略优于 FIFO」这种没信息量的结论。合格的做法是按局部性模型生成维护一个大小固定的工作集大部分访问落在工作集内小概率跳到工作集外引入新页。这样跑出来的曲线才有区分度。/* 线性同余生成器同一 seed 在任何平台结果一致便于复现和写进报告 */ static unsigned lcg_next(unsigned *s) { *s (*s) * 1103515245u 12345u; return (*s 16) 0x7fffu; } /* * ref : 输出数组 * n : 引用串长度访问次数 * npage : 页号取值 0..npage-1 * ws_size : 工作集大小建议取 2~4 倍页框数 * locality: 落在工作集内的概率0.8~0.9 比较接近真实程序 */ void gen_ref(int *ref, int n, int npage, int ws_size, double locality, unsigned seed) { unsigned s seed; int ws[MAX_FRAME * 4]; int i, k; for (k 0; k ws_size; k) /* 初始化工作集 */ ws[k] (int)(lcg_next(s) % (unsigned)npage); for (i 0; i n; i) { double r (double)(lcg_next(s) % 10000u) / 10000.0; if (r locality) { /* 局部访问 */ ref[i] ws[lcg_next(s) % (unsigned)ws_size]; } else { /* 跳到工作集外替换其中一个槽 */ int slot (int)(lcg_next(s) % (unsigned)ws_size); ws[slot] (int)(lcg_next(s) % (unsigned)npage); ref[i] ws[slot]; } } }参数上我一般这么配n 1000npage 12ws_size 8locality 0.85页框数分别取 3、4、5、6。为什么页号空间要明显大于工作集因为如果npage只比页框数大一点点四个算法的缺页率都会趋近于 1比较就没意义了。为什么不用rand()因为 C 标准并没有规定rand()的具体实现同一份代码在 Linux 上编译和在别的环境里编译srand(1)给出的序列可能不同报告里的数字就对不上了——这一点在需要提交可复现结果的时候是硬伤。2.2 页框表的表示方式决定后面好不好改页框表还有另一种常见写法一个int pages[MAX_FRAME]数组存页号另外用int clock_hand和unsigned ref_bits位图辅助。这种写法在 FIFO 下最省事但换到 LRU 就得再加一个int ages[MAX_FRAME]换到 CLOCK 又得维护位图和指针的一致性。结构体数组虽然多占几十个字节但每个页框的元信息是绑在一起的写第四个算法时几乎不用动前面的代码。初始化一定要用EMPTY_PAGE而不是 0。这是新手最容易翻车的地方页号 0 是合法页号如果页框初始值填 0第一次访问页号 0 时会被判成命中缺页次数就少了一次而你对着参考结果看半天也找不出哪里错了。void init_frames(Frame *f, int nframe) { int i; for (i 0; i nframe; i) { f[i].page EMPTY_PAGE; f[i].load_time -1; f[i].last_use -1; f[i].ref_bit 0; } }2.3 FIFO 与 LRU 的实现差异一个动头一个动尾两个算法的外层循环完全一样遍历引用串、查命中、未命中则选一个页框换出、累加缺页计数。差别只在两处命中时是否更新状态以及未命中时按什么规则挑牺牲页框。/* * 通用骨架algo 决定淘汰策略 * 返回值缺页次数fault_pos 记录每次缺页在引用串中的下标可为 NULL */ int run_fifo(const int *ref, int n, int nframe, int *fault_pos, int *nfault) { Frame f[MAX_FRAME]; int i, j, t 0, faults 0, victim; init_frames(f, nframe); for (i 0; i n; i) { int cur ref[i], hit 0; for (j 0; j nframe; j) { /* 查命中 */ if (f[j].page cur) { hit 1; break; } } if (hit) continue; /* FIFO 命中不改 load_time */ victim -1; for (j 0; j nframe; j) { /* 优先用空页框 */ if (f[j].page EMPTY_PAGE) { victim j; break; } } if (victim -1) { /* 满了淘汰装入最早的 */ victim 0; for (j 1; j nframe; j) if (f[j].load_time f[victim].load_time) victim j; } f[victim].page cur; f[victim].load_time t; faults; if (fault_pos) fault_pos[faults - 1] i; } *nfault faults; return faults; }LRU 只改三行命中时刷新last_use淘汰时比last_use而不是load_time装入时也写last_use。这三行改动看着小但它决定了两个算法在「循环访问大于页框数的工作集」时的表现差异FIFO 会把马上要用的页换出去因为它老LRU 不会。int run_lru(const int *ref, int n, int nframe, int *nfault) { Frame f[MAX_FRAME]; int i, j, t 0, faults 0, victim; init_frames(f, nframe); for (i 0; i n; i) { int cur ref[i], hit -1; for (j 0; j nframe; j) if (f[j].page cur) { hit j; break; } if (hit 0) { /* 关键差异一命中也要刷新 */ f[hit].last_use t; continue; } victim -1; for (j 0; j nframe; j) if (f[j].page EMPTY_PAGE) { victim j; break; } if (victim -1) { /* 关键差异二比 last_use */ victim 0; for (j 1; j nframe; j) if (f[j].last_use f[victim].last_use) victim j; } f[victim].page cur; f[victim].last_use t; faults; } *nfault faults; return faults; }参数方面只有两个需要调的nframe页框数1 到MAX_FRAME和n访问次数。注意当nframe大于引用串中不同页号的个数时所有算法都不会发生置换缺页次数恒等于不同页号个数这时候比较缺页率毫无意义。写报告前先确认nframe 不同页号个数否则结果表里全是相同的数字。3. 把 OPT 和 CLOCK 补上从最理想基准到工程近似FIFO 和 LRU 是「看起来合理」的两个极端OPT 是无法实现的理论下界CLOCK 是工程上真在用的近似。四个放在一起跑缺页率才有参照系LRU 离 OPT 有多远CLOCK 离 LRU 有多远这两个差距才是实验报告里该讨论的东西而不是干巴巴地列四个数字。3.1 OPT 的「看未来」其实是一次反向扫描OPT 的规则是淘汰「未来最长时间不会被访问」的页。直接实现就是每次置换时对页框里每个页号都在引用串当前位置之后找它下一次出现的下标取下标最大的那个换出去如果某个页号以后再也不出现就给它一个n无穷远优先淘汰它。/* 返回 page 在 ref[pos..n-1] 中第一次出现的下标找不到返回 n */ static int next_use(const int *ref, int n, int pos, int page) { int k; for (k pos; k n; k) if (ref[k] page) return k; return n; /* n 表示再也不用了优先级最高 */ } int run_opt(const int *ref, int n, int nframe, int *nfault) { Frame f[MAX_FRAME]; int i, j, faults 0, victim; init_frames(f, nframe); for (i 0; i n; i) { int cur ref[i], hit 0; for (j 0; j nframe; j) if (f[j].page cur) { hit 1; break; } if (hit) continue; victim -1; for (j 0; j nframe; j) if (f[j].page EMPTY_PAGE) { victim j; break; } if (victim -1) { int far -1; victim 0; for (j 0; j nframe; j) { int k next_use(ref, n, i 1, f[j].page); if (k far) { far k; victim j; } /* 严格大于同远取先遇到的 */ } } f[victim].page cur; faults; } *nfault faults; return faults; }next_use从i 1开始扫不能从i开始。当前位置的页就是cur它不在页框里否则就是命中了从i开始虽然不影响结果但会让「自己和自己比」的语义变得可疑。另外far 用严格大于遇到两个页号未来都不再用都返回n时会淘汰下标较小的那个页框这是确定性的方便复现。时间复杂度是 O(n × nframe × n)引用串 1000 条、页框 6 个的时候大概是六百万次比较毫秒级完全不用优化。真要做长串十万级可以预处理一张「每个页号下次出现位置」的链表把单次查找降到 O(1)但课程实验没必要。3.2 CLOCK 的指针回绕与访问位清零顺序CLOCK 用一个环形指针扫页框指针指向的页框访问位是 1 就清零并前进是 0 就选中它换出。命中时把对应页框的访问位置 1。它不需要像 LRU 那样维护精确的时间序硬件上只要一个引用位就能近似这就是它在真实系统里活下来的原因。int run_clock(const int *ref, int n, int nframe, int *nfault) { Frame f[MAX_FRAME]; int i, j, hand 0, faults 0, victim; init_frames(f, nframe); for (i 0; i n; i) { int cur ref[i], hit 0; for (j 0; j nframe; j) if (f[j].page cur) { hit 1; f[j].ref_bit 1; break; } if (hit) continue; victim -1; for (j 0; j nframe; j) if (f[j].page EMPTY_PAGE) { victim j; break; } if (victim -1) { while (1) { /* 最多绕两圈必然停下 */ if (f[hand].ref_bit 0) { victim hand; break; } f[hand].ref_bit 0; /* 给第二次机会 */ hand (hand 1) % nframe; } } f[victim].page cur; f[victim].ref_bit 1; /* 新装入的页访问位置 1 */ hand (victim 1) % nframe; /* 无论空框还是换出指针都后移 */ faults; } *nfault faults; return faults; }两个顺序问题必须写对。第一hand (victim 1) % nframe要在赋值之后、且对「填空白页框」的情况也要执行否则前几次填框时指针不动等框填满后指针还停在 0扫描起点就不对了。第二ref_bit的清零只能发生在扫描过程中不能在命中的时候顺手清——命中意味着这个页刚被用过它的访问位应该是 1 而不是 0。% nframe取模保证了回绕但代价是每次都要做除法。真要抠性能可以写成if (hand nframe) hand 0;课程实验里无所谓。3.3 同一份数据跑四组算法对比表与 Belady 异常复现把四个函数塞进同一个main用经典引用串跑页框数 3 和 4 两组输出如下。这四个数字建议手工验算一遍再写报告因为后面所有结论都建立在这张表上。算法页框数 3 缺页次数页框数 4 缺页次数是否出现 Belady 异常OPT75否LRU108否FIFO910是CLOCK910是int main(void) { int ref[] {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}; int n (int)(sizeof(ref) / sizeof(ref[0])); int nf, nframe; for (nframe 3; nframe 4; nframe) { run_fifo (ref, n, nframe, NULL, nf); printf(FIFO frames%d faults%2d\n, nframe, nf); run_lru (ref, n, nframe, nf); printf(LRU frames%d faults%2d\n, nframe, nf); run_opt (ref, n, nframe, nf); printf(OPT frames%d faults%2d\n, nframe, nf); run_clock(ref, n, nframe, nf); printf(CLOCK frames%d faults%2d\n, nframe, nf); } return 0; }编译运行gcc -O2 -Wall -Wextra -o page_replace page_replace.c ./page_replaceFIFO frames3 faults 9 LRU frames3 faults10 OPT frames3 faults 7 CLOCK frames3 faults 9 FIFO frames4 faults10 LRU frames4 faults 8 OPT frames4 faults 5 CLOCK frames4 faults10这张表最值得写进报告的两句话是LRU 和 OPT 是栈式算法stack algorithm页框数增加时缺页集合只会缩小所以永远不会出现 Belady 异常FIFO 和 CLOCK 不是栈式算法页框数增加可能打乱淘汰顺序反而把即将访问的页提前换出去。CLOCK 出现和 FIFO 完全相同的 9 和 10不是巧合它就是 FIFO 加了访问位的近似版本。4. 页面置换实验排查五个让缺页率对不上的细节这段是血泪经验。代码跑通了不等于结果对下面五条是「编译无警告、程序不崩溃、但数字就是和参考结果差一点」的典型来源按出现频率从高到低排。4.1 缺页次数总比参考值少一次页框初始化用了 0现象手工验算经典串页框数 3 时 FIFO 应该缺页 9 次程序输出 8 次而且少的正好是引用串第一次出现页号 0 的那一次。原因init_frames里把page初始化成了 0。页号 0 是合法页号程序在查命中时发现页框里有 0直接判成命中第一次访问就没计入缺页。或者反过来把faults的初值写成 1 来「补」这一次结果引用串首元素不是新页时又多算了一次。解决空页框必须用不可能的哨兵值。#define EMPTY_PAGE (-1)页号从非负数开始取。同时在查命中之前不要做任何「页框里有 0 就算空」的判断。改完重新跑经典串FIFO 页框 3 应该稳定出 9。4.2 页框数加上去缺页反而更多先确认是不是 Belady现象页框从 3 加到 4FIFO 缺页次数从 9 变成 10于是开始怀疑淘汰逻辑写反、load_time没递增、或者页框数组越界。原因这不是 bug是 FIFO 的固有性质。经典串 1 2 3 4 1 2 5 1 2 3 4 5 在页框 4 时第一次缺页发生在访问 5 的位置而页框 3 时由于前面的替换顺序不同恰好把 5 要用的替换位置错开了。解决验证两个判据。一是这类异常只能出现在 FIFO 和 CLOCK 上LRU 和 OPT 不会出现二是换一组随机串比如gen_ref生成 1000 条跑页框 3 到 8画一条缺页次数曲线FIFO 的曲线应该是不单调的LRU 和 OPT 必须单调不增。如果 LRU 也出现上升那才是真 bug多半是命中时忘了刷新last_use。4.3 同一份引用串跑两次结果不一样全局状态没清现象main里连着调用run_clock两次第二次比第一次少缺页或者把run_lru的调用顺序换一下结果就变了。原因hand指针、逻辑时钟t、faults计数器被写成了static或者文件作用域的全局变量。第一次调用结束后hand停在中间某个位置第二次调用从那里接着扫起点就不对了。解决所有算法状态要么是函数内的局部变量要么在函数入口显式重置。Frame f[MAX_FRAME]放在函数内、每次调用重新init_frames这是最省事的写法。页框数 16、引用串 256 的情况下这个数组也就一百多字节栈上完全放得下。4.4 CLOCK 的结果和 FIFO 一模一样访问位永远是 0现象跑出来 CLOCK 和 FIFO 的缺页序列完全相同一个字节都不差。原因命中时忘了把f[hit].ref_bit 1或者置换循环里把ref_bit 0写在了判断前面导致每次扫描看到的都是 0第一次就选中行为退化成了纯 FIFO。这个 bug 很隐蔽因为结果「看起来合理」——CLOCK 本来就该接近 FIFO。解决加一行调试输出打印每次置换时被选中页框的ref_bit正常情况下应该能看到「部分页框被跳过并清零」的记录。如果每次都是第一个被扫到的页框被选中那访问位就没生效。另外一个判据是在工作集明显小于页框数的引用串上CLOCK 的缺页次数应该明显低于 FIFO如果低于不了同样是这个问题。4.5 报告里的「缺页次数」和「置换次数」混着用现象页框数 3、引用串长度 12缺页 9 次报告里写「发生 9 次置换」被追问「前 3 次缺页时页框是空的没有页可换怎么会有 9 次置换」。原因缺页次数 冷启动缺页页框尚未填满时的缺页 置换缺页页框已满、需要换出时的缺页。这两个量在页框数大于 1 时一定不相等。解决在结构里同时维护faults和replacements只有走到「页框已满、选中牺牲页」的分支才给replacements加一。缺页率用faults / n置换率用replacements / n。我的习惯是把victim究竟来自「空页框」还是「淘汰」这件事显式打日志一眼就能看出两个计数该不该加。5. 验证结果的可信度状态快照、对拍脚本与一条硬习惯四个算法的结果表填完其实还不能直接写报告因为你没有任何独立证据证明这张表是对的。数字好看不代表算对尤其是 OPT 这种写起来容易边界差一的算法。我的做法是加两层验证。5.1 每一步打一行状态快照人工核对前 10 步在通用骨架的循环体末尾加一行打印把当前访问的页号、是否命中、页框内容、牺牲页框一起输出。前 10 步手工验算后面交给对拍。/* 调试开关-DDUMP 编译时才输出正式跑性能不受影响 */ #ifdef DUMP static void dump_step(int i, int cur, int hit, const Frame *f, int nframe, int victim) { int k; printf([%02d] page%d %s victim%d |, i, cur, hit ? HIT : FAULT, victim); for (k 0; k nframe; k) { if (f[k].page EMPTY_PAGE) printf( [ -]); else printf( [%2d], f[k].page); } printf(\n); } #endif编译命令加-DDUMPgcc -O0 -g -DDUMP -Wall -o page_replace_dbg page_replace.c前 10 步的输出应该能和纸笔验算逐行对上。对不上的第一个分歧点就是 bug 所在。这个方法比断点调试快因为它不需要你去猜在哪一行下断点。5.2 用独立实现做对拍别自己验证自己同一个算法写两遍、然后比对很容易两个版本犯同一个错。有效的对拍是换一种完全不同的实现思路。比如 OPT主实现是「每次置换时向后扫描找下次使用位置」对拍版本可以用 Python 写一个「反向遍历引用串预先算出每个位置每个页号的下次出现」的预处理版本两边的缺页次数必须完全相等。# opt_ref.py —— OPT 的独立实现用来对拍 C 版本 def opt_faults(ref, nframe): frames, faults [-1] * nframe, 0 for i, page in enumerate(ref): if page in frames: continue if -1 in frames: frames[frames.index(-1)] page else: # 计算每个页框内页号的下次使用位置最远的换出 nxt [] for p in frames: try: nxt.append(ref.index(p, i 1)) except ValueError: nxt.append(len(ref) 1) # 不再使用 frames[nxt.index(max(nxt))] page faults 1 return faults把 C 版本输出的缺页次数和这段 Python 的结果贴在一起比一致才算过。LRU 也可以这么对拍换成一个「用有序字典维护访问顺序」的版本即可。5.3 我自己的强制流程从那以后我每次做这类实验都强制走一遍固定顺序先拿经典 12 条串跑 FIFO 页框 3必须出 9再跑页框 4必须出 10这一步同时验证了 FIFO 和 Belady然后用 LRU 跑同一组必须是 10 和 8这一步验证命中刷新最后 OPT 出 7 和 5这一步验证反向查找的边界。四组数字全对上才允许自己用随机长串去算报告里的缺页率曲线。少了这一步后面所有结论都建在流沙上。这套流程不复杂但它把「程序能跑」和「结果可信」这两件事分开了。页面置换实验真正练的不是背四个算法的规则而是知道每个数字为什么是这个值以及当它不对的时候该先看哪一行。希望帮到你。本文还有配套的精品资源点击获取