异构系统双关键级分布式功能的动态调度

刘樑骄　谢国琪　李仁发　杨　柳　刘　彦

1(湖南大学信息科学与工程学院　长沙　410082)2(嵌入式与网络计算湖南省重点实验室(湖南大学)　长沙　410082)3　　　(湖南省发展和改革委员会　长沙　410004) (llj1984109@qq.com)



异构系统双关键级分布式功能的动态调度

刘樑骄1,2谢国琪1,2李仁发1,2杨柳3刘彦1,2

1(湖南大学信息科学与工程学院长沙410082)2(嵌入式与网络计算湖南省重点实验室(湖南大学)长沙410082)3(湖南省发展和改革委员会长沙410004) (llj1984109@qq.com)

摘要异构分布式嵌入式系统是由多种不同关键级功能组成的混合关键级系统，且每个功能又是由多个具有优先级约束的任务组成的分布式功能.异构分布式嵌入式系统的混合关键级调度在性能与时间约束上面临严重的冲突.如何提高系统总体性能，并仍然确保高关键级功能的实时性，在性能与实时性上取得合理的权衡则成为研究的主要优化问题.提出公平策略的动态双关键级任务调度算法F_DDHEFT(fairness on dynamic dual-criticality heterogeneous earliest finish time)以提高系统的整体性能;提出关键级策略的动态双关键级任务调度算法C_DDHEFT(criticality on dynamic dual-criticality heterogeneous earliest finish time) 以满足高关键级功能的实时性;提出时限时距策略的动态双关键级任务调度算法D_DDHEFT(deadline-span on dynamic dual-criticality heterogeneous earliest finish time)，在满足高关键级功能实时性的基础上，提高系统的整体性能，最终在性能与时间约束上取得合理的权衡.实例分析和实验结果验证了D_DDHEFT算法的优越性.

关键词异构分布式嵌入式系统;双关键级；性能；实时；时限时距

新一代高端嵌入式系统是典型的异构分布式嵌入式系统.例如，汽车电子系统由100多个异构ECU(electronic control unit)、各类传感器、执行器和网关等处理单元组成，并通过CAN(controller area network)，FlexRay，LIN(local interconnect network)，MOST(media oriented system transport)和以太网等多种异构网络总线互联，系统体系结构的异构性日趋明显[1-3].当前，一辆豪华轿车至少包含70个ECU以及2 500个信号以完成各种复杂功能的执行[4].与此同时，具有优先级约束的分布式功能在任务数和复杂性上与日俱增.例如汽车电子系统中的线控刹车是典型的分布式主动安全功能，从感知数据开始到执行刹车指令结束，该功能所包含的计算任务存在明显的优先级约束[5].整个过程需分配给5个ECU、1个传感器和2个执行器等处理单元.不同的任务之间产生不同的通信信号并被打包成消息在网络总线上传输.

异构分布式嵌入式系统体系结构是一种典型的分布式集成体系结构，这种结构将多种安全与非安全关键功能集成到了同一个平台，并由此在学术界和工业界引入了关键级与混合关键级系统的概念，并成为复杂嵌入式系统的主要研究热点[6].“关键级”强调某个功能发生安全事故的严重性后果，以表示其重要程度，并经过了第三方机构的严格认证.高关键级功能相比低关键级功能意味着前者在时间需求上要求更加严格苛刻，错过高关键级功能的时隙将会造成严重的安全问题.关键级在汽车电子系统中用汽车安全完整性等级表示[7].道路车辆-功能安全标准规范“IS026262”对汽车电子系统中的功能从低到高划分成A,B,C,D四个ASIL.其中，D为最高关键级，其安全性需求最为苛刻；A为最低等级，安全性需求最低.

任务调度是混合关键级系统的核心研究内容.通过高效的任务调度算法，可充分利用异构分布式嵌入式系统中的处理器和通信等资源以提高系统性能，但是面向具有不同关键级的分布式功能的调度却面临严峻的挑战.

首先，尽管混合关键级系统概念自诞生以来提出了众多的调度理论与算法，但是大多方法都是基于周期任务模型或随机任务模型，且都是从”任务级”的角度研究其调度问题[8-14].然而异构分布式嵌入式系统中的分布式功能所包含的任务存在明显的优先级约束，传统的”任务级”模型显然无法精确描述任务之间的优先级约束.如何从“功能级”的角度建立分布式的系统模型显得至关重要.近年来相关学者针对汽车电子系统提出了时序链[15]、功能链[16]和任务链[17]等功能模型以适应任务间的优先级约束问题，但仅限于简单的分布式功能.随着功能的日益复杂化与并行化，迫切需要一种能够更加精确反映功能特性的模型.在并行与分布式计算领域，有向无环图(directed acyclic graph， DAG) 是一个能够描述具有复杂的任务优先级约束与蕴含通信开销的分布式功能的常用模型[18-19].

其次，异构分布式嵌入式系统在性能与时间约束上面临严重的冲突.若从系统的角度来看，降低整个系统的调度长度、提高系统性能是其主要目标.若从功能的角度来看，满足其时间约束、确保实时性是其主要需求.然而，对于具有资源约束的大规模异构分布式嵌入式系统，不可能满足所有分布式功能的时间约束，因此满足高关键级功能的时限、确保安全性则成为主要目标.在并行与分布式计算领域，通过公平调度多个分布式功能来降低系统的调度长度是一种可行的方法，但是应用于异构分布式嵌入式系统则会使得大量分布式功能(包括高关键级功能和低关键级功能)的时间约束无法满足.

因此，如何提高系统的整体性能并确保高关键级功能的实时性则成为异构分布式嵌入式系统的混合关键级任务调度需要优化的主要问题.为此，本文旨在通过提出精确反映分布式功能的混合关键级系统模型，并在此基础上提出优化的任务调度算法，最小化系统性能与功能时限之间的冲突，在性能与实时性上取得合理的权衡.

1相关研究

由于公平性是提高并行与分布式系统性能的重要方法，而满足高关键级分布式功能的时间约束则是混合关键级的主要研究内容，因此本节将公平性和混合关键级的相关研究分别论述.

1.1公平性研究

针对单个分布式功能的DAG任务调度是研究多个分布式功能DAG调度的重要基础.异构系统单DAG任务调度一般包含2个步骤：1)根据优先级进行任务排序;2)将任务分配到合适的处理器上.异构分布式系统的DAG任务调度算法是一个典型的NP难问题，比较有名的算法有CPOP[18]，HEFT[18]，HSV[19]等.同单DAG任务调度一样，异构系统多DAG调度也包含任务优先级排序和处理器分配2个步骤.文献[20]提出了将多个DAG合成一个复合DAG后， 再利用诸如HEFT等经典的单DAG调度算法调度.很明显，合成方法没有考虑公平性问题.同样，先来先服务(first come first serve， FCFS)和及时服务(serve on time， SOT)也都不能体现公平性.

