第11讲 调度 I：从 CPU 排队到实时约束的调度策略

本文根据《第11讲 调度I.md》的对话转录整理而成，核心目标不是罗列算法名称，而是建立一条主线：调度本质上是在有限 CPU 资源上，对不同任务的时间需求、响应需求、公平需求和截止时间需求进行权衡。

1. 调度的基本问题：谁运行、在哪运行、运行多久

在现代操作系统中，任务数量通常远大于 CPU 核心数量。即使是普通桌面系统，也可能同时存在上百个进程或线程，而真正能在某一时刻运行的任务数量受限于处理器核心数。

因此，调度器至少要回答三个问题：

1. 下一个执行的任务是谁
2. 该任务在哪个 CPU 上执行
3. 该任务执行多长时间

在单核调度中，重点主要是第一个和第三个问题：同一个 CPU 上，多个就绪任务如何排队、如何切换、每个任务运行多久。

  flowchart TD
    A[多个任务进入系统] --> B[就绪队列 Ready Queue]
    B --> C{调度器决策}
    C --> D[选择下一个任务]
    C --> E[决定运行时长]
    D --> F[任务运行 Running]
    F -->|时间片到| B
    F -->|等待 I/O/锁| G[阻塞 Blocked]
    G -->|事件完成| B
  

这张图强调：调度不是孤立算法，而是和进程状态转换、时钟中断、上下文切换共同构成运行机制。

2. 策略与机制：调度算法不是调度的全部

调度中有一个重要区分：策略 Policy 和 机制 Mechanism。

例如，时间片轮转 RR 的策略是“每个任务轮流运行一小段时间”。但这个策略必须依赖机制实现：硬件定时器触发中断，操作系统进入内核态，保存当前任务上下文，再恢复下一个任务上下文。

所以，学习调度时不能只问“算法是什么”，还要问：

• 它依赖什么机制？
• 它优化什么指标？
• 它牺牲什么指标？
• 它适合哪类任务？

3. 调度目标：没有绝对最优，只有场景取舍

调度器并不是简单追求“快”。不同任务对系统有不同要求，因此调度目标天然存在冲突。

这些目标之间经常冲突：

• 为了让短任务更快完成，长任务可能长期等待。
• 为了提高交互响应，可以缩短时间片，但上下文切换开销会上升。
• 为了保证高优先级任务及时执行，低优先级任务可能饥饿。
• 为了保证公平，可能牺牲平均周转时间。

❗ 本节核心结论： 调度不是寻找唯一正确算法，而是在响应时间、周转时间、公平性、实时性和开销之间做权衡。

4. 批处理任务、交互式任务与实时任务

调度策略之所以分类，是因为不同任务对系统有不同要求。这里最容易混淆的是批处理任务、交互式任务和实时任务。

4.1 批处理任务

批处理任务 batch task 指的是：不需要用户实时盯着结果，只希望系统把一批工作尽快处理完的任务。

典型例子包括：

• 编译大型项目
• 批量压缩图片
• 数据库夜间备份
• 批量生成实验数据
• 视频转码
• 机器学习训练

批处理任务更关注吞吐量和周转时间，而不是立刻给用户反馈。

它和 Windows 的 .bat 批处理文件有联系，但不是同一个概念：

.bat 文件可能启动批处理任务，但批处理任务不等于 .bat 文件。

4.2 交互式任务

交互式任务主要指需要快速响应用户操作的任务，典型是人机交互。

例如：

• 键盘输入
• 鼠标移动
• 浏览器点击
• 终端命令输入
• VS Code 编辑代码
• 游戏角色移动
• 音乐播放控制

交互式任务的关键不是计算量大，而是用户希望系统迅速反馈。敲下一个字符后，如果两秒后才显示，系统就会被认为“卡”。

所以交互式任务最关注的是响应时间。

4.3 实时任务

实时任务 real-time task 的“实时”不是“正在运行”的意思，也不是“尽快运行”的意思。

它的专业含义是：任务必须在规定的截止时间 deadline 前完成，否则结果价值下降，甚至造成严重后果。

交互式任务也发生在现实时间中，批处理任务也在真实运行，但它们通常不叫实时任务。实时任务的种差在于：正确性依赖时间约束。

❗ 本节核心结论： 批处理关注吞吐和完成时间，交互式任务关注响应时间，实时任务关注 deadline；它们的区别不在于“是否正在运行”，而在于对时间的要求不同。

