第 4 章 内存管理¶
依据：《操作系统概论》（2017 年版）第 4 章、配套自考大纲及附录答案。下文编号指大纲“考核内容与考核要求”；标注“自编”的算例为学习辅助，不是真题。
复习导航：大纲要求与笔记位置¶
| 大纲条目 | 层次 | 位置 | 学完应能做到 |
|---|---|---|---|
| 1.1–1.2 层次、局部性 | 识记 | 第 1 节 | 解释为何能用小容量高速存储支持大程序 |
| 2.1–2.3 链接与装入 | 领会 | 第 2 节 | 区分链接、装入、重定位 |
| 3.1–3.3 连续分配与动态分区 | 识记、简单应用 | 第 3 节 | 说明三类连续分配的原理与碎片，用 FF、NF、BF 完成分配与回收合并 |
| 4.1–4.2 页、页框、页表与地址映射 | 识记、综合应用 | 第 4 节 | 区分逻辑页和物理页框，拆地址、查页表、拼物理地址 |
| 4.3 快表（TLB） | 领会 | 第 5 节 | 说明命中、未命中与访存性能 |
| 4.4 二级分页 | 综合应用 | 第 6 节 | 拆分字段、逐级查表 |
| 4.5–4.6 分段、段页式 | 领会 | 第 7 节 | 说明地址结构、越界检查与映射 |
| 5.1–5.2 虚拟存储与请求分页硬件 | 识记、领会 | 第 8 节 | 说出定义与四个特征，说明页表项与缺页处理 |
| 5.3–5.4 页框分配 | 识记 | 第 9 节 | 说明最少页框、分配和置换范围 |
| 5.5 页面置换 | 领会 | 第 10 节 | 逐次跟踪六类算法 |
| 5.6–5.7 缺页性能、工作集与抖动 | 领会、识记 | 第 11 节 | 算有效访存时间，说明抖动的原因与预防 |
| 6.1–6.3 伙伴系统 | 领会 | 第 12 节 | 说明拆分、分配与释放合并 |
全章十二节按“分配 → 映射 → 扩充”递进：第 1–3 节铺垫存储层次、重定位与连续分区分配；第 4–7 节讲离散分配下的硬件地址变换（分页、TLB、两级页表、反置页表、分段与段页式）；第 8–11 节进入虚拟存储，围绕缺页处理、页面置换和抖动展开；第 12 节补充内核管理物理页框的伙伴系统。
本章学习目标¶
本章围绕三个问题展开：程序如何分配内存空间，逻辑地址如何转换为物理地址，以及程序不能全部装入主存时，如何利用外存实现虚拟存储。地址转换由操作系统与硬件配合完成。
先区分逻辑地址与物理地址，再区分“缺少连续空间”和“所需页面尚未装入主存”。前者可通过分页离散分配，后者需由缺页处理按需调入，必要时进行页面置换。地址切分、置换状态演进和有效访存时间都应动手推算。
1 存储层次与局部性（1.1–1.2，识记）¶
存储层次依次为寄存器 → 高速缓存（Cache）→ 内存（主存）→ 外存。靠近 CPU 的层次通常速度更快、每比特成本更高、容量更小；主存保存当前运行所需的程序和数据，外存提供较大容量。
小容量高速存储器能够发挥作用，主要依靠程序的局部性：
- 时间局部性：近期访问过的指令或数据，随后可能再次访问，如循环体和循环变量。
- 空间局部性：访问某地址后，随后可能访问相邻地址，如顺序取指、按行遍历数组。
局部性是一种常见倾向，并非保证。访问集中于近期内容或相邻位置时，缓存和按需调页通常有效；无规律地跨大范围访问时，效果可能下降。
2 链接、装入与重定位（2.1–2.3，领会）¶
一份源代码要真正跑起来，中间得过三道关：
源程序 → 编译/汇编 → 目标模块 → 链接 → 装入模块 → 装入内存 → 执行
链接将分别编译的目标模块组合起来，并解析跨模块的函数和变量引用。装入将可执行模块放入运行时地址空间。重定位则根据实际装入位置调整模块中的地址。
按地址确定或转换的时机，装入方式分为以下三类：
| 方式 | 地址何时确定/转换 | 理解要点 |
|---|---|---|
| 绝对装入 | 编译或汇编时确定物理地址 | 程序只能装入指定位置，不便于多道程序共享主存 |
| 静态重定位 | 装入时由软件一次性修改相关地址 | 无需硬件动态变换；装入后不能直接移动程序 |
| 动态重定位 | 每次访存时由硬件根据重定位寄存器转换地址 | 运行期间可改变程序的装入位置，是离散分配和虚拟存储的基础之一 |
链接也分静态和动态。静态链接在装入前将目标模块和所需库函数合成装入模块，调整相对地址并解析外部符号；动态链接则将部分工作推迟到装入时，或运行中首次调用时完成。动态库可供多个进程共享，更新单个模块时也不必重新编译整个程序。
自编例：某进程逻辑地址为 120，动态重定位基址寄存器值为 8000，硬件先核对 120 没有超出界限（段长/上限），确认合法后相加得出物理地址 \(8000 + 120 = 8120\)。
3 连续分配与动态分区（3.1–3.3，识记、简单应用）¶
早期内存管理要求一道程序在物理内存里占一整段连续空间。按用户区切不切分、分界线动不动，连续分配演进出三种做法：
| 方式 | 分配办法 | 主要问题 |
|---|---|---|
| 单一连续分配 | 除操作系统占用的系统区外，整个用户区只装一道程序 | 不能支持多道程序并发，用户区其余部分无法供其他程序使用 |
| 固定分区 | 预先把用户区切成固定块数（大小可相等也可不等），一区装一道 | 程序比分区小会留下无法利用的内部碎片；程序大于最大分区时无法装入 |
| 动态分区 | 不预先划线，进程来申请多少就从空闲区现切多少 | 反复分配回收后，分区之间夹杂大量零散小空隙，形成外部碎片 |
固定分区只需维护一张固定长度的分区说明表，记清各区大小、起址和“已分配／未分配”状态；动态分区的块数和起止位置时刻在变，得用空闲分区表或空闲分区链动态维护，链表的排序方式直接对应下面三种查找算法。
3.1 FF、NF、BF¶
| 算法 | 如何选空闲区 | 特点 |
|---|---|---|
| 首次适应 FF | 空闲链按地址递增排，每次从头找第一个放得下的区 | 查找快，高地址易保住大块空闲；低地址端会被反复切碎 |
| 循环首次适应 NF | 接着上次分配停下的位置往后找，到尾端就绕回表头 | 空闲区分布比 FF 均匀，但常把高地址的大整块提前切散 |
| 最佳适应 BF | 空闲链按容量递增排，挑能放下的最小那一块 | 每次切完剩的尾巴最小，结果攒出一堆谁也塞不进的极小外部碎片 |
自编例：空闲区按地址依次为 (100,100)、(300,50)、(500,200)，二元组代表 (起址, 长度)。现申请 40，约定从选中分区的低地址端切出：
- FF 从头扫，选中
(100,100)，切走[100,140)，原空闲区缩为(140,60)。 - BF 找最贴合的最小块，选中
(300,50)，剩(340,10)。 - NF 从上次查找结束的位置继续：若本次从第三块开始，就选中
(500,200)，剩余(540,160)。计算前应先确定上次指针停止的位置。
连续处理多次申请与释放时，每完成一步都要更新空闲表，再处理下一次请求。若切分后的剩余空间小于题设规定的最小剩余阈值，则将整块分配给该进程，不再保留单独的空闲项。
3.2 回收与合并¶
回收时可将分区写成左闭右开区间 [起址, 起址+长度)。若前一空闲区的右端点等于回收区的左端点，或回收区的右端点等于后一空闲区的左端点，就可合并对应的空闲区。只有地址相邻且都已空闲的区域才能合并。
| 回收区与空闲区关系 | 处理 |
|---|---|
| 上下都不相邻 | 插入新的空闲表项 |
| 只与前一空闲区相邻 | 增加前一区长度 |
| 只与后一空闲区相邻 | 修改后一区起址并增加长度 |
| 同时与前后相邻 | 三块合一，删除多余表项 |
自编例：现有空闲区 [100,140) 和 [180,220)，现释放 [140,180)。释放区与前后两块都相邻，因此合并为 [100,220)，总长 120，空闲表项比原先减少一条。可用“合并后空闲总长＝原空闲总长＋本次释放量”检查是否漏算边界。
4 基本分页与地址变换（4.1–4.2，识记、综合应用）¶
动态分区可能出现空闲总量足够、却没有足够大连续空间的情况。分页将进程逻辑地址空间划分为固定大小的页（页面），将物理内存划分为同样大小的页框（物理块）。各页可存入不同空闲页框，由每个进程的页表记录页号到页框号的映射。基本分页要求运行前装入全部页面；第 8 节的请求分页才允许按需调入。
分页消除了外部碎片，但最后一页可能未装满，形成内部碎片；在通常的平均估计中，浪费约为半页。页较小时，末页浪费减少，但页表增大；页较大时，页表缩小，页内碎片及一次调页带入的无用数据则可能增加。
地址变换按三步走：先按页大小 \(L\) 把逻辑地址 \(A\) 拆成页号 \(p\) 和页内偏移 \(d\)，核对页号 \(p\) 没有越过页表长度 \(N\)（合法范围 \(0 \le p < N\)），再以 \(p\) 查页表拿到页框号 \(f\)，最后拼出物理地址 \(PA\)：
页大小取 \(2^k\) 时，MMU 可直接按二进制位切分地址，无需执行整除和取余：低 \(k\) 位保留为页内偏移 \(d\)，其余高位为页号 \(p\)。取得页框号 \(f\) 后，将其放在高位、偏移 \(d\) 放在低位，两段拼接为物理地址。因此，纸面公式中的乘加并不意味着硬件必须执行乘法和加法指令。
自编例：页大小为 \(1\ \text{KB} = 1024\ \text{B}\)，逻辑地址为 \(2500\)。页表显示第 2 页映射到第 7 号页框。先拆分逻辑地址：\(2500 = 2 \times 1024 + 452\)，所以 \(p=2\)、页内偏移 \(d=452\)。再计算物理地址：\(PA = 7 \times 1024 + 452 = 7620\)。页框号是编号，计算物理地址时要先乘页大小，得到页框的起始字节地址。
把常用的两种页大小按 32 位地址摆出来对照（教材图 4-31 就是这套切位拼接的硬件画法）：
| 页大小 | 页内偏移取低位 | 页号取高位 | 本例拆分 |
|---|---|---|---|
| 1 KB = 2^10 | 低 10 位 | 高 22 位 | 2500 → 页号 2、偏移 452 |
| 4 KB = 2^12 | 低 12 位 | 高 20 位 | 00403005H → 页号 00403H、偏移 005H |
5 快表（TLB）与访存性能（4.3，领会）¶
在页表与数据均位于主存、且没有其他缓存的基本分页模型中，一次数据访问需要两次主存访问：先查页表取得页框号，再访问目标单元。快表（TLB）是 MMU 中的高速缓存，保存近期使用的页表项，以减少地址翻译的开销。
地址转换时先查 TLB：命中即可取得页框号；未命中则查主存页表，并将映射填入 TLB。注意，TLB 未命中只表示缓存中没有该映射，不等于页面不在主存。只有确认缺页后，才需要从外存调入页面。
假设单级页表在主存、先查 TLB 未命中再查主存（串行查询）且页面都在主存，设查 TLB 耗时 \(t\)、单次主存访问耗时 \(m\)、TLB 命中率为 \(h\)：
教材例 4-7 代入 \(m = 120\ \text{ns}, t = 20\ \text{ns}, h = 90\%\)，得到 \(EAT = 20 + 1.1 \times 120 = 152\ \text{ns}\)，小于不设 TLB 时的 \(240\ \text{ns}\)。
这套公式对应“先查 TLB、未命中再查一级页表”的串行路径。题目若规定 TLB 与主存可并行查询，命中耗时可能按 \(\max(t, m)\)（通常记作 \(m\)）计算；若采用两级页表，未命中时还需增加一次页表访问。应先画出题设路径，再计算各分支的耗时。
CPU Cache 缓存的是指令和数据本身，TLB 缓存的是虚页号到页框号的地址映射。不同进程的相同虚页号可能对应不同页框，因此进程切换时，需要清除不再适用的 TLB 项，或用地址空间标识（ASID）区分映射。
6 两级页表（4.4，综合应用）¶
逻辑地址空间较大时，单级页表可能占用较多内存。两级页表将页表再分一层：顶层页目录的每个目录项指向一张二级页表；未使用的逻辑地址范围无需建立对应的二级页表。
6.1 反差算例：多了一级，凭什么反而省内存¶
参数：32 位逻辑地址空间（4 GB）、页大小 4 KB、页表项 4 B。先算单级页表：
在本例的完整单级页表模型中，需要连续的 4 MB 空间，且即使进程只使用少量地址，也仍需保留完整表项。两级页表用于减少这种稀疏地址空间下的开销。
两级的账分两块：
关键是按需建表：若进程使用的 4 MB 逻辑空间恰好落在同一页目录项覆盖的范围内，只需 1 张二级页表：
4 MB 到 8 KB，差 512 倍。
两级页表节省空间的前提是逻辑地址空间稀疏。若地址空间全部使用，需要 4 KB + 1024 × 4 KB = 4 MB + 4 KB，反而比单级页表多一个页目录。它的优势在于只为已使用的地址范围建立下级页表，且每张表仅占一页，不必申请大段连续空间。
6.2 地址怎么拆、怎么查¶
以教材常见的 32 位地址 10 位页目录号 p1 | 10 位二级页号 p2 | 12 位偏移 d 为例：
- 页大小
2^12=4096 B=4 KB；逻辑地址空间2^32 B=4 GB。 - 页目录最多 1024 项，每张二级页表最多 1024 项；一张二级页表覆盖
1024×4 KB=4 MB逻辑空间。 - 页表项若为 4 B，每张二级页表占 4 KB。
查表次序是：由页目录第 \(p_1\) 项定位二级页表，再由二级页表第 \(p_2\) 项取得页框号 \(f\)。
自编例：A=00403005H，拆得 p1=1、p2=3、d=5。若目录第 1 项定位某二级页表，该表第 3 项给出页框 2AH，则 PA=2A005H。
三个字段的取法与查表次序列成表，比背公式直白（教材图 4-37、图 4-38 是这两步的图示）：
| 字段 | 取法 | 本例（A=00403005H） |
|---|---|---|
| 页目录号 p1 | A 右移 22 位 | 1 |
| 二级页号 p2 | A 右移 12 位后对 1024 取余 | 3 |
| 页内偏移 d | A 对 4096 取余 | 5 |
| 页框号 f | 页目录第 1 项定位二级页表，该表第 3 项 | 2AH |
| 物理地址 PA | f 左移 12 位再加 d | 2A005H |
无 TLB 且各级表都在内存时，二级分页一次数据访问通常要访存 3 次，依次读页目录、二级页表和目标单元。
6.3 反置页表：怎么建、怎么查¶
反置页表按物理页框建立表项，而非按各进程的逻辑页建表。物理内存有多少页框，就有多少表项；每项记录该页框所属的进程标识 PID、虚页号 VPN 及保护信息。
表的大小因此与虚拟空间、进程数都脱钩，只跟真实内存有关。4 GB 内存、4 KB 页，页框共 2^20 个，每项 4 B，整张表 4 MB，服务全系统所有进程。
反置页表按页框号排列，但地址转换提供的是 (PID, VPN)。若逐项查找，最坏需访问 2^20 个表项，代价很大。因此通常为 (PID, VPN) 建立哈希表，通过散列找到候选项，并用链地址法等方式处理冲突。
反置页表只记录当前驻留主存的页，系统还需另设结构记录非驻留页的外存位置。共享页也需额外处理：同一页框可能对应多个进程的不同 (PID, VPN)，单个表项不能直接容纳所有映射。
反置页表的建法与查法压成一张表：
| 问题 | 做法 |
|---|---|
| 表项按什么建 | 每个物理页框一项，与虚拟空间大小、进程数无关 |
| 查表方向 | 用（PID, VPN）反查页框号，与页表方向相反 |
| 怎么查得快 | 先哈希到候选表项，冲突用链地址法 |
| 缺页与共享页怎么补 | 另备外存位置登记；共享页靠额外结构串多组映射 |
7 分段与段页式（4.5–4.6，领会）¶
分页按固定大小划分地址空间，不直接体现代码、数据和栈等逻辑边界。分段则按程序的逻辑结构组织：代码段、数据段、栈段各自从 0 编址，长度由内容决定。逻辑地址表示为二维的 (段号 s, 段内偏移 d)，段表项记录物理起址 base、段长 length 及读写执行权限。
分段地址转换需要进行段内偏移越界检查：先核对段号 \(s\) 是否在段表范围内，再读取第 \(s\) 项的 base 和 length，确认偏移合法后，将基址与偏移相加。这里使用加法，与分页的按位拼接不同：
自编例：2 号段基址 6000、段长 500，访问 (2,120) 落在 [0, 500) 内，物理地址为 \(6000 + 120 = 6120\)；而访问 (2,500) 当场触发越界中断，因为段长 500 对应的合法偏移只到 499。
| 比较 | 分页 | 分段 |
|---|---|---|
| 划分依据 | 固定大小的物理管理单位 | 程序的逻辑模块 |
| 长度 | 固定（由硬件定） | 可变（由程序逻辑定） |
| 程序员视角 | 透明，一维线性地址由硬件自动切分 | 可见，二维地址显式给出段号与偏移 |
| 碎片 | 页内碎片（无外部碎片） | 段间外部碎片（无内部碎片） |
| 共享与保护 | 按页硬切，跨页边界不好对齐逻辑模块 | 按整段赋权或共享代码段，干净自然 |
段页式结合分段的逻辑组织与分页的离散分配：先将程序分段，再把每段划分为固定大小的页。逻辑地址为 (段号 s, 段内页号 p, 页内偏移 d)，先用 s 查段表取得页表起址，再用 p 查页表取得页框号，最后与 d 拼成物理地址。不设 TLB 且两类表均在主存时，一次数据访问需 3 次主存访问（段表 → 页表 → 数据）。与两级页表不同，段页式的第一层表示长度可变、独立受保护的逻辑段；两级页表只是分层索引同一分页地址空间。
8 虚拟存储与请求分页（5.1–5.2，识记、领会）¶
基本分页和基本分段要求程序全部装入主存后才能运行。虚拟存储利用局部性，先装入当前需要的部分，其余保留在外存；运行中访问未驻留的页面时，再由操作系统调入，必要时换出暂不使用的页面。因此，进程的逻辑地址空间可以大于可用物理内存，其范围仍受地址位数及外存等条件限制。
教材归纳了四个特征：多次性（分批装入）、对换性（运行中允许换入换出）、虚拟性（从逻辑上扩充内存容量）、离散性（物理存放不必连续，为前三者提供基础）。虚拟存储并未增加物理内存；若换页过于频繁，仍会严重降低性能，见第 11 节的抖动。
请求分页的页表项除页框号外，还需要管理信息：状态位（存在位）表示页面是否在主存；访问位 A 记录近期是否访问过，供置换算法参考；修改位 M（脏位）记录调入后是否被改写，干净页可直接淘汰，脏页则需先写回外存；外存地址用于定位待调入的页面。
当一条指令访问到合法但状态位为“不在主存”的页面时，软硬件按五步接力完成缺页中断处理：
- 硬件 MMU 查页表发现缺页，触发缺页异常陷入内核，保存现场。
- 内核核实访问地址合法后，从页表项或配套结构读出该页在外存的位置。
- 查看主存有无空闲页框；若已满，按置换算法挑一页淘汰，看修改位决定是否先写盘。
- 启动磁盘 I/O 把目标页读进空闲页框，当前进程阻塞让出 CPU；等磁盘中断报信读完后，改写页表（置存在位、填页框号）并同步失效或更新 TLB，唤醒该进程回就绪队列。
- 该进程再次被调度上 CPU 时，重新执行刚才引发缺页的那条指令。
缺页异常与第 2 章的普通外部中断不同：外部中断通常在指令边界处理，返回后执行下一条指令；缺页异常发生在当前指令取指或访存时，调页后需要重新执行本条指令。按本节的整条指令重启模型，若一条指令涉及多个页面，分配的页框应足以容纳这些页面，避免反复缺页而无法完成指令。
9 页框分配与调入策略（5.3–5.4，识记）¶
请求分页需确定两项策略：分给每个进程多少页框（分配策略），以及缺页置换时可从哪些进程的页框中选择（置换范围）。两者形成以下三种组合。“固定分配＋全局置换”不成立，因为从其他进程取得页框会改变各进程持有的页框数：
| 策略 | 驻留页框数量 | 牺牲页来源 |
|---|---|---|
| 固定分配、局部置换 | 装入时定死，运行期间不变 | 只能从本进程自己的驻留集里挑 |
| 可变分配、全局置换 | 运行期间随全局置换增减 | 从全系统可置换页框池里挑，被挑中者少一框、缺页者多一框 |
| 可变分配、局部置换 | 平时不变，缺页率过高或过低时由内核增减配额 | 只从本进程自己的驻留集里挑 |
大纲条文里写的“动态分配”就是教材正文说的“可变分配”，答题时认准同一个意思即可。至于初始页框怎么分，常见三种：平均分配、按进程大小成比例分配、按优先权分配（或比例加优先权折中）。
还需区分页面何时调入、从哪调入。缺页后再调入称为请求调页；利用空间局部性提前调入预计会用到的页，称为预调页。教材模型中，文件区较分散，对换区（Swap）连续分配、读写较快。若对换区足够大，可先复制程序，之后从对换区调页；若不足，则未修改页从文件区调入，修改页换出到对换区，后续再从对换区调入。
10 页面置换算法（5.5，领会）¶
页框已满且需调入新页时，系统要选择一个页面换出；替换策略会影响缺页率。大纲要求领会六种算法：
| 算法 | 淘汰依据 | 易错点 |
|---|---|---|
| OPT 最佳 | 淘汰将来最长时间不再用（或永不再用）的页 | 需要预知未来访问序列，用作理论性能对照 |
| FIFO 先进先出 | 淘汰最早装进内存的那一页 | 命中不改排队次序；有 Belady 异常（多给页框缺页次数反倒变多） |
| LRU 最近最久未使用 | 淘汰过去最长时间没被碰过的页 | 性能贴近 OPT 且无 Belady 异常，但每次命中都得更新先后次序，硬件开销大 |
| LFU 最少使用 | 淘汰累计访问次数最少的页 | 只统计次数，不考虑最近访问时间；历史高频页可能长期保留，常配合定期右移衰减 |
| 简单 CLOCK | 循环指针扫访问位 A |
装入或访问置 A=1；淘汰时从当前指针扫，见 1 清 0 放过，见 0 当场换出并把指针推向下一格 |
| 改进 CLOCK | 同时看访问位 A 和修改位 M |
宁可淘汰干净页省一次写盘，分四档优先级扫描 |
名称需要按算法定义区分：大纲中的“最近最少使用”对应按次数统计的 LFU；LRU 则是“最近最久未使用”。前者比较访问频次，后者比较距上次访问的时间。
改进型 CLOCK 按 (A, M) 区分四类页面：(0,0) 最近未用且干净，优先淘汰；其次为 (0,1)、(1,0) 和 (1,1)。教材采用两轮扫描：第一轮寻找 (0,0)，不改动 A 位；若未找到，第二轮寻找 (0,1)，并将经过页面的 A 位清 0。仍未找到时，重复上述过程，利用已更新的访问位继续选择。
教材还介绍两种改进方法：附加引用位算法为每页设置一个 8 位移位寄存器，定期右移，以访问历史近似 LRU；页面缓冲算法（PBA）保留空闲页链表和修改页链表，暂缓覆写淘汰页。若页面很快再次被访问，可直接恢复，省去读盘；修改页也可集中写回。
10.1 自编逐步例：FIFO 与 LRU¶
3 个页框初始为空，访问串 1,2,3,1,4,1,2。表中固定列顺序表示页框位置，缺包括首次装入；无空闲页框时才发生淘汰。
| 次序 | 访问 | FIFO 页框 | FIFO | LRU 页框 | LRU |
|---|---|---|---|---|---|
| 1 | 1 | 1,-,- | 缺 | 1,-,- | 缺 |
| 2 | 2 | 1,2,- | 缺 | 1,2,- | 缺 |
| 3 | 3 | 1,2,3 | 缺 | 1,2,3 | 缺 |
| 4 | 1 | 1,2,3 | 中 | 1,2,3 | 中 |
| 5 | 4 | 4,2,3 | 缺，淘汰 1 | 1,4,3 | 缺，淘汰 2 |
| 6 | 1 | 4,1,3 | 缺，淘汰 2 | 1,4,3 | 中 |
| 7 | 2 | 4,1,2 | 缺，淘汰 3 | 1,4,2 | 缺，淘汰 3 |
FIFO 缺页 6 次、置换 3 次；LRU 缺页 5 次、置换 2 次。缺页率分别为 6/7、5/7。OPT 在本串第 5 步淘汰页 3（其后不再访问），合计缺页 4 次。
10.2 状态演进表：补记淘汰顺序¶
10.1 记录的是固定页框里放了谁；选淘汰页时，还要另记一条顺序。FIFO 按装入时间排列，命中不调整；LRU 按最近访问时间排列，每次访问都把该页记为最新。更新次序只需维护管理信息，不需要搬动页框里的数据。
下面继续使用同一序列。两条顺序都从左到右表示“最早 → 最新”；页框已满且发生缺页时，淘汰左端页。
| 步骤 | 访问页 | FIFO 装入顺序 | LRU 最近访问顺序 | 本步关键动作 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 首次装入 |
| 2 | 2 | 1,2 | 1,2 | 使用空页框 |
| 3 | 3 | 1,2,3 | 1,2,3 | 空页框用尽 |
| 4 | 1 | 1,2,3 | 2,3,1 | 都命中；只有 LRU 更新次序 |
| 5 | 4 | 2,3,4 | 3,1,4 | FIFO 淘汰 1，LRU 淘汰 2 |
| 6 | 1 | 3,4,1 | 3,4,1 | FIFO 缺页并淘汰 2；LRU 命中 |
| 7 | 2 | 4,1,2 | 4,1,2 | 都缺页并淘汰 3 |
FIFO 共缺页 6 次、置换 3 次；LRU 共缺页 5 次、置换 2 次。第 4 步命中后是否更新次序，决定了第 5 步淘汰谁，也决定了第 6 步是否再次缺页。
11 有效访存时间、工作集与抖动（5.6–5.7，领会、识记）¶
有效访存时间（EAT）会受到缺页率 \(p\) 的影响。设页面在内存时的正常访问时间为 \(m\)，缺页处理的总时间 \(F\) 已包含页面调入后的那次访存，则
若题目给出的缺页开销 \(S\) 不包含最后一次访存，则使用 \(EAT = m + pS\)。
自编例：主存访问时间 \(m = 100\ \text{ns}\)，缺页总耗时 \(F = 10\ \text{ms} = 10\,000\,000\ \text{ns}\)。缺页率为十万分之一（\(p = 10^{-5}\)）时，
结果是正常访存时间的两倍。原因是一次缺页处理约等于十万次正常访存；即使缺页率很低，也会明显拉高平均时间。
进程需要多少页框，可用工作集 \(W(t, \Delta)\) 估计。Denning 将它定义为时刻 \(t\) 之前、长度为 \(\Delta\) 的窗口内访问过的不同页面集合；工作集大小 \(|W(t, \Delta)|\) 是集合中的页面数。窗口可按时间或最近访问次数定义，以题设为准。例如，最近 5 次访问为 1, 2, 1, 3, 2 时，工作集为 {1, 2, 3}，大小为 3，窗口长度为 5。
若分配的页框不足以容纳进程的活跃工作集，页面会频繁换入换出，使进程大部分时间用于调页、CPU 利用率下降，这就是抖动（颠簸）。若系统因 CPU 空闲而继续增加进程，可能进一步减少每个进程的可用页框，加重抖动。控制方法包括局部置换、按工作集或缺页率调整页框、挂起部分进程释放内存，以及增加物理内存。
12 伙伴系统（6.1–6.3，领会）¶
用户进程的页面可以离散映射，但内核申请某些缓冲区等结构时可能需要连续的物理页框。Linux 等内核使用伙伴系统（Buddy System）管理空闲空间，将 \(2^k\) 个连续页框组成的块称为 \(k\) 阶块，按阶分别维护空闲链表。
申请 \(n\) 个页框时，先向上取整到可容纳它的最小 \(2^k\)。若 \(k\) 阶链表有空闲块，直接分配；否则从 \(k+1\) 阶或更高阶取得空闲块，逐级对半拆分为 \(k\) 阶块。分配其中一块，另一块加入 \(k\) 阶空闲链表。
自编例：初始有一块 16 页框空闲区，现申请 3 页框，需分配 \(2^2 = 4\) 页框。先将 16 拆为 8 + 8，再将其中一个 8 拆为 4 + 4。分配一个 4，其中 1 页框形成内部碎片；剩余一个 4 和一个 8 分别加入对应阶的空闲链表。
释放时，只有由同一 \(2^{k+1}\) 上级块拆出的两个空闲伙伴块才能合并，大小相同且相邻还不够。设块大小为 \(b=2^k\)，对齐的起始页框号为 \(x\)，伙伴起址为 x XOR b。
例如，[0, 4) 和 [4, 8) 的起址满足 \(0\oplus4=4\)，因此可合并为 [0, 8)。[4, 8) 与 [8, 12) 虽然相邻，但分别属于 [0, 8) 和 [8, 16) 两个上级块；\(4\oplus4=0\)，不等于 8，不能合并。教材中的阶数上限、页大小和 Linux 结构定义属于特定版本实例；本节重点是拆分规则和用异或判断伙伴块。
13 考核要求¶
本章大纲分 6 组。识记包括存储层次与局部性（1.1–1.2）、连续分配与固定分区（3.1–3.2）、分页概念（4.1）、虚拟存储定义（5.1）、页框分配策略（5.3–5.4）和抖动（5.7）。领会包括链接装入与重定位（2.1–2.3）、TLB（4.3）、分段与段页式（4.5–4.6）、缺页中断处理（5.2）、页面置换与 EAT 计算（5.5–5.6），以及伙伴系统（6.1–6.3）。
简单应用和综合应用涉及三类计算：动态分区的分配与回收（3.3）、基本分页地址映射（4.2）和两级页表地址映射（4.4）。练习时应能画表并完成十六进制地址切分。
14 教材本章习题¶
题目取自教材第 4 章“思考题与练习题”（共 16 题），答案取自教材附录“部分习题参考答案”（全部收录）。
14.1 单项选择题¶
1. 关于操作系统内存管理的功能，下列叙述错误的是【 】。
答案与解析
参考答案： C。内存管理的作用之一是让程序使用逻辑地址（虚拟地址）访问内存。逻辑地址到物理地址的转换由软硬件协同完成，物理地址并不直接暴露给程序。
2. 在基于分页的虚拟存储管理系统中，页表项增加了修改位字段，下列程序中，需要使用这个字段的是【 】。
答案与解析
参考答案： B。修改位标记该页调入后是否被写过。选择换出页时据此判断是否必须先写回外存；未被修改的页可直接丢弃。
3. 多道程序环境下，操作系统分配 CPU 资源的基本单位是【 】。
答案与解析
参考答案： B。多道程序环境中进程是资源分配与独立运行的基本单位；作业是面向用户的提交单位，程序是静态的。
4. 采用二级分页的存储管理系统中，若分页逻辑地址用 32 位表示，其中高 10 位表示页目录号 p1，中间 10 位表示页号 p2，低 12 位表示页内偏移，则一个进程的逻辑地址空间大小最大为【 】。
答案与解析
参考答案： A。逻辑地址共 32 位，无论怎样划分为 p1、p2、d，可寻址空间都是 2³²＝4 GB。不要误按页内偏移 12 位答成 4 KB。
5. 在一个实际系统中，进行页置换时，通常选择换出的页是【 】。
答案与解析
参考答案： C。D 是理论最优（OPT）的判据，实际系统无法预知将来。实际做法综合访问位与修改位，优先淘汰近期既未访问又未修改的页，同时避免写回开销。
14.2 填空题¶
6. 连续内存管理方式有 3 种，即___、___和___。
答案与解析
参考答案： 单一连续区分配；固定分区分配；动态分区分配。
7. CPU 的页表寄存器用于存放 ___ 进程的页表起始地址。
答案与解析
参考答案： 当前。
8. LRU 置换算法选择的换出页是 ___ 的页。
答案与解析
参考答案： 最近最久未访问。
9. 快表中存放的内容是___。
答案与解析
参考答案： 最近被访问过的页表项。
10. 在分段存储管理系统中，段表项中包含的基本内容有 ___ 和 ___。
答案与解析
参考答案： 段基址；段大小。教材附录另列出“段号”，但段号用于索引段表，本身不作为段表项的基本内容保存。
11. 虚拟存储管理系统的特征有多次性、___、___和___。
答案与解析
参考答案： 离散性；对换性；虚拟性。
14.3 简答题¶
12. 静态链接程序完成什么功能？
答案与解析
参考答案： 把若干目标模块组合成一个完整的装入模块，同时处理模块组合引起的相对地址变化和外部符号引用。前一项工作是重定位，后一项是符号解析。
13. 请说明分页存储管理的基本原理。
答案与解析
参考答案： 把逻辑地址空间划分为大小相等的页，把物理内存划分为同样大小的页框。页可以离散地放入任意页框，系统用页表把页号转换为页框号。页内偏移保持不变，与页框号拼接成物理地址，从而避免连续分配的外部碎片。
14. 什么是抖动？抖动产生的原因是什么？
答案与解析
参考答案： 抖动是进程频繁换页、用于换页的时间超过有效执行时间的状态。原因通常是分配给进程的页框数不足以容纳其当前工作集，使刚换出的页很快又被访问。可通过减少并发度、调整页框分配或增加内存缓解。
15. 请说明分段存储管理的原理。
答案与解析
参考答案： 按程序的逻辑单位（如代码段、数据段、栈段）划分地址空间，每段长度可变。系统先以段号查段表，读取段基址和段长，检查段内偏移是否越界；合法时以段基址加偏移得到物理地址。分段便于共享与保护，但会产生外部碎片。
14.4 综合应用¶
16. 初始空闲链中第一个空闲区起址 20 KB、大小 10 KB；第二个起址 50 KB、大小 100 KB；第三个起址 300 KB、大小 10 KB。分别画出释放条件（1）（2）（3）后的空闲链（教材图 4-57 至图 4-60）。
答案与解析
参考答案： 三种情形的结果见教材附录图 A-1a 至 A-1c。作答时先读出各图中被释放区的起址与长度，再按第 3.2 节判断能否合并。与前一空闲区末址相接，就并入前者；与后一空闲区首址相接，就并入后者；两侧都相接，三者合并为一块；都不相接，则作为新空闲区按地址插入链中。三个释放条件的具体数值以原图为准。第 3.2 节另给出文字数据完整的合并例。
15 闭卷复习与跨章联系（补充）¶
一、闭卷自答（合上书逐题口述）
- 存储层次与局部性，为什么能让小容量高速存储支撑大程序？
- FF、NF、BF 各怎么选空闲区？回收时哪几种情况要合并？
- 逻辑地址怎么切成页号和页内偏移，物理地址怎么拼？TLB 命中率怎么进公式？
- 二级页表为什么可能更省？地址怎么拆、目录和页表怎么查？
- 反置页表按什么建、怎么查？虚拟存储四个特征与缺页处理分几步？
- 六种置换算法各依据什么？FIFO 的异常在哪？伙伴系统怎么拆、怎么合并？
二、本章易错
- 只有前一区的终点等于后一区的起点，两个区间才在物理地址上相邻（第 3.2 节）。
- TLB 没命中不等于缺页：缺的只是地址翻译的缓存项，页通常还在内存里（第 5 节）。
- 两级页表省内存的前提是地址空间稀疏；全部用满时反而多出一个页目录（第 6.1 节）。
三、本章骨架
| 层次 | 回答什么 | 所在节 |
|---|---|---|
| 放哪儿 | 连续分配、分区与页框 | 第 1–4 节 |
| 怎么翻 | 分页、分段、段页式、TLB、二级页表、反置页表 | 第 4–7 节 |
| 按需调页 | 虚拟存储、缺页、页面置换、工作集 | 第 8–11 节 |
| 分配物理块 | 伙伴系统的拆分与合并 | 第 12 节 |
四、跨章指路
- 拥有独立地址空间的进程实体与缺页阻塞后的三态切换，见第 2 章。
- 文件读写要经过本章的地址映射才能落进物理内存缓冲区（见第 5 章）；而一次缺页中断到底要等多少毫秒，取决于磁盘寻道调度与缓冲管理（见第 6 章）。
- 见《计算机组成原理》第 5 章：那边讲 MMU、TLB 与 CPU Cache 协同工作的硬件通路；这边讲页框分配、页面置换策略与进程隔离。