Zhao等人[21]首次指出了在多DAG调度中的公平性问题，并提出了slowdown驱动的多DAG静态公平任务调度算法Fairness.我们也提出了考虑通信开销的静态调度算法[1].多分布式功能DAG动态调度更加符合现实需求.动态调度即可在任意时刻提交新的功能到系统中，目前主要有RANK_HYBD[22],OWM[23],FDWS[24]等算法.动态调度算法与静态调度算法的主要区别在于前者在有新功能提交时，要判断当前处理器是否空闲以及如何实现公平性等问题.如果当前处理器忙，OWM会继续将任务保留在系统的公共就绪队列中等待处理器空闲，以等待下一轮的分配.OWM的等待方式过于被动，FDWS则通过为每个处理器提供一个处理器等待队列来实现任务的分配时隙并等待处理器空闲，以减少多次的就绪调度.

1.2混合关键级研究

2007年Vestal[8]在嵌入式实时系统领域顶级国际会议RTSS上首次提出了混合关键级系统的概念以及相应的固定优先级任务调度策略.从此混合关键级系统相关的基础理论和调度问题迅速成为实时系统领域的热点问题.混合关键级系统包括周期任务模型和随机任务模型2个主要模型，调度策略则包括固定优先级抢占式策略、固定优先级非抢占式策略、动态优先级策略等.由此可见，混合关键级系统的调度问题实际上是传统实时系统在面临多种关键级任务时的扩展，因此改进和扩展的RM和EDF算法也成为混合关键级系统的主要调度方法[8-14].

早期的研究主要集中在单处理器调度，由于成本、功耗和性能等需求，基于多处理器或多核架构的混合关键级调度成为近年来的研究热点[25-26].分区调度和全局调度是这类架构的2种主要调度算法.分区调度即通过时间分区的方式将任务静态地分配到处理器核上，在任务分配给具体的处理器核以后，该任务只能在该处理器核上调度执行，被抢占或被挂起以后也不能再迁移到其他处理器核上调度执行.而全局调度策略可以将任务分配到任何处理器核上，并可在处理器之间迁移.需要指出的是，目前的混合关键级系统主要考虑双关键级系统，即包括高关键级和低关键级，或者安全关键级或非安全关键级2种级别.高关键体现为功能或任务的强实时性，低关键级体现为软实时性；而对于非关键级功能或任务，则无需关注其实时性需求.尽管双关键级仅考虑2个关键级问题，但是其调度问题仍然是一件非常复杂的工作，许多存在的问题需要综合权衡考虑，主要包括确保高关键级功能或任务的实时性、提高系统性能或资源利用率、处理器空闲时隙、系统关键级切换等问题.因此，本文也将双关键级系统作为研究对象，从“功能级”的角度研究异构分布式嵌入式系统的混合关键级调度问题.

近年来，具有优先级约束任务的混合关键级功能的调度研究也取得一定进展.将每个分布式功能抽象成DAG模型，文献[27-30]提出了一系列的异构分布式系统的混合关键级调度算法.文献[27]中通过采用时间与空间分区实现功能的隔离.每一个实时功能运行在独立的时间分区，其中高关键级功能使用静态循环调度算法，低关键级功能则使用固定优先级抢占策略以满足所有功能的时限.文献[28]对文献[27]的工作进行了扩展，考虑了不同关键级功能的分区共享问题.上述2项工作的主要问题在于忽略了任务之间的通信开销.因此在文献[29]考虑在处理器之间通过TTEthernet协议实现通信，但仍对通信开销缺乏定量的分析.文献[30]则着重考虑满足硬实时功能的可调度性，并最大化软实时功能的服务质量.上述工作都基于如下前提：当且仅当系统有足够的时间和空间分区，混合关键级功能才能集成到同一个平台上来；其次，上述工作所采用的方法都是基于传统混合关键级系统的调度理论，包括使用改进的RM，EDF调度算法和分区调度机制等.尽管采用了DAG模型抽象了分布式功能，但并未充分利用异构分布式系统中DAG模型的经典理论与方法，无法体现异构分布式嵌入式系统的分布式与并行化特征.

本文的主要目标就是解决上述研究中面临的一些问题，提出面向异构分布式嵌入式系统的混合关键级模型，从“功能级”以及“并行与分布式计算”的角度来研究性能与时间约束权衡下的动态调度优化问题.

2系统模型

以异构分布式汽车电子系统为例，它由多个异构 ECU(不同供应商提供的ECU在设计方法或硬件实现上不同)、传感器和执行器等处理设备组成，本文将这些处理单元统称为处理器，并用集合P={p1，p2，…} 来表示.用CL={LC,HC}表示系统中的关键级层次，当前混合关键级系统的研究也主要集中在双关键级系统[8-14]，因此本文也基于双关键级系统，将功能划分为低关键级(lower-criticality,LC) 和高关键级(higher-criticality,HC)两种，且满足高关键级功能的实时性是必需的目标，否则会造成严重的安全问题.

以汽车电子系统中的线控刹车功能为例，它的实现是由多个相互具有数据依赖的任务组成.当驾驶者踩下刹车踏板时，首先同时对汽车当前的运行状态和周围的物理环境信息进行采集，接着将接触信号以电子形式传输至通过多种总线互连的ECU单元，ECU接收到信号并处理后，再传送给其他ECU单元执行并开启楔轴承机械装置，并以恰当的频率对刹车执行器发出指令启动刹车信号，然后传输给执行器执行刹车动作.整个计算执行和信号传送需要在毫秒级内完成[5].上述功能任务在不同处理器上执行并产生大量的通信开销，且这些功能任务又存在优先级约束的依赖关系，它的实现需要通过总线网络进行交互和协作才能完成.因此可以用一个有向无环图DAG来描述一个分布式功能[18-19]，这也是并行与分布式计算领域分布式功能的常用模型.在本文用Func={N,W,E,C,criticality,lower_bound,deadline,arrival_time,makespan}表示一个分布式功能.其中N={n1,n2,…}表示任务集合；由于处理器处理能力的异构性，使得不同任务在不同的处理器计算时间不尽相同，因此定义W为一个|N|×|P|的矩阵，wi,k表示任务ni在处理器pk上的计算开销；E={e1,2,e2,3,…,ei,j,…}描述为任务间的优先级约束与数据依赖关系集合；本文假设处理器之间采用CAN总线型互联，使用C={c1,2,c2,3,…,ci,j,…}描述具有数据依赖的任务之间的通信开销集合，如果将这2个任务分配到同一个处理器上，则通信开销为0.通信开销的描述与经典DAG模型一样[18-19].由于处理器之间通过CAN，FlexRay，LIN，MOST等多种类型的网络和网关实现互联，不同总线的带宽不尽相同，因此任务之间的通信开销也不同，描述C={c1,2,c2,3,…,ci,j,…}为具有数据依赖的任务之间的通信开销集合，如果将这2个任务分配到同一个处理器上，则通信开销为0.pred(ni)表示任务ni的直接前驱任务集合；ind(ni)表示任务ni的入度，也就是其直接前驱任务集合的个数，当前任务只有在它全部前驱任务的数据到达后才能执行.succ(ni)表示任务ni的直接后继任务集合；outd(ni)表示任务ni的出度，也就其直接后继任务集合的个数.没有前驱任务的任务为入口任务，记为nentry；没有后继任务的任务为出口任务，记为nexit.criticality∈CL表示该功能的关键级；lower_bound表示该功能单独占用所有处理器资源时的调度长度,本文称之为下界；deadline表示该功能的时限.criticality，lower_bound，deadline这3个参数都由第三方认证机构给出.arrival_time表示功能的到达时间；makespan表示功能的最终调度长度.

