第10章：CPU 调度——谁先上 CPU
元数据卡
| 属性 | 值 |
|---|---|
| 叙事密度 | 12% |
| 主语言 | C（模拟描述） |
| 配角语言 | Java (Thread scheduler) |
| 前置 | 第9章（线程与同步） |
| 难度 |
核心问题：地心调度台上有 10 个任务同时请求执行，你的引擎只有 4 个汽缸（核）。操作系统如何决定："你先上，你等着"？
你在哪
"现在轮到你来决定谁先上 CPU了。多个进程/线程在等待队列里排队，调度器需要选择下一个。这里没有完美的策略——只有针对不同场景的权衡。"
上一章你学会了怎么创建线程、用锁保护共享数据。但有个问题没问：当同时有 100 个线程就绪时，到底哪个先跑上 CPU？
这不只是操作系统内核才能碰到的问题。写多线程应用时，你也会面临同样的决定：工作线程的优先级怎么设？后台任务要不要降低频率？
这一章讲调度——不是具体的调度器怎么实现，而是调度的策略与权衡。
你的任务
本章分层
- 必读：调度三大指标的权衡；FCFS / SJF / RR 三种经典算法
- 选读：优先级调度与优先级反转；多级反馈队列（MLFQ）如何自动分类进程
- 深水区：Linux CFS 的 vruntime 与红黑树实现；nice 值与 root 权限的关系 本章不会要求你掌握
- CFS 源码中的红黑树操作细节
- CPU 亲和性（CPU Affinity）的配置
- 组调度（Group Scheduling）的实现
你的程序需要同时处理三种任务：
- 交互式任务：用户按键盘后 10ms 内必须有响应，否则用户觉得"卡"
- 批处理任务：视频转码，可以慢但希望尽快完成
- 后台任务：定期同步文件，不紧急但最好别完全饿死
如果你来设计调度器，你会怎么做？
遭遇战：谁先执行？
假设三个进程同时到达：
| 进程 | 需要运行时间 | 类型 |
|---|---|---|
| A | 10s | 批处理 |
| B | 1s | 交互式（紧急） |
| C | 2s | 后台同步 |
不同的调度策略→截然不同的结果。
获得技能：调度的三个指标
调度策略的优劣，核心看三个指标。每个指标对应一类用户感受。
1⃣ 周转时间（Turnaround Time）
$$T_{turnaround} = T_{completion} - T_{arrival}$$
从进程到达直到结束的总时间。用户送了一个大文件去压缩，什么时候能拿回结果——这就是周转时间。
批处理场景下最关键。
2⃣ 响应时间（Response Time）
$$T_{response} = T_{first_run} - T_{arrival}$$
从进程到达直到第一次被调度执行的时间。你在编辑器中打字，按下 'A' 键到屏幕上显示 'A' —— 响应时间越短，系统感觉越"流畅"。
交互式场景下最关键。
3⃣ 公平性（Fairness）
每个进程获得的 CPU 时间是否合理。一个进程如果永远得不到 CPU 时间，就会饿死（starvation）。
关键洞察：三个指标不可能同时最优化。追求最小周转时间可能饿死短进程；追求最小响应时间可能频繁切换带来巨大开销；追求绝对公平可能降低吞吐量。调度就是一场永无止境的权衡。
获得技能：先来先服务（FCFS / FIFO）
最简单的策略：谁先来谁先上，非抢占式（non-preemptive），进程主动释放 CPU（比如 I/O 等待）之前不会被打断。
// 模拟 FCFS 调度
// 假设三个进程在 t=0 同时到达
Process p[] = {
{.name="A", .burst=10}, // 批处理大任务
{.name="B", .burst=1}, // 交互式小任务
{.name="C", .burst=2}, // 后台同步
};
// FCFS: A → B → C
// A: 完成时间 10, 周转 10, 响应 0
// B: 完成时间 11, 周转 11, 响应 10
// C: 完成时间 13, 周转 13, 响应 12
// 平均周转: (10+11+13)/3 = 11.3s
// B 的响应时间: 10s → 交互式体验灾难！问题：如果 B 是编辑器按键响应，用户按了键之后要等 10 秒才看到字母？这个调度器会被丢出窗外。
这就是 ** convoy effect（护航效应）**：一个长进程拖慢后面所有短进程。
获得技能：最短作业优先（SJF）
谁最短谁先上。也分抢占式和非抢占式。
非抢占式 SJF：
// SJF (non-preemptive): 谁最短谁先上
// B(1s) → C(2s) → A(10s)
// B: 完成 1, 周转 1, 响应 0
// C: 完成 3, 周转 3, 响应 1
// A: 完成 13, 周转 13, 响应 3
// 平均周转: (1+3+13)/3 = 5.7s ← 比 FCFS 好一倍抢占式 SJF（也叫最短剩余时间优先 SRTF）：
// SRTF: A 执行了 2ms 后，新到达的 B(1ms) → 抢占 A
// A 才跑 2s, 还剩 8s, B 最短 → B 先上
// B 完成后, C(2s) < A 剩余 8s → C 上
// C 完成后 → A 上
// 平均周转更短理论上，SJF 在平均周转时间上是最优的（这叫 SJF Optimality 定理）。
但现实远不完美：
- 不知道执行时间：你怎么知道一个进程需要跑多久？只能靠历史预测（Sheriff-like 算法：$T_{next} = \alpha T_{observed} + (1-\alpha) T_{prev_guess}$）
- 长进程可能饿死：如果一直有比它短的进程加入，长进程永远得不到 CPU
获得技能：时间片轮转（Round Robin, RR）
这是占领交互式场景的杀手锏。每个进程运行一个固定时间片（time quantum / time slice），时间到了就被抢占，轮到下一个就绪进程。
// RR, time quantum = 1s
// A(10s), B(1s), C(2s) 同时到达
//
// t=0: A (还剩9s)
// t=1: B (还剩0s, 完成!)
// t=2: C (还剩1s)
// t=3: A (还剩8s)
// t=4: C (还剩0s, 完成!)
// t=5~13: A 独占直到完成
//
// 响应时间:
// A: 0, B: 1, C: 2 → 平均 1s ← 比 FCFS(平均 7.3s) 和 SJF(平均 1.3s) 都好
// 但周转时间变差了:
// A: 13, B: 1, C: 4 → 平均 6s ← 比 FCFS(11.3) 好，比 SJF(5.7) 差关键洞察：响应时间 vs 周转时间的经典权衡。用更多上下文切换的代价换来了更低的响应时间。
时间片选多大？
这是 RR 中最微妙的问题：
| 时间片 | 响应时间 | 上下文切换开销 | 效果 |
|---|---|---|---|
| 太短（1μs） | 极好 | 极高（90% CPU 花在切换上） | 系统变慢 |
| 适中（10-100ms） | 好 | 可接受（~1%开销） | 主流选择 |
| 太长（1s） | 差 | 低 | 退化到 FCFS |
现代操作系统：Linux 调度的时间片通常在 1ms~20ms 之间。每次上下文切换（从寄存器保存到 TLB 刷新）大约需要 1-10μs。100ms 时间片意味着切换开销约 0.01%，可以忽略。
获得技能：优先级调度
有些任务天生比其他任务重要。操作系统中断处理比用户程序重要，前台应用比后台服务重要。
// 优先级调度示例
Process processes[] = {
{.name="Audio", .burst=5, .priority=1}, // 高优先级，音频处理
{.name="Editor", .burst=8, .priority=3}, // 中优先级，文本编辑器
{.name="Backup", .burst=20, .priority=5}, // 低优先级，定时备份
};
// 按优先级执行：Audio → Editor → Backup致命问题——优先级反转（Priority Inversion）：
高优先级进程 H 需要锁 L
中优先级进程 M 正在运行
低优先级进程 L 持有锁 L
→ H 等 L 释放锁，但 L 被 M 抢占
→ H 被 M 间接阻塞！这不是理论问题。1997 年火星探路者号在火星上频繁系统重启，最后发现就是因为优先级反转导致看门狗超时。修复方式就是优先级继承（priority inheritance）——当 L 持有 H 需要的锁时，L 临时继承 H 的优先级，确保 L 能快速运行并释放锁。
# Python 中设置线程优先级（实际支持有限）
import threading
import os
# 大多数桌面系统：调度策略由内核管理，用户态设置优先级的API效果有限
# 真要做实时调度，需要 Linux 的 SCHED_FIFO / SCHED_RR 策略和 root 权限常见陷阱：多级反馈队列（MLFQ）
前面几种策略各有优缺点。现实中没有一个调度器只用一种算法。MLFQ 就是将多种策略组合起来的实用方案。
核心思想：
- 有 多个队列，每个队列对应不同优先级
- 高优先级队列 RR 时间片短，低优先级队列 RR 时间片长
- 新进程进最高优先级队列
- 进程用完了时间片→降级到下一级队列
- 进程在时间片内主动让出 CPU（如 I/O 等待）→ 保持或提升优先级
// MLFQ 抽象模型（简化版）
#define N_QUEUES 3
#define TIME_SLICES {10ms, 50ms, 200ms}
// Q0: 时间片 10ms → 新进程 / 交互式进程
// Q1: 时间片 50ms → 半交互式
// Q2: 时间片 200ms → CPU 密集型（批处理）这个设计妙在哪里？
- 交互进程：每次只跑一点点 CPU 就做 I/O 了（键盘输入→休眠等用户按下一个键），一直留在 Q0，响应极快
- CPU 密集进程：一直用满时间片，迅速降到 Q2，虽然时间片长但频率低，不影响交互进程
- 无需事先知识：不像 SJF 需要预知运行时间，MLFQ 通过行为观察自动分类
MLFQ 发明者 Corbato 因此获得 1990 年图灵奖。颁奖词说 MLFQ 是"最被广泛使用的调度算法之一"——这种谦虚的说法掩盖了它几乎是所有通用操作系统调度器的基础。
Linux 实验（面向系统编程/运维方向的读者）：CFS 的详细实现是个 12000 行的内核调度器。以下只讲 CFS 的核心思想，不作为通关要求。
获得技能：Linux CFS（完全公平调度）
从 Linux 2.6.23 开始，Linux 默认调度器换成了 CFS（Completely Fair Scheduler），由 Con Kolivas 的首创理念演化而来，Ingo Molnar 实现。
CFS 放弃了传统的"时间片 + 优先级队列"模式。
核心思想：一个 理想的多任务处理器 应该在任意时刻让所有可运行进程以完全相等的速度推进。但现实中只有一个 CPU——所以 CFS 记录每个进程已获得的 虚拟运行时间（vruntime），每次选择 vruntime 最小 的进程运行。
// CFS 伪逻辑
// 每次调度时：
struct task *pick_next_task(struct rq *rq) {
// 红黑树中最左节点 = vruntime 最小的进程
return rb_entry(rb_first_cached(&rq->cfs_tasks),
struct task, run_node);
}
// 运行期间更新 vruntime
void update_curr(struct rq *rq) {
struct task *curr = rq->curr;
u64 delta_exec = now - curr->exec_start;
curr->vruntime += delta_exec; // 等比例积累
}优先级的影响：高优先级进程的 vruntime 增长更慢，所以它被选中的概率更高。CFS 通过 权重（weight） 控制：
$$vruntime_delta = delta_exec \times \frac{NICE_0_LOAD}{weight}$$
NICE_0_LOAD 是普通优先级（nice=0）的权重值。高优先级（nice=-20）的权重更大，所以同样的实际运行时间贡献更少的 vruntime，意味着更频繁地被选中。
数据结构：CFS 将每个可运行进程放在一个**红黑树（Red-Black Tree）**中，key 是 vruntime。选择"下一个谁上 CPU"就是 O(log n) 的树查找——对几千个线程依然很快。
Linux 实验：
nice值调整需要 root 权限才能升高优先级（设置为负值）。以下 Python 示例展示的是 Linux nice 值的用户态接口。
Linux 实验：
nice值调整需要 root 权限才能升高优先级（设置为负值）。以下 Python 示例展示的是 Linux nice 值的用ce(10) # 降低当前进程优先级
CFS 视角: 这个进程的 vruntime 增长更快 → 更少被调度
### CFS vs 传统时间片调度
| 方面 | 传统（RR/MLFQ） | CFS |
|------|----------------|-----|
| 时间片 | 固定或按队列 | 动态，由目标延迟和进程数决定 |
| 数据结构 | 链表/多级队列 | 红黑树 |
| 公平性 | 各队列内部轮转 | 全系统按 vruntime 精确公平 |
| 休眠进程 | 唤醒时可能被惩罚 | 休眠时 vruntime 不变，唤醒时获得"补偿"→ 有好的交互性 |
| 切换频率 | 固定周期 | 自适应 |
---
## 通关挑战
**问题**：实现一个简化版 CFS 调度器模拟（非抢占式模拟），使用最小堆选择下一个进程。
```c
// sched_sim.c - 用最小堆模拟 CFS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char name[16];
int vruntime; // 虚拟运行时间（模拟）
int remaining; // 剩余运行时间
} Process;
// 最小堆
typedef struct {
Process **data;
int size;
int cap;
} MinHeap;
void heap_push(MinHeap *h, Process *p) {
// 在堆中按 vruntime 排序
int i = h->size++;
h->data[i] = p;
while (i > 0 && h->data[i]->vruntime < h->data[(i-1)/2]->vruntime) {
Process *tmp = h->data[i];
h->data[i] = h->data[(i-1)/2];
h->data[(i-1)/2] = tmp;
i = (i-1)/2;
}
}
Process *heap_pop(MinHeap *h) {
// 取出 vruntime 最小的进程
if (h->size == 0) return NULL;
Process *min = h->data[0];
h->data[0] = h->data[--h->size];
// 下沉调整...
return min;
}
// 模拟运行一个时间单位
void run(Process *p) {
printf("Running %s (vruntime=%d, remaining=%d)\n",
p->name, p->vruntime, p->remaining);
p->vruntime += 1; // 实际运行时间等同 vruntime 增长
p->remaining--;
}思考题：如果时间片耗尽前进程调用了 sleep() 或 wait()，CFS 中 vruntime 会如何处理？为什么这样设计有利于交互式进程？
（答案见下方提示）
提示：休眠进程在休眠期间 vruntime 不增长；唤醒后以"较低的 vruntime"回到红黑树 → 立即被选中 → 交互式进程获得低响应时间。这与 MLFQ 中"I/O型进程留高优先级队列"的效果等价，但实现更优雅。
验收标准
通关本章后，你应该能：
- 解释 FCFS 的 convoy effect
- 说出 SJF 为什么只能理论最优
- 计算 RR 在不同时间片下的平均响应/周转时间
- 描述 MLFQ 如何自动分类交互进程和 CPU 密集型进程
- 理解 CFS 的 vruntime 机制和红黑树的作用
- 解释上下文切换的开销来源（寄存器保存、TLB 刷新、缓存污染）
- 复述优先级反转的历史案例（火星探路者号）
常见卡点
| 卡点 | 表现 | 原因 |
|---|---|---|
| 混淆响应时间和周转时间 | 分析 RR 时算错 | 响应 = 第一次上 CPU，周转 = 完全结束 |
| 忘记非抢占式 | 认为 FCFS 可以打断 | 非抢占式=运行到阻塞或主动让出 |
| 过度追求公平 | 切换过于频繁，有效计算很少 | 上下文切换不是免费的 |
| 以为 CFS 是最优的 | 觉得 CFS 解决了一切 | 实时系统用 SCHED_FIFO，CFS 不适合硬实时 |
现在不需要理解
- 完全公平调度器的具体源码—— Linux 内核
kernel/sched/fair.c有 12000 行。你不需要读源码才知道它怎么工作 - CPU 亲和性（CPU Affinity）—— 把某个进程绑定到特定核心上运行。优化缓存性能用的，不是调度器核心逻辑
- 组调度（Group Scheduling）—— CFS 的扩展：对用户组而不是进程做公平分配
- BFS / MuQSS—— Con Kolivas 的桌面优化调度器，为了低延迟交互而放弃 CFS 的全系统公平性。不是主线内核
旅人笔记
调度器是操作系统中最像"政治"的部分：有多个利益方（进程），资源有限（CPU 核心），没有完美方案（每个指标都在 trade-off）。
从 FCFS 到 SJF 再到 RR，每一步都是对新场景的回应。MLFQ 是工程上的集大成者——不需要预知就能自适应。而 CFS 从另一个角度（虚拟时间公平）解决了同样的问题，用红黑树这个数据结构的优雅让实现变得简洁。
但调度器的故事还没结束。当 CPU 频率不再大幅增长、多核成为常态，调度算法的重点开始从"谁用 CPU"转向"数据离 CPU 有多远"——NUMA（非一致性内存访问）让这个问题变得复杂。但那已经是另一章的课题了。
回到现实：写你那百万并发 Web 服务器时，留意线程优先级、注意不要忘记 yield()、记得调 nice——但是真正决定谁先上 CPU 的，依然是你操作系统内核里那个名叫 schedule() 的函数。
🚪 下一站预告
第11章：锁实现与动态存储——锁是怎么工作的？malloc 背后发生了什么？
调度器选好了下一个线程，但多线程之间需要互斥。锁在硬件层面怎么实现？spinlock 和 mutex 的底层区别？每个 malloc/free 调用背后，内存分配器在做什么？下一章，从调度走向同步和存储。