HLA/RTI下周期与非周期任务调度的实时性改进

刘述田 戴树岭

(北京航空航天大学 虚拟现实技术与系统国家重点实验室，北京100191)

张亚琳

(中国航空无线电电子研究所，上海200241)

高层体系结构(HLA，High Level Architecture)作为分布式仿真的IEEE标准，已经被大量的军用和民用系统所采用，至今已经发展到IEEE 1516-2010［1］.实时系统是一类其正确性不仅依赖于逻辑计算结果，而且依赖于得到这些结果的时间的系统.有很多学者尝试把 HLA/RTI(Run-Time Infrastructure)与实时性结合起来研究，因为在实际应用中有很多情形需要在实时分布式仿真系统中按照HLA规则开发RTI.然而HLA并没有把实时性作为一项要求放在规则当中，按照其开发的系统并不能满足实时性要求.

研究者主要在以下4个方面提出研究方法对RTI的实时性加以改进:①把服务质量(QoS，Quality of Service)机制融合到HLA的规则当中，增强系统的可预测性［2］，QoS机制提供差异化服务，保证了网络应用能够根据需求占用带宽，为HLA/RTI通信提供了更大的灵活性以及更高效的资源利用率;②在实现RTI的本地节点上，文献［2－4］使用多线程及线程池提高任务队列的处理效率，使得系统能够同时处理多个任务队列并且降低了创建与销毁线程的系统开销，增强了系统的可预测性与扩展性;③使用了全局调度、可抢占调度等调度策略，使得系统能够及时处理最紧迫的任务，避免任务错过截止时间［3－4］，文献［5］提出以图论的方法研究优先顺序限制条件下的任务调度问题;④文献［6－7］提出了专用通信协议以提高HLA的实时性能，但是成本较高，没有被广泛采用.

系统的实时性就是要求系统能够对任意的任务具有可以预测的响应，亦即系统能够在有限的时间内对任务请求完成响应并运行.上述方法使得HLA/RTI应用能够更好地利用系统资源，在联邦成员数量增长时有更好的扩展性，以及更好的RTI服务反应能力，这些都显著增强了RTI的实时性.但是这些方法在通信协议、操作系统层次考虑实时性问题，而没有在联邦成员这一层面考虑如何进行任务调度.多数文献虽然提出了不少方法增强实时性，但是却没有对调度策略的可行性进行分析与证明［2－5］，其调度策略因而比较缺少说服力.周期性任务的时间属性在运行前就已明确，这样在指定的时间点所有的时间限制条件都容易满足，因而是易于预测的［8］;但是非周期任务在未开始时并不能确定该任务到达的时间，因此非周期任务给系统实时性带来较大的不确定性，调度非周期任务的运行也相对较难，然而其却在较大程度上影响了对系统实时性的判断.本文将从在联邦成员内部任务调度这一角度入手，进行周期与非周期任务的综合实时调度，讨论如何增强HLA/RTI的实时性，提出任务调度策略以及对这些策略进行调度可行性分析.

1 HLA/RTI通信模型

RTI作为仿真系统架构的中间件，必须能够为系统中的仿真节点即联邦成员提供统一的标准，使得它们能够互相通信、互操作以确保行为保持一致.依据HLA的规则，联邦成员间的通信必须通过RTI来实现，RTI是HLA的核心.如图1所示，所有的联邦成员交换信息都必须经过RTI，联邦成员和RTI组成一个不受限制的、可扩充的分布式仿真系统.

图1 HLA/RTI通信模型［3］

联邦成员在每个仿真循环中每隔一个时间间隔通过RTI服务，如sendInteractions()等向其他联邦成员发送信息，如图2所示.

图2 联邦成员任务间优先顺序约束

现实世界中，使用数据的任务只能在产生该数据的任务完成之后发生，这种数据约束关系称为优先顺序约束.每个联邦成员接收与发送数据以与其他联邦成员进行交互，这些数据是由周期性或非周期性任务产生的，联邦成员处理任务的实时性主要体现在如何处理这些具有优先顺序约束的周期性与非周期性任务.

2 周期任务调度及可行性分析

2.1 任务约束关系定义