混合关键级系统包括多种安全关键和非安全关键功能，我们用MS={{Func1,Func2,…},system_criticality,makespan}表示.其中system_criticality∈CL表示当前系统所处的关键级，并且可以在LC和HC之间进行切换；makespan表示系统的整体调度长度.由于一个任务分配到不同处理器会产生一定的通信开销并使问题变得更加复杂.因此本文仅考虑非抢占式调度，而不包括抢占式调度和分区机制.

如图1为由3个分布式功能组成的双关键级系统，包含FuncA,FuncB，FuncC.表1为相应的参数值，其中FuncB为高关键级功能，到达时刻为20;FuncA和FuncC为低关键级功能，到达时刻分别为0和50.图1中，任务A1与任务A2之间的连线表示只有A1执行完成后A2才有机会执行，连接任务A1与A2边的权值表示它们之间的通信开销为18；若任务A1与A2在分配在同一处理器上，则通信开销为0.表1中任务A1与处理器p1所结合处的数字14表示任务A1在处理器p1上的计算开销为14.

Fig. 1　Dual-criticality systems with three distributed functionalities.图1　包含3个分布式功能的双关键级系统

FunctionalityCriticalityArrivalTimeTaskProcessorp1p2p3ranku(ni)FuncALC0FuncBHC20FuncC50LCA1141619109A213191878A311131981A41381781A512131070A61316964A77151143A85111436A918122045A102171615B145642B29101120B318171631B421151935B57656C181119110C21413891C39121663C418151431C518162039C651078

3调度策略

3.1认证分析

HEFT算法是并行与分布式计算中众所周知的具有低复杂度和高性能的DAG调度算法[18].该算法使用向上排序值(ranku)的降序排列作为任务优先级排序标准，计算为

(1)

使用最小最早完成时间作为处理器分配，计算为

(2)

其中，

(3)

avail[pk]表示处理器pk的可用时间，AFT(ni)表示任务ni的实际完成时间.很明显，对于分布式功能中的优先级约束的任务，最早完成时间策略体现了一种典型的贪婪策略.

混合关键级系统中的高关键级功能具有严格的硬实时需求，且需通过第三方认证机构进行严格的认证.因此，第三方认证机构必须采用公认有说服力的标准算法对该功能进行严格的评估.作为低复杂度和高性能调度算法的著名算法，HEFT完全可以也应该作为异构分布式嵌入式系统中的功能认证算法.第三方认证机构对高关键级功能进行认证时，会独占所有处理器进行调度，此时具有最小的调度长度，本文称之为下界(lower_bound).根据下界值，第三方认证机构经过安全分析和风险评估后，会给出一个合理的时限时距(deadline_span).需要指出的是，本文的主要工作是假设功能的高低关键级级别已经通过认证获得，并在此基础上进行调度.而不是具体的安全分析和风险评估，也就是不对高低关键级关键进行具体的度量.因此，本文的研究假设高低关键级级别已经度量.综合lower_bound，deadline_span，arrival_time可得出该功能的绝对时限:

(4)

对于分布式功能的每个任务，也存在相应的下界为

(5)

因此，每个任务的绝对时限为

(6)

表2、表3分别列出了图1所示的高关键级功能FuncB及其任务的下界值和绝对时限.

Table 2　Attributes of Higher CriticalityFuncB

Table 3　Attributes of Tasks ofFuncB

3.2公平策略

首先提出系统的调度框架，如图2所示，该框架引入3个队列，分别为任务优先级队列task_priority_queue、公共就绪队列common_ready_queue以及任务分配队列task_allocation_queue.

1) 每一个分布式功能都拥有一个task_priority_queue，用于对任务优先级进行排序；

2) 系统中仅有一个common_ready_queue，用于存储待分配的就绪任务；

3) 每一个处理器都拥有一个task_allocation_queue，用于存储分配到该处理器的相应任务.

公平策略的任务调度一共包括5个主要步骤：

Step1. 任务排序.对一个分布式功能排序，并按ranku式(1)的降序排列.

Step2. 任务就绪.基于轮转的公平策略，从每一个分布式功能的task_priority_queue中取出一个ranku最大的就绪任务(只有该任务的所有前驱任务分配完成后，该任务才能成为就绪任务)，放入到common_ready_queue中，同样按ranku的降序排列.

Step3. 任务分配.依次从common_ready_queue中取出每个就绪任务，在插入法的基础上将其分配到具有最小EFT的处理器task_allocation_queues上.

Step4. 任务执行.若task_allocation_queue中任务的开始时间等于当前时间，对该任务进行调度.

Step5. 新功能到达.若当前时刻有新的分布式功能到达，则取消所有task_allocation_queue中未开始调度的任务，并将这些任务放回各自的task_priority_queue中.重复Step1，将新的分布式功能的任务与其他功能中未分配的任务一起进行新一轮的公平分配.

Fig. 2　Scheduling framework of systems.图2　系统调度框架

依据上述调度框架和公平策略，提出公平策略的动态双关键级任务调度算法F_DDHEFT(fairness on dynamic dual-criticality heterogeneous earliest finish time),该算法步骤如算法1所示：

算法1.F_DDHEFT算法.

输入：处理器集；

输出：调度结果.

while (有功能需调度) do

if (有一个功能Funcnew在时刻current_time到达) then

计算Funcnew中所有任务的ranku值，并将这些任务放入到队列task_priority_queue(Funcnew) 中;

MS.add(Funcnew);

