上一篇把反向映射讲清楚了：内核可以从物理页找回所有映射方。一旦找到，下一个问题是：在所有缓存着的页面中，选谁回收？这就是 LRU 和 workingset 机制要回答的事。

核心问题可以压成一句话：

Linux VM 无法知道未来访问序列，只能用最近访问证据、链表分层和 refault 信息近似估计 working set。

问题从哪里来

教材把 LRU 画成一个链表：每次访问把页面移到头部，回收时从尾部摘掉。理论上，这对局部性良好的负载接近最优。

实际系统无法直接实现教材 LRU。原因有三：

第一，每次内存访问都移动链表节点，开销不可承受。用户态一个循环可能每秒触发亿次内存访问，不可能每次都走内核锁链表。

第二，精确 LRU 需要全局排序。两个进程分别访问各自的页面，真正的 LRU 需要知道谁先谁后，需要一个全局时间戳或全局链表锁，NUMA 架构下这是严重瓶颈。

第三，内核的信息来源有限。硬件只提供 PTE 的 Accessed 位：访问过就置 1，内核定期清除再观察是否重新置 1。这是一个"采样"而不是"时间戳"。

因此 Linux 实现的不是 LRU，而是一套近似 LRU 的分层系统。经典实现用 active/inactive 两级链表 + referenced 标记，现代实现（Multi-Gen LRU）用多代分层 + refault 统计。两者目标相同：在有限信息下把热页面留下，把冷页面回收。

经典 LRU：active/inactive 分层

经典实现把可回收页面放进四条链表，按两个维度组织：

维度一 维度二 链表
active file active file LRU
active anon active anon LRU
inactive file inactive file LRU
inactive anon inactive anon LRU

这四条链表组织在 lruvec 结构中。官方文档明确 lruvec 是 per-node 的：

Per-node lruvec holding LRU lists and related parameters.

页面在这四条链表之间流动的规则大致是：

  1. 新分配的页面一般进 inactive 链表。
  2. 页面被再次访问时（Accessed 位被发现为 1），设置 referenced 标志。
  3. 如果页面在 inactive 链表上被第二次发现 referenced，提升到 active 链表。
  4. 回收扫描时，active 链表的页面被降级到 inactive 链表（清除 referenced）。
  5. inactive 链表尾部的页面是回收候选者。

这套规则的核心逻辑是"二次机会"：一页面必须被访问两次才能进入 active，不是单纯"最近访问过就不回收"。这避免了一次性大量顺序读（比如 find / 或 dd）把整个 active 链表冲掉。

pagevec / folio_batch：批处理避免锁争用

上述链表操作看起来意味着每次页面状态变化都要拿 lru_lock 修改链表。实际不是——内核使用 per-CPU 的 folio_batch（旧版本叫 pagevec，容量 31 个 folio 指针）做攒批。页面访问、激活、去激活等操作先把 folio 指针放进当前 CPU 的 batch，batch 满或特定时机（如 drain 调用）才一次性拿 lru_lock 把整批操作提交到链表。

这个设计的效果：正常运行时 LRU 链表操作几乎不争锁，吞吐远好于 naive per-page locking。代价是链表状态有短暂滞后——一个刚被访问的页面可能还在 inactive 链表上待几毫秒才被移动。对回收决策来说，这点滞后可以接受。

为什么分 file 和 anon

文件页和匿名页回收的成本不同。干净文件页可以直接丢弃（原始数据在磁盘上），脏文件页要先写回再丢弃。匿名页没有文件 backing，回收必须写到 swap。swap 通常比文件写回更贵。

分开两条链表让内核可以独立调控两类页面的回收比例。vm.swappiness 参数控制匿名页回收的相对积极程度：值越高，越愿意 swap 匿名页；值为 0 时几乎只回收文件页。

workingset 检测与 refault

单纯的 active/inactive 无法回答一个关键问题：一个被回收的页面究竟是真的冷，还是只是因为内存不够才被挤掉的热页面？

workingset 子系统解决这个问题。核心思路：当一个被回收的页面再次被访问（refault），把它重新加入时考虑"它在回收时的距离"。如果 refault 距离表明该页面应当属于 working set（即它在上次回收时排位靠前），直接把它提升到 active 链表，而不是从 inactive 重新开始。

