第 15 篇：交换与页面置换——内存不够时先扔谁

一、地址空间可以比内存大

第 12 篇的演示里，我们申请了 1 GB 地址空间，只占了 8 MB 物理内存。当时的解释是"按需分页——碰哪页给哪页"。

但如果你真的把 1 GB 全碰了，而机器只有 512 MB 呢？

答案是：把暂时用不到的页挪到磁盘上，把物理帧腾出来。 这块磁盘空间叫交换区（swap）。

这件事之所以能做，全靠第 12 篇那个有效位。一个页表项的有效位是 0，可以有两种含义：

• 这个地址根本不合法 → 缺页时内核发 SIGSEGV（第 10 篇那个演示）。
• 这个地址合法，但内容现在在磁盘上 → 缺页时内核把它读回来，重填页表项，重新执行那条指令。

⭐ 对进程来说，这两种情况的区别是"程序崩了"和"这条指令有点慢"。 而它自己完全分不清刚才发生了哪种——它甚至不知道发生过什么。

打个比方

酒店满房了，但还有团要住。

前台的做法是：把某个团的行李从房间里搬到地下仓库，房间腾给新来的。

• 那个团的房号不变（虚拟地址不变），行程单一个字不用改。
• 只是他们回房拿东西时，前台得说"稍等，我去仓库取"——这一等就是几毫秒到几十毫秒，而在内存里取只要几十纳秒。差了五个数量级。
• 所以真正的问题不是"能不能搬"，是**“搬谁的”**。搬错了，那个团一分钟往仓库跑八趟。

⭐ 这一篇后半段全部在讲"搬谁的"。

二、什么时候搬，搬到什么程度

内核不会等到内存耗尽才动手——那时候已经晚了，任何一次分配都要先等一次磁盘写。

所以它设了两条水位线：

• 空闲内存跌破低水位 → 后台的回收线程（kswapd）开始干活，把页往外挪，直到回到高水位。
• 如果回收赶不上分配的速度，才会让分配的那个进程自己同步回收——这时候你的程序就真的卡住了。

⭐ 这是个通用模式：把昂贵的清理工作提前到后台，异步做完，避免它出现在关键路径上。 第 27 篇的文件系统日志刷盘也是同一手。

哪些页可以走

不是所有页都能被换出去：

⭐ 这里脏位（第 12 篇那张表）第一次派上用场：一个文件页如果没被写过，扔掉它是免费的——需要时重新从文件读就行。这也是为什么内存紧张时，第一批被牺牲的总是页缓存。

三、⭐ 挑谁走：又一次"最优但用不了"

假设必须扔掉一页，扔哪个？

最优策略很好说：扔掉未来最晚才会被用到的那一页。这能证明是最优的。

它也同样用不了——要预知未来。

⚠️ 这是这门课第二次遇到这个形状。第 5 篇的 SJF 要知道每个作业要跑多久，这里要知道每一页下次什么时候被访问。两次的处理方式也一样：把最优当尺子，量你实际用的那个差多远。

几个能用的：

FIFO：最早进来的先走。实现最简单，效果差——一个进来得早但一直在用的页会被扔掉。它还有个著名的怪毛病叫 Belady 异常：给它更多的物理内存，缺页反而更多。（其它几个策略都不会这样。）

LRU（最近最少使用）：扔掉最久没被访问过的那一页。这是个很好的近似，因为它押的是时间局部性——刚用过的很可能马上再用。

但严格的 LRU 做不起。它要求每次内存访问都去更新一个链表，把这一页移到表头。每次访问。 那比第 12 篇那笔"访存翻倍"的账还贵。

硬件只肯给一个位

于是硬件退了一步：页表项里给一个访问位（第 12 篇那张表里的那一位）。

• 这一页被访问了 → 硬件自动置 1。
• 操作系统随时可以把它清 0。

就这一个位，没有时间戳，没有顺序。

时钟算法（clock）用它凑合出一个 LRU 的近似：

1. 把所有物理帧想象成一个环，一根指针指着某处。
2. 要淘汰时，看指针指的这一页的访问位。
   • 是 1：说明这一轮它被用过。把它清 0，指针往前走，再看下一个。
   • 是 0：说明从上次清 0 到现在它一次都没被碰过。就是它了。

