OS-5/6 内存管理与虚拟内存

这一部分为什么存在？

多道程序要求多个进程同时驻留内存，立刻产生四个管理问题：

1. 放哪：进程大小不一、来来去去，内存这块蛋糕怎么切？
2. 找不到怎么办：程序编译时不知道将来被装在内存什么位置（逻辑地址产生于编译阶段，2011 年 30 题），运行时怎么重定位到实际物理地址？
3. 保护与共享：进程 A 不能改进程 B 的内存；但共享库又要能被多个进程共用（2019 年 28 题共享段）。
4. 不够怎么办：所有进程的总需求超过物理内存是常态。

主线因果链：连续分配 → 产生碎片 → 离散分配（分页/分段）→ 离散+重定位使“部分装入”成为可能 → 虚拟内存 → 缺页与置换 → 置换失控导致抖动 → 工作集模型。地址转换链条（页表/TLB/Cache）本身见 X-1，本模块聚焦每代方案“为什么取代上一代”。

flowchart TD
    A["多道程序：多进程同时驻留"] --> B["连续分配<br/>单一 / 固定分区 / 动态分区"]
    B --> C["碎片问题<br/>外部碎片 → 紧凑（要重定位）"]
    C --> D["离散分配：分页<br/>固定大小、无外部碎片"]
    C --> E["离散分配：分段<br/>按逻辑单位、便共享保护"]
    D & E --> F["段页式：先分段再分页"]
    D --> G["页表太大 → 多级页表"]
    D --> H["部分装入成为可能<br/>→ 请求分页（虚拟内存）"]
    H --> I["缺页 → 置换算法"]
    I --> J["置换过于频繁 → 抖动"]
    J --> K["工作集模型<br/>驻留集 ≥ 工作集"]

核心概念：

1. 连续分配与动态分区四算法

单一连续分配（单道）→ 固定分区（内部碎片）→ 动态分区：按需划分，但回收合并后产生外部碎片。选区策略四选一：

• 2010 年 28 题：55MB、最佳适应，分配 15/30、释放 15、再分 8/6 → 最大空闲分区 10MB。
• 2017 年 25 题：最佳适应 + 每次分配回收后重排空闲链。

2. 分页：用“切碎”消灭外部碎片

把内存和进程都切成定长的页框/页，任意页可放任意页框 → 无外部碎片，只剩最后一页的内部碎片。代价：

• 每次访存要先查页表（多一次访存）→ TLB（见 X-1）；
• 32 位 + 4KB 页 → 页表百万项且要连续存放 → 多级页表：把页表再分页，顶级页目录常驻，下级按需调入。优点是离散存放、节省连续空间——不是减少页表项总字节数（2014 年 32 题陷阱）；2010 年 29 题考页目录表项个数计算。
• 分段互补：页面对用户透明但破坏逻辑完整性，段按逻辑单位便于共享与保护（共享段只存一份、各进程段号不必相同——2019 年 28 题 B 项陷阱）；段页式 = 段内再分页，兼两者之长。

3. 虚拟内存：从“全装入”到“用到再装”

离散分配 + 动态重定位使“部分页面在内存即可运行”成立：

1. 页表项加有效位：在内存 → 正常转换；不在 → 缺页异常（内中断，CPU 在地址转换时检测到，2019 年 14 题）；
2. 陷入内核 → OS 查外存地址 → 找空闲页框（无则按置换算法淘汰，脏页先写回）→ 磁盘 I/O 读入 → 改页表、更新 TLB → 重新执行缺页指令；
3. 缺页处理中 OS 可能做的事：修改页表、磁盘 I/O、分配页框（2013 年 28 题：三者都可能）。

页面分配与置换策略的组合（2015 年 30 题陷阱）：

4. 置换算法与缺页率（细节见 X-1 §5，此处补 OS 视角）

OPT（理论基准）/ FIFO（队列，有 Belady 异常，2014-30）/ LRU（栈，最接近 OPT）/ Clock 与改进 Clock（硬件友好：只看 A 位/A、M 位，淘汰次序 (0,0)→(0,1)→(1,0)→(1,1)，2016-26）。影响缺页率的因素：置换算法、驻留集/工作集大小、进程数量——页缓冲队列长度不影响（2022 年 30 题）。

5. 抖动与工作集

多道程度过高 → 每进程驻留集 < 工作集 → 缺页率飙升 → 进程大量阻塞 → 调度程序误以为“并发度不够”再引入新进程 → 恶性循环，CPU 利用率雪崩。解决：降低多道程度（撤销部分进程，2011-29）、按工作集配足驻留集、局部置换防止一个进程拖垮全局。