5. 经典调度算法：FCFS、SJF、STCF 与 RR

经典调度算法主要解决“任务如何排队”的问题。

5.1 FCFS：先到先得

FCFS，即 First Come First Served，谁先到谁先执行。

它的优点是简单、直观、容易实现。缺点是对短任务和 I/O 密集型任务不友好。

假设有三个任务：

FCFS 的执行顺序是：

1

A -> B -> C

C 只需要 2 个时间单位，却要等 B 的 7 个时间单位执行完。这就是典型的 convoy effect：一个长任务堵住后面一串短任务。

对 I/O 密集型任务也类似。I/O 密集型任务往往只需要一点 CPU 时间来发起 I/O 请求，然后就阻塞等待设备。如果它迟迟拿不到 CPU，它连 I/O 请求都发不出去，磁盘或网络设备也可能闲着。

5.2 SJF：最短任务优先

SJF，即 Shortest Job First，每次选择总执行时间最短的任务。

它可以降低平均周转时间，但有两个问题：

• 需要提前知道任务运行时间，现实中很难准确知道。
• 长任务可能饥饿，因为短任务不断到来时，长任务一直被推迟。

5.3 STCF：最短完成时间优先

STCF，即 Shortest Time-to-Completion First，每次选择剩余执行时间最短的任务。

SJF 和 STCF 的区别是：

STCF 允许“插队”：如果一个长任务正在运行，此时来了一个剩余时间更短的新任务，调度器可以打断长任务，先执行新任务。

5.4 RR：时间片轮转

RR，即 Round Robin，每个任务运行一个时间片，时间片用完后换下一个任务。

RR 的核心优势是公平和响应性，适合交互式系统。但时间片长度非常关键：

时间片过短时，CPU 并不是完全空闲，而是花太多时间在保存和恢复上下文上，真正执行用户任务的有效时间减少。

❗ 本节核心结论： FCFS 简单但容易拖累短任务；SJF/STCF 优化平均周转时间但可能饿死长任务；RR 提升响应性但依赖合适的时间片。

6. 优先级调度：谁更重要，谁先运行

现实中的任务并不完全平等。系统任务、实时任务、交互式任务、后台任务和批处理任务对系统的重要性不同。

优先级调度的基本思想是：优先级高的任务先运行。

典型优先级可以理解为：

不过，优先级调度会带来三个典型问题。

6.1 低资源利用率

低资源利用率不是说 CPU 一定闲着，而是说系统中的多种资源没有被并行利用起来。

假设有两个任务：

• A：CPU 密集型任务，一直需要 CPU 计算。
• B：I/O 密集型任务，只需要 1ms CPU 发起磁盘读请求，然后等待 10ms 磁盘 I/O。

如果调度器一直偏向 A，那么：

1
2
3

0ms ~ 20ms：CPU 执行 A
             磁盘闲着
             B 没机会发起 I/O

这时 CPU 很忙，但磁盘空闲，整体资源利用率不高。

更好的做法是让 B 先运行 1ms：

1
2

0ms ~ 1ms：B 使用 CPU 发起 I/O
1ms ~ 11ms：磁盘处理 B 的 I/O，同时 CPU 执行 A

这样 CPU 和磁盘可以并行工作，系统整体吞吐更高。

因此，I/O 密集型任务通常应当获得较高优先级。因为它们只需要一点 CPU，就能把 I/O 设备也调动起来。

6.2 优先级反转

优先级反转是优先级调度中的经典问题。

设优先级为：

1

A > B > C

过程如下：

1. 低优先级任务 C 持有某个锁。
2. 高优先级任务 A 也需要这个锁，于是 A 阻塞。
3. 中优先级任务 B 不需要这个锁，因此可以运行。
4. B 抢占 C，导致 C 无法继续运行。
5. C 无法释放锁，A 就继续阻塞。

结果是：A 明明优先级最高，却被 B 间接压制。

解决方法是优先级继承：A 暂时把自己的高优先级“借给”C，让 C 先于 B 运行，尽快释放锁。锁释放后，A 解除阻塞，C 恢复原优先级。

6.3 低优先级任务饥饿

如果系统中不断出现高优先级任务，低优先级任务可能长期得不到 CPU。

这就是 starvation，饥饿。

MLFQ 正是为了解决这类问题而出现的一种重要策略。

