操作系统内存管理大题通关：分页、页面置换与有效访问时间-平芜编程栈

1. 先建一张题型地图：内存管理大题就这六类问法

内存管理这一章，教材上理论铺得最开，但落到卷子上，大题的形状其实非常固定。你翻十套卷子，会发现它们反反复复就在问那六件事：地址怎么变、页表占多大、页面怎么换、缺页率怎么算、分区怎么分、工作集怎么求。真正让人丢分的从来不是"没学过"，而是同一个知识点换一种问法就认不出来，或者算到一半被单位、进制、表格抄写搞崩。

我自己的复习顺序是先"归类"再"刷题"。归类就是把这六类题各自的输入—工具—输出写在一张纸上，做题时先判断这是哪一类，再调用对应模板。这个动作看着笨，但比无脑刷五十道题管用得多，因为考场上最怕的是"这道题我没见过"，而归类之后你会发现，所谓的新题只是老题换了个外壳。

1.1 六类题型的核心公式速查

下面这张表是我自己整理并反复修订过的版本，左边是题型，中间是核心工具，右边那一列特意写了"最容易翻车的地方"——这一列才是这张表的真正价值所在。

题型	典型问法	核心工具/公式	高频翻车点
动态分区分配	给空闲分区表和作业序列，画分配过程	首次适应、最佳适应、最坏适应、循环首次适应	回收时的相邻空闲区合并
分页地址变换	给逻辑地址求物理地址	页号 = 逻辑地址 / 页面大小；偏移 = 逻辑地址 mod 页面大小	十六进制拆位、页号起始值
页表尺寸与多级页表	求页表占用多少字节	项数 = 2^(页号位数)，页表大小 = 项数 × 项长	忘记乘进程数、项长取值
页面置换算法	给引用串求缺页次数/缺页率	FIFO、LRU、OPT、Clock	首次访问是否计缺页、表格抄错列
有效访问时间	求 EAT	命中率×单次时间 + 未命中率×多次时间，再叠加缺页率	单位不统一、缺页时间是否含访存
工作集与抖动	求工作集大小、判断是否抖动	WS(t, Δ)，可用页框数对比	窗口定义（按次数还是按时间）

把这张表背下来意义不大，真正要做的是每一类都亲手推演三五道，直到你能在不看答案的情况下自己解释为什么这一步要这么做。比如最佳适应为什么容易产生小碎片、两级页表为什么能省空间、LRU 为什么不会被 Belady 异常影响，这些问题想通了，题目怎么变形都不怕。

1.2 为什么这些题总在细节上丢分

说个很实在的观察：内存管理大题的难度是"台阶型"的——看答案觉得简单，自己动手就错。原因通常集中在这几处。

第一是单位混乱。有效访问时间那道题，内存访问给的是纳秒，磁盘访问给的是毫秒，缺页率给的是小数或百分数，稍不留神就是三个数量级的偏差。我踩过最典型的一次，是把 8ms 直接代进以 ns 为单位的公式，算出 EAT 等于八千多纳秒，还觉得答案挺合理。

第二是进制转换。十六进制地址和页面大小的关系是天然的"对齐"关系，页面大小是 4KB 时，末三位十六进制数就是页内偏移，前面是页号，这个规律一旦掌握，拆地址就是两三秒的事；反过来如果硬算十进制，就等着出错。

第三是表格推演过程中的抄写错误。置换算法题给十几个引用数字，要在三四行里反复比对，手写时漏一个数、抄错一列，后面全盘皆错，而这类题通常不给分步骤的宽容度。

提示：置换算法题一律用"逐列推进"的表格，不要用文字叙述过程。表格每一列对应一个引用数字，命中就在格子里打勾，缺页就写下当前页框内容，这样即使最后结果错了，过程分也拿得到。

还有一类隐形的坑是概念前提被忽略。比如题目没写"采用请求分页"你就不能默认有缺页，题目前面给的是"页表项 4 字节"你就不能用 2 字节去算，题目问"页表占用"你要先判断是问单个进程的还是整个系统的。这些前提通常在题干第一句，或者一句不起眼的括号里，读题时用笔圈出来是值得的。

