操作系统存储管理实验：地址转换、内存分配与页面置换

存储管理这个实验，是操作系统课程里最容易被做成"填空作业"的一节。我帮人看过不少版本：页表数组开好，地址转换函数里一行除法一行取模写完，置换算法套个 while 循环，跑出来的数字往报告里一贴，看着挺像回事。然后被追问一句"为什么三帧反而比四帧缺页少"就卡住了。存储管理实验真正难的地方不在代码量，而在于它同时踩在三个不同的抽象层上：硬件层的地址翻译、内核层的空间分配、策略层的置换决策。这三层搅在一起写，代码能跑但结论一定站不住。下面我按自己带人做这个实验的顺序，把每一层的动机、实现细节和踩过的坑摊开讲，代码片段都可以直接拿去改。

1. 先把实验目标拆开：这个实验到底在练什么

1.1 三层能力：地址转换、空间分配、页面置换

很多人一上手就直奔"写个 LRU"，因为置换算法看起来最有算法味，最好写，也最容易出对比图表。但存储管理实验的主干其实是地址转换，置换只是它下游的一个分支。我习惯把它拆成三层来看。

第一层是地址转换，核心就一件事：给一个逻辑地址，算出物理地址，或者告诉系统"这个页不在内存里"。这一层要处理的是页大小、页号位宽、偏移位宽、页表项字段、越界判定。它是纯确定性的，输入什么输出什么，写完就能用手算验证。

第二层是空间分配，也就是内存里那些空闲区怎么被切给进程。连续分配下的首次适应、最佳适应、最坏适应、循环首次适应，本质是同一套空闲区数据结构配四种查找策略。这一层练的是数据结构与碎片认知。

第三层是页面置换，在物理帧不够时决定淘汰谁。FIFO、LRU、OPT、Clock 这些，练的是策略思维和指标计算。这一层最容易出"看起来对"的代码，也最需要标尺来校验。

把这三层分清楚的好处很直接：调试的时候你知道该在哪一层找问题。缺页率算错，八成在第三层的统计口径；物理地址算错，一定在第一层的位运算；内存分配后碎片率离谱，问题在第二层的链表维护。

1.2 为什么三层不能混着写

我见过最典型的一种写法，是把地址转换和置换揉在一个函数里：判断页表项有效位，无效就顺手调一次置换，置换完接着算物理地址。代码短了二十行，但埋了三个隐患。

第一，统计口径会乱。缺页次数到底在哪个位置加一？如果转换函数里加了一次，置换函数里又加一次，最后数字直接翻倍。正确做法是缺页判定和缺页处理分离，计数只放在判定处。

第二，测试无法隔离。置换算法要单独测，你得能喂一串纯页号序列进去，不依赖页表和地址。如果它和转换函数耦合，你连一个干净的对照实验都做不了。

第三，报告写不出层次。实验报告里最值钱的部分是"为什么这个策略在这个访问模式下表现更好"，这需要你分别控制变量。混着写，你只能说"跑出来是这样"，说不出"因为这样所以这样"。

我的一般做法是：底层写一个纯粹的地址转换模块，中间写一个页表管理模块，上层写一个置换策略模块，策略模块只依赖"帧数组 + 页号序列"这两个输入。模块之间用明确的返回值约定，比如1表示命中、0表示缺页、-1表示地址越界。这个约定看着不起眼，但后面排错全靠它。

1.3 语言与工程结构的选型取舍

语言这块没有标准答案，但选错了会白费力气。我一般的建议是：地址转换和内存分配用 C 写，置换算法模拟用 Python 写。

C 的优势是能真实控制位宽。页表项用位域定义，你能直观看到"有效位占 1 bit、物理帧号占 20 bit"是什么概念，也能真切体会到把 32 位地址硬塞进int时的符号问题。用 Python 写地址转换，一个>>12就完事了，反而失去了位运算的训练价值。

Python 的优势是置换算法写起来快、改起来更快。你要对比 FIFO 和 LRU 在十组随机序列上的表现，Python 里换个函数名就能跑，C 里还得重新编译。而且 Python 的collections.OrderedDict和deque直接就是 LRU 和 FIFO 的现成骨架，能把注意力放在策略逻辑上而不是链表指针上。

工程结构上，我建议至少分成三个文件：mmu.c（地址转换）、alloc.c（分区分配）、replace.py（置换模拟），再加一个gen_trace.py生成测试序列。别嫌麻烦，后面写报告要出四张对比表的时候，你会庆幸当初分了文件。