7. 多级反馈队列 MLFQ：用行为推测任务类型

MLFQ，即 Multi-Level Feedback Queue，多级反馈队列。它的思想是：系统并不知道任务到底是短任务、长任务、交互式任务还是 CPU 密集型任务，因此通过任务运行行为来动态调整优先级。

基本规则可以概括为：

1. 新任务默认进入最高优先级队列。
2. 总是优先运行最高优先级的非空队列。
3. 如果任务用完整个时间片还没结束，说明它可能是长任务，降低优先级。
4. 如果任务很快主动阻塞，例如等待 I/O，说明它可能是交互式任务，保留较高优先级。
5. 低优先级队列通常使用更长时间片，减少切换开销。
6. 定期把所有任务提升到最高优先级，防止饥饿。

可以设定三个队列：

再设定三个任务：

MLFQ 的运行效果大致如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

初始：
Q0: A, B
Q1:
Q2:

A 运行 1 个单位，用完整个时间片，降到 Q1：
Q0: B
Q1: A
Q2:

B 运行 1 个单位后主动等待 I/O，保持较高优先级：
Q0:
Q1: A
Q2:
B: blocked

A 在 Q1 运行 2 个单位，仍未结束，降到 Q2：
Q0:
Q1:
Q2: A

B 的 I/O 完成，C 到达：
Q0: B, C
Q1:
Q2: A

B 再次优先运行，C 也较快完成，A 在低优先级队列继续运行。

MLFQ 的效果是：

• B 这种交互式任务经常很快得到响应。
• C 这种短任务能较快完成。
• A 这种长计算任务会被降级，但仍然能继续运行。
• 定期 priority boost 可以防止 A 永远饥饿。

❗ 本节核心结论： MLFQ 不需要提前知道任务类型，而是根据任务是否用完整个时间片、是否主动阻塞来推测任务类型，并动态调整优先级。

8. 公平共享调度：公平不是每个任务一样多

优先级调度关心“谁先运行”，公平共享调度关心“长期来看每个人分到多少 CPU”。

这在多用户或云计算场景中很重要。假设用户 A 创建 4 个任务，用户 B 创建 1 个任务。如果普通 RR 按任务平均分配，那么 A 可能拿到 80% CPU，B 只能拿到 20%。这对用户 B 不公平。

公平共享调度的核心是：

CPU 应该按用户或任务的权重比例分配，而不是按任务数量机械均分。

例如：

那么 A 应该获得 B 的 2 倍 CPU 时间。这不是不公平，而是按权重定义后的公平。

9. 彩票调度与步幅调度

公平共享调度中，ticket、stride、pass 是三个核心概念。

9.1 ticket：权重

ticket 表示任务权重。ticket 越多，任务应该获得的 CPU 时间比例越大。

公式是：

1

任务占用比例 = 任务 ticket / 总 ticket

例如：

如果 A1 和 A2 都属于用户 A，那么用户 A 总共获得 50%。

9.2 彩票调度

彩票调度 Lottery Scheduling 的规则很简单：

1. 每个任务持有若干 ticket。
2. 每次调度随机抽一张票。
3. 抽中的 ticket 属于哪个任务，就运行哪个任务。

ticket 多的任务被抽中的概率更大。长期来看，任务获得的 CPU 时间比例会接近 ticket 比例。

彩票调度的优点是简单，并且票少的任务仍有机会被抽中，不容易彻底饥饿。缺点是随机性较强，短期结果可能不精确。

9.3 stride：步幅

步幅调度 Stride Scheduling 可以看作彩票调度的确定性版本。

它使用公式：

1

stride = MaxStride / ticket

其中，MaxStride 是一个足够大的整数，常见做法是设成所有 ticket 的最小公倍数，目的是避免小数，方便整数计算。

例如：

这里可以取：

1

MaxStride = 300

所以：

1
2
3

A1.stride = 300 / 30 = 10
A2.stride = 300 / 50 = 6
B1.stride = 300 / 60 = 5

ticket 越大，stride 越小。

9.4 pass：累计虚拟时间

pass 表示任务累计运行的虚拟时间。步幅调度规则是：

1. 每次选择 pass 最小的任务运行。
2. 任务运行一个时间片后，执行：

1

pass = pass + stride

因此：

• ticket 多 → stride 小
• stride 小 → 每次运行后 pass 增长慢
• pass 增长慢 → 更容易再次成为 pass 最小者
• 更容易再次被选中 → 获得更多 CPU 时间

