# 第 5 章 调度与 CPU 虚拟化
> 一个物理核要假装成多个 CPU，靠的是"谁该在下一纳秒上 CPU"这个决策的连续正确性。
## 学习目标
读完本章，你应当能够：
1. 论证吞吐、延迟、公平三者不可能同时最优，并指出任意调度算法至少牺牲哪一项。
2. 说出 FCFS/SJF/优先级/轮转/MLFQ 各自的致命场景，以及 MLFQ 的防欺骗规则在机制上封住了什么。
3. 用 `vruntime` 更新公式和 `nice → weight` 表，手算多进程场景下的 CPU 份额比与各自时间片。
4. 解释新唤醒进程的 `vruntime` 为什么必须被拉到 `min_vruntime` 附近，以及不这么做会导致哪两种灾难。
5. 区分 `SCHED_NORMAL`/`BATCH`/`IDLE`/`FIFO`/`RR`/`DEADLINE`，说明实时进程如何饿死普通进程。
6. 解释 CPU 缓存亲和为什么常常比负载均衡更重要，并说出 `sched_domain` 与 NUMA 感知调度的分工。
7. 拆解一次上下文切换的开销构成，用 `vmstat` 的 `cs` 与 `pidstat -w` 区分自愿/非自愿切换。
8. 说明 CPU 虚拟化的两条技术路线与 KVM 依赖的硬件辅助，以及除 CPU 外还有哪些资源必须虚拟化。
### 前置知识检查
| 你需要知道 | 在哪一节补齐 |
|---|---|
| cache 层次、cache line、主存访问延迟量级 | 见第 1 章 1.1 节 |
| `fork`/`clone`、进程状态、内核栈与用户栈的区分 | 见第 4 章 4.1、4.2 节 |
| 用户态/内核态切换与时钟中断的基本路径 | 见第 9 章 9.1、9.3 节 |
| 页表与 TLB 的作用 | 见第 8 章 8.2 节（本章只用到"换页表会失效 TLB"这一结论） |
## 5.1 调度的三个目标与根本矛盾
调度器要在每个可运行实体（runnable entity，Linux 中即 `task_struct`）之间分配稀缺资源：CPU 时间，而它同时被三个目标拉扯。
| 目标 | 度量口径 | 极端最优策略 | 代价 |
|---|---|---|---|
| 吞吐（throughput） | 单位时间完成的任务数 | 任务尽量跑完再切换（切换有成本） | 先到的长任务占住 CPU，短任务全部等待 |
| 延迟（latency） | 就绪到首次上 CPU、以及完成时间的分布（p50/p99） | 谁快到期限谁先跑（近似 SJF/SRTF） | 必须预知未来；长任务无限延后 |
| 公平（fairness） | 各任务 CPU 占比是否与权重成比例 | 严格按权重轮转，粒度越细越公平 | 时间片趋近 0 时全部时间花在切换上 |
三者的矛盾是**结构性的**：一次上下文切换约 1~5 μs（口径：`vmstat` 的 `cs` 与 `perf sched` 统计，含直接开销），时间片缩到与之同量级，CPU 就有一半时间在保存/恢复现场；把长任务一次跑完吞吐最高，但排在后面的短任务延迟爆炸（FCFS 的护航效应）；严格公平又会让交互任务每次只拿到几毫秒，用户感知仍然抖动。
> [!IMPORTANT]
> 不存在完美调度器，因为最优性依赖**任务未来行为**（下次何时就绪、要跑多久），而它在运行前不可知。所有实用调度器都是"用可观测的历史去近似未来"，每一个都有专门的对抗负载（adversarial workload）。面试时若答"硬件不够快所以做不到完美"，就直接跑偏了。
**抢占式（preemptive）vs 非抢占式（non-preemptive）**：判据只有一条——**运行中的任务能否被外力夺走 CPU**。非抢占式下任务自己让出（终止、阻塞、主动 `sched_yield`），实现简单，但一个死循环任务能锁死整个系统。抢占式下内核在中断返回点检查 `TIF_NEED_RESCHED` 标志，必要时调用 `schedule()` 换人；触发源有三类：时钟中断（时间片耗尽）、更高优先级任务唤醒时 `try_to_wake_up` 中的可抢占判断、用户态信号的投递点。`CONFIG_PREEMPT_NONE`/`VOLUNTARY`/`PREEMPT`/`PREEMPT_RT` 的差异只在于**内核态代码是否也可被抢占**；用户态任务在 Linux 上始终可抢占。
> [!NOTE]
> 追问点："抢占的检查点为什么放在中断返回路径，而不是每条指令之间？"因为抢占需要一次内核态入口，中断返回是已有的、开销固定的检查窗口；逐指令比对优先级需要硬件在每个指令边界介入，收益远不抵成本。
## 5.2 经典调度算法速查：每个算法的致命场景
下面五种算法本科都讲过，本节只保留**面试官用来区分"背过"还是"懂"的那一列**。
| 算法 | 一句话机制 | 致命场景（面试必答） | 是否抢占 |
|---|---|---|---|
| 先来先服务（first-come first-served, FCFS） | 按到达顺序排队，队头不完成不换人 | **护航效应**：100 ms 的 CPU 密集任务后面排着 100 个 1 ms 任务时，平均等待被队头拉爆；平均周转时间对顺序极敏感 | 否 |
| 最短作业优先（shortest job first, SJF） | 每次选剩余运行时间最短的 | **要求预知未来**；只能用历史值预测，任务突然变长就失准；持续到达的短任务会无限推迟长任务 | 否 |
| 最短剩余时间优先（shortest time-to-completion first, STCF） | SJF 的抢占版：新任务剩余更短就换人 | 同样依赖预知；短任务密集到达时长任务几乎拿不到 CPU | 是 |
| 优先级调度（priority scheduling） | 选优先级最高者 | **饥饿**：持续有高优先级任务到达时低优先级永不运行。解法只有老化（aging），但老化速度又要调参 | 两者皆可 |
| 轮转（round robin, RR） | 按到达顺序轮流，每人固定时间片 `q` | **`q` 是死结**：太大退化成 FCFS；太小时切换占比约 `c/(q + c)`（`c` 为切换成本）；响应时间也不随 `q` 缩小而线性变好 | 是 |
| 多级反馈队列（multi-level feedback queue, MLFQ） | 多级队列 + 按行为动态调优先级 + 周期性提升 | **可以欺骗**：在时间片快耗尽前主动让出 CPU，就能长期留在高优先级队列 | 是 |
**MLFQ 的五条规则**（能说出编号与"每条堵的是什么洞"，层次立刻不同）：
```text
规则 1：Priority(A) > Priority(B) ⟹ A 运行（B 不运行）
规则 2：Priority(A) = Priority(B) ⟹ A、B 按轮转共享该优先级的时间片
规则 3：新任务进入最高优先级队列
规则 4a：任务用完整时间片 ⟹ 优先级降一级（判定为 CPU 密集，惩罚）
规则 4b：任务在时间片用完前主动放弃 CPU ⟹ 优先级不变（判定为交互，奖励）
规则 5：每经过时间周期 S，把所有任务提升到最高优先级（防饥饿、防行为变化后不被重识别）
```
规则 4b 是**欺骗入口**：纯 CPU 密集进程只要在时间片耗尽前做一次无关 I/O，就能永久霸占高优先级队列。防欺骗方案是**记账改造**：不看"是否在时间片内放弃"，而是记录每层累计消耗的 CPU 时间（total accounting），累计到阈值就降级。
> [!WARNING]
> MLFQ 最常见的错误回答是"高优先级时间片短、低优先级时间片长"。时间片长度确实是参数，但**不是机制核心**；核心是"用观测到的行为反推任务类型，再用优先级编码这个推断"。被追问"MLFQ 与 CFS 的本质差别"时，落点应是：**MLFQ 靠离散队列与启发式分类（猜测），CFS 靠连续权重与精确的虚拟时间记账（按比例分配）**。
## 5.3 CFS 完整机制：vruntime 与红黑树
完全公平调度（Completely Fair Scheduler, CFS）是 `SCHED_NORMAL` 的实现。它的出发点是反问：**"如果 CPU 是能被无限细分的资源，公平应该长什么样？"** 理想模型是 N 个任务各以 `1/N` 速度并行推进；单核只能用极小粒度轮流逼近，而这会撞上切换开销。CFS 的解法是**不分配时间片，只维护虚拟时间**。
### 5.3.1 vruntime 更新公式
```text
vruntime += 实际运行时间 × (NICE_0_LOAD / weight) NICE_0_LOAD = 1024
含义：权重越大（nice 越小），每消耗 1 ns 真实 CPU 时间，记账的 vruntime 增长越慢
⟹ 越晚被追上 ⟹ 分到越多 CPU
为什么这样就自动按比例分配？设 A、B 同时在就绪队列中，交替运行直到两者 vruntime 追上：
vruntime_A = (1024 / weight_A) × t_A
vruntime_B = (1024 / weight_B) × t_B
追上时两者相等 ⟹ (1024 / weight_A) × t_A = (1024 / weight_B) × t_B
⟹ t_A / t_B = weight_A / weight_B
```
**CPU 时间严格正比于权重**，不需要额外的比例控制逻辑——比例是记账方式的副作用。
### 5.3.2 红黑树：最左节点就是下一个
`vruntime` 是单调递增的键，就绪队列只需"快速取最小 + 快速插入 + 快速删除任意节点"。CFS 选红黑树（`cfs_rq.tasks_timeline`）：
```text
red-black tree keyed by vruntime
(min on the left)
(42)
/ \
(28) (67)
/ \ / \
(17) (31) (55) (89)
▲
rb_leftmost 缓存指针 ⟹ O(1) 取下一个，无需每次 O(log n) 下潜
插入（唤醒/新建）O(log n)，需旋转再平衡（树高上界 2·log₂(n+1)）
删除（阻塞/退出）O(log n)；取最小（热路径）O(1)，靠 rb_leftmost 缓存
为什么不选堆：二叉堆取最小也是 O(1)（看根），但"删除任意节点"（阻塞、
唤醒重入队、改优先级、被迁移）需要 decrease-key 且实现繁琐；红黑树对
任意键都是 O(log n) 且实现成熟。
```
### 5.3.3 时间片由 sched_latency、min_granularity、nr_running 共同决定
CFS 不存固定时间片，每次调度时现算：
```text
调度周期 = max( sched_latency_ns , nr_running × min_granularity_ns )
sched_latency_ns 默认 6 ms（早期内核 12 ms）
min_granularity_ns 默认 0.75 ms
任务 i 的时间片 = 调度周期 × weight_i / Σ weight_j （j 为本 CPU 全部可运行任务）
```
- `sched_latency` 是**目标周期**：可运行任务不多时，希望这段时间内每个任务至少被调度一次，从而控制响应量级。
- `nr_running` 一旦使 `nr_running × min_granularity > sched_latency`，周期就**被撑大**，因为不能让任何任务的时间片小于 `min_granularity`。
- `min_granularity` 是**切换开销的护栏**：保证时间片显著大于一次切换（约 1~5 μs），代价是任务数极大时周期拉长、延迟变差。
> [!TIP]
> 心算口诀：`时间片 = 周期 × 我的权重 / 总权重`。被追问"200 个任务同时可运行时呢"，先算周期 `200 × 0.75 ms = 150 ms`，再按权重分。这解释了为什么满载机器上单任务响应明显变差：**问题不在切换本身，而在调度周期被 `min_granularity` 撑到了上百毫秒**。
### 5.3.4 nice → weight 换算表与算例
内核用预计算表 `sched_prio_to_weight` 把 nice 映射到权重，规则是每级约 `1.25` 倍，且 `nice 0 ⟹ 1024`：
| nice | weight | nice | weight | nice | weight |
|---|---|---|---|---|---|
| −20 | 88761 | −5 | 3121 | 3 | 526 |
| −15 | 29154 | −4 | 2501 | 5 | 335 |
| −10 | 9548 | −3 | 2004 | 10 | 110 |
| −1 | 1277 | −2 | 1605 | 19 | 15 |
| 0 | 1024 | 1 | 820 | — | — |
由表可直接验证必须记住的三个倍数：
| nice 差 | 权重比（低 nice 方 : 高 nice 方） | 通俗表述 |
|---|---|---|
| 1（0 对 1） | 1277 / 1024 = 1.247 | 低 nice 一方约多拿 25% |
| 19（−20 对 19） | 88761 / 15 = 5917 | 近乎独占 |
| 5（0 对 5） | 1024 / 335 = 3.057 | "差 5 约 3 倍" |
| 10（0 对 10） | 1024 / 110 = 9.31 | "差 10 约一个数量级"（约 9.3 倍） |
**完整算例**：某 CPU 上有三个可运行任务 A(nice 0, weight 1024)、B(nice 0, weight 1024)、C(nice 5, weight 335)。
```text
Σ weight = 1024 + 1024 + 335 = 2383
调度周期 = max(6 ms, 3 × 0.75 ms) = max(6, 2.25) = 6 ms
时间片：
A = 6 ms × 1024/2383 = 2.579 ms
B = 6 ms × 1024/2383 = 2.579 ms
C = 6 ms × 335/2383 = 0.843 ms
验证 vruntime 步长（三个任务各跑满自己的时间片）：
Δvruntime_A = (1024/1024) × 2.579 ms = 2.579 ms
Δvruntime_B = (1024/1024) × 2.579 ms = 2.579 ms
Δvruntime_C = (1024/ 335) × 0.843 ms = 3.057 × 0.843 ms = 2.579 ms
⟹ 三者 vruntime 步长完全相同。这就是"完全公平"的准确含义：
公平的对象是虚拟时间，而不是真实时间。
```
> [!IMPORTANT]
> 加分点在于用"C 每跑 1 ms 真实时间，vruntime 就跑 3.057 ms"来解释 C 的时间片为何只有 A 的约 1/3。只会答"nice 小的权重大所以分时间多"，说明只知结论；能写出 `Δvruntime = 实际时间 × 1024/weight` 并算出三者步长相等，才算摸到机制。
## 5.4 min_vruntime：新唤醒进程的 vruntime 从哪来
`vruntime` 只在任务**占用 CPU** 时增长，睡眠期间不增长。于是必须回答：**刚 `fork` 出来或刚睡醒的任务，`vruntime` 初值设为多少？** 两个直觉答案各有灾难：取 `0`（或任意极小值）时它是队列最小值，会被连续选中直到追平队列——每秒 `fork` 上千次的短连接服务因此可独吞 CPU，把老任务饿死，这是 fork bomb 的调度版本；取"队列当前最大值"看似安全，却既惩罚了真正交互的新任务，又没解决根本问题——睡眠任务沿用它入睡时的旧 `vruntime`（睡眠期间被冻结），醒来时早已远小于 `min_vruntime`。Linux 的做法：每个 `cfs_rq` 维护 `min_vruntime`（队列上 vruntime 的最小值，随最左节点前移单调上升），新唤醒/新创建任务的 `vruntime` 被**设置为不低于 `min_vruntime`**——`place_entity()` 先按 `sched_vslice()` 算出该任务应得的时间片并折算成 vruntime 补贴，再取补贴结果与 `min_vruntime` 的较大者。
```text
min_vruntime 的演化与唤醒放置
vruntime 轴 ──────────────────────────────────────────────▶
▲ ▲ ▲
min_vruntime A(在跑) B(阻塞中，vruntime 冻结)
│
│ 新任务 C 唤醒：vruntime 被拉到 min_vruntime 附近（略偏右）
▼
┌───────────┬───────────┬───────────┐
│ min_vrt │ C │ A │ C 要等 A 跑完这一轮才轮到
└───────────┴───────────┴───────────┘
```
> [!NOTE]
> `min_vruntime` 是高频考点，因为它用同一个动作解决两个相反方向的问题：**防止新任务饿死老任务**（不让新任务的 vruntime 远小于队列最小值），也**防止长期睡眠任务醒来独占 CPU**（不让它历史遗留的小 vruntime 生效）。注意"睡眠任务醒来后 vruntime 落后"是**必然**的（睡眠期间不记账），必须由 `place_entity()` 主动修正。追问下一层："那唤醒补贴不是又让它插队了吗？"——补贴量由 `sched_vslice()` 按权重给出，但仍以 `min_vruntime` 为下界，因此最多让高权重任务少等一轮，不会形成独占。
## 5.5 调度类与优先级：实时进程如何饿死普通进程
Linux 按"调度类（scheduling class）"分层，每层是独立的调度器实现，**高层的类只要队列非空，低层就完全没机会**。
| 调度类 | 策略常量 | 优先级 | 机制要点 | 典型用途 |
|---|---|---|---|---|
| `stop_sched_class` | — | 最高（内部） | 用于 CPU 热插拔、停机 | 内核内部 |
| `dl_sched_class` | `SCHED_DEADLINE` | 最高（用户可见） | 按 `(runtime, deadline, period)` 做 CBS/EDF 带宽预留，每周期最多用 `runtime`，超了被 throttle | 硬实时、音视频流水线 |
| `rt_sched_class` | `SCHED_FIFO`/`SCHED_RR` | 1~99（越大越优先） | 按实时优先级位图选最高队列；`FIFO` 不吃时间片，`RR` 吃固定时间片后轮转到同优先级队尾 | 中断下半部线程、低延迟采集 |
| `fair_sched_class` | `SCHED_NORMAL`/`SCHED_BATCH`/`SCHED_IDLE` | nice −20~19 | CFS；`BATCH` 标记为非交互、不做唤醒抢占；`IDLE` 权重极低，只在 CPU 空闲时才跑 | 普通进程、批处理、后台任务 |
| `idle_sched_class` | — | 最低 | 每 CPU 一个 idle 线程 | 省电 |
`nice` 与实时优先级是两套独立编号：`nice` 是 −20~19（越小越优先），实时优先级是 1~99（越大越优先），且**任意实时进程都优先于任意 nice 进程**。
```text
内核内部优先级 prio（0 最高，139 最低）
0 ─────────── 99 ──────────────── 100 ──────────────── 139
│ stop / dl │ 实时 RT (1~99) │ CFS: nice -20 ~ 19 │
│ │ 映射 prio 0~99 │ 映射 prio 100~139 │
└─────────────┴────────────────────┴───────────────────────┘
```
**"实时进程会把普通进程饿死"不是 bug，是语义**：RT 类队列非空时 CFS 队列根本不被查询，一个优先级 1 的 `SCHED_FIFO` 死循环线程就能让该核上的普通任务永久得不到调度。两个实际后果：设置 RT 优先级需要 `CAP_SYS_NICE`（或 `RLIMIT_RTPRIO`），否则普通用户即可瘫痪整台机器；RT 任务默认受**带宽限制**保护，`sched_rt_runtime_us`（默认 950000 μs）与 `sched_rt_period_us`（默认 1000000 μs）意味着 RT 任务每 1 s 最多占用 950 ms，留 50 ms 给普通任务，设为 `-1` 才是真正不限制——这是排查"RT 任务为何偶尔卡一下"时该看的第一个旋钮。
> [!CAUTION]
> 常见答崩方式：把"优先级"当成单一维度，说"`SCHED_FIFO` 优先级是 0，所以排在 nice 后面"。实时优先级**数值越大越优先**，与 nice 方向相反，两套编号也不通用；被追问"`nice -20` 与 `SCHED_FIFO` 优先级 1 谁先跑"答错，就暴露没用过 `chrt`。
`SCHED_DEADLINE` 单独记一句：它不是"更高优先级的 RT"，而是**带宽预留**。参数须满足 `runtime ≤ deadline ≤ period`；内核用 EDF 在 dl 任务间排序，并在 `runtime` 用尽时强制 throttle——所以它会"跑着跑着被停"，与 `SCHED_FIFO` 的"跑到自己让出为止"是两种不同的保证。
## 5.6 多核调度：亲和性、负载均衡与 sched_domain
多核引入了单核不存在的问题：**任务放在哪个 CPU 上跑**。两条原则相互冲突。**CPU 亲和性（CPU affinity）**：任务在某核跑过后，其数据与指令大概率还在该核私有 cache（L1/L2）里；迁移意味着私有 cache 作废并重新填充——**L1 命中约 1 ns、L3 约 15 ns、主存约 100 ns（口径：单次访存延迟量级）**，一次迁移省下的均衡收益很容易被 cache 冷启动吃掉，这就是实践中**缓存亲和收益常大于负载均衡收益**的原因。**负载均衡（load balancing）**：又不能因为亲和就把 8 个任务全堆一核、让其余 7 核空转。调和工作交给层次化的**调度域（sched_domain）**：均衡只在域内进行，且范围越大触发越稀疏。
```text
sched_domain 层次（自底向上，范围越大、均衡越贵、触发越稀疏）
┌─────────────────── NUMA node ─────────────────────┐ ← 迁移最贵：跨节点访存约 1.5~2 倍
│ ┌────────── 物理封装 package ──────────────────┐ │
│ │ ┌── L2 共享域 ──┐ ┌── L2 共享域 ──┐ │ │
│ │ │ SMT 同核两线程 │ │ SMT 同核两线程 │ ... │ │
│ │ │ CPU0 CPU1 │ │ CPU2 CPU3 │ │ │
│ │ └───────────────┘ └───────────────┘ │ │
│ └───────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────┘
均衡顺序：同核兄弟线程间 → 同 package → 同 NUMA 节点 → 跨节点
越往外层越"不情愿"：迁移破坏 cache 亲和，跨 NUMA 还要多付内存延迟
```
| `load_balance()` 触发时机 | 触发点 | 特点 |
|---|---|---|
| 周期性均衡 | 调度 tick 上按 `sched_domain` 的 `balance_interval` 检查（idle 的 CPU 更频繁） | 慢速、逐步拉平，避免抖动 |
| 新建任务时 | `fork` 后 `select_task_rq_fair()` 按 `wake_affine` 等启发式选核 | 从源头避免不均 |
| 唤醒任务时 | `try_to_wake_up` → `select_task_rq` | 优先放回上次运行的核（保 cache），除非该核明显过载 |
| 空闲核主动拉取 | idle 的 CPU 进入 `newidle_balance()` 偷任务 | 解决"一核忙死、一核空转"，不打断忙核 |
| 拉取失败时 | 退回 `active_balance`，向目标 CPU 发 IPI 让它自己把任务推出去 | 跨核迁移必须由源/目标 CPU 在安全上下文执行 |
> [!IMPORTANT]
> 高频追问："为什么不让忙的 CPU 直接把任务推给空闲 CPU，而非要空闲 CPU 来拉？"因为忙 CPU 并不知道哪个核真空闲，逐个试探要发 IPI（跨核中断，成本高且打断对方 cache 局部性）；空闲 CPU 最清楚自己空闲，由它发起可把探测成本降到最低，还天然收敛为"N 个空闲核不会同时抢同一个任务"。
**NUMA 感知调度（NUMA-aware scheduling）**：多路机器上每个 NUMA 节点有本地内存，跨节点访存延迟约为本地的 1.5~2 倍。调度器做两件事：NUMA 层均衡设更高门槛，且迁移时同步改掉任务的"首选节点"，否则它在远端跑还要访问本地内存；自动 NUMA balancing（`/proc/sys/kernel/numa_balancing`）周期性把部分页设为 `PROT_NONE`，用缺页捕捉任务真正访问哪块内存，再把任务或页迁到同一节点（缺页路径见第 8 章 8.3 节）。
```bash
# -p 作用于已有 PID，-c 表示用 CPU 列表而非位掩码
taskset -pc $$ # 看当前 shell 能在哪些 CPU 上跑
taskset -pc 0,3 12345 # 把 PID 12345 绑到 CPU 0 与 3
# numactl 同时控制 CPU 亲和与内存分配节点，用来验证 NUMA 局部性收益
numactl --cpunodebind=0 --membind=0 ./service # CPU 与内存都锁在节点 0
numastat -p $(pidof service) # 看本地/远端节点的内存分布
```
> [!TIP]
> 高并发服务的常见调优是"一个 worker 线程固定绑一核 + 关闭该核的自动 NUMA balancing"，目的是压掉迁移带来的尾延迟抖动（p99），平均吞吐往往没有明显变化。把这个 trade-off 说清楚——**绑核优化的是延迟的稳定性，不是吞吐**——比背 `taskset` 语法有价值得多。
## 5.7 上下文切换：开销构成与量化
上下文切换（context switch）是"内核保存一个任务的可恢复执行状态，并恢复另一个任务的同类状态"。它贵不在切换这个动作，而在**切换导致的环境失效**。
```text
直接开销：① 保存寄存器现场（通用寄存器、PC、SP、标志位）
② 切换内核栈与 thread_info / task_struct 指针
③ 更新 rq->curr、结算 vruntime 记账、把旧任务插回红黑树
④ 从 rb_leftmost 取下一个任务，恢复它的寄存器现场
⑤ 切换 mm_struct ⟹ 换 CR3 ⟹ TLB 失效（有 PCID 时不必全刷）
⑥ 切换浮点/SIMD 状态、调试寄存器（多为惰性恢复）
间接开销（不花指令，却让后续代码变慢，最常被漏答）：
A. TLB 冷启动：原有地址翻译失效，重新走页表遍历
B. 私有 cache 污染：新任务把旧任务的工作集挤出 L1/L2
C. 分支预测器状态被搅乱：预测表混入另一个任务的跳转历史
D. 流水线前端冲刷：跳转到新 PC，取指单元重新填满
```
| 指标 | 典型量级 | 观测方式 |
|---|---|---|
| 直接开销（保存/恢复 + 栈切换） | 约 1~3 μs | `perf stat -e context-switches`、`perf sched latency` |
| 含 TLB/cache 间接影响的端到端 | 约 3~5 μs；大工作集或跨 NUMA 可到 10 μs 以上 | 微基准（`lmbench` 类测试的 `lat_ctx`） |
| 与系统调用的对比 | 系统调用约 100 ns ~ 1 μs，即切换比"进一次内核"还贵数倍 | `perf stat`、`strace -c` |
| 线程 vs 进程切换 | 同进程内线程共享 `mm_struct`，不换 CR3，省掉 TLB 冲刷与页表遍历 | `/proc/[pid]/status` 的 `voluntary_ctxt_switches` |
> [!NOTE]
> 现代 CPU 用 PCID（process-context identifier，`CR3` 中的地址空间标识，见 Intel SDM 对 CR3 的描述）缓解 TLB 冲刷：给地址空间打标签，切换时不必清空 TLB，只失效被复用的标签。这是"线程切换比进程切换便宜"被削弱的原因；答"进程切换慢因为要换页表"不算错，但不知道 PCID 就答不出"慢多少取决于 TLB 覆盖了多少工作集"。
自愿切换 vs 非自愿切换，是排查中区分"进程在等"和"进程被抢"的分水岭：
| 类型 | 产生原因 | 观测字段 | 高值意味着什么 |
|---|---|---|---|
| 自愿切换（voluntary） | 主动阻塞：等 I/O、等锁、`sleep`、`read` 无数据 | `/proc/[pid]/status` 的 `voluntary_ctxt_switches` | 时间花在等待上，瓶颈很可能在 I/O 或锁竞争，而非 CPU |
| 非自愿切换（involuntary） | 时间片耗尽被抢占，或被更高优先级任务插队 | `nonvoluntary_ctxt_switches`；`pidstat -w` 的 `nvcswch/s` | 任务想跑却抢不到 CPU：CPU 饱和、被 RT 任务压制、或频繁被中断打断 |
```bash
vmstat 1 # r 列是可运行队列长度；cs 是每秒上下文切换数；in 是每秒中断数
# r b swpd free buff cache si so bi bo in cs us sy id wa st
# 2 0 0 812345 12345 456789 0 0 12 34 1200 3400 8 4 88 0 0
# cs 极高（数十万/秒）而 us+sy 不高 ⟹ 切换本身在吃 CPU，属于调度抖动
pidstat -w -p $(pidof service) 1
# UID PID cswch/s nvcswch/s Command
# 999 1234 1200.0 85.0 service
# 判断口诀：cswch/s 高 ⟹ 在等资源；nvcswch/s 高 ⟹ 抢不到 CPU
```
## 5.8 CPU 虚拟化：敏感指令与 KVM 的硬件辅助
CPU 虚拟化要在一台物理机上同时跑多个操作系统实例，且每个实例都以为自己独占 CPU。难点非常具体：**guest 内核里的特权指令怎么办？** 一类是**特权指令（privileged instruction）**，如 `lgdt`、`mov cr3`、`hlt`，在用户态执行会触发异常，可让 guest 内核陷入（trap）到 hypervisor 由其模拟——**陷入-模拟（trap-and-emulate）**，前提是硬件必须在非特权模式下执行它们时陷入；另一类是**敏感指令（sensitive instruction）**，会读取或改变系统状态，其中一部分在传统 x86 上**用户态执行不陷入**（如 `sgdt`/`sidt` 直接返回真实值），这类"敏感但非特权"的指令构成**虚拟化漏洞（virtualization hole）**，使纯陷入模拟在 x86 上不可能实现，必须靠二进制翻译或半虚拟化绕过。
| 路线 | 机制 | 代价 | 代表 |
|---|---|---|---|
| 陷入模拟 | 敏感指令在非特权态执行触发异常，hypervisor 捕获后模拟；对能陷入的指令（`hlt`、I/O 端口访问）效率高 | 每条被模拟的指令都是一次 VM exit，成本比系统调用高一到两个数量级 | KVM 对多数特权指令的处理 |
| 二进制翻译 | 扫描 guest 内核代码，把"敏感但不陷入"的指令就地改写成能陷入的形式并缓存翻译块 | 首次执行要扫描与改写，难处理自修改代码；好处是不改 guest | 纯软件全虚拟化思路 |
| 半虚拟化（paravirtualization） | 改 guest 内核源码，把敏感操作换成显式 hypercall | 必须能改 guest 内核（闭源系统不行），性能最好 | `virtio` 系列设备驱动 |
| 硬件辅助 | CPU 原生提供两种运行模式，敏感指令与特权访问自动触发 VM exit | 需要 CPU 支持，VM exit 本身仍有固定成本 | Intel VT-x、AMD-V |
**KVM 的定位**：KVM 只是 Linux 内核模块，提供 `/dev/kvm` 与 `KVM_RUN` ioctl，把 QEMU 之类用户态程序变成 VMM。guest 的 vCPU 就是宿主上的一个线程；`KVM_RUN` 让物理 CPU 进入非根模式（non-root operation）直接执行 guest 代码，遇到必须由 hypervisor 处理的事件（`EXIT_REASON`）才退出到根模式。**KVM 不模拟 CPU、也不逐条翻译指令**，只做"硬件虚拟化能力的转发与调度"，因此 guest 性能上限由 VM exit 次数与单次处理成本决定。
| 扩展 | 虚拟化的对象 | 解决的问题 |
|---|---|---|
| VT-x（`VMX`）与 EPT | CPU 本身与内存地址翻译 | 提供根/非根模式与 `VMCS`（虚拟机控制结构），存放 guest/host 状态与退出原因；`EPT`（extended page tables）让"guest 物理地址 → 宿主物理地址"的翻译由硬件完成，避免每次访存都 VM exit，也消除了"影子页表"的软件同步开销 |
| VT-d / IOMMU | 设备直通（passthrough）时的 DMA | 没有 IOMMU 时直通设备的 DMA 用真实物理地址，可绕过 hypervisor 读写任意内存；VT-d 提供设备侧地址翻译与中断重映射，使直通在安全前提下可用 |
> [!IMPORTANT]
> "CPU 是唯一被虚拟化的资源吗？"答案必须是否定的，且要逐类说清主体与陷阱：
> **内存**靠 EPT 做二级翻译，坑在超分 + 气球驱动（ballooning）+ KSM 页合并，
> 共享物理页必须写时复制，否则一个 guest 的写入会污染另一个（机制见第 4 章 4.2 节）；
> **I/O** 最贵：全模拟设备每次访问都 VM exit，`virtio` 用共享内存环（virtqueue）把"每次一个 exit"
> 降到"批量几个 exit"，直通（VFIO）几乎零开销但依赖 VT-d，SR-IOV 把数据面下放到硬件；
> **中断**需要虚拟中断控制器，注入要经 VM exit，直通设备的中断重映射依赖 VT-d；
> **时间**必须虚拟化：`TSC` 可直通，但 vCPU 被调度出去的时间在 guest 内不可见，
> 定时器与真实时间会偏离，这是"虚拟机里时间不准"的根因；
> **带宽/IOPS** 的多租户争抢表现为邻居噪声（noisy neighbor），靠 cgroup 配额约束，见第 10 章 10.4 节。
## 本章小结
| 关键结论 | 一句话表述 | 常见错误 |
|---|---|---|
| 三个目标无法同时最优；抢占的判据只有一条 | 最优依赖未来行为而未来不可知，每个算法都有对抗负载；抢占看的是运行中的任务能否被外力夺走 CPU | 答"用更好的算法就能兼顾"；把"优先级调度"等同于"抢占式调度" |
| `vruntime` 是加权虚拟时间 | `vruntime += 实际时间 × 1024/weight`，公平的对象是虚拟时间 | 说 CFS 给高优先级进程固定更长的时间片，忽略"每次现算" |
| 红黑树 + `rb_leftmost` | `O(1)` 取下一个，`O(log n)` 插入与删除任意节点 | 答"用堆因为取最小 O(1)"，说不出堆删除任意键的短板 |
| `min_vruntime` 双向保护 | 新唤醒/新建任务的 `vruntime` 被拉到队列最小值附近 | 认为"睡眠久了醒来独占 CPU"是正常现象而非需要修正的问题 |
| 实时进程按语义饿死普通进程 | RT 类队列非空时 CFS 不被查询，带宽由 `sched_rt_runtime_us` 限制 | 把 RT 优先级与 nice 混为一谈，或说 RT 数值越小越优先 |
| 缓存亲和常胜于负载均衡；切换贵在间接开销 | 迁移作废私有 cache；直接开销 1~3 μs，TLB/cache/分支预测器失效才是主要损失 | 认为"均衡越彻底越好"；只答"保存和恢复寄存器" |
| CPU 不是唯一被虚拟化的资源 | 内存靠 EPT、I/O 靠 virtio/直通、时间靠 TSC 与中断注入 | 答"是的，其他资源都是模拟的"，说不出各资源主体与陷阱 |
## 自测题
**Q1**（计算）某单核 CPU 有 4 个可运行任务，nice 分别为 0、0、5、10；`sched_latency = 6 ms`、`min_granularity = 0.75 ms`。求调度周期与各任务时间片，并验证 nice 10 的任务其 `vruntime` 步长是否与其他任务一致。
答案与解析
权重：nice 0 → 1024，nice 5 → 335，nice 10 → 110，`Σ weight = 1024 + 1024 + 335 + 110 = 2493`；周期 `= max(6 ms, 4 × 0.75 ms) = 6 ms`。
```text
nice 0（两个）: 6 × 1024/2493 = 2.464 ms（各一个）
nice 5 : 6 × 335/2493 = 0.806 ms
nice 10 : 6 × 110/2493 = 0.265 ms
校验：2×2.464 + 0.806 + 0.265 ≈ 6.000 ms ✓
vruntime 步长：2.464 ms（nice 0）、3.057 × 0.806 = 2.464 ms（nice 5）、9.309 × 0.265 = 2.467 ms（nice 10）
⟹ 四者步长相同，nice 10 的任务长期获得约 4.4% 的单核时间，而不会被跳过。
```
**错在哪**：把 CFS 当成"给高优先级进程更长固定时间片"，忽略了时间片每次现算、且公平的对象是虚拟时间。
**面试官会怎么追问**：①"把 `min_granularity` 改成 1 ms、任务数变成 100 个会怎样"——周期被撑到 100 ms，最坏情况下一个任务要等 100 ms 才轮到自己，这是就绪队列过长导致响应变慢的直接原因。②"nice 10 改成 19 呢"——权重 15，时间片约 `6 × 15/2398 = 37.5 μs`，已接近一次上下文切换（1~5 μs）的 10 倍以内，切换占比不再可忽略，这正是 `min_granularity` 存在的意义。
答案与解析
前提事实：`vruntime` 只在任务占用 CPU 时增长，睡眠期间冻结，所以队列最小值 `min_vruntime` 单调上升，而长期睡眠任务的 `vruntime` 停在入睡那一刻。
**不修正、新任务 `vruntime` 取极小值（极端为 0）**：新任务是队列最小值，调度器只看最左节点，于是连续选中它直到追平队列——每秒 `fork` 大量短命进程的服务，每个新进程都插到最前面，老任务被无限推后，**新任务饿死老任务**。**不修正、唤醒任务沿用旧 `vruntime`**：交互任务（睡 1 s、跑 1 ms）的 `vruntime` 增长极慢，长期远小于持续运行的任务，醒来后就会"补偿式"独占 CPU，而它永远补不上这 1 s（每轮只该拿 1 ms），于是反复以小 `vruntime` 领先，**睡眠任务反复独占 CPU**。
**面试官会怎么追问**：①"那睡眠任务岂不是白白损失应得 CPU"——是的，CFS 保证长期稳态下的比例份额，**不承诺补发**；交互任务要的是低延迟而非大份额。②"`min_vruntime` 为什么必须单调不减"——回退会让新入队任务又落到过小位置，修正失效，且单调性保证"最左节点前移"不会形成调度回环。③"每秒 fork 的程序为什么更占便宜"——短命进程几乎不消耗 CPU，真正的问题是**创建频率**，解法是线程池/`epoll` 或限制 fork 速率，而不是调调度器。
答案与解析
**方向对，但表述不完整，"快多少"还依赖硬件特性。** 机制上正确的部分：同进程线程共享 `mm_struct`，切换时 `CR3` 不变，不需要换页表；进程切换必须改 `CR3`。不完整之处有三点：**不换页表 ≠ 不失效 TLB**——若切到另一个 CPU 上运行，该 CPU 的 TLB 里没有这个地址空间的条目，仍要重新走页表遍历，只有"同一 CPU、同一地址空间"的切换才真正免掉 TLB 损失；**PCID 削弱了差距**——现代 x86 的 TLB 条目可携带地址空间标签，切换 `CR3` 时不必全局刷新，此时进程切换的额外成本主要变成"新任务工作集不在 cache 里"；**成本大头常不在 TLB 而在 cache 与分支预测器**——即使 TLB 保留，新任务的数据与指令也不在 L1/L2。
**错在哪**：把"快不快"简化成"要不要换 CR3"。**加分答法**：分三种情形——同 CPU 同地址空间（最省）、同 CPU 不同地址空间但有 PCID（次省）、跨 CPU 甚至跨 NUMA（最贵，cache 冷启动主导）。工程上与其纠结线程还是进程，不如先解决跨核迁移。
答案与解析
**判断**：`nvcswch/s`（非自愿）高而 `cswch/s`（自愿）不高，说明线程**不是**在等 I/O 或等锁，而是**想跑却抢不到 CPU**——被抢占。用户态使用率只有 40%，说明 CPU 容量不是被业务逻辑吃掉的，**上下文切换本身就是消耗方**。**按可能性排查**：① 就绪队列过长（`vmstat` 的 `r` 远大于 8）；② 实时任务周期性抢占（`ps -eLo pid,tid,cls,rtprio` 看 `cls` 是否为 `FF`/`RR`）；③ 高频唤醒风暴（忙轮询 + `sched_yield`、每毫秒唤醒几十个线程）；④ 中断集中在一核（若 `in` 也高，查 `/proc/interrupts` 分布与 RSS/RPS）；⑤ 若 `cswch/s` 其实也不低，应怀疑 futex 竞争导致的自愿切换（见第 6 章 6.3 节）而非调度器。定位工具：`pidstat -w -t 1`、`perf sched latency`、`perf record -e sched:sched_switch -a -- sleep 5`。
**压掉开销**：把 runnable 线程数与核数对齐（CPU 密集取 `nproc`，I/O 密集取 `nproc × (1 + 等待/计算)`）；消除忙轮询与过频 `sched_yield`；关键线程绑核并用 `isolcpus` 摘出通用均衡；核查 RT 任务的优先级与 `sched_rt_runtime_us` 带宽；网卡中断按队列分散到多核。**面试官会怎么追问**："`cs` 高但 `us` 不高，怎么排除系统调用引起？"看 `sy` 与 `in`；若 `sy` 也低，说明 CPU 花在调度路径的"轻量但高频"工作上，此时 `perf top` 通常会看到 `schedule`、`finish_task_switch`、`try_to_wake_up` 排在前面。
答案与解析
**(1) 正确。** 这正是虚拟化漏洞的定义：敏感指令中有一部分在 x86 用户态执行时**不触发异常**（如直接读取描述符表寄存器），hypervisor 无从捕获，只能靠**扫描并改写 guest 代码的二进制翻译**（或半虚拟化）绕过，直到 VT-x/AMD-V 提供强制陷入的硬件机制。
**(2) 错误。** KVM 基于硬件虚拟化，**不逐条模拟 guest 指令**。vCPU 是宿主线程，`KVM_RUN` 让物理 CPU 进入非根模式直接执行 guest 代码，绝大多数指令以原生速度运行，只有必须由 hypervisor 介入的事件才 VM exit。所以瓶颈是 **VM exit 的频率与单次成本**，KVM 根本没有翻译环节。"模拟每条指令"描述的是无 KVM 时 QEMU 的 TCG 模式。
**(3) 错误。** VT-d 虚拟化的是 **I/O 侧**：为设备 DMA 提供地址翻译与中断重映射，是**设备直通**的安全前提。没有 VT-d，直通设备的 DMA 用真实物理地址，可绕过 hypervisor 读写任意内存。负责 guest 内存地址翻译的是 **EPT**（Intel）/ **NPT**（AMD），属 CPU 侧扩展。
**错在哪**：三条踩的是同一个坑——把"某类资源"与"某项技术"混为一谈，没区分 CPU 侧（VT-x/EPT）、I/O 侧（VT-d/IOMMU）与软件层（KVM 的调度、QEMU 的设备模型）。**面试官会怎么追问**：①"既然有 EPT，为什么还出现过影子页表"——影子页表是 EPT 之前的软件方案，为每个 guest 维护"guest 虚拟地址 → 宿主物理地址"的合成页表，guest 每次改页表都要同步；EPT 把这一步交给硬件，代价是 TLB miss 时多走一级，所以虚拟化环境里大页收益更明显。②"虚拟机里 `sleep(1)` 真睡满 1 秒吗"——不一定，vCPU 被调度出去的时间在 guest 内不可见，定时器精度取决于虚拟时钟源（如 `kvm-clock`），这也是虚拟机上延迟敏感业务必须做时钟同步的原因。