2. 动态分区分配大题：三种算法的手算差异与空闲分区表怎么画

连续分配管理方式里的动态分区分配，是内存管理章节里最"动手"的一类题。它不需要复杂公式，但要你在纸上模拟一个分配器，一步步更新空闲分区表。这类题的评分点非常明确：分配位置对不对、剩余分区大小对不对、要不要合并——三项全对才给满分。

2.1 题目给的是什么，你要画什么

题目的标准形态是这样的：给一张空闲分区表，每项包含起始地址和大小，分区按地址递增排列；再给一个作业序列，每个作业请求若干大小的内存；要求画出每次分配后的空闲分区表，或者计算某次分配之后剩余的碎片大小。

手算的时候我建议用下面这个格式，横着一行写清楚"作业—请求大小—分配到的位置—剩余情况"，比画方块图快得多也清楚得多。关键字在于：分配之后空闲分区表要重新按地址排序，这一步很多人会漏。

2.2 一个例子跑通三种算法

假设初始空闲分区表如下（地址递增）：

序号	起始地址	大小
1	100K	50K
2	200K	40K
3	300K	20K
4	400K	60K

作业序列：A 请求 30K，B 请求 45K，C 请求 15K。

首次适应：从低地址开始找第一个够大的分区。

A(30K)：100K 处的 50K 够 → 分配 30K，剩 20K，起始地址变为 130K。
B(45K)：130K 处的 20K 不够，200K 处的 40K 不够，300K 处的 20K 不够，400K 处的 60K 够 → 分配 45K，剩 15K，起始地址 445K。
C(15K)：回到低地址，130K 处的 20K 够 → 分配 15K，剩 5K，起始地址 145K。

最终空闲区：145K/5K、200K/40K、300K/20K、445K/15K。

最佳适应：每次找容量最小且足够的分区。这里必须注意，最佳适应是把空闲区按容量递增排序来找的，不是按地址。

A(30K)：候选 50K、40K、60K（20K 不够），最小够大的是 40K → 分配在 200K 处，剩 10K，起始地址 230K。
B(45K)：候选 50K、60K、10K（不够），最小够大的是 50K → 分配在 100K 处，剩 5K，起始地址 145K。
C(15K)：候选 10K 不够、5K 不够、20K 够、60K 够 → 最小够大是 300K 处的 20K → 全部用掉，该分区从表中消失。

最终空闲区：145K/5K、230K/10K、400K/60K。

最坏适应：每次挑最大的分区切。

A(30K)：最大的是 400K 处 60K → 分配 30K，剩 30K，起始地址 430K。
B(45K)：候选 50K、40K、20K、30K → 最大是 100K 处的 50K → 分配 45K，剩 5K，起始地址 145K。
C(15K)：候选剩下的 40K、20K、30K → 最大是 200K 处的 40K → 分配 15K，剩 25K，起始地址 215K。

对同一个作业序列，三种算法给出了三套完全不同的空闲分区表。这就是为什么这类题必须老老实实按算法规则走，凭"感觉"分配必错。

2.3 内存回收的四种相邻情况

分配会做，回收更容易错。当一个作业释放它占用的分区时，要看它的前后是否有空闲分区，一共四种情况：

情况	处理方式
前后都不空闲	单独成一个新空闲区
前空闲、后占用	与前面的空闲区合并，起始地址取前者的
前占用、后空闲	与后面的空闲区合并，大小相加
前后都空闲	三块合并成一块，大小是三者之和

注意：合并后的起始地址一律取地址较小的那块，大小是相加，中间不能留空洞。很多同学会在"前后都空闲"时只合并一侧，结果空闲区表里出现两块本该连着却分开的记录。

2.4 内部碎片与外部碎片的判定

连续分配的两种典型问题：内部碎片和外部碎片。固定分区会产生内部碎片——分区内部分配出去但用不完的部分；动态分区会产生外部碎片——分区之间那些太小、谁都放不下的小空闲块。

