浅析RM与EDF实时调度算法 (2).docx

PAGE\*MERGEFORMAT5

浅析RM与EDF实时调度算法

1引言
与非实时系统相比，嵌入式实时系统因其所控制物理过程的动态性，要求运行于其中的单个任务必须满足其时限要求，以确保整个系统的正确性和安全性[1]。在航空航天、电信、制造、国防等领域，对实时系统有着强烈的应用需求。实时处理和实时系统的研究和应用工作已经有了相当长的历史，在实时任务调度理论、实时操作系统、实时通信等方面取得了大量成果。
实时任务调度理论是实时处理技术的核心和关键[2]。这是因为，实时任务具有时限要求，在一个或多个处理器之间调度实时任务，需要判断是否每个任务的执行都能在其截止期限内完成。如果每个任务的执行都能在其截止期限内完成，则称该调度是可行。可调度性判定就是判定给定的个实时任务在应用某种调度算法的前提下能否产生一个可行的调度。调度算法的设计要尽可能满足任务可调度性的要求[3]。

2实时调度分类
由于实时系统的侧重点不同，实时调度亦有多种分类方式。常见的分类有，根据任务实时性要求的重要程度，分为硬实时调度和软实时调度——在硬实时调度中任务必须在其截止期限内执行完毕，否则将产生严重后果。而对于软实时任务，当系统负载过重的时候，允许发生错过截止期限的情况，根据任务是在一个或多个处理器上运行，分为单处理器实时调度和多处理器实时调度，多处理器实时调度又可分为集中式调度和分布式调度；根据调度算法和可调度性判定是在任务运行之前还是运行期间进行的，分为静态调度、动态调度和混合调度；根据被调度的任务是否可以互相抢占，分为抢占式调度和非抢占式调度；根据任务请求到达的情况不同。分为周期性任务调度和非周期性任务调度。不同调度方式具有各自的优缺点，适用于不同类型的实时系统。

3RM与EDF调度算法简介
1973年，Liu和Layland提出了一种适用于可抢占的硬实时周期性任务调度的静态优先级调度算法——速率单调（RateMonotonic，简称RM）调度算法，并对其可调度性判定问题进行了研究。RM算法是一种静态分配优先级算法，它根据任务的周期来分配优先级，周期越小，任务的优先级越高。Liu和Layland在文献[4]中证明了RM算法是最优的，即对于在任何其他静态优先级算法下可调度的任务集合，在RM算法下也是可调度的。RM算法基于建立在一系列理想假设基础上的理想调度模型，而在应用中，考虑到各种因素的影响，需要对这些假设进行修正[5]，目前已有大量关于RM算法及其各种扩展情况下的调度算法以及实时任务在这些下的可调度性判定研究的文献。
最早截止期优先（EarliestDeadlineFirst，简称EDF）调度算法是一种动态优先级任务调度算法，它按照当前作业的绝对截止期为其分配优先级，作业的绝对截止期越短，其优先级别越高，相反，作业的绝对截止期越长，其优先级别越低。在EDF调度算法中，具有最高优先级别的作业总是最先得到执行。如果当前有其他较低优先级作业正在执行，则该较低优先级作业被抢占，让位给具有最高优先级的作业执行那个，直至就绪队列中没有高于该作业优先级的作业时，该作业恢复执行。
Liu和Layland已经证明，EDF调度算法的可调度利用率等于1，EDF调度算法也是一种最优的调度算法。尽管EDF调度算法在处理器利用率小于等于1的情况下能够实现最优调度，但是，当系统超载时，任务调度成功率降低，切换次数增多，系统的调度性能下降。

4相关工作
首先对于一些符号、概念、术语进行如下定义：
——第个实时任务；
——任务集合中任务的数量；
——任务的执行时间；
——任务的周期；
——系统运行的时间，；
——任务的释放时间；
——任务的相对时间限（相对于释放时间）；
——任务的绝对时间限。
任务的释放时间是指所有用来开始执行任务的资源都可用的时间，即任务开始执行的时间。任务的绝对时间限是指任务必须完成的时间。任务的相对时间限是指绝对时间限减去释放时间。
RM、EDF调度算法基于如下假设条件：
(1)高优先级的任务可以抢占低优先级的任务；
(2)没有任务有非抢先的部分，并且抢先的成本可以忽略；
(3)只有处理器资源是竞争的，内存、I/O和其他资源是足够的，即无需竞争；
(4)所有任务都是无关的，不存在先后次序的约束；
(5)任务集合中的所有任务都是周期性的；
(6)任务的相对时间限等于它的周期。
这些假设是RM和EDF算法的基础，是对理想情况的研究，在实际实时系统项目中会考虑各种因素的影响。本文提到的混合算法也是基于以上假设。

5RM、EDF及混合调度算法分析
在RM调度算法中，任务的优先级与它的周期反向相关，如果任务比的周期小，则比的优先级高。处理器总是优先执行当前处于就绪状态的优先级最大的任务，并且任务的优先级固定。
RM调度算法对于给定周期性任务集可调度性的充分条