实时系统调度算法：RM与EDF原理与应用对比
1. 实时系统调度概述
实时系统调度是确保系统在严格时间约束下正确运行的核心技术。在嵌入式系统领域，调度算法的选择直接影响着系统的响应性、可靠性和资源利用率。实时调度主要分为两大类：固定优先级调度和动态优先级调度。
固定优先级调度（如RM调度）在系统设计阶段就为每个任务分配固定的优先级，运行时保持不变。这种调度方式实现简单，开销小，但处理器利用率较低。动态优先级调度（如EDF调度）则根据任务的实时状态动态调整优先级，能够实现更高的处理器利用率，但实现复杂度较高。
2. 固定优先级调度：RM算法详解
2.1 RM调度基本原理
速率单调调度(Rate-Monotonic, RM)是一种经典的固定优先级调度算法，由Liu和Layland于1973年提出。其核心原则是：任务的优先级与其周期成反比，周期越短的任务优先级越高。
考虑两个周期性任务：
- 任务1：周期p1=4，执行时间e1=1
- 任务2：周期p2=6，执行时间e2=？
2.2 RM可调度性分析
对于RM调度，存在一个最大可调度利用率上界。对于n个任务，这个上界是：
U(n) = n(2^(1/n) - 1)
当n→∞时，这个值趋近于ln2≈0.693。这意味着如果任务集的总利用率不超过69.3%，RM调度一定能保证所有任务按时完成。
2.2.1 最大执行时间计算
给定任务1的e1=1，我们需要计算任务2的最大e2使得调度可行。通过时间需求分析(time-demand analysis)可以确定：
- 在时间区间[0,6]内，任务1需要执行⌈6/4⌉=2次
- 任务2需要执行1次
- 总需求时间为2*e1 + e2 ≤ 6
- 因此e2 ≤ 6 - 2*1 = 4
但是考虑到RM的可调度利用率上界，实际最大e2会更小。通过更精确的计算，可以得到e2的最大值为2。
2.2.2 非RM固定优先级调度
如果采用非RM的固定优先级分配（如任务2优先级高于任务1），可调度性会发生变化。这种情况下，任务2的截止期限必须得到优先保证，因此任务1可能会错过截止期限。通过类似的分析可以确定，此时e2的最大值可能更小。
2.3 处理器利用率比较
处理器利用率U的计算公式为： U = e1/p1 + e2/p2
对于RM调度：
- 当e1=1, e2=2时，U = 1/4 + 2/6 ≈ 0.25 + 0.333 = 0.583
对于非RM固定优先级调度：
- 可达到的利用率通常低于RM调度
- 这表明RM在固定优先级调度中是最优的
2.4 100%利用率情况
在RM调度下，当任务周期成谐波关系（即一个任务的周期是另一个的整数倍）时，有可能实现100%的处理器利用率。例如：
- 任务1：p1=2, e1=1
- 任务2：p2=4, e2=1 此时U = 1/2 + 1/4 = 0.75 < 1
要达到100%利用率，需要更特殊的参数设置，如：
- 任务1：p1=2, e1=2
- 任务2：p1=2, e2=0 这实际上相当于单任务系统。
3. 动态优先级调度：EDF算法详解
3.1 EDF调度基本原理
最早截止期限优先(Earliest Deadline First, EDF)是一种动态优先级调度算法。其核心原则是：总是执行截止期限最近的任务。EDF在单处理器系统下是最优的，只要任务集的总利用率不超过100%，就存在可行的调度方案。
考虑同样的两个任务：
- 任务1：p1=4, e1=1, 相对截止期限d1=4
- 任务2：p2=6, e2=?, 相对截止期限d2=6
3.2 EDF可调度性分析
对于EDF调度，可调度条件是： Σ(ei/pi) ≤ 1
对于我们的例子： 1/4 + e2/6 ≤ 1 ⇒ e2 ≤ 6*(1 - 1/4) = 4.5
因此，e2的最大值为4（假设执行时间为整数）。
3.3 EDF与RM比较
3.3.1 抢占行为
EDF通常比RM产生更少的抢占，因为优先级是动态调整的。在RM中，短周期任务总是会抢占长周期任务，即使后者更紧急。
3.3.2 利用率比较
EDF可以实现更高的处理器利用率（最高100%），而RM的最高利用率约为69.3%。在我们的例子中：
- EDF最大U = 1/4 + 4/6 ≈ 0.916
- RM最大U ≈ 0.583
3.4 EDF调度示例
考虑以下任务集：
- 任务1：p1=2, e1=1
- 任务2：p2=3, e2=1
EDF调度序列： 时间0-1：任务1（截止时间2） 时间1-2：任务2（截止时间3） 时间2-3：任务1（新的实例，截止时间4） 时间3-4：任务2（新的实例，截止时间6） 时间4-5：任务1（新的实例，截止时间6） ...
这种调度实现了U=1/2+1/3≈0.833的利用率。
4. 调度异常与优先级反转
4.1 调度异常现象
在某些情况下，减少任务执行时间或增加处理器数量反而会导致调度性能下降，这种现象称为调度异常。
考虑一个任务前驱图示例：
- 8个任务，执行时间分别为3,2,2,5,5,5,10,5
- 在2个处理器上，makespan（完成所有任务的时间）可能比在3个处理器上更短
4.2 优先级反转问题
当任务共享资源时，可能出现高优先级任务被低优先级任务阻塞的情况，称为优先级反转。解决方法是使用优先级继承协议或优先级天花板协议。
4.2.1 优先级继承协议
当高优先级任务因资源被低优先级任务占用而阻塞时，低优先级任务临时继承高优先级，以避免被中等优先级任务抢占。
4.2.2 代码重排序解决方案
在某些情况下，通过调整任务中锁的获取顺序可以避免死锁。例如，总是按固定顺序获取多个锁。
5. 实际应用建议
5.1 调度算法选择指南
对于简单的周期性任务系统，RM调度是较好的选择：
- 实现简单
- 运行时开销小
- 适合处理器利用率要求不高(<70%)的场景
对于复杂或高利用率要求的系统，考虑EDF调度：
- 能实现更高的处理器利用率
- 适合动态环境
- 但实现复杂度较高
当任务间有资源共享时：
- 必须考虑优先级反转问题
- 实现适当的同步协议
- 可能需要结合两种调度策略的优点
5.2 实现注意事项
上下文切换开销：
- EDF通常导致更多的上下文切换
- 需要评估其对系统性能的影响
截止期限监控：
- EDF需要持续跟踪任务截止期限
- 需要高效的优先级队列实现
可预测性：
- RM调度的行为更易预测
- 适合安全性关键系统
超载处理：
- 明确系统在超载情况下的行为
- 设计适当的降级策略
在实际嵌入式系统开发中，调度算法的选择需要综合考虑任务特性、资源约束和系统要求。通过本文的分析，读者应该能够根据具体应用场景，在RM和EDF等调度策略中做出合理选择。