一种基于EDF的实时任务调度算法浅析

刘伟

摘 要 实时系统的高可靠性、计算准确性及输出结果的实时性使得其在各领域的应用越来越广泛。而实时调度算法是实时系统中的关键技术。本文在EDF算法的基础上提出了一种新的实时调度算法，该算法通过任务的可推迟执行时间逐次逼近，能够快速准确的计算出每个任务的最大可挪用时间。

关键词 实时性；实时调度算法；单调速率优先；最早截止期优先；计算时间

前言

实时系统是指能够及时响应外部发生的随机事件，并在规定时间内完成对事件处理的计算机系统。实时系统具有高可靠性、实时性、少人工干预、专用性等特征，广泛应用于航天控制、工业控制、机器人智能控制、云计算、多处理器下多媒体流调度以及嵌入式智能设备等各个重要领域。实时系统不仅应用广泛，而且要求严格。对实时调度算法的研究，是实时领域的一个重要的研究课题[1]。

1 实时调度算法

实时调度算法可以分为两类：静态调度算法和动态调度算法。RM 和 EDF 调度算法分别是经典的静态和动态实时高度算法，在实时调度领域占有重要地位。EDF调度算法按照实时任务截止期的远近来分配优先级，截止期越近的任务优先级越高，任何时刻总是运行优先级最高的任务，即总是优先运行最紧迫的任务。因为在不同时刻，两个周期任务截止期的远近关系可能会改变，所以EDF调度算法是一种动态优先级调度算法。EDF算法不仅对于硬实时周期任务调度，而且对于硬实时非周期任务的调度来说都是最优的动态优先级调度算法本文在EDF算法的基础上提出了一种新的实时调度算法，该算法通过任务的可推迟执行时间逐次逼近，能够快速准确的计算出每个任务的最大可挪用时间[2]。

2 任务模型

本文使用以下概念来描述实时系统。

定义1（超周期，hyperperiod）：硬实时周期任务集中的所有任务周期的最小公倍数，记为H，H=LCM（T1，T2，…，Tn），其中LCM是最小公倍数函数。

定义2（周期任务的负载）：一个周期任务平均对处理器的占用率，记为u，u=C/T，C为周期任务每次的执行时间，T为周期任务的周期，即每次释放的时间间隔。

定义3（周期任务集的负载）：系统中周期任务集中所有周期任务的负载之和，記为U，U= （n为周期任务集中的周期任务数）[3]。

另外，针对该任务模型本文还作如下假定：

（1）系统中有且只有一个处理器；

（2）系统中任务之间相互独立，即除CPU外，它们没有依赖关系和共享资源；

（3）任务都是可以被剥夺的，任务切换和调度的时间为0或可以忽略；

（4）所有硬实时周期任务的相对截止期都等于它们的周期，即D=T。

3 最早截止期优先调度算法的改进

根据EDF算法调度硬实时周期任务集的可调度性判定条件，当周期任务集的负载U等于1时，EDF算法仍然是可调度的，所以如果单独把第i个周期任务的执行时间增大（1-u）Ti，使得所有周期任务的负载之和刚好等于1，这时所有任务也都可以在截止时刻前完成，显然如果不增加第i个周期任务的执行时间，那么它至少可以在截止时刻前（1-u）Ti时刻完成，即第i个周期任务的最大可挪用时间至少为（1-U）Ti。把所有周期任务按照周期的从小到大排序，使得T1T2……Tn。令⊿P=（1-U）T1，那么所有任务的最小可延迟时间，即所求的最大可挪用时间P⊿P。然后用⊿P去逼近最大可挪用时间P。如图1所示，根据最小周期T，可以把时间划分为等分的[ti，ti+1]时间段，使得ti=iT1：（i=0，1，…）[4]。

算法的具体过程如下：

（1）找出周期任务集中的周期最小的一个，假定为周期任务1。令⊿P=（1-u）T1，P=（T1-C1），m=1；

（2）m=m+1；

（3）对每一个周期任务i，计算它的截止时刻，如果，则根据公式计算该任务的可延迟时间，求出截止时刻在中的所有任务的最小可延迟时间Pm。如果Pm

（4）如果P>m⊿P，转（2）。

（5）完成。P为最大可挪用时间。

因为每一个时间段[tm-1，tm]的长度是最小的周期T1，所以截止期在一个时间段中的任务最多只有n个（n为周期任务数），可得在第（3）步中的最多只需要计算n次可延迟时间。令M表示算法结束时的m，根据算法的结束条件可知：其中（1-U1）T1是P的一个上界。所以算法的时间复杂度是。如果周期任务集的总负载不大于90%，可以保证最多10步就可以算出P[5]。

4 结束语

论文提出了对EDF算法的改进算法。该算法通过任务的可推迟执行时间逐次逼近，能够快速准确的计算出每个任务的最大可挪用时间，并证明了该算法的时间复杂度只和周期任务集的总负载及周期任务数有关。

参考文献

[1] Burns A，Prasad D，Bondavalli A，et al. The meaning and role of value in scheduling flexible real-time systems[J]. Journal of Systems Architecture，2000，46（4）：305-325.

[2] Kim Dong-Sung，Choi Dong-Hyuk，Mohapatra Prasant.Real-time scheduling method for networked discrete control systems[J]. Control Engineering Practice，2009，17（5）：564-570.

[3] 乔颖，王宏安，戴国忠. 一种新的实时多处理器系统的动态调度算法[J].软件学报，2002，13（1）：51-58.

[4] 何军，孙玉方.提高软非周期任务相应性能的调度算法[J].软件学报，1998，9（10）：721-727.

[5] 涂刚，阳富明，卢炎生.基于动态优先级策略的最优软非周期任务调度算法[J].计算机研究与发展，2004，41（21）：2026-2034.