Theory · OS · Page Replacement
内存不够换谁出去：OPT · FIFO · LRU · LFU · Clock —— 以及 Linux / Redis / MySQL 的工业变体
OPT 定下限（不可实现）→ FIFO 简单但 Belady 异常 → LRU 用局部性逼近 OPT → Clock 用引用位做廉价近似
所有算法都在赌局部性：过去被访问的页，未来更可能再被访问——赌对了缺页率就低
Linux 双链表 + MGLRU、Redis 采样 LRU/LFU、MySQL Buffer Pool 的 young/old 分区——教科书思想的部署级改造
The Problem · Locality
进程要访问的页不在内存（缺页），而物理内存已满——必须挑一页"请出去"，腾出物理框。挑谁出去就是置换算法的全部内容；挑得不好，刚换出去的页马上又要换回来（缺页率飙升）。
时间局部性：刚访问过的页/数据，不久还会再访问（循环、热点数据）；空间局部性：访问某页后，相邻页大概率也被访问（数组、顺序代码）。于是"最近/最频繁使用的页"是"未来会用的页"的好代理——LRU/LFU 都是这个赌注的具体形式。
缺页次数 / 访问次数。major fault（要读盘）的代价是万级访存时间——缺页率差 1% 对延迟都是灾难。置换算法的目标：给定页框数，最小化缺页率。
Optimal Replacement · Belady
缺页时置换未来最长时间不再被访问的页——"预知未来"的算法，缺页率是所有算法的理论下限（Belady 1966 提出）。
需要知道未来的完整访问序列——等于要预知程序将来的每一步。真正的用途：离线模拟的基准线，其他算法用"缺页率 / OPT 缺页率"衡量逼近程度。
页框 3，序列 7,0,1,2,0,3,0,4：访问 2 缺页时，内存 {7,0,1}——0 马上要用、1 还会出现，7 最久不再出现 → 换 7。OPT 每一步都"换得刚刚好"。
OPT 满足包含性质：n 个页框的驻留集 ⊆ n+1 个页框的驻留集——这类"栈式算法"缺页率随页框数单调下降。FIFO 不满足，于是有了著名反例（下一页）。
| 算法 | 信息来源 | 可实现性 |
|---|---|---|
| OPT | 未来访问序列 | 否（理论基准） |
| LRU | 过去的访问序列 | 可（代价：精确计时/栈维护） |
| FIFO | 进入内存的先后 | 可（最便宜） |
| Clock | 1 位引用位 | 可（硬件成本最低） |
FIFO · Belady's Anomaly
换出最早进入内存的页：维护一个 FIFO 队列，命中不动、缺页时队头出队。实现 O(1)、零硬件支持。问题：进入早 ≠ 不再用——全局变量、循环体这类"老而热"的页会被冤枉换出。
序列 1,2,3,4,1,2,5,1,2,3,4,5：3 个页框缺页 9 次，4 个页框反而 10 次——内存变多，缺页率反而升高！原因：FIFO 不是栈式算法，页框数变了，换出的"历史顺序"整个错位。
它证明了 FIFO 的行为反直觉、不可靠——这也是现实系统几乎不用纯 FIFO 的原因（Redis/CDN 缓存用它时都打了补丁，如随机驱逐或按 TTL）。LRU/OPT 这类栈式算法可证明无此异常。
Least Recently Used
换出最长时间未被访问的页。它用"过去"逼近 OPT 的"未来"——局部性成立时是现实可实现算法中缺页率最优的一档；且是栈式算法，无 Belady 异常。
精确 LRU 每次内存访问都要更新顺序（哈希 + 双向链表 O(1) 也不行——那是软件缓存的奢侈，硬件访存路径上多一跳都嫌贵）。内核只在缺页时才有软件介入机会，所以只能用硬件留的一枚引用位 A（每次访问硬件置 1）做近似——这就是 Clock 算法的由来（第 7 页）。
应用层（Redis/Memcached/进程内缓存）每次访问本来就要走代码路径，维护哈希表 + 双向链表的精确 LRU 才划算——哈希表 deck 的 LRU 实现题（LeetCode 146）就是它。
// 软件层精确 LRU：哈希 + 双向链表 O(1) // 146 题范式（Go 版骨架） type LRUCache struct { m map[int]*node // key → 链表节点 head, tail *node // 哨兵：head=最新 cap int } // Get: 链表摘下节点挪到 head // Put: 已存在则更新+挪头； // 不存在则插头；超容删 tail.prev // 全部操作 O(1)，靠双向链表 O(1) 摘除
LFU · Cache Pollution
换出访问次数最少的页。赌注从"最近用过"（时间维度）换成"用得最多"（频率维度）：对长期稳定的热点（配置、元数据、热商品）比 LRU 更稳。
① 历史包袱：曾经的热点（已冷）频率值居高不下，赖着不走——需要定期衰减/老化（周期减半）才有意义；② 新页入场即最低频，新热点还没攒够次数就被换出——需要"新页保护期"。工程实现（如 Redis LFU）用对数计数器 + 时间衰减一并解决。
一次性批量扫描（全表扫描、备份、日志聚合）让每个冷页都"被访问过一次"，把真热页全部挤出 LRU——污染后热请求集体缺页。解法三件套：分区（新页先进小隔离区，二次访问才转正）、采样（近似替代精确）、频率加权（LRU-K/LFU 混合）。
| 对比 | LRU | LFU |
|---|---|---|
| 赌注 | 最近用过的会再用 | 用得多的会再用 |
| 擅长 | 短周期热点、顺序局部性 | 长周期稳定热点 |
| 怕什么 | 批量扫描污染 | 热点转移（历史包袱） |
| 实现要点 | 哈希 + 双链 O(1) | 计数器 + 衰减 |
| 典型部署 | MySQL/内核近 LRU | Redis LFU 模式 |
Clock · Second Chance · Enhanced
Linux active/inactive · MGLRU
每 zone/节点维护 active 与 inactive 两组 LRU 链表（文件页/匿名页各一套）：缺页访问把页提升 active（置引用位），active 冷却后降级 inactive，内存紧张时从 inactive 链表尾部回收——"二次机会"以链表形式落地，硬件引用位+A/D 位做辅助证据。
大内存机器上双链表扫描成本高、分代粗。Linux 6.1 引入 MGLRU（多代 LRU）：按访问年龄分代，代际间做批量判断，减少扫描与锁竞争——大规模内存 + 轻负载场景收益明显，逐步在新发行版默认启用。
置换算法在内核里长在 kswapd / 直接回收流程里：候选页按"文件页/匿名页 × 冷热"出队，脏页写回、匿名页进 swap——第 7 篇的回收流水线，就是本页算法的执行现场。
| 层次 | 机制 | 对应教科书概念 |
|---|---|---|
| 硬件 | PTE 的 A / D 位 | 引用位 / 脏位（Clock 的原料） |
| 链表层 | active / inactive 双链 | 第二次机会 / 近似 LRU |
| 现代层 | MGLRU 分代（6.1+） | 分代 LRU（LFU 思想相邻） |
| 执行层 | kswapd / 直接回收 | 缺页与换页的调度现场 |
Thrashing · Working Set
页框不足以容纳进程的活跃页集合：换出马上要用的页 → 马上缺页换回 → 再换出别的热页……CPU 几乎全耗在换页 I/O 上，利用率上升但有效吞吐暴跌——典型症状：CPU 空闲（等 I/O）但系统慢爆，si/so 疯涨。
进程在窗口 Δ 内实际访问的页集合 = 工作集 W(t, Δ)。要流畅运行：Σ 所有进程的工作集 ≤ 物理内存。调度器据此做"工作集准入"：内存不够装下新进程的工作集就先别切给它 CPU（swapping 挂起整个进程）——把"页级置换"升级成"进程级换出"。
① 单机并发进程/服务数量要按内存预算算，不是按 CPU 核数；② 容器 memory limit 卡在热数据边缘 = 人造抖动（监控 cgroup 的 pgmajfault）；③ 抖动苗头：缺页率高 + CPU 低 + si/so 高 → 减负载或加内存，调算法没用。
Redis · MySQL in Production
逐出不用精确 LRU：随机采样 N 个 key（默认 5）逐出其中最久未用的——省维护链表的成本，效果接近 LRU；可调 maxmemory-samples 提升精度。LFU 模式（4.0+）：8 位对数计数器（越大概率递增，防止计数溢出与存储放大）+ 分钟级时间衰减——一次治好 LFU 的"历史包袱"。
InnoDB 把 LRU 链表切 5/8 young + 3/8 old，新页必须先进 old 区头部（midpoint insertion），在 old 区停留超过 innodb_old_blocks_time（默认 1s）再被访问才升 young。专治两病：预读失效（预读页未及使用就被换出→ 先在 old 区冷置）与全表扫描污染（扫描页只在 old 区自转，不冲掉 young 热页）。
都拒绝"教科书直出"：近似换精确（成本）、分区防污染（准入）、衰减抗老化（时效）——三个补丁方向对应第 6 页的三种坑。
| 系统 | 方案 | 治什么 |
|---|---|---|
| Redis | 采样 LRU（N=5） | 精确 LRU 的维护成本 |
| Redis LFU | 对数计数 + 衰减 | 频率包袱、计数爆炸 |
| InnoDB | 5/8+3/8 分区 + midpoint | 预读失效、扫描污染 |
| InnoDB | old 区驻留 1s 才转正 | 瞬时访问冒充热点 |
| Linux | 双链 active/inactive + MGLRU | 访存路径不可介入的替代 |
Interview QA
OPT 最优但需预知未来（基准）；FIFO 便宜但换"最老"不是"最冷"且有 Belady 异常；LRU 贴局部性但实现贵、怕扫描污染；LFU 抗短期扰动但怕热点转移；Clock 用 1 位引用位做 LRU 廉价近似。
页框增多缺页率反而升高。序列 1,2,3,4,1,2,5,1,2,3,4,5：3 框缺页 9 次、4 框 10 次。根因：FIFO 非栈式算法；LRU/OPT 栈式，无此异常。
哈希表定位 + 双向链表维护顺序，访问/换出都 O(1)——但那是软件缓存的实现。内核每次访存路径上只能靠硬件置 1 位引用位，无法维护完整顺序，所以用 Clock / active-inactive 双链近似。
环形扫指针：A=1 清零放行（给它第二次机会），A=0 淘汰装入新页。直觉 = FIFO 的结构 + LRU 的语义；改进版加脏位：优先淘汰 (A=0,M=0)，(A=0,M=1) 写回后再换，省磁盘写。
活跃页集合超出物理内存，CPU 时间耗在换页 I/O 上，利用率高但吞吐崩。发现：缺页率高 + si/so 高 + CPU 等待高。解决：减并发/加内存/挂起进程（工作集准入），调置换算法无效。
精确 LRU 要全局链表，成本高且多线程争抢——随机采样 5 个 key 逐出最旧，效果足够。LFU 用 8 位对数计数器（概率递增）+ 定期衰减，既省空间又抗"历史包袱"。
新页进 3/8 的 old 区，驻留超 1s 再访问才升 young 区——预读但没用的页在 old 区自然淘汰，全表扫描的冷页不冲 young 热页。一招治"预读失效 + 扫描污染"两个 LRU 经典病。
独立的两级：TLB miss 是"翻译慢"（页表遍历，微秒内），缺页是"数据不在"（磁盘 I/O，毫秒级）。但治理同源：局部性好，TLB 命中率高、工作集小，两者都少——这就是为什么大数据系统痴迷数据布局与预取。
Related & References
哈希表 →（LRU 的 O(1) 载体：LC 146）
Redis 内存淘汰 →（采样 LRU / LFU 的完整实现）
LRU 缓存（手撕实现）→（哈希 + 双链表的 O(1) 结构）
参考来源（本 deck 结论可溯源至下列一手材料）
| OSTEP ch.22（Beyond Physical Memory） | 置换策略谱系与 Belady 异常分析 |
| CSAPP ch.9.4 / OSTEP ch.19（TLB） | 引用位、Clock 的硬件语境 |
| kernel Documentation/admin-guide/mm（multigen_lru） | active/inactive 双链与 MGLRU（6.1+） |
| redis.io topics/lru-cache（maxmemory-samples / LFU） | 采样数默认 5、对数计数器与衰减参数 |
| MySQL 8.0 Manual: InnoDB Buffer Pool（innodb_old_blocks_time） | midpoint insertion 与 1s 驻留阈值 |
| Denning, 1968（Working Set Model） | 工作集与抖动的原始论文 |