劉述田 戴樹嶺

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

張亞琳

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

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

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

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

1 HLA/RTI通信模型

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

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

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

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

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

2 周期任務(wù)調(diào)度及可行性分析

2.1 任務(wù)約束關(guān)系定義

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

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

圖3 周期性任務(wù)符號(hào)定義

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

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

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

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

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

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

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

圖4 周期性擴(kuò)展優(yōu)先順序約束關(guān)系［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 任務(wù)調(diào)度方法與分析

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

考慮每一個(gè)任務(wù)的信息約束隊(duì)列，見圖5，其長度與任務(wù)周期有如下關(guān)系:

圖5 信息隊(duì)列與任務(wù)隊(duì)列

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

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

根據(jù)文獻(xiàn)［13］，可得定理1.

定理1 設(shè)S為一個(gè)周期性任務(wù)集合{Ti|1≤i≤n，n∈N}，Ei是任務(wù)Ti的最差情形下的計(jì)算時(shí)間，Pi是任務(wù)Ti運(yùn)行周期.如果S是可調(diào)度的，當(dāng)且僅當(dāng)

引理1 設(shè)S為一個(gè)周期性任務(wù)集合{Ti|1≤i≤n，n∈N}，Ei是任務(wù)Ti的最差情形下的時(shí)間，Δt是步進(jìn)式聯(lián)邦成員的運(yùn)行步長.如果S在步進(jìn)式聯(lián)邦成員上按照本節(jié)前述的調(diào)度方式是可調(diào)度的，當(dāng)且僅當(dāng)

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

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

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

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

式中，ti為任務(wù)Ti的最長響應(yīng)時(shí)間;Ei，Ej分別為任務(wù)Ti，Tj的最長計(jì)算時(shí)間;Pj為任務(wù)Tj的周期;h(i)為同一任務(wù)隊(duì)列優(yōu)先權(quán)比任務(wù)Ti高的任務(wù)集合.

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

3 D-EDF算法及分析

交互的任務(wù)屬于典型的非周期任務(wù)，這種類型的任務(wù)由于人在回路中，其實(shí)時(shí)性要求往往較強(qiáng)，要求事件必須在截止時(shí)間前得到響應(yīng)，否則系統(tǒng)則會(huì)給人以嚴(yán)重失真的感覺，甚至?xí)虼俗龀鲥e(cuò)誤判斷.

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

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

周期任務(wù)與非周期任務(wù)的混合任務(wù)的調(diào)度算法通常采用“服務(wù)器”調(diào)度策略［15－16］.這種策略把非周期性任務(wù)當(dāng)作周期性任務(wù)處理，加快對(duì)非周期任務(wù)的響應(yīng)速度.

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

根據(jù)周期性任務(wù)在每一個(gè)周期的運(yùn)行情況，事先確定每個(gè)周期內(nèi)非周期任務(wù)可以占用的最大比率UA，故第m個(gè)周期可以調(diào)度的非周期任務(wù)集合F(m)必須滿足如下條件:

則可以保證第m個(gè)周期可以調(diào)度的任務(wù)滿足式(8)，若要同時(shí)滿足式(9)，則必須對(duì)F(m)使用EDF調(diào)度算法.

上述采用2次EDF調(diào)度算法的策略，命名為D-EDF(Double-EDF)算法.

定理2 給定一個(gè)周期性任務(wù)集合S={Ti|1≤i≤n，n∈N}處理器利用率為UP，以及一個(gè)非周期性任務(wù)集合Q={Ji|1≤i≤m，m∈N}處理器利用率為UA，如果整個(gè)任務(wù)集合是DEDF可調(diào)度的，當(dāng)且僅當(dāng)

證明 D-EDF按照第2節(jié)的策略產(chǎn)生一個(gè)唯一的調(diào)度任務(wù)列表X，并且X是周期性的，其處理器利用率U=UP+UA，即若X是可行的，當(dāng)且僅當(dāng)U≤1.注意到定理1，則可證明U≤1，即UP+UA≤1.證畢

4 結(jié) 束 語

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