页面回收与交换

写作时间：2026-03-30 首次提交，2026-04-03 最近修改
当前字符：5024

上一课讲了按需分页和缺页异常：页在第一次访问时才装入内存。但物理内存终究有限——如果只管装进来不管赶出去，RAM 很快就会被占满。这一课回答剩下的一半问题：内存不够时先赶走谁，赶出去之后放到哪里。

页面替换

页面替换(page replacement)是在可用物理内存不足时，从当前驻留的页面中选出一部分移走，为新页面腾出空间的机制。

最理想的策略是 OPT(Optimal)：永远替换未来最长时间不会再被访问的页。它给出了缺页次数的理论下界，但因为内核无法预知未来访问序列，所以 OPT 只能作为分析基准。

最朴素的可实现算法是 FIFO(First In, First Out)：谁最早进入内存，谁先被替换。但 FIFO 会出现一个反直觉的现象——分给进程的页帧数增加，缺页次数反而可能上升。这叫 Belady 异常(Belady's anomaly)。用引用序列 1 2 3 4 1 2 5 1 2 3 4 5 逐步推导，可以直接看到它发生的过程。

3 个页帧时的替换过程（方括号内按 FIFO 顺序排列，最左边最早进入）：

访问 1 → [1]              缺页
访问 2 → [1, 2]           缺页
访问 3 → [1, 2, 3]        缺页
访问 4 → [2, 3, 4]        缺页（淘汰 1，最早进入）
访问 1 → [3, 4, 1]        缺页（淘汰 2）
访问 2 → [4, 1, 2]        缺页（淘汰 3）
访问 5 → [1, 2, 5]        缺页（淘汰 4）
访问 1 →                   命中
访问 2 →                   命中
访问 3 → [2, 5, 3]        缺页（淘汰 1）
访问 4 → [5, 3, 4]        缺页（淘汰 2）
访问 5 →                   命中

共 9 次缺页

4 个页帧时的替换过程：

访问 1 → [1]              缺页
访问 2 → [1, 2]           缺页
访问 3 → [1, 2, 3]        缺页
访问 4 → [1, 2, 3, 4]     缺页
访问 1 →                   命中
访问 2 →                   命中
访问 5 → [2, 3, 4, 5]     缺页（淘汰 1）
访问 1 → [3, 4, 5, 1]     缺页（淘汰 2）
访问 2 → [4, 5, 1, 2]     缺页（淘汰 3）
访问 3 → [5, 1, 2, 3]     缺页（淘汰 4）
访问 4 → [1, 2, 3, 4]     缺页（淘汰 5）
访问 5 → [2, 3, 4, 5]     缺页（淘汰 1）

共 10 次缺页

4 帧比 3 帧多了一帧可用空间，缺页次数反而从 9 次增到 10 次。原因在于 FIFO 只看"进入顺序"，不看页面是否还在被频繁使用——"最早进来"不等于"现在最不重要"。

LRU(Least Recently Used)用"最近没用过的页将来也不太可能马上用到"这一局部性假设来选择替换目标，直觉比 FIFO 更贴合程序行为。但精确 LRU 要求在每次内存访问时维护全局访问顺序，在多核高并发下这个代价比替换决策本身还高。

为什么精确 LRU 很少直接实现？

内存访问是最频繁的硬件事件之一。要在每次访问时更新一个排序结构，开销远超替换本身。即使用硬件 Accessed 位记录访问，内核也只能周期性采样和清理，无法得到严格的全局先后顺序。所以现实系统几乎都在做近似 LRU。

时钟算法

时钟算法(Clock，也叫 Second-Chance)是经典的近似 LRU 方案。它把所有驻留页组成一个环形链表，用一个扫描指针像时钟表针一样不断前进。

用一个具体的例子来看它怎样工作。假设有 4 个页帧，当前环的状态是（指针指向页 A）：

        ──→ A(1) ──→ B(0) ──→ C(1) ──→ D(1) ──→ 回到 A
        ↑
      指针

括号里的数字是 Accessed 位：1 表示最近被访问过，0 表示没有。现在需要替换一个页：

指针在 A，Accessed = 1。内核给 A "第二次机会"：把 A 的 Accessed 位清为 0，指针前进。
指针到 B，Accessed = 0。B 在上一轮扫描后没有被访问过——这就是替换目标。

找到替换目标的过程：

        ──→ A(1→0) ──→ B(0) ← 替换！
                        ↑
                      指针停在这里

如果所有页的 Accessed 位都是 1，指针会绕一整圈，把所有位都清掉，最终回到起点——这时起点的 Accessed 位已经是 0 了，它就成了替换目标。这意味着只有"绕了一整圈都没有被再次访问"的页才会被淘汰，越热的页越不容易被选中。

Linux 的页面回收

Linux 没有直接使用时钟算法，而是用链表来组织页面的冷热关系。长期以来的方案是两条链表：活跃链表(active list) 和不活跃链表(inactive list)。

一个新装入的页先进入 inactive list。如果它在 inactive list 上被再次访问，就提升到 active list——说明这个页确实在被使用。active list 上的页在一段时间没有被访问后会降回 inactive list。回收时，内核优先从 inactive list 的尾部挑选目标。

用一个页的生命周期来看这个过程：

首次缺页装入
  │
  ▼
inactive list ──被再次访问──→ active list
  │                              │
  │                        长时间未访问
  │                              │
  │                              ▼
  │                        降回 inactive list
  │
  ├── 回收扫描到，Accessed = 0 → 被淘汰
  └── 回收扫描到，Accessed = 1 → 清除 Accessed，下次再看

多代 LRU(Multi-Gen LRU, MGLRU)是近年来的改进。它不只分 active/inactive 两档，而是把页按访问新旧程度分进多个 generation（代）。刚被访问的页在最年轻的一代，随着时间推移逐渐"老化"到更老的代。回收时优先扫描最老一代，避免浪费时间扫描明显还在活跃使用的页。在多种工作负载交织的场景下，MGLRU 比传统两链表方案有更少的误回收。

工作集与抖动

工作集(working set)是一个进程在某段时间窗口内反复使用的那组页面。

一个进程的地址空间可以很大，但在某个时间段内真正被循环访问的往往只是其中一小部分。页面回收的目标就是尽量保住工作集，把工作集之外的冷页让出去。

当系统中所有活跃进程的工作集总和超过了可用物理内存，内核刚换出一页，进程很快又把它读回来；刚补进另一页，又被迫赶出去。CPU 大量时间耗在缺页处理、页回收和 I/O 等待上，真正推进计算的时间很少。这种状态叫抖动(thrashing)。抖动的典型表现不是 CPU 空闲，而是系统处于一种低效的忙碌：page fault 频率极高，用户感觉机器几乎什么都做不动。

交换

交换(swap)是在匿名页被回收时把其内容写到后备存储中，以便未来再次访问时能恢复的机制。

页面替换决定了"谁该出去"，但不同类型的页，出去的方式不同：

页类型	回收时的动作	原因
干净文件页	直接丢弃	文件里有权威副本，随时可以重读
脏文件页	先回写文件，再丢弃	修改过的内容必须先保存回文件
匿名页	写入交换区	没有文件可以重读，必须自己保留一份后备

交换区主要服务于匿名页——堆、栈和 MAP_PRIVATE 写时复制后的脏页都没有对应的文件，如果不把内容保存到交换区就直接释放，数据就永久丢失了。

一个匿名页被换出时，内核把页的内容写入交换区（磁盘上的 swap 分区或 swap 文件），然后把 PTE 从"指向物理页帧"改为"指向交换区的某个位置"，最后释放物理页帧。当进程再次访问这个地址时，CPU 发现 PTE 的 Present 位为 0，触发缺页异常（major fault）。内核从交换区把内容读回一张新的物理页帧，更新 PTE，进程继续执行。

内存压缩

内存压缩(memory compression)在页面被真正换出到慢速存储之前，先尝试把内容压缩以更少的物理内存承载更多页面。

在交换路径上，真正写磁盘是最慢的一步。内存压缩在这一步之前插入了一个缓冲层：先尝试用 CPU 压缩页面内容，如果压缩后足够小，就留在 RAM 中的压缩池里，不去碰磁盘。

两个常见机制。zswap 在 swap 路径入口处拦截即将换出的匿名页，压缩后放在 RAM 中的池里。池满时才真正写到后端 swap 设备。zram 更激进——它把一块压缩后的 RAM 直接暴露为块设备，再把这个块设备当作 swap 用。数据逻辑上"换出了"，物理上仍在内存中，只是变成了压缩形式。

                              zswap 路径
                              ┌──────────────────────┐
匿名页需要换出 ──→ 尝试压缩 ──→│ 压缩池（RAM）         │──池满──→ 后端 swap 设备
                              └──────────────────────┘

                              zram 路径
匿名页需要换出 ──→ 写入 zram 块设备（本质是压缩后的 RAM）

本质上是拿 CPU 压缩/解压的开销换取更少的磁盘 I/O。在内存压力中等且页面可压缩性较高时很划算，因为一次压缩解压比一次磁盘读写快得多。当页面根本不可压缩，或者系统瓶颈在 CPU 而不是内存时，压缩层反而会成为额外负担。

小结

概念	说明
FIFO / Belady 异常	最朴素的替换算法，增加页帧数可能反而增加缺页次数
LRU	基于局部性假设的替换策略，精确实现代价太高
时钟算法	用环形扫描和 Accessed 位近似 LRU
active / inactive list	Linux 长期使用的两链表冷热分层方案
MGLRU	把页面按访问新旧分成多代，减少误回收
工作集	一段时间内进程真正频繁使用的那组页面
抖动	工作集总和超过可用内存后的高频换页状态
交换	为匿名页提供后备存储，使其可被回收后恢复
内存压缩 (zswap / zram)	在真正 swap 之前先压缩匿名页，拿 CPU 换 I/O

页面回收与交换 ​

页面替换 ​

时钟算法 ​

Linux 的页面回收 ​

工作集与抖动 ​

交换 ​

内存压缩 ​

小结 ​