浅析RM与EDF实时调度算法1 引言与非实时系统相比，嵌入式实时系统因其所控制物理过程的动态性，要求运行于其中的单个任务必须满足其时限要求，以确保整个系统的正确性和安全性[1]。

在航空航天、电信、制造、国防等领域，对实时系统有着强烈的应用需求。

实时处理和实时系统的研究和应用工作已经有了相当长的历史，在实时任务调度理论、实时操作系统、实时通信等方面取得了大量成果。

实时任务调度理论是实时处理技术的核心和关键[2]。

这是因为，实时任务具有时限要求，在一个或多个处理器之间调度实时任务，需要判断是否每个任务的执行都能在其截止期限内完成。

如果每个任务的执行都能在其截止期限内完成，则称该调度是可行。

可调度性判定就是判定给定的n个实时任务在应用某种调度算法的前提下能否产生一个可行的调度。

调度算法的设计要尽可能满足任务可调度性的要求[3]。

2 实时调度分类由于实时系统的侧重点不同，实时调度亦有多种分类方式。

常见的分类有，根据任务实时性要求的重要程度，分为硬实时调度和软实时调度——在硬实时调度中任务必须在其截止期限内执行完毕，否则将产生严重后果。

而对于软实时任务，当系统负载过重的时候，允许发生错过截止期限的情况，根据任务是在一个或多个处理器上运行，分为单处理器实时调度和多处理器实时调度，多处理器实时调度又可分为集中式调度和分布式调度；根据调度算法和可调度性判定是在任务运行之前还是运行期间进行的，分为静态调度、动态调度和混合调度；根据被调度的任务是否可以互相抢占，分为抢占式调度和非抢占式调度；根据任务请求到达的情况不同。

分为周期性任务调度和非周期性任务调度。

不同调度方式具有各自的优缺点，适用于不同类型的实时系统。

3 RM与EDF调度算法简介1973年，Liu 和Layland 提出了一种适用于可抢占的硬实时周期性任务调度的静态优先级调度算法——速率单调（Rate Monotonic ，简称RM ）调度算法，并对其可调度性判定问题进行了研究。

RM 算法是一种静态分配优先级算法，它根据任务的周期来分配优先级，周期越小，任务的优先级越高。

Liu 和Layland 在文献[4]中证明了RM 算法是最优的，即对于在任何其他静态优先级算法下可调度的任务集合，在RM 算法下也是可调度的。

RM 算法基于建立在一系列理想假设基础上的理想调度模型，而在应用中，考虑到各种因素的影响，需要对这些假设进行修正[5]，目前已有大量关于RM 算法及其各种扩展情况下的调度算法以及实时任务在这些下的可调度性判定研究的文献。

最早截止期优先（Earliest Deadline First ，简称EDF ）调度算法是一种动态优先级任务调度算法，它按照当前作业的绝对截止期为其分配优先级，作业的绝对截止期越短，其优先级别越高，相反，作业的绝对截止期越长，其优先级别越低。

在EDF 调度算法中，具有最高优先级别的作业总是最先得到执行。

如果当前有其他较低优先级作业正在执行，则该较低优先级作业被抢占，让位给具有最高优先级的作业执行那个，直至就绪队列中没有高于该作业优先级的作业时，该作业恢复执行。

Liu 和Layland 已经证明，EDF 调度算法的可调度利用率等于1，EDF 调度算法也是一种最优的调度算法。

尽管EDF 调度算法在处理器利用率小于等于1的情况下能够实现最优调度，但是，当系统超载时，任务调度成功率降低，切换次数增多，系统的调度性能下降。

4 相关工作首先对于一些符号、概念、术语进行如下定义：i T ——第i 个实时任务；n ——任务集合中任务的数量；i e ——任务i T 的执行时间；i p ——任务i T 的周期；t ——系统运行的时间，0t ；i r ——任务i T 的释放时间；i d ——任务i T 的相对时间限（相对于释放时间）；i D ——任务i T 的绝对时间限。

任务的释放时间是指所有用来开始执行任务的资源都可用的时间，即任务开始执行的时间。

任务的绝对时间限是指任务必须完成的时间。

任务的相对时间限是指绝对时间限减去释放时间。

RM 、EDF 调度算法基于如下假设条件：(1) 高优先级的任务可以抢占低优先级的任务；(2) 没有任务有非抢先的部分，并且抢先的成本可以忽略；(3) 只有处理器资源是竞争的，内存、I/O 和其他资源是足够的，即无需竞争；(4) 所有任务都是无关的，不存在先后次序的约束；(5) 任务集合中的所有任务都是周期性的；(6) 任务的相对时间限等于它的周期。

这些假设是RM 和EDF 算法的基础，是对理想情况的研究，在实际实时系统项目中会考虑各种因素的影响。

本文提到的混合算法也是基于以上假设。

5 RM 、EDF 及混合调度算法分析在RM 调度算法中，任务的优先级与它的周期反向相关，如果i T 任务j T 比的周期小，则i T 比j T 的优先级高。

