虚拟内存与页面置换

虚拟内存的核心思想

虚拟内存允许程序使用比物理内存更大的地址空间，其核心思想是：不需要把程序的所有页面都加载到物理内存中，只加载当前需要的部分，其余存放在磁盘上。

比喻：图书馆的阅览桌（物理内存）空间有限，但你可以从存书架（磁盘）上随时取需要的书。阅览桌满了就把暂时不看的书放回架上，腾出位置给新书。

                虚拟地址空间（很大）
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ P0 │ P1 │ P2 │ P3 │ P4 │ P5 │ P6 │ P7 │
└──┬─┴──┬─┴────┴──┬─┴────┴──┬─┴────┴────┘
   │    │         │         │
   ▼    ▼         ▼         ▼
┌────┬────┬────┬────┐      磁盘（交换区）
│ P0 │ P1 │ P3 │ P5 │      ┌────┬────┬────┐
│    │    │    │    │      │ P2 │ P4 │ P6 │
└────┴────┴────┴────┘      └────┴────┴────┘
   物理内存（有限）           暂时不用的页面

缺页异常（Page Fault）

当 CPU 访问一个虚拟页面，但该页面不在物理内存中（页表项的有效位为 0），就会触发缺页异常：

CPU 访问虚拟地址
    │
    ▼
查页表 ─── 有效位 = 1 ───▶ 正常访问物理内存
    │
  有效位 = 0（缺页）
    │
    ▼
触发缺页异常 (Page Fault)
    │
    ▼
内核介入处理:
    │
    ├── 物理内存有空闲帧 → 从磁盘加载页面到空闲帧
    │                     → 更新页表
    │                     → 重新执行触发异常的指令
    │
    └── 物理内存已满 → 选择一个「牺牲页面」（页面置换算法）
                     → 如果牺牲页面被修改过（脏页），先写回磁盘
                     → 加载新页面到该帧
                     → 更新页表
                     → 重新执行触发异常的指令

缺页率（Page Fault Rate）直接影响系统性能。假设内存访问 100ns，磁盘访问 10ms：

• 有效访问时间 = (1-p) × 100ns + p × 10,000,000ns
• 若 p = 0.001（千分之一），有效访问时间 ≈ 10μs，性能下降 100 倍

因此，好的页面置换算法至关重要。

页面置换算法

1. 最优置换算法（OPT）

置换将来最长时间不会被使用的页面。理论上最优，但需要预知未来，实际无法实现，仅作为衡量其他算法优劣的基准。

2. 先进先出（FIFO）

置换最早进入内存的页面。简单但效果差，可能换出正在频繁使用的页面。

页面引用序列: 7 0 1 2 0 3 0 4

帧数 = 3:
访问 7: [7, -, -]  缺页 ✓
访问 0: [7, 0, -]  缺页 ✓
访问 1: [7, 0, 1]  缺页 ✓
访问 2: [2, 0, 1]  缺页 ✓ (置换最早的 7)
访问 0: [2, 0, 1]  命中
访问 3: [2, 3, 1]  缺页 ✓ (置换最早的 0)
访问 0: [2, 3, 0]  缺页 ✓ (置换最早的 1)
访问 4: [4, 3, 0]  缺页 ✓ (置换最早的 2)

缺页次数 = 7

Belady 异常：FIFO 算法中，增加物理帧数反而可能导致缺页次数增加。这是 FIFO 的反直觉缺陷。

3. 最近最少使用（LRU）

置换最近最长时间未被访问的页面。基于局部性原理——最近没用的页面将来也不太可能用。

同样的引用序列: 7 0 1 2 0 3 0 4

帧数 = 3:
访问 7: [7, -, -]  缺页 ✓
访问 0: [7, 0, -]  缺页 ✓
访问 1: [7, 0, 1]  缺页 ✓
访问 2: [2, 0, 1]  缺页 ✓ (7 最久未用)
访问 0: [2, 0, 1]  命中    (0 变为最近使用)
访问 3: [2, 0, 3]  缺页 ✓ (1 最久未用)
访问 0: [2, 0, 3]  命中
访问 4: [4, 0, 3]  缺页 ✓ (2 最久未用)

缺页次数 = 6 (优于 FIFO 的 7)

LRU 的实现方式：

• 计数器法：每个页面记录最后访问时间，置换时找最小时间戳。开销大。
• 栈法：用双向链表，访问一个页面就移到栈顶，置换栈底。每次访问需要移动节点。

4. 时钟替换算法（Clock / Second Chance）

LRU 的近似实现，也是实际操作系统中最常用的算法。每个页面有一个访问位（Reference Bit），硬件在页面被访问时自动置 1。

       ┌── R=1 ──┐
       │         │
  ┌────▼────┐   │
  │  Page A  │   │      指针（时钟指针）
  ├──────────┤   │         │
  │  Page B  │ R=0 ◀───────┘
  ├──────────┤
  │  Page C  │ R=1
  ├──────────┤
  │  Page D  │ R=0 ← 置换这个！
  └──────────┘

算法:
1. 检查指针指向的页面
2. R=0 → 置换该页面
3. R=1 → 将 R 置为 0，移动指针到下一页（给它"第二次机会"）
4. 重复直到找到 R=0 的页面

抖动（Thrashing）

当系统中进程过多，每个进程分到的物理帧太少，导致频繁缺页，CPU 大部分时间都在处理缺页异常而非执行有用代码。这种现象叫抖动。

CPU 利用率
     ▲
     │      ╱╲
     │     ╱  ╲
     │    ╱    ╲ ← 抖动开始
     │   ╱      ╲
     │  ╱        ╲___
     │ ╱
     └────────────────────▶ 进程数量
         最佳点

解决方法：

• 减少多道程序度（减少同时运行的进程数）
• 使用工作集模型：跟踪每个进程最近访问的页面集合（工作集），确保分配足够的帧来容纳工作集

生产高频题

什么是虚拟内存？

虚拟内存通过按需分页机制，让程序可以使用比物理内存更大的地址空间。只把当前需要的页面加载到物理内存，其余存放在磁盘上，通过缺页异常按需加载。

LRU 和 FIFO 有什么区别？

FIFO 只考虑页面进入内存的先后顺序，可能换出正在频繁使用的页面；LRU 考虑最近一次访问时间，置换最久未被访问的页面，更符合程序局部性原理，缺页率通常更低。

什么是抖动？怎么解决？

抖动是指进程过多导致每个进程分到的物理帧不足，频繁发生缺页，CPU 大部分时间花在处理缺页异常上。解决方法是减少同时运行的进程数，或使用工作集模型确保每个进程有足够的帧。