基于多处理器实时调度策略的研究

摘 要： 多处理器系统中实时调度算法起着重要的作用。在结合了RMS和EDF调度算法的基础上提出了一种含阈值的多处理器实时任务调度策略，使任务能够在阈值范围内在各处理器上进行迁移，避免了部分处理器处于空闲，部分处理器过于繁忙导致任务被挂起的现象，保证了各处理器利用率的相对平衡。

关键词： 多处理器系统； RMS调度算法： EDF调度算法； 实时任务调度模型

中图分类号： TN40?34； TP393 文献标识码： A 文章编号： 1004?373X（2013）21?0124?04

0 引 言

随着计算机技术的不断发展，对多处理器系统的需求不断增加，特别是在航空、导航领域不仅要求系统拥有良好的并行性，还要保证系统的实时性。因此，好的调度策略就显得尤为重要。在这里针对多处理器的结构提出了一种RMS和EDF算法相结合的实时任务调度模型，通过阈值的设定使任务能够在处理器上进行迁移。该调度策略充分利用了RMS和EDF算法的优点，为了充分保证实时性在模型的验证中对EDF算法做了改进，较大程度克服了EDF调度算法引起的多米诺效应，提供了较好的实时调度性能。

1 理论基础

1.1 RMS算法

为解决周期性任务，提出了速率单调调度算法（Rate Monotonic Scheduling，RMS），任务优先级的确定基于任务的周期，优先级最高的任务周期最短。当有多个任务可供执行时，周期最短的任务首先得到服务。RMS算法需要满足以下假设的前提[1]：

①所有任务都是周期性的；

②任务间不需要同步，没有共享资源，任务间的切换时间可忽略不计；

③CPU必须总是执行优先级最高的任务，必须是可被抢占的。

在以上假设的基础上衡量RMS算法有效性需保证不等式（1）成立：

若把任务的优先级描述成关于它们速率的函数，其结果是一个单调递增函数。表1给出了这个上界的一些值。当任务数目增加时，调度上界收敛于ln 2。即在单处理器中它的使用率为69.3%。

RMS算法的优点是开销小，在任务的截止时间等于其周期的条件下，速率单调算法已被证明是静态最优的调度算法。

1.2 EDF算法

截止期最早的任务优先调度算法，该算法规定任务的截止期限越小，优先级越高。EDF（Earliest Deadline First）是一种动态的优先级调度算法，优先级与任务的最后截止期限成反比。理论上每个时刻都要计算处于等待调度状态的任务调度优先级，系统下个时刻调度的任务是不确定的，与系统中其他任务有关系。其调度有效性的验证需满足不等式（2）成立：

EDF的主要优点是：任务的优先级能够根据需要动态改变，使得系统适应性比较好。在软实时消息的调度上要优于静态调度算法。

EDF的缺陷是：如果一个实时任务在其执行时间之前提前完成本周期内的工作，则在这个周期内剩余的空闲时间里其他任务也不能运行，CPU将处于相对空闲状态；如果一个实时任务超出了自己的执行时间，工作没有结束，则将保持当前的优先级继续执行，这样就会顺延本来已经安排的后续任务，形成多米诺效应，造成多个任务超出截止时间。

EDF算法的改进如下：

（1）当一个实时任务在分配的执行时间之前完成本周期的工作，并且此时有多个任务在等待，剩余的时间片应该分配给优先级最高的任务。

（2）当一个实时任务超出了自己的执行时间，工作没有结束，这时采用向下一个周期借入的策略，以当前的优先级运行完成余下工作，保证到来的下一个任务的有效执行，解除了连续多个任务超出截止时间的多米诺效应。

2 多处理器系统的实时任务调度策略

多处理器调度就是将[n]个任务分配到[m]个处理器上（需要满足前后约束关系），确保每个任务能准确迅速地完成。任务调度概念图如图1所示。

因此，在多处理器任务实时调度中涉及以下2个相关的问题：

（1）如何把任务分配到各处理器。在这里使用全局调度策略，任务到来时首先将任务放入公共就绪队列中，使用RMS算法确定任务的优先级，完成任务到处理器的分派，周期越短优先级越高越优先被分配。接下来的工作就可被看做是单处理器上任务的调度。

（2）在单个处理器中如何调度就绪任务。当就绪任务被放入到各处理器就绪队列时，我们使用改进后的EDF算法进行调度，保证任务的执行。

2.1 调度算法相关参数

任务集定义为[T={t1，t2，t3，…，tn}。]

任务使用4元祖定义[ti（Ai，Ci，Ti，Di）。]

其中，[Ai]：任务[i]的到达时间；[Ci]：任务[i]的执行时间；其中，[Ti]为任务[i]的周期；[Di]为任务[i]的最后截止期限。

定义：每一个处理器的利用率为总任务在特定的处理器上执行利用率之和，即：

2.2 算法思想

