混合关键级多任务调度中低关键级任务的积极处理＊

黄丽达，李 龙，李仁发，谢 勇

（1.湖南大学嵌入式与网络计算湖南省重点实验室，湖南 长沙410082；2.厦门理工学院计算机与信息工程学院，福建 厦门361024）

1 引言

当前，在嵌入式系统领域，将多种功能整合在一个资源共享的平台上是重要的研究内容。不同功能的计算任务其重要性是不同的，一般用不同关键级来表述，比如在航空和汽车等领域，均有多层次关键级的划分。混合关键级多任务系统（后文简称为混合关键级系统）正是致力于在尽量减少物理设备冗余的情况下，让多个关键级的任务在同一个平台上执行，相对低关键级任务不会影响高关键级任务的时限要求。系统关键级与当前正在运行的任务的关键级一致，每个任务在各关键级都有相应的执行时间上限 WCET（Worst Cast Execution Time，最差情况下执行时间），一旦具有更高关键级任务的执行时间超出了当前关键级的预期WCET，则立即提升系统关键级［1］。

一旦系统关键级提升，为了保证高关键级任务取得更多的CPU计算时间以满足其截止时限，目前通常的处理办法是立即抛弃或者无限期挂起低关键级任务。这种处理方法过于消极，武断地将低关键级任务抛弃，可能会带来负面影响，正在执行的任务通常会访存数据，那么数据的一致性和完整性可能会由于任务的无限期挂起受到影响［2］，尤其是在控制系统中。同时，任务的WCET是其计算时间的保守上限估值，即实际任务执行时间并不会总能达到WCET，那么CPU很可能出现空闲；且不论采用哪一种调度方案，多处理器系统中总会有未被分配的空闲时段（以上两种空闲时段后文中总称为slack）。因此，在提升系统关键级时，消极地抛弃低关键级是不可取的，用更加谨慎积极的方式处理低关键级任务是可行的。

混合关键级多任务调度最早源于Vestals，他在文献［1］中首先正式提出并定义了在多重认证需求下的混合关键级多任务调度问题，并提出了一个适合混合关键级系统的固定优先级调度算法。

de Niz D等［3］从增加系统运行的鲁棒性出发，讨论了在normal和critical双模式下低关键级任务和高关键级任务不同的运行模式，其核心在于高关键级任务窃取低关键级任务的CPU执行时间以保证自己的截止时限；而Baruah S等［4］则从静态验证的角度讨论了混合关键级的多任务调度，在相对保守的认证执行标准和较开放的假设条件下，均能保证相对较高的资源利用率。近年，随着多处理器在嵌入式系统中的广泛应用，一些研究开始转向基于多处理器或多核平台上的混合关键级多任务调度［5，6］。文献［7］在分布式环境下讨论混合关键级任务的局部调度，分析了在多处理器平台上可能出现的关键级反转问题，并着重讨论了结合关键级和过载利用率进行任务到处理器的分配。文献［8］考虑的是以固定优先级的全局调度来处理混合关键级调度问题。截止目前，在多处理器平台上的混合关键级调度研究尚处于起步阶段，审慎处理低关键级任务的研究还相当少。Santy F等［9］首先关注到一般混合关键级调度中被抛弃的低关键级任务，并从多模式的角度讨论了重启低关键级任务的可行性。Su Han等［10］则依据可变周期的弹性调度理论，构建了一个弹性混合关键级多任务模型，通过弹性化处理相对低关键集任务的周期使其获得更频繁的执行。

本文基于同构多处理器平台，对混合关键级多任务调度中低关键级任务进行积极处理。在保证高关键级任务满足其截止时限的同时，尽可能充分利用多处理器的执行能力。为此构建了两类队列：任务队列和空闲时隙队列S＿Que（Slack Queue）。其中任务队列包括两个队列：一个队列是常规任务队列R＿Que（Routine Queue），用于容纳通常混合关键级系统中就绪待调度的任务集；另一个队列是低关键级保留队列L－Que（Low Criticality Reserving Queue），用于保留关键级提升时“被抛弃”的低关键级任务。空闲时隙队列S＿Que是一个全局性队列，整个系统执行过程中各处理器上的动态空闲时隙都被回收到S＿Que。L－Que中的任务则从S＿Que中获得可用的执行时间。这样就实现了不同关键级任务在不同时段不同场景下的“混合调度”，从而获得更好的系统性能。