实时系统中，通常对一系列周期性任务进行抽象，为每个任务实例分配优先权，在运行时根据优先权进行调度.周期性任务集合S中的一个任务Ti可以用一个四元组进行描述［9］:

任务Ti每隔周期 Pi释放一个实例 Ti［k］，k∈N;Ei表示任务Ti的最差情形下的执行时间;ri［k］表示任务实例 Ti［k］的释放时间;di［k］表示任务实例Ti［k］的截止时间，如图3所示.

图3 周期性任务符号定义

定义1 如果一个调度策略使得任务集合能够满足所有时间限制条件而执行完毕，则称这个调度策略是可行的，该任务集合是可调度的.

定义2 设S为一个任务集合，Ti，Tj∈S，如果必须在Ti执行完毕后才能开始执行Tj，则称Ti优先于Tj，表示为Ti≻Tj，其中符号≻定义为关系“优先于”.

定义3 设S为一个周期性任务集合，Ti，Tj∈S，Pi和 Pj分别是 Ti和 Tj的周期，Mij⊆N2，对于∀(m，n)∈Mij，若有 Ti［m］≻Tj［n］，则称Ti≻Tj为扩展优先顺序约束.若 m=n且 Pi=Pj，则称Ti≻Tj为简单优先顺序约束.

这个关系描述了无限个任务实例的约束关系，注意到S是一个周期性任务集合，可以用循环的形式来描述任务实例的约束关系.对于∀m，n∈N，用lmn表示m和n的最小公倍数，用Γn表示区间［0，n］内的整数的集合.

定义4 设S为一个周期性任务集合，Ti，Tj∈ S ，Pi和 Pj分别是 Ti和 Tj的周期，p=lPiPj，对于，若∃q∈N，使得

则称Tj≻Ti为周期性扩展优先顺序约束.

这个定义可用图4详细解释，其中给出了几种不同周期的任务可能的优先顺序约束关系.

图4 周期性扩展优先顺序约束关系［10］

例 如，图 4a 有 Mij={(0，0)}，Ti［0］≻Tj［0］，Ti［1］≻ Tj［3］，Ti［2］≻ Tj［6］，…;图4c 有Mij={(0，0)}，Ti［0］≻ Tj［0］，Ti［3］≻ Tj［1］，Ti［6］≻ Tj［2］，…;图4d 有Mij={(0，0)，(2，1)，(3，2)}，Ti［0］≻ Tj［0］，Ti［2］≻ Tj［1］，Ti［3］≻ Tj［2］，Ti［5］≻Tj［3］，Ti［7］≻ Tj［4］，Ti［8］≻ Tj［5］，….

2.2 任务调度方法与分析

多数分布交互式仿真系统，以时间步进(time-stepped)的模式［11］进行时间推进，绝大部分任务都是时间驱动的周期性任务.任务与任务之间的同步关系体现在传入传出数据队列的处理方式上.为了增强RTI的实时性，加快对联邦成员间的信息处理速度，逐渐放弃了早期RTI的阻塞式处理方式，而采用了非阻塞式［12］.非阻塞式处理方式虽然加快了信息处理速度，但是也增加了对数据处理的不确定性，进而可能严重影响系统处理任务的效率.如图4c所示，任务2的周期是任务1的周期的3倍，在通常情形下，任务1在任务2的一个周期内发送3个数据，处理器接收到数据就会唤醒一个任务来处理这个数据，这样就会造成任务多执行了2次，使系统做了重复的工作，造成效率的降低，在频率差别更大的情形下效率下降得更明显.如果按照定义3的方式来定义任务之间的约束关系，由图4可以发现，不管传入的信息周期与本联邦成员长短关系如何，每个周期都至多只执行一次处理信息的任务，这样就提高了系统的效率.

考虑每一个任务的信息约束队列，见图5，其长度与任务周期有如下关系:

图5 信息队列与任务队列