将任务分配队列中未执行的任务放回到各功能的任务优先级队列;

while (有任务可以分配)

for (m=1;m≤|MS|;m++)

从task_priority_queue(Funcm)中取出任务ni;

common_ready_queue.put(ni);

end for

while (!common_ready_queue.empty()) do

从common_ready_queue中取出任务ni;

基于插入法将任务ni分配到具有最小EFT(ni,pk)的task_allocation_queue(pk)中;

end while

end while

end if

end while

F_DDHEFT算法的时间复杂度为O(m×n2×p).其中m代表功能数，n表示包含最多任务数的功能拥有的任务数，p为处理器数.遍历所有功能的时间复杂度应为O(m)；遍历任务次数的时间复杂度应为O(n)；计算ni的EFT需遍历其前驱和各处理器的时间复杂度应为O(n×p).因此F_DDHEFT算法的时间复杂度为O(m×n2×p).

本文提出的公平策略的最大改进在于当有新功能到达时，不像OWM或者FDWS算法那样会阻塞自己并等待其他任务完成.本文的策略会取消那些“已选择处理器但未开始调度的任务”，并与新的DAG一起进行公平分配.基于图1提供的混合关键级实例，图3所示为F_DDHEFT算法的执行过程.

Fig. 3　Process of task scheduling based on the fairness policy.图3　基于公平策略的任务调度过程

1) 如图3(a)所示，低关键级功能FuncA在时刻0到达，根据向上排序值ranku分配所有任务到相应的任务分配队列.任务分配顺序依次为{A1,A3,A4,A2,A5,A6,A9,A7,A8,A10}.

2) 如图3(b)所示，高关键级功能FuncB在时刻20到达，从公平的角度出发，取消任务分配队列中未开始执行的任务，这些任务是{A2,A5,A6,A9,A7,A8,A10}.

3) 如图3(c)所示，FuncB中的任务{B1,B4,B3,B2,B5}与FuncA中取消的任务{A2,A5,A6,A9,A7,A8,A10}一起公平调度,公平调度顺序为{A2,B1,A5,B4,A6,B3,A9,B2,A7,B5,A8,A10}.需要指出的是，由于FuncB是高关键级功能，其调度长度FuncB.makespan=67,超过了CA所认证的绝对时限FuncB.deadline=66(如表2所示).因此FuncB会对系统造成严重的安全问题.

4) 如图3(d)所示，低关键级功能FuncC在时刻50到达，同样从公平的角度出发，取消任务分配队列中未开始执行的任务，这些任务是{A9,A8,A10}与{B5}.

5) 如图3(e)所示，FuncC中的任务{C1,C2,C3,C5,C4,C6}与FuncA中取消的任务{A9,A8,A10}和FuncB中取消的任务{B5}一起公平分配,分配顺序为{C1,A9,B5,C2,A8,C3,A10,C5,C4,C6}.此时，对于高关键级分布式功能FuncB，其调度长度FuncB.makespan=71,仍然超过了CA所认证的绝对时限FuncB.deadline=66(如表2所示).因此FuncB会持续对系统造成严重的安全问题.需要指出的是，此时系统的调度长度MS.makespan=102，该项指标反映系统的整体性能，MS.makespan越低，则性能越好.

3.3关键级策略

如引言所述，以及通过3.2节所展示的实例，公平任务调度易造成高关键级功能错过其绝对时限，这对安全高度关键的分布式嵌入式系统来说无法容忍.因此，本节提出动态环境下满足高关键级功能绝对时限的任务调度算法以解决上述问题.

系统关键级是混合关键级系统中的一个重要概念.系统关键级可以进行切换，比如从低关键级提升到高关键级，也可以从高关键级降回低关键级.系统关键级的提升或下降实际上是系统的模式转换.对于双关键级系统，如果系统处于低关键级，那么所有关键级功能都可以在该模式下执行；如果系统处于高关键级，那么仅有高关键级功能可以在该模式下执行.因此，如图3所示的公平任务调度实例，为保证所有功能都有公平执行的机会，系统始终处于低关键级模式下.

由于系统中可能有多个高关键级功能，并且可在任意时刻提交新的高关键级功能到系统中，此时系统也不可能满足所有高关键级功能的实时性.因此根据实时调度理论的EDF(earliest deadline first)策略,在高关键级模式下，系统会对所有高关键级功能按照“绝对时限”的降序排列，并优先分配EDF最小的高关键级功能中的所有任务.

本文还提出关键级策略的动态双关键级调度算法C_DDHEFT(criticality on dynamic dual-criticality heterogeneous earliest finish time),其核心思想就是通过牺牲低关键级的公平执行机会，优先执行高关键级功能以满足时限.C_DDHEFT算法的步骤如算法2所示：

算法2.C_DDHEFT算法.

输入：处理器集；

输出：调度结果.

while (有功能需调度) do

if (有一个功能Funcnew在时刻current_time到达) then

计算Funcnew中所有任务的ranku值，并将这些任务放入到队列task_priority_queue(Funcnew) 中;

MS.add(Funcnew);

if (Funcnew).criticality=HC) then

MS.system_criticality=HC;

将任务分配队列中未执行的任务放回到各功能的任务优先级队列;

else

仅将低关键级功能中的任务分配队列中未执行的任务放回到各功能的任务优先级队列;

end if

if (MS.system_criticality=HC) then

将高关键级功能按照EDF的降序排列；

for (m=1;m≤|MS.higher_criticality.functionalities|;m++)

从task_priority_queue(Funcm)中取出一个任务ni;

基于插入法将任务ni分配到具有最小EFT(ni,pk)的task_allocation_queue(pk)中;

end for

end if

MS.system_criticality=LC;

while (有任务可以分配)

for (m=1;m≤|MS|;m++)

从task_priority_queue(Funcm)中取出一个任务ni;

common_ready_queue.put(ni);

end for

while (!common_ready_queue.empty()) do

从common_ready_queue中取出一个任务ni;

基于插入法将任务ni分配到具有最小EFT(ni,pk) 的task_allocation_queue(pk)中;

end while

end while

end if

end while

C_DDHEFT算法的时间复杂度与F_DDHEFT算法一样，也为O(m×n2×p).

C_DDHEFT算法与F_DDHEFT算法的区别主要有2点:1)若新到达的功能是高关键级功能，那么系统会提升系统关键级，并取消所有任务分配队列中未开始执行的任务.①依据EDF原则对高关键级功能进行分配，待全部分配完成后将系统关键级降级为低关键级;②再与其他被取消分配的任务一起进行公平分配.2)若新到达的功能是低关键级功能，那么系统只会取消所有任务分配队列中未开始执行的低关键级功能中的任务(不包括高关键级功能中的任务)，新到达的功能只与这些被取消分配的任务一起进行公平调度(换言之，低关键级功能不会影响高关键级功能中的任务分配).基于图1提供的混合关键级实例，图4为C_DDHEFT算法的任务调度过程.