2 任务模型与定义

设定多处理器平台由m个同构处理器组成，记为π＝｛π1，π2，…，πm｝。混合关键级多任务集由n个具有周期性的任务组成，记为Γ＝｛τ1，τ2，…，τn｝。任务之间相互独立，不存在依赖关系。任务之间允许抢占。每个任务都有其相应的最高关键级。系统关键级与正在运行的任务的关键级一致，即当前同时执行的任务集具有相同关键级。一个任务τi由一个四元组〈Ti，Di，Li，Ci〉表示，其中：

（1）Ti表示任务τi连续两次作业（job）之间的最小时间间隔，即周期。

（2）Di表示任务τi的相对截止时限，Di≤Ti，在之后的讨论中，任务均视为具有默认截止时限，即Di＝Ti。

（3）Li∈｛L1，L2，…，Lk｝，其中L1表示最低关键级LO，Lk表示最高关键级LH，即L的下标越大表示关键级越高。

（4）Ci表示最差情况下的执行时间（WCET），Ci实际上是一个大小为k的向量，Ci（l）表示任务τi处于 关 键 级l 时 的 WCET，l∈ ［L1，Lk］，且Ci（L1）≤Ci（L2）≤…≤Ci（Li）＝Ci（Li＋1）＝…＝Ci（Lk），即任务在低关键级的WCET总是小于或等于高关键级的WCET，而一旦当前系统到达任务既定最高关键级，那么相应任务不能再提升关键级，即在之后的系统关键级提升时其WCET不再变化。

WCET实际是任务占用CPU的保守上限时间，对于任意任务，其实际所需的执行时间总是满足≤Ci（Li）。拥有较高关键级的任务若是超过其在较低关键级的预期 W CET，那么提升系统关键级l，高关键级任务继续执行，低关键级被挂起不再继续执行，此时无论对于高关键级任务还是低关键级任务，将已经执行的部分记为，未执行完毕的部分记为，且满足＋＝。

在上述任务模型中，将任务τi的一次执行称之为作业（job），记为Ji1，Ji2，Ji3，……，每一个任务的job序列是无限的。为了讨论分析简便起见，视所有任务的每一个job均是在其周期一开始就释放。任务τi释放时间记为ri。那么，任务的绝对截止时限记为di＝ri＋Di。

CPU利用率（后文简称为利用率）为：

是任务的WCET与其周期的比值，即一个job的有效计算时间比率。对于混合关键级系统而言，因为每个任务在不同关键级的WCET可能是不同的，那么就应当考虑不同关键级的利用率。对于任意任务τi在不同关键级其相应的利用率为：

Table1 A set of mixed－criticality tasks表1 一个简单混合关键级任务集示例

表1所示的是一个简单的任务集，若是在单处理器平台上，系统关键级l＝L1时，利用率为：

系统关键级升到L2时，由于相对的低关键级任务τ1被无限期挂起，此时利用率为：

类似地，当系统关键级升到L3时，相对的低关键级任务τ2被无限期挂起，此时利用率为：

即由于不同关键级下执行的任务集不同，不同关键级下的利用率也会不同：

下面定义：若一个混合关键多任务调度算法是正确的，那么对于任务集的所有实例均要满足：

（1）当系统关键级不高于任务既定关键级时，任务的每个实例在其周期T内均有足够的运行时间执行完毕，满足其截止时限；

（2）当系统关键级比任务既定关键级高时，所有比该任务关键级高的任务集在其周期T内可获得足够的运行时间执行完毕，并保证截止时限。

