虚拟内存与页面置换：缺页中断、置换算法与抖动

一句话定义

虚拟内存 = 请求分页（按需把页调入内存）+ 页面置换（内存满时换出某些页到磁盘），配合局部性原理，让进程的地址空间可以远大于物理内存。

为什么重要

它让"内存不足"从一个死刑判决变成一个可管理的性能梯度；它也是把 COW、mmap 文件、页缓存（kp-027）缝合在一起的机制枢纽。但它的代价模型同样重要：缺页率失控时的抖动（thrashing）能把系统拖入 seconds-per-page 的深渊——无数"服务器突然卡死"的事故都终结在这里。

前置知识

kp-017（页表与缺页异常）；kp-002（磁盘与内存的数量级差）。

核心概念

• 缺页中断处理：无效页 → 查找后备存储（swap 分区/文件）→ 分配帧调入 → 更新 PTE → 重启指令。
• 局部性原理：时间局部性（刚访问的还会访问）与空间局部性（邻近的会被访问），置换算法的全部可行性都建立在它上面。
• FIFO / Belady 异常：FIFO 可能出现"帧越多缺页越多"的反直觉现象。
• LRU 与时钟（Clock）近似：LRU 理想但硬件开销大，实际用引用位的环形扫描近似。
• 工作集（working set）：时间窗口内活跃页集合，进程必须"装得下工作集"才能高效运行。
• 抖动（thrashing）：总工作集 > 物理内存，系统陷入"换入换出"的空转。

原理与机制

缺页处理全流程：

访问页 P -> TLB 未命中 -> 页表遍历发现 PTE 有效位=0 -> 缺页异常陷入内核
内核: P 有后备(swap/文件)? -> 无: SIGSEGV (段错误, 程序bug)
      有: 找空闲帧; 无空闲 -> 选牺牲页(置换算法)
          牺牲页脏? -> 写回 swap; 否则直接丢弃
      从磁盘调入 P 到帧, 更新 PTE, TLB 装载, 重启触发指令

置换算法对比（访问串 1,2,3,4,1,2,5,1,2,3,4,5，3 帧 vs 4 帧缺页数）：

FIFO: 3帧=9 次, 4帧=10 次   <-- Belady 异常: 加内存反而更差
LRU : 3帧=10 次, 4帧=8 次   <-- 栈式算法, 无异常
Clock(近似LRU): 接近 LRU, 硬件只需 PTE 里 1 个引用位

代价公式（有效访问时间 EAT）：EAT = (1−p)×内存访问 + p×缺页处理，取内存访问 100ns、缺页处理 8ms（含磁盘 I/O），则缺页率 p=1/10000 时 EAT 已达 800ns，8 倍劣化；p 再升一个数量级即接近抖动。这解释了为什么"swap 用了 500MB"本身不是问题、"每秒 si/so 飙升"才是。

直观类比

物理内存像办公桌，磁盘像档案柜：桌面放不下时把最久不用的文件归档（置换），需要时再取出（缺页）。抖动就是文件在桌面与柜子之间来回飞——你全程都在搬文件，没干正事。

实例或案例

vmstat 1                  # si/so 列: 每秒换入/换出页数, 持续非零即疑似抖动
sar -B 1                  # 缺页率 majflt/s（重要缺页, 需要磁盘 I/O 的那种）
cat /proc/meminfo         # SwapTotal/SwapFree/Cached 全景
ps -eo pid,rss,vsz,cmd --sort=-rss | head   # 物理内存大户 RSS 排名

制造抖动实验：程序顺序遍历一个远大于物理内存的数组（malloc(100GB) 循环写入），观察 vmstat 的 si/so 同时飙升、吞吐崩塌——这就是缺页率的物理呈现。

常见误区

• Swap 使用率高 = 内存不足：只要 majflt 低、si/so 平稳，冷页躺在 swap 里反而是高效利用。
• LRU 被硬件直接实现：真实硬件只有引用位，操作系统用时钟算法近似，实时系统另有 LRU-K 等变体。
• 认为缺页都是故障：程序首次启动的页加载、COW 触发、文件 mmap 首读，全是"良性缺页"。

与其他知识点的关系

缺页的三种触发（首次调入、COW、保护错）连接 kp-007 与 kp-017；文件页与匿名页的回收策略连接 kp-027 页缓存；Linux 的回收工程实现见 kp-019。

延伸阅读

Denning 1968 工作集模型论文；《操作系统概念》第 9 章含各置换算法完整演算。

自测题

1. Belady 异常说明什么？

答：FIFO 不是栈式算法，增加物理帧数反而可能增加缺页；LRU 等栈式算法无此异常。

1. 为什么用时钟算法而不是真 LRU？

答：真 LRU 需要每次访存更新链表，硬件代价不可接受；时钟算法仅用 PTE 的引用位加环形指针扫描，以近似的准确性换取可实现的成本。

1. 如何区分"swap 占用高但健康"与"正在抖动"？

答：看动态指标——majflt/s 与 vmstat 的 si/so：前者平稳接近零即健康；后者持续高位、CPU 大量时间消耗在系统态，即抖动。