Fig. 4　Process of task scheduling based on the criticality policy.图4　基于关键级策略的任务调度过程

1) 低关键级功能FuncA在时刻0到达，系统关键级为LC,根据向上排序值ranku分配所有任务到相应的任务分配队列.任务分配顺序依次为{A1,A3,A4,A2,A5,A6,A9,A7,A8,A10}.上述过程与图3(a)完全相同，这里不再画图描述.

2) 如图4(a)所示，高关键级功能FuncB在时刻20到达，系统关键级提升到HC,取消任务分配队列中未开始执行的任务，这些任务是{A2,A5,A6,A9,A7,A8,A10}.

3) 如图4(b)所示，FuncB中的任务{B1,B4,B3,B2,B5}优先分配，分配完成后，系统关键级切换回LC，FuncA中取消的任务{A2,A5,A6,A9,A7,A8,A10}再进行分配,整个任务分配顺序依次为{B1,B4,B3,B2,B5,A2,A5,A6,A9,A7,A8,A10}.FuncB是高关键级分布式功能，此时其调度长度FuncB.makespan=56,满足CA所认证的绝对时限FuncB.deadline=66(如表2所示).因此FuncB不会对系统造成安全问题.

4) 如图4(c)所示，低关键级功能FuncC在时刻50到达，取消所有低关键级功能中未开始执行的任务，这些任务是{A9,A8,A10}.

5) 如图4(d)所示，FuncC中的任务{C1,C2,C3,C5,C4,C6}与FuncA中取消的任务{A9,A8,A10}一起公平分配,分配顺序为{C1,A9,C2,A8,C3,A10,C5,C4,C6}.此时，对于高关键级分布式功能FuncB，由于它并未受低关键级功能达到所造成的影响，因此它的调度长度仍然为FuncB.makespan=56.特别需要指出的是，此时系统的调度长度MS.makespan=123，明显超过3.2节公平调度的调度长度102.因此尽管关键级的调度策略满足了FuncB的实时性，但造成了系统整体性能过低.

3.4时限时距策略

通过3.2节公平策略和3.3节关键级策略的实例分析可知：公平策略能够提高性能，但造成高关键级功能实时性得不到满足.关键级策略虽能够满足高关键级功能的实时性，但造成系统的整体性能急剧下降.异构分布式嵌入式系统的混合关键级任务调度在性能与时间约束上面临严重的冲突.如何在动态环境下提高系统整体性能，并仍然确保高关键级功能的实时性，在性能与实时性之间取得合理的权衡则成为主要的优化问题.

提出时限时距的动态双关键级调度算法D_DDHEFT(deadline-span on dynamic dual-criticality heterogeneous earliest finish time),其核心思想就是通过判断每个任务的时限是否满足来决定进一步的任务分配.D_DDHEFT算法的步骤如算法3所示：

算法3. D_DDHEFT算法.

输入：处理器集；

输出：调度结果.

while (有功能需调度) do

if (有一个功能Funcnew在时刻current_time到达) then

计算Funcnew中所有任务的ranku值，并将这些任务放入到队列task_priority_queue(Funcnew) 中;

MS.add(Funcnew);

将任务分配队列中未执行的任务放回到各功能的任务优先级队列;

while (有任务可以分配)

for (m=1;m≤|MS|;m++)

从task_priority_queue(Funcm)中取出一个任务ni;

common_ready_queue.put(ni);

end for

Fig. 5　Process of task scheduling based on the deadline-span policy.图5　基于时限时距策略的任务调度过程

while (!common_ready_queue.empty()) do

从common_ready_queue中取出一个任务ni;

基于插入法将任务ni分配到具有最小EFT(ni,pk) 的task_allocation_queue(pk)中;

if (Func(ni).criticality=HC&&makespan(ni)>deadline(ni)) then

取消本轮与前一轮的任务分配结果;

将这些取消的任务放回到各功能的任务优先级队列;

清空common_ready_queue;

MS.system_criticality=HC;

end if

end while

if (MS.system_criticality=HC)

将高关键级功能按照EDF的降序排列；

for (m=1;m≤|MS.higher_criticality.functionalities|;m++)

从task_priority_queue(Funcm)中取出一个任务ni;

基于插入法将任务ni分配到具有最小EFT(ni,pk) 的task_allocation_queue(pk)中;

end for

MS.system_criticality=LC;

end if

end while

end if

end while

D_DDHEFT算法的时间复杂度与F_DDHEFT和C_DDHEFT一样都为O(m×n2×p).D_DDHEFT并没有因为权衡优化而造成时间复杂度增长，由此表明关键级提升的优化不会造成时间复杂度的增长.图5为D_DDHEFT算法的任务调度过程.

1) 低关键级功能FuncA在时刻0到达，系统关键级为LC,根据向上排序值ranku分配所有任务到相应的任务分配队列.任务分配顺序依次为{A1,A3,A4,A2,A5,A6,A9,A7,A8,A10}.上述过程与图4(a)完全相同，这里不再赘述.

2) 如图5(a)所示，高关键级功能FuncB在时刻20到达，此时系统关键级并不急于提升到HC,而是FuncB中的任务与FuncA中的任务一起公平分配，直到B3错过其时隙(makespan(B3)=58,大于deadline(B3)=52)(如表2所示)，如图5(b)所示.

此时，系统关键级提升到HC,如图5(c)所示,取消本轮与前一轮的公平任务分配(由于本轮分配尚未分配完成，若只取消本轮，继续分配还是本轮的分配结果，因此需要取消到前一轮)，这些任务是{A5,B4,A6,B3}.

3) 如图5(d)所示，FuncB中的任务{B4,B3,B2,B5}优先分配，分配完成后，系统关键级切回LC，FuncA中取消的任务{A5,A6,A9,A7,A8,A10}再分配,整个任务分配顺序为{B4,B3,B2,B5,A5,A6,A9,A7,A8,A10}.FuncB是高关键级分布式功能，此时其调度长度FuncB.makespan=61,满足CA所认证的绝对时限deadline=66(如表2所示).因此FuncB不会对系统造成安全问题.

4) 如图5(e)所示，低关键级功能FuncC在时刻50到达，取消所有低关键级功能中未开始执行的任务，他们是FuncA中的{A9,A7,A8,A10}和FuncB中的{B5}.