单处理器的多个周期性任务的调度策略已经有非常成熟的算法，文献［13］证明了动态优先权调度策略，如最早截止时间优先(EDF，Earliest Deadline First)算法能够获得最高100%的CPU利用率，并且该算法是最优的.在RTI环境下，单处理器下任务间的约束关系转化为联邦成员间任务间的优先顺序约束关系和时间约束关系.以任务的角度来看，传入的信息和发送的信息可以视为不同联邦成员的任务之间约束信号，该信号唤醒了任务实例进而执行.

每个联邦成员的任务队列处理如图5所示，在任务处理过程中，比较任务就绪队列中每个任务的截止时间，最小的截止时间任务获得最高的优先权，优先运行.

根据文献［13］，可得定理1.

定理1 设S为一个周期性任务集合{Ti|1≤i≤n，n∈N}，Ei是任务Ti的最差情形下的计算时间，Pi是任务Ti运行周期.如果S是可调度的，当且仅当

引理1 设S为一个周期性任务集合{Ti|1≤i≤n，n∈N}，Ei是任务Ti的最差情形下的时间，Δt是步进式联邦成员的运行步长.如果S在步进式联邦成员上按照本节前述的调度方式是可调度的，当且仅当

必要性.若S是可调度的，由步进式联邦任务(如图5)及本节前述的调度方式，每个任务在一个步长内至多只执行一次，按照最多情形计算，有Pi=Δt，由定理1，若S是可调度的，则有

如果Pi＞Δt，按照上述EDF算法，在某些步长时间内联邦成员有更多的空闲计算时间，式(6)必然成立.证毕

这说明，若一个周期性任务集合在整个时间轴上按照上述调度方式是可调度的，则该任务集合每一个任务的实例在步长Δt内必须是可调度的.

若要确保任务的可预测性，一是要确定每个周期处理传入信息队列的某个特定数据.根据定义3，只要确定了Mij，那么就可以按照这个选择方式进行处理.二是要确定该数据在队列中的等待时间.任意一个任务实例Ti的最长响应时间可以表示为

式中，ti为任务Ti的最长响应时间;Ei，Ej分别为任务Ti，Tj的最长计算时间;Pj为任务Tj的周期;h(i)为同一任务队列优先权比任务Ti高的任务集合.

根据引理1，若ti大于本联邦成员的步长Δt，就说明本联邦成员不能处理完毕所有的任务，系统处理能力不足，则数据队列随着时间的推进不断地增长，达不到实时的性能要求.另一个侧面也说明，在这种情形下任何一种任务调度策略都是不可行的，因为EDF算法是最优的［13］.

3 D-EDF算法及分析

交互的任务属于典型的非周期任务，这种类型的任务由于人在回路中，其实时性要求往往较强，要求事件必须在截止时间前得到响应，否则系统则会给人以严重失真的感觉，甚至会因此做出错误判断.

非周期任务集合Q的一个任务Ji可以用一个三元组来描述［14］:

式中，任务 Ji在绝对时刻 Ai［k］到达一个实例Ji［k］，k∈N;Ei为任务Ji的最差情形下的执行时间;di［k］为任务实例Ji［k］的绝对截止时间.这些定义与周期任务相似，可以参考图3.

周期任务与非周期任务的混合任务的调度算法通常采用“服务器”调度策略［15－16］.这种策略把非周期性任务当作周期性任务处理，加快对非周期任务的响应速度.

时间步进式联邦的特点是，所有的任务实例要么在一个周期内完成，要么在下一个周期内完成，不能跨越2 个周期.以 si［k］表示实例 Ji［k］的开始执行时间，fi［k］表示实例Ji［k］的执行完成时间，若Ji［k］在第m个周期内完成，则有

根据周期性任务在每一个周期的运行情况，事先确定每个周期内非周期任务可以占用的最大比率UA，故第m个周期可以调度的非周期任务集合F(m)必须满足如下条件:

则可以保证第m个周期可以调度的任务满足式(8)，若要同时满足式(9)，则必须对F(m)使用EDF调度算法.

上述采用2次EDF调度算法的策略，命名为D-EDF(Double-EDF)算法.

定理2 给定一个周期性任务集合S={Ti|1≤i≤n，n∈N}处理器利用率为UP，以及一个非周期性任务集合Q={Ji|1≤i≤m，m∈N}处理器利用率为UA，如果整个任务集合是DEDF可调度的，当且仅当