在之前几乎所有的混合关键级多任务调度研究中，为了保证前述定义中的（2），一旦系统关键级提升，低关键级任务不论是否已经被释放均立即终止，所以不会考虑低关键级任务在系统处于高关键级状态时的 WCET。但是，本文对低关键级任务进行保留处理，促使其尽可能地执行完毕，所以如表1所示，低关键级任务在高关键级下的行为不发生变化，即其WCET保持不变。

在实时调度理论中，可接受任务是指若系统使用某种调度算法能够被正确调度，即满足截止时限的任务。可接受任务数目，或可接受任务占总释放任务的比率，是衡量系统性能的重要指标之一［11］。

3 调度算法描述

按照如何将任务分配给处理器的方式，多处理器平台上的实时调度大致上可以划分为全局调度和局部调度两种。所谓全局调度，是指待调度任务可以在任意一个处理器上执行，任务随时可以在不同处理器之间迁移；所谓局部调度，是指待调度任务只能按照某种预先分配规则，固定在某一个处理器上执行，不可迁移。文献［12］指出，局部调度更加适合硬实时任务集，而全局调度更适合软实时任务调度需求。对混合关键级多任务集而言，文献［13］指出，以可接受任务数目为性能指标，局部调度要优于全局调度。

现有的混合关键级系统中，除了少量具有最高关键级的、与生命和重大财产安全休戚相关的任务以外，大部分任务之间的“硬”与“软”的界定具有相对性［14］。比如，在从相对低关键级提升到相对高关键级时，低关键级任务呈现出某些软实时任务的特性，而高关键级任务则被视为硬实时任务来确保执行，系统的每一次关键级提升，实际都是这种模式的一次切换。

基于前述结论，我们对处于某关键级下的多任务集进行局部调度，而将在关键级提升时挂起的低关键级任务序列进行“全局性”调度。

这里的全局性是指低关键级要全局分配的是多关键级任务在多处理器上执行时产生的动态空闲（Dynamic Slack）。修改文献［15］中的动态空闲回收规则，描述如下：

（1）系统一旦开始执行，就开始回收各处理器上的空闲时隙（slack，记为sp），为简单起见，不限定最小可回收空闲时隙的时长。

（2）每一片回收的空闲时隙使用二元组（q，d）来描述，其中q表示空闲时隙时长；d表示其绝对截止时限，若超过d时刻则这片空闲时隙失效。

（3）若任务τi在时刻t＜di执行完毕，且其＜Ci，那么产生空闲时隙（min（Ci－，di－t），di）。

（4）未失效的空闲时隙按照d的时间顺序保存在空闲时隙队列S＿Que中，待分配给L＿Que中的任务使用。

（5）若该片空闲时隙失效，或者被使用完毕，则从S＿Que上出列；否则，未使用完的空闲时隙（q－（L），d）重新入列S＿Que，并重复（4）中的分配，j其中，（Lj）表示L＿Que上的某个任务πj的未执行完毕的部分，且0≤（Lj）＜（Lj）≤Cj（Lj）。

同时，引入双任务队列：一个称之为常规任务队列R－Que，用于容纳待调度任务，对该队列上的任务进行局部调度；另一个称之为低关键级保留队列L－Que，用于容纳关键级提升时被挂起的相对低关键级任务，对L－Que中的任务集面向全局队列S＿Que进行调度。

整个调度过程大略可以分为三个阶段：

第一阶段：释放的任务序列依次入列R－Que，对于R－Que上的任务进行局部调度。我们修改了文献［13］中的局部调度算法：将任务映射到处理器的方法以Best－First替换了原来的First－Fit——每次选取当前利用率最低的处理器优先分配，故均衡了各个处理器的负载，并提高了调度成功率。

第二阶段：一旦发生关键级提升，从各个处理器对应的待处理队列中，出列未执行完毕的低关键级任务，并按照如下准则入/出列L－Que：

（1）关键级高的任务优先—当系统中存在两个以上的关键级时，关键级的提升可能会发生不止一次，那么被挂起的相对低关键级任务之间的关键级也不是一致的；

（2）若关键级相同则未执行时间较少的任务优先。

第三阶段：将S＿Que上的时隙依据前述第二阶段的规则和前文的动态空闲回收规则（4）分配给L＿Que上的任务。