5) 如图5(f)所示，FuncC中的任务{C1,C2,C3,C5,C4,C6}与FuncA中的{A9,A7,A8,A10},以及FuncB中任务{B5}一起公平分配,分配顺序依次为{C1,A9,B5,C2,A7,C3,A8,C5,A10,C4,C6}.此时，对于高关键级分布式功能FuncB，尽管其与其他功能中的任务一起分配，但其调度长度仍然为FuncB.makespan=61.特别需要指出的是，此时系统的调度长度MS.makespan=104，明显低于3.3节关键级策略调度的调度长度123.不难发现，时限时距策略调度在满足FuncB实时性的前提下，有效地提高了系统的整体性能.

4实验

4.1评价指标

本文采用系统的调度长度比(schedule length ratio, SLR)[18]、功能之间的不公平性(unfairness)[19]以及高关键级功能的时隙错失率(deadlines missed radio, DMR)[31]作为评价指标.

实验的硬件环境为1台配置了奔腾双核处理器(3.2 GHz2.0 GB RAM)的Windows XP机器，使用 Java语言，根据不同参数生成各种不同特性的DAG功能样本.主要包括任务个数n={30,40,50,60,70,80,90,100}.产生随机DAG的参数设置为：任务个数n={30,40,50,60,70,80,90,100}，形状参数α={0.5,1.0,2.0,4.0}，最大出度β={1,2,3,4,5}，最大入度γ={1,2,3,4,5}，通信开销与计算开销的比值CCR={0.1,0.5,1.0,5.0,10.0}，任务在不同处理器上执行时间的差异度η={0.1,0.5,1.0,2.0,4.0}.假设wi表示任务ni的平均计算开销，那么任务ni在处理器pk上的计算开销为

wi(1-η4)≤wi,k≤wi(1+η4).

(7)

以上参数主要针对单个功能，整个系统中的功能数为MSN={10,20,30,40,50}， 不同功能的到达时距(arrival interval) 为{0,50,100,150,200}，每个高关键级功能的相对时限定为其下界的110%.

4.2公平性算法比较

本节的实验主要验证本文提出的算法与同类算法(RANK_HYBD[22],OWM[23],FDWS[24])采用的公平策略在性能上的比较.

实验1.探究SLR和Unfairness随功能到达时距变化的情况.功能样本从样本空间取出.每个功能的到达时距的变化范围是0～200，并以50个时距递增.到达时距的大小反映了系统中功能的动态负载情况，总到达的功能数固定为50.所有功能具有同样的关键级.本文提出的F_DDHEFT与同类算法进行比较.

图6所示为采用4种算法的SLR和Unfairness随功能到达时距变化情况.实验结果显示，到达间距越大，平均SLR和平均Unfairness越低.表明动态提交功能的间距越大，任务需要重新调度的几率减少，性能结果更好.F_DDHEFT的平均SLR优于RANK_HYBD，OWN，FDWS的平均百分比分别达30%，10%，5%以上；平均Unfairness优于RANK_HYBD，OWN，FDWS的平均百分比分别为30%，30%，15%.从数据分析可知，通过公平调度可以尽可能地提高调度性能，且F_DDHEFT相比同类算法性能更好.

Fig. 6　SLR and Unfairness for varying deadline-spans.图6　SLR和Unfairness随功能到达时距变化的情况

4.3本文提出的算法比较

据我们所知，这是第1次针对性能与实时权衡的异构分布式嵌入式系统双关键级的动态研究，因此本节的实验主要探究和验证本文提出的3种算法在性能、实时及其权衡的优化.

实验2. 探究SLR，Unfairness，DMR随系统中功能数变化的情况.基于双关键级系统，系统总的到达时距固定为0，即所有功能都在时刻0同时到达.高关键级功能数的变化范围为10～50，并以10递增.功能数目反映了系统的工作负载情况.通过对本文所提出的3种算法(F_DDHEFT,C_DDHEFT,D_DDHEFT)进行实验并比较相应结果.

图7(a)和图7(b)所示为3种算法的SLR和Unfairness随系统功能数目变化情况.随着功能数目增加，SLR都增大，不公平性都越来越高，这表明了系统中任务调度的公平性越来越低，系统的总体性能在逐渐下降.可以发现F_DDHEFT拥有最好的性能，并且随着功能数目的增多，系统的SLR并未显著增长，始终控制在1.9～2.6范围内，不公平性也最低；C_DDHEFT表现最差，而且随着系统负载不断加大，性能越低.图7(c)所示为采用3种算法的DMR随系统功能数目变化情况，随着功能数增加，DMR都越来越高.F_DDHEFT在DMR表现最差，DMR始终控制在90%以上；C_DDHEFT在DMR表现最好.

Fig. 7　SLR,Unfairness and DMR for varying numbers of functionalities.图7　SLR，Unfairness，DMR随系统中功能数变化的情况

上述实验可以发现，无论SLR和Unfairness，还是DMR， D_DDHEFT处于F_DDHEFT和C_DDHEFT之间,并且在DMR上与C_DDHEFT较为接近， DMR整体控制在20%～65%.DDHEFT在性能和实时性上体现了合理的权衡.

实验3. 探究SLR，Unfairness，DMR随功能到达时距变化的情况.功能样本从样本空间取出.每个功能的到达时距的变化范围是0～200，并以50个时距递增.到达时距的大小反映了系统中功能的动态负载情况，总到达的功能数固定为50.基于双关键级系统，每个功能被认证为高关键级功能或低关键级功能,2种功能数目各占一半.通过对本文所提出的3种算法(F_DDHEFT,C_DDHEFT,D_DDHEFT)进行实验并比较相应结果.

图8所示为采用3种算法的SLR，Unfairness，DMR随功能到达时距变化情况.随着到达时距的增大，SLR都减少，不公平性降低，DMR降低，体现系统的各项指标都在提升.当到达时距较小时，3种算法的差距较为明显，一定程度上反映了3种算法的特点.随着到达时距不断增长，3种算法的差距逐渐减少，这实际上体现了3种算法最终趋近一种各自采用HEFT独立调度时的表现.

Fig. 8　SLR,Unfairness and DMR for varying deadline-spans.图8　SLR，Unfairness，DMR随功能到达时距变化的情况

实验4. 探究DMR随高关键级功能数变化的情况.功能样本同样从样本空间取出.基于双关键级系统，系统总的功能数固定为50，高关键级功能数的变化范围是0～50，并以10递增.系统总的到达时距固定为0.高关键级功能数的多少反映了系统的实时需求情况.通过对本文所提出的3种算法(F_DDHEFT,C_DDHEFT,D_DDHEFT)进行实验并比较相应结果.