上面那个例子跑完之后，最佳适应留下了 5K 和 10K 两个小块，最坏适应留下了 15K、20K 级别的块。如果后面再来一个请求 25K 的作业，最佳适应的结果就放不下，尽管空闲总量够——这就是外部碎片带来的"总量够但用不上"的典型困境。解决办法是紧凑，把已分配区移到一端，空闲区合并成一大块，代价是需要重定位和动态重定位寄存器的支持。

3. 分页地址变换：逻辑地址拆分的三步法

分页系统的地址变换是整章出现频率最高的计算题，几乎没有一份卷子会跳过它。它的核心只有一句话：逻辑地址被拆成页号和页内偏移，页号查表换成页框号，页框号和原偏移拼起来就是物理地址。听起来简单，但真正做题时，麻烦在于进制和单位。

3.1 先算页面大小的位数

第一步永远是确定页面大小对应几位二进制。这一步决定了后面所有拆分的位置。

1KB = 2^10，偏移占 10 位；
2KB = 2^11，偏移占 11 位；
4KB = 2^12，偏移占 12 位；
1MB = 2^20，偏移占 20 位。

如果逻辑地址是 32 位、页面大小 4KB，那么页号就是 32 − 12 = 20 位，页号取值范围是 0 到 2^20 − 1。这一步要先写在草稿纸边上，后面所有计算都依赖它。

3.2 十进制与十六进制两条路

十进制路线适合题目给的是十进制地址。公式就两条：

页号 = 逻辑地址 / 页面大小（整除，向下取整） 页内偏移 = 逻辑地址 mod 页面大小 物理地址 = 页框号 × 页面大小 + 页内偏移

十六进制路线在页面大小是 4KB（也就是 0x1000）的时候极其好用，因为除以 0x1000 在十六进制里就是"右移三位"。举个例子，逻辑地址 0x3A5F：

末三位是偏移：0xA5F；
前面的部分是页号：0x3，也就是十进制 3；
查页表，若页号 3 对应页框号 5，物理地址就是 0x5A5F。

换算一下验证：0x3A5F = 3 × 4096 + 2655 = 14943；物理地址 0x5A5F = 5 × 4096 + 2655 = 23135。两边完全一致。

提示：只要页面大小是 2 的整数次幂，十六进制地址的"低位就是偏移"这个性质就成立。页面大小是 16KB 时，偏移占 14 位，也就是末三位半十六进制，这时候要小心半位的处理，最好回到二进制去数，别硬套。

3.3 缺页发生在哪一步

地址变换的完整链路是：CPU 给出逻辑地址 → 拆出页号和偏移 → 查 TLB → 命中直接拿页框号 → 未命中查页表 → 页表项有效位为 1 则取页框号 → 有效位为 0 触发缺页中断 → 操作系统调页 → 更新页表 → 重新执行指令。

所以在题目里看到"页表项有效位为 0"，那不是让你算物理地址，而是让你写缺页中断的处理流程。这两类问法经常出现在同一道题的两个小问里，第一问算地址，第二问模拟一次缺页，答的时候要把"重新执行"这一步写出来，因为缺页中断处理完之后是回到原指令重试，不是接着往下执行。

另外还有一个容易被忽略的细节：如果题目给了访问位和修改位，置换的时候要判断是不是脏页。修改位为 1 说明页面被写过，换出时必须写回磁盘，换出代价更高。这个点在置换算法和有效访问时间两类题里都会用到，但很多同学只把它当成页表结构的知识点背，做题时想不起来。

4. 页表尺寸与多级页表：一道"页表占多大"题目的完整推演

"页表占多少内存"这类题看着像送分，实际上是最容易因为一个默认取值而全盘错掉的一类。它的难点不在计算，在于你对页表结构的假设必须和题目一致。

4.1 页表项数怎么来

页表的项数只取决于页号的位数，和物理内存大小无关。页号有多少位，就最多有多少个不同的页，每一项对应一个页的映射。

以一个典型配置为例：逻辑地址 32 位，页面大小 4KB，页表项 4 字节。

页内偏移 = 12 位，页号 = 20 位；
页表项数 = 2^20 = 1M 项；
单个进程的页表大小 = 1M × 4B = 4MB。

