CPU 调度算法
为什么需要 CPU 调度
在多道程序系统中，多个进程竞争有限的 CPU 资源。CPU 调度器（Scheduler）的任务是决定下一个执行哪个进程，以及执行多长时间。
好的调度算法需要平衡以下目标：
| 指标 | 含义 | 对谁重要 |
|---|---|---|
| CPU 利用率 | CPU 忙碌时间的占比 | 系统管理者 |
| 吞吐量 | 单位时间内完成的进程数 | 系统管理者 |
| 周转时间 | 从提交到完成的总时间 | 批处理用户 |
| 等待时间 | 在就绪队列中等待的总时间 | 所有用户 |
| 响应时间 | 从提交到首次响应的时间 | 交互式用户 |
非抢占式 vs 抢占式
| 类型 | 说明 | 优缺点 |
|---|---|---|
| 非抢占式 | 进程一旦获得 CPU，就一直运行到结束或主动让出 | 简单，但可能饿死其他进程 |
| 抢占式 | 调度器可以在任意时刻中断当前进程，切换到另一个 | 响应性好，但需要处理并发问题 |
现代操作系统几乎都采用抢占式调度。
经典调度算法
1. 先来先服务（FCFS）
最简单的算法：谁先到就绪队列，谁先执行。
到达顺序: P1(24ms) → P2(3ms) → P3(3ms)
执行甘特图:
|---- P1 ----|-- P2 --|-- P3 --|
0 24 27 30
等待时间: P1=0, P2=24, P3=27
平均等待: (0+24+27)/3 = 17ms
缺点：护航效应（Convoy Effect） — 一个长进程排在前面，后面的短进程全都要等很久。如果换一下顺序：
执行顺序: P2(3ms) → P3(3ms) → P1(24ms)
等待时间: P2=0, P3=3, P1=6
平均等待: (0+3+6)/3 = 3ms ← 大幅下降！
2. 短作业优先（SJF）
选择预计执行时间最短的进程优先执行，可以证明这是使平均等待时间最小的算法。
进程: P1(6ms) P2(8ms) P3(7ms) P4(3ms)
SJF: P4(3) → P1(6) → P3(7) → P2(8)
等待: P4=0, P1=3, P3=9, P2=16
平均: (0+3+9+16)/4 = 7ms
缺点：(1) 需要预知执行时间（实际中只能估算）；(2) 饥饿问题 — 长进程可能永远得不到执行。
3. 时间片轮转（Round Robin, RR）
每个进程分配一个时间片（Time Quantum），时间片用完就被抢占，排到队尾。
时间片 = 4ms
进程: P1(24ms) P2(3ms) P3(3ms)
|P1 |P2 |P3 |P1 |P1 |P1 |P1 |P1 |
0 4 7 10 14 18 22 26 30
P2 和 P3 都在 10ms 内完成（不用等 P1 跑完 24ms）
时间片大小的权衡：
- 太大 → 退化成 FCFS，响应慢
- 太小 → 上下文切换频繁，开销大
- 通常设置为 10~100ms
4. 优先级调度
为每个进程分配优先级，优先级高的先执行。
饥饿问题的解决方案：老化（Aging） — 随着等待时间增加，逐步提升进程的优先级。
5. 多级反馈队列（MLFQ）
结合了时间片轮转和优先级调度的优点，是实际操作系统中最常用的算法：
优先级高 ┌────────────────────┐ 时间片 = 8ms
Queue 0 │ P_new ──▶ 执行 │ 新进程先进入最高优先级队列
└────────┬───────────┘
时间片用完│降级
┌────────▼───────────┐ 时间片 = 16ms
Queue 1 │ 执行 │
└────────┬───────────┘
时间片用完│降级
┌────────▼───────────┐ 时间片 = 32ms
Queue 2 │ 执行 (FCFS) │ 最低优先级，FCFS 执行
优先级低 └────────────────────┘
规则：
- 新进程进入最高优先级队列
- 用完时间片没执行完 → 降到下一级队列（CPU 密集型）
- 在时间片内主动让出 CPU（如等待 I/O）→ 留在当前队列（I/O 密集型）
- 定期将所有进程提升到最高优先级（防止饥饿）
6. 完全公平调度（CFS）
CFS（Completely Fair Scheduler）是 Linux 内核当前使用的调度算法（自 2.6.23 起）。
核心思想：不使用固定时间片，而是保证每个进程获得公平的 CPU 时间份额。
红黑树
(按 vruntime 排序)
┌───┐
│ 30│
╱ ╲
┌───┐ ┌───┐
│ 15│ │ 45│
╱ ╱
┌───┐ ┌───┐
│ 10│ │ 35│
↑
vruntime 最小的进程
= 下一个被调度执行的进程
vruntime（虚拟运行时间）：每个进程实际运行时间 × (默认权重 / 进程权重)。vruntime 越小说明该进程获得的 CPU 时间越少，应该优先调度。
| 进程 | nice 值 | 权重 | 实际运行 10ms 后的 vruntime |
|---|---|---|---|
| P1 | 0 (默认) | 1024 | 10ms |
| P2 | -5 (高优先级) | 3121 | 10 × 1024/3121 ≈ 3.3ms |
| P3 | +5 (低优先级) | 335 | 10 × 1024/335 ≈ 30.6ms |
高优先级进程的 vruntime 增长慢 → 更容易排在红黑树左侧 → 更频繁被调度。
生产高频题
常见的进程调度算法有哪些？
FCFS（先来先服务）、SJF（短作业优先）、时间片轮转（RR）、优先级调度、多级反馈队列（MLFQ）。Linux 使用 CFS（完全公平调度器），基于红黑树和虚拟运行时间实现公平调度。
什么是时间片？太大或太小会怎样？
时间片是轮转调度中每个进程一次最多使用 CPU 的时间长度。太大则退化为 FCFS，响应时间差；太小则上下文切换过于频繁，系统开销大。
Linux 的 CFS 调度器的核心思想？
CFS 使用虚拟运行时间（vruntime）来衡量每个进程获得的 CPU 时间是否公平。通过红黑树维护所有可运行进程，每次选择 vruntime 最小的进程运行。高优先级进程的 vruntime 增长更慢，因此会更频繁地被调度。