页面置换与 IO
内存不够时换谁出去、磁盘 IO 怎么高效，是内存和存储的交界。面试主线：置换算法对比、抖动是什么、IO 模型演进。
页面置换算法
| 算法 | 机制 | 评价 |
|---|---|---|
| FIFO | 先进先出 | 简单，Belady 异常（增加页框反而更多缺页） |
| LRU | 淘汰最久未使用 | 最优的实用近似，硬件支持成本高 |
| 近似 LRU | 访问位/时钟算法（Clock） | 硬件友好的 LRU 近似，Linux 实际使用 |
| LFU | 淘汰使用频率最低 | 防热点冷落，实现复杂 |
| OPT（理论） | 淘汰未来最久不用的 | 最优，但不可实现，用作对比基准 |
Clock 算法（考点）：页框排成环，访问位 1 表示近期用过；指针扫到访问位 0 的淘汰，扫过的 1 清 0。近似 LRU、开销小，Linux 的改进版（二次机会、双链表）就是基于它。
Belady 异常：FIFO 下增加物理页框反而缺页更多。LRU 和 OPT 不会（栈式算法）。
抖动（Thrashing）
- 抖动：进程数太多，每个进程的工作集都放不下，频繁缺页换页，CPU 大量时间花在换页上，吞吐骤降
- 工作集（working set）：进程近期频繁访问的页集合
- 解法：保证每个进程的工作集在内存（限制进程数/分配策略）、局部置换（只换自己的页）
面试话术：抖动的本质是内存过载，不是 CPU 问题。看系统“CPU 忙但吞吐低、磁盘 IO 满”就是抖动。
IO 模型
| 模型 | 机制 | 特点 |
|---|---|---|
| 阻塞 IO | 等数据就绪才返回 | 简单，线程被占用 |
| 非阻塞 IO | 没数据立刻返回，轮询 | 浪费 CPU |
| IO 多路复用 | select/poll/epoll 一次等多个 fd | 单线程管理海量连接（见 Redis 线程模型篇） |
| 异步 IO（AIO） | 内核完成拷贝后通知 | 最彻底，实现复杂 |
| DMA | 外设直接写内存，不占 CPU | 一切高效 IO 的基础 |
DMA 是前提：磁盘数据经 DMA 进内存，CPU 只做发起和收尾。没有 DMA，IO 期间 CPU 全被占用。
零拷贝（sendfile）：数据从磁盘到网卡不经用户态拷贝，靠 DMA 和页缓存直接转发。高性能网络服务的标配（见 Kafka 的高吞吐）。
面试追问
- LRU 和 FIFO？ LRU 按使用时间淘汰（近似最优），FIFO 按进入顺序（有 Belady 异常）
- Clock 算法是什么？ 环状页框 + 访问位扫描：找访问位 0 的淘汰，扫过的清 0。LRU 的硬件友好近似
- 抖动是什么？ 工作集放不下，疯狂缺页换页，吞吐骤降。解法：保证工作集在内存
- IO 多路复用解决什么？ 一个线程等大量连接：select/poll/epoll。高并发网络的基础
- 零拷贝？ 数据不经用户态拷贝直达目标（sendfile + DMA）。Kafka、Nginx 高吞吐的原因之一