第 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 外还有哪些资源必须虚拟化。

前置知识检查

5.1 调度的三个目标与根本矛盾

调度器要在每个可运行实体（runnable entity，Linux 中即 task_struct）之间分配稀缺资源：CPU 时间，而它同时被三个目标拉扯。

三者的矛盾是结构性的：一次上下文切换约 1~5 μs（口径：vmstat 的 cs 与 perf sched 统计，含直接开销），时间片缩到与之同量级，CPU 就有一半时间在保存/恢复现场；把长任务一次跑完吞吐最高，但排在后面的短任务延迟爆炸（FCFS 的护航效应）；严格公平又会让交互任务每次只拿到几毫秒，用户感知仍然抖动。

抢占式（preemptive）vs 非抢占式（non-preemptive）：判据只有一条——运行中的任务能否被外力夺走 CPU。非抢占式下任务自己让出（终止、阻塞、主动 sched_yield），实现简单，但一个死循环任务能锁死整个系统。抢占式下内核在中断返回点检查 TIF_NEED_RESCHED 标志，必要时调用 schedule() 换人；触发源有三类：时钟中断（时间片耗尽）、更高优先级任务唤醒时 try_to_wake_up 中的可抢占判断、用户态信号的投递点。CONFIG_PREEMPT_NONE/VOLUNTARY/PREEMPT/PREEMPT_RT 的差异只在于内核态代码是否也可被抢占；用户态任务在 Linux 上始终可抢占。

5.2 经典调度算法速查：每个算法的致命场景

下面五种算法本科都讲过，本节只保留面试官用来区分"背过"还是"懂"的那一列。

MLFQ 的五条规则（能说出编号与"每条堵的是什么洞”，层次立刻不同）：

1
2
3
4
5
6

规则 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），累计到阈值就降级。

5.3 CFS 完整机制：vruntime 与红黑树

完全公平调度（Completely Fair Scheduler, CFS）是 SCHED_NORMAL 的实现。它的出发点是反问：“如果 CPU 是能被无限细分的资源，公平应该长什么样？” 理想模型是 N 个任务各以 1/N 速度并行推进；单核只能用极小粒度轮流逼近，而这会撞上切换开销。CFS 的解法是不分配时间片，只维护虚拟时间。

5.3.1 vruntime 更新公式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

                    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 不存固定时间片，每次调度时现算：

1
2
3
4
5

调度周期 = 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），代价是任务数极大时周期拉长、延迟变差。

5.3.4 nice → weight 换算表与算例

内核用预计算表 sched_prio_to_weight 把 nice 映射到权重，规则是每级约 1.25 倍，且 nice 0 ⟹ 1024：

由表可直接验证必须记住的三个倍数：

完整算例：某 CPU 上有三个可运行任务 A(nice 0, weight 1024)、B(nice 0, weight 1024)、C(nice 5, weight 335)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Σ 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 步长完全相同。这就是"完全公平"的准确含义：
     公平的对象是虚拟时间，而不是真实时间。

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 的较大者。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

   min_vruntime 的演化与唤醒放置

   vruntime 轴 ──────────────────────────────────────────────▶
                  ▲                       ▲            ▲
             min_vruntime             A(在跑)      B(阻塞中，vruntime 冻结)
                  │
                  │  新任务 C 唤醒：vruntime 被拉到 min_vruntime 附近（略偏右）
                  ▼
        ┌───────────┬───────────┬───────────┐
        │ min_vrt   │     C     │     A     │  C 要等 A 跑完这一轮才轮到
        └───────────┴───────────┴───────────┘

5.5 调度类与优先级：实时进程如何饿死普通进程

Linux 按"调度类（scheduling class）“分层，每层是独立的调度器实现，高层的类只要队列非空，低层就完全没机会。

nice 与实时优先级是两套独立编号：nice 是 −20_{19（越小越优先），实时优先级是 1}99（越大越优先），且任意实时进程都优先于任意 nice 进程。

