基于基于RM与与EDF的实时混合调度算法研究的实时混合调度算法研究
通过对实时系统中静态调度算法RM和动态调度算法EDF的研究与分析，针对两种调度算法在实际应用中的问
题，提出了一种基于阈值δ的混合调度算法，将RM与EDF调度算法相结合，并从数学角度描述了混合调度算法
的可调度性与实时任务的周期、执行时间等属性之间的关系，给出了混合调度算法可调度性的充分必要条件。
最后用实验验证了混合调度算法的有效性。
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调度算法对于给定周期性任务集
另外，RM属于静态调度算法，适合于问题要求比较明确的系统，额外开销小，可预测性好。但是，由于静态调度算法一旦
做出调度决定后，在整个运行期间就无法再进行更改，因此，它的灵活性不如动态调度算法，不适合于不可预测环境下的调
度。EDF是一种动态调度算法，需要在变化的环境中做出反应，这类算法应用比较灵活，适合于任务不断生成的动态实时系统
中。但是，动态调度算法的可预测性差并且运行开销较大。
3 混合调度算法混合调度算法
关于混合调度算法的研究，参考文献[5]中提出了一种方案。对于一个任务集而言,其中任务1，2，…，k，这k个任务是具有
最短周期的任务,采用固定分配优先级的RMS调度算法调度执行,而余下的任务k+1，…，m采用EDF调度算法调度执行[5]。这
种调度算法只是简单地将任务分为两组，每组分别采用不同的调度算法，并没有很好地将RM与EDF调度算法结合。因此，本
评论0