之后每次关键级提升都将重复第二和第三阶段的工作。

第一阶段局部调度算法描述如下：

步骤1－1 m个同构处理器，R－Que中是就绪的任务集Γ＝｛τ1，τ2，…，τn｝，当前系统关键级为l∈｛L1，L2，…，Lk｝，其中初始关键级是L1，且初始阶段L－Que为空；

步骤1－2 若∃τi∈Γ，l＝Li，那么对于∀τj∈Γ，其Lj＞l，那么将任务τj分配给当前U（l）最小的处理器；

步骤1－3 若∃/τj∈R－Que，那么将任务τi再分配给当前U（l）最小的处理器，直至R－Que上的任务分配完毕。

第二阶段相对低关键级任务入列L-Que的算法描述如下：

步骤2－1 当前关键级为l时，若有∀τj∈Γ，其Lj＞l，if＞Cj（l），then l＝Li＋1；

步骤2－2 若∃τi∈Γ，且其Li＜l，无论其是否已经分配到各个处理器开始执行，还是在R－Que尚未开始执行，均立刻将τi进行出列处理；

步骤2－3 将步骤2－2中的所有低关键级任务τi入列L－Que：若此时L＿Que不止一个任务，即∃τs，τt∈LQue，

第三阶段L－Que上的低关键级任务全局性调度描述如下：

步骤3－1 记此时L－Que上的任务集为Γlow，每一个Γi∈Γlow，均具有

步骤3－2 按照步骤2－3中的规则出列任务τ′i，同时选取S＿Que中q最小的动态时隙sp，

鉴于上述调度方法涉及两类队列——任务队列和空闲时隙队列，在下文描述中，将本文调度算法简称为MC－DQ。

4 仿真实验

鉴于文献［16］的任务集被多篇文献［9，17］参照应用，仿照其生成测试任务集，对MC－DQ算法进行了仿真实验。依据不同CPU利用率可接受任务集占总任务集的比例，在处理器个数为2、4、8的情况下，与MC－Partition进行了比较，参见图1～图3。可以看到本文所述算法将接受任务集比例平均提高了31%左右，所增加的可接受任务均为当前一般MC调度中被消极抛弃的低关键级任务，性能提升不受处理器个数和利用率限制的影响。

Figure 1 Comparison between MC－DG and MC－Partition on double－processor platform图1 双处理器时 MC－DQ与MC－Partition比较

Figure 2 Comparison between MC－DG and MC－Partition on four－processor platform图2 四处理器时 MC－DQ与MC－Partition比较

Figure 3 Comparison between MC－DG and MC－Partition on eight－processor platform图3 八处理器时MC－DQ与MC－Partition比较

参照同样考虑多处理器平台上低关键级任务处理的文献［9］，本文比较了算法 MC－DQ与文献［9］中所提及的如下三种多关键级任务调度算法：

（1）TA：即通常的多关键级任务调度处理，一旦任务执行时间超过其关键级的 WCET，那么系统关键级提升，而所有的任务均被抛弃；

（2）CD：在TA的基础上，关键级提升后，一旦出现l级的空闲时间，则将系统关键级降至最低；

（3）CD－A：在 CD 基础上，考虑容差（Allowance），进一步约束系统关键级提升条件。

如图4和图5所示，本文算法在相同利用率情况下能获得更大的可接受任务集，抛弃的任务比例比CD－A还要低14%左右，性能不受处理器个数的影响。

Figure 4 Tasks acceptable ratio of different scheduling algorithms with different utilizations图4 不同调度算法在不同利用率下可接受任务集比例

5 结束语

Figure 5 Discarded tasks ration camparison of different scheduling algorigthms图5 比较不同调度算法的抛弃任务集比例