如果系统里同时有 100 个进程，光是页表就要占 400MB。这个数字本身就回答了"为什么要多级页表"这个问题——不是因为算法高级，而是因为一级页表实在太胖了。

注意：页表项的大小是题目给的重要前提。教材上常见的有 2 字节、4 字节、8 字节三种。页表项里通常包含页框号、有效位、修改位、访问位、保护位等字段，所以它的尺寸往往比"存页框号所需的字节数"更大。题目给什么就用什么，不要自己按页框号的位数去推。

4.2 两级页表的分拆规则

两级页表的做法是把 20 位的页号再切成两段。常见的分法是外层的页目录索引 10 位，内层的页表索引 10 位。

这样一级页表（页目录）有 2^10 = 1024 项，每项 4 字节，正好 4KB ——刚好一页，这就是分拆位数的隐含目标：让每一级页表自己也占用整数个页面，这样才能被分页机制统一管理。

二级页表每个也是 4KB。关键在于，进程不需要为整个 4GB 逻辑空间都建二级页表，只需要为实际用到的区域建。如果某个进程只用到了最低的 8MB 空间，那它需要的二级页表可能只有两三个，总开销是 4KB（页目录）+ 2 × 4KB（二级页表）= 12KB，而不是 4MB。这就是多级页表真正的收益所在。

方案	页表空间开销	访存次数（不含 TLB）
一级页表	4MB（每进程）	2 次
两级页表	页目录 4KB + 按需的二级页表	3 次
加 TLB	不变	命中时接近 1 次

访存次数从 2 次变成 3 次，这是多级页表付出的代价。所以真实系统里多级页表一定和 TLB 搭配使用，TLB 命中时根本不走多级查找这条路。

4.3 反置页表为什么能省空间

反置页表的思路是反过来记：不为每个逻辑页建表项，而是为每个物理页框建一个表项，里面记录"这个页框现在装的是哪个进程的哪一页"。

物理内存 4GB、页面 4KB 时，页框数是 2^20 = 1M，反置页表就是 1M 项。每项包含进程标识和页号，按 8 字节算总共 8MB，而且整个系统只有这一份，所有进程共享。

对比一下就清楚了：正排页表每进程 4MB，100 个进程 400MB；反置页表全系统 8MB。省空间的原理是"表项数跟着物理内存走，不跟逻辑地址空间走"。

它的代价是查表变慢——要按进程标识和页号去搜索整张表，这个搜索通常靠散列表来加速。另外反置页表在换页时不好处理共享页面。这些细节在概念题里出现过，答题时点出"省空间、但查找复杂"就够了。

5. 页面置换算法：FIFO/LRU/OPT/Clock 的推演模板与 Belady 异常

置换算法是整章最考验耐心的题型。给一串访问序列，给一个页框数，让你求缺页次数和缺页率。核心能力只有两个：把手算过程组织成表格，以及准确判断"该换谁"。

5.1 画表规则

我的做法是画一张横向的表格，列数等于引用串长度，每一列记录三件事：当前访问的页号、页框里现在装了什么、是否缺页。页框内部用一个顺序标记表示"谁最老"。

引用串我统一用教材上那个经典序列，方便和标准答案对：7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1，页框数取 3。

5.2 FIFO、LRU、OPT 的推演结果

先把结论列出来，再解释一个算法的完整过程。

算法	缺页次数	缺页率
OPT（最佳置换）	9	45%
LRU（最近最久未使用）	12	60%
FIFO（先进先出）	15	75%

FIFO 的完整推演过程：每个页框维护一个进入顺序，缺页时淘汰最早进入的那个。

访问 7，缺页，装入，页框为 [7]
访问 0，缺页，装入，[7, 0]
访问 1，缺页，装入，[7, 0, 1]
访问 2，缺页，淘汰 7，[2, 0, 1]
访问 0，命中
访问 3，缺页，淘汰 0，[2, 3, 1]
访问 0，缺页，淘汰 1，[2, 3, 0]
访问 4，缺页，淘汰 2，[4, 3, 0]
访问 2，缺页，淘汰 3，[4, 2, 0]
访问 3，缺页，淘汰 0，[4, 2, 3]
访问 0，缺页，淘汰 4，[0, 2, 3]
访问 3，命中
访问 2，命中
访问 1，缺页，淘汰 2，[0, 1, 3]
访问 2，缺页，淘汰 3，[0, 1, 2]
访问 0，命中
访问 1，命中
访问 7，缺页，淘汰 0，[7, 1, 2]
访问 0，缺页，淘汰 1，[7, 0, 2]
访问 1，缺页，淘汰 2，[7, 0, 1]

