第五章：CPU 调度

当线程等待网络数据时，它无法利用 CPU 推进；数据到达后，其响应时间又取决于获得 CPU 的延迟。通用系统还需同时满足交互任务的响应性、批处理任务的吞吐、实时任务的截止时间和不同进程间的资源隔离。

调度器在动态变化的可运行线程集合之间分配 CPU 时间。其评价指标包括吞吐、响应时间、公平性、截止时间满足率、缓存局部性与能耗。

xv6 调度器

xv6 为每个 hart 保留一个 scheduler context。scheduler() 在 proc[] 中扫描 RUNNABLE 进程，取得 p->lock，把状态改为 RUNNING，设置当前 cpu->proc，再调用 swtch(&c->context, &p->context)。

进程主动 yield()、因 timer interrupt 被抢占或在 sleep() 中阻塞时，会经 sched() 执行相反的 swtch(&p->context, &c->context)。于是每次进程切换都经过 scheduler：

进程 A 内核栈
  → swtch(A context, CPU scheduler context)
  → scheduler 选择 B
  → swtch(CPU scheduler context, B context)
  → 进程 B 内核栈

调度器本身也是一段需要栈和寄存器现场的执行流，并不是悬浮在所有进程之外的抽象决策器。

线程状态

线程大致在几种状态间转换：

            被抢占 / 时间片到
Running  ───────────────────→ Runnable
   │                              │
   │ 等锁、等数据、等定时器        │ 被调度
   ▼                              │
Sleeping / Blocked ───────────────┘
             事件完成、被唤醒

Running 表示正在某个 CPU 上执行，Runnable 表示有资格执行但在等 CPU，Blocked 表示即使给 CPU 也无法前进。把阻塞线程留在运行队列只会浪费扫描和时间片。

Linux 工具还会显示更细的状态。例如“不可中断睡眠”表示当前内核等待不能被普通信号立即打断，不表示进程永远无法终止。后续分析以状态转移为准，不依赖特定工具中的单字母编码。

xv6 的 proc.state 正好对应这张状态图。RUNNABLE 表示等待 scheduler，RUNNING 表示正由某个 hart 执行，SLEEPING 还同时保存 chan，ZOMBIE 则已停止执行但等待父进程 wait() 回收。

抢占

若线程只能在系统调用或主动 yield 时交出 CPU，恶意死循环可以永久占用核心。周期性时钟、每 CPU 定时器和外部中断让内核重新获得控制权，并判断当前线程是否应被抢占。

在 xv6 中，timer trap 后 usertrap() 或 kerneltrap() 直接调用 yield()。xv6 没有复杂时间片记账：每次 timer tick 都给 scheduler 一次重新选择机会。

Linux 扩展

抢占不是“每次中断必切线程”。中断处理后，调度器比较当前情况：若原线程仍最适合执行，直接返回更便宜；若有更紧急任务或时间份额已用尽，才切换。

现代 tickless 内核在空闲或适合的场景减少固定频率时钟中断，以降低功耗和抖动。调度器仍使用时间基准，但不要求持续产生固定周期中断。

上下文切换

从线程 A 切到 B，内核要保存 A 的执行现场并恢复 B：通用寄存器、栈指针、程序计数器、浮点/向量状态以及调度所需信息。若跨地址空间，还要切换页表上下文；若跨 CPU，缓存和 NUMA 局部性也会改变。

除保存和恢复寄存器的直接成本外，上下文切换还会产生：

• B 的代码和数据把 A 的缓存工作集挤走；
• 分支预测、TLB 和预取状态发生扰动；
• 线程迁移到另一个 NUMA 节点后访问远端内存；
• 频繁唤醒让 CPU 无法进入更深省电状态。

因此，上下文切换成本取决于地址空间、工作集和 CPU 拓扑。评估时应测量目标工作负载的吞吐和尾延迟，而非仅测切换指令路径。

RISC-V xv6 的 swtch.S 只有一组 sd 和 ld：保存 ra/sp/s0-s11 到旧 struct context，从新 context 恢复同一组寄存器，然后 ret。caller-saved registers 已由调用约定负责，用户寄存器则早已保存在 trapframe。区分 context 和 trapframe，才能看清“内核调用链切换”与“用户现场保存”不是同一件事。

Linux 上下文切换

Linux 中，调度决策发生在 __schedule()：它从当前 CPU 的 run queue 选择 next，必要时调用 context_switch() 更换地址空间，最后经体系结构相关的 switch_to() 进入 __switch_to_asm。这段汇编保存 callee-saved registers，把当前 RSP 写进旧任务，再从新任务装入 RSP。因此“切换线程”的最小机械核心就是换内核栈；完整成本还包括前后的调度、地址空间和扩展寄存器处理。

运行队列

xv6 没有单独的 run queue。每个 hart 的 scheduler() 都线性扫描同一个 proc[]，尝试取得进程锁并寻找 RUNNABLE 项。这种实现短而清楚，但进程数量和 CPU 数增大后，重复扫描与锁竞争都会变贵。

Linux 使用 per-CPU run queue，让本地选择便宜，再周期性或在空闲时做负载均衡。

这带来新的权衡：

• 留在原 CPU 有缓存局部性；
• 迁移到空闲 CPU 可以更早运行；
• 唤醒者与被唤醒者放在同一核心，可能减少通信延迟，也可能互相抢占；
• SMT 逻辑核共享部分执行资源，两个 CPU 编号不等于两份完整性能。