在教学模型中，所有任务的初始 pass 可以设为 0。但真实系统中，新任务加入时通常不会简单设成 0。否则如果系统已经运行很久，老任务 pass 都很大，新任务 pass 为 0，就会不公平地连续被调度。更合理的做法是把新任务 pass 设为当前运行队列的最小 pass 或某个基准虚拟时间。

Linux CFS 中的 vruntime 就可以类比为这里的 pass。

❗ 本节核心结论： ticket 决定长期 CPU 占比，stride 决定每次运行后 pass 增加多少，pass 决定下一次谁更该被调度。

10. 实时调度：重点不是快，而是按时

实时调度的核心不是“尽量快”，而是“必须在 deadline 前完成”。

对于周期任务，常用 CPU 利用率衡量任务总需求：

1

U = 执行时间 / 周期

多个周期任务的总利用率为：

1

U_total = U1 + U2 + ... + Un

如果 U_total > 1，说明任务总 CPU 需求已经超过单核 CPU 能力，一定无法全部按时完成。

但 U_total < 1 只说明从总工作量上看 CPU 理论上够用，不保证某个具体调度策略一定能满足所有 deadline。

10.1 RM：速率单调调度

RM，即 Rate-Monotonic，是静态优先级实时调度。

规则是：

1

周期越短，优先级越高

它的优先级关系在任务参数确定后基本固定。注意，RM 不是提前规划好完整执行序列，而是提前确定任务之间的相对优先级。实际执行序列仍取决于任务到达、释放、阻塞和抢占情况。

RM 的问题是：即使 U_total < 1，也可能错过 deadline。

例如：

总利用率为：

1

U = 5/13 + 3/5 = 64/65 < 1

从总量看，CPU 似乎够用。但 RM 规定周期短者优先，所以 B 优先级高于 A。B 会周期性抢占 A，导致 A 可能在自己的 deadline 前还没完成。

这说明：

总时间够，不代表时间安排一定合适。

10.2 EDF：最早截止时间优先

EDF，即 Earliest Deadline First，是动态优先级实时调度。

规则是：

1

谁的 deadline 最近，谁先运行

EDF 的优先级不是静态固定的，而是随着当前任务集合和各自 deadline 动态变化。

EDF 更直接围绕 deadline 做决策，因此在实时调度中具有重要理论意义。但如果任务集合本身不可调度，例如 U_total > 1，EDF 也无法创造额外 CPU 时间，甚至可能出现多个任务连续错过 deadline 的多米诺效应。

❗ 本节核心结论： RM 靠固定周期规则决定优先级，EDF 根据当前 deadline 动态调整优先级；U < 1 只是总工作量可能可行，不等于任意调度策略都能成功。

11. 易混概念整理

12. 复习清单

学完本讲后，应能回答：

• 调度器主要决定哪三个问题？
• 为什么调度没有唯一正确答案？
• 周转时间和响应时间有什么区别？
• 批处理任务、交互式任务、实时任务分别关注什么？
• FCFS 为什么容易拖累短任务和 I/O 密集型任务？
• SJF 和 STCF 的核心区别是什么？
• RR 的时间片太长和太短分别有什么问题？
• 什么是优先级反转？优先级继承如何解决？
• 为什么 I/O 密集型任务优先级太低会降低资源利用率？
• MLFQ 如何根据任务行为动态调整优先级？
• ticket、stride、pass 分别表示什么？
• 为什么 stride 越小，任务越容易再次被调度？
• RM 为什么在 U < 1 时仍可能失败？
• EDF 为什么叫动态优先级调度？

最终总结

调度 I 的主线可以压缩为一句话：

操作系统调度不是单纯让任务“快点跑”，而是在有限 CPU 上，根据任务的响应需求、完成需求、公平需求和 deadline 约束，决定谁先运行、运行多久、如何避免饥饿和错过时限。

FCFS、SJF、STCF 和 RR 解决的是基本排队问题；优先级调度解决的是“谁更重要”；MLFQ 通过行为反馈动态推测任务类型；公平共享调度解决的是“长期 CPU 时间如何按权重分配”；实时调度则进一步要求任务必须在 deadline 前完成。

真正掌握调度，不是背下算法名，而是能解释每个策略在优化什么、牺牲什么，以及它为什么适合某一类任务。