具体机制：

  1. 页面从 page cache 中被回收时，内核在对应的 xarray slot 中记录一个 shadow entry，编码该页面被回收时的"时钟位置"（基于 inactive 链表长度的逻辑时钟）。
  2. 当该页面再次被访问并重新加入 page cache 时（refault），内核比较当前时钟与 shadow entry 中的时钟差值。
  3. 如果差值小于 active 链表的长度，说明该页面在回收前本应在 active 中，直接激活。

/proc/vmstat 中的 workingset_refault_file 和 workingset_refault_anon 计数器就反映这个事件的发生频率。refault 频率高意味着系统正在回收热页面——内存不够用了。

模式提炼：观测过去来猜测未来

1
unknown future -> observed recency -> approximate retention
维度 教材 LRU 内核近似 LRU
信息来源 精确访问时间 PTE Accessed 位（采样）
排序方式 全局时间排序 分层链表 + 二次机会
错误修正 无需（精确） refault 距离反馈
扫描开销 O(1) 移动（理论） 批量扫描 + 惰性降级
准确度 最优 对局部性良好负载接近最优

这种"不可能精确观测，用采样+反馈逼近"的模式在系统设计中反复出现：TCP 拥塞控制用 RTT 采样猜测带宽、数据库查询优化器用统计直方图猜测选择率、垃圾回收用 write barrier 采样猜测引用变化。

Multi-Gen LRU：更细粒度的分代

经典 active/inactive 只有两级。Multi-Gen LRU（MGLRU）把这个概念推广到多代。官方文档对它的定位：

an alternative LRU implementation that optimizes page reclaim and improves performance under memory pressure.

MGLRU 的核心概念是 generation。每个 lruvec 内部维护多个代（MIN_NR_GENS 到 MAX_NR_GENS），每代对应相似访问时间的一组页面：

  • lrugen->max_seq：最年轻的代号。
  • lrugen->min_seq[]：最老的代号，anon 和 file 分别追踪。

两个关键操作形成闭环：

Aging（老化）：递增 max_seq，把通过 PTE Accessed 位发现的热页面提升到最新代，冷页面自然落入旧代。Aging 通过 page table walk 扫描 PTE，发现 Accessed 位后清除并更新页面的 gen 计数器。

Eviction（回收）：从最老代开始回收。当一代的页面全部被回收或提升后，递增 min_seq。回收时如果发现某页面的 gen 计数器已被 aging 更新（变新了），跳过它。

MGLRU 相对经典实现的改进：

维度 经典 active/inactive Multi-Gen LRU
时间粒度 二级（热/冷） 多代（更细的时间切分）
空间利用 纯 rmap 遍历 Bloom filter 过滤活跃 mm_struct + page table walk 利用空间局部性
反馈机制 refault 只判断 active/inactive refault 比例比较（anon vs file）跨类型平衡
memcg 扩展 O(n) 遍历 memcg LRU 分片，最优 O(1)

MGLRU 在内核中作为可选配置存在。读源码时通过 CONFIG_LRU_GEN 判断当前内核是否启用。用户空间可以通过 /sys/kernel/mm/lru_gen/ 下的接口观察代信息。

一个最小实验：观察 LRU 活动

下面这个实验用一个循环访问程序制造明确的冷热分区，同时观察 /proc/vmstat 中的 LRU 计数器变化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

static void read_vmstat(const char *label, const char *keys[], int nkeys) {
    FILE *f = fopen("/proc/vmstat", "r");
    if (!f) { perror("fopen vmstat"); return; }
    printf("--- %s ---\n", label);
    char line[256];
    while (fgets(line, sizeof(line), f)) {
        for (int i = 0; i < nkeys; i++) {
            if (strncmp(line, keys[i], strlen(keys[i])) == 0) {
                printf("  %s", line);
            }
        }
    }
    fclose(f);
}