尽管低关键级任务在安全性和重要性上要让位于高关键级任务，但是其数据完整性和一致性对系统的正确执行还是相当有意义的。而实际任务执行过程中，处理器上总是存在可观的空闲时隙。因此，本文基于同构多处理器平台，一反目前混合关键级多任务调度中在高关键级运行阶段消极地对低关键级任务进行抛弃的处理，动态回收所有处理器的空闲时隙专供被抛弃的低关键级任务调度，并结合关键级提升前后的局部调度，以CPU利用率和系统可接受任务比例等作为性能衡量的主要指标。本文的调度算法在确保高关键级任务满足截止时限的同时，获取了更好的整体性能。

实际上，对低关键级任务的处理可以借鉴（m，k）弱硬实时调度的相关调度方法，并充分考虑其偏离截止时限后价值函数的下降情况，整体系统可执行任务数量可能尚会有进一步的提升空间。

［1］ Vestal S.Preemptive scheduling of multi－criticality systems with varying degrees of execution time assurance［C］∥Proc of the 28th IEEE Real－Time Systems Symposium，2007：239－243.

［2］ Kumar C，Vyas S，Cytron R K，et al.Scheduling challenges in mixed－critical real－time heterogeneous computing platforms［C］∥Proc of International Conference on Computational Science，2013：1891－1898.

［3］ de Niz D，Lakshmanan K，Rajkumar R R.On the scheduling of mixed－criticality real－time task sets［C］∥Proc of the Real－Time Systems Symposium，2009：291－300.

［4］ Baruah S，Vestal S.Schedulability analysis of sporadic tasks with multiple criticality specifications［C］∥Proc of the 20th Euromicro Conference on Real－Time Systems，2008：147－155.

［5］ Baker T P，Baruah S K.Schedulability analysis of multiprocessor sporadic task systems［K］.Handbook of Real－Time and Embedded System，NC：Chapman Hall/CRC，2007.

［6］ Herman J，Kenna C，Mollison M，et al.RTOS support for multicore mixed－criticality systems［C］∥Proc of the 18th Real－Time and Embedded Technology and Applications Symposium，2012：197－208.

［7］ Lakshmanan K，de Niz D，Rajkumar R R，et al.Resource allocation in distributed mixed－criticality cyber－physical systems［C］∥Proc of the 30th International Conference of Distributed Computing Systems，2010：169－178.

［8］ Pathan R.Schedulability analysis of mixed－criticality systems on multiprocessors［C］∥Proc of the 24th Euromicro Conference on Real－Time Systems，2012：309－320.

［9］ Santy F，George L，Thierry P，et al.Relaxing mixed－criticality scheduling strictness for task sets scheduled with fp［C］∥Proc of the 24th Euromicro Conference on Real－Time Systems，2012：155－165.

［10］ Su Hang，Zhu Da－kai.An elastic mixed－criticality task model and its scheduling algorithm［C］∥Proc of IEEE/ACM Design，Automation，and Test in Europe，2013：147－152.

［11］ Liu J W S W.Real－time systems［M］.NJ：Prentice Hall PTR Upper Saddle River，2000.

［12］ Lauzac S，Melkem R，Mosse D.Comparison of global and partitioning schemes for scheduling rate monotonic tasks on a multiprocessor［C］∥Proc of the 10th Euromicro Workshop on Real－Time Systems，1998：188－195.

［13］ Baruah S，Chattopadhyay B，Li H，et al.Mixed－criticality scheduling on multiprocessors［J］.Real－Time System，2013（49）：1－36.

［14］ Mixed Criticality Systems.Report from the Workshop on Mixed Criticality Systems Held on 03rd［R］.Belgium，2012.

［15］ Brandenburg B B，Anderson J H.Integrating hard/soft real－time tasks and best－effort jobs on multiprocessors［C］∥Proc of the 19th Euromicro Conference on Real－Time Systems，2007：61－70.

［16］ Baruah S K，Burns A，Davis R I.Response－time analysis for mixed criticality systems［C］∥Proc of 2011 IEEE Real－Time Systems Symposium，2011：34－43.

［17］ Ekberg P，Yi W.Outstanding paper award：Bounding and shaping the demand of mixed－criticality sporadic tasks［C］∥Proc of the 24th Euromicro Conference on Real－Time Systems，2012：135－144.