CPU 调度 — 公平与响应之间的交易
一句话总结
调度器是一项政策：它要在吞吐量、等待时间、响应时间和公平性这些相互冲突的目标之间决定牺牲什么。
为什么需要了解这些
可运行进程多于核心时，必然有人等待。仅改变运行顺序，同一组任务的平均等待时间就可能相差数倍。假设三个进程的 CPU burst 分别为 24、3、3，并同时到达：
- 按 P1、P2、P3 执行，等待时间为 0、24、27，平均为 17。
- 按 P2、P3、P1 执行，等待时间为 6、0、3，平均为 3。
完成相同工作所需总时间不变，平均等待时间却相差五倍以上。短任务排在长任务后的现象称为护航效应(convoy effect)，是先来先服务 FCFS 的典型弱点。
工作原理
主要算法可概括如下。
| 算法 | 抢占 | 饥饿 | 优点 | 弱点 |
|---|---|---|---|---|
| FCFS | 否 | 否 | 简单 | 护航效应 |
| SJF | 否 | 是 | 平均等待时间最优 | 无法知道下一次 burst |
| SRTF | 是 | 是 | 响应优于 SJF | 需要预测，切换增加 |
| 优先级 | 两者皆可 | 是 | 可反映政策 | 饥饿，需要老化 |
| 轮转 | 是 | 否 | 响应时间均衡 | 时间片难以选择 |
| 多级反馈队列 | 是 | 可能 | 最灵活 | 参数很多 |
SJF 可证明在平均等待时间上最优，但有致命问题：无法预知下一次 CPU burst 长度。 实现中通常用过去 burst 的指数平均预测：新预测值 = α×最近实测值 + (1−α)×上次预测值，α 常取 0.5。
轮转调度的关键是时间片。过大就退化为 FCFS，过小则上下文切换成本会吞噬真正的工作时间。经验上会让 80% 的 CPU burst 能在一个时间片内结束。
Linux CFS 从另一角度处理公平性。它追踪每个任务的虚拟运行时间(vruntime)，选择最小者运行。vruntime 等于实际运行时间除以权重，权重来自 nice 值。nice 越低（优先级越高），权重越大，vruntime 增长越慢，因此更常被选择。任务以红黑树管理，插入删除为对数时间，最左节点始终是下一个运行对象。
实际工作中的表现
容器 CPU 限制直接使用这些概念。cgroup CPU 份额(shares/weight)相当于 CFS 权重，只在竞争时决定比例；CPU 配额则限制每个周期可用时间。份额降低并不会阻止容器使用空闲 CPU。
配额还有另一陷阱：多线程应用可能在周期开始时耗尽配额，随后整个应用停到下一周期，发生节流。若平均 CPU 利用率不高但尾延迟突增，应先看节流计数器。
不使用 CPU 的等待更常见
以上讨论的是就绪进程争夺 CPU，但真实服务器中，大部分等待时间来自等待 I/O 完成。混淆两者会使性能诊断完全走偏。
负载平均值(load average)是典型误区。Linux 不仅统计可运行进程，也统计等待磁盘 I/O 的进程。 因而 CPU 使用率 20%、负载平均值 30 完全可能。此时增加 CPU 没有效果，应检查磁盘或网络。
进程状态能直接显示区别：R 表示正在运行或等待运行，D 表示不可中断等待。 D 状态长期持续时，进程连信号也无法响应；存储停顿时，大量进程甚至无法退出，正是这个原因。
等待本身也影响调度。等待很久后唤醒的进程此前没有使用 CPU，所以 vruntime 较小，会优先运行。交互程序响应迅速正得益于此：等待键盘输入期间 vruntime 不增长，输入到达后便可超越一直计算的进程先运行。
因此诊断响应缓慢时，不能只看 CPU 使用率。 应先区分运行队列过长、I/O 等待过长，还是发生了配额节流。三者的原因和应对完全不同，一张 CPU 图无法区分它们。
后续测验将确认什么
确认你能计算为何同一任务集合仅改变顺序就会改变平均等待时间，并解释 CFS 如何用 vruntime 表达优先级。