int main(void) {
    const char *keys[] = {
        "pgscan_kswapd",
        "pgscan_direct",
        "pgsteal_kswapd",
        "pgsteal_direct",
        "workingset_refault_file",
        "workingset_refault_anon",
        "workingset_activate_file",
        "workingset_activate_anon",
    };
    int nkeys = sizeof(keys) / sizeof(keys[0]);

    read_vmstat("before allocation", keys, nkeys);

    /* 分配 512MB，全部写一遍建立映射 */
    size_t size = 512UL * 1024 * 1024;
    char *buf = malloc(size);
    if (!buf) { perror("malloc"); return 1; }
    memset(buf, 'A', size);

    read_vmstat("after memset 512MB", keys, nkeys);

    /* 只反复访问前 64MB（热区），后 448MB 变冷 */
    size_t hot = 64UL * 1024 * 1024;
    long page_size = sysconf(_SC_PAGESIZE);
    for (int round = 0; round < 20; round++) {
        volatile char sink = 0;
        for (size_t off = 0; off < hot; off += (size_t)page_size) {
            sink += buf[off];
        }
        (void)sink;
    }

    read_vmstat("after 20 rounds on hot 64MB", keys, nkeys);

    free(buf);
    return 0;
}

编译与运行：

1
2
cc -Wall -Wextra -O2 lru_demo.c -o lru_demo
./lru_demo

注意：这个实验需要在内存相对紧张的环境下才能看到 pgscan 和 pgsteal 的变化。如果机器内存充裕（512MB 远小于可用内存），不会触发回收。可以同时运行一个内存压力程序，或者在 cgroup 中限制内存来放大效果：

1
2
3
4
5
# 在 cgroup v2 环境下限制内存为 256MB
mkdir -p /sys/fs/cgroup/lru_test
echo 256M > /sys/fs/cgroup/lru_test/memory.max
echo $$ > /sys/fs/cgroup/lru_test/cgroup.procs
./lru_demo

完成实验后清理：

1
2
3
rm -f lru_demo lru_demo.c
# 如果创建了 cgroup：
# rmdir /sys/fs/cgroup/lru_test

读取实验结果

在内存受限环境下预期看到的行为：

第一阶段（memset 512MB）：如果 512MB 超过可用内存，pgscan_kswapd 和 pgsteal_kswapd 开始增长，说明 kswapd 被唤醒并开始回收。如果压力更大，pgscan_direct 也会出现（分配路径上直接回收）。

第二阶段（反复访问前 64MB）：热区页面的 Accessed 位被反复设置，aging 扫描时它们被保护在 active 链表或年轻代中。冷区（后 448MB）的页面如果被回收过又被重新 fault 回来，workingset_refault_anon 增长。

关键观察：

  • workingset_refault_* 非零表示系统在回收后来发现有些页面其实不该回收——内存不够装下 working set。
  • workingset_activate_* 表示 refault 回来的页面被直接激活（跳过 inactive），说明 workingset 检测在工作。
  • pgscan 与 pgsteal 的差值反映"扫描了但没能回收的页面数"——这些页面要么被引用、要么脏、要么被锁定。

如果机器内存充足（512MB 完全放得下），所有计数器变化极小或为零，说明没有触发回收。这本身也是一个观察：LRU 机制只在内存压力出现时才产生可观测行为。

模式提炼：信号只在压力下可观测

1
2
no pressure -> no reclaim -> no LRU signal
pressure -> reclaim scans -> counters move -> refault reveals errors

内存管理的很多信号都有这个特点：系统表现良好时几乎看不到迹象，只有在边界条件下才显现。这和分布式系统里的背压（backpressure）类似——只有队列满了才能看到丢包或超时。

idle page tracking：另一种 working set 观测

除了内核自身的 LRU 近似，用户空间也可以主动观测 working set。idle page tracking 提供了这条路径。

原理分三步：

  1. 通过 /sys/kernel/mm/page_idle/bitmap 把目标页面全部标记为 idle。
  2. 等待一段时间，让进程正常运行。
  3. 再次读取 bitmap：仍然标记为 idle 的页面在这段时间内没有被访问过。

内部实现：标记 idle 时内核清除该页面所有映射的 PTE Accessed 位。为了不干扰回收器（回收器也读 Accessed 位），内核同时在页面上设置一个 Young 标志作为补偿。

限制：需要 CONFIG_IDLE_PAGE_TRACKING=y，只追踪 LRU 上的用户页面，需要 root 权限读写 bitmap。

这个接口的设计哲学与本篇主题一致：内核用采样（Accessed 位）来近似真实访问模式，idle page tracking 只是把同样的采样能力暴露给用户空间。

核心结构：lruvec

struct lruvec 持有一个 node（或 memcg）的全部 LRU 链表（include/linux/mmzone.h，精简）：

