第 4 章 内存管理¶
依据：本地《操作系统概论（2017年版）》第四章、书前大纲第四章“考核内容与考核要求”、附录部分习题答案。条目编号按考核要求；例题除明确标注教材外均为自编。计算中 KB、MB、GB 按 1024 进位，地址和页号从 0 开始。
复习导航¶
| 大纲条目 | 层次 | 学习目标与位置 |
|---|---|---|
| 1.1—1.2 层次、局部性 | 识记 | 第 1 节：解释为何能用小容量高速存储支持大程序 |
| 2.1—2.3 链接与装入 | 领会 | 第 2 节：区分链接、装入、重定位 |
| 3.1—3.2 单一连续、固定分区 | 识记 | 第 3 节：原理、数据结构和碎片 |
| 3.3 动态分区 | 简单应用 | 第 3 节：FF、NF、BF 分配与回收合并 |
| 4.1 页、页框、页表 | 识记 | 第 4 节：区分逻辑页和物理页框 |
| 4.2 分页地址映射 | 综合应用 | 第 4 节：拆地址、查页表、拼物理地址 |
| 4.3 TLB | 领会 | 第 5 节：命中、未命中与性能 |
| 4.4 二级分页 | 综合应用 | 第 6 节：拆分字段、逐级查表 |
| 4.5—4.6 分段、段页式 | 领会 | 第 7 节：地址结构、越界检查、映射 |
| 5.1 虚拟存储 | 识记 | 第 8 节：定义与四个特征 |
| 5.2 请求分页硬件 | 领会 | 第 8 节：页表项、缺页异常处理 |
| 5.3—5.4 页框分配 | 识记 | 第 9 节：最少页框、分配和置换范围 |
| 5.5 页面置换 | 领会 | 第 10 节：逐次跟踪六类算法 |
| 5.6 缺页性能、工作集 | 领会 | 第 11 节：计算有效访存时间 |
| 5.7 抖动 | 识记 | 第 11 节：原因与预防 |
| 6.1—6.3 伙伴系统 | 领会 | 第 12 节：拆分、分配、释放合并 |
程序用逻辑地址访问指令和数据，由操作系统与硬件共同转换为物理地址。内存分配方式决定程序如何存放，地址变换机制决定一次访问如何完成。虚拟存储则利用局部性，只把当前需要的部分留在主存，用调页和置换管理有限的物理空间。
1 存储层次与局部性（1.1—1.2）¶
典型层次是寄存器 → 高速缓存 → 主存 → 外存。越靠近 CPU，通常速度越快、单位容量成本越高、容量越小。主存保存正在执行的程序和数据；外存提供容量，访问速度较慢。
时间局部性：刚访问过的信息，近期可能再次访问，例如循环体。空间局部性：访问某地址后，近期可能访问其邻近地址，例如顺序执行指令、遍历数组。由于访问往往集中在少量近期使用或位置相邻的内容上，缓存和按需调页能够减少对慢速存储器的访问。其效果取决于程序实际的访问序列。
2 链接、装入与重定位（2.1—2.3）¶
源程序 → 编译/汇编 → 目标模块 → 链接 → 装入模块 → 装入内存 → 执行
链接解决模块间如何组合、外部符号引用如何对应；装入把可执行内容放入内存；重定位使地址与实际存放位置一致。
| 方式 | 地址何时确定/转换 | 理解要点 |
|---|---|---|
| 绝对装入 | 装入前已知实际位置 | 地址已确定，装入位置受限 |
| 静态重定位 | 装入时一次修改有关地址 | 运行中通常不能随意移动；移动需重新处理地址 |
| 动态重定位 | 执行时由硬件完成映射 | 程序保留逻辑地址，便于运行中移动和离散存放 |
静态链接在装入前组合目标模块，修改各模块的相对地址，并把外部调用符号替换为相应的连接地址。动态链接则把部分链接工作延迟到装入或运行时，便于共享库和更新模块。链接处理模块之间的引用关系，重定位处理地址与存放位置的对应关系。
自编例：某逻辑地址 120，动态重定位基址为 8000，则物理地址为 8120；还必须先确认逻辑地址在允许的范围内。
3 连续分配与动态分区（3.1—3.3）¶
连续分配要求一个程序占据一段连续的物理内存。单一连续分配、固定分区和动态分区的区别，在于用户区如何划分，以及分区是否随请求改变。
| 方式 | 分配办法 | 主要问题 |
|---|---|---|
| 单一连续分配 | 系统区之外的用户区供一个用户程序使用 | 难以支持多道程序充分利用内存 |
| 固定分区 | 预先划成固定数目、大小相等或不等的分区 | 分区内部未用空间形成内部碎片；大程序可能放不进任何分区 |
| 动态分区 | 按请求从空闲区切分 | 分配回收后产生分散的小空闲区，即外部碎片 |
固定分区可用分区说明表记录分区大小、起址、状态。动态分区用空闲分区表或链记录起址、大小等；链的排序规则影响查找算法。
3.1 FF、NF、BF¶
| 算法 | 如何选空闲区 | 特点 |
|---|---|---|
| 首次适应 FF | 按地址递增，从表头找第一个足够大的空闲区 | 查找较直接，低地址处容易留下小碎片 |
| 循环首次适应 NF | 从上次查找结束处继续，必要时循环 | 避免每次集中扫描表头，可能消耗高地址大块 |
| 最佳适应 BF | 从所有足够大的分区中选择最小者 | 本次剩余小，容易产生难利用的极小碎片 |
自编例：空闲区按地址依次为 (100,100)、(300,50)、(500,200)，二元组为“起址、长度”。申请 40，从选中区低地址分配。
- FF 选
(100,100)，剩(140,60)。 - BF 选
(300,50)，剩(340,10)。 - NF 若本次从第三个区开始，选
(500,200)，剩(540,160)。因此，NF 的分配结果还取决于本次查找的起点。
连续多次请求时，每一步都要先更新空闲表，再执行下一步。若剩余空间小到不值得建立独立空闲区，是否整块分配按题设的最小剩余阈值处理。
3.2 回收与合并¶
把分区表示为半开区间 [起址, 起址+长度)。只有前一区的终点等于后一区的起点，两个区间才在物理地址上相邻。
| 回收区与空闲区关系 | 处理 |
|---|---|
| 上下都不相邻 | 插入新的空闲表项 |
| 只与前一空闲区相邻 | 增加前一区长度 |
| 只与后一空闲区相邻 | 修改后一区起址并增加长度 |
| 同时与前后相邻 | 三块合一，删除多余表项 |
自编例：空闲 [100,140) 和 [180,220)，释放 [140,180)。合并后得到 [100,220)，长度为 120，空闲总量应等于原空闲总量加本次释放量。
4 基本分页与地址变换（4.1—4.2，综合应用）¶
动态分区可能出现空闲总量足够、却没有足够大连续空间的情况。分页将程序和内存划分为等长单位，使程序能够利用分散的空闲页框。
页是逻辑地址空间中的等长单位；页框/物理块是内存中的等长单位，两者大小相同。进程的各页可以存入不连续页框。页表记录本进程页号到页框号的映射。基本分页通常要求程序的页全部装入后运行；请求分页允许只装入一部分。
分页主要消除外部碎片，但最后一页可能未装满而产生内部碎片。页较小可减少页内浪费，却需要更多页表项；页较大可减小页表，但可能增加无用数据调入量。
页大小 L，逻辑地址 A
页号 p = A // L
页内偏移 d = A % L
检查 p 是否在页表范围内；查得页框号 f
物理地址 PA = f × L + d
若页大小 L=2^k，地址低 k 位为偏移，其余高位为页号。映射只改变页号对应的页框号，页内偏移保持不变。若页表长度表示表项数 N，合法页号是 0≤p<N。
自编例：页大小 1 KB，逻辑地址 2500，页表中第 2 页在第 7 页框。2500=2×1024+452，故 PA=7×1024+452=7620。7 是页框编号，乘以页大小才是该页框的物理起址。
5 快表 TLB 与访存性能（4.3）¶
TLB 是保存近期页表项的专用快速缓存。命中时直接得到页框号；未命中时查内存页表，并把映射补入 TLB。TLB 未命中只说明快表没有该项，页仍可能在主存；缺页是所需页不在主存。
假设单级页表在内存、串行查 TLB、不缺页，TLB 访问时间为 t，内存访问时间为 m，命中率为 h：
命中：t + m
未命中：t + 2m
EAT = h(t+m) + (1-h)(t+2m) = t + (2-h)m
教材例 4-7：m=120 ns，t=20 ns，h=90%，得 EAT=152 ns；无 TLB 需 240 ns。该公式以串行查询单级页表为前提；并行查询或多级页表需要根据各自的访问路径计算。
进程切换可能留下旧进程映射，可刷新 TLB 或在条目中附地址空间标识 ASID。TLB 缓存的是地址映射信息，与缓存程序数据的高速缓存用途不同。
6 两级页表（4.4，综合应用）¶
当逻辑地址空间扩大时，单级页表会占用较多空间。两级页表把页表本身分页，再用页目录定位各张二级页表。未使用的逻辑地址区域可以不建立对应二级页表，避免要求整张页表连续驻留。
以教材常见的 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。
p1 = A // 2^22
p2 = (A // 2^12) % 1024
d = A % 4096
页目录[p1] → 二级页表位置
二级页表[p2] → 页框号 f
PA = f × 4096 + d
自编例：A=0x00403005，拆得 p1=1、p2=3、d=5。若目录第 1 项定位某二级页表，该表第 3 项给出页框 0x2A，则 PA=0x2A005。
无 TLB 且各级表都在主存时，二级分页一次数据访问通常要访存 3 次。三次访问依次读页目录、二级页表和目标单元。
教材还介绍了反置页表。它改为按物理页框建立表项，通过进程标识与页号寻找映射，从另一角度控制页表规模；这与按进程逻辑页建表的方向相反。
7 分段与段页式（4.5—4.6）¶
分页采用固定大小的管理单位。分段依据程序的逻辑结构划分空间，如代码段、数据段和栈段，各段长度可以不同。逻辑地址是 (段号 s, 段内偏移 d)，段表项保存段基址、段长以及保护等信息。
检查段号 s 合法
查段表取得 base 和 length
检查 0 ≤ d < length
PA = base + d
自编例：段 2 基址 6000、段长 500，地址 (2,120) 映射为 6120；(2,500) 越界，因为段长 500 时最大合法偏移为 499。
| 比较 | 分页 | 分段 |
|---|---|---|
| 划分依据 | 固定大小的管理单位 | 程序逻辑意义 |
| 长度 | 固定 | 可变 |
| 程序员视角 | 通常透明，线性地址可自动拆分 | 以段号和偏移表示逻辑单位 |
| 碎片 | 页内碎片 | 段间外部碎片 |
| 共享与保护 | 以页为单位 | 易按逻辑模块实施 |
段页式结合了两种方法：先按逻辑单位分段，再对每段分页。逻辑地址为 (段号 s, 段内页号 p, 页内偏移 d)。地址变换先查段表取得该段页表的位置，再查页表取得页框号；页内偏移直接相加。无 TLB、表均在主存且无缺页时，通常也是 3 次访存。段页式的第一层描述逻辑段，与二级分页中纯粹拆分页号的页目录意义不同。
8 虚拟存储与请求分页（5.1—5.2）¶
基本分页要求运行前装入程序的全部页。虚拟存储要解决的是程序大于可用主存的情况。它只把当前需要的部分装入主存，其余留在外存，运行中按需调入、必要时换出；由此提供的逻辑地址空间可以大于实际分配的主存。
四个特征：多次性（分多次装入）、对换性（运行中可换入换出）、虚拟性（逻辑容量可超过实分主存）、离散性（物理位置可不连续）。它依赖地址变换、外存后援和局部性；这不等于可以无限扩大物理内存。
请求分页的页表项除页框号外，还需驻留/存在状态、访问位、修改位、外存位置等。访问位帮助判断近期使用情况；修改位决定淘汰时是否需要写回。页不在主存时，页框号不能当作有效主存映射使用。
访问合法但尚未驻留的页时，系统需要完成以下缺页处理：
- 硬件检查页表发现页不在内存，产生缺页异常，保存必要现场。
- 系统验证访问是否合法，定位该页的外存副本。
- 若无空闲页框，选择牺牲页；脏页先写回，干净页通常不必写回。
- 调入所需页，等待 I/O 的进程阻塞；I/O 完成后更新页表和相关 TLB 信息。
- 恢复进程，重新执行引起缺页的指令。
一次指令可能访问多个页，所需最少页框数与指令格式、寻址方式和体系结构有关。缺页异常与当前指令的访存操作有关，可以发生在指令执行期间。这与教材中在指令结束后检查外部中断的模型不同。
9 页框分配与调入策略（5.3—5.4）¶
请求分页需要同时确定进程可占用多少页框，以及缺页时可以从哪些页框中选择换出对象。前者属于分配策略，后者限定置换范围。
| 策略 | 驻留页框数量 | 牺牲页来源 |
|---|---|---|
| 固定分配、局部置换 | 预先给定，运行中保持 | 本进程驻留集 |
| 可变分配、全局置换 | 可变化 | 全局可置换页框 |
| 可变分配、局部置换 | 可按缺页情况调整 | 置换通常限定本进程 |
大纲用“动态分配”描述后两类，教材正文用“可变分配”，复习时对应理解。页框可以平均分配、按进程大小成比例分配或结合优先权分配。
请求调页在缺页时调入；预调页在使用前预计并调入。调入位置可能来自对换区或文件所在区域。调入策略决定装入的时机和来源，置换算法决定没有空闲页框时换出哪一页。
10 页面置换算法（5.5）¶
置换范围确定后，还需要选择具体的换出页。不同算法使用的信息不同：FIFO 依据装入先后，LRU 依据最近访问时间，LFU 依据访问次数；CLOCK 则利用访问位等信息近似判断页面的使用情况。
| 算法 | 淘汰依据 | 易错点 |
|---|---|---|
| OPT 最佳 | 未来最久才访问，或以后不再访问 | 需未来信息，主要作为比较基准 |
| FIFO | 最早装入的页 | 命中不改变入队先后；增加页框可能反而增加缺页 |
| LRU | 过去最长时间未访问 | 每次命中也更新最近使用关系 |
| LFU 最少使用 | 近期使用次数最少 | 比较次数而非最近一次访问时间；可用衰减避免旧热点长期滞留 |
| 简单 CLOCK | 访问位与循环指针 | A=1 清零再看下一页，A=0 选中 |
| 改进 CLOCK | 访问位 A 与修改位 M | 优先近期未访问且未修改的页 |
大纲“最近最少使用”一项对应教材 LFU 的按次数统计。LRU 是“最近最久未使用”，两者中文名称相近，含义不同，不能混用。
简单 CLOCK：访问页时置 A=1；置换时从指针开始，遇 1 清零、遇 0 换出。因此，跟踪该算法时需要同时记录指针位置、各页 A 位及置换后的指针移动规则。
改进 CLOCK 的四类为 (0,0)、(0,1)、(1,0)、(1,1)。教材给出的过程是先扫描寻找 (0,0)，本轮不改 A；未找到则扫描寻找 (0,1)，并把经过页的 A 清零；再失败则重复。它同时考虑近期使用情况和写回代价。由于扫描会修改访问位，最终结果取决于扫描顺序和状态变化。
附加引用位用若干位记录访问历史并衰减；页缓冲算法把换出页分入干净页链和修改页链，尽量保留可复用内容、集中处理写回。这两项用于补充理解教材。
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 次。
11 有效访存时间、工作集与抖动（5.6—5.7）¶
设缺页率为 p，正常访存耗时 m，一次缺页路径的总耗时为 F，则 EAT=(1-p)m+pF。若题目给的是正常访问之外的额外缺页开销 S，则 EAT=m+pS。两个公式的区别在于，缺页耗时是否已经包含重启后的访问。
自编例：m=100 ns，F=10 ms=10,000,000 ns，p=10^-5，则 EAT=199.999 ns≈200 ns。缺页率只有十万分之一，平均访问时间却接近翻倍，因为磁盘开销远大于主存访问。
工作集 W(t,Δ) 是最近一段窗口内访问过的页集合，不是访问次数。自编例：最近 5 次访问为 1,2,1,3,2，工作集 {1,2,3}，大小为 3。
抖动是进程频繁换页、系统把大量时间花在调页上的现象。驻留集不足以覆盖活跃工作集时容易出现；若此时一味增加多道程序度，可能让可用页框更紧张。预防可采用局部置换限制相互影响、工作集或缺页率控制、挂起部分进程降低并发负荷、增加可用内存等。虚拟内存解决逻辑容量问题，不能消除真实内存不足的性能代价。
12 伙伴系统（6.1—6.3）¶
伙伴系统按 2^k 个连续页框组织空闲链。申请时向上取整到能够容纳请求的最小阶；该阶无空闲块，就从更大阶取得一块，反复平分。释放时检查同阶伙伴是否空闲，符合条件则合并并递归向上。
自编例：只有一个 16 页框空闲块，申请 3 页框，实际取 4 页框。拆分 16→8+8→4+4+8，分配一个 4，余下一个 4 和一个 8；已分配块中有 1 页框未利用。
两块必须大小相同、物理相邻，且共同来自同一个上阶块，才能成为伙伴。若以页框号表示同阶块起点 x、块大小 b，则伙伴起点可用 x XOR b 求出（要求按 b 对齐）。例如大小 4 的 [0,4) 与 [4,8) 可以合并。[4,8) 与 [8,12) 虽相邻，却不是伙伴。教材列出的阶数、页大小和内核结构例子属于书中版本，不当作所有 Linux 版本的固定配置。
13 考核要求¶
本章 6 条考核条目中，1.1—1.2、2.1—2.3、3.1—3.2 属识记。3.3 动态分区与第四章后半的置换算法属简单应用。4.1—4.2 基本分页与地址变换、4.4 两级页表属综合应用。
本章重点为分页存储管理、分段存储管理、段页式存储管理的实现原理及其地址变换过程；虚拟存储管理系统的定义；基于分页的虚拟存储管理系统实现的原理。难点为分页存储管理的基本原理、二级分页系统的地址映射。
14 教材本章习题¶
题目取自教材第四章“思考题与练习题”，答案依据教材附录“部分习题参考答案”第四章。
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 填空题¶
1. 连续内存管理方式有 3 种，即、和___。
答案与解析
单一连续区分配；固定分区分配；动态分区分配。
2. CPU 的页表寄存器用于存放 ___ 进程的页表起始地址。
答案与解析
当前。
3. LRU 置换算法选择的换出页是 ___ 的页。
答案与解析
最近最久未访问。
4. 快表中存放的内容是___。
答案与解析
最近被访问过的页表项。
5. 在分段存储管理系统中，段表项中包含的基本内容有 ___ 和 ___。
答案与解析
段基址；段大小。教材附录另列出“段号”，但段号用于索引段表，本身不作为段表项的基本内容保存。
6. 虚拟存储管理系统的特征有多次性、、和___。
答案与解析
对换性；虚拟性。
14.3 简答题¶
1. 静态链接程序完成什么功能？
答案与解析
把若干目标模块组合成一个完整的装入模块，同时处理模块组合引起的相对地址变化和外部符号引用。前一项工作是重定位，后一项是符号解析。
2. 请说明分页存储管理的基本原理。
答案与解析
把逻辑地址空间划分为大小相等的页，把物理内存划分为同样大小的页框。页可以离散地放入任意页框，系统用页表把页号转换为页框号。页内偏移保持不变，与页框号拼接成物理地址，从而避免连续分配的外部碎片。
3. 什么是抖动？抖动产生的原因是什么？
答案与解析
抖动是进程频繁换页、用于换页的时间超过有效执行时间的状态。原因通常是分配给进程的页框数不足以容纳其当前工作集，使刚换出的页很快又被访问。可通过减少并发度、调整页框分配或增加内存缓解。
4. 请说明分段存储管理的原理。
答案与解析
按程序的逻辑单位（如代码段、数据段、栈段）划分地址空间，每段长度可变。系统先以段号查段表，读取段基址和段长，检查段内偏移是否越界；合法时以段基址加偏移得到物理地址。分段便于共享与保护，但会产生外部碎片。
14.4 综合应用¶
教材原题：初始空闲链中第一个空闲区起址 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 闭卷复习与跨章联系（补充）¶
本章的应用练习包括分页、二级分页、分段和段页式的地址变换，以及页面置换过程和有效访存时间计算。练习时需明确地址字段、查表次序和时间单位，并区分题目采用的访问路径与开销定义。
第 2 章的进程在这里表现为拥有独立地址空间的实体。第 5 章的文件读写要经过本章的地址映射，才能落到物理内存。一次缺页处理的实际耗时，则由第 6 章的缓冲与磁盘调度决定。与计算机组成原理第 5 章对照：那边讲地址转换的硬件路径与 Cache 协作；这边讲分配、置换策略与进程隔离。