在这里使用全局调度机制来维护一个全局调度队列，即公共就绪队列将到来的等待被分配的任务分配到独立的不同处理器上。在全局调度队列中使用RMS算法将任务分配给各处理器，拥有最高优先级的任务被分配到第一个处理器所对应的就绪队列中，依次分配；如图2所示，当任务依次顺序放入QUEUE（0…[n]）队列后，等待各个处理器的调度（在初次任务分配时假设QUEUE（0…[n]）队列均为空），在此处QUEUE（0…[n]）队列要求与处理器一一对应。在各独立的处理器中使用改进的EDF算法进一步执行任务调度。

对于单处理器而言，改进后的EDF算法能够很好地完成调度工作，但是对于超负载的问题出现时改进后的EDF算法也不再有效。因此，在多处理器系统中，当系统超过它的利用率限制（即阈值）时需要进行任务的迁移。在任务迁移前先要对阈值做如下的计算：

（1）阈值计算：[f=U1+U2+…+Unn。]

（2）超负载处理器：该处理器的利用率[Ui]>1或者[Ui>f。]

（3）轻负载处理器：该处理器的利用率[Ui]

（4）迁移任务的选择：在此调度模型中，改进后的EDF算法根据截止期限的长短确定任务的优先调度顺序。因此，处于最低优先级的任务就成为被迁移的对象。

此时，EDF算法的改进以及任务的迁移都有助于解决多米诺效应，并保证各独立处理器利用率的平衡。

2.3 实时任务调度过程

实时任务调度流程图如图3所示。

具体过程如下：

（1）开始；

（2）周期任务集到达；

（3）根据RMS算法确定任务的周期指定任务的优先级；

（4）在任务优先级确定的基础上将任务分派到各处理器上；

（5）在各处理器上使用改进后的EDF算法进行任务的调度，在此处被调度任务的优先级与任务的截止期限成反比，即截止期限越短优先级越高，越优先被调度；

（6）各处理器上利用率与计算的阈值做比较，如果[Ui>f，]则该处理器被认为超负载的，需要进行任务的迁移，将超负载处理器上的任务迁移到轻负载的处理器上进行调度；

（7）结束。

2.4 调度算法的实现

上节给出了多处理器实任务实时调度的模型，在本节将运用上面提出的调度模型对任务进行模拟调度，进一步了解所提出的调度模型的思想与调度过程。

在此多处理器系统中假设存在4个处理器，每一个处理器被视为同构本身无优先级高低之分，且每一个处理器对应一个QUEUQ（0…4）队列；等待分派的任务集[T={t1，t2，t3，t4，t5，t6，t7，t8，t9}，][t1]（0，1，2，2），[t2]（1，3，6，6），[t3]（1，2，2，2），[t4]（1，2，4，4），[t5]（3，1，5，5），[t6]（4，2，8，8），[t7]（2，1，6，6），[t8]（5，2，10，10），[t9]（4，4，12，12）调度步骤如下：

步骤一：将任务集[T]中的任务分派到QUEUE（0…[n]）就绪队列：

根据RMS调度算法的思想，任务集[T]按照任务的周期的大小排序依次为：

[t1]=[t3]

周期越小越优先被分派，因此，任务[t1]被分派到处理器0所对应的QUEUR0队列中，[t3]被分派到QUEUR1队列中，同理， [t4]、[t5] [t2]、[t7]、[t6]、[t8]、[t9]依次顺序被分派到QUEUR2、QUEUR3、QUEUR0、QUEUR1、QUEUR2、QUEUR3、QUEUR0队列中。分派结束后在各QUEUR（0…[n]）队列中的调度序列如图4所示。

3 结 语

本本提出的多处理器实时任务调度模型，利用RMS算法在一定程度上既满足了任务到处理器的分配，又保证了短任务优先被调度的优势。在单处理器上任务的调度使用改进后的EDF算法并能够对任务进行迁移，充分保证了任务调度的实时性。在未来的工作中将进一步完善实验以提高系统的性能。

参考文献

[1] 王永吉，陈秋萍.单调速率及其扩展算法的可调度性判断[J].软件学报，2009，15（6）：799?814.

[2] 尹江会，刘捷，管素清.实时系统中传统调度方式的一种改进方法[J].计算机工程与应用，2005（6）：72?74.

[3] 谢敏，李桥梁.嵌入式实时操作系统任务调度算法优化[J].电子科技，2005（12）：24?26.

[4] LIU C L， LAYLAND J W. Scheduling algorithms for multiprogramming in a [hard?real?time] environment [J]. Journal of ACM， 1973， 20（1）： 174?189.

[5] 杨立身，王中海.嵌入式实时操作系统任务调度算法改进[J].计算机应用，2009，29（9）：2517?2519.

[6] 梁红兵.《计算机操作系统》学习指导与题解[M].西安：西安电子科技大学出版社，2008.

[7] 谭耀铬.操作系统[M].北京：中国人民大学出版社，2007.

[8] XU L H， BRUCK J. Deterministic voting in distributed systems using error?correcting codes [J]. IEEE Transactions on Paralled and Distributed Systems， 1998， 9（8）： 813?824.

[9] 瞿鸿鸣.单处理器系统的实时调度算法研究[J].微机发展，2003（10）：99?100.

[10] 秦啸，韩宗芬，李胜利，等.多处理机系统的高效实时容错调度算法[J].华中理工大学学报，1999，27（7）：14?16.