虚拟内存
为什么需要虚拟内存
程序要运行，传统做法是把整个进程全部装入内存。但很多程序实际运行时只会用到其中一小部分代码和数据（比如错误处理分支、冷门功能），全部装入浪费物理内存，也限制了多道程序并发数。
虚拟内存的核心思想：只把进程当前真正需要的部分装入内存，其余仍留外存，需要时再调入。
这带来三个直接好处：
- 进程逻辑地址空间可以超过物理内存大小
- 物理内存中能同时容纳更多进程
- 每个进程的装入量减少，换入换出开销更小
局部性原理
虚拟内存能成立的前提是程序访问内存具有局部性——它不会把整个地址空间均匀扫一遍。
| 类型 | 含义 | 典型场景 |
|---|---|---|
| 时间局部性 | 刚访问过的数据/指令，不久后很可能再次被访问 | 循环体、频繁使用的变量 |
| 空间局部性 | 某地址被访问后，相邻地址很可能也被访问 | 顺序执行的指令、数组遍历 |
局部性保证了按需调页在多数场景下有效。但如果程序访问模式是随机跳跃（如哈希表全表扫描），缺页会极为频繁，虚拟内存反而拖累性能——这就是”按需调入不适合线性/随机搜索”的本质原因。
页表原理与地址变换 → 页式管理
页表项在虚拟内存中的扩展
虚拟内存下并非所有页都在内存中，页表项除了基本字段外，还需额外记录：
| 字段 | 作用 |
|---|---|
| 存在位（有效位） | 该页是否已在内存中 |
| 外存地址 | 若不在内存，记录它在外存（文件区/对换区）的位置 |
| 访问位 | 该页近期是否被访问过（置换判断依据） |
| 修改位（脏位） | 该页内容是否被修改过（换出时决定是否回写） |
页表项基本字段（页框号、保护位等）见 页式管理·页表。
缺页中断
CPU 访存，MMU 查页表——基本流程同 页式管理·地址变换，唯一的区别在步骤 2：当存在位 = 0，页不在内存，触发缺页中断（内中断，指令执行期间发生）：
1. CPU 访存，MMU 查页表发现该页不在内存
2. 硬件触发缺页中断，陷入操作系统
3. OS 查 PCB 找到该页在外存中的位置
4. 若内存有空闲页框 → 直接装入
若无空闲页框 → 按置换算法选一页换出
5. 被换出页若修改过（脏页）→ 先回写外存
6. 将所需页面装入目标页框，更新页表
7. 重新执行刚才因缺页而中断的那条指令
TLB 原理 → 页式管理·TLB
多级页表原理 → 页式管理·两级页表
页框分配
虚拟内存不是无限制占用物理内存，每个进程只分配一定数量的页框。
最小页框数与驻留集
- 最小页框数：进程能正常运行所需的最少页框数。由指令集架构决定——至少需要覆盖一条指令执行过程中可能访问的所有页面（指令本身、源操作数、目的操作数）。
- 驻留集：某一时刻实际分配给进程、驻留在内存中的页面集合。对应的页框数量就是驻留集大小。
驻留集大小的影响
| 驻留集大小 | 影响 |
|---|---|
| 太小 | 频繁缺页，刚调入的页马上又被换出，CPU 大量时间耗费在调页 |
| 太大 | 单个进程缺页少，但挤占其他进程的可用页框，降低并发度 |
内存分配与置换策略
策略组合由两个维度决定：页框数是否固定、置换范围是局部还是全局。
| 策略 | 页框数 | 置换范围 | 特点 |
|---|---|---|---|
| 固定分配局部置换 | 固定 | 本进程 | 隔离性强，管理简单；初始分配不当则频繁缺页 |
| 可变分配全局置换 | 可变 | 所有进程 | 整体利用率高；进程间互相影响大 |
| 可变分配局部置换 | 可变 | 本进程 | 折中方案：动态调整 + 局部控制 |
固定分配局部置换
进程启动时分配固定数量页框，此后不变。缺页时只能从本进程自己的页框中选一页换出。问题是如果没估准进程的实际内存需求，分配不足时进程会持续缺页。
可变分配全局置换
系统根据运行情况动态增减进程页框数。缺页时，换出目标可以来自任何进程，回收的空闲页框也可以重新分配给缺页多的进程。缺点是进程间干扰：一个缺页频繁的进程可能挤占其他进程的页框。
可变分配局部置换
页框数可以动态调整，但每次缺页置换时只从本进程驻留集中选页换出。它试图兼顾灵活性与隔离性。
换入来源：文件区与对换区
缺页时从外存调入的页面来源分两种：
| 来源 | 存放内容 | 调入场景 |
|---|---|---|
| 文件区 | 原始程序文件、只读数据 | 该页未被修改过，可直接从可执行文件重新读入 |
| 对换区 | 曾经装入内存后被换出的页面 | 运行中被修改过的页换出后存于此处，缺页时从对换区调回 |
本质区别：文件区的页”丢了还能从原文件拿”，对换区的页”丢了就没法恢复，必须保存”。
页引用字符串
页面置换算法的输入是什么？答案是进程运行期间依次访问的逻辑页号序列——页引用字符串（Reference String）。
比如某进程先后访问了第 0 页、第 2 页、第 1 页……：
每个数字是一个逻辑页号，不是物理地址，也不是字节地址。
计算题的标准化套路：给定引用字符串 + 可用页框数，逐页模拟置换算法的行为，统计缺页次数（或命中次数）。
引用字符串的来源：
- 由进程的实际访存地址序列 页大小，取商（页号）得到
- 连续重复访问同一页号是否合并为一个，看题目说明
引用字符串是页号序列——这是最容易搞混的点：把地址直接当页号算，结果全是错的。
页面置换算法
发生缺页且无空闲页框时，必须选一页换出。选择策略就是页面置换算法。
OPT 最佳置换算法
规则：淘汰未来最长时间内不再被访问的页面。
- 缺页率最低，是理论上的最优解
- 无法实现：OS 不可能预知未来访问序列
- 用途：作为评价其他算法的比较基准
FIFO 先进先出置换算法
规则：淘汰最早进入内存的页面。
- 实现简单：维护一个 FIFO 队列即可
- 只看新旧不看频率，可能把经常使用的”老页”换出去
- Belady 异常：分配的页框数增多，缺页次数反而增加
Belady 异常示例：访问序列
3,2,1,0,3,2,4,3,2,1,0,4，3 个页框时缺页 9 次，4 个页框时反而缺页 10 次。FIFO 是典型的会出现 Belady 异常的算法。
LRU 最近最久未使用
规则：淘汰最近最长时间未被访问过的页面。
- 基于局部性原理：很久没用的页接下来大概率也不会用
- 性能接近 OPT
- 实现代价高：需要记录每次访问的时间戳或维护访问栈
LRU 的硬件实现方式：
| 方式 | 做法 | 开销 |
|---|---|---|
| 计数器 | 每次访存 CPU 将递增的时钟值写入页表项，置换时找最小值 | 每次访存都要写内存 |
| 栈 | 每次访问将该页号移到栈顶，置换时取栈底页号 | 每次访存都要调整栈（指针操作较多） |
CLOCK 时钟置换算法（NRU 近似）
规则：驻留集页面排成环形链表，指针循环扫描，利用访问位判断。
1. 指针指向某页
2. 若访问位 = 0 → 换出该页
3. 若访问位 = 1 → 清 0，跳过，指针继续移动
相当于给访问过的页”第二次机会”——这轮被扫到但近期用过，先放过；下一轮再扫到如果仍未被访问，就淘汰。
- 比 LRU 实现简单得多（只用一个硬件位）
- 效果明显好于 FIFO
- 实际系统中非常常用
改进 CLOCK 算法
在访问位之外纳入修改位，因为换出脏页要回写磁盘，代价远大于换出干净页。
按 分为四档优先级：
| 优先级 | (访问位, 修改位) | 含义 | 换出策略 |
|---|---|---|---|
| 最高换出 | (0, 0) | 最近未用，未修改 | 首选淘汰，无需回写 |
| 次选 | (0, 1) | 最近未用，已修改 | 可淘汰，但需回写 |
| 较留 | (1, 0) | 最近用过，未修改 | 暂缓 |
| 最低换出 | (1, 1) | 最近用过，已修改 | 尽量保留 |
扫描逻辑：先找 (0, 0)，找不到再找 (0, 1)，同时沿途把访问位清 0——给所有页面一次”降级”的机会。
抖动与工作集
抖动
进程分配的页框数太少，活跃页面装不下驻留集，导致页面刚调入就被换出、马上又调入——系统大量时间耗费在调页 I/O 上，CPU 利用率反而暴跌。
抖动发生链路：
驻留集 < 活跃页面 → 频繁缺页 → 大量 I/O 等待 → CPU 空闲
→ 调度器误判"CPU 闲，加进程" → 进程更多 → 缺页更严重 → 死循环
工作集
工作集：某段时间窗口 内，进程频繁访问的页面集合。可以理解为进程在当前阶段”真正离不开”的那批页。
| 关系 | 结果 |
|---|---|
| 驻留集 工作集 | 缺页率低，正常运行 |
| 驻留集 工作集 | 频繁缺页，可能抖动 |
工作集模型常被用于指导驻留集大小的动态调整：操作系统监控每个进程的工作集变化，据此增减其分配的页框数。这也引出了工作集置换算法——换出不在当前工作集中的页面。
写时复制（Copy-on-Write）
fork() 创建子进程时，传统做法是把父进程的整个地址空间完整复制一份。但大多数情况下，fork() 之后紧跟 exec()，刚复制完的页面马上就被覆盖——复制完全白做。
Copy-on-Write 策略：
fork()时父子进程共享同一套物理页面，页表项标记为只读- 任意一方试图写入某页 → 触发页保护异常
- OS 捕获异常，此时才真正复制该页，并为写入方恢复可写权限
- 没被写的页面继续共享，永不复制
这样大量节省了 fork() 的内存开销和时间。
页框回收
系统不会等到一个空闲页框都没有才行动。当空闲页框数低于某阈值（低水位线），就启动后台回收。
回收时区分：
| 页面类型 | 回收处理 |
|---|---|
| 干净页（修改位=0） | 可直接回收；若来自文件映射且未修改，需要时再从文件读入 |
| 脏页（修改位=1） | 必须先回写磁盘/对换区，再回收页框 |
内存映射（Memory-Mapped I/O）
操作系统将文件或设备的一段内容映射到进程的虚拟地址空间，进程可以像访问内存一样访问文件内容。
| 优势 | 说明 |
|---|---|
| 简化文件访问 | 不必显式 read/write，指针操作即可 |
| 按需调页 | 访问到哪页就调入哪页（demand paging） |
| 多进程共享 | 多个进程把同一文件映射到各自地址空间，底层共享同一物理页 |
内存映射本质上是利用虚拟地址空间的映射能力，让不同访问者围绕同一份实际物理内容建立联系——与共享内存原理相通。