一种实时混合调度算法设计和实现

 

　　实时调度算法是嵌入式实时系统设计和实现的关键问题之一，也是保障实时系统两个必备特性（时限性和可靠性）的重要方法，是实时系统中重要而活跃的研究领域。 在众多的实时调度算法中，速率单调（Rate Monotonic,RM）和早截止期限优先（Eartiest Deadline First,EDF）分别是静态调度和动态调度领域中经典的调度算法。RM算法属于静态调度算法，在系统运行前决定任务的调度，实现简单，在满足前提条件的情况下可以保证实时任务集的成功调度。EDF算法属于动态调度算法，在系统运行时决定任务的调度，CPU利用率可以达到100%（理想情况下）。虽然RM和EDF算法以其各自所具备的优良性能在嵌入式实时系统中得到了广泛应用，但是我们也不能忽视它们本身存在的实时性问题。 虽然一些改进后的算法能支持更复杂的任务集特性，但这些算法都是开环的调度算法。开环就意味着一旦调度器被创建，它们就不能基于持续的反馈进行调整了。尽管开环调度算法在负载建模的静态或动态系统中执行良好，但是该类算法在不可预测的动态系统环境下性能却较差。

　　实时系统（Real-time operating system,RTOS）的正确性不仅依赖系统计算的逻辑结果，还依赖于产生这个结果的时间。实时系统能够在指定或者确定的时间内完成系统功能和外部或内部、同步或异步时间做出响应的系统。因此实时系统应该在事先定义的时间范围内识别和处理离散事件的能力；系统能够处理和储存控制系统所需要的大量数据。

　　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 混合调度算法

　　对于一个任务集而言，其中任务1,2,…，k,这k个任务是具有短周期的任务，采用固定分配优先级的RMS调度算法调度执行，而余下的任务k+1,…，m采用EDF调度算法调度执行[5].这种调度算法只是简单地将任务分为两组，每组分别采用不同的调度算法，并没有很好地将RM与EDF调度算法结合。因此，本文提出了一种崭新的混合调度算法。

　　3.1 算法描述

　　周期性任务集符合RM、EDF算法假设条件（1）~（5），Ti、Tj为任务集中处于就绪态任务的时间限的两个任务，时间限分别为Di、Dj,且Di≥Dj.调度方法分两种情况：

　　（1）当Di>Dj时，若Di-Dj<δ，则说明任务间的紧迫性高，采用EDF调度方法；若Di-Dj≥δ，则说明任务间的紧迫性低，采用RM调度方法。

　　（2）当Di=Dj时，采用RM调度方法。

　　算法主要流程如图1所示。

 

 

　　图1中δ为阈值，其意义代表任务间的紧迫性，要根据具体实时系统进行确定。当δ足够小，如 δ=0时，混合调度算法就退化为RM调度算法；当δ足够大时，混合调度算法就退化为EDF调度算法。由此可见，混合调度算法是RM与EDF的一个很好的折中。

　　3.2 算法的可调度性分析

　　调度算法调度任务集，调度算法的任务[4]是使各个任务满足各自的时间限，因此，研究调度算法的可调度性与任务的周期、执行时间等属性之间的关系、给出调度算法可调度性的判断依据是必须完成的工作。

　　下面研究混合调度算法可调度性的充分必要条件。先给出一个示例，从这个特殊的示例中，可以得到一般性的结论。

　　有三个周期任务，周期为p1=2,p2=5,p3=10;执行时间是e1=0.5,e2=3.5,e3=0.5;阈值选取为δ=1.5.由于是周期任务，所以任务的时间限Di即为任务各个周期的结束时刻，任务的释放时刻ri为任务各个周期的开始时刻，则任务在混合调度算法下的执行流程如图2所示。

 

 

　　观察上面每一个任务的次迭代。启动任务T1,这是优先级的任务，它不会被系统中的其他任务耽搁。当T1被释放时，处理器会中断正在运行的工作，而去执行T1.因此，为保证T1能够被可行地调度而满足的条件为e1≤p1,这显然是一个必要条件，也是一个充分条件。

　　现在考察T2.如果它的次迭代能在[0,p2]上找到足够的时间，它就可以成功运行。假设T2在t时刻结束，在[0,t]上释放的任务T1的总迭代次数是[t/p1],为了使T2在t时刻结束，在[0,t]释放的任务T1的每迭代都必须被完成，此外还必须有可用的时间e2去执行T2,即必须满足条件：

  

　　其中Wi（t）是被T1,T2,…，Ti所执行的工作总量。因此可调度性的充分必要条件为：给定一个由n个周期性任务构成的集合，任务Ti能够使用混合调度算法切实可行地调度的充分必要条件是存在某个t∈[0,pi],且t为p1,p2,…，或pi的倍数，使得Li（t）≤1.

　　4 实验结果及分析

　　对于实时系统调度算法来说，截止期错失率DMR（Deadlines Missed Rate）是衡量调度算法性能的一个重要指标。所谓的截止期错失率就是指系统中未被调度成功的任务的个数与参与调度的任务个数之比。它与调度成功率成反比，截止期错失率越高，则调度成功率越低。在实验中，比较了RM、EDF和混合调度算法在不同工作负载情况下的截止期错失率。

　　实验的硬件平台是一个基于32位ARM微控制器的嵌入式系统。实时任务集由5个周期性任务组成，这个任务集的属性描述如表1所示。

 

 

　　为了对实时任务进行定期的统计，系统在实时任务建立之前，首先产生内核任务和空闲任务。内核任务具有优先级，每隔一段时间，对各个任务的截止期错失率进行统计；空闲任务具有优先级，当所有任务均处于不可调度状态时，可以运行空闲任务。统计结果如图3所示。

 

 

　　从图3可以看出，在一定的负载范围内，RM算法和EDF算法都能够保证任务的截止期成功率，可以很好地用来调度实时任务。随着负载的增加，RM算法的截止期错失率开始增加，性能开始下降，而EDF仍然具有很好的性能，即EDF算法比RM算法可以承受更多的负载。但是当系统过载时，EDF算法截止期错失率急剧上升，性能下降很快，而RM算法则相对稳定，到一定程度时EDF算法性能低于RM算法性能。混合调度算法性能曲线介于RM算法与EDF算法之间，在一定的负载范围内，同样能够实时调度任务，而且可以承受的负载范围比RM范围大；当负载增加时，这种算法性能比EDF算法性能下降慢，表现出很好的稳定性。

　　本文基于RM与EDF调度算法，提出了一种基于阈值δ的混合调度算法。这种算法可以根据需要调节阈值δ，制定符合需要的算法性能。当δ取较小值时，混合调度算法侧重于RM算法性能；当δ取较大值时，混合调度算法侧重于EDF算法性能。实验表明，在实际应用中，使用混合调度算法比单独使用RM或EDF调度算法具有更好的灵活性，能够根据需要产生理想的调度性能。