劉述田 戴樹嶺

(北京航空航天大學 虛擬現(xiàn)實技術與系統(tǒng)國家重點實驗室，北京100191)

張亞琳

(中國航空無線電電子研究所，上海200241)

高層體系結構(HLA，High Level Architecture)作為分布式仿真的IEEE標準，已經(jīng)被大量的軍用和民用系統(tǒng)所采用，至今已經(jīng)發(fā)展到IEEE 1516-2010［1］.實時系統(tǒng)是一類其正確性不僅依賴于邏輯計算結果，而且依賴于得到這些結果的時間的系統(tǒng).有很多學者嘗試把 HLA/RTI(Run-Time Infrastructure)與實時性結合起來研究，因為在實際應用中有很多情形需要在實時分布式仿真系統(tǒng)中按照HLA規(guī)則開發(fā)RTI.然而HLA并沒有把實時性作為一項要求放在規(guī)則當中，按照其開發(fā)的系統(tǒng)并不能滿足實時性要求.

研究者主要在以下4個方面提出研究方法對RTI的實時性加以改進:①把服務質量(QoS，Quality of Service)機制融合到HLA的規(guī)則當中，增強系統(tǒng)的可預測性［2］，QoS機制提供差異化服務，保證了網(wǎng)絡應用能夠根據(jù)需求占用帶寬，為HLA/RTI通信提供了更大的靈活性以及更高效的資源利用率;②在實現(xiàn)RTI的本地節(jié)點上，文獻［2－4］使用多線程及線程池提高任務隊列的處理效率，使得系統(tǒng)能夠同時處理多個任務隊列并且降低了創(chuàng)建與銷毀線程的系統(tǒng)開銷，增強了系統(tǒng)的可預測性與擴展性;③使用了全局調度、可搶占調度等調度策略，使得系統(tǒng)能夠及時處理最緊迫的任務，避免任務錯過截止時間［3－4］，文獻［5］提出以圖論的方法研究優(yōu)先順序限制條件下的任務調度問題;④文獻［6－7］提出了專用通信協(xié)議以提高HLA的實時性能，但是成本較高，沒有被廣泛采用.

系統(tǒng)的實時性就是要求系統(tǒng)能夠對任意的任務具有可以預測的響應，亦即系統(tǒng)能夠在有限的時間內(nèi)對任務請求完成響應并運行.上述方法使得HLA/RTI應用能夠更好地利用系統(tǒng)資源，在聯(lián)邦成員數(shù)量增長時有更好的擴展性，以及更好的RTI服務反應能力，這些都顯著增強了RTI的實時性.但是這些方法在通信協(xié)議、操作系統(tǒng)層次考慮實時性問題，而沒有在聯(lián)邦成員這一層面考慮如何進行任務調度.多數(shù)文獻雖然提出了不少方法增強實時性，但是卻沒有對調度策略的可行性進行分析與證明［2－5］，其調度策略因而比較缺少說服力.周期性任務的時間屬性在運行前就已明確，這樣在指定的時間點所有的時間限制條件都容易滿足，因而是易于預測的［8］;但是非周期任務在未開始時并不能確定該任務到達的時間，因此非周期任務給系統(tǒng)實時性帶來較大的不確定性，調度非周期任務的運行也相對較難，然而其卻在較大程度上影響了對系統(tǒng)實時性的判斷.本文將從在聯(lián)邦成員內(nèi)部任務調度這一角度入手，進行周期與非周期任務的綜合實時調度，討論如何增強HLA/RTI的實時性，提出任務調度策略以及對這些策略進行調度可行性分析.

1 HLA/RTI通信模型

RTI作為仿真系統(tǒng)架構的中間件，必須能夠為系統(tǒng)中的仿真節(jié)點即聯(lián)邦成員提供統(tǒng)一的標準，使得它們能夠互相通信、互操作以確保行為保持一致.依據(jù)HLA的規(guī)則，聯(lián)邦成員間的通信必須通過RTI來實現(xiàn)，RTI是HLA的核心.如圖1所示，所有的聯(lián)邦成員交換信息都必須經(jīng)過RTI，聯(lián)邦成員和RTI組成一個不受限制的、可擴充的分布式仿真系統(tǒng).

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

聯(lián)邦成員在每個仿真循環(huán)中每隔一個時間間隔通過RTI服務，如sendInteractions()等向其他聯(lián)邦成員發(fā)送信息，如圖2所示.

圖2 聯(lián)邦成員任務間優(yōu)先順序約束

現(xiàn)實世界中，使用數(shù)據(jù)的任務只能在產(chǎn)生該數(shù)據(jù)的任務完成之后發(fā)生，這種數(shù)據(jù)約束關系稱為優(yōu)先順序約束.每個聯(lián)邦成員接收與發(fā)送數(shù)據(jù)以與其他聯(lián)邦成員進行交互，這些數(shù)據(jù)是由周期性或非周期性任務產(chǎn)生的，聯(lián)邦成員處理任務的實時性主要體現(xiàn)在如何處理這些具有優(yōu)先順序約束的周期性與非周期性任務.

