基于RM与EDF的实时混合调度算法研究
摘 要：通过对实时系统中静态调度算法RM和动态调度算法EDF的研究与分析，针对两种调度算法在实际应用中的问题，提出了一种基于阈值δ的混合调度算法，将RM与EDF调度算法相结合，并从数学角度描述了混合调度算法的可调度性与实时任务的周期、执行时间等属性之间的关系，给出了混合调度算法可调度性的充分必要条件。最后用实验验证了混合调度算法的有效性。
关键词：实时系统；速率单调调度算法；最早截止期限优先调度算法；可调度性
实时系统是指能够在确定时间内执行计算或者处理事务并且对外部的异步事件做出及时响应的计算机系统[1]。实时系统最大的特点是时间的确定性，即实时性。由于实时调度算法是实时系统的核心算法，是影响实时系统实时性的最大因素，因此，对实时调度算法的研究具有重要的意义。
RM速率单调（Rate Monotonic）算法是一种静态分配优先级的算法，它根据任务的周期来分配优先级，周期越小，任务的优先级越高[5]。而最早截止期限优先EDF(Earliest Deadline First)算法是一种动态分配优先级的算法，它根据任务的紧迫程度来分配优先级[4]。在现有实时系统中，RM算法和EDF算法是使用最多的两种实时调度算法。但是，这两种算法都是在系统中单独使用，适用面较窄，稳定性差。如果将两者结合将是一条有效的解决途径。本文在这方面进行了探索，提出了一种崭新的混合调度算法，并验证了算法的有效性。
1 相关工作
对一些符号、概念、术语进行如下定义：
任务的释放时间是指所有用来开始执行任务的资源都可用的时间，即任务开始执行的时间。任务的绝对时间限是指任务必须完成的时间。任务的相对时间限是指绝对时间限减去释放时间。
RM、EDF调度算法基于如下假设条件[3]：
(1)高优先级的任务可以抢先低优先级的任务。
(2)没有任务有非抢先的部分，并且抢先的成本可以忽略。
(3)只有处理器资源是竞争的，内存、I/O和其他资源是足够的，即无需竞争。
(4)所有的任务都是无关的，不存在先后次序的约束。
(5)任务集合中的所有任务都是周期性的。
(6)任务的相对时间限等于它的周期。
这些假设是RM和EDF算法的基础，是对理想情况的研究，在实际实时系统项目中会考虑各种实际因素的影响。文中提出的混合调度算法也是基于以上假设。
2 RM与EDF调度算法介绍及分析
在RM调度算法中，任务的优先级与它的周期反向相关，如果任务Ti比任务Tj的周期小，则Ti比Tj的优先级高。处理器总是优先执行当前处于就绪状态的周期最小即优先级最大的任务。任务的优先级固定。
RM调度算法对于给定周期性任务集可调度性的充分条件是[2]：
另外，RM属于静态调度算法，适合于问题要求比较明确的系统，额外开销小，可预测性好。但是，由于静态调度算法一旦做出调度决定后，在整个运行期间就无法再进行更改，因此，它的灵活性不如动态调度算法，不适合于不可预测环境下的调度。EDF是一种动态调度算法，需要在变化的环境中做出反应，这类算法应用比较灵活，适合于任务不断生成的动态实时系统中。但是，动态调度算法的可预测性差并且运行开销较大。
3 混合调度算法
关于混合调度算法的研究，参考文献[5]中提出了一种方案。对于一个任务集而言,其中任务1，2，…，k，这k个任务是具有最短周期的任务,采用固定分配优先级的RMS调度算法调度执行,而余下的任务k+1，…，m采用EDF调度算法调度执行[5]。这种调度算法只是简单地将任务分为两组，每组分别采用不同的调度算法，并没有很好地将RM与EDF调度算法结合。因此，本文提出了一种崭新的混合调度算法。
3.1 算法描述
