企业官网建设流程全解析

简介：这份操作系统实验七配套材料面向正在学习虚拟存储与页面置换算法的本科生及课程实验者，围绕页面置换模拟程序的补全、改进与性能对比展开。内容在示例程序基础上补充“增强二次机会”等置换算法的模拟实现，并支持输入不同的内存页面引用串和实存帧数，观察缺页与置换过程，进而与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 = 1000，npage = 12，ws_size = 8，locality = 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 两组，输出如下。这四个数字建议手工验算一遍再写报告，因为后面所有结论都建立在这张表上。

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_replace

FIFO frames=3 faults= 9 LRU frames=3 faults=10 OPT frames=3 faults= 7 CLOCK frames=3 faults= 9 FIFO frames=4 faults=10 LRU frames=4 faults= 8 OPT frames=4 faults= 5 CLOCK frames=4 faults=10

这张表最值得写进报告的两句话是：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 加到 4，FIFO 缺页次数从 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

编译命令加-DDUMP：

gcc -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，这一步验证反向查找的边界。四组数字全对上，才允许自己用随机长串去算报告里的缺页率曲线。少了这一步，后面所有结论都建在流沙上。

这套流程不复杂，但它把「程序能跑」和「结果可信」这两件事分开了。页面置换实验真正练的不是背四个算法的规则，而是知道每个数字为什么是这个值，以及当它不对的时候该先看哪一行。希望帮到你。

本文还有配套的精品资源，点击获取