2 周期任務調度及可行性分析

2.1 任務約束關系定義

實時系統(tǒng)中，通常對一系列周期性任務進行抽象，為每個任務實例分配優(yōu)先權，在運行時根據(jù)優(yōu)先權進行調度.周期性任務集合S中的一個任務Ti可以用一個四元組進行描述［9］:

任務Ti每隔周期 Pi釋放一個實例 Ti［k］，k∈N;Ei表示任務Ti的最差情形下的執(zhí)行時間;ri［k］表示任務實例 Ti［k］的釋放時間;di［k］表示任務實例Ti［k］的截止時間，如圖3所示.

圖3 周期性任務符號定義

定義1 如果一個調度策略使得任務集合能夠滿足所有時間限制條件而執(zhí)行完畢，則稱這個調度策略是可行的，該任務集合是可調度的.

定義2 設S為一個任務集合，Ti，Tj∈S，如果必須在Ti執(zhí)行完畢后才能開始執(zhí)行Tj，則稱Ti優(yōu)先于Tj，表示為Ti?Tj，其中符號?定義為關系“優(yōu)先于”.

定義3 設S為一個周期性任務集合，Ti，Tj∈S，Pi和 Pj分別是 Ti和 Tj的周期，Mij?N2，對于?(m，n)∈Mij，若有 Ti［m］?Tj［n］，則稱Ti?Tj為擴展優(yōu)先順序約束.若 m=n且 Pi=Pj，則稱Ti?Tj為簡單優(yōu)先順序約束.

這個關系描述了無限個任務實例的約束關系，注意到S是一個周期性任務集合，可以用循環(huán)的形式來描述任務實例的約束關系.對于?m，n∈N，用lmn表示m和n的最小公倍數(shù)，用Γn表示區(qū)間［0，n］內(nèi)的整數(shù)的集合.

定義4 設S為一個周期性任務集合，Ti，Tj∈ S ，Pi和 Pj分別是 Ti和 Tj的周期，p=lPiPj，對于，若?q∈N，使得

則稱Tj?Ti為周期性擴展優(yōu)先順序約束.

這個定義可用圖4詳細解釋，其中給出了幾種不同周期的任務可能的優(yōu)先順序約束關系.

圖4 周期性擴展優(yōu)先順序約束關系［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 任務調度方法與分析

多數(shù)分布交互式仿真系統(tǒng)，以時間步進(time-stepped)的模式［11］進行時間推進，絕大部分任務都是時間驅動的周期性任務.任務與任務之間的同步關系體現(xiàn)在傳入傳出數(shù)據(jù)隊列的處理方式上.為了增強RTI的實時性，加快對聯(lián)邦成員間的信息處理速度，逐漸放棄了早期RTI的阻塞式處理方式，而采用了非阻塞式［12］.非阻塞式處理方式雖然加快了信息處理速度，但是也增加了對數(shù)據(jù)處理的不確定性，進而可能嚴重影響系統(tǒng)處理任務的效率.如圖4c所示，任務2的周期是任務1的周期的3倍，在通常情形下，任務1在任務2的一個周期內(nèi)發(fā)送3個數(shù)據(jù)，處理器接收到數(shù)據(jù)就會喚醒一個任務來處理這個數(shù)據(jù)，這樣就會造成任務多執(zhí)行了2次，使系統(tǒng)做了重復的工作，造成效率的降低，在頻率差別更大的情形下效率下降得更明顯.如果按照定義3的方式來定義任務之間的約束關系，由圖4可以發(fā)現(xiàn)，不管傳入的信息周期與本聯(lián)邦成員長短關系如何，每個周期都至多只執(zhí)行一次處理信息的任務，這樣就提高了系統(tǒng)的效率.

考慮每一個任務的信息約束隊列，見圖5，其長度與任務周期有如下關系:

圖5 信息隊列與任務隊列

單處理器的多個周期性任務的調度策略已經(jīng)有非常成熟的算法，文獻［13］證明了動態(tài)優(yōu)先權調度策略，如最早截止時間優(yōu)先(EDF，Earliest Deadline First)算法能夠獲得最高100%的CPU利用率，并且該算法是最優(yōu)的.在RTI環(huán)境下，單處理器下任務間的約束關系轉化為聯(lián)邦成員間任務間的優(yōu)先順序約束關系和時間約束關系.以任務的角度來看，傳入的信息和發(fā)送的信息可以視為不同聯(lián)邦成員的任務之間約束信號，該信號喚醒了任務實例進而執(zhí)行.

