1 引言
3 RM与EDF调度算法简介
足任务可调度性的要求[3]。
2 实时调度分类
同调度方式具有各自的优缺点，适用于不同类型的实时系统。
务调度理论、实时操作系统、实时通信等方面取得了大量成果。
浅析RM与EDF实时调度算法
性[1]。在航空航天、电信、制造、国防等领域，对实时系统有着强烈的应用需
实时任务调度理论是实时处理技术的核心和关键[2]。这是因为，实时任务
完成，则称该调度是可行。可调度性判定就是判定给定的n个实时任务在应用
根据任务请求到达的情况不同。分为周期性任务调度和非周期性任务调度。不
判定是在任务运行之前还是运行期间进行的，分为静态调度、动态调度和混合
处理器实时调度又可分为集中式调度和分布式调度；根据调度算法和可调度性
在一个或多个处理器上运行，分为单处理器实时调度和多处理器实时调度，多
时任务，当系统负载过重的时候，允许发生错过截止期限的情况，根据任务是
调度中任务必须在其截止期限内执行完毕，否则将产生严重后果。而对于软实
根据任务实时性要求的重要程度，分为硬实时调度和软实时调度——在硬实时
某种调度算法的前提下能否产生一个可行的调度。调度算法的设计要尽可能满
求。实时处理和实时系统的研究和应用工作已经有了相当长的历史，在实时任
运行于其中的单个任务必须满足其时限要求，以确保整个系统的正确性和安全
与非实时系统相比，嵌入式实时系统因其所控制物理过程的动态性，要求
务的执行都能在其截止期限内完成。如果每个任务的执行都能在其截止期限内
具有时限要求，在一个或多个处理器之间调度实时任务，需要判断是否每个任
调度；根据被调度的任务是否可以互相抢占，分为抢占式调度和非抢占式调度；
由于实时系统的侧重点不同，实时调度亦有多种分类方式。常见的分类有，
1
业时，该作业恢复执行。
4 相关工作
Ti——第i个实时任务；
ei——任务Ti的执行时间；
pi——任务Ti的周期；
换次数增多，系统的调度性能下降。
t——系统运行的时间，t0；
Liu和Layland已经证明，EDF调度算法的可调度利用率等于1，EDF调度最早截止期优先（Earliest Deadline First，简称EDF）调度算法是一种动态
n——任务集合中任务的数量；
的调度算法以及实时任务在这些下的可调度性判定研究的文献。
它根据任务的周期来分配优先级，周期越小，任务的优先级越高。Liu和
Layland在文献[4]中证明了RM算法是最优的，即对于在任何其他静态优先级
并对其可调度性判定问题进行了研究。RM算法是一种静态分配优先级算法，
需要对这些假设进行修正[5]，目前已有大量关于RM算法及其各种扩展情况下
算法下可调度的任务集合，在RM算法下也是可调度的。RM算法基于建立在
绝对截止期越短，其优先级别越高，相反，作业的绝对截止期越长，其优先级
优先级任务调度算法，它按照当前作业的绝对截止期为其分配优先级，作业的
具有最高优先级的作业执行那个，直至就绪队列中没有高于该作业优先级的作
果当前有其他较低优先级作业正在执行，则该较低优先级作业被抢占，让位给
一系列理想假设基础上的理想调度模型，而在应用中，考虑到各种因素的影响，
度的静态优先级调度算法——速率单调（Rate Monotonic，简称RM）调度算法，
别越低。在EDF调度算法中，具有最高优先级别的作业总是最先得到执行。如
的情况下能够实现最优调度，但是，当系统超载时，任务调度成功率降低，切
算法也是一种最优的调度算法。尽管EDF调度算法在处理器利用率小于等于1
首先对于一些符号、概念、术语进行如下定义：
1973年，Liu和Layland提出了一种适用于可抢占的硬实时周期性任务调
2
争；
nri——任务Ti的释放时间；
Di——任务Ti的绝对时间限。
间限是指绝对时间限减去释放时间。
i1先级最大的任务，并且任务的优先级固定。
开始执行的时间。任务的绝对时间限是指任务必须完成的时间。任务的相对时
的周期小，则Ti比Tj的优先级高。处理器总是优先执行当前处于就绪状态的优
着它们的绝对时间限的接近程度而变化。
(6) 任务的相对时间限等于它的周期。RM、EDF调度算法基于如下假设条件：(5) 任务集合中的所有任务都是周期性的；
5 RM、EDF及混合调度算法分析
di——任务Ti的相对时间限（相对于释放时间）；
(1) 高优先级的任务可以抢占低优先级的任务；
(4) 所有任务都是无关的，不存在先后次序的约束；
(2) 没有任务有非抢先的部分，并且抢先的成本可以忽略；
统项目中会考虑各种因素的影响。本文提到的混合算法也是基于以上假设。
RM调度算法对于给定周期性任务集可调度性的充分条件是：
ein(21/n1) pi先执行当前处于就绪状态的绝对时间限最早的任务，任务优先级并不固定，随
任务的释放时间是指所有用来开始执行任务的资源都可用的时间，即任务
在RM调度算法中，任务的优先级与它的周期反向相关，如果Ti任务Tj比
在EDF调度算法中，任务的优先级与它的绝对时间限相关，处理器总是优
这些假设是RM和EDF算法的基础，是对理想情况的研究，在实际实时系
(3) 只有处理器资源是竞争的，内存、I/O和其他资源是足够的，即无需竞
3
(1)
ni1ni1度算法的可预测性差并且运行开销较大。
ei1 pi不同的调度算法，并没有很好的将RM与EDF调度算法相结合。
EDF算法可以承受较高的工作负载，但是一旦过载，其性能急剧下降。
EDF调度算法对于给定周期性任务集可调度性的充分必要条件是：
5 RM和EDF算法的理论发展与实际应用
分析或者只是少数几种算法之间的简单比较，这不利于实时系统的开发[5]。
法能承受的工作负载要低。RM算法虽然承受的工作负载要低，但性能稳定。
另外，RM属于静态调度算法，适合于问题要求比较明确的系统，额外开
用固定分配优先级的RM算法调度执行，而余下的任务k1,k2,,m则采用
单调递减，所以当n1时，n(21/n1)1。这说明RM调度算法比EDF调度算
类应用的性能有很大的负面影响。目前所建立的理想化调度理论基本上都忽略
(2)
行期间就无法再进行更改，因此，它的灵活性不如动态调度算法，不适合不可销小，可预测性好。但是，由于静态调度算法一旦做出调度决定后，在整个运预测环境的调度。EDF是一种动态调度算法，需要在变化的环境中做出反应，
式(1)和(2)中ei/pi是指任务集的工作负载。由于n(21/n1)随着值的增加这类算法应用 比较灵活，适合于任务不断生成的动态实时系统中。但是动态调
关于混合调度算法的研究，Liu和Layland在文献[4]中提出了一种方案。对
试、分析和比较。但迄今为止，对这些算法的性能分析都是基于理论上的定性
算法，找更优化的确切和构造性算法。另一方面也要对这些算法的性能进行测
对RM及其扩展可调度性的研究，一方面要从理论上研究更好的最小上界
EDF调度算法执行。这种调度算法只是简单的将任务分为两组，每组分别采用
此外，由于RM算法作为代表固定优先级调度的经典实时调度算法，可被
应用于实时操作系统(RTOS)的嵌入式实时系统，而任务的上下文切换开销对此
于一个任务集而言，其中任务1,2,,k，这k个任务是具有最短周期的任务，采
4
[7]
[6]
[1]
Deadline
2004,32(1) ．2008,29(2) ．
2009,35(18) ．
支持内核级的EDF调度算法。
每个时钟单位选择要执行的任务不同[6]。
environment. Journal of ACM [J].1973,20(1):174-1.
参考文献
[2] 王济勇，赵海，林涛等．计算机学报[J],2005,28(2)．
[5] 邢建生，刘军祥，王永吉．计算机研究与发展[J],2005,42(11) ．
在特定硬件平台上操作系统内核中的实现存在着很大的差距。
罗玎玎，赵海，孙佩刚等．RM的运行时开销研究与算法改进
Jeffay等人在1991年提出了非抢占式EDF调度算法(Non-Preemptive
EDF调度算法是一种抢占式调度算法，为了适应不可抢占任务的需要，
现端到端时延保证的研究，主要集中在实时通信领域[7]。虽然在现有的大多数
实时性。现有对端到端实时任务调度模型的研究成果集中在固定优先级的周期
了在非理想资源上调度一个任务集所产生的实现开销，因此实时调度理论与其
在国防、金融、电信、航空等重要应用领域中，往往要求分布式系统具有
价过高。但最新研究表明，如果在操作系统内核为作业提供绝对截止期表示机
性端到端实时任务调度。而将动态优先级算法（主要是EDF调度策略）用于实
制，在内核中实现的EDF调度器的复杂度与固定优先级调度器相当，而由于抢
实时操作系统中，内核仅支持固定优先级调度，在此基础上实现EDF调度的代
以支持动态优先级调度机制提供了可能性。可以预计将有更多的实时操作系统
度器相当或更佳的性能。目前正在兴起的开放源码实时操作系统也为修改核心
占引起的作业切换次数要小得多，在作业延迟抖动等方面具有与固定优先级调
序只是在一个任务执行完成后才决定下一个要执行的任务，这与抢占式方案在
[3] 王永吉，陈秋萍．单调速率及其扩展算法的可调度性判定[J] ．软件学报,2004,15(6)．
[4] Liu CL , Layland JW . Scheduling algorithms for multiprogramming in a hard-real-time
萧伟，冯怡宝，应启．改进型EDF调度算法的研究与实现
First，NPEDF)。NPEDF中一个任务一旦执行就要执行完成。调度程
王济勇，林涛，王金东．EDF调度算法抢占行为的研究及改进．电子学报[J],
5
[J] [J]
．通信学报,
．计算机工程,
Earliest