统计缺页共 15 次，缺页率 15/20 = 75%。

LRU 的区别只在于淘汰谁：淘汰的是"最长时间没有被访问过"的那一页。刚才那串里，第一次淘汰发生在访问 2 的时候，FIFO 淘汰的是 7（最先进入），LRU 淘汰的也是 7（最近最久没用）。但到后面就分道扬镳了，比如访问 3 的时候，FIFO 淘汰 0，LRU 淘汰的是 1，因为 0 在之前刚被访问过。这就是为什么 LRU 在这串上比 FIFO 少 3 次缺页。

OPT 需要看到未来：淘汰"未来最长时间不会被访问"的页。做题时要在引用串的当前位置往后扫，找出每个页框里的页下一次出现的位置，谁的"下次出现位置"最靠后（或者干脆不再出现），就淘汰谁。回到访问 2 那一步：页框里是 [7, 0, 1]，7 的下一次出现在第 18 位，0 在第 5 位，1 在第 14 位，最靠后的是 7，淘汰它。

提示：OPT 手算最容易在"后面还出现不出现"上漏看。建议在引用串下方用铅笔标出每一页的所有出现位置，判断时直接对照，不要凭眼扫。

5.3 Belady 异常

FIFO 有一个反直觉的毛病：页框数增加，缺页次数反而可能变多。经典反例是引用串 1、2、3、4、1、2、5、1、2、3、4、5。

页框数 3：缺页 9 次（1、2、3、4、1、2、5、3、4）
页框数 4：缺页 10 次（1、2、3、4、5、1、2、3、4、5）

多了 1 个页框，反而多缺 1 次。这种现象叫 Belady 异常，LRU 和 OPT 不会出现，因为它们满足"栈算法"性质——页框数 n 的驻留集一定是页框数 n+1 驻留集的子集。

考场上如果题目问"为什么 FIFO 会出现这种异常"，标准答法是：FIFO 的淘汰策略与页面的访问历史无关，新增页框会打乱原有的置换节奏，导致原本还能命中的页面被提前换出；而 LRU 具有栈性质，增加页框只会让驻留集单调扩大，因此不会异常。

5.4 Clock 算法的正确手算姿势

Clock 是 LRU 的近似实现，硬件开销小，真实系统里用得比 LRU 多，题目也会考。它的规则是：页框排成一个环形缓冲区，每个页有一个访问位；需要一个页框时，指针从当前位置向前扫，遇到访问位为 1 的就把它清零并跳过，遇到访问位为 0 的就选它淘汰。

手算时的常见错误是"跳过之后忘了把访问位清零"。一定要记住，指针扫过的每一页，访问位都被改成 0——这正是 Clock 用一次遍历就把"最近用过"的信息抹掉的机制。

改进型 Clock 引入修改位，把页面分成四类：(访问位, 修改位) = (0,0)、(0,1)、(1,0)、(1,1)。淘汰顺序是优先选 (0,0)，其次是 (0,1)，然后才是 (1,0)、(1,1)。题目如果给了访问位和修改位的当前值，照着这个优先级挑就行。

6. 缺页率与有效访问时间：公式怎么拼、单位怎么统一

有效访问时间（EAT）这类题的可怕之处在于，它的公式看起来很长，但本质上就是把一条访存路径上所有可能的分支按概率加权。拆开看只有两类分支：命中或者未命中，未命中里再分 TLB 未命中和缺页。

6.1 只有 TLB 的情况

设 TLB 查找耗时 ε，内存访问耗时 t，TLB 命中率 α。

命中：查 TLB（ε）+ 访问内存一次（t）
未命中：查 TLB（ε）+ 访问内存查页表（t）+ 访问内存取数据（t）

