第 3 章 内存管理
408 操作系统第 3 章 内存管理复习讲义，涵盖核心概念、重点考点与典型题型。
Last updated on
先看一张整章地图：
为什么要管理内存
│
├── 地址问题：逻辑地址 → 物理地址
│
├── 分配问题
│ ├─ 连续分配
│ │ ├─ 单一连续
│ │ ├─ 固定分区
│ │ └─ 动态分区
│ │ └─ FF / NF / BF / WF
│ │
│ └─ 非连续分配
│ ├─ 分页 ★★★★★
│ ├─ 分段 ★★★
│ └─ 段页式 ★★★
│
└── 内存不够怎么办？
↓
虚拟内存 ★★★★★
│
├─ 请求分页
├─ 缺页异常 ★★★★★
├─ 页框分配
├─ 页面置换 ★★★★★
│ ├─ OPT
│ ├─ FIFO
│ ├─ LRU
│ └─ CLOCK
├─ 抖动
├─ 页框回收
└─ 内存映射文件从考研角度，建议把本章理解成一句话：
操作系统想办法把进程看到的“自己的连续大内存”，映射到实际上零零散散、有限而且被许多进程共享的物理内存。
一、先搞懂：为什么操作系统一定要管理内存？
如果只有一个程序运行，事情非常简单：
内存
┌──────────────┐
│ 操作系统 │
├──────────────┤
│ 用户程序 │
└──────────────┘但多道程序出现以后：
内存
┌──────────────┐
│ 操作系统 │
├──────────────┤
│ 进程 A │
├──────────────┤
│ 进程 B │
├──────────────┤
│ 进程 C │
└──────────────┘马上出现几个问题：
- A、B、C 分别放哪里？
- A 能不能覆盖 B 的数据？
- A 程序中写的地址
1000到底对应物理内存哪个位置？ - 某进程退出以后，空间怎么回收？
- 空闲空间散成很多小块怎么办？
- 一个 10GB 程序能不能在只有 8GB 内存的机器上运行？
- 不同进程能否共享相同代码？
因此资料把内存管理的核心功能概括为：内存分配与回收、地址映射、内存保护与共享、内存扩充。
二、逻辑地址、物理地址与地址重定位
这是后面分页、分段、虚拟内存的地基。
1. 物理地址
物理地址就是真正送到主存地址总线上的地址。
假设主存中：
0
...
10000 ← 某进程实际装在这里
10001
...那么 10000 就是物理地址。
2. 逻辑地址
程序员写程序的时候当然不可能提前知道：
“以后操作系统会把我的程序恰好装到物理地址 10000。”
所以程序中使用的是相对于自身地址空间的地址：
0
1
2
...
500
...这就是逻辑地址。
例如：
进程自己的逻辑地址空间
0 main()
100
200
500 x
...但进程可能实际被操作系统放到：
物理内存
10000 ← 进程起始位置
...
10500 ← 逻辑地址 500 对应这里于是最朴素的转换就是：
三、静态重定位和动态重定位
这部分很容易和“分页地址转换”混淆。
1. 静态重定位
装入程序时一次性完成地址修改。
例如进程程序中：
进程装入物理地址：
装入时直接把地址改成：
以后程序里直接用 10500。
问题是：一旦改完，这个程序就不方便再移动。
因此静态重定位要求：
- 装入前获得足够连续空间；
- 装入以后位置基本固定；
- 很难进行内存紧凑。
2. 动态重定位
动态重定位并不提前改掉逻辑地址，而是在每次执行到该地址时再转换。
需要一个重定位寄存器：
重定位寄存器 = 10000
逻辑地址 = 500
↓
物理地址 = 10500即：
其中：
- ：Physical Address；
- ：Base Address；
- ：Logical Address。
这样，如果操作系统以后把整个进程移动到 20000：
重定位寄存器 = 20000程序自己的地址仍然是 500：
程序自己完全不知道被移动过。
所以紧凑技术要求动态重定位支持。资料也专门指出：动态运行时装入支持程序移动，使操作系统可以进行紧凑。
四、内存保护：基址寄存器 + 界限寄存器
这是一个非常漂亮的设计。
假设：
进程被分配：
物理起点 = 10000
长度 = 4000设置：
重定位寄存器 = 10000
界地址寄存器 = 4000进程发出逻辑地址 。
首先：
如果不是：
越界！如果合法：
所以可以记：
界限寄存器负责“比”，重定位寄存器负责“加”。
资料也明确这样总结，而且这些寄存器只能由操作系统用特权指令修改，否则用户程序自己修改基址就能访问别人的内存。
五、内存共享
不同进程的逻辑地址空间彼此独立，并不意味着物理内存绝不能重合。
比如：
进程 A 页表 ─┐
├──→ 同一组物理代码页
进程 B 页表 ─┘尤其是只读代码非常适合共享。
资料中的例子是 40 个用户同时运行一个：
- 代码区：160KB
- 数据区：40KB
如果完全不共享：
如果共享代码：
节省非常明显。允许多个进程同时访问、但不允许修改的代码称为可重入代码/纯代码；每个进程仍保留自己的私有数据区。
六、连续分配管理
现在进入真正的“怎么给进程分内存”。
连续分配的共同特点：
一个进程占据一整块连续的物理内存。
资料依次介绍：
单一连续
↓
固定分区
↓
动态分区
↓
发现连续分配还是有碎片
↓
分页这是技术演进逻辑，不要死背。
七、单一连续分配
内存只有：
┌───────────────┐
│ 操作系统 │
├───────────────┤
│ 一个用户进程 │
│ │
│ │
└───────────────┘优点：极其简单。
缺点：
- 只能运行一道用户程序；
- 内存利用率低；
- 大量空间可能浪费。
了解即可。
八、固定分区分配
提前把内存切成几块：
┌──────────────┐
│ OS │
├──────────────┤
│ 100MB │
├──────────────┤
│ 200MB │
├──────────────┤
│ 300MB │
└──────────────┘假设一个 120MB 程序进入 200MB 分区：
200MB 分区
┌──────────────┐
│ 120MB 程序 │
├──────────────┤
│ 80MB 浪费 │ ← 内部碎片
└──────────────┘高频概念：内部碎片
所谓内部碎片：
已经分配给进程的区域内部，却存在没有被有效使用的空间。
固定分区会产生内部碎片。
九、动态分区分配 ★★★★
这块选择题非常爱考。
进程来多少，就给多少连续空间。
例如开始：
1000MB 空闲依次来：
A 200MB
B 300MB
C 100MB形成：
| A200 | B300 | C100 | 空闲400 |后来 B 退出：
| A200 | 空闲300 | C100 | 空闲400 |现在总空闲：
如果来了一个 500MB 进程，能装吗？
不能。
因为最大的连续空闲区只有 400MB。
这就是：
外部碎片
空闲空间总量够，但被分割成许多不连续的小块。
动态分区主要产生外部碎片。
十、内部碎片和外部碎片一定分清
这是 408 高频陷阱。
| 管理方式 | 内部碎片 | 外部碎片 |
|---|---|---|
| 单一连续 | 有 | 无 |
| 固定分区 | 有 | 无 |
| 动态分区 | 通常无 | 有 |
| 分页 | 有 | 无 |
| 分段 | 通常无 | 有 |
| 段页式 | 有 | 无（分页层面） |
分页为什么还有内部碎片？
因为最后一页可能没装满。
例如页大小 4KB，一个进程需要 10KB：
第0页 4KB
第1页 4KB
第2页 2KB + 浪费2KB这 2KB 就是页内的内部碎片。
资料明确指出分页消除了外部碎片，但仍可能存在内部碎片，并指出平均页内碎片约半页。
十一、动态分区的四种分配算法 ★★★★
资料的考点追踪显示，动态分区算法特点在 2019、2024 等年份被考查，最佳适应的分配过程也曾直接出题。
一定掌握：
| 算法 | 怎么找 | 空闲链组织 |
|---|---|---|
| First Fit | 第一个够大的 | 地址递增 |
| Next Fit | 从上次位置继续找 | 地址循环 |
| Best Fit | 最小但够大的 | 容量递增 |
| Worst Fit | 最大的 | 容量递减 |
1. 首次适应 First Fit
假设：
100 500 200 400申请：
180从头找：
- 100 不够；
- 500 够；
于是切 500。
特点：
看到第一个能装下的就用。
综合性能通常比较好。
2. 邻近适应 Next Fit
和 First Fit 类似，但不是每次从头开始。
假设上次在：
↓
100 500 200 400下次从这里继续找，再循环一圈。
优点：避免总扫描低地址。
缺点：可能把各处的大块逐渐切碎。
3. 最佳适应 Best Fit
申请 180：
空闲块：
100, 200, 400, 500能满足的是：
200,400,500选最小的：
200剩：
问题恰恰就在这：
经常产生大量非常小、以后谁也用不了的碎片。
所以：
Best Fit 名字叫“最佳”，实际不代表综合性能最佳。
4. 最坏适应 Worst Fit
仍然申请 180：
100,200,400,500选最大的：
500剩：
它想避免制造很小的碎片。
但缺点是：
一直切最大的空闲块，很快系统里就没有真正的大块空间了。
十二、动态分区算法题怎么做？
资料中有一道典型题：
空闲分区：
100, 450, 250, 200, 600 KB依次申请：
212, 417, 112, 426 KB问哪种算法能全部完成。
对于 Best Fit：
剩：
然后：
剩：
然后：
剩：
最后：
剩：
全部成功，因此题中答案为最佳适应。
做这种题不要凭感觉
一定维护当前空闲表：
原空闲表
→ 第一次分配
→ 更新
→ 第二次
→ 更新
...尤其：
- First Fit 看地址顺序；
- Best Fit 看大小顺序；
- Next Fit 记住上次查找位置。
十三、动态分区回收的四种情况
回收一个区域 ，只看它前后。
情况 1：前面空闲
[前空闲][X]合并。
情况 2：后面空闲
[X][后空闲]合并。
情况 3：前后都空闲
[前空闲][X][后空闲]三个合成一个。
情况 4：前后都不是空闲
新建一个空闲分区表项。
这正是资料总结的动态分区回收四种情况。
十四、紧凑
假设：
A | 空100 | B | 空200 | C | 空300总空闲：
但没有一个 600 的连续块。
把进程移动：
A | B | C | 空600这就叫紧凑。
但是移动以后：
B 原来地址 ≠ B 现在地址
C 原来地址 ≠ C 现在地址所以必须有动态重定位。
这是非常经典的因果链：
外部碎片
↓
紧凑
↓
移动进程
↓
物理地址发生变化
↓
必须动态重定位十五、分页存储管理 ★★★★★
这是整个第三章最重要的部分之一。
连续分配的核心问题：
一个进程必须找到一块足够大的连续空间。
那为什么一定要求连续？
把一个进程切成小块不就行了？
于是产生分页。
十六、页、页面、页框
假设页面大小：
进程：
逻辑页0
逻辑页1
逻辑页2
逻辑页3物理内存也切成 4KB 一块：
页框0
页框1
页框2
页框3
页框4
...然后：
逻辑页0 → 页框6
逻辑页1 → 页框2
逻辑页2 → 页框10
逻辑页3 → 页框3发现了吗？
进程的页：
0 1 2 3逻辑上连续。
但物理上可以：
6 2 10 3完全不连续。
这正是分页最重要的意义：
消除对连续物理空间的要求，从而消除外部碎片。
十七、页表到底是什么？ ★★★★★
既然：
页0 → 框6
页1 → 框2
页2 → 框10
页3 → 框3CPU 怎么知道？
维护一张表：
| 页号 | 页框号 |
|---|---|
| 0 | 6 |
| 1 | 2 |
| 2 | 10 |
| 3 | 3 |
这就是页表。
这里有一个常见坑：
页号通常是页表中的索引，因此页表项不需要再显式存一个页号。
也就是说页表实际上更像：
page_table[0] = 6
page_table[1] = 2
page_table[2] = 10
page_table[3] = 3十八、分页地址转换 ★★★★★
这是必会计算。
假设页面大小为 ，逻辑地址为 。
首先拆成：
其中：
- ：页号；
- ：页内偏移。
然后页表：
其中 是页框号。
最后：
这就是分页地址转换最核心的公式。
十九、为什么页大小通常是 ？
假设页面大小：
那么地址最低 12 位天然就是页内偏移。
一个 32 位逻辑地址：
┌────────────────────┬────────────┐
│ 页号 │ 页内偏移 │
│ 20bit │ 12bit │
└────────────────────┴────────────┘根本不用真的执行除法。
直接：
高20位 → 页号
低12位 → 页内偏移硬件处理非常方便。
二十、分页地址转换完整过程
假设：
逻辑地址 ACPU 做：
A
│
├── 页号 P
│ │
│ ↓
│ 查页表
│ │
│ ↓
│ 页框号 b
│
└── 页内偏移 W
│
↓
拼接 / 计算
↓
物理地址数学表达：
查到：
于是：
注意：
页内偏移在地址转换过程中不变。
改变的是：
逻辑页号 → 物理页框号二十一、页表项地址怎么求？
假设：
- 页表起始物理地址 ；
- 页号 ；
- 每个页表项大小 。
第 个页表项地址：
这个和数组寻址完全一样。
所以很多 408 页表综合题本质是：
逻辑地址
→ 页号
→ 页表项地址
→ 页框号
→ 物理地址二十二、页表项到底需要多大？
资料给出了典型思路。
假如：
- 物理地址空间 32 位；
- 页面 4KB。
物理内存页框数：
所以至少需要：
才能表示页框号。
但一个页表项不仅要有页框号，还可能有：
有效位
访问位
修改位
权限位
...再考虑存储对齐，实际可能采用 4B 页表项。
二十三、为什么普通页表会让访存慢一倍？
假如页表存在内存。
CPU 想读取变量 x。
不能直接访问 x，因为手里只有虚拟地址。
于是：
第一次访问内存：
读页表 → 得到页框号
第二次访问内存：
真正访问 x所以一次逻辑访存变成至少两次物理访存。
怎么办？
TLB。
二十四、TLB / 快表 ★★★★★
TLB 本质：
页表项的高速缓存。
完整页表在主存：
慢表近期常用页表项放 TLB：
快表因为程序存在局部性：
刚访问页5
↓
接下来很可能继续访问页5于是把：
页5 → 页框17缓存起来。
资料明确指出 TLB 是具有并行查找能力的高速缓存，用于保存当前活跃的若干页表项。
二十五、TLB 命中与不命中
命中
虚拟地址
↓
TLB
↓ 命中
页框号
↓
访问真正数据无需读取主存中的页表。
TLB 未命中
虚拟地址
↓
TLB miss
↓
主存页表
↓
找到页框号
↓
更新TLB
↓
访问数据非常重要：
TLB 未命中 ≠ 缺页。
这是最容易混淆的东西之一。
TLB miss 只是：
快表里没有这个页表项。
但是页可能完全就在主存中。
二十六、TLB、页表、缺页三者关系
可以这样记：
TLB
↓
“最近映射关系在不在高速缓存？”
页表状态位
↓
“页面在不在物理内存？”
缺页
↓
“不在内存，需要从外存调进来。”因此：
TLB 命中
一定意味着对应页已经在内存。
TLB 未命中
有两种：
页在内存 → 普通 TLB miss
页不在内存 → 缺页二十七、TLB 有效访问时间计算 ★★★★★
这种题不要背死公式，因为题目可能规定：
- TLB 和内存串行查找；
- TLB 和页表同时查找。
要根据题干画流程。
资料中有一道题规定：
- TLB：1ns；
- 内存：100ns；
- TLB 与页表同时查找；
- 命中率 。
命中：
未命中，由于页表查询和 TLB 同时进行，到 100ns 已经获得页框号，再访问一次数据：
所以：
要求：
则：
资料题答案就是约 。
核心技巧
不要先写公式。
先写：
命中路径花多久？
未命中路径花多久？再求期望：
二十八、多级页表 ★★★★
为什么需要？
假设：
- 32 位虚拟地址；
- 页大小 4KB；
- 页表项 4B。
虚拟页数：
页表大小：
每个进程都可能需要一个很大的连续页表。
但现实中进程可能只用了地址空间的一小部分。
例如：
4GB 虚拟空间
低地址：程序
中间：大量未使用
高地址：栈为什么为没用到的区域准备页表项？
于是把页表本身再分页。
二十九、二级页表怎么理解？
逻辑地址：
┌────────┬────────┬────────────┐
│一级页号│二级页号│ 页内偏移 │
└────────┴────────┴────────────┘过程：
一级页号
↓
一级页表
↓
找到某张二级页表在哪
↓
二级页号
↓
二级页表
↓
找到数据页框
↓
页内偏移
↓
物理地址所以：
一级页表项保存的是对应二级页表所在的物理页框号。
这是配套模拟题直接考过的点。
三十、多级页表解决了什么，又付出了什么？
这是资料直接要求思考的问题。
优点
不用一次建立巨大单级页表。
只为实际使用的地址区建立下级页表。
所以：
节省页表占用的内存。
缺点
访问次数增加。
二级页表、没有 TLB：
1. 查一级页表
2. 查二级页表
3. 访问真正数据需要 3 次主存访问。
所以资料总结：
多级页表以更复杂、更慢的地址转换，换取更低的页表空间开销。
三十一、分段存储管理 ★★★
分页是从计算机管理内存角度出发。
分段则从程序员看到的程序逻辑结构出发。
一个程序天然包含：
主程序
函数A
函数B
全局数据
栈
...于是：
段0 主程序
段1 函数A
段2 数据
段3 栈不同段长度可以不同。
三十二、分段逻辑地址
分段地址不是单纯一个连续的线性数，而由：
段号 S
+
段内偏移 W组成。
即：
例如：
(3, 500)意思是：
第 3 段中的第 500 个字节。
资料明确将分段地址称为二维地址，并强调段号和段内偏移共同定位一个地址。
三十三、段表
例如：
| 段号 | 段基址 | 段长 |
|---|---|---|
| 0 | 10000 | 3000 |
| 1 | 30000 | 1000 |
| 2 | 50000 | 6000 |
访问：
先检查：
合法。
再计算：
三十四、为什么段表必须保存“段长”？
因为不同段大小不同：
段0：3000
段1：1000
段2：6000如果访问：
虽然：
能算出来，但其实已经越出第 1 段。
所以先必须检查：
此外还要检查：
资料将这两步称为分段系统的地址越界保护。
三十五、分页和分段的核心区别 ★★★★
| 分页 | 分段 | |
|---|---|---|
| 划分依据 | 系统固定划分 | 程序逻辑结构 |
| 单位大小 | 固定 | 可变 |
| 对程序员 | 基本透明 | 有逻辑意义 |
| 地址 | 页号+页内偏移 | 段号+段内偏移 |
| 外部碎片 | 无 | 有 |
| 内部碎片 | 有 | 通常无 |
| 共享保护 | 可以 | 更自然 |
| 每个逻辑单元 | 无明确语义 | 代码段、数据段等 |
一句话：
分页解决“内存怎么高效装”；分段解决“程序怎么按逻辑组织”。
三十六、段页式存储管理 ★★★
那能不能：
程序员看起来按段
+
物理内存实际上按页当然可以。
这就是段页式。
先分段：
段0
段1
段2每段再分页：
段0：
页0 页1 页2
段1：
页0 页1于是逻辑地址：
┌──────┬──────┬──────────┐
│ 段号 │ 页号 │ 页内偏移 │
└──────┴──────┴──────────┘即：
三十七、段页式地址转换
这是重点理解过程。
每个进程：
一张段表每个段：
一张页表所以：
逻辑地址 (S,P,W)
↓
段号 S
↓
段表
↓
找到该段页表的位置
↓
页号 P
↓
该段页表
↓
页框号 b
↓
加/拼接 W
↓
物理地址一定记：
一个进程一张段表；一个段一张页表，所以一个进程可能有多张页表。
无 TLB 时：
访问段表
访问页表
访问真正数据通常需要 3 次主存访问。
三十八、学习页式、段式、段页式只抓三件事
资料自己给出了一个非常好的复习方法：
对三种管理方式，只需要牢牢掌握：
- 逻辑地址结构
- 页表/段表表项结构
- 寻址过程
例如：
| 类型 | 地址结构 | 表项 | 寻址 |
|---|---|---|---|
| 分页 | 页框号 | 页表→页框 | |
| 分段 | 基址+段长 | 段表→基址 | |
| 段页 | 段表→页表 | 段表→页表→页框 |
这样比死背几十句话有效得多。
三十九、为什么要虚拟内存？ ★★★★★
前面基本分页虽然允许：
进程物理上不连续但是传统管理仍有两个限制。
资料称为：
一次性
程序必须全部装进内存才能运行。
驻留性
程序一旦装进去，运行期间一直留在内存。
问题：
一个 10GB 程序，而物理内存只剩 5GB：
传统基本分页：
装不进去
→ 不能运行但程序真的会在某一个瞬间同时使用全部 10GB 内容吗？
通常不会。
所以产生虚拟内存。
四十、虚拟内存的理论基础：局部性原理 ★★★★★
1. 时间局部性
刚访问过的东西，近期很可能再次访问。
例如：
for (...)
sum += a;变量：
sum
a
循环控制变量会反复访问。
2. 空间局部性
访问某个地址以后，很可能访问附近地址。
例如：
for (i=0;i<n;i++)
sum += a[i];数组：
a[0],a[1],a[2],a[3]...连续存放。
因此访问 a[0] 后，很可能访问附近的 a[1]。
资料明确将时间局部性、空间局部性作为虚拟内存的理论基础。
四十一、虚拟内存真正的思想
既然程序在某段时间只集中使用少量页面：
只把现在需要的页面放进内存。
例如进程有：
1000页当前只使用：
5,6,7,20那么内存中可能只放：
5 6 7 20剩余 996 页：
留在外存如果以后访问第 300 页：
发现不在内存
↓
把第300页从磁盘调入
↓
继续运行这就是请求分页。
四十二、虚拟地址空间不一定大于物理空间
408 很喜欢这类语言陷阱。
错误说法：
“虚拟地址空间总是大于物理地址空间。”
不是。
虚拟地址空间最大大小主要取决于：
虚拟地址位数物理地址空间取决于：
物理地址位数二者没有“虚拟一定大于物理”的数学必然关系。配套题也专门把这一说法列为错误项。
实际虚拟内存技术允许：
一个进程的虚拟地址空间可以大于当前实际物理内存。
“可以”不等于“必须”。
四十三、请求分页系统 ★★★★★
基本分页页表可能只是：
页号 → 页框号请求分页需要知道更多信息：
| 字段 | 作用 |
|---|---|
| 页框号 | 当前在哪个页框 |
| 状态位 | 页面在不在内存 |
| 访问字段 | 最近访问情况 |
| 修改位 | 是否被修改 |
| 外存地址 | 页面在磁盘哪里 |
资料中特别列出这几个字段。
四十四、状态位 P
例如：
| 页号 | 页框 | P |
|---|---|---|
| 0 | 5 | 1 |
| 1 | — | 0 |
| 2 | 8 | 1 |
访问页 2：
P=1
→ 在内存访问页 1：
P=0
→ 不在内存
→ 缺页异常四十五、修改位 M 为什么重要？
假如一个页面从磁盘读进来以后：
从未修改现在要淘汰。
磁盘上原来的内容和内存里完全相同。
直接扔掉即可：
不写磁盘如果页面被改过：
内存内容 ≠ 磁盘内容淘汰前必须：
写回磁盘所以：
修改过的页比干净页更“贵”。
这直接导致后面的改进 CLOCK 算法。
四十六、缺页异常完整处理流程 ★★★★★
这是本章必须真正理解的过程。资料的考点追踪显示缺页处理在 2011、2013、2014、2020、2022 等年份被多次考查。
CPU 访问逻辑地址：
虚拟地址
↓
TLB
┌──────┴──────┐
命中 未命中
↓ ↓
得到页框 查页表
↓
P = ?
┌─────┴─────┐
P=1 P=0
↓ ↓
得页框 缺页异常
↓
操作系统接管
↓
内存是否有空闲页框？
┌──────┴──────┐
有 无
↓ ↓
直接用 选牺牲页
↓
脏页要写回
↓
调入目标页面
↓
修改页表/TLB
↓
重新执行访存四十七、缺页不是普通的函数调用
缺页是由硬件发现：
P=0然后触发异常。
此时：
用户程序
↓
异常
↓
内核处理
↓
磁盘 I/O
↓
页面装入
↓
重新执行导致缺页的指令/地址转换资料特别指出两点：
1. 缺页发生在指令执行期间
并不是一定等到指令执行结束以后。
2. 一条指令可能多次缺页
例如某条复杂指令：
指令本身跨2页
源操作数跨2页
目的操作数跨2页最多可能涉及：
个页面，因此可能多次触发缺页。
四十八、三个异常情况一定区分
情况一：TLB miss
TLB 里没有
页在内存正常查页表即可。
情况二：Page Fault
页表存在这个页
但 P=0页面合法，只是当前没在内存。
需要从磁盘调入。
情况三：地址越界
例如进程总共只有 10 页，却访问：
第20页这是：
非法地址访问不是“把第20页从磁盘调进来”。
因为这个页压根不属于该进程合法地址空间。
四十九、页框、驻留集与最小页框数 ★★★★
驻留集
一个进程当前占用的所有物理页框集合。
例如：
进程P驻留集：
{3, 7, 10, 18}驻留集大小：
为什么不能只给一个页框？
假如一条指令：
LOAD X指令自己在页面 A。
操作数 X 在页面 B。
至少可能需要：
A + B两个页面。
资料给出的典型结论是：
单地址 + 直接寻址
至少 2 页框：
指令
数据一级间接寻址
至少 3 页框：
指令
指针
数据复杂情况下，一条指令和两个操作数各跨两个页面：
最少可能需要 6 个页框。
五十、驻留集是不是越大越好？
不是。
驻留集太小：
频繁缺页
↓
频繁磁盘IO
↓
性能暴跌驻留集太大：
这个进程占很多页框
↓
别的进程页框减少
↓
系统并发进程数降低所以是一个平衡问题。
五十一、三种页框分配/置换策略 ★★★
资料指出 2015 年统考直接考过名称。
1. 固定分配 + 局部置换
给进程 P：
4 个页框运行过程中始终 4 个。
缺页时：
只能淘汰 P 自己的页面。
2. 可变分配 + 全局置换
P 缺页：
有空闲框 → 再给 P 一个
没有空闲框
→ 可以从整个系统所有进程的页框中选一个淘汰所以 P 的驻留集可能变大或变小。
3. 可变分配 + 局部置换
正常缺页时先在自己里面替换。
但系统还会根据缺页率调整：
缺页率过高 → 多给一些框
缺页率过低 → 回收一些框资料还特别提醒：
“固定分配 + 全局置换”这一组合在这里不成立，因为全局置换可能改变某进程拥有的页框数量，与“固定”矛盾。
五十二、页面置换算法 ★★★★★
这是和分页地址转换并列的超级重点。
当：
发生缺页
+
没有空闲页框必须问：
淘汰谁？
这就是页面置换算法。
四大算法：
OPT
FIFO
LRU
CLOCK五十三、OPT 最佳置换算法
思想：
淘汰“未来最长时间不会被访问”的页面。
例如当前：
内存：A B C从现在往未来看：
A 2步以后访问
B 100步以后访问
C 5步以后访问那么淘汰：
B因为未来最久才用它。
OPT 为什么最好？
理论上每一步都作出最理想选择，所以缺页率最低。
为什么实际不能用？
因为：
操作系统不知道未来的页面访问序列。
所以它主要用于：
作为理论最优基准，评价其他算法。
资料中的典型序列配 3 个页框，OPT 共发生 9 次缺页。
五十四、FIFO 先进先出 ★★★★
思想：
谁最早进入内存，就淘汰谁。
例如：
进入顺序：
A → B → C缺页后：
淘汰 A简单。
但最大问题：
最早进来
≠
最近没用A 虽然来得早，但可能是一个一直频繁访问的热点页。
FIFO 完全不管。
五十五、FIFO 的超级考点：Belady 异常
正常直觉：
页框越多，缺页应该越少。
FIFO 却可能出现：
页框更多
↓
缺页反而更多资料例子：
页面序列：
3,2,1,0,3,2,4,3,2,1,0,43 个页框：
次缺页。
4 个页框：
次缺页。
这就是 Belady 异常。
在教材所重点比较的 FIFO、LRU、OPT 中：
- FIFO 可能；
- LRU 不会；
- OPT 不会。
五十六、LRU 最近最久未使用 ★★★★★
全称：
Least Recently Used
思想：
淘汰“过去最长时间没有访问”的页面。
注意与 OPT 的区别。
OPT
看：
未来谁未来最晚用。
LRU
看：
过去谁已经最久没用。
资料专门强调：
OPT 面向未来，而 LRU 根据过去的访问历史进行判断。
五十七、LRU 怎么手算？
当前内存：
1 2 3现在访问：
4缺页。
向访问序列左边倒着看：
谁最近一次出现离当前位置最远？假设：
... 2 ... 1 ........ 3 ... | 4最近：
3 最近
1 次之
2 最久淘汰：
2所以手算 LRU 不一定要真的维护计时器。
口诀：
缺页时向左找，最后出现最远的淘汰。
五十八、FIFO 与 LRU 手算最容易错在哪里？
假设命中一个已经在内存中的页面。
LRU
它的“最近使用时间”必须更新。
FIFO
进入内存的时间不变。
例如：
FIFO 队列：
A B C访问 A 命中。
FIFO 顺序还是：
A B C不是：
B C A因为 FIFO 看：
什么时候进入内存。
LRU 才看：
什么时候最近被访问。
五十九、资料中的典型置换题
访问序列：
5,4,3,2,4,3,1,4,3,2,1,53 个页框。
资料给出的计算结果：
做这类题建议画：
| 访问 | 框1 | 框2 | 框3 | 缺页？ |
|---|---|---|---|---|
| 5 | 5 | ✓ | ||
| 4 | 5 | 4 | ✓ | |
| 3 | 5 | 4 | 3 | ✓ |
| ... |
千万不要纯心算。
六十、缺页率怎么算？
定义非常直接：
例如资料中的 LRU 题：
页面序列一共：
次访问。
3 页框时缺页：
次：
4 页框时缺页：
次：
注意：
一开始空页框时把第一页装进去，同样算缺页。
但通常：
初始装入是否算“页面置换”则不是一回事。
初始缺页：
缺页 ✓
淘汰旧页 ✗六十一、CLOCK 时钟算法 ★★★★★
LRU 效果很好，但精确实现 LRU 成本较高。
所以设计一个便宜的近似算法：
CLOCK / Second Chance。
每页增加一个访问位：
访问页面：
所有页框组成环：
A
↗ ↘
D B
↖ ↙
C有一个时钟指针。
六十二、简单 CLOCK 算法过程
发生缺页需要淘汰时：
指针指向
直接淘汰。
指针指向
说明最近访问过：
A = 1 → 改成 0然后：
指针向后走相当于：
再给它一次机会。
所以又叫 Second Chance。
资料的具体规则也是：
六十三、CLOCK 为什么近似 LRU？
LRU 精确问：
谁已经最久没访问？
CLOCK 不知道精确时间，只知道：
最近访问过？ 1
最近没访问？ 0于是优先淘汰：
0相当于用 1 bit 的粗略历史逼近 LRU。
六十四、改进型 CLOCK ★★★★★
简单 CLOCK 只考虑：
但是前面说了：
脏页淘汰比干净页贵。
所以再加：
得到：
四类：
| 类别 | 含义 | 淘汰优先级 | ||
|---|---|---|---|---|
| 1 | 0 | 0 | 没访问、没修改 | 最优 |
| 2 | 0 | 1 | 没访问、修改过 | 次优 |
| 3 | 1 | 0 | 最近访问、干净 | 较差 |
| 4 | 1 | 1 | 最近访问、脏 | 最差 |
记忆：
先“不访问”，再“不修改”。
因为：
- ：预计短期不太会再用；
- ：淘汰不用写磁盘。
六十五、改进 CLOCK 扫描过程
资料给出的逻辑是：
第一轮寻找：
找到马上淘汰。
如果没有，再寻找：
并在这一过程中把经过页面的 清零。
之后再重新寻找：
再没有就找：
最终一定能选出来。
六十六、四大页面置换算法总结
| 算法 | 看什么 | 优点 | 缺点 |
|---|---|---|---|
| OPT | 未来 | 理论最优 | 不可实现 |
| FIFO | 进入时间 | 最简单 | 性能差、可能 Belady |
| LRU | 过去访问时间 | 接近 OPT | 实现开销大 |
| CLOCK | 访问位 | 性价比好 | 只是近似 LRU |
| 改进 CLOCK | 访问位+修改位 | 兼顾使用与 I/O | 扫描更复杂 |
从 408 复习角度：
一定会做 FIFO、LRU、CLOCK 的过程题。
六十七、抖动 / 颠簸
这是理解型内容。
假设一个进程正常运行至少需要经常使用：
A B C D但只给它两个页框。
于是：
访问A → 调入A
访问B → 调入B
访问C → 淘汰A
访问D → 淘汰B
访问A → 又把A调回来
访问B → 又把B调回来
...CPU 大量时间不再计算，而是在：
缺页
读磁盘
写磁盘
换页这叫抖动。
资料定义为：
刚换出去的页面很快又要换入，刚换入的页面又很快被换出，根本原因是进程拥有的物理块过少。
六十八、工作集怎么理解？
这一节在资料目录中标有 *，所以对于 408 主线复习，理解思想即可。
可以把工作集简单理解成：
进程最近一段时间真正活跃、经常使用的那些页面。
例如最近运行阶段主要反复访问：
1,2,4,5那么这几个页面就是当前活跃集合的核心。
如果给它的页框连这些活跃页都容不下：
频繁互相替换
↓
抖动所以其思想本质是：
至少让进程当前真正需要的一组页面比较稳定地驻留内存。
六十九、页面缓冲算法与页框回收
这一块不是前面地址转换、页面置换那么核心，但理解系统为什么这样设计很有帮助。
一个页面被选中“淘汰”，不一定马上彻底丢掉。
系统可以维护：
空闲页面链表
修改页面链表干净页
如果页面没修改：
先放进空闲页框链表数据甚至可以暂时保留。
如果刚淘汰，马上又有人需要它：
直接捡回来不用读磁盘。
脏页
如果页面已经修改：
先放修改页面链表不要每淘汰一页就立即进行一次磁盘写。
可以积累一批后：
批量写盘减少磁盘 I/O 次数。资料明确指出页面缓冲算法通过这两类链表降低换入换出频率，并让简单 FIFO 等算法也能获得较好的实际表现。
七十、内存映射文件 mmap ★★★
这是近年需要重视的新考点，资料标记为 2025 考点。
传统文件访问：
read(...)
write(...)内存映射则可以把：
磁盘文件映射到：
进程虚拟地址空间的一段区域之后：
p[i]表面上像读内存。
底层：
第一次访问对应页
↓
可能缺页
↓
OS从文件调入程序无需自己关心具体磁盘读操作。
七十一、mmap 与共享内存
假设进程 A：
虚拟页 100进程 B：
虚拟页 500可以让：
A 虚页100 ─┐
├──→ 同一物理页框
B 虚页500 ─┘于是 A 修改以后，B 访问相同共享映射可看到对应内容。
因此 mmap 两个主要作用：
- 文件像内存一样访问；
- 方便多个进程共享同一文件/物理页。
七十二、虚拟存储器性能受什么影响？ ★★★★
资料明确标记这一部分在 2020、2022 被考查。核心指标：
缺页率。
影响缺页率和总体性能的几个因素：
页面大小
页框数量
页面置换算法
页面写回策略
程序局部性七十三、页面大小是不是越大越好？
不是。
页面小
优点：
内部碎片小缺点：
页数多
→ 页表大
→ 管理开销大
→ 更多页表项页面大
优点：
页数少
→ 页表小
→ 一次磁盘I/O传更多相邻数据缺点：
页内碎片大所以页面大小是权衡。
七十四、页框数是不是越多越好？
对某单个进程：
页框增加
→ 通常缺页率下降但达到某个程度后：
再增加
→ 缺页率改善已经很小与此同时：
你多占一个页框
→ 其他进程少一个页框
→ 系统并发度降低所以不是无限多越好。
七十五、程序局部性为什么能极大影响缺页率？
例如二维数组按行存储：
int a[128][128];程序 A：
for (j=0; j<128; j++)
for (i=0; i<128; i++)
use(a[i][j]);按列访问。
内存实际却：
a[0][0] a[0][1] ... a[0][127]
a[1][0] a[1][1] ...连续访问经常跨到不同页面。
如果改成按行：
for (i=0; i<128; i++)
for (j=0; j<128; j++)
use(a[i][j]);一旦把包含当前行的页调进来，可以连续访问大量元素。
配套资料中的类似题甚至出现：
级别的页故障与约
次页故障的巨大差别。
所以：
程序的数据访问顺序本身就是虚拟内存性能的重要因素。
七十六、本章最容易混的十组概念
1. 页 vs 页框
页：进程逻辑地址空间
页框：物理内存大小相同。
2. 页号 vs 页框号
页号：虚拟
页框号：物理页表完成：
页号 → 页框号3. TLB miss vs page fault
TLB miss：
映射不在快表
Page fault：
页面不在物理内存4. 内部碎片 vs 外部碎片
内部：
分给我的空间里面浪费
外部：
空闲空间散在分区之间5. 页表 vs TLB
页表：
完整映射
TLB：
近期页表项缓存6. 基本分页 vs 请求分页
基本分页：
运行前把全部页面装入请求分页：
需要哪个页面再装哪个7. 分页 vs 分段
分页：
固定大小
系统管理
提高物理内存利用率分段：
可变大小
反映程序逻辑
利于保护共享8. OPT vs LRU
OPT：看未来
LRU：看过去9. FIFO vs LRU 命中后的处理
FIFO：
命中不改变进入顺序LRU：
命中意味着它刚刚被使用，历史必须更新10. 缺页次数 vs 页面置换次数
初始空框：
访问新页
→ 缺页
→ 直接装入有：
缺页但是没有：
页面置换所以：
七十七、408 做页表综合题的固定流程 ★★★★★
遇到任何页表、TLB、Cache、请求分页混合题，建议严格按照这个顺序。
Step 1：先拆虚拟地址
页面大小：
则：
低 k 位 = 页内偏移
其余高位 = 虚页号Step 2：先问 TLB
TLB hit？是：
直接获得页框否：
访问页表Step 3：检查页表有效/存在位
页面在内存。
缺页。
Step 4：缺页时看有没有空闲页框
有：
直接装入没有：
执行页面置换算法Step 5：若淘汰页脏
需要写回磁盘。
Step 6：调入所需页
更新：
页表
TLB
访问位
修改位Step 7：重新执行导致缺页的访问
最终：
这套流程基本可以覆盖本章最重要的综合计算题。
七十八、408 页面置换题固定流程 ★★★★★
给：
页面序列
页框数
算法第一步画表。
例如：
序列：
1 2 3 4 2 1 ...3 页框：
| 访问 | 框1 | 框2 | 框3 | 缺页 |
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 |
然后：
FIFO
记录：
最早进入内存的是谁。
LRU
记录：
最近最久没有使用的是谁。
OPT
看：
后面谁最晚出现。
CLOCK
维护：
访问位
+
时钟指针不要跳步骤。
七十九、本章重要程度排序
结合资料中的考点追踪，建议按下面优先级复习。
| 级别 | 内容 |
|---|---|
| S | 分页地址结构与虚实地址转换 |
| S | 页表、TLB、多级页表 |
| S | 请求分页、缺页异常处理 |
| S | FIFO、LRU、OPT、CLOCK |
| A | 动态分区 FF/NF/BF/WF |
| A | 页框分配、驻留集、缺页率 |
| A | 内部/外部碎片 |
| B | 分段、段页式 |
| B | 虚拟内存局部性 |
| B | mmap |
| C | 页面缓冲、页框回收、抖动/工作集 |
其中从资料中的考点追踪看：
- 动态分区算法：2019、2024 等；
- TLB 性能：2009；
- 缺页处理：2011、2013、2014、2020、2022；
- LRU：2009、2015、2019、2025；
- CLOCK：2010、2012 等；
- 页框分配策略：2015；
- 最小页框数：2025；
- 内存映射文件：2025；
- 虚拟存储性能：2020、2022。
八十、最后把第三章压缩成一条知识链
你如果能把下面这条链完全讲出来，第三章主干基本就通了：
多道程序共享内存
↓
必须分配、保护、地址转换
↓
连续分配
↓
固定分区 → 内部碎片
动态分区 → 外部碎片
↓
分页
↓
页 / 页框 / 页表
↓
虚拟地址
[页号 | 页内偏移]
↓
页号查页表
↓
页框号
↓
物理地址
↓
普通页表太慢
↓
TLB
↓
普通页表太大
↓
多级页表
↓
程序逻辑结构又不明显
↓
分段 / 段页式
↓
但传统分页仍要求全部装入
↓
局部性原理
↓
虚拟内存
↓
请求分页
↓
页面不在内存
↓
缺页异常
↓
有空闲框 → 调入
无空闲框 → 页面置换
↓
OPT / FIFO / LRU / CLOCK
↓
缺页过多 → 抖动
↓
调整驻留集、改善局部性、
选择更好的置换/写回策略最需要真正做到“看到题就会做”的，是这四套流程：
这四块掌握以后，第 3 章的大多数选择题和综合分析题就有了稳定的解题框架。