证明 D-EDF按照第2节的策略产生一个唯一的调度任务列表X，并且X是周期性的，其处理器利用率U=UP+UA，即若X是可行的，当且仅当U≤1.注意到定理1，则可证明U≤1，即UP+UA≤1.证毕

4 结 束 语

将任务调度策略应用到RTI中，在联邦成员这一层次上综合调度周期与非周期任务的运行，提高了RTI的实时性，使得HLA可以应用到实时系统中，提高开发效率.具有优先顺序约束的任务调度的可预测性在很大程度上依赖于数据传输的确定性，即确定了发送数据的长度与时间就可以确定收到数据的长度与时间.但是由于分布式应用环境的特殊性，网络通信有很多不确定性，网络环境需要能够保证通信延迟的上限或者能够提供QoS通信，以调度远端进程满足任务的截止时间，减少或者消除任务调度的抖动.任务调度也要考虑通信延迟的不确定性，在提高任务调度的可预测性的同时也要减少数据顺序不一致带来的不确定性，这些都是以后可以研究的内容.

References)

［1］IEEE 1516-2010 Standard for modeling and simulation(M＆S)high level architecture(HLA):framework and rules［S］

［2］Zhao Hui，Georganas N D.HLA real-time extension［C］//Distributed Simulation and Real-Time Applications，Fifth IEEE International Workshop on，DS-RT 2001.Cincinnati:IEEE，2001:12－21

［3］Guan Li，Zou Ruping，Zhu Bin.An HLA/RTI architecture based on multi-thread processing［J］.Jornal of China Ordance，2010，6(3):182－188

［4］Boukerche A，Lu K.A novel approach to real-time RTI based distributed simulation system［C］//38th Proceedings of Simulation Symposium Proceeding ANSS’05.Washington DC:IEEE Computer Society，2005:267 －274

［5］Adelantado M，Siron P.Towards an HLA run-time infrastructure with hard real-time capabilities［C］//International Simulation Multi-Conference.Ottava:Pierre Siron，2010:12 －14

［6］Mike D B，Zyda M，Watsen K，et al.Virtual reality transfer protocol(vrtp)design rationale［C］//Proc of the Sixth IEEE International Workshop on Enabling Technologies.MIT:IEEE Computer Society Press，1997:18 －20

［7］Zhao Hui.HLA streaming and real-time extensions［D］.Ottawa:University of Ottawa，2002

［8］Tang H.Combining hard periodic and soft aperiodic real-time task scheduling on heterogeneous compute resources［C］//2011 International Conference on Parallel Processing(ICPP).Taipei:IEEE，2011:753 －762

［9］Buttazzo G C.Periodic task scheduling［M］.New York:Springer，2011:9 －118

［10］Forget J，Boniol F，Grolleau E.Scheduling dependent periodic tasks without synchronization mechanisms［C］//16th IEEE Real-Time and Embedded Technology and Applications Symposium.Stockholm:IEEE，2010:301 －310

［11］Mclean T，Fujimoto R，Fitzgibbons B.Middleware for real-time distributed simulations［J］.Concurrency and Computation:Practice＆Experience-Distributed Simulation and Real-Time Applications，2004，16(15):1483 －1501

［12］Fujimoto R，Mclean T，Perumalla K，et al.Design of high performance RTI software［C］//Fourth IEEE International Workshop on Distributed Simulation and Real-Time Applications.San Francisco:IEEE，2000:89 －96

［13］Liu C L，Layland J W.Scheduling algorithms for multiprogramming in hard real-time environments［J］.Journal of the ACM，1973，20(1):46 －61

［14］Buttazzo G C.Aperiodic task scheduling［M］.New York:Springer，2011:53 － 78

［15］Spuri M，Buttazzo G C.Scheduling aperiodic tasks in dynamic priority systems ［J］.Real-Time Systems，1995，10(2):179－210

［16］Marchand A，Silly-Chetto M.Dynamic real-time scheduling of firm periodic tasks with hard and soft aperiodic tasks［J］.Real-Time Systems，2006，32(1):21 －47