提示：如果课程要求统一用一种语言，那就都用 C，但置换部分务必把"帧数组"和"页号序列"做成函数参数，别用全局变量。全局变量是实验报告里数据对不上的头号嫌疑犯。

2. 地址转换：一切的地基

2.1 逻辑地址怎么拆成页号和偏移

这一段的原理任何教材都写了，但真正写代码时出问题的地方在位宽推导，而不是公式本身。

给定两个参数：地址总线宽度N位，页大小2^k字节。那么页内偏移占低k位，页号占高N-k位，页表项数量是2^(N-k)。这个推导必须能脱口而出，因为后面所有参数都从这里来。

举个具体例子。32 位地址，页大小 4KB。4KB =2^12，所以k=12，偏移占低 12 位，页号占高 20 位，页表项数2^20 = 1048576项。用位运算写出来就是：

#define PAGE_SHIFT 12 #define PAGE_SIZE (1u << PAGE_SHIFT) // 4096 #define OFFSET_MASK (PAGE_SIZE - 1) // 0x00000FFF #define VPN_MASK (~OFFSET_MASK) // 0xFFFFF000 unsigned int vpn = vaddr >> PAGE_SHIFT; // 页号 unsigned int offset = vaddr & OFFSET_MASK; // 页内偏移

这里有个新手常犯的错误：用/和%代替移位和掩码。vaddr / 4096和vaddr % 4096在页大小是 2 的幂时结果完全一样，编译器一般也会优化成移位，但一旦页大小不是 2 的幂（有些实验会故意设成 1KB、2KB 之外的怪值），除法和取模仍然对，移位就错了。所以要么统一用除法取模保证通用性，要么在注释里写死"页大小必须是 2 的幂"。我倾向于用位运算，但把约束写在注释第一行。

另一个坑是有符号数。如果你把地址定义成int而不是unsigned int，当地址的最高位是 1 时（比如0x80000000），右移会做符号扩展，算出来的页号直接变成负数。这个 bug 在测试用例全用低地址时根本发现不了，一上高地址就炸。地址、页号、帧号这类量，一律用无符号类型。

2.2 页表项里那些位不是装饰

教材上的页表项通常画成一个方块，里面塞了有效位、修改位、访问位、保护位、物理帧号。很多人写代码时只保留"有效位 + 帧号"，其余全扔了，觉得反正实验用不上。这个取舍在只做地址转换时没问题，但一旦你要做置换算法，访问位和修改位就是核心输入。

我一般这样定义：