所以：

EAT = α × (ε + t) + (1 − α) × (ε + 2t)

代入一组实际数字：ε = 10ns，t = 100ns，α = 98%。

EAT = 0.98 × 110 + 0.02 × 210 = 107.8 + 4.2 = 112ns

注意 TLB 查找时间在两种情况里都要算，因为它无论如何都会执行一次。这一点是很多人的失分点：直接把命中写成 t、未命中写成 2t，忘了加 ε。

6.2 再叠加缺页

缺页的场景要把缺页率 p 叠上去：

EAT = (1 − p) × (上面算出的无缺页 EAT) + p × 缺页处理时间

缺页处理时间通常是一个很大的数，量级在毫秒，来源包括：缺页中断的处理开销、判断所需页面是否在内存、有空闲页框就分配、没有就选一页换出（脏页要写回磁盘）、从磁盘读入所需页面、更新页表和 TLB、恢复进程运行。

用上一节的 112ns，加上 p = 0.001、缺页处理时间 10ms（也就是 10^7 ns）：

EAT = 0.999 × 112 + 0.001 × 10^7 ≈ 111.9 + 10000 ≈ 10111.9ns ≈ 10.1μs

千分之一的缺页率，把 112ns 抬到了 10μs 左右，慢了近 90 倍。这个结果本身就是一道很好的概念题答案：缺页是极其昂贵的操作，必须用尽可能好的置换算法把它压下去，哪怕把缺页率从 0.001 降到 0.0001，EAT 也会从 10μs 掉到 1.1μs 量级。

6.3 单位陷阱与量级感

这类题丢分，八成栽在单位上。我的对策是所有时间统一换算成纳秒后再代入，并且换算时把指数写全。

单位	纳秒表示	记忆方式
1μs	10^3 ns	微秒是千分之一毫秒
1ms	10^6 ns	毫秒是百万纳秒
1s	10^9 ns	秒是十亿纳秒

养成一个习惯：把磁盘访问时间、缺页处理时间先换算成 ns，再进公式。如果最后算出的 EAT 比单次内存访问时间还小，那一定是哪一步错了——EAT 永远不小于最好情况下的单次访存时间，这是个很好的量级自检。

注意：有的题目把缺页处理时间写成"包括 6ms 的磁盘访问和 1ms 的中断处理"，这时候要相加而不是取其一。也有题目直接说"缺页处理开销为 M，忽略其他时间"，那就不用再叠加。读题时把"包含"和"另有"这两个词划出来。

7. 分段与段页式：越界检查与访存次数

分页是"按固定大小切"，分段是"按逻辑单位切"，两者的地址变换结构不同，题目问法也不同。分段的地址变换多了一步越界检查，这是它区别于分页的关键，也是最常被考的地方。

7.1 段表结构与越界检查

逻辑地址由段号和段内偏移组成。段表每一项包含两个关键字段：段长和基址（段的起始物理地址）。

变换流程是：

用段号查段表，取出段长和基址；
比较段内偏移和段长，如果偏移 ≥ 段长，产生越界中断；
否则物理地址 = 基址 + 段内偏移。

注意这里的判定条件是"偏移 ≥ 段长"就中断，不是"偏移 > 段长"。因为偏移是从 0 开始计数的，段长为 L 时合法偏移范围是 0 到 L−1，偏移等于 L 已经越界了。这个等号是个高频陷阱，我在模拟卷上错过两次。

还有一点：分段中段的长度可变，所以每个段的越界界限都不同，必须查段表才能判断；而分页中所有页大小相同，越界检查只需要看页号是否超过页表项数，比分段简单。

7.2 段页式地址变换

段页式把两者结合：先按逻辑单位分段，再把每个段按固定大小分页。逻辑地址的结构变成三段：段号、段内页号、页内偏移。

变换过程是这样的：

用段号查段表，得到该段的页表起始地址；
用段内页号查这个页表，得到页框号；
页框号拼接页内偏移，得到物理地址。

