Appearance
第五章：CPU 调度
调度管理执行流与 CPU 的对应关系。进程持有内存和文件，不代表它此刻占用 CPU。调度系统需要保存暂未执行的现场，维护运行资格，再把选中的现场装回 CPU。
执行流可能正在运行、已就绪但等待 CPU，或因条件不满足而阻塞。事件完成能让阻塞者恢复运行资格；调度器从可运行者中选择下一位；上下文切换保存旧现场并恢复新现场。每个执行流的状态，与每个 CPU 当前正在执行谁，需要保持一致。
这里有三个不同层次：状态机规定谁有资格运行；上下文切换使暂停和恢复成为可能；调度策略决定合格者中先选谁。xv6 用扫描进程表实现可运行集合，Linux 采用更复杂的运行队列，但这三个层次仍可分别分析。
本章还会用等待队列连接设备和同步：唤醒改变运行资格，调度决定实际执行时间。
进程状态与上下文切换
首先回答谁能运行、怎样暂停与恢复。这里的机制不依赖某一种公平性策略。
线程状态
线程大致在几种状态间转换：
text
被抢占 / 时间片到
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 调度器
现在把前面的两个条件合起来：候选进程必须是 RUNNABLE，切换时必须保存旧现场并恢复新现场。xv6 用下面这段循环把它们连接起来。这里的 hart 指 RISC-V 的硬件执行线程。
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：
text
进程 A 内核栈
→ swtch(A context, CPU scheduler context)
→ scheduler 选择 B
→ swtch(CPU scheduler context, B context)
→ 进程 B 内核栈调度器本身也是一段需要栈和寄存器现场的执行流，并不是悬浮在所有进程之外的抽象决策器。
阻塞与唤醒
阻塞条件和 CPU 使用权由不同部分维护，等待协议把两者接起来。
等待队列
设进程 A 正在读取空管道。它不能只把自己标成睡眠，还要让生产者知道“数据到达时该唤醒谁”。更麻烦的是，数据可能恰好在检查之后、睡眠之前到达。等待协议必须覆盖这个缝隙。
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。数据结构不同，但必须原子衔接“检查条件、登记等待、进入睡眠”的要求相同。
管道阻塞示例
设 A 从管道读数据，B 正在做计算。A 发现管道为空，在同步协议保护下登记等待并变为 SLEEPING，保存自己的内核现场后切回调度器。调度器选中 RUNNABLE 的 B，恢复 B 的现场。数据到达时，生产者唤醒 A，使 A 变为 RUNNABLE；直到调度器再次选中 A，它才真正继续执行，并重新检查管道。
这条过程区分了三个容易混淆的时刻：事件完成、具备运行资格、实际得到 CPU。增加优先级主要影响后两者之间的等待，不能凭空让磁盘或网络更快。
检查条件、修改状态和登记等待期间，其他核心可能也在操作这些对象，因此这些状态变化需要由锁和等待协议共同保护。
Linux 调度策略
选择下一个执行流要在公平、响应、截止时间和局部性之间权衡。
运行队列
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。
优先级反转
设低优先级 L 持有锁，高优先级 H 等这把锁，中优先级 M 不断抢占 L：
text
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 工具用于观察相同问题在多核系统中的表现。
bash
# 观察一段命令的上下文切换与迁移
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压力测试时同时看平均延迟和高分位延迟。调度问题常常不影响平均值，却让少数请求等待几十倍时间。
练习
先回答前两题，再用实现细节核对后面的题目。
设备已经完成请求，线程却没有立即继续执行。应检查等待状态、可运行集合还是 CPU 选择策略？怎样区分这些情况？
同一进程的线程切换、跨进程切换和系统调用入口，各需要改变哪些现场与地址环境？
xv6 为什么在
scheduler()和进程内核线程之间切换，而不是直接在两个用户进程之间切换？sched()调用swtch()前必须满足哪些锁和中断条件？timer interrupt、
yield()、状态改为RUNNABLE和swtch()分别承担什么责任？xv6 扫描进程表的策略在进程数增大时有什么问题？Linux per-CPU run queue 如何改变这个代价？
唤醒只把进程变为 runnable，为什么不保证它立刻执行？