每個聯(lián)邦成員的任務隊列處理如圖5所示，在任務處理過程中，比較任務就緒隊列中每個任務的截止時間，最小的截止時間任務獲得最高的優(yōu)先權，優(yōu)先運行.

根據(jù)文獻［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是步進式聯(lián)邦成員的運行步長.如果S在步進式聯(lián)邦成員上按照本節(jié)前述的調度方式是可調度的，當且僅當

必要性.若S是可調度的，由步進式聯(lián)邦任務(如圖5)及本節(jié)前述的調度方式，每個任務在一個步長內(nèi)至多只執(zhí)行一次，按照最多情形計算，有Pi=Δt，由定理1，若S是可調度的，則有

如果Pi＞Δt，按照上述EDF算法，在某些步長時間內(nèi)聯(lián)邦成員有更多的空閑計算時間，式(6)必然成立.證畢

這說明，若一個周期性任務集合在整個時間軸上按照上述調度方式是可調度的，則該任務集合每一個任務的實例在步長Δt內(nèi)必須是可調度的.

若要確保任務的可預測性，一是要確定每個周期處理傳入信息隊列的某個特定數(shù)據(jù).根據(jù)定義3，只要確定了Mij，那么就可以按照這個選擇方式進行處理.二是要確定該數(shù)據(jù)在隊列中的等待時間.任意一個任務實例Ti的最長響應時間可以表示為

式中，ti為任務Ti的最長響應時間;Ei，Ej分別為任務Ti，Tj的最長計算時間;Pj為任務Tj的周期;h(i)為同一任務隊列優(yōu)先權比任務Ti高的任務集合.

根據(jù)引理1，若ti大于本聯(lián)邦成員的步長Δt，就說明本聯(lián)邦成員不能處理完畢所有的任務，系統(tǒng)處理能力不足，則數(shù)據(jù)隊列隨著時間的推進不斷地增長，達不到實時的性能要求.另一個側面也說明，在這種情形下任何一種任務調度策略都是不可行的，因為EDF算法是最優(yōu)的［13］.

3 D-EDF算法及分析

交互的任務屬于典型的非周期任務，這種類型的任務由于人在回路中，其實時性要求往往較強，要求事件必須在截止時間前得到響應，否則系統(tǒng)則會給人以嚴重失真的感覺，甚至會因此做出錯誤判斷.

非周期任務集合Q的一個任務Ji可以用一個三元組來描述［14］:

式中，任務 Ji在絕對時刻 Ai［k］到達一個實例Ji［k］，k∈N;Ei為任務Ji的最差情形下的執(zhí)行時間;di［k］為任務實例Ji［k］的絕對截止時間.這些定義與周期任務相似，可以參考圖3.

周期任務與非周期任務的混合任務的調度算法通常采用“服務器”調度策略［15－16］.這種策略把非周期性任務當作周期性任務處理，加快對非周期任務的響應速度.

時間步進式聯(lián)邦的特點是，所有的任務實例要么在一個周期內(nèi)完成，要么在下一個周期內(nèi)完成，不能跨越2 個周期.以 si［k］表示實例 Ji［k］的開始執(zhí)行時間，fi［k］表示實例Ji［k］的執(zhí)行完成時間，若Ji［k］在第m個周期內(nèi)完成，則有

根據(jù)周期性任務在每一個周期的運行情況，事先確定每個周期內(nèi)非周期任務可以占用的最大比率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節(jié)的策略產(chǎn)生一個唯一的調度任務列表X，并且X是周期性的，其處理器利用率U=UP+UA，即若X是可行的，當且僅當U≤1.注意到定理1，則可證明U≤1，即UP+UA≤1.證畢

4 結 束 語

將任務調度策略應用到RTI中，在聯(lián)邦成員這一層次上綜合調度周期與非周期任務的運行，提高了RTI的實時性，使得HLA可以應用到實時系統(tǒng)中，提高開發(fā)效率.具有優(yōu)先順序約束的任務調度的可預測性在很大程度上依賴于數(shù)據(jù)傳輸?shù)拇_定性，即確定了發(fā)送數(shù)據(jù)的長度與時間就可以確定收到數(shù)據(jù)的長度與時間.但是由于分布式應用環(huán)境的特殊性，網(wǎng)絡通信有很多不確定性，網(wǎng)絡環(huán)境需要能夠保證通信延遲的上限或者能夠提供QoS通信，以調度遠端進程滿足任務的截止時間，減少或者消除任務調度的抖動.任務調度也要考慮通信延遲的不確定性，在提高任務調度的可預測性的同時也要減少數(shù)據(jù)順序不一致帶來的不確定性，這些都是以后可以研究的內(nèi)容.

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，F(xiàn)ifth 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，F(xiàn)ujimoto R，F(xiàn)itzgibbons 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