处理器总是优先执行当前处于就绪状态的优先级最大的任务，并且任务的优先级固定。

RM 调度算法对于给定周期性任务集可调度性的充分条件是：1/1(21)n n i i ie n p =≤-∑ (1) 在EDF 调度算法中，任务的优先级与它的绝对时间限相关，处理器总是优先执行当前处于就绪状态的绝对时间限最早的任务，任务优先级并不固定，随着它们的绝对时间限的接近程度而变化。

EDF 调度算法对于给定周期性任务集可调度性的充分必要条件是：11n i i ie p =≤∑ (2) 式(1)和(2)中1/n i i i e p =∑是指任务集的工作负载。

由于1/(21)n n -随着值的增加单调递减，所以当1n ≥时，1/(21)1n n -≤。

这说明RM 调度算法比EDF 调度算法能承受的工作负载要低。

RM 算法虽然承受的工作负载要低，但性能稳定。

EDF 算法可以承受较高的工作负载，但是一旦过载，其性能急剧下降。

另外，RM 属于静态调度算法，适合于问题要求比较明确的系统，额外开销小，可预测性好。

但是，由于静态调度算法一旦做出调度决定后，在整个运行期间就无法再进行更改，因此，它的灵活性不如动态调度算法，不适合不可预测环境的调度。

EDF 是一种动态调度算法，需要在变化的环境中做出反应，这类算法应用 比较灵活，适合于任务不断生成的动态实时系统中。

但是动态调度算法的可预测性差并且运行开销较大。

关于混合调度算法的研究，Liu 和Layland 在文献[4]中提出了一种方案。

对于一个任务集而言，其中任务1,2,,k ，这k 个任务是具有最短周期的任务，采用固定分配优先级的RM 算法调度执行，而余下的任务1,2,,k k m ++则采用EDF 调度算法执行。

这种调度算法只是简单的将任务分为两组，每组分别采用不同的调度算法，并没有很好的将RM 与EDF 调度算法相结合。

5 RM 和EDF 算法的理论发展与实际应用对RM 及其扩展可调度性的研究，一方面要从理论上研究更好的最小上界算法，找更优化的确切和构造性算法。

另一方面也要对这些算法的性能进行测试、分析和比较。

但迄今为止，对这些算法的性能分析都是基于理论上的定性分析或者只是少数几种算法之间的简单比较，这不利于实时系统的开发[5]。

此外，由于RM 算法作为代表固定优先级调度的经典实时调度算法，可被应用于实时操作系统(RTOS)的嵌入式实时系统，而任务的上下文切换开销对此类应用的性能有很大的负面影响。

目前所建立的理想化调度理论基本上都忽略了在非理想资源上调度一个任务集所产生的实现开销，因此实时调度理论与其在特定硬件平台上操作系统内核中的实现存在着很大的差距。

EDF调度算法是一种抢占式调度算法，为了适应不可抢占任务的需要，Jeffay 等人在1991年提出了非抢占式EDF调度算法(Non-Preemptive Earliest Deadline First，NPEDF)。

NPEDF中一个任务一旦执行就要执行完成。

调度程序只是在一个任务执行完成后才决定下一个要执行的任务，这与抢占式方案在每个时钟单位选择要执行的任务不同[6]。

在国防、金融、电信、航空等重要应用领域中，往往要求分布式系统具有实时性。

现有对端到端实时任务调度模型的研究成果集中在固定优先级的周期性端到端实时任务调度。

而将动态优先级算法（主要是EDF调度策略）用于实现端到端时延保证的研究，主要集中在实时通信领域[7]。

虽然在现有的大多数实时操作系统中，内核仅支持固定优先级调度，在此基础上实现EDF调度的代价过高。

但最新研究表明，如果在操作系统内核为作业提供绝对截止期表示机制，在内核中实现的EDF调度器的复杂度与固定优先级调度器相当，而由于抢占引起的作业切换次数要小得多，在作业延迟抖动等方面具有与固定优先级调度器相当或更佳的性能。

目前正在兴起的开放源码实时操作系统也为修改核心以支持动态优先级调度机制提供了可能性。

可以预计将有更多的实时操作系统支持内核级的EDF 调度算法。

参考文献[1] 罗玎玎，赵海，孙佩刚等．RM的运行时开销研究与算法改进[J] ．通信学报,2008,29(2) ．[2] 王济勇，赵海，林涛等．计算机学报[J],2005,28(2)．[3] 王永吉，陈秋萍．单调速率及其扩展算法的可调度性判定[J] ．软件学报,2004,15(6)．[4] Liu CL , Layland JW . Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of ACM [J].1973,20(1):174-189.[5] 邢建生，刘军祥，王永吉．计算机研究与发展[J],2005,42(11) ．[6] 王济勇，林涛，王金东．EDF调度算法抢占行为的研究及改进．电子学报[J],2004,32(1) ．[7] 萧伟，冯怡宝，应启．改进型EDF调度算法的研究与实现[J] ．计算机工程,2009,35(18) ．。