图9所示为采用3种算法的DMR随高关键级功能数变化的情况.F_DDHEFT仍然表现最差，C_DDHEFT表现最好,D_DDHEFT与C_DDHEFT较为接近.在高关键级功能数为50的时候，3种算法的表现差距很小.这是因为此时不存在低关键级功能，而C_DDHEFT和D_DDHEFT只能通过EDF来满足少量高关键级功能的实时性.

Fig. 9　DMR for varying numbers of functionalities.图9　DMR随高关键级功能数目变化

Fig. 10　DMR and WCRT for varying deadline spans.图10　DMR，WCRT随功能到达时距变化

实验5. 汽车电子系统是典型的异构分布式嵌入式系统.我们基于实际汽车电子环境，探讨端到端的响应时间与DMR随到达时距变化的情况.系统使用的功能为线控刹车功能和安全气囊功能.线控刹车功能为高关键级功能，它包括10个优先级约束的任务.安全气囊为低关键级功能，它包括8个优先级约束的任务.这2个功能共享5个ECU.所有的ECU有不同的计算能力.实验环境下，到达时距的变化范围是0～40 ms并以10 ms的增量递增，到达功能数一共为10个，高关键级功能与低关键级功能各占一半.图10所示为采用3种算法的DMR和WCRT随到达时距的变化情况.可以发现实际环境下的实验结果与随机样本结果的整体趋势一样.在满足实时性上，F_DDHEFT仍然表现最差，C_DDHEFT表现最好,D_DDHEFT与C_DDHEFT较为接近.在总体性能上，F_DDHEFT仍然表现最好，C_DDHEFT表现最差,D_DDHEFT与F_DDHEFT较为接近.再次验证了D_DDHEFT在整体性能和实时性上的合理权衡.

5结论

本文面向异构分布式嵌入式系统，开展双关键级分布式功能的动态任务调度研究.以多DAG双关键级动态模型为基础，从“功能级”以及“并行与分布式计算”的角度，通过分析现有公平调度和混合关键级调度的研究进展，提出了面向不同目标的动态任务调度算法.包括以提高系统性能为目标的公平策略算法F_DDHEFT，以满足更多高关键级功能实时性的关键级策略算法C_DDHEFT，和在满足更多高关键级功能实时性的基础上提高系统性能的时限时距策略算法D_DDHEFT，使得在系统整体性能和高关键级功能实时之间能够达到一种合理的权衡.最后通过实验将本文提出的3种算法进行全方位比较，实验结果验证了本文所提出的D_DDHEFT算法在满足更多高关键级功能实时性的条件下，能够有效地提高系统整体性能，且在汽车电子系统这一典型的异构分布式嵌入式系统中也有较好表现.

参考文献

[1]Xie Guoqi, Li Renfa, Yang Fan, et al. Multiple-DAG off-line task scheduling for heterogeneous networked automobile electronic system[J]. Journal on Communications, 2013, 34(12): 20-32 (in Chinese)(谢国琪, 李仁发, 杨帆, 等. 异构网络化汽车电子系统中多DAG离线任务调度[J]. 通信学报, 2013, 34(12): 20-32)

[2]Xie Guoqi, Li Renfa, Liu Lin, et al. DAG Reliability model and fault-tolerant algorithm for heterogeneous distributed system[J]. Chinese Journal of Computers, 2013, 36(10): 2019-2032 (in Chinese)(谢国琪, 李仁发, 刘琳, 等. 异构分布式系统DAG可靠性模型与容错算法[J]. 计算机学报, 2013, 36(10): 2019-2032)

[3] Seo S H, Kim J H, Hwang S H, et al. A reliable gateway for in-vehicle networks based on lin, can, and flexray[J]. ACM Trans on Embedded Computing Systems, 2012, 11(1): 1-24

[4]Buckl C, Camek A, Kainz G, et al. The software car: Building ICT architectures for future electric vehicles[C] //Proc of Electric Vehicle Conf. Piscataway, NJ: IEEE, 2012: 1-8

[5]Fürst S. Challenges in the design of automotive software[C] //Proc of the Conf on Design, Automation and Test in Europe. Piscataway, NJ: IEEE, 2010: 256-258

[6]Kelly O R, Aydin H, Zhao B. On partitioned scheduling of fixed-priority mixed-criticality task sets[C] //Proc of the 10th IEEE Int Conf on Trust, Security and Privacy in Computing and Communications. Piscataway, NJ: IEEE, 2011: 1051-1059

[7]Sinha P. Architectural design and reliability analysis of a fail-operational brake-by-wire system from ISO 26262 perspectives[J]. Reliability Engineering & System Safety, 2011, 96(10): 1349-1359

[8]Vestal S. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[C] //Proc of IEEE Real-Time Systems Symp (RTSS 2007). Piscataway, NJ: IEEE, 2007: 239-243

[9]De Niz D, Lakshmanan K, Rajkumar R. On the scheduling of mixed-criticality real-time task sets[C] //Proc of IEEE Real-Time Systems Symp (RTSS 2009). Piscataway, NJ: IEEE, 2009: 291-300

[10]Lakshmanan K, De Niz D, Rajkumar R. Mixed-criticality task synchronization in zero-slack scheduling[C] //Proc of IEEE Real-Time and Embedded Technology and Applications Symp. Piscataway, NJ: IEEE, 2011: 47-56

[11]Baruah S, Vestal S. Schedulability analysis of sporadic tasks with multiple criticality specifications[C] //Proc of Euromicro Conf on Real-Time Systems. Piscataway, NJ: IEEE, 2008: 147-155

[12]Petters S M, Lawitzky M, Heffernan R, et al. Towards real multi-criticality scheduling[C] //Proc of IEEE Int Conf on Embedded and Real-Time Computing Systems and Applications. Piscataway, NJ: IEEE, 2009: 155-164

[13]Dorin F, Richard P, Richard M, et al. Schedulability and sensitivity analysis of multiple criticality tasks with fixed-priorities[J]. Real-Time Systems, 2010, 46(3): 305-331

[14]Li H, Baruah S. An algorithm for scheduling certifiable mixed-criticality sporadic task systems[C] //Proc of IEEE Real-Time Systems Symp (RTSS 2010). Piscataway, NJ: IEEE, 2010: 183-192

[15]Zeller M, Prehofer C, Weiss G, et al. Towards self-adaptation in real-time, networked systems: Efficient solving of system constraints for automotive embedded systems[C] //Proc of Int Conf Self-Adaptive and Self-Organizing Systems. Piscataway, NJ: IEEE, 2010: 79-88

[16]Katoen J P, Noll T, Wu H, et al. Model-based energy optimization of automotive control systems[C] //Proc of the Conf on Design, Automation and Test in Europe. Piscataway, NJ: IEEE, 2013: 761-766