这需要三次访存：查段表、查页表、取数据。如果只用段表，是两次访存；只用页表，也是两次访存。段页式为了同时获得"逻辑上便于共享和保护"和"物理上消除外部碎片"这两个好处，付出了多一次访存的代价——这个取舍在概念题里经常被问。

段页式的越界检查要在两个地方做：一是段内页号不能超过该段的页表长度，二是页内偏移不能超过页面大小。两个检查缺一不可，因为一段的最后一页通常是不满的，光检查页号范围还不够。

7.3 访存次数与 TLB 的配合

把各类方案的访存次数放在一起对照，会更清楚为什么真实系统最后都选了带 TLB 的分页或者段页式：

方案	无 TLB 访存次数	有 TLB（命中）
一级分页	2	1
二级分页	3	1
分段	2	1
段页式	3	1

TLB 命中时，页框号直接从快表拿到，不需要走页表层级，这是它能把三次访存压到一次的原因。但要注意，TLB 里存的是"页号—页框号"的映射，段页式下 TLB 的表项还要额外带上段号的标识，否则不同段里的同一个页号会混淆。这个细节在选择题里出现过。

8. 虚拟内存边界：工作集、抖动与页框分配

这一类题属于"看似简单、实则定义决定答案"。工作集的算法本身很简单，但不同教材对窗口的定义不一样，做题第一步必须确认题目用的是哪一种。

8.1 工作集窗口的两种定义

工作集 WS(t, Δ) 指的是在时刻 t 之前的 Δ 时间窗口内，进程访问过的所有页面的集合。这里的 Δ 可以是时间长度（比如最近 10ms），也可以是访问次数（比如最近 k 次访存）。题目给了哪一种就用哪一种。

用引用串 2、6、1、5、7、7、7、7、5、1、6、2、3、4、1 走一遍，取窗口大小为最近 4 次访问（含当前这次）：

时刻	当前访问	窗口内引用	工作集
1	2	2	{2}
2	6	2, 6	{2, 6}
3	1	2, 6, 1	{1, 2, 6}
4	5	2, 6, 1, 5	{1, 2, 5, 6}
5	7	6, 1, 5, 7	{1, 5, 6, 7}
6	7	1, 5, 7, 7	{1, 5, 7}
7	7	5, 7, 7, 7	{5, 7}
8	7	7, 7, 7, 7	{7}
9	5	7, 7, 7, 5	{5, 7}
10	1	7, 7, 5, 1	{1, 5, 7}
11	6	7, 5, 1, 6	{1, 5, 6, 7}
12	2	5, 1, 6, 2	{1, 2, 5, 6}
13	3	1, 6, 2, 3	{1, 2, 3, 6}
14	4	6, 2, 3, 4	{2, 3, 4, 6}
15	1	2, 3, 4, 1	{1, 2, 3, 4}

从这张表能直观看到工作集的"收缩—扩张"节奏：第 5 到第 8 时刻，因为反复访问 7，工作集缩小到只有一页；之后又逐步扩回 4 页。这正对应操作系统在运行过程中访存局部性的变化。

8.2 抖动判定与页框数的关系

抖动的定义是：刚被换出的页面很快又要被访问，于是又要换入，系统把大量时间花在换页上，CPU 利用率急剧下降。

判定的方法就是拿可用页框数和工作集大小比：可用页框数小于当前工作集大小时，进程就会频繁缺页，处在抖动状态。

用上面的表来说明：如果给这个进程分配 4 个页框，那在工作集最大为 4 的时刻（第 4、5、12、13、14、15 时刻）它刚好够用，不抖动；如果只给 2 个页框，那第 4 时刻之后就一直不够，必然抖动。

防止抖动的思路有三条：

局部置换策略：每个进程只在自己的页框里置换，不去抢别人的，缺点是不能灵活调剂；
工作集模型：操作系统周期性统计每个进程的工作集，给它分配不小于工作集大小的页框数，不够就把部分进程挂起，把页框腾出来；
页错误频率控制：设定上下阈值，缺页率超过上阈值就多给页框，低于下阈值就收回一些页框。

这三条里，工作集模型最直观，也最常被出成大题。

8.3 页框分配和置换范围

