CPU 调度
调度器决定下一个运行谁。公平、响应、吞吐是不可兼得的三角：FIFO 吞吐好响应差，轮转响应好吞吐一般。本章讲各策略优化的目标与代价，以及多核调度中的负载均衡与亲和性。
调度的三个目标
Section titled “调度的三个目标”- 周转时间（吞吐导向）：任务从提交到完成的总时间；
- 响应时间（交互导向）：从提交到首次响应；
- 公平：不饿死任何人。
三者矛盾：响应好要求频繁切换（时间片小），频繁切换付出上下文切换成本（→ 进程、线程与上下文切换）拖累吞吐。
FIFO（先来先服务）
Section titled “FIFO（先来先服务）”简单、吞吐好（无切换开销）、护航效应（convoy：一个长任务拖住后面所有短任务）。
SJF（最短作业优先）
Section titled “SJF（最短作业优先）”平均周转时间最优（数学可证），但需要预知作业长度——现实中只能估计，且长任务可能饿死。
轮转（Round Robin）
Section titled “轮转（Round Robin）”时间片轮转：响应时间最好（时间片 / n），时间片过大退化成 FIFO、过小被切换成本吞掉——时间片是响应与吞吐的旋钮（现代 1–10 ms）。
多级反馈队列（MLFQ）
Section titled “多级反馈队列（MLFQ）”用历史行为近似 SJF：多个优先级队列，新任务进最高优先级；用满时间片的（CPU 密集）降级，提前让出的（I/O 密集）留级——交互任务自动获得高优先级与短时间片，CPU 密集任务沉底拿大时间片。MLFQ 用历史行为近似 SJF，无需预知长度；配套防作弊（防游戏调度器：周期性提升所有任务、记账时间片）。
CFS（完全公平调度）
Section titled “CFS（完全公平调度）”Linux 的做法：每个任务记录虚拟运行时间（vruntime），CFS 用红黑树按虚拟运行时间排序，总是运行最小的——理想的"每个任务分到 1/n 的 CPU"的可执行版本。优先级（nice 值）映射成 vruntime 的流速；CFS 用红黑树按虚拟运行时间排序使选取 。
硬实时（截止期错过即失败）用 EDF（最早截止期优先）或速率单调；可调度性可以证明（利用率 ≤ 1 的条件），但需要任务的最坏执行时间可测。
单核策略之上的两个新问题：
- 负载均衡：任务在核间迁移，避免有的核忙死有的闲着；
- 亲和性（affinity）：任务留在原核能保住缓存热度（→ 存储层次与缓存），迁移要付出缓存/TLB 重热成本。
亲和性与负载均衡是一对矛盾：均衡要迁移，亲和要不动。现代调度器的折中：分层域（per-core 队列 + 周期性跨域拉取）、迁移阈值。NUMA（内存有远近之别）让这组矛盾更尖锐：跨 NUMA 节点访存慢 1.5–2 倍，调度还要考虑内存位置。
- 公平、响应、吞吐是三角：时间片是响应与吞吐的旋钮
- SJF 平均周转最优但需要预知长度；MLFQ 用历史行为近似 SJF
- CFS 用红黑树按虚拟运行时间排序：完全公平的可执行版本
- 亲和性与负载均衡是一对矛盾：折中是分层域与迁移阈值
- 实时调度可证明可调度性，前提是最坏执行时间可测