⭐ 这个算法漂亮在它把"排序"换成了"筛选"。它不知道谁最久没被用，但它知道谁"最近一轮完全没被用"——而这就够了。用一个位换掉了一整套链表维护。

回到前台那本账：他没办法知道哪个团最久没回过房间——那要给每次开门都记一笔，太贵了。但他可以每隔一阵子把所有房间的门把手擦一遍，下次巡查时看哪几个还是干净的。 干净的那些，就是这一轮谁都没碰过的。行李先从那里搬。

真实的 Linux 更复杂一些：它维护两条链表（活跃、不活跃），页要被访问两次才升到活跃链表，防止一次顺序扫描把真正的热数据全冲掉。但核心还是"访问位 + 二次机会"这个思路。

四、跑一遍看看：LRU 的经典最坏情况

上面说 LRU 押的是时间局部性。那如果一个程序没有时间局部性呢？

最经典的反例是循环顺序扫描一个比缓存大的数据集。我们让它真的发生：

# evict.py
import os, time

PATH, MB = "/tmp/big.bin", 800

def stat(key):
    for line in open("/sys/fs/cgroup/memory.stat"):
        if line.startswith(key + " "):
            return int(line.split()[1])
    return 0

limit = open("/sys/fs/cgroup/memory.max").read().strip()
print(f"  容器内存上限：{int(limit)>>20} MB      文件大小：{MB} MB")

with open(PATH, "wb") as f:
    for _ in range(MB): f.write(b"x" * (1 << 20))
os.sync()

def sweep(tag):
    s0, t0 = stat("pgsteal"), time.time()
    with open(PATH, "rb") as f:
        while f.read(1 << 20): pass
    print(f"  {tag}  用时 {time.time()-t0:5.2f} 秒   "
          f"缓存里现在有 {stat('file')>>20:>4} MB   本轮内核赶走了 {(stat('pgsteal')-s0)*4>>10:>4} MB")

sweep("第 1 遍"); sweep("第 2 遍"); sweep("第 3 遍")
os.unlink(PATH)

=== --memory=2g ===
  容器内存上限：2048 MB      文件大小：800 MB
  第 1 遍  用时  0.05 秒   缓存里现在有  800 MB   本轮内核赶走了    0 MB
  第 2 遍  用时  0.03 秒   缓存里现在有  800 MB   本轮内核赶走了    0 MB
  第 3 遍  用时  0.03 秒   缓存里现在有  800 MB   本轮内核赶走了    0 MB

=== --memory=256m ===
  容器内存上限：256 MB      文件大小：800 MB
  第 1 遍  用时  0.15 秒   缓存里现在有  252 MB   本轮内核赶走了  799 MB
  第 2 遍  用时  0.12 秒   缓存里现在有  252 MB   本轮内核赶走了  800 MB
  第 3 遍  用时  0.12 秒   缓存里现在有  252 MB   本轮内核赶走了  799 MB

两组的访问模式一模一样——同一个文件，同样从头读到尾，读三遍。唯一的区别是内存上限。

• 上限 2 GB：文件全在缓存里，三遍一页都没淘汰。
• 上限 256 MB：缓存卡在 252 MB，每一遍内核都要赶走约 800 MB——等于整个文件被完整地淘汰了一次又一次。

⭐ 看第二组的荒谬之处：缓存里明明一直存着 252 MB，但命中率约等于零。

因为你从头扫到尾：读到文件末尾时，缓存里留着的是最后那 252 MB；而下一遍你要从开头读起——开头那部分刚好是最早被赶走的。每一页都在你即将用到它之前被扔掉。

这就是 LRU 的教科书最坏情况。而它并不罕见——任何"周期性完整扫一遍数据"的负载都长这样：批处理任务、全表扫描、日志重放。

⚠️ 数据库因此普遍不信任操作系统的页缓存，自己管理缓冲池，用的多是 LRU-K、2Q、ARC 这类对扫描有抵抗力的算法。

五、颠簸，和最后的手段

如果所有进程的工作集加起来就是比物理内存大呢？

那就会颠簸（thrashing）：刚换出去一页，马上就有人要它，只好换回来，同时又得换出另一页……

