第 3 章 内存管理（连续分配 · 分页分段 · 虚拟内存）
本章地位：内存管理是 408 操作系统部分分值最重、计算题最密集的一章：地址翻译（给逻辑地址算物理地址）、页表 / 多级页表大小、TLB 有效访问时间、页面置换缺页次数，都是可以精确到「代数值验证」的硬计算；同时碎片、重定位、抖动等概念辨析几乎每年都有选择题。主线只有一条：程序怎么装进内存 → 怎么把逻辑地址变成物理地址 → 内存不够用时怎么办。抓住这条主线，十几种零散概念就都挂得上钩。
| 考点 | 常考题型 | 热度 | 本章位置 |
|---|---|---|---|
| 重定位（静态 / 动态）与内存保护 | 选择题 | ★★★ | 3.1 |
| 动态分区四种分配算法、碎片辨析 | 选择 / 大题 | ★★★★ | 3.2 |
| 分页地址翻译、页表与多级页表大小 | 大题（几乎必考） | ★★★★★ | 3.3 |
| 快表 TLB 与有效访问时间 EAT | 计算题 | ★★★★ | 3.3 |
| 分段越界判断、分页 vs 分段、段页式 | 选择题 | ★★★ | 3.4 |
| 缺页中断流程与性能计算 | 选择 / 计算 | ★★★★ | 3.5 |
| 页面置换算法（含 Belady 异常、改进 CLOCK） | 大题（几乎必考） | ★★★★★ | 3.5 |
| 页面分配策略、抖动与工作集 | 选择题 | ★★★ | 3.5 |
3.1 内存管理概念与程序装入
- 内存空间的分配与回收：操作系统记录哪些内存空闲（数据结构：空闲分区表 / 空闲分区链 / 位图 / 页框链），按需分配给进程，回收时合并相邻空闲区；
- 地址转换（重定位）：把程序中的逻辑地址翻译成物理地址；
- 内存保护：保证各进程在自己的地址空间内运行，互不越界干扰；
- 内存扩充：借助覆盖、交换、虚拟存储技术，让「小内存」跑「大程序」。
3.1.1 逻辑地址与物理地址
② 「从 0 开始编址」意味着题目给十进制逻辑地址时，页号 = 地址 ÷ 页大小（取整），页内偏移 = 余数——先拆后查，顺序不能反（见 3.3）。
3.1.2 三种装入方式与重定位
源程序要经过编译（.obj）→ 链接（.exe，形成完整逻辑地址空间）→ 装入（映射到物理内存）三步才能运行。按「什么时候做地址转换」分三种装入方式：
| 装入方式 | 何时重定位 | 程序能否移动 | 适用场景 |
|---|---|---|---|
| 绝对装入 | 编译时（程序中直接写死物理地址） | 不能 | 单道环境，编译时已知程序将放到何处 |
| 可重定位装入（静态重定位） | 装入时一次性全部转换 | 装入后不能再移动 | 早期多道批处理，需连续分配一整块 |
| 动态运行时装入（动态重定位） | 运行时逐条转换（借助重定位寄存器） | 可以移动，还可请求调入更多内容 | 现代 OS，是虚拟内存的前提 |
下列关于地址重定位的叙述中，错误的是（ ）
A. 静态重定位在程序装入时完成地址变换，装入后程序不能在内存中移动
B. 动态重定位需要重定位寄存器的支持，程序运行期间可以在内存中移动
C. 采用动态重定位的系统中，进程的物理地址在装入时就已全部确定
D. 动态重定位是实现虚拟存储器的基础之一
查看解答
C。逐项分析：
A 对：静态重定位装入时一次改完所有地址，之后若移动，已改好的地址全部作废，所以不能再移动；
B 对：动态重定位执行时才做「逻辑地址 + 重定位寄存器」，移动程序后只需修改寄存器内容，程序代码不动；
C 错：动态重定位下物理地址在每条指令执行时才实时算出，装入时并不确定——这正是程序可移动、可部分装入的原因；
D 对：虚拟内存「先调入一部分即可运行」依赖运行中继续调入并重定位，静态重定位做不到。
判断正误：(1) 逻辑地址就是物理地址经过编译后的另一种写法；(2) 每个进程的逻辑地址空间都从 0 开始；(3) 采用静态重定位时，进程运行中仍可申请再移动到更大的空闲区。
查看答案
(1) 错：两者是不同空间的概念，逻辑地址面向程序（相对地址），物理地址面向存储器（绝对地址），需重定位建立映射；
(2) 对：各进程逻辑地址空间独立，都从 0 编址，所以不同进程中同一个逻辑地址对应不同物理单元；
(3) 错：静态重定位装入后不能移动，想移动只能靠动态重定位。
3.1.3 内存保护的两种实现
- 上、下限寄存器：存放进程物理地址空间的上限与下限。访存时检查：下限 ≤ 物理地址 ≤ 上限，越界则产生越界中断（陷入异常）；
- 重定位寄存器 + 界地址寄存器：重定位寄存器存物理起始地址（基址），界地址寄存器存逻辑地址空间长度（限长）。访存时先判 逻辑地址 < 界地址寄存器内容，合法则 物理地址 = 重定位寄存器内容 + 逻辑地址。
某系统采用「重定位寄存器 + 界地址寄存器」实施保护，重定位寄存器内容为 3000，界地址寄存器内容为 500。进程访问逻辑地址 600 会发生什么？若访问逻辑地址 400，对应物理地址是多少（按字节编址）？
查看答案
逻辑地址 600 ≥ 界地址 500 → 越界，产生越界中断，不会去访存；逻辑地址 400 < 500 合法，物理地址 = 3000 + 400 = 3400。注意先判断、后相加，顺序别颠倒。
3.2 连续分配管理方式
连续分配指为一个用户程序划分一段连续的内存空间。按「分区何时划分、能否变化」分为单一连续、固定分区、动态分区三种，碎片类型各不相同——内部 / 外部碎片之辨是本节选择题的常客。
3.2.1 单一连续与固定分区分配
- 单一连续分配：内存分系统区 + 用户区，用户区任一时刻只装一道程序。无外部碎片，有内部碎片（分给它的用不完也算它的），利用率最低；
- 固定分区分配：用户区预先划成若干固定大小的分区（大小可相等也可不等，不等时按常用作业规模搭配可提高利用率），每个分区装一道作业，支持多道。分区总有剩余 → 内部碎片；分区之间不会出现无法利用的小空闲 → 无外部碎片；
- 动态分区分配：进程装入时才按其大小「量体裁衣」建分区 → 分区内部不浪费，但进程不断进出会在分区之间留下难以利用的小空闲块 → 外部碎片。
3.2.2 动态分区分配与空闲分区表
固定分区分配中，各分区大小可以不相等，这样做的主要目的是什么？固定分区有外部碎片吗？
查看答案
根据常驻作业的大小配置不同分区，小作业进小分区、大作业进大分区，减少每个分区内被浪费的空间（内部碎片），提高内存利用率；固定分区的空闲空间始终整块地留在分区之外，不会被作业切割得七零八落，因此无外部碎片（浪费都算作内部碎片）。
3.2.3 四种动态分区分配算法 高频考点
| 算法 | 空闲区排列规则 | 选择策略 | 优缺点 |
|---|---|---|---|
| 首次适应 First Fit | 按地址递增 | 从头顺序找第 1 个够大的 | 简单、开销小；低址部分不断被切小，但高址端保留大分区，综合性能通常最好 |
| 最佳适应 Best Fit | 按容量递增 | 第 1 个够大的即最小的够大者 | 「只求够用」每次剩下最小的碎片 → 产生大量难以利用的小外部碎片 |
| 最坏适应 Worst Fit | 按容量递减 | 挑最大的分区切 | 切剩的块仍较大尚可再用，但大分区迅速耗尽，后续大作业难以装入 |
| 邻近适应 Next Fit | 按地址递增（循环链） | 从上次查找结束处继续找第 1 个够大的 | 分配更均匀，但大的高址分区更早被用掉，综合通常不优于首次适应 |
② 邻近适应的空闲链仍按地址递增（不是按容量），只是查找起点不回表头；
③ 分配算法针对的是动态分区；固定分区不存在「选哪块更好」的问题（分区大小固定，作业进匹配的分区即可）。
某系统内存空闲分区（按地址递增）依次为 100KB、500KB、200KB、300KB、600KB。现有作业序列依次申请 212KB、117KB、526KB。分别用首次适应、最佳适应、最坏适应算法处理，各作业装入哪个分区？哪种算法最终无法满足第三个作业？
查看解答
首次适应（从头找第 1 个够大的，剩余留在原地）：
212K → 500K（剩 288K）；117K → 288K（剩 171K）；526K → 现有 100K、171K、200K、300K、600K 中只有 600K 够 → 600K（剩 74K）。三个作业全部装入 ✓
最佳适应（每次挑最小够大者）：212K → 300K（剩 88K）；117K → 200K（剩 83K）；526K → 600K（剩 74K）。全部装入 ✓（但留下 88K、83K 等小碎片）
最坏适应（每次挑最大者）：212K → 600K（剩 388K）；117K → 388K（剩 271K）；526K → 现有 100K、500K、200K、300K、271K 都不够 → 分配失败。
套路总结：这类题拿空闲区列表逐步「划掉—改余量」即可；最佳适应盯着「够用的最小」，最坏适应盯着「最大」，首次适应从低址起按顺序找。三种算法分完后再检查一遍剩余容量表，防止算错。
接例 2 的初始状态，若采用邻近适应算法（初始指针在表头），三个作业分别装入哪个分区？
查看答案
212K：从表头起 → 500K（剩 288K），指针移到 500K 分区；
117K：从指针处向后找 → 288K 够（剩 171K），指针停在原 500K 分区；
526K：从指针处向后 → 200K、300K 不够，绕回 100K 也不够，到 600K 够 → 600K（剩 74K）。
对比：首次适应第三步是「从头找」，邻近适应是「从上次位置接着找」，本题结果恰好相同，但中间检查的分区不同——真题常考这个差别。
3.2.4 分区回收、碎片与紧凑
| 情况 | 处理办法 |
|---|---|
| ① 仅前邻接空闲区 | 与前邻合并：修改前邻分区大小 += R（起始地址不变） |
| ② 仅后邻接空闲区 | 与后邻合并：新分区起始地址 = A，大小 = R + 后邻大小（回收区地址作为新起点） |
| ③ 前后都邻接空闲区 | 三区合一：修改前邻大小 += R + 后邻大小，删除后邻表项（起始地址仍为前邻的） |
| ④ 前后都不邻接 | 新建一个表项（起始地址 A、大小 R），按地址有序插入空闲表 |
| 管理方式 | 内部碎片 | 外部碎片 |
|---|---|---|
| 单一连续分配 | 有（整个用户区的富余） | 无 |
| 固定分区分配 | 有（分区内浪费） | 无 |
| 动态分区分配 | 无（量体裁衣） | 有（分区之间的小空闲） |
| 基本分页 | 有（最后一页凑不满） | 无 |
| 基本分段 | 无 | 有（段间小空闲） |
| 段页式 | 有（每段最后一页的页内碎片） | 无 |
某动态分区系统回收一个起始地址 60K、大小 30K 的分区时，空闲分区表中已有两个空闲区：起始 30K 大小 30K，起始 90K 大小 20K。本次回收属于哪种情况？回收后空闲区表变成什么样？
查看答案
回收区 [60K, 90K) 与前邻 [30K, 60K) 恰好相邻、与后邻 [90K, 110K) 也相邻 → 情况③前后都邻接：三区合一为起始 30K、大小 30 + 30 + 20 = 80K 的一个空闲区，删除原后邻表项。回收后空闲表仅剩一项：起始 30K，大小 80K（假设无其他空闲区）。
3.3 基本分页存储管理 高频考点
3.3.1 页面、页框与地址结构
② 分页没有外部碎片（任何页框都能用），但平均每个进程浪费半页内部碎片；
③ 十进制地址先「除页大小取商余」再查页表；十六进制地址直接按位数切（4KB → 低 12 位十六进制 3 位）。
某分页系统页大小 4KB，某进程页表如下：页 0→物理块 5，页 1→块 9，页 2→块 7，页 3→块 1。求：(1) 逻辑地址 8644 的物理地址；(2) 十六进制逻辑地址 0x17A3 的物理地址。
查看解答
4KB = \(2^{12}\,\mathrm{B}\)，页内偏移 12 位。4KB 页大小 → 页号 = ⌊地址 / 4096⌋，偏移 = 地址 mod 4096。
(1) \(8644 = 2\times4096 + 452\) → 页号 2、偏移 452。查表：页 2 → 块 7。物理地址 = \(7\times4096 + 452 = 28672 + 452 = \mathbf{29124}\)。
(2) 4KB 页 → 低 3 个十六进制位（12 位二进制）是偏移：0x17A3 → 页号 0x1、偏移 0x7A3。页 1 → 块 9（0x9）。物理地址按「块号拼偏移」直接写出：0x9 | 0x7A3 → 0x97A3。验证：0x17A3 = 6051 = 1×4096 + 1955（0x7A3 = 1955 ✓）；0x97A3 = 9×4096 + 1955 = 36864 + 1955 = 38819 ✓。
套路总结：十六进制题不用换十进制，直接「切低位、查表、拼块号」：物理地址 = 块号按页大小补零拼接 + 原偏移。0x17A3 → 块 9 → 0x9 拼 0x7A3 → 0x97A3。
页大小改为 1KB，页表：页 0→块 3，页 1→块 6，页 2→块 9，页 3→块 11，页 4→块 8。求逻辑地址 4500 与 1023 的物理地址。
查看答案
1KB = \(2^{10}\,\mathrm{B}\)：\(4500 = 4\times1024 + 404\) → 页 4 → 块 8 → \(8\times1024 + 404 = \mathbf{8196}\)；
\(1023 = 0\times1024 + 1023\) → 页 0 → 块 3 → \(3\times1024 + 1023 = \mathbf{4095}\)（正好是页 0 的最后一字节）。
3.3.2 页表与地址转换全过程
输入: 逻辑地址 A, 页大小 L, 页表始址 M, 页表长度 len
P = A / L; W = A mod L; // 拆分: 页号与页内偏移
if (P >= len)
触发越界中断, 终止访问; // 页号越界
B = 内存[M + P * 表项长度]; // 查页表得物理块号 (1 次访存)
物理地址 = B * L + W; // 块号乘页大小, 偏移原样照抄
return 访问内存[物理地址]; // 再 1 次访存, 共 2 次3.3.3 页表大小的计算
某 32 位系统，页面大小 4KB，页表项 4B，内存 4GB。(1) 逻辑地址如何划分？(2) 单级页表多大？(3) 若要求页表本身也按页离散存放（每页 4KB），需要几级页表？各级占多少位？
查看解答
(1) 4KB = \(2^{12}\) → 页内偏移 12 位，页号 \(32-12=\) 20 位，进程最多 \(2^{20}\) 页；
(2) 单级页表 = \(2^{20}\) 项 × 4B = 4MB——它必须连续存放才能用「始址 + 页号×4」寻址，4MB 连续内存代价很大；
(3) 一页 4KB 能放 \(4096/4 = 2^{10}\) 个表项 → 每级页表管理 10 位；20 位页号拆成 10 + 10：32 位地址 = 10 位一级页号 + 10 位二级页号 + 12 位偏移。一级页表（页目录）\(2^{10}\) 项 × 4B = 4KB，恰好一页，可整体常驻内存。
套路总结：级数 = ⌈(地址位数 − 偏移位数) / 每级管理位数⌉。位数对不上时最后一级少几位（如 40 位地址 → 10+10+8+12 三级）。
3.3.4 快表 TLB 与有效访问时间 高频考点
某系统访存一次 100ns，访问 TLB 一次 20ns，单级页表，TLB 命中率 90%。分别按以下两种模型求一次访存的有效时间 EAT：
模型一：先访 TLB，未命中再访存查页表（串行）；
模型二：TLB 查找与访存查页表同时启动（并行，未命中的 TLB 时间被查页表时间覆盖）。
查看解答
模型一（串行）：命中 = TLB 20 + 取数据 100 = 120ns；未命中 = TLB 20 + 查页表 100 + 取数据 100 = 220ns。
\[ EAT = 0.9\times120 + 0.1\times220 = 108+22 = 130\ \mathrm{ns} \]模型二（并行）：命中仍是 20+100 = 120ns；未命中时 TLB 的 20ns 与查页表的 100ns 重叠，只计 100 + 100 = 200ns。
\[ EAT = 0.9\times120 + 0.1\times200 = 108+20 = 128\ \mathrm{ns} \]对比：完全不用 TLB 的基本分页每次 \(2\times100=200\)ns，引入 TLB 后性能显著改善。
易错：题目不说明时按王道 / 真题习惯用模型一（TLB 时间每次都计）；看到「同时访问 / 并行访问 TLB 与页表」才用模型二。二级页表 + TLB 串行公式：\(EAT = h(t_{TLB}+t_{mem}) + (1-h)(t_{TLB}+3t_{mem})\)。
二级页表系统，访存 100ns，TLB 10ns，命中率 98%。求无 TLB 与有 TLB（串行模型）两种情况下的 EAT，并计算加速比。
查看答案
无 TLB：\(3\times100=300\)ns（页目录、页表、数据各一次）；
有 TLB：\(EAT = 0.98\times(10+100)+0.02\times(10+300) = 107.8+6.2 = 114\)ns；
加速比 \(300/114\approx2.6\) 倍。可见页表级数越多，TLB 省下的访存越多。
3.3.5 两级与多级页表
② 分级后访存次数增加：\(n\) 级页表无 TLB 时需 \(n+1\) 次访存（单级 2 次、二级 3 次）——靠 TLB 挽回；
③ 各级「每级管理位数」由「一页能装多少个表项」决定，不是想怎么拆就怎么拆。
某系统逻辑地址 40 位，页面 4KB，页表项 4B，要求页表分页离散存放。至少需要几级页表？画出地址划分。
查看答案
偏移 12 位 → 页号共 \(40-12=28\) 位；一页 4KB 装 \(2^{10}\) 项 → 每级管 10 位；\(\lceil 28/10\rceil = 3\) 级。
划分：10 位一级 + 10 位二级 + 8 位三级 + 12 位偏移（最后一级只管 \(28-20=8\) 位，页目录仅 \(2^{8}=256\) 项 = 1KB）。
无 TLB 访存 \(3+1=4\) 次。注意级数向上取整、末级位数可以不满 10 位。
3.4 基本分段与段页式管理
3.4.1 分段：二维地址空间
- 段号 \(S\) 与段表长度比较：\(S\ge\) 段表长度 → 段号越界，中断；
- 段表始址 + \(S\times\)表项长度 → 取出该段的段长 C 与基址 B；
- 段内偏移 \(W\ge C\) → 段内越界，中断（分段特有！分页的页内偏移不可能越界——地址拆分方式保证偏移恒小于页大小）；
- 物理地址 = \(B + W\)。整个过程访存 2 次（段表 1 次 + 数据 1 次）。
某进程段表如下（按字节编址）：
| 段号 | 段长 | 基址 |
|---|---|---|
| 0 | 15KB | 100KB |
| 1 | 30KB | 130KB |
| 2 | 20KB | 180KB |
| 3 | 10KB | 220KB |
判断下列逻辑地址是否越界，越界的指出原因，合法的算出物理地址：(a) (2, 15K)；(b) (3, 12K)；(c) (0, 8K)；(d) (4, 1K)。
查看解答
(a) 段号 2 < 4 ✓，偏移 15K < 段长 20K ✓ → 合法，物理地址 = 180K + 15K = 195KB；
(b) 段号 3 < 4 ✓，但偏移 12K ≥ 段长 10K → 段内越界中断；
(c) 段号 0 ✓，8K < 15K ✓ → 100K + 8K = 108KB；
(d) 段号 4 ≥ 段表长度 4 → 段号越界中断（段表只有 0～3 段）。
易错：分页只判一次越界（页号 ≥ 页表长度），分段要判两次（段号、段内偏移各一次）。若题目给十进制一维地址，先按「段号位数 + 偏移位数」拆成二维再判断。
3.4.2 分页 vs 分段对比 高频考点
| 对比维度 | 分页 | 分段 |
|---|---|---|
| 划分依据 | 物理划分：按固定页大小机械切分 | 逻辑划分：按程序模块（代码 / 数据 / 栈） |
| 地址空间 | 一维：一个线性地址即可确定（页号隐含在地址高位） | 二维：必须 (段号, 段内偏移) 两个分量 |
| 大小 | 页大小固定，由硬件决定 | 段长可变，由程序逻辑决定 |
| 对程序员 | 透明（不可见） | 可见（需要程序员 / 编译器划分段） |
| 碎片 | 内部碎片（最后一页凑不满），无外部碎片 | 外部碎片（段间小空闲），无内部碎片 |
| 共享与保护 | 不易实现（页是机械切块，不对应完整模块） | 便于共享和保护（以段为单位共享，如共享代码段；需可重入码） |
| 越界判断 | 一次（页号 vs 页表长度） | 两次（段号 vs 段表长度、偏移 vs 段长） |
3.4.3 段页式管理
- 段号 S 查段表（访存①）→ 得到该段页表始址；
- 页号 P 查该段页表（访存②）→ 得到物理块号 B；
- 物理地址 = B×页大小 + W，取数据（访存③）。
段页式存储管理中，逻辑地址结构为「6 位段号 + 10 位页号 + 12 位页内偏移」。(1) 该系统逻辑地址共多少位？进程最多多少段？(2) 无快表时访问一个数据需几次访存？(3) 段页式有无外部碎片？
查看答案
(1) \(6+10+12=28\) 位；段数 \(2^{6}=64\) 段，每段最多 \(2^{10}\) 页，页大小 \(2^{12}\,\mathrm{B}=4\mathrm{KB}\)；
(2) 段表、页表、数据各访存一次，共 3 次；
(3) 无外部碎片（内存按页框分配），但每段最后一页可能有内部碎片。
3.5 虚拟内存与请求分页 高频考点
3.5.1 局部性原理与虚拟内存
- 时间局部性：刚被执行 / 访问过的指令 / 数据很快会再次被访问（循环、反复调用的函数、累加变量）；
- 空间局部性：刚被访问的存储单元附近的内容很快会被访问（顺序执行、数组顺序扫描）。
3.5.2 请求分页与缺页中断
| 字段 | 含义 | 用途 |
|---|---|---|
| 物理块号 | 页在内存的位置 | 地址转换 |
| 状态位（有效位） | 该页是否已调入内存 | 为 0 触发缺页中断 |
| 访问位 | 最近是否被访问过 | 供置换算法参考（CLOCK / LRU 近似） |
| 修改位 | 调入后是否被修改过 | 淘汰时为 1 才写回外存，减少 I/O |
| 外存地址 | 该页在外存（对换区 / 文件区）的位置 | 缺页时调入 |
- 属于内中断（异常）中的「故障」（fault），而非外中断（I/O 请求引起的外部事件）；
- 在指令执行期间产生和处理（不是一条指令执行完后才检查——外中断才是「指令周期末尾」检查）；
- 一条指令可能引发多次缺页：如
copy A, B两个操作数各跨一页，取指令本身还可能跨页，最多可缺 4 次（指令本身 2 页 + 两个操作数各 2 页）。
trap 缺页中断(页号 P):
if (页表[P].状态位 == 1) return; // 在内存, 正常访问
阻塞当前进程, 转缺页中断处理程序;
if (无空闲页框) {
V = 页面置换算法选淘汰页(); // OPT/FIFO/LRU/CLOCK
if (页表[V].修改位 == 1)
写回外存[页表[V].外存地址]; // 脏页必须写回
回收 V 的页框; 置 页表[V].有效 = 0;
}
从外存[页表[P].外存地址] 调入页 P; // I/O, 耗时毫秒级
更新页表[P]: 块号 = 页框号, 状态位 = 1, 访问位 = 1;
唤醒进程, 重新执行被中断的指令; // 注意: 不是下一条某请求分页系统，一次访存 100ns，一次缺页处理平均 8ms（含全部 I/O 与调度开销），当前缺页率 \(p=10^{-3}\)。(1) 求 EAT；(2) 若要求缺页带来的平均开销不超过 10%（即 EAT ≤ 110ns），缺页率最高是多少？
查看解答
(1) \(8\,\mathrm{ms}=8\times10^{6}\,\mathrm{ns}\)：
\[ EAT=(1-10^{-3})\times100+10^{-3}\times8\times10^{6}=99.9+8000=8099.9\ \mathrm{ns}\approx8.1\,\mu\mathrm{s} \](2) \(100+p\,(8\times10^{6}-100)\le110 \Rightarrow p\le\dfrac{10}{7\,999\,900}\approx1.25\times10^{-6}\)，即平均每 80 万次访存至多缺页 1 次。
易错：缺页率仅 0.1%，EAT 就暴涨 80 倍——磁盘 I/O 比访存慢 5 个数量级，这就是「抖动」致命的原因（3.5.4）。单位先统一成 ns 再算。
3.5.3 页面置换算法 高频考点
缺页而无空闲页框时，必须淘汰一页。算法评价标准是缺页次数（缺页率）。注意：「缺页次数」= 装入次数 + 置换次数，页面已在内存的访问不算缺页；做题时把引用串逐个过一遍，命中打勾、缺页打叉。
1. 最佳置换算法 OPT（理论 benchmark）
2. 先进先出 FIFO 与 Belady 异常
引用串 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。用 FIFO 分别在 3 个、4 个页框下推演，统计缺页次数。
查看解答
3 帧（× 为缺页，每步框内为当前页面，加粗为新调入）：
| 访问 | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 框1 | 1 | 1 | 1 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 5 |
| 框2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | |
| 框3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | ||
| 缺页 | × | × | × | × | × | × | × | × | × |
共 9 次缺页（末尾访问 5 时 5 已在内存，命中）。
4 帧：
| 访问 | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 框1 | 1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 4 | 4 |
| 框2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 5 | |
| 框3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | ||
| 框4 | 4 | 4 | 4 | 4 | 4 | 4 | 3 | 3 | 3 | |||
| 缺页 | × | × | × | × | × | × | × | × | × | × |
共 10 次缺页——页框从 3 增到 4，缺页反而 9 → 10，这就是 Belady 异常。根源：FIFO 不是栈式算法（\(k\) 帧时的页集合并非 \(k+1\) 帧时的子集）；LRU 与 OPT 是栈式算法，不会出现异常。
套路总结：FIFO 推演必须记「进入顺序」（队头最老），不能只看表格当前摆放；被淘汰的是最早进入的那页，哪怕它最近刚被用过。
3. LRU 最近最久未使用
引用串 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，分配 3 个页框，页框初始为空。分别用 OPT、FIFO、LRU 算法求缺页次数与命中率。
查看解答
逐位推演（框内从左到右按各算法自身顺序排列；× = 缺页，○ = 命中）：
| 访问 | FIFO 框内 | 缺页 | LRU 框内（右端最新） | 缺页 | OPT 框内 | 缺页 |
|---|---|---|---|---|---|---|
| 7 | 7 | × | 7 | × | 7 | × |
| 0 | 7,0 | × | 7,0 | × | 7,0 | × |
| 1 | 7,0,1 | × | 7,0,1 | × | 7,0,1 | × |
| 2 | 2,0,1 | × | 0,1,2 | × | 2,0,1 | × |
| 0 | 2,0,1 | ○ | 1,2,0 | ○ | 2,0,1 | ○ |
| 3 | 2,3,1 | × | 2,0,3 | × | 2,0,3 | × |
| 0 | 2,3,0 | × | 2,3,0 | ○ | 2,0,3 | ○ |
| 4 | 4,3,0 | × | 3,0,4 | × | 2,4,3 | × |
| 2 | 4,2,0 | × | 0,4,2 | × | 2,4,3 | ○ |
| 3 | 4,2,3 | × | 4,2,3 | × | 2,4,3 | ○ |
| 0 | 0,2,3 | × | 2,3,0 | × | 2,0,3 | × |
| 3 | 0,2,3 | ○ | 2,0,3 | ○ | 2,0,3 | ○ |
| 2 | 0,2,3 | ○ | 0,3,2 | ○ | 2,0,3 | ○ |
| 1 | 0,1,3 | × | 3,2,1 | × | 2,0,1 | × |
| 2 | 0,1,2 | × | 3,1,2 | ○ | 2,0,1 | ○ |
| 0 | 0,1,2 | ○ | 1,2,0 | × | 2,0,1 | ○ |
| 1 | 0,1,2 | ○ | 2,0,1 | ○ | 2,0,1 | ○ |
| 7 | 7,1,2 | × | 0,1,7 | × | 7,0,1 | × |
| 0 | 7,0,2 | × | 1,7,0 | ○ | 7,0,1 | ○ |
| 1 | 7,0,1 | × | 7,0,1 | ○ | 7,0,1 | ○ |
统计：FIFO 缺页 15 次（命中率 5/20 = 25%），LRU 缺页 12 次（8/20 = 40%），OPT 缺页 9 次（11/20 = 55%）。
关键分歧点回放：第 4 步访问 2 时 FIFO 淘汰最早进入的 7，LRU 也淘汰 7（7 是最久未用），OPT 同样淘汰 7（7 在未来第 18 步才再现，最远）；第 7 步访问 0 时 FIFO 因第 6 步刚把 0 换出而再次缺页，LRU 则命中——FIFO 的「无视访问历史」正是它缺页多的根源。
结论：OPT 9 < LRU 12 < FIFO 15，OPT 不可实现仅作基准；LRU 利用历史近似 OPT，性能最好但硬件贵；FIFO 最简单但可能 Belady 异常。
易错：① 前 3 次冷启动不算「置换」但算「缺页」；② LRU 命中时也要更新顺序，漏更新后面全错；③ 别用「看起来快满」直觉代替逐位推演——大题必须列表。
4. CLOCK 算法（简单时钟 / NRU 近似）
5. 改进型 CLOCK（访问位 A + 修改位 M）
- 第 1 轮：找 (0, 0)——最好：最近没用过、也没改过，直接覆盖不用写回；扫描中不修改标志位；
- 第 2 轮：找 (0, 1)——最近没用过但被修改过，淘汰前须写回外存；找到即选；扫描中把扫过页的 A 置 0；
- 第 3 轮：重复第 1 轮（此时所有 A 已被清 0，等价于找 M=0）；
- 第 4 轮：重复第 2 轮（找 M=1）。
某时刻 4 个页框中页面状态如下（A = 访问位，M = 修改位），指针指向页框 1。现需淘汰一页装入新页，用改进 CLOCK 给出推演过程。
| 页框 | 页面 | 访问位 A | 修改位 M |
|---|---|---|---|
| 1 | P1 | 0 | 1 |
| 2 | P2 | 1 | 0 |
| 3 | P3 | 1 | 1 |
| 4 | P4 | 0 | 1 |
查看解答
第 1 轮（找 (0,0)，不改标志）：框1 (0,1) 不是 → 框2 (1,0) 不是 → 框3 (1,1) 不是 → 框4 (0,1) 不是 → 一圈没有 (0,0)。
第 2 轮（找 (0,1)，扫过的页 A 置 0）：回到框1，(0,1) 命中 → 淘汰 P1。因 M=1，淘汰前须把 P1 写回外存；新页装入框 1，置 (A,M)=(1,0)，指针前移到框 2。
注：若第 2 轮也扫完一圈无果（说明全是 (1,x)），则第 2 轮结束时所有 A 已被清 0，第 3 轮从指针处再找 (0,0) 必然命中；再不行第 4 轮找 (0,1) 也必然命中——四轮之内必选出。
套路总结：先数一圈有没有 (0,0)；没有就带着「A 置 0」再扫一圈找 (0,1)。推演题把每轮每框的 (A,M) 列成表，边扫边改，防止跳步。
引用串 4,3,2,1,4,3,5,4,3,2,1,5，3 个页框，初始为空。(1) 分别求 LRU 与 FIFO 的缺页次数；(2) 本题说明什么？
查看答案
(1) 逐位推演可得：LRU 缺页 10 次，FIFO 缺页 9 次（本串下 FIFO 反而更少）。
LRU 简推：前 3 次缺页装入 4,3,2；访问 1 缺、淘汰 4 → 访问 4 缺、淘汰 3 → 访问 3 缺、淘汰 2 → 访问 5 缺、淘汰 1 → 4 命中、3 命中 → 访问 2 缺、淘汰 5 → 访问 1 缺、淘汰 4 → 访问 5 缺、淘汰 3，共 10 次；FIFO 因淘汰顺序不同恰好少一次。
(2) 说明 LRU 不一定总比 FIFO 好——LRU 基于局部性假设，对特定访问串（局部性差的串）可能吃亏；但统计意义（多数程序）上 LRU 优于 FIFO，且 LRU 无 Belady 异常。
3.5.4 页面分配策略、抖动与工作集
| 维度 | 方案 | 含义 |
|---|---|---|
| 分配多少（驻留集大小） | 固定分配 | 运行前定死页框数，不再变（难以准确估准） |
| 可变分配 | 运行中按缺页情况动态增减页框 | |
| 置换范围 | 局部置换 | 只能淘汰自己的页，缺页率只取决于自己 |
| 全局置换 | 可淘汰任意进程的页，会「抢别人内存」，被抢进程缺页率受他人影响 |
- 预调页：运行前预测性地把可能用到的页一次调入（主要用于首次启动，猜测失败则白调）；请求调页：运行中缺哪调哪（虚拟内存的常规方式，I/O 次数少但单次延迟高）；
- 从何处调页：对换区（快，但外存对换空间有限）；文件区（慢；没被修改过的页不必写回，淘汰后需要时直接从文件区重读）；UNIX 折中：首次从文件区调入、换出时写对换区，之后都走对换区。
- 抖动：刚被换出的页很快又要访问，缺页率急剧上升，进程把时间耗在「换出 / 调入」的 I/O 上，CPU 利用率骤降。根本原因：驻留集太小，装不下进程的工作集（多道程序度太高、分给每个进程的页框太少也会引发）。危险的正反馈：CPU 利用率低 → 调度器以为 CPU 空闲 → 继续增加进程 → 每个进程分到的页框更少 → 缺页更多 → 利用率更低。对策：降低多道程序度、按工作集给足页框；
- 工作集 \(W(t,\Delta)\)：在某时刻 \(t\) 之前的 \(\Delta\) 个访问中实际访问过的不同页面集合，\(\Delta\) 称工作集窗口。工作集是「近期活跃页」的估计：驻留集 ⊇ 工作集时缺页率很低；若内存装不下所有进程的工作集总和，就应挂起（换出）部分进程，防抖动。
② 「全局置换」不等于「可变分配」：前者说能淘汰谁的页，后者说自己页框数变不变；
③ 工作集大小 ≤ 窗口 \(\Delta\)（不同页才计数）；增大 \(\Delta\) 工作集一般变大。
3.5.5 请求分段与请求段页式（简述）
简答：(1) 为什么「固定分配 + 全局置换」不合理？(2) 某进程缺页率突然飙升、CPU 利用率骤降，最可能的原因是什么？给出两条对策。
查看答案
(1) 全局置换允许淘汰其他进程的页框，等于动态改变各进程的驻留集大小，与「固定分配」自相矛盾；
(2) 最可能是抖动：驻留集装不下工作集，或系统多道程序度过高。对策：降低多道程序度（挂起 / 换出部分进程）；按工作集模型给缺页频繁的进程增加页框（可变分配 + 局部置换）。
3.6 章末自测 真题风格
限时 60 分钟，先做后看答案。难度：★★ 基础 / ★★★ 强化 / ★★★★ 冲刺。所有计算题答案均可用具体数值代入复核。
采用动态重定位的系统中，进程在内存中移动位置后，为使其继续正确运行，操作系统必须（ ）
A. 修改进程的所有逻辑地址 B. 修改重定位寄存器的内容 C. 重新编译链接该进程 D. 修改页表长度
查看答案
B。动态重定位下程序体内保持逻辑地址不变，物理地址 = 逻辑地址 + 重定位寄存器，移动后只需改寄存器（进程上 CPU 时由 OS 设置）。修改所有逻辑地址是静态重定位的做法且移动后已不可行。
关于动态分区分配算法，下列说法错误的是（ ）
A. 首次适应算法的空闲分区链按地址递增排列 B. 最佳适应算法容易产生大量小的外部碎片 C. 最坏适应算法下大分区消耗快，不利于后续大作业 D. 邻近适应算法总能使缺页率最低
查看答案
D。邻近适应只是让查找起点循环前进、分配更均匀，与缺页率（页面置换概念）毫无关系，且综合性能通常不优于首次适应。A、B、C 均为正确表述。
某分页系统页大小 2KB，页表：页 0→块 2，页 1→块 4，页 2→块 6，页 3→块 8。逻辑地址 5418 的物理地址是（ ）
A. 10262 B. 13610 C. 12288 D. 11466
查看答案
B。2KB = 2048B：\(5418 = 2\times2048 + 1322\) → 页 2、偏移 1322；块 6 → \(6\times2048+1322 = 12288+1322 = 13610\)。（A 是误用块 5?常见错法：先算 \(5418\div 1024\)；D = \(5418 + 8\times756\) 无意义；C 漏加偏移。）
某 32 位系统页面大小 8KB，页表项 8B，采用单级页表时页表最大约（ ）
A. 4MB B. 8MB C. 16MB D. 32MB
查看答案
A。8KB = \(2^{13}\,\mathrm{B}\) → 页内偏移 13 位 → 页号 \(32-13=19\) 位 → \(2^{19}=524\,288\) 个页表项；页表 = \(524\,288\times8\,\mathrm{B}=4\,194\,304\,\mathrm{B}=4\,\mathrm{MB}\)。陷阱 C（16MB）是把页大小误当 4KB（\(2^{20}\times8\,\mathrm{B}=8\,\mathrm{MB}\) 对应 B，\(2^{21}\) 项才得 16MB）；做题先写「偏移位数」，再定项数，最后乘项长。
二级页表、无快表的系统中，存取一个数据需要访问内存（ ）次；若快表命中则为（ ）次。
A. 2；1 B. 3；1 C. 3；2 D. 4；1
查看答案
B。二级页表：查页目录（1）+ 查二级页表（1）+ 取数据（1）= 3 次；快表命中：TLB 中直接得到块号（TLB 不算访存），只需取数据 1 次。
某进程段表：段 0 长度 10KB 基址 20KB，段 1 长度 15KB 基址 40KB，段 2 长度 8KB 基址 60KB。逻辑地址 (1, 16K) 和 (2, 6K) 分别（ ）
A. 都合法 B. 前者段内越界，后者合法 C. 前者合法，后者越界 D. 都越界
查看答案
B。(1, 16K)：段号 1 合法，但偏移 16K ≥ 段长 15K → 段内越界；(2, 6K)：6K < 8K 合法，物理地址 = 60K + 6K = 66K。
关于缺页中断，下列说法正确的是（ ）
A. 属于外中断，在一条指令执行结束后检测 B. 属于内中断中的故障，指令执行期间产生并处理 C. 一条指令最多产生一次缺页中断 D. 缺页中断处理后从下一条指令继续执行
查看答案
B。缺页中断属内中断（异常）中的「故障」：指令执行期间发现页不在内存立即陷入处理；一条指令可能多次缺页（操作数、指令本身都可能跨页）；处理完应重新执行被中断的指令（它还没执行完），D 错。
分配的物理块数（页框数）增多时，缺页次数反而可能增多的算法是（ ）
A. LRU B. OPT C. FIFO D. 改进 CLOCK
查看答案
C。这是 FIFO 的 Belady 异常（见例 8：3 帧 9 次 → 4 帧 10 次）。LRU 与 OPT 是栈式算法（\(k\) 帧时的页面集合是 \(k+1\) 帧时的子集），块数增多缺页次数必不增；改进 CLOCK 以 CLOCK/FIFO 思想为基础，也可能出现类似异常，但「增多反而增多」的经典指认对象是 FIFO。
系统出现抖动（颠簸）现象的根本原因是（ ）
A. 页面太大 B. 进程的驻留集小于其工作集 C. 磁盘速度太快 D. 采用了全局置换
查看答案
B。驻留集装不下工作集 → 刚换出的页马上又要用 → 缺页率飙升、CPU 都耗在 I/O 上。对策：降低多道程序度、按工作集给足页框。
页大小 2KB，页表：页 0→块 2，页 1→块 4，页 2→块 6，页 3→块 8。求：(1) 逻辑地址 5418 的物理地址；(2) 十六进制逻辑地址 0x18A7 的物理地址。
查看解答
(1) \(5418 = 2\times2048 + 1322\) → 页 2、偏移 1322；块 6 → \(6\times2048+1322 = \mathbf{13610}\)。
(2) 2KB → 偏移 11 位，十六进制低 \(11/4\approx2.75\) 位不整——2KB 页不能按「切十六进制低位」走，先转十进制：0x18A7 = \(1\times4096+8\times256+10\times16+7 = 6311\)；\(6311 = 3\times2048 + 167\) → 页 3、偏移 167；块 8 → \(8\times2048+167 = \mathbf{16551}\)。
注意与 4KB 页的差别：页大小是 2 的幂但十六进制位数不整（11 位）时，老老实实按十进制除法拆分。
引用串 2,3,2,1,5,2,4,5,3,2,5,2，3 个页框，初始为空。分别用 FIFO 和 LRU 推演，求缺页次数与命中率。
查看解答
FIFO（记进入队列，队头淘汰；括号内为每次访问后的页框内容，加粗为新调入）：
2 [2] 缺 → 3 [2,3] 缺 → 2 命中 → 1 [2,3,1] 缺 → 5 [5,3,1] 缺（淘 2）→ 2 [5,2,1] 缺（淘 3）→ 4 [5,2,4] 缺（淘 1）→ 5 命中 → 3 [3,2,4] 缺（淘 5）→ 2 命中 → 5 [3,5,4] 缺（淘 2）→ 2 [3,5,2] 缺（淘 4）。
缺页 9 次，命中 3 次，命中率 3/12 = 25%。
LRU（括号内为栈，右端为最近使用）：2 [2] 缺 → 3 [2,3] 缺 → 2 命中 → [3,2] → 1 [3,2,1] 缺 → 5 [2,1,5] 缺（淘最久未用的 3）→ 2 命中 → [1,5,2] → 4 [5,2,4] 缺（淘 1）→ 5 命中 → [2,4,5] → 3 [4,5,3] 缺（淘 2）→ 2 [5,3,2] 缺（淘 4）→ 5 命中 → [3,2,5] → 2 命中 → [3,5,2]。
缺页 7 次，命中 5 次，命中率 5/12 ≈ 41.7%。结论：本串 LRU 明显优于 FIFO——LRU 在第 3、6 步「续命」了频繁复用的 2 和 5。
结论：本串 LRU 明显优于 FIFO。
二级页表系统，TLB 访问 15ns，访存 120ns，TLB 命中率 90%（串行模型，未命中时 TLB 时间照计）。求一次访存的有效访问时间 EAT。
查看解答
命中：\(15+120 = 135\)ns（TLB + 取数据 1 次访存）；未命中：\(15 + 3\times120 = 375\)ns（TLB + 页目录 + 页表 + 数据）。
\[ EAT = 0.9\times135 + 0.1\times375 = 121.5+37.5 = 159\ \mathrm{ns} \]无 TLB 时为 \(3\times120=360\)ns，TLB 使访存提速约 2.3 倍。
3.7 本章考点总结
| 考点 | 常考题型 | 热度 | 核心方法 / 结论 |
|---|---|---|---|
| 重定位与内存保护 | 选择题 | ★★★ | 静态一次定终身不能移动；动态靠重定位寄存器随时可搬；保护用上下限寄存器（比物理地址）或重定位 + 界地址寄存器（先比逻辑地址再加基址） |
| 连续分配与分配算法 | 选择 / 大题 | ★★★★ | 固定分区内部碎片、动态分区外部碎片；首次适应通常综合最优，最佳适应碎片最多，最坏适应耗尽大分区，邻近适应循环查找；回收四情况合并 |
| 分页地址翻译 | 大题必考 | ★★★★★ | 拆（页号 = ⌊A/页大小⌋）→ 查页表 → 拼（物理 = 块号×页大小 + 偏移）；4KB 页十六进制直接切低 3 位；偏移永不参与查表 |
| 页表 / 多级页表 | 计算题 | ★★★★ | 页表 = (地址空间 ÷ 页大小) × 项长；32 位 4KB 页 4B 项 → 单级 4MB、拆 10+10+12 两级；多级页表解决「连续 + 全驻留」，不省总量；n 级无快表 n+1 次访存 |
| TLB 与 EAT | 计算题 | ★★★★ | 串行：\(EAT=h(t_{TLB}+t_m)+(1-h)(t_{TLB}+kt_m)\)（k = 查页表 + 取数据的访存次数）；并行：未命中不计 TLB 时间；命中恒 1 次访存 |
| 分段与段页式 | 选择题 | ★★★ | 二维地址、两次越界判断、物理 = 基址 + 偏移；页物理 / 段逻辑、页透明 / 段可见、页内部碎片 / 段外部碎片、段好共享；段页式先段后页 3 次访存 |
| 缺页中断与性能 | 选择 / 计算 | ★★★★ | 内中断故障、指令执行期间处理、一条指令可多次缺页、处理完重新执行本指令；\(EAT=(1-p)t+pT\)，磁盘 I/O 比访存慢 5 个数量级 |
| 页面置换算法 | 大题必考 | ★★★★★ | OPT 最低但不可实现；FIFO 简单有 Belady（3 帧 9 → 4 帧 10）；LRU 性能好硬件贵、栈式无异常；CLOCK 用访问位，改进型 (A,M) 四轮优先 (0,0) |
| 分配策略与抖动 | 选择题 | ★★★ | 固定 / 可变 × 局部 / 全局（固定 + 全局不成立）；抖动 = 驻留集 < 工作集，CPU 利用率骤降；工作集 \(W(t,\Delta)\) 为 Δ 窗口内不同页集合 |