主题
第五章 内存管理：分页、分段与虚拟内存
1. 为什么需要地址转换
第二章说过，每个进程都以为自己独占一条从 0 开始的内存。这当然是假象——物理内存只有一条，凭什么每个进程都觉得自己从地址 0 开始？
答案：程序里写的地址是逻辑地址（也叫虚拟地址，程序视角的门牌号），真正访问内存时由硬件把它翻译成物理地址（内存条上的真实位置）。这次翻译不是多此一举，它一口气解决三个问题：
- 重定位：程序编译时不知道自己将来被装进内存哪个位置。有了翻译层，程序统一按"从 0 开始"编址，装到哪儿都能跑。
- 保护：每个进程只能通过自己的翻译表访问自己的内存，翻译表里没有的地址一律拦截——进程再嚣张也摸不到别人的数据。
- 共享：想让两个进程共用一段代码（比如同一个库），只需让两张翻译表指向同一块物理内存。
一句话点透：逻辑地址是操作系统发给每个进程的"专属幻觉"，翻译由硬件中的内存管理单元 MMU 在每次访存时自动完成。
2. 连续分配与碎片
最朴素的做法：给每个进程分一段连续的物理内存。分法有固定分区（预先切成固定大小的格子）和动态分区（按需切割）。动态分区释放回收后，内存里会留下大小不一的空闲块，于是有了"挑哪块"的策略：
| 策略 | 规则 | 优缺点 |
|---|---|---|
| 首次适应 | 从头找，遇到第一块够大的就用 | 简单，通常综合表现不差；低地址端易碎 |
| 最佳适应 | 挑能装下的最小空闲块 | 听着节省，实际制造大量装不了东西的小碎屑 |
| 最坏适应 | 挑最大的空闲块切 | 剩下的仍较大还能用；但大块很快被消耗殆尽 |
注意反直觉结论：最佳适应不是最佳——它专门产生极小的、几乎无法再利用的空闲碎屑。
2.1 内碎片与外碎片辨析（高频考点）
| 碎片类型 | 定义 | 产生场景 | 白话比喻 |
|---|---|---|---|
| 内碎片 | 分给进程的块内部用不完的部分 | 固定分区、分页 | 4 人开了 6 人包间，空 2 座但别人不能坐 |
| 外碎片 | 空闲区太零散，总量够但没有一块连续的够大 | 动态分区、分段 | 停车场空位总面积够停卡车，可惜全是零散小格 |
记法：分固定大小的都产生内碎片，按需分配连续区域的都产生外碎片。外碎片可用"紧凑"（把进程挪到一起拼出大空闲区）缓解，但搬家开销大。想根治外碎片，就要放弃"连续"这个执念——这就引出了分页。
3. 分页机制：化整为零
思想：把逻辑地址空间切成固定大小的页（如 4KB），把物理内存切成同样大小的页框（块）。任何一页可以放进任何一个页框，页与页在物理上不必连续。每个进程一张页表，记录"第几页放在了第几框"。
外碎片就此消失（所有块一样大，任何空框都能用）；代价是每个进程最后一页平均浪费半页——退回了少量内碎片。这笔交易非常划算。
3.1 地址转换：手算例题
逻辑地址被机械地拆成两段：页号 = 逻辑地址 ÷ 页大小（取商），页内偏移 = 逻辑地址 mod 页大小（取余）。翻译时页号换成页框号，偏移原样拼接。
例题：页大小 1KB（1024 字节），页表为：0 号页 → 2 号框，1 号页 → 5 号框，2 号页 → 8 号框。求逻辑地址 2500 的物理地址。
- 页号 = 2500 ÷ 1024 = 2（商），页内偏移 = 2500 − 2 × 1024 = 452。
- 查页表：2 号页在 8 号框。
- 物理地址 = 8 × 1024 + 452 = 8644。
若给的是二进制/十六进制，套路相同：页大小 2 的 n 次方，则逻辑地址低 n 位是偏移、高位是页号，翻译时只换高位、低位照抄。
3.2 页表放哪儿：TLB 为什么能加速
页表本身放在内存里。这带来一个尴尬：每访问一个数据，都要先访存查页表、再访存取数据——访存次数翻倍。
解药是快表 TLB（Translation Lookaside Buffer，白话：MMU 里的一小块超高速缓存，存最近用过的"页号→框号"对照条目）。访存时先查 TLB：命中则直接得到框号，不用再读内存里的页表；未命中才去查页表，并把结果填入 TLB 备用。
TLB 为什么有效？因为程序访存有局部性——短时间内反复访问同一批页，几十条 TLB 条目就能覆盖绝大多数访问。设 TLB 命中率 90%、查 TLB 忽略不计、访存一次 100ns，则平均访存时间 = 0.9 × 100 + 0.1 × 200 = 110ns，远优于无 TLB 的 200ns。
多级页表一句话：进程地址空间很大时页表本身太大，就把页表也切页、再建一张"页表的页表"，按需加载，用时间换空间。
4. 分段与段页式
4.1 分段：按逻辑意义划分
分页是操作系统按固定大小机械切割，程序员无感。分段则按程序的逻辑单元划分：代码段、数据段、栈段各成一段，每段长度不同，逻辑地址 =（段号，段内偏移）二维表示。段表记录每段的起始地址（基址）和长度（界限），翻译时检查偏移不得越过段长。
4.2 分页 vs 分段对照表（高频考点）
| 对比项 | 分页 | 分段 |
|---|---|---|
| 划分依据 | 物理需要，固定大小机械切 | 逻辑意义，按程序结构切 |
| 大小 | 页大小固定，由系统定 | 段长不定，由程序决定 |
| 对程序员 | 透明，不可见 | 可见，编程可按段引用 |
| 地址形式 | 一维：一个数字拆页号加偏移 | 二维：必须给出段号和段内偏移 |
| 碎片 | 只有少量内碎片 | 有外碎片，无内碎片 |
| 共享与保护 | 以页为单位，不贴合逻辑边界 | 以段为单位，天然贴合，更方便 |
段页式：先按逻辑分段，段内再分页装入——共享保护看段、内存利用看页，两全其美；代价是逻辑地址要经过段表、页表两次查表，访存次数更多。
5. 虚拟内存：借磁盘扩内存
到目前为止仍假设进程整个装入内存。但观察发现：程序运行遵循局部性原理——时间局部性（刚用过的很快还会再用，如循环变量）与空间局部性（用了某处，附近的很快也会用到，如顺序扫描数组）。既然任一时刻真正活跃的只是一小部分页，何必全部装入？
虚拟内存由此而来：只装入当前需要的页，其余留在磁盘上；访问到不在内存的页时再临时调入。这就是请求分页。效果：进程看到的地址空间可以远大于物理内存，更多进程得以同时驻留内存。
虚拟内存的三个特征：多次性（作业分多次调入）、对换性（页可换入换出）、虚拟性（逻辑容量大于物理容量）。它的物质基础是"页表 + 缺页中断机制 + 磁盘对换区"。
6. 缺页中断处理流程
访问的页不在内存时，MMU 触发缺页中断（属于第一章讲的内中断/异常），由操作系统补救：
两个细节常考：其一，牺牲页只有被修改过（脏页）才需写回磁盘，没改过的磁盘上本来就有副本，直接覆盖即可——页表里的"修改位"就是干这个的；其二，处理完后重新执行引起缺页的那条指令，而不是跳到下一条。
7. 页面置换算法：手算例题
内存满了要"挑谁滚蛋"，挑得不好，刚踢走的马上又要用。约定例题统一使用引用串 7 0 1 2 0 3 0 4 2 3 0 3，内存 3 个页框，初始为空。注意：首次装入某页也算一次缺页。
7.1 OPT 最佳置换：理论天花板
规则：淘汰将来最长时间不会被访问的页。需要预知未来，无法实现，只作为衡量其他算法的标尺。
| 访问 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 内存 | 7 | 7 0 | 7 0 1 | 2 0 1 | 2 0 1 | 2 0 3 | 2 0 3 | 2 4 3 | 2 4 3 | 2 4 3 | 2 0 3 | 2 0 3 |
| 缺页 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 |
推演关键步：访问 2 时淘汰 7（7 此后再不出现）；访问 3 时淘汰 1（1 再不出现）；访问 4 时比较未来——2 在第 9 次、3 在第 10 次、0 在第 11 次才被用到，0 最远，淘汰 0；第 11 次访问 0 时缺页，淘汰再也不用的 4。共缺页 7 次。哪怕 0 将来还要用，OPT 也照淘不误——它只看"谁最晚才被用"，不看"还用不用"。
7.2 FIFO 先进先出：谁来得早谁走
规则：淘汰在内存中待得最久的页。实现只需一个队列，但"住得久"不等于"没用了"。
| 访问 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 内存 | 7 | 7 0 | 7 0 1 | 2 0 1 | 2 0 1 | 2 3 1 | 2 3 0 | 4 3 0 | 4 2 0 | 4 2 3 | 0 2 3 | 0 2 3 |
| 缺页 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 |
共缺页 10 次。注意第 6、7 次：淘汰 0 之后紧接着又要访问 0，只好再把 3 踢换回 0——FIFO 的典型愚蠢时刻。
Belady 异常：FIFO 独有的怪病——给它更多页框，缺页反而可能更多（经典反例引用串 1 2 3 4 1 2 5 1 2 3 4 5：3 框缺 9 次，4 框缺 10 次）。OPT 和 LRU 永远不会发生 Belady 异常。
7.3 LRU 最近最久未使用：用过去预测未来
规则：淘汰最长时间没被访问过的页。依据正是局部性原理：最近没用的，近期大概率也不用——这是"用历史模仿 OPT"。
| 访问 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 内存 | 7 | 7 0 | 7 0 1 | 2 0 1 | 2 0 1 | 2 0 3 | 2 0 3 | 4 0 3 | 4 0 2 | 3 0 2 | 3 0 2 | 3 0 2 |
| 缺页 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 | 缺 |
第 8 次访问 4 时，最久未用者是 2？查历史：最近使用序为 0（第 7 次）、3（第 6 次）、2（第 4 次），故淘汰 2；第 9 次访问 2 又缺，淘汰最久未用的 3；第 10 次访问 3 再缺，淘汰 4。共缺页 9 次。手算技巧：从当前位置向左回看，最晚出现的那个页就是牺牲品。
LRU 效果好但实现贵——严格实现要给每页记时间戳或维护访问栈，硬件开销大，于是有了下面的近似版。
7.4 Clock 时钟算法：LRU 的廉价近似
规则：所有页排成环，每页一个访问位（被访问过置 1）。指针扫描：遇到访问位为 1 的，清零并放它一马、指针前移；遇到 0 的，就淘汰它。白话：给每页一次缓刑机会，第二圈还没被用过就出局。改进型再加修改位，优先淘汰"既没被访问又没被修改"的页，省一次写盘。
| 算法 | 本例缺页数 | 定位 |
|---|---|---|
| OPT | 7 | 理论最优，不可实现，用作标尺 |
| FIFO | 10 | 最容易实现，性能差，有 Belady 异常 |
| LRU | 9 | 性能接近 OPT，实现开销大 |
| Clock | 介于 FIFO 与 LRU 之间 | 工程折中，实际系统主流选择 |
8. 抖动与工作集
抖动（颠簸）：分给进程的页框太少，装不下它当前活跃的页集合，于是刚换出的页马上又被访问——系统把绝大部分时间花在换页的磁盘 I/O 上，CPU 利用率骤降。危险的连锁反应：CPU 利用率低 → 系统以为负载不足 → 调入更多进程 → 每个进程页框更少 → 抖动更凶。
工作集：进程在最近一个时间窗口内实际访问的页面集合，即"当前活跃页"的度量。防抖动的原则：分给进程的页框数不低于其工作集大小；内存装不下这么多进程的工作集，就减少多道程序数量（挂起部分进程），而不是继续硬塞。
9. 本章要点回顾
| 主题 | 必须记住的结论 |
|---|---|
| 地址转换 | 解决重定位、保护、共享三件事，由 MMU 硬件完成 |
| 碎片 | 固定切割产生内碎片，连续按需分配产生外碎片；最佳适应不是最佳 |
| 分页手算 | 页号取商、偏移取余；偏移位数由页大小决定，翻译只换高位 |
| TLB | 缓存页表条目，靠局部性获得高命中率，减少访存次数 |
| 分页 vs 分段 | 分页固定、透明、一维、内碎片；分段逻辑、可见、二维、外碎片 |
| 虚拟内存 | 局部性原理是理论根基；多次性、对换性、虚拟性 |
| 缺页处理 | 脏页才写回；处理完重新执行原指令 |
| 置换算法 | OPT 标尺、FIFO 有 Belady 异常、LRU 近似最优、Clock 工程折中 |
| 抖动 | 页框少于工作集所致；解法是减少并发进程数而非加大调入 |
10. 做题提醒
- 数缺页次数时，初始装入也算缺页，别只数置换发生的次数。
- 页大小为 2 的 n 次方时，逻辑地址低 n 位直接抄到物理地址——考题若选项里偏移变了，直接排除。
- Belady 异常只属于 FIFO；说 LRU 或 OPT 有 Belady 异常的选项都是错的。
- 基本分页系统一次访存的数据访问需要 2 次访问内存（查页表 + 取数据），段页式要 3 次，TLB 命中则减为 1 次。
- 分页对程序员透明、地址一维；分段对程序员可见、地址二维——"分页地址是二维的"是经典错误表述。
- 缺页率高不一定是算法差，先看页框数是否小于工作集；抖动的对策是降低多道程序度，选"增加进程数"的选项必错。