4. 调度算法（下）：EDF 原理、LLF 原理与混合调度策略
上一章我们聊了 RM 和 DM 这些固定优先级算法。说实话，它们虽然简单可靠，但有个硬伤——CPU 利用率上不去。我早年做一款工业相机的时候，RM 调度死活只能跑到 78% 的利用率，再高就丢帧。后来换成 EDF，直接干到 92%，还稳稳的。
这一章，我们就来啃两块硬骨头：EDF（最早截止时间优先）和LLF（最小空闲时间优先）。它们都是动态优先级算法，能榨干 CPU 的最后一点性能。但用不好，也会翻车。
4.1 EDF：最早截止时间优先
EDF 的思路很直白：谁的截止时间最近，谁先跑。每次调度时，系统检查所有就绪任务，挑出截止时间最小的那个执行。
你想想看，这就像你手头有多个 deadline 不同的活儿。EDF 就是那个不停提醒你「先做最急的」的监工。
4.1.1 工作原理
每个任务 τ_i 在释放时，系统会计算它的绝对截止时间：
d_i = r_i + D_i其中 r_i 是释放时间，D_i 是相对截止时间。调度器维护一个就绪队列，按 d_i 升序排列。每次调度，取队首任务执行。
我画了一张图，帮你理解 EDF 的调度过程：
4.1.2 可调度性分析
EDF 有一个非常漂亮的理论结论：对于一组周期任务，如果总利用率 U ≤ 1，那么 EDF 一定能调度。注意，这里没有 RM 那个 69.3% 的上限。
EDF 可调度条件：
U = Σ (C_i / T_i) ≤ 1
其中 C_i 是任务 i 的最坏执行时间，T_i 是周期。
我当年第一次看到这个结论时，觉得太完美了。但实际用起来，有两个坑：
- 过载时的多米诺效应：一旦 U > 1，EDF 会瞬间崩溃，大量任务同时错过截止时间。不像 RM，过载时至少高优先级任务还能保住。
- 实现开销：每次调度都要比较截止时间，队列维护比固定优先级复杂。
我曾经踩过的坑：在一个视频处理项目中，我用 EDF 调度三个任务，测试时利用率 95%，跑得稳稳的。结果现场环境温度升高，CPU 降频，一个任务的执行时间从 8ms 涨到 11ms。利用率瞬间变成 105%，整个系统像多米诺骨牌一样，所有任务都错过了截止时间。从那以后，我养成了一个习惯——EDF 系统必须留至少 10% 的余量。
4.1.3 EDF 的变体
实际工程中，纯 EDF 用得不多。更常见的是它的变体：
| 变体名称 | 核心思想 | 适用场景 |
|---|---|---|
| 抢占式 EDF | 新任务释放时，如果它的截止时间更早，立即抢占当前任务 | 硬实时系统，截止时间严格 |
| 非抢占式 EDF | 任务开始执行后不允许被抢占，直到主动挂起 | 临界区保护、不可抢占资源 |
| 服务器 EDF | 将非周期任务封装成「服务器任务」，用 EDF 调度 | 混合任务集（周期+非周期） |
4.2 LLF：最小空闲时间优先
LLF 是另一个动态优先级算法。它的思路是：谁的空闲时间最少，谁先跑。
空闲时间（Laxity）定义为：
L_i = d_i - t - C_rem_i其中 d_i 是绝对截止时间，t 是当前时间，C_rem_i 是剩余执行时间。
说白了，空闲时间就是「在不耽误截止时间的前提下，还能摸鱼多久」。空闲时间越少，说明这个任务越危险，必须优先执行。
4.2.1 LLF 与 EDF 的对比
这两个算法经常被放在一起比较。我整理了一张表：
| 对比维度 | EDF | LLF |
|---|---|---|
| 调度依据 | 截止时间 d_i | 空闲时间 L_i |
| 抢占频率 | 较低（只在任务释放时检查） | 较高（每次时钟中断都可能变化） |
| 实现复杂度 | 中等 | 较高（需要跟踪剩余执行时间） |
| 过载行为 | 多米诺效应 | 更早检测到危险任务 |
| 适用场景 | 周期任务为主 | 执行时间变化大的任务 |
我个人习惯：能用 EDF 就不用 LLF。为什么？LLF 的抢占太频繁了。你想想看，每次时钟滴答，所有就绪任务的空闲时间都在变，调度器得重新算一遍。这本身就会吃掉不少 CPU 时间。
一个小技巧：如果你非要用 LLF，可以设置一个「空闲时间阈值」。只有当任务的 L_i 小于某个值（比如 2ms）时，才触发重新调度。这样可以大幅减少不必要的上下文切换。
4.2.2 LLF 的致命弱点
LLF 有一个著名的毛病——颠簸（Thrashing）。当多个任务的空闲时间接近时，调度器会在它们之间频繁切换，导致大量上下文切换开销。
举个例子：两个任务 A 和 B，空闲时间都是 5ms。LLF 会让 A 跑一会儿，然后发现 B 的空闲时间更小了，切到 B；跑一会儿又发现 A 更小了，再切回来。结果两个任务都没怎么干活，全在切来切去。
我在一个雷达信号处理项目中遇到过这个问题。当时用了 LLF，结果上下文切换开销占了 CPU 的 30%。后来换成 EDF，一切正常。
4.3 混合调度策略
现实世界不是非黑即白的。很多时候，我们需要把多种调度策略揉在一起用。这就是混合调度。
4.3.1 为什么要混合？
单一调度算法总有短板：
- RM/ DM：利用率上不去，但实现简单、行为可预测
- EDF：利用率高，但过载时崩溃
- LLF：能处理执行时间变化，但开销大
混合调度的思路是：取长补短。把任务分成不同的「类」，每类用不同的调度策略。
4.3.2 常见的混合模式
我总结了几种工程上常用的混合模式：
| 模式名称 | 结构 | 典型应用 |
|---|---|---|
| 两层调度 | 上层用 EDF 分配时间片，下层用 RM 执行 | 多媒体系统（视频+音频+控制） |
| 固定+动态 | 关键任务用 RM，非关键任务用 EDF | 汽车电子（安全任务+信息娱乐） |
| 服务器机制 | 用固定优先级调度服务器，服务器内部用 EDF | 航空电子（ARINC 653 分区调度） |
| 优先级继承+EDF | 资源访问用优先级继承，任务调度用 EDF | 机器人操作系统（ROS 2） |
4.3.3 实战案例：一个混合调度器的设计
假设我们要设计一个无人机飞控系统，任务集如下：
- 姿态控制：周期 1ms，执行时间 0.2ms，硬实时
- GPS 定位：周期 10ms，执行时间 1ms，软实时
- 图像处理：周期 33ms，执行时间 5ms，非实时
- 日志记录：非周期，执行时间 0.5ms，尽力而为
我的设计方案是这样的：
// 混合调度器伪代码
void scheduler() {
// 第一层：固定优先级（RM）
// 姿态控制优先级最高
if (attitude_task_ready()) {
execute_attitude();
return;
}
// 第二层：EDF 调度
// GPS 和图像处理按截止时间排序
task_t *next = edf_select(gps_task, image_task);
if (next) {
execute(next);
return;
}
// 第三层：后台执行
// 日志记录等非实时任务
execute_background();
}这个设计的好处是：
- 姿态控制永远不被阻塞，满足硬实时要求
- GPS 和图像处理在剩余时间里按 EDF 调度，利用率高
- 日志记录只在空闲时执行，不影响关键任务
混合调度的核心原则：
1. 关键任务用固定优先级，保证确定性
2. 非关键任务用动态优先级，提高利用率
3. 非实时任务用后台调度，不占用实时带宽
4.3.4 混合调度的调试要点
混合调度调试起来比单一算法麻烦。我分享几个经验：
- 先测边界：分别测试每种调度策略的边界条件，再测混合后的交互
- 加日志点：在每个调度决策点打印「谁调度了谁」，方便事后分析
- 监控切换频率：如果发现不同调度层之间频繁切换，说明设计有问题
- 留余量：混合调度本身有额外开销，建议留 15%-20% 的 CPU 余量
我曾经踩过的坑：在一个混合调度系统中，我把一个软实时任务误标成了硬实时，结果它占用了大量 CPU 时间，导致真正的硬实时任务被饿死。调试了两天才发现是优先级配置错了。所以，一定要在代码里显式标注每个任务的实时等级，并且做代码审查。
4.4 本章小结
这一章我们聊了三个核心内容：
- EDF：利用率高，可调度条件简单（U ≤ 1），但过载时容易崩溃
- LLF：能感知任务紧急程度，但开销大，容易颠簸
- 混合调度：取长补短，关键任务用固定优先级，非关键任务用动态优先级
说实话，没有银弹。每种调度算法都有自己的脾气。我的建议是：先搞清楚你的任务集特点，再选算法。如果任务周期稳定、执行时间可预测，EDF 是首选。如果任务执行时间变化大，考虑 LLF 或混合调度。如果系统安全等级高，老老实实用 RM。