CPU 使用率跌到个位数，磁盘 100% 忙，整个系统像死了一样。 而且它有正反馈——越慢，堆积的请求越多，工作集越大，越慢。

现代 Linux 的兜底手段是 OOM killer：与其让所有人一起卡死，不如挑一个进程杀掉。

⚠️ 挑谁，靠一个叫 oom_score 的启发式打分（大致是"占内存最多的那个"）。这个选择常常不是你想要的——它可能杀掉你的数据库，而放过那个真正泄漏的脚本。你可以用 oom_score_adj 干预。

上面那个 --memory=256m 的实验里，如果把文件改成 800 MB 的匿名内存（而不是文件缓存），容器就会被直接 OOM 杀掉：匿名页没有地方可退——容器里通常没有交换区，而文件页至少还能扔掉重读。

⭐ 这就是容器时代和教科书的一个重大差别：交换区常常是关掉的，“内存不够"的结局不是变慢，而是被杀。

六、代价与取舍

这一层换来了什么： 地址空间可以大于物理内存；空闲内存可以拿来当磁盘缓存（Linux 的"内存总是用满"就是这么回事，那是特性不是问题）。

它花了什么：

• 访问延迟的方差爆炸。 命中是纳秒，缺页是毫秒，差五个数量级。你的 p99 延迟由缺页率决定，而缺页率你控制不了。
• 策略永远是近似的。 硬件只肯给一个访问位，剩下的全靠猜。

它放弃了什么： 性能的可解释性。 你的程序变慢了，可能是因为另一个进程申请了内存，把你的页挤了出去。你自己的代码一个字没改。

近年有两个变化值得知道：

• zram / zswap：不往磁盘写，在内存里压缩。用 CPU 换内存，比读磁盘快一两个数量级。手机和很多云主机默认开着。
• 多代 LRU（MGLRU，Linux 6.1 起）：把两条链表换成多"代”，用更细的年龄信息挑victim，而不是靠一次次二次机会。这是页面置换二十年来最大的一次改动——⭐ 说明这依然是策略，依然没有标准答案。

七、小结

• 交换靠的是第 12 篇那个有效位：0 可以表示"非法"，也可以表示"在磁盘上"。对进程来说，区别是崩溃和"这条指令有点慢"，而它分不清。
• 内核用高低水位提前在后台回收，避免让回收出现在关键路径上。
• 文件页没改过就直接扔（脏位在这里第一次派用场），匿名页必须先写进交换区。所以内存紧张时先牺牲页缓存。
• ⚠️ 最优置换要预知未来——这门课第二次遇到"最优但用不了"。
• 严格 LRU 做不起（每次访问都要更新链表），硬件只给一个访问位，时钟算法用它凑合。⭐ 它把"排序"换成了"筛选"：不知道谁最久没用，但知道谁"最近一轮完全没用"。
• ⭐ 实测 LRU 的最坏情况：同一个 800 MB 文件反复顺序扫，缓存 2 GB 时零淘汰，缓存 256 MB 时每遍淘汰 800 MB，命中率归零——因为每一页都在即将被用到之前被扔掉。数据库因此自己管缓冲池。
• 颠簸会正反馈；OOM killer 是兜底，但它挑谁常常不合你意。⭐ 容器里通常没有交换区，“内存不够"的结局是被杀而不是变慢。

思考题

1. FIFO 的 Belady 异常说"给更多内存反而缺页更多”。为什么 LRU 不会有这个毛病？（提示：想想"n 个帧时缓存里的内容"和"n+1 个帧时"之间是什么关系。）
2. 第四节那个实验，如果把三遍扫描的方向改成"第 1 遍正着读，第 2 遍倒着读，第 3 遍正着读"，结果会变好吗？为什么？
3. 时钟算法只用一个访问位。如果硬件肯给两位（比如一个 2 比特的计数器），你能设计出更好的策略吗？多出来的那一位值不值？
4. 酒店那个比方里，“匿名页必须先写进交换区、文件页可以直接扔"对应什么？为什么有的行李搬走之前要先登记，有的直接扔掉就行？

延伸

• 上一篇：第 14 篇：更小的页表——多级页表
• 下一篇：第 16 篇：线程——共享地址空间的代价