[17]Heinrich P, Prehofer C. Network-wide energy optimization for adaptive embedded systems[J]. ACM SIGBED Review, 2013, 10(1): 33-36

[18]Topcuoglu H, Hariri S, Wu M. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Trans on Parallel and Distributed Systems, 2002, 13(3): 260-274

[19]Xie G, Li R, Xiao X, et al. A high-performance dag task scheduling algorithm for heterogeneous networked embedded systems[C] //Proc of IEEE Int Conf on Advanced Information Networking and Applications. Piscataway, NJ: IEEE, 2014: 1011-1016

[20]Hönig U, Schiffmann W. A meta-algorithm for scheduling multiple DAGs in homogeneous system environments[C] //Proc of the Parallel and Distributed Computing and Systems. Piscataway, NJ: IEEE, 2006: 147-152

[21]Zhao Henan, Sakellariou R. Scheduling multiple DAGs onto heterogeneous systems[C] //Proc of the IEEE Int Conf on Parallel and Distributed Processing Symp. Piscataway, NJ: IEEE, 2006: 189-194

[22]Yu Z F, Shi W S. A planner-guided scheduling strategy for multiple workflow applications[C] //Proc of the Int Parallel Processing Workshops. Piscataway, NJ: IEEE, 2008: 1-8

[23]Hsu C C, Huang K C, Wang F J. On line scheduling of workflow applications in grid environments[J]. Future Generation Computer Systems, 2011, 27(6): 860-870

[24]Arabnejad H, Barbosa J. Fairness resource sharing for dynamic workflow scheduling on heterogeneous systems[C] //Proc of the 10th IEEE Int Symp on Parallel and Distributed Processing with Applications. Piscataway, NJ: IEEE, 2012: 633-639

[25]Anderson J, Baruah S, Brandenburg B. Multicore operating-system support for mixed criticality[C] //Proc of the Workshop on Mixed Criticality: Roadmap to Evolving UAV Certification. Piscataway, NJ: IEEE, 2009: 1-11

[26]Mollison M S, Erickso J P, Anderson J H, et al. Mixed-criticality real-time scheduling for multicore systems[C] //Proc of IEEE Int Conf on Computer and Information Technology. Piscataway, NJ: IEEE, 2010: 1864-1871

[27]Tamas-Selicean D, Pop P. Optimization of time-partitions for mixed-criticality real-time distributed embedded systems[C] //Proc of Object/Component/Service-Oriented Real-Time Distributed Computing Workshops(ISORCW). Piscataway, NJ: IEEE, 2011: 1-10

[28]Tamas-Selicean D, Pop P. Design optimization of mixed-criticality real-time applications on cost-constrained partitioned architectures[C] //Proc of IEEE Real-Time Systems Symp (RTSS 2011). Piscataway, NJ: IEEE, 2011: 24-33

[29]Tamas-Selicean D, Marinescu S, Pop P. Analysis and optimization of mixed-criticality applications on partitioned distributed architectures[C] //Proc of System Safety, incorporating the Cyber Security Conf. Piscataway, NJ: IEEE, 2012: 1-6

[30]Tamas-Selicean D, Pop P. Optimization of partitioned architectures to support soft real-time applications[C] //Proc of the 20th IEEE Pacific Rim Int Symp on Dependable Computing(PRDC 2014). Piscataway, NJ: IEEE, 2014: 24-33

[31]Kang W, Son S H, Stankovic J A, et al. I/O-aware deadline miss ratio management in real-time embedded databases[C] //Proc of IEEE Real-Time Systems Symp (RTSS 2007). Piscataway, NJ: IEEE, 2007: 277-287

Liu Liangjiao, born in 1984. PhD candidate. Student member of China Computer Federation. His main research interests include embedded computing, distributed computing, and automobile electronic systems.

Xie Guoqi, born in 1983. PhD, assistant professor. Member of China Computer Federation. His main research interests include embedded systems, distributed systems, real-time systems, in-vehicle networks, and cyber-physical systems.

Li Renfa, born in 1957. Professor, PhD, and PhD supervisor. Distinguished member of China Computer Federation. His main research interests include embedded computing, distributed computing, automobile electronic systems, and cyber-physical systems(CPS).

Yang Liu, born in 1983. PhD. His main research interests include embedded computing, cloud computing, and software engineering.

Liu Yan, born in 1979. PhD, assistant professor. Member of China Computer Federation. His main research interests include computer architecture, multicore scheduling, distributed computing systems.

Dynamic Scheduling of Dual-Criticality Distributed Functionalities on Heterogeneous Systems

Liu Liangjiao1,2, Xie Guoqi1,2, Li Renfa1,2, Yang Liu3, and Liu Yan1,2

1(CollegeofComputerScienceandElectronicEngineering,HunanUniversity,Changsha410082)2(KeyLaboratoryforEmbeddedandNetworkComputingofHunanProvince(HunanUniversity),Changsha410082)3(DevelopmentandReformCommissionofHunanProvince,Changsha410004)

AbstractHeterogeneous distributed systems are mixed-criticality systems consisting of multiple functionalities with different criticality levels. A distributed functionality contains multiple precedence-constrained tasks. Mixed-criticality scheduling of heterogeneous distributed systems faces severe conflicts between performance and time constraints. Improving the overall performance of systems while still meeting the deadlines of higher-criticality functionalities, and making a reasonable tradeoff between performance and timing are major optimization problems. The F_DDHEFT(fairness of dynamic dual-criticality heterogeneous earliest finish time) algorithm is to improve the performance of systems. The C_DDHEFT (criticality of dynamic dual-criticality heterogeneous earliest finish time) algorithm is to meet the deadlines of higher-criticality functionalities. The D_DDHEFT (deadline-span of dynamic dual-criticality heterogeneous earliest finish time) algorithm is to allow the lower-criticality functionalities to be processed positively for better overall performance while still meeting the deadlines of higher-criticality functionalities, such that a reasonable tradeoff between performance and timing is made. Both example and extensive experimental evaluation demonstrate significant improvement of the D_DDHEFT algorithm.

Key wordsheterogeneous distributed embedded systems; dual-criticality; performance; real-time; deadline-span

收稿日期：2015-02-27；修回日期：2015-09-06

基金项目：国家自然科学基金项目(61173036,61202102,61300039,61300037,61402170);国家“八六三”高技术研究发展计划基金项目(2012AA01A301-01);中国博士后科学基金项目(2016M592422)

通信作者：谢国琪(xgqman@hnu.edu.cn)

中图法分类号TP316

This work was supported by the National Natural Science Foundation of China (61173036,61202102,61300039,61300037,61402170) and the National High Technology Research and Development Program of China (863 Program) (2012AA01A301-01), and the China Postdoctoral Science Foundation (2016M592422).