1
2
3
4
5
6
7
8
9
10
11
struct lruvec {
    /* 经典 active/inactive 四条链表 */
    struct list_head lists[NR_LRU_LISTS];
    unsigned long anon_cost;       /* 匿名页回收成本估计 */
    unsigned long file_cost;       /* 文件页回收成本估计 */
    atomic_long_t nonresident_age; /* workingset refault 时钟 */
#ifdef CONFIG_LRU_GEN
    struct lru_gen_folio lrugen;   /* Multi-Gen LRU 的分代数据 */
    struct lru_gen_mm_state mm_state; /* mm walk 状态 */
#endif
};

NR_LRU_LISTS = 5（inactive anon, active anon, inactive file, active file, unevictable）。

源码锚点

入口 读它的目的
mm/vmscan.c shrink_lruvec()、shrink_active_list()、shrink_inactive_list()
mm/workingset.c shadow entry 编码、refault 距离计算、workingset_refault()
include/linux/mmzone.h struct lruvec、LRU 链表枚举
mm/vmscan.c (MGLRU section) lru_gen_age_node()、evict_folios()
Documentation/admin-guide/mm/idle_page_tracking.rst idle page tracking 接口说明

读 shrink_inactive_list 时可以带着一个问题：扫描到一个页面后，哪些条件会让内核跳过它而不回收？这些"跳过条件"直接影响 pgscan 与 pgsteal 的差值。

研究生迁移表

Linux 概念 一般系统设计
active/inactive 链表 分层缓存（L1/L2 cache、CDN 热区/冷区）
referenced + 二次机会 采样验证后的晋升策略
workingset refault 缓存 miss 反馈驱动准入策略
Multi-Gen LRU 多级时间分桶（时间轮、分代 GC）
idle page tracking 用户态可观测性探针
pgscan/pgsteal 差值 扫描 vs 实际回收 = 无效扫描率

LRU 近似策略与数据库 buffer pool 的 clock-sweep 算法思路一致：不追求精确排序，而是用低开销的分层加上错误修正来逼近最优。

常见误解

第一个误解是把内核 LRU 等同于教材的链表 LRU。教材 LRU 在每次访问时移动节点，内核从未这样实现。内核用 Accessed 位采样，惰性扫描，批量处理。

第二个误解是认为 active 链表里的页面永远不会被回收。在内存压力极大时，active 页面会被降级到 inactive 再回收。active 只是"更难被回收"而不是"不可回收"。

第三个误解是认为 Multi-Gen LRU 完全取代了经典实现。MGLRU 是可选的（CONFIG_LRU_GEN），未启用时仍走经典 active/inactive 路径。两套实现共存在同一棵源码树中。

第四个误解是认为 workingset_refault 计数器高一定意味着要加内存。它意味着当前分配给该 cgroup 或节点的内存不够装下 working set，但"加内存"只是解决方案之一——减少 working set（优化访问模式）或调整 cgroup 限额也行。

第五个误解是把 idle page tracking 和内核 LRU 混为一谈。idle page tracking 是用户空间的主动观测工具，它在 Accessed 位上打标记再回收结果。内核 LRU 是被动的自动管理。两者共享底层机制（PTE Accessed 位），但服务的对象不同。

练习

第一，在一台 Linux 机器上运行文中实验（必要时用 cgroup 限制内存到 256MB），记录三个阶段的 pgscan、pgsteal、workingset_refault 变化。改变 hot 区大小（32MB、128MB、256MB），观察 refault 计数如何变化。

第二，读 mm/workingset.c 中 workingset_refault() 的实现。画出 shadow entry 编码的字段布局，解释"refault 距离"是如何从编码中恢复的。

第三，在一台启用了 MGLRU 的机器上（检查 /sys/kernel/mm/lru_gen/ 是否存在），读取 lru_gen 的调试输出，辨认代号、类型、页面计数之间的关系。

第四，用 sar -B 1 60 或持续读取 /proc/vmstat，在一个 IO 密集负载（如 find / -type f -exec cat {} + > /dev/null）下观察 pgscan 和 pgsteal 的比值。解释为什么顺序 IO 负载下这个比值接近 1，而随机访问负载下可能小于 1。

第五，查阅 Documentation/admin-guide/mm/idle_page_tracking.rst，在一台启用该功能的机器上对一个进程执行"标记 idle → 等待 10 秒 → 读回结果"的流程，估算该进程的 working set 大小。比较这个结果与 /proc/<pid>/smaps 中 Rss 的差异。

系列导航

参考资料