CPU affinity 限制线程可运行的核心集合。它可以改善局部性和可预测性，也可能阻止负载均衡。是否绑核应根据迁移、缓存和队列延迟的测量结果决定。

Linux 公平调度

xv6 的扫描器没有 nice、权重或公平性记账；它只是一个足以展示状态转换和 swtch() 的策略。公平调度属于在同一机制接口上增加的策略。

当前 Linux 普通调度类的选择逻辑位于 kernel/sched/fair.c，核心已从早期“选最小 vruntime”的 CFS 叙述发展为 EEVDF。调度实体先根据 virtual runtime 计算 lag；lag 非负表示尚未超用份额，在 eligible 实体中再选择 virtual deadline 最早者。

交互程序除长期 CPU 份额外，还对唤醒延迟敏感；CPU 密集任务主要关心长期吞吐。调度策略需要在响应性、公平性、缓存局部性和切换成本之间折中。

“nice 值更高/更低”只改变竞争时的权重，不代表一条硬截止时间。机器空闲时，低优先级任务仍可使用全部 CPU。

这一区分很重要：EEVDF 中的 virtual deadline 是实现加权公平和延迟请求的内部量，不等于 SCHED_DEADLINE 向用户暴露的实时 deadline。后者有 runtime、deadline、period 和 admission control，代码位于 kernel/sched/deadline.c。

等待队列

worker 对空管道执行阻塞 read() 时，xv6 调用 sleep(chan, lock)：持有 p->lock 后释放条件锁，把 p->chan 设为对象地址、状态设为 SLEEPING，再进入 sched()。生产者写入后调用 wakeup(chan) 扫描 proc[]，把匹配的 sleeper 改为 RUNNABLE。

检查条件与加入等待队列之间存在 lost wakeup 风险：若事件在两步之间发生，唤醒方可能观察不到等待线程，而该线程随后进入睡眠。条件变量和内核 wait queue 必须通过同步协议将条件检查与睡眠关联起来，不能把 sleep() 和 wakeup() 视为相互独立的通知。

唤醒操作只将线程转换为 runnable，不保证立即执行。系统过载时，从事件完成到线程实际获得 CPU 的 run-queue latency 可能成为主要尾延迟来源。

Linux 不会为每次 wakeup 扫描所有任务，而是使用 wait queue 保存等待者，并把唤醒任务入相应 CPU run queue。数据结构不同，但必须原子衔接“检查条件、登记等待、进入睡眠”的要求相同。

优先级反转

设低优先级 L 持有锁，高优先级 H 等这把锁，中优先级 M 不断抢占 L：

L 持锁 ──被 M 抢占──> 无法释放锁
H 等锁 ─────────────> 间接被 M 延迟

结果是最高优先级反而等最低优先级。优先级继承让 L 在持锁期间临时继承 H 的优先级，尽快运行并释放锁。它说明调度器不能只看线程自己的属性，还要理解等待依赖。

多层锁、I/O 与中断会让依赖链更复杂。实时系统尤其需要限制临界区和最坏阻塞时间，而不仅是提高平均性能。

实时调度

实时系统关心的是截止时间：晚到的正确结果可能等同错误。软实时允许偶发错过，硬实时则要求可证明的最坏情况界限。

固定优先级、deadline 调度等策略可以表达实时需求，但调度器不是唯一变量。不可抢占临界区、缺页、内存回收、设备固件、SMI、锁竞争都可能制造长尾。要求实时性意味着沿整条路径消除无界操作，通常还要预分配内存、锁页、隔离 CPU 和控制中断。

实时线程若不受约束地死循环，也能饿死整个系统。因此接口往往需要特权、运行预算或 throttling。可预测性本身也是一种需要治理的资源。

能耗调度

2026 年的调度器还必须理解异构核心、动态频率和能耗。同一任务放在高性能核心可能更快，也可能用更多电；把任务集中到少数核心可以让其他核心深度休眠，却可能造成热点。

现代调度策略还需考虑每瓦性能、温度和空闲状态。吞吐、延迟、能效和温度约束可能相互冲突，调度策略需根据系统目标确定权重。

实验

先在 xv6 中给 scheduler()、sched() 和 swtch() 设置断点。让一个进程主动 sleep()，另一个进程将它 wakeup()；记录 p->state、p->context.sp 和 CPU 的 scheduler context。下面的 Linux 工具用于观察相同问题在多核系统中的表现。

# 观察一段命令的上下文切换与迁移
perf stat -e context-switches,cpu-migrations,task-clock ./worker 2>/dev/null

# 看各线程状态、所在 CPU、优先级
ps -eLo pid,tid,psr,stat,ni,pri,comm | less

# 观察调度事件（需要相应权限）
perf sched record -- sleep 1
perf sched timehist

压力测试时同时看平均延迟和高分位延迟。调度问题常常不影响平均值，却让少数请求等待几十倍时间。

练习

1. xv6 为什么在 scheduler() 和进程内核线程之间切换，而不是直接在两个用户进程之间切换？
2. sched() 调用 swtch() 前必须满足哪些锁和中断条件？
3. timer interrupt、yield()、状态改为 RUNNABLE 和 swtch() 分别承担什么责任？
4. xv6 扫描进程表的策略在进程数增大时有什么问题？Linux per-CPU run queue 如何改变这个代价？
5. 唤醒只把进程变为 runnable，为什么不保证它立刻执行？

上一章：虚拟内存 · 下一章：共享内存并发 →