分配策略上，常见的有两种问法。平均分配是把 m 个页框平均分给 n 个进程，每个进程 m/n 个；按比例分配是依据进程大小按比例给，比如进程大小分别是 10 页、30 页、60 页，总页框 100 个，那就分别给 10、30、60 个。

置换范围上，分为局部置换和全局置换：

置换范围	特点	缺点
局部置换	只在本进程分到的页框里换	页框分配不合理时无法自我调节
全局置换	可以从系统空闲页框里取，也可以换其他进程的页	可能影响其他进程的缺页率

提示：局部置换和全局置换跟"固定分配/可变分配"是一对组合，常见的有固定分配局部置换、可变分配全局置换、可变分配局部置换三种。答题时如果题目问"哪种策略能动态调整页框数"，答案一定是可变分配的那两种。

9. 考场上怎么答：模板与易错清单

刷到最后，你会发现真正决定分数上限的不是"会不会"，而是"能不能在有限时间里把会的东西完整落纸"。我总结了一套自己用着顺手的答题顺序，供参考。

9.1 通用答题模板

拿到一道内存管理大题，先花半分钟做完三件事：

圈出前提：页面大小、地址位数、页表项大小、是否使用 TLB、是否请求分页、页框数；
写出公式：在草稿纸左上角把要用到的公式和单位换算写出来，避免中途找公式；
判断题型：属于第一节那张表里的哪一类，然后调用对应模板。

写答案时，计算题一定要把中间步骤留下来——页号是多少、偏移是多少、查表得到的页框号是多少。一是方便自己回查，二是阅卷时步骤分很实在，尤其置换算法这种过程繁多的题。

9.2 二十条易错点清单

下面这份清单是我自己攒的，每条后面都来自真实踩过的坑。

序号	易错点	正确做法
1	首次访问不算缺页	首次访问页面一定缺页，要计入
2	页号从 1 开始编号	页号从 0 开始
3	越界判定用"偏移 > 段长"	应为"偏移 ≥ 段长"
4	页表大小忘记乘进程数	看清题目问单进程还是全系统
5	页表项大小自己猜	用题目给的值
6	多级页表分级位数随意拆	让每级页表正好占一页
7	有效访问时间漏算 TLB 查找	命中和未命中都要加 ε
8	单位混用	全部换算成纳秒再算
9	缺页处理时间漏加写回时间	脏页换出要算进去
10	FIFO 用页框数算索引	用进入顺序维护，不要算下标
11	LRU 用"上次访问时刻"判断却记错时刻	每步更新访问时刻表
12	OPT 漏看"以后不再出现"	不再出现的优先级最高
13	FIFO 增加页框后缺页数一定减少	Belady 异常可能变多
14	Clock 扫过不清访问位	指针扫过即清零
15	局部置换能自动调整页框	只有可变分配可以
16	工作集窗口定义想当然	先确认按时间还是按次数
17	抖动判定只看缺页率	要和可用页框数、工作集大小对比
18	分区回收只合并一侧	四种邻近情况都要判断
19	动态分区分配后不重排序空闲表	每次操作后按地址重排
20	十六进制地址硬算十进制	页面为 2 的幂时直接按位对齐拆

最后再补一句关于复习节奏的体会。我第一次做内存管理大题的时候，是按照教材顺序一道一道刷的，结果刷完第三章，回头再看第二章的置换算法又忘了。后来改成按题型刷——今天只刷地址变换，明天只刷置换算法，每个题型连着做十道以上，直到能在两三分钟内判断题型并写出公式。这个方法的效率比按章节顺序刷高出很多，因为同一类题之间共享的"套路"被反复强化，而跨题型的干扰被排除了。

另外，这类题建议手写练习而不是看着答案点头。看着答案觉得"原来如此"的题目，真正动笔时大概率还是会在第一行就卡住。我自己的做法是把做错的题抄在一个本子上，只写题干关键条件和最后卡住的那一步，隔一周再做一次，能独立做出来才算过。这个笨办法帮我省下了考场上大量的犹豫时间：看到"求有效访问时间"，我的手会先写出那几个单位换算，而不是先发呆。