1
2
3
4
5
6

  内核内部优先级 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 任务为何偶尔卡一下"时该看的第一个旋钮。

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）：均衡只在域内进行，且范围越大触发越稀疏。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

   sched_domain 层次（自底向上，范围越大、均衡越贵、触发越稀疏）

   ┌─────────────────── NUMA node ─────────────────────┐ ← 迁移最贵：跨节点访存约 1.5~2 倍
   │  ┌────────── 物理封装 package ──────────────────┐  │
   │  │  ┌── L2 共享域 ──┐  ┌── L2 共享域 ──┐        │  │
   │  │  │ SMT 同核两线程 │  │ SMT 同核两线程 │  ...   │  │
   │  │  │ CPU0    CPU1  │  │ CPU2    CPU3  │        │  │
   │  │  └───────────────┘  └───────────────┘        │  │
   │  └───────────────────────────────────────────────┘  │
   └─────────────────────────────────────────────────────┘

   均衡顺序：同核兄弟线程间 → 同 package → 同 NUMA 节点 → 跨节点
   越往外层越"不情愿"：迁移破坏 cache 亲和，跨 NUMA 还要多付内存延迟

NUMA 感知调度（NUMA-aware scheduling）：多路机器上每个 NUMA 节点有本地内存，跨节点访存延迟约为本地的 1.5~2 倍。调度器做两件事：NUMA 层均衡设更高门槛，且迁移时同步改掉任务的"首选节点”，否则它在远端跑还要访问本地内存；自动 NUMA balancing（/proc/sys/kernel/numa_balancing）周期性把部分页设为 PROT_NONE，用缺页捕捉任务真正访问哪块内存，再把任务或页迁到同一节点（缺页路径见第 8 章 8.3 节）。

1
2
3
4
5
6
7

# -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)                    # 看本地/远端节点的内存分布

5.7 上下文切换：开销构成与量化

上下文切换（context switch）是"内核保存一个任务的可恢复执行状态，并恢复另一个任务的同类状态"。它贵不在切换这个动作，而在切换导致的环境失效。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

  直接开销：① 保存寄存器现场（通用寄存器、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，取指单元重新填满

自愿切换 vs 非自愿切换，是排查中区分"进程在等"和"进程被抢"的分水岭：

1
2
3
4
5
6
7
8
9

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 上不可能实现，必须靠二进制翻译或半虚拟化绕过。

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 次数与单次处理成本决定。

本章小结

自测题

Q1（计算）某单核 CPU 有 4 个可运行任务，nice 分别为 0、0、5、10；sched_latency = 6 ms、min_granularity = 0.75 ms。求调度周期与各任务时间片，并验证 nice 10 的任务其 vruntime 步长是否与其他任务一致。

1
2
3
4
5
6

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% 的单核时间，而不会被跳过。

Q2（推导）说明为什么把新任务或刚唤醒任务的 vruntime 设为不低于 min_vruntime，既避免饿死老任务又避免睡眠进程醒来独占 CPU；去掉这一修正，两个方向分别发生什么？

Q3（辨析）“线程切换比进程切换快，因为进程切换要换页表、刷新 TLB，线程切换不用。“这句话对吗？

Q4（设计）一个 8 核服务：用户态 CPU 使用率仅约 40%，但 vmstat 的 cs 高达 30 万/秒，pidstat -w 显示各工作线程 nvcswch/s 很高而 cswch/s 不高。给出判断与排查步骤，并说明从哪入手压掉这个开销。

Q5（判断）逐条判断下列说法是否正确并说明理由：(1) x86 上最早无法用陷入-模拟实现全虚拟化，是因为有些敏感指令在用户态执行不会陷入；(2) KVM 会模拟 guest 的每一条指令，所以 guest 性能主要取决于 KVM 的翻译效率；(3) VT-d 是用来加速 guest 内存地址翻译的。

面试高频问题与陷阱

延伸阅读

• Linux 内核源码：kernel/sched/fair.c（update_curr()、place_entity()、sched_slice()、pick_next_task_fair()）、kernel/sched/core.c（__schedule()、try_to_wake_up()）、kernel/sched/rt.c、kernel/sched/deadline.c。
• Linux 内核文档：Documentation/scheduler/sched-design-CFS.rst、sched-deadline.rst、sched-nice-design.rst。
• man 7 sched（各调度策略语义与 sched_setattr）、man 1 taskset、man 8 numactl、man 1 chrt、man 5 proc（/proc/[pid]/sched、/proc/[pid]/status 的 voluntary_ctxt_switches 字段）。
• Intel SDM Volume 3C：VMX（非根操作、VMCS、VM exit 原因）与 EPT 章节；Intel VT-d 规范（DMA 重映射与中断重映射）。
• Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau,《Operating Systems: Three Easy Pieces》第 7~10 章（调度与 MLFQ）、第 23 章（虚拟化：VT-x 与 KVM 的实现讨论）。