typedef struct { unsigned int pfn : 20; // 物理帧号 unsigned int valid : 1; // 是否在内存 unsigned int dirty : 1; // 是否被写过 unsigned int accessed : 1; // 是否被访问过 unsigned int prot : 3; // 读/写/执行权限 } pte_t;

这几个位各自的作用要能说清楚：

• 有效位（valid）：0 表示这个页不在物理内存，访问它就触发缺页异常。这是缺页判定的唯一依据，不要用"帧号是否为 0"来代替，因为 0 号帧是合法帧。
• 修改位（dirty）：写操作时置 1。置换时如果脏位为 1，淘汰前必须写回磁盘，代价翻倍。改进型 Clock 算法就是靠它区分淘汰优先级。
• 访问位（accessed）：读或写都置 1，由 Clock 算法周期性清零。它近似反映"最近是否用过"。
• 保护位（prot）：读、写、执行三种权限的编码。实验里可以简化，但至少要能演示"往只读页写触发保护异常"这个场景，这是加分项。

注意：valid和prot是两回事。页在内存里但只读，valid=1, prot=只读，写它应该报保护错误而不是缺页。很多实验代码把这两种异常合并成一个返回值，导致错误处理逻辑根本区分不开。

2.3 TLB 命中与缺失的完整判定路径

加了 TLB 之后，地址转换就不是"查一次页表"这么简单了。完整的判定顺序是：

1. 拆分逻辑地址，得到页号和偏移。先判页号是否越界，越界直接返回错误，不要往下走。
2. 拿页号查 TLB。命中则直接取出帧号，跳到第 6 步。
3. TLB 未命中，查内存中的页表。
4. 页表项valid=0，触发缺页异常，交给置换模块处理；处理完重新执行这条指令（实验中可以简化为重新走一遍流程）。
5. 页表项valid=1，把这一项填入 TLB。TLB 满了要按替换策略淘汰一项（实验里常用 LRU 或轮转）。
6. 用帧号拼偏移，得到物理地址：paddr = (pfn << PAGE_SHIFT) | offset。
7. 若是写操作，置脏位和访问位；若是读操作，只置访问位。

这个顺序里有两个细节特别容易被写错。

第一个是越界判定要在查 TLB 之前。我见过先查 TLB 再判越界的版本，结果一个超范围的页号恰好命中了 TLB 里某个残留项，直接算出一个荒唐的物理地址。越界是最便宜也最该先做的检查。

第二个是TLB 未命中不等于缺页。这两个概念混在一起是高频错误。TLB 未命中只是"快表里没有这条映射"，页表里大概率有；缺页是"页表说这个页不在内存"。前者是性能事件，后者是异常事件，处理代价差好几个数量级。统计的时候必须分开计数，否则你算出来的"缺页率"其实是"TLB 缺失率"，量级完全不对。

2.4 多级页表的动机：一个 4MB 的页表问题

单级页表在 32 位、4KB 页的配置下，页表项数是2^20 = 1048576。假设每项 4 字节，一个进程的页表就要占1048576 × 4B = 4MB。这个数字要亲手算一遍才有感觉。

4MB 的页表意味着什么？假设系统里有 100 个进程，光页表就要 400MB 连续物理内存。而且这 4MB 还必须是连续的，因为要能用页号直接索引。在物理内存本来就紧张的机器上，这个开销是灾难性的。更荒唐的是，绝大多数进程实际只用到几 MB 的地址空间，那 4MB 页表里 99% 的项都是无效的。

两级页表的思路就是把这张大表切开。32 位地址拆成10 + 10 + 12：高 10 位是页目录索引，中间 10 位是页表索引，低 12 位是偏移。顶级页目录有2^10 = 1024项，占1024 × 4B = 4KB，刚好一页。每个二级页表也是 4KB。

关键在于：二级页表可以按需分配。一个进程如果只用了低 4MB 地址空间，它只需要 1 个页目录 + 1 个二级页表，总共 8KB，而不是 4MB。省下来的空间是三个数量级。

写代码的时候，两级转换是这样的：

unsigned int pgdir_idx = (vaddr >> 22) & 0x3FF; // 高 10 位 unsigned int pgtbl_idx = (vaddr >> 12) & 0x3FF; // 中间 10 位 unsigned int offset = vaddr & 0xFFF; // 低 12 位 pde_t *pde = &pgdir[pgdir_idx]; if (!pde->present) return PAGE_FAULT; pte_t *pte = &pde->table[pgtbl_idx]; if (!pte->valid) return PAGE_FAULT; unsigned int paddr = (pte->pfn << 12) | offset;

注意这里出现了两次缺页判定机会：页目录项不存在，或者二级页表项无效。实验里如果只判第二次，遇到大范围未映射的地址会直接段错误。我在第一次做这个实验时就栽在这里，访问0x40000000附近的地址，页目录项是空的，解引用空指针直接崩，排查了半天才反应过来。

3. 内存分配：连续分配算法与空闲区管理

3.1 四种放置算法的真实差异

连续分配这一块，教材罗列了首次适应（First Fit）、循环首次适应（Next Fit）、最佳适应（Best Fit）、最坏适应（Worst Fit）四种。背定义很容易，但它们的差异只有在你亲手跑过几组作业序列之后才有体感。

首次适应从空闲区链表头部开始，找到第一个足够大的就切。优点是快，缺点是低地址区域会被反复切割，留下大量小碎片，高地址的大块反而长期闲置。

循环首次适应从上一次分配结束的位置开始找，形成一个环形扫描。它把压力均摊到整个地址空间，碎片分布更均匀，代价是空闲区链表要维护一个游标。

最佳适应遍历整个链表，找能满足要求的最小空闲区。听起来最优，实际上是最容易制造垃圾碎片的算法——它总是把大块切得只剩一点点，那些剩下来的几十字节碎片谁也用不上。

最坏适应反过来，总是从最大的空闲区里切。好处是切完剩下的块还足够大，能继续用；坏处是大块很快被消耗光，遇到大作业时无块可用。

这四种算法的取舍，本质是"查找速度"和"碎片形态"之间的权衡，没有绝对最优。我一般会在报告里用同一组作业序列跑四种算法，把最终的空闲区数量和最大空闲区大小两个指标列出来对比，比单纯比"分配成功率"有说服力得多。

3.2 空闲链表还是位图：数据结构选型

空闲区的组织方式主要有两种：空闲分区链表和位图。

空闲分区链表把每个空闲区做成一个节点，记录起始地址和长度，按地址排序串起来。优点是查找快、合并方便；缺点是要维护指针，节点本身占内存，而且链表的插入删除容易出现野指针。

位图用一个 bit 表示一个分配单位（比如一页）是否被占用。优点是结构简单、查连续空闲块方便、不需要额外指针；缺点是空间开销固定（哪怕只有一个进程也要占满整张位图），而且查找连续块需要扫描。

我的选择标准是：做分区分配实验用链表，做页式分配实验用位图。因为分区分配的作业大小是任意的，链表能精确表达"从 0x1000 开始、长度 0x2345 的空闲区"；页式分配的粒度固定是一页，位图天然合适。

链表节点的定义大概长这样：

typedef struct FreeBlock { unsigned int start; // 起始地址 unsigned int size; // 长度（字节） struct FreeBlock *next; } FreeBlock;

分配时的核心动作是切割：找到足够大的块后，如果剩余空间还够一个最小分配单位，就把原块拆成"已分配部分 + 新的空闲块"；如果不够，就整块给出去。回收时的核心动作是合并：新释放的块要和前后相邻的空闲块检查地址是否连续，连续就合并成一个。合并这一步最容易漏，漏了之后空闲区数量会虚高，碎片率算出来完全失真。

提示：合并时一定要判"前一块的 start + size == 当前块的 start"和"当前块的 start + size == 后一块的 start"，别只判其中一边。只判一边的代码在特定释放顺序下会把本该合并的块漏掉，这种 bug 靠随机测试很难复现，得手工构造用例。

3.3 碎片与紧凑：什么时候该考虑

碎片分两种：内部碎片是分配出去但用不上的空间（比如按页分配，进程只要 1KB 却给了 4KB），外部碎片是空闲但太小、谁也塞不进去的空隙。

连续分配主要产生外部碎片。当空闲总量够、但没有任何一个连续块够大时，就发生了"分配失败但内存没满"的尴尬局面。解决办法是紧凑：把所有已分配的块往低地址挪，把碎片拼成一个大块。

紧凑的实现不复杂，把所有已分配块的起始地址按顺序重排一遍，然后更新进程的基址寄存器即可。但在真实系统里代价极高，因为要搬运大量数据，还要保证搬运过程中不被打断。所以实际系统里紧凑是最后手段，能不用就不用。

实验里我建议至少模拟一次紧凑，把紧凑前后的空闲区数量和最大空闲块大小打印出来对比。这个对比特别直观，能让"外部碎片"从一个抽象名词变成一个看得见的数字。

3.4 一组可复现的对比数据

下面这组数据来自我常用的一个测试序列：内存 640KB，初始一整块空闲，作业请求按[130, 60, 100, 200, 140, 80, 50, 90]KB 依次到来，中途释放第 2 个和第 4 个作业。用四种算法分别跑，记录分配成功数和最终空闲区数量。

这组数字的说服力在于它和直觉相反：最佳适应听起来最好，实际上碎片最多、最大空闲块最小，因为它把大块切得太碎。首次适应虽然简单，但因为倾向于在低地址反复切割，反而保住了高地址的大块，最大空闲块仅次于循环首次适应。这类"反直觉"的结论，就是实验报告里最值得写的东西。

注意：具体数值依赖你的释放顺序和最小分配单位，别照抄。重要的是趋势，以及你能解释清楚这个趋势是怎么来的。

4. 页面置换：写对和"看起来对"的距离

4.1 FIFO 与 Belady 异常的手工验证

FIFO 的规则简单到几乎不会写错：维护一个队列，缺页时淘汰队头，新页入队尾。正因为它简单，它才适合用来验证你的整个模拟框架是否正确。

经典序列1,2,3,4,1,2,5,1,2,3,4,5是必须手算一遍的。三帧情况下：

三帧共缺页 9 次。同样序列换成四帧，手算下来是 10 次。帧数变多，缺页反而变多，这就是 Belady 异常。

这个现象的意义在于：它证明了"增加物理内存一定能提升性能"这个朴素认知是错的。FIFO 之所以会出现这种反常，是因为它只看"什么时候进来的"，完全不管"用了多少次"。一个很早进来但一直在用的页，会被一个刚进来但只用一次的页挤掉。

写代码验证这个现象，是检验你的模拟框架有没有"偷偷依赖帧号顺序"的最好办法。如果你的实现每次都把新页放在第一个空帧，而不是真正维护一个先进先出的队列，那你跑出来的结果会和手算对不上——因为你实现的其实是"第一次有空位就放"，不是 FIFO。

4.2 LRU 的两种实现：链表加哈希 vs 时间戳

LRU 淘汰"最久未被使用"的页，规则听着和 FIFO 差不多，实现难度差一个档次。

时间戳法最直观：给每个帧维护一个"最后访问时刻"，每次访问更新。缺页时线性扫描所有帧，找时间戳最小的淘汰。实现十分钟能写完，缺点是每次缺页 O(帧数) 的扫描。

双向链表 + 哈希表是标准解法：链表头部放最近访问的页，尾部放最久未用的页，每次访问把节点移到头部，缺页时直接摘尾部。用哈希表存"页号到链表节点"的映射，查找 O(1)。这套结构在 Python 里几乎免费：

from collections import OrderedDict class LRU: def __init__(self, capacity): self.cap = capacity self.data = OrderedDict() self.faults = 0 def access(self, page): if page in self.data: self.data.move_to_end(page) # 访问后挪到"最新"端 return False # 命中 self.faults += 1 if len(self.data) >= self.cap: self.data.popitem(last=False) # 淘汰最久未用 self.data[page] = True return True # 缺页

OrderedDict的move_to_end和popitem(last=False)就是链表头尾操作的封装，写起来干净，时间复杂度也对。

但这里有个陷阱值得单独说：平局怎么处理。如果两个帧的时间戳完全相同（在离散的访问序列里，如果每次访问只更新被访问的那一页，其他页时间戳保持不变，就可能出现并列最小），淘汰谁？不同实现会给出不同答案，导致同样的序列跑出不同的缺页次数。我建议在时间戳里带上一个单调递增的计数器而不是系统时间，保证严格全序，消除歧义。

4.3 OPT 的价值是当标尺

OPT（最佳置换）淘汰"未来最长时间不会被访问"的页，需要预知未来，现实中不可能实现。那为什么实验还要写它？

因为它是理论下界。任何实际算法在同一个序列上的缺页次数都不可能少于 OPT。有了这个标尺，你才能说"我的 LRU 比 OPT 多了 3 次缺页，差距 15%"，而不是干巴巴地说"LRU 缺页 20 次"。有了参照系，数字才有意义。

实现上，OPT 每次缺页时，对当前内存中的每一页，向后扫描剩余序列，找到它下一次出现的距离；距离最远的（或者干脆不再出现的）淘汰。不再出现的页要优先处理，用一个足够大的距离值（比如序列长度 + 1）表示。

def opt_choice(mem, seq, cur): farthest, victim = -1, None for p in mem: try: nxt = seq.index(p, cur + 1) except ValueError: return p # 以后不再用，直接淘汰 if nxt > farthest: farthest, victim = nxt, p return victim

这段代码的正确性依赖于seq.index(p, cur+1)从当前位置之后开始找。如果写成从 0 开始找，就会把"已经过去的访问"算进去，得到完全错误的结果。这个错误我见过两次，都是因为拷贝粘贴时没改起始参数。

提示：list.index是 O(n) 扫描，加上外层循环，OPT 整体是 O(缺页次数 × 帧数 × 序列长度)。序列长一点就会明显变慢。实验里序列控制在 1000 以内完全够用，别拿几万条的序列去跑 OPT。

4.4 Clock 与改进型 Clock 的实现要点

Clock 算法是 FIFO 和 LRU 的折中，用一个环形缓冲加一个访问位，扫描指针转圈，遇到访问位为 0 的就淘汰，为 1 的就清零并跳过。它不需要移动链表节点，也不需要维护时间戳，硬件开销极小，是最接近工程实用的方案之一。

实现的关键是指针不能重置。很多人的写法是每次缺页都从索引 0 开始扫描，那实现的就退化成了"扫描到第一个访问位为 0 的"，失去了 Clock 的轮转特性。正确做法是把指针存成实例变量，每次从上次停下的位置继续。

改进型 Clock 再引入修改位，把页分成四类，按优先级淘汰：

扫描时先找第一类，找不到就找第二类，同时把扫过的访问位清零，再扫一轮找第三类。这套逻辑的工程意义很实在：优先淘汰不用写回的页，能省一次磁盘 I/O。在磁盘比内存慢五个数量级的年代，这个优化值几个数量级的性能。

4.5 命中率、缺页率与有效访问时间的算法

指标计算这块，公式不难，难在统计口径。

命中率 = 命中次数 / 总访问次数，缺页率 = 缺页次数 / 总访问次数，两者相加为 1。前提是每次访问只有"命中"和"缺页"两种结果，不能有第三种。"首次装入"算不算缺页？算。因为物理帧里确实没有这个页，必须从外存读入。有些人把首次装入单独计数，导致缺页率偏低，和理论值对不上。

有效访问时间（EAT）的简化公式，不带 TLB 时是：

EAT = (1 - p) × t_mem + p × t_fault

其中p是缺页率，t_mem是内存访问时间，t_fault是缺页处理时间。带 TLB 时更完整的版本是：

EAT = α × t_tlb + (1 - α) × [(1 - p) × (t_tlb + t_mem) + p × (t_tlb + t_mem + t_fault)]

代一组数感受一下。设t_tlb = 10ns，t_mem = 100ns，α = 0.8，t_fault = 8ms = 8,000,000ns。

缺页率p = 10^-4时：

EAT = 0.8 × 10 + 0.2 × [0.9999 × 110 + 0.0001 × (110 + 8,000,000)] = 8 + 0.2 × [109.989 + 800.011] = 8 + 0.2 × 910 ≈ 190 ns

缺页率涨到p = 10^-3（只差一个数量级）时：

EAT = 8 + 0.2 × [0.999 × 110 + 0.001 × 8,000,110] = 8 + 0.2 × [109.89 + 8000.11] = 8 + 0.2 × 8110 ≈ 1630 ns

缺页率差 10 倍，EAT 差了 8 倍多。这个计算做一遍，你就明白为什么所有操作系统都在拼命优化缺页率，也明白为什么置换算法的优劣在真实系统里是生死攸关的事，而不是教科书上的练习题。

5. 完整实操：从零跑通一次实验

5.1 工程结构与编译

我推荐的目录结构是这样：

os-mm-lab/ ├── include/ │ ├── mmu.h # 页表项、地址宏 │ └── alloc.h # 空闲块结构 ├── src/ │ ├── mmu.c # 地址转换、TLB │ ├── alloc.c # 四种放置算法 │ └── main.c # 测试驱动 ├── sim/ │ ├── replace.py # 四种置换算法 │ └── gen_trace.py # 访问序列生成 └── Makefile

编译命令很简单：

gcc -O2 -Wall -Wextra -std=c11 -Iinclude src/*.c -o mm-lab

-Wall -Wextra一定要加。地址转换里的隐式类型转换、位域赋值溢出、有符号无符号比较，这些警告能帮你提前抓出一半的低级错误。我见过太多人因为没开警告，把unsigned int和int混用，跑出来的物理地址高位全是0xFFFFFFFF，还以为是页表算错了。

5.2 核心数据结构

页表用数组，TLB 用一个小数组加轮转指针，物理内存用一个帧数组表示：

#define PAGE_SHIFT 12 #define PAGE_SIZE (1u << PAGE_SHIFT) #define PT_ENTRIES (1u << 20) // 2^20 个页表项 #define TLB_SIZE 16 #define FRAME_COUNT 256 typedef struct { unsigned int pfn : 20; unsigned int valid : 1; unsigned int dirty : 1; unsigned int acc : 1; } pte_t; typedef struct { unsigned int vpn; unsigned int pfn; unsigned int stamp; int valid; } tlb_entry_t; static pte_t page_table[PT_ENTRIES]; static tlb_entry_t tlb[TLB_SIZE]; static int tlb_ptr = 0; static unsigned int clk = 0;

PT_ENTRIES设成2^20，静态数组占1048576 × 4B = 4MB，放在全局区完全没问题。如果嫌大，改成2^16并把地址宽度缩小到 28 位，功能一样能演示，内存压力小很多。

5.3 地址转换的实现

前面拆过的逻辑，这里给一个带 TLB 的完整版本：

/* 返回 1 命中, 0 缺页, -1 越界 */ int mmu_translate(unsigned int vaddr, int is_write, unsigned int *paddr) { unsigned int vpn = vaddr >> PAGE_SHIFT; unsigned int off = vaddr & (PAGE_SIZE - 1); if (vpn >= PT_ENTRIES) return -1; // 先判越界 clk++; for (int i = 0; i < TLB_SIZE; i++) { // 查 TLB if (tlb[i].valid && tlb[i].vpn == vpn) { tlb[i].stamp = clk; *paddr = (tlb[i].pfn << PAGE_SHIFT) | off; page_table[vpn].acc = 1; if (is_write) page_table[vpn].dirty = 1; return 1; } } pte_t *e = &page_table[vpn]; // 查页表 if (!e->valid) return 0; // 真缺页 e->acc = 1; if (is_write) e->dirty = 1; /* 填 TLB，满了按 LRU 淘汰 */ int slot = -1, lru = -1; unsigned int oldest = 0xFFFFFFFFu; for (int i = 0; i < TLB_SIZE; i++) { if (!tlb[i].valid) { slot = i; break; } if (tlb[i].stamp < oldest) { oldest = tlb[i].stamp; lru = i; } } if (slot < 0) slot = lru; tlb[slot].vpn = vpn; tlb[slot].pfn = e->pfn; tlb[slot].stamp = clk; tlb[slot].valid = 1; *paddr = (e->pfn << PAGE_SHIFT) | off; return 1; }

这段代码里有个易错点：写操作应该同时置访问位和脏位，不能只置脏位。访问位的语义是"被访问过"，写当然也是访问。只置脏位的写法在 Clock 算法里会导致刚写过的页被判定为"未访问"，过早淘汰。

5.4 缺页处理与置换主循环

缺页处理负责"分配一个帧、更新页表、如果需要则写回脏页"。用一个简单的帧位图管理空闲帧：

def handle_fault(page, mem, algo_state, clock): if len(mem) < FRAME_COUNT: mem.append(page) return 0 # 直接装入，无需淘汰 victim = algo_state.pick(mem, page, clock) mem[mem.index(victim)] = page return 1 if is_dirty(victim) else 0 # 返回写回次数

主循环就是把访问序列喂进去，统计三个数：命中次数、缺页次数、写回次数。这三个数字是所有对比表的基础，一定要一次跑全，别分三次跑——分三次跑很容易因为随机种子不同导致序列不同，数据就不可比了。

5.5 分区分配模拟

四种放置算法的差异只在"挑哪一块"这一个函数里，其余逻辑可以完全共用：

FreeBlock* find_first(FreeBlock *head, unsigned int size) { for (FreeBlock *p = head; p; p = p->next) if (p->size >= size) return p; return NULL; } FreeBlock* find_best(FreeBlock *head, unsigned int size) { FreeBlock *best = NULL; for (FreeBlock *p = head; p; p = p->next) if (p->size >= size && (!best || p->size < best->size)) best = p; return best; } FreeBlock* find_worst(FreeBlock *head, unsigned int size) { FreeBlock *worst = NULL; for (FreeBlock *p = head; p; p = p->next) if (p->size >= size && (!worst || p->size > worst->size)) worst = p; return worst; }

三个函数结构几乎一样，区别只在比较符号和是否提前返回。写完之后你会立刻发现：首次适应可以提前 break，最佳和最坏必须遍历完，这就是"快"和"优"的直接体现。

5.6 随机序列生成与批量对照

要出有说服力的数据，必须跑多组不同特性的序列。我一般生成三类：

• 顺序型：0,1,2,3,...,N循环，模拟顺序扫描文件。这类序列下所有算法表现都不错，区分度低。
• 局部型：80% 的访问落在 20% 的页上，模拟程序的热点循环。这类序列下 LRU 优势明显。
• 随机型：均匀随机，模拟访问模式混乱的场景。这类序列下 FIFO 和 LRU 差距缩小。

import random def gen_locality(n, pages, hot_ratio=0.8, hot_pages=5): seq = [] for _ in range(n): if random.random() < hot_ratio: seq.append(random.randrange(hot_pages)) else: seq.append(random.randrange(pages)) return seq

每类序列跑 5 个随机种子，取平均，再把四种算法在三种模式下的缺页率做成一张 4×3 的表。这张表放到报告里，比任何文字描述都有分量。

6. 常见问题排查实录

6.1 缺页次数对不上手算结果

这是最高频的问题。排查顺序我固定为三步。

第一步，检查首次装入是否计数。空帧状态下装入第一页一定缺页，这一点所有实现都应该一致。如果你手算 9 次、程序 6 次，差的那 3 次大概率就是前三次装入没算。

第二步，检查淘汰时的队列维护。以 FIFO 为例，如果你的实现是"缺页时把新页覆盖到索引fault_count % frames的位置"，那确实是 FIFO；如果是"找第一个空闲槽位填入"，那在帧未填满之前行为不同，填满之后也可能因为淘汰位置不对而偏差。手算时拿张纸把每一轮的内存状态写下来，和程序打印的状态逐轮对比，通常三轮之内就能定位。

第三步，检查序列本身。很多人手算用的序列和程序读入的序列不一致，比如手算时把重复访问漏了一个。把序列打印出来数字数，看着傻，但有效。

6.2 结果随机抖动，同样的算法跑两次不一样

只有一种可能：算法内部有未初始化状态或依赖了随机性。

Clock算法的指针、LRU的时间戳、TLB的轮转位置，这些状态变量如果不重置，跑第二组序列时会带着上一组的残留状态，结果当然不同。我一般在每个测试用例开始前调一次reset_state()，把所有状态清干净。

还有一种隐蔽的情况：用了dict或set的遍历顺序。Python 3.7 之后 dict 保序，但如果你用set存帧集合再遍历，顺序就不确定了，淘汰谁取决于哈希值。涉及淘汰的逻辑一律用列表或OrderedDict，别用set。

6.3 边界与类型陷阱

几个我踩过或见别人踩过的坑，列出来备查。

页号正好等于页表项数量。vpn == PT_ENTRIES时，page_table[vpn]已经越界了。判定必须是vpn >= PT_ENTRIES，不能写>。

物理地址回绕。帧号占 20 位，pfn << 12之后是 32 位，如果pfn最大能到2^20 - 1，左移 12 位不会溢出。但如果帧号字段定义成 21 位，就会溢出成 0。位域的位数要和地址宽度严格对应，这里不能拍脑袋。

序列里的页号超出范围。随机生成的序列要以实际页数为上界，否则访问到不存在的页会走越界分支，统计出来的缺页率偏高。生成序列时把上界写成pages而不是2^20，能省不少迷惑。

写回次数统计漏了。淘汰脏页要写回，这是置换开销的主要部分。如果你的对比表只有缺页率没有写回次数，等于只说了一半。改进型 Clock 的优化效果全靠写回次数体现，这一项必须统计。

6.4 速查表

7. 实验报告与答辩：怎么把数据讲成结论

7.1 图表怎么摆

报告的图表不在多，在能支撑结论。我建议至少放这四组。

第一组，Belady 异常验证表。同一序列在 3 帧和 4 帧下的 FIFO 缺页次数，配上每一轮的内存状态。这组图表的作用是证明你的模拟框架是真的在按 FIFO 跑，而不是碰巧跑出个数。

第二组，四种置换算法在三种访问模式下的缺页率对比。4×3 的表格加一张柱状对比。这组图表的作用是说明"没有普适最优算法，只有适配访问模式的算法"。局部性强的序列下 LRU 明显占优，随机序列下差距缩小，这个趋势要能从数据里看出来。

第三组，LRU 与 OPT 的差距。把 OPT 当上界，算出 LRU 相对 OPT 的百分比差距。这个数字能量化"我们的算法离理论最优还有多远"。

第四组，四种分区分配算法的碎片对比。空闲区数量、最大空闲块、碎片率三个指标。这组的作用是把"最佳适应反而最差"这个反直觉结论坐实。

每组图表配一段不超过五行的说明，讲清楚"这组数据在回答什么问题"。别写"如图所示"这种废话，直接写"三帧 9 次、四帧 10 次，说明 FIFO 不满足栈性质"。

7.2 三句能被追问的回答

答辩或者报告里被追问，通常集中在这三个问题。提前想好回答，比临时发挥稳得多。

为什么 FIFO 会出现 Belady 异常，LRU 不会？回答的核心是"栈性质"。LRU 满足包含性质：帧数为m时内存中的页集合，永远是帧数为m+1时集合的子集。所以增加帧数只可能减少缺页。FIFO 不满足这个性质，一个页可能因为"进来得早"被淘汰，而它明明还在被使用，增加帧数只是延长了它的存活时间，反而可能让它在新一轮访问时刚好被踢掉。

为什么改进型 Clock 优先淘汰"未访问且未修改"的页？两个维度分别对应两种代价。未访问意味着近期不太可能马上用到，淘汰它不会立刻引发缺页；未修改意味着不需要写回磁盘，省一次 I/O。两个条件同时满足，淘汰代价最低。这两条其实是在用极低的硬件成本，近似 LRU 的判断，同时顺带优化了写回开销。

如果物理内存足够大，还需要置换算法吗？需要，但形式变了。内存够大时缺页率极低，置换算法很少被触发，它的作用从"性能优化"退化成"兜底保护"——防止某个进程把所有内存吃光。这时候一般会加工作集监控，动态调整每个进程的帧配额，而不是单纯靠置换策略。

最后分享一个我在这个实验里最实在的体会：先手算，再写码。任何一组置换序列，动手在纸上推一遍，把每轮的内存状态写出来，然后再去写代码。看起来慢，但省下的调试时间远超这点投入。我见过太多人代码写完跑出个数就交，被问"这个数怎么来的"答不上来——其实只要当初花十分钟手算一遍，整个实验的理解深度就完全不同了。存储管理这一块，代码只是手段，能说清楚每一个数字背后的因果，才是这个实验真正要练的东西。