分页 vs 分段（本模块第一易混对）：为什么易混——都是离散分配、都要查表转换。本质区别——页是物理定长切分（为消除碎片服务，用户无感），段是逻辑变长切分（为共享保护服务，用户可见）；分页地址一维、分段二维；分页内部碎片无外部碎片，分段反之。判别线索：题目给“页大小、页框”→ 分页计算；给“段号、共享、越界保护”→ 分段（2009-27：段号 8 位 → 最大段长 $2^{24}$；2016-28：段式地址转换 + 越界检查）。

连续分配 vs 离散分配：连续分配简单、无需页表但碎片无解（紧凑要停机搬移）；离散分配以“一次额外查表”换“零外部碎片 + 部分装入能力”——这次交换是虚拟内存的前提，是理解全章的总钥匙。

虚拟存储器 vs 虚拟地址（易混对）：虚拟地址是程序看到的地址空间（编址方式），虚拟存储器是“内存+外存+请求调入机制”构成的系统；前者是概念，后者是实现。判别线索：谈“32 位地址能编多大”→ 虚拟地址；谈“缺页、置换、驻留集”→ 虚拟存储器。

形态一：动态分区计算：2010-28（最佳适应后最大空闲分区）、2017-25（BF 重排链）、2019-32（最易碎片 = 最佳适应）、2024 年选择题（分配算法辨析）。

形态二：分页/分段地址计算：2009-27（最大段长 $2^{24}$）、2010-29（页目录表项数）、2016-28（段式转换与越界）、二级页表系列大题（2013-46、2015-46、2017-46、2020-46，见 X-1）。

形态三：请求分页大题：2009-46（TLB + LRU + 驻留集 2，逐地址算时间与物理地址）、2010-46（固定分配局部置换，FIFO 与 CLOCK 分别求 17CAH 的物理地址）、2012-45（扫描回收 + 空闲页框链的新式置换）、2014-46（数组访问的缺页与 TLB 次数）、2024-46（缺页次数与页故障地址）。

形态四：概念辨析：2011-29（抖动对策）、2011-30（逻辑地址形成于编译阶段）、2013-28（缺页处理的操作集）、2014-32（多级页表优点）、2015-30（固定分配不能配全局置换）、2016-29（窗口法求工作集）、2019-28（共享段）、2022-30（缺页率影响因素）。

做题触发词：看到“最大空闲分区”→ 按算法逐步模拟分配释放；看到“页目录号相同”→ 共享一个二级页表；看到“固定分配”→ 立刻检查置换策略是否局部；看到“CPU 利用率随并发度先升后降”→ 抖动。

来源：真题markdown/2009-2024统考真题.md 对应题号；复习资料 P3 §七。

• 向前依赖：OS-1 进程（内存管理的对象）、OS-0 中断（缺页是异常，X-2）。
• 向后引出：
  • 地址转换的硬件细节与 Cache → CO-3 / X-1；
  • 缺页要读磁盘 → 页面在外存的存放（交换区/文件）→ OS-7 文件系统；磁盘 I/O → OS-8 / CO-7 DMA；
  • 页面在磁盘与内存间换入换出 → 磁盘调度直接影响缺页代价（OS-8）；
  • 数据结构视角：多级页表是多级索引树，与文件系统的索引分配、B+ 树同构（X-8）。

1. 多道程序对内存提出了哪四个问题？（放哪、重定位、保护共享、不够怎么办）
2. 连续分配为什么必然产生碎片？内部、外部碎片分别由谁产生？
3. 动态分区四种选区算法各有什么病？哪个最容易产生碎片？
4. 紧凑能解决外部碎片，代价是什么？（搬移 + 动态重定位）
5. 分页怎么消灭外部碎片？引入了什么新代价？（查页表多一次访存、页表过大）
6. 页表太大怎么办？多级页表真正省的是什么？（连续空间，不是表项总量）
7. 分段存在的理由？为什么段号在共享时不必相同？
8. 离散分配为什么使“部分装入”成为可能？（页可离散放 + 动态重定位）
9. 有效位为 0 触发什么？缺页处理五步是什么？处理后从哪继续？
10. 固定分配为什么不能配全局置换？
11. 置换算法怎么选页？FIFO 的 Belady 异常为什么会发生？（见 X-1）
12. 缺页率受什么影响？页缓冲队列长度影响吗？
13. 抖动怎么形成恶性循环？为什么“撤销部分进程”是有效对策？
14. 本模块如何接入“虚拟地址 → TLB → Cache → 主存”的完整链条？（X-1）