第四节：最早截止时间优先（EDF）——动态调度的王者
各位做运动控制的同行，今天我们来聊聊EDF调度。说实话，我刚入行那会儿，对EDF是又爱又怕。爱的是它理论上能把CPU利用率压到100%，怕的是它一旦过载，系统崩溃的方式比RMS惨烈得多。我有个项目就吃过这个亏，后面细说。
一、EDF的核心思想：谁先死，谁先跑
EDF的全称是Earliest Deadline First。翻译成人话就是：哪个任务的截止时间最近，就先执行哪个。
这和RMS完全不同。RMS是静态的，优先级在任务创建时就定死了。EDF是动态的，优先级随着时间变化。你想想看，一个任务的截止时间是10ms，另一个是20ms，那10ms的那个优先级就高。等10ms的任务执行完了，20ms的任务可能变成了新的“最早截止”，优先级就上来了。
我习惯把EDF比作急诊室分诊。RMS像是按挂号顺序看病，EDF是按病情紧急程度。谁快不行了先救谁，很直观对吧？
二、动态优先级：EDF怎么算优先级？
EDF的优先级计算公式其实很简单：
优先级 = 当前时间 - 截止时间注意，这个值是负的。截止时间越近，这个值越小（负得越多），优先级越高。实际实现时，我们通常用截止时间的绝对值来比较。
举个例子：
- 任务A：周期10ms，执行时间3ms，截止时间=当前时间+10ms
- 任务B：周期15ms，执行时间4ms，截止时间=当前时间+15ms
在t=0时刻，A的截止时间是10ms，B是15ms。A先跑。等A跑完3ms，时间到了t=3ms。此时A的下一个周期还没到，B的截止时间还剩12ms。如果此时有新任务C进来，截止时间是8ms，那C就插队到B前面。
嗯，这里要注意：EDF的优先级是实时计算的。每次任务切换时，调度器都要重新算一遍所有就绪任务的截止时间。这比RMS的固定优先级开销大不少。
关键点：EDF的优先级不是任务本身的属性，而是任务实例（Job）的属性。同一个任务的不同周期实例，优先级可能完全不同。
三、可调度性分析：EDF的“体检报告”
EDF的可调度性分析比RMS简单得多。RMS需要算一堆公式，EDF只需要看一个指标：总利用率。
对于n个周期任务，如果满足：
U = Σ(Ci/Ti) ≤ 1那么这些任务就是可调度的。其中Ci是执行时间，Ti是周期。
你没看错，就是≤1。EDF理论上可以把CPU用到100%而不丢deadline。RMS呢？最坏情况下只能用到约69%（ln2 ≈ 0.693）。
我当年第一次看到这个结论时，第一反应是：那还要RMS干嘛？直接全上EDF不就行了？
后来在实际项目中碰了壁，才明白事情没那么简单。
注意：EDF的≤1可调度条件是针对周期任务的。如果任务有释放抖动、非周期任务、或者任务间有依赖关系，这个条件就不够用了。我曾经在一个多轴同步项目中，就因为没考虑任务间的共享资源互斥，导致U=0.85的系统频繁丢deadline。
四、EDF vs RMS：到底选哪个？
这个问题我经常被问到。直接上对比表：
| 对比项 | EDF | RMS |
|---|---|---|
| 优先级分配 | 动态，实时计算 | 静态，固定不变 |
| CPU利用率上限 | 100%（理论） | 约69%（最坏情况） |
| 调度开销 | 较高，每次切换都要算 | 低，直接查表 |
| 过载行为 | 多米诺骨牌式崩溃 | 低优先级任务先丢 |
| 实现复杂度 | 高，需要定时器管理 | 低，简单粗暴 |
| 适用场景 | CPU紧张、任务数多 | 任务少、要求确定性 |
我个人习惯这样选：
- 任务数少于5个，周期固定：用RMS。简单可靠，调试方便。
- 任务数多，CPU利用率高：用EDF。能压榨出更多性能。
- 有非周期任务或突发任务：用EDF的变种，比如EDF with servers。
我曾经在一个6轴机器人控制器项目中，用了RMS死活调不通，CPU利用率卡在65%就上不去了。换成EDF后，利用率干到92%，所有轴都能跑到1ms周期。但代价是调试阶段出了好几次多米诺骨牌崩溃，排查起来比RMS费劲多了。
五、EDF的实战避坑指南
这里分享几个我踩过的坑：
- 过载检测要提前做：EDF一旦过载，所有任务都可能丢deadline。不像RMS，至少高优先级的还能保住。我建议在调度器里加一个利用率监控，超过90%就报警。
- 注意优先级反转：EDF本身不解决优先级反转问题。如果任务间有共享资源，必须配合优先级继承协议或立即继承协议。我有个项目就是忘了这茬，结果一个低优先级的任务拿着锁不放，高优先级的EDF任务全堵死了。
- 定时器精度要够：EDF依赖精确的截止时间比较。如果系统定时器分辨率太低，比如只有1ms，那截止时间差0.5ms的两个任务就分不清谁先谁后了。我建议至少用微秒级的定时器。
- 任务切换次数会暴增：EDF的切换次数通常比RMS多。因为每次有新任务就绪，都可能触发重新调度。如果切换开销太大，反而得不偿失。我一般会限制每秒切换次数上限。
小技巧：在实际工程中，我常用混合方案。比如把关键任务（如急停、安全逻辑）用RMS跑固定高优先级，把非关键任务（如日志、状态上报）用EDF跑。这样既保证了确定性，又提高了利用率。
六、EDF的调度流程图
下面这张图展示了EDF调度器的核心逻辑。我画得比较简洁，但关键步骤都在了：
这张图的核心逻辑其实就三步：算截止时间 → 找最小的 → 决定是否抢占。但实际工程中，第二步和第三步之间还有很多细节，比如怎么处理相同截止时间的任务（我一般按FIFO处理），怎么处理任务执行过程中截止时间更新的情况。
七、写在最后
EDF是个好算法，但用好它需要你对系统有全面的把握。我个人建议，如果你刚开始接触实时调度，先从RMS入手。等把RMS玩透了，再挑战EDF。毕竟，RMS翻车了还能抢救一下，EDF翻车了可能就是全线崩溃。
好了，EDF的内容就聊到这儿。记住一句话：EDF给你100%的利用率，但也要你100%的谨慎。