ARINC653分區(qū)操作系統(tǒng)多核處理器任務(wù)調(diào)度設(shè)計(jì)①

黎 明,莫 軍

(中電科航空電子有限公司,成都 611731)

1 引言

綜合模塊化航空電子系統(tǒng)被廣泛應(yīng)用于新一代民用客機(jī),如空客 A380、波音 787 等,相對(duì)傳統(tǒng)的航電系統(tǒng),采用IMA架構(gòu)的航電系統(tǒng)具備集成度高、維護(hù)方便以及設(shè)備重量減輕等優(yōu)勢(shì).

ARINC653規(guī)范[1]是美國(guó)航空電子工程委員會(huì)制定的適用于軟件的實(shí)時(shí)操作系統(tǒng)標(biāo)準(zhǔn),它定義了IMA架構(gòu)下的實(shí)時(shí)操作系統(tǒng)的行為邏輯和向應(yīng)用程序提供的接口規(guī)范.在該規(guī)范中實(shí)時(shí)操作系統(tǒng)將硬件資源劃分為時(shí)間和空間相互獨(dú)立的資源分區(qū),應(yīng)用程序加載于這些時(shí)空獨(dú)立的資源分區(qū)之上.分區(qū)是ARINC653 規(guī)范的一個(gè)核心概念,它實(shí)現(xiàn)了應(yīng)用程序的時(shí)空隔離.用戶實(shí)現(xiàn)的一個(gè)應(yīng)用程序是一組計(jì)算任務(wù)的集合,加載于一個(gè)資源分區(qū)之上.這些計(jì)算任務(wù)在分區(qū)內(nèi)進(jìn)行本地調(diào)度[2–4],與其他分區(qū)內(nèi)的任務(wù)調(diào)度相互獨(dú)立,若干個(gè)時(shí)間資源分區(qū)之間進(jìn)行分區(qū)間調(diào)度以共享處理器的計(jì)算時(shí)間資源.

隨著機(jī)載電子系統(tǒng)綜合化、模塊化的發(fā)展,分區(qū)操作系統(tǒng)成為航空計(jì)算機(jī)的主流操作系統(tǒng).宏內(nèi)核、微內(nèi)核曾被分區(qū)操作系統(tǒng)所采用,但單核處理器已經(jīng)達(dá)到性能瓶頸,很難滿足綜合化航空電子高性能計(jì)算要求,本文基于分區(qū)單核操作系統(tǒng)環(huán)境的任務(wù)調(diào)度,結(jié)合傳統(tǒng)多核操作系統(tǒng)的特點(diǎn),重點(diǎn)研究了機(jī)載綜合化航空電子多核處理分區(qū)操作系統(tǒng)的任務(wù)調(diào)度.

ARINC653規(guī)范指定單核處理器作為硬件平臺(tái),面對(duì)機(jī)載單核處理器系統(tǒng)任務(wù)調(diào)度有很多的學(xué)者做了大量深入的研究[5,6].隨著實(shí)時(shí)多核處理器技術(shù)的發(fā)展,多核處理器已經(jīng)逐步在航空電子系統(tǒng)中得到了廣泛的應(yīng)用,但是如何進(jìn)行任務(wù)分配和調(diào)度[7,8],滿足機(jī)載系統(tǒng)的實(shí)時(shí)性要求則成為一個(gè)關(guān)鍵問題,因此對(duì)符合ARINC653規(guī)范的,運(yùn)行在多核處理器上的實(shí)時(shí)調(diào)度方法的研究則成為航空電子系統(tǒng)領(lǐng)域的研究熱點(diǎn)[9–11].基于上述原因,本文提出一種基于多核的任務(wù)負(fù)載比例輪轉(zhuǎn)的調(diào)度方法 (Multi-kernel Load Proportional Round Robin,MLPRR),該方法采用基于任務(wù)負(fù)載比例算法生成多核處理器任務(wù)調(diào)度的任務(wù)就緒隊(duì)列,對(duì)任務(wù)就緒隊(duì)列采用輪轉(zhuǎn)調(diào)度的方式將各個(gè)任務(wù)分配到空閑的處理器核上,以任務(wù)的負(fù)載比例計(jì)算任務(wù)權(quán)值,完成任務(wù)在多核處理器上的調(diào)度,從而滿足多核分區(qū)操作系統(tǒng)的實(shí)時(shí)性要求.

2 實(shí)時(shí)調(diào)度模型

2.1 任務(wù)模型

多核處理器負(fù)載比例輪轉(zhuǎn)調(diào)度多任務(wù)多核處理器建模如下:

設(shè)子系統(tǒng)任務(wù)集為T={T1,T2,…,Tn},采用實(shí)時(shí)周期性任務(wù)模型,每個(gè)任務(wù)可表示為Ti=(Zi,Ci,Pi,Di).其中,Zi為任務(wù)的分區(qū)標(biāo)示,Ci為任務(wù)處理時(shí)間,Pi為任務(wù)處理周期,Di為任務(wù)最大允許延遲,一般設(shè)置

權(quán)值計(jì)算方法決定了對(duì)任務(wù)的權(quán)值分配,直接影響到算法的實(shí)時(shí)可調(diào)度性.本文采用基于負(fù)載比例的權(quán)值計(jì)算方法,具體計(jì)算方法為:

1)根據(jù)單個(gè)任務(wù)Ti在任務(wù)集T所占負(fù)載比例計(jì)算權(quán)值:

2)任務(wù)負(fù)載率:

3)總負(fù)載率為:

其中,Ci為第i個(gè)任務(wù)的處理時(shí)間,Pi為第i個(gè)任務(wù)的處理周期,Ui為第i個(gè)任務(wù)的任務(wù)負(fù)載率,U為系統(tǒng)中所有任務(wù)的任務(wù)負(fù)載率總和.

2.2 任務(wù)調(diào)度模型

針對(duì)上述任務(wù)模型,設(shè)計(jì)周期性分區(qū)任務(wù)在多核處理器上的任務(wù)調(diào)度模型如圖1所示.任務(wù)調(diào)度模型S={S1,S2,…,Sn},Si=(Ti,Ki),K={K1,K2,…,KM}.任務(wù)調(diào)度模型中,采用基于任務(wù)負(fù)載比例算法生成多核處理器任務(wù)調(diào)度的任務(wù)就緒隊(duì)列,對(duì)任務(wù)就緒隊(duì)列采用輪轉(zhuǎn)調(diào)度的方式將各個(gè)任務(wù)分配到空閑的處理器核上.

圖1 任務(wù)調(diào)度模型圖

2.3 實(shí)時(shí)輪轉(zhuǎn)調(diào)度約束

在多核處理器任務(wù)調(diào)度算法中,除了計(jì)算任務(wù)的權(quán)值Wi外,系統(tǒng)參數(shù)主要包括輪轉(zhuǎn)長(zhǎng)度TRL、處理器核的數(shù)目M.合理的參數(shù)設(shè)計(jì)對(duì)任務(wù)的可調(diào)度性有很大的影響[12].

要滿足實(shí)時(shí)需求,必須要求調(diào)度算法為任務(wù)Ti分配的權(quán)值Wi滿足兩個(gè)約束條件.

1) 輪轉(zhuǎn)處理時(shí)間約束

對(duì)于n個(gè)周期事件,事件i以周期Pi發(fā)生,事件需要Ci秒處理時(shí)間,需要滿足的條件是:

對(duì)于具有M個(gè)核的多核處理器,忽略處理器內(nèi)部消耗,需要滿足的條件是:

2) 輪轉(zhuǎn)調(diào)度權(quán)值約束

對(duì)于n個(gè)分區(qū)任務(wù)數(shù),需要滿足的條件是:

式中Wi為任務(wù)的權(quán)值,M為多核處理器的核數(shù)目,TRL為輪轉(zhuǎn)調(diào)度周期時(shí)長(zhǎng).

2.4 多任務(wù)負(fù)載比例輪轉(zhuǎn)調(diào)度方法

多任務(wù)負(fù)載比例輪轉(zhuǎn)調(diào)度方法主要分為如下4個(gè)步驟:

1) 確定多核處理器輪轉(zhuǎn)周期TRL;

2) 基于任務(wù)權(quán)值分配方法,分別計(jì)算每個(gè)任務(wù)在每輪調(diào)度中的權(quán)值Wi;

3) 搜索任務(wù)隊(duì)列中的所有任務(wù),將權(quán)值高的任務(wù)排在等待處理隊(duì)列的最前面;

4) 搜索處理器的各個(gè)核是否空閑,將搜索到的第一個(gè)空閑處理器核分配給等待隊(duì)列隊(duì)首的任務(wù).

具體的處理流程如圖2所示.

圖2 任務(wù)調(diào)度處理流程圖

3 模型參數(shù)

3.1 可調(diào)度性分析

對(duì)系統(tǒng)內(nèi)M個(gè)處理器核上的n個(gè)任務(wù)啟動(dòng)負(fù)載比例權(quán)值輪轉(zhuǎn)調(diào)度算法,為保證任務(wù)的實(shí)時(shí)性,任務(wù)的最大延遲不大于輪轉(zhuǎn)周期[13].

定理.當(dāng)M滿足:

時(shí),多核處理器任務(wù)負(fù)載比例權(quán)值調(diào)度算法,確保系統(tǒng)內(nèi)所有任務(wù)滿足實(shí)行性.

證明.任務(wù)Ti按負(fù)載比例分配權(quán)值:

多核處理器輪轉(zhuǎn)調(diào)度下任務(wù)Ti的最大延遲為:

為了滿足任務(wù)的實(shí)時(shí)性,對(duì)分區(qū)內(nèi)各個(gè)任務(wù)應(yīng)滿足的條件是:

證畢.

3.2 系統(tǒng)參數(shù)評(píng)價(jià)函數(shù)

輪轉(zhuǎn)長(zhǎng)度TRL越大,調(diào)度算法用于任務(wù)間切換的消耗越小,處理器數(shù)目M越小,系統(tǒng)資源浪費(fèi)越少[13],令評(píng)價(jià)函數(shù)

將綜合模塊化航空電子系統(tǒng)的多核實(shí)時(shí)調(diào)度問題轉(zhuǎn)換為非線性最優(yōu)化問題,函數(shù)值越小,系統(tǒng)任務(wù)的可調(diào)度性越高.

4 仿真實(shí)驗(yàn)與分析

為了驗(yàn)證提出的基于多核的任務(wù)負(fù)載比例輪轉(zhuǎn)的調(diào)度方法的有效性,利用離散事件仿真方法建立分區(qū)任務(wù)多核處理調(diào)度模型,對(duì)任務(wù)集進(jìn)行離散事件仿真實(shí)驗(yàn).

仿真實(shí)驗(yàn)采用JDK1.5自帶的任務(wù)調(diào)度工具Timer類搭建模擬仿真環(huán)境,實(shí)現(xiàn)基于多核的任務(wù)負(fù)載比例輪轉(zhuǎn)調(diào)度方法.該方法利用Timer類的兩個(gè)內(nèi)部類TaskQueue和TaskThread類,分別模擬任務(wù)調(diào)度模型中的任務(wù)集 T={T1,T2,…,Tn}和處理器核集K={K1,K2,…,Km}.

實(shí)驗(yàn)主要考量基于任務(wù)負(fù)載比例權(quán)值計(jì)算,不同的輪轉(zhuǎn)周期TRL對(duì)系統(tǒng)性能的影響.進(jìn)一步地,驗(yàn)證算法的可調(diào)度性,即對(duì)調(diào)度方法的可調(diào)度性進(jìn)行判定[14].將基于MLPRR的判定方法與文獻(xiàn)[15]提出的BAR判定方法以及文獻(xiàn)[16]提出的RTA判定方法進(jìn)行了比較.

具體實(shí)驗(yàn)方法如下:

每個(gè)任務(wù)可表示為Ti=(Zi,Ci,Pi,Di),仿真時(shí)不區(qū)分任務(wù)所屬的分區(qū),且設(shè)Di為Pi,故可以簡(jiǎn)化任務(wù)模型為Ti=(Ci,Pi,Di).

實(shí)驗(yàn)參照文獻(xiàn)[8]方式隨機(jī)生成任務(wù),任務(wù)的利用率Ui的分布符合以δ為期望的指數(shù)分布,生成過程中排除Ui>1的情況; 周期Ti服從[1,200]上的均勻分布.

實(shí)驗(yàn)步驟按照下述三步進(jìn)行:

1) 初始化任務(wù)集,任務(wù)個(gè)數(shù)為n+1;

2) 采用文獻(xiàn)[14]提出的任務(wù)集具有可行性的必要條件進(jìn)行檢驗(yàn).若該任務(wù)集可行,則使用相應(yīng)的判定方法對(duì)任務(wù)集進(jìn)行可調(diào)度性判定;

3)若該任務(wù)集被判定為可調(diào)度任務(wù)集,則向該任務(wù)集中增加一個(gè)新任務(wù),得到一個(gè)新的任務(wù)集,重復(fù)步驟2).

此處設(shè)定處理器核的數(shù)量M=4,平均利用率δ=0.6,最終的測(cè)試任務(wù)集為1000個(gè)任務(wù).其實(shí)驗(yàn)結(jié)果如圖3,圖4所示.

圖3 任務(wù)處理時(shí)間比較

圖3列示了10個(gè)任務(wù)在不同輪詢周期TRL=5和TRL=12 的任務(wù)處理時(shí)間.由圖3可以得出:TRL=12所需的任務(wù)處理時(shí)間比TRL=5所需的任務(wù)處理時(shí)間少,任務(wù)的可調(diào)度性越高,實(shí)時(shí)性更好.

從圖4可以得出: 滿足可調(diào)度性的任務(wù)集有767個(gè)任務(wù).其中,通過BAR判定方法的任務(wù)集有285個(gè),通過RTA判定方法的任務(wù)集有426個(gè),通過本文提出的MLPRR判定方法的任務(wù)集有458個(gè).

圖4 可調(diào)度性判定比較

實(shí)驗(yàn)表明: 本文提出的MLPRR方法具有更好的可調(diào)度性,尤其是隨著判定任務(wù)集數(shù)量的增加,MLPRR方法顯示出了更強(qiáng)的判定優(yōu)勢(shì).這充分本文提出的基于多核負(fù)載比例輪轉(zhuǎn)的調(diào)度方法MLPRR為分區(qū)操作系統(tǒng)多核處理器任務(wù)調(diào)度提供了一種有效的調(diào)度策略.

5 小結(jié)

本文提出了一種基于ARINC653分區(qū)操作系統(tǒng)的多核處理器任務(wù)調(diào)度的任務(wù)負(fù)載比例輪轉(zhuǎn)調(diào)度方法MLPRR,該方法以任務(wù)的負(fù)載比例計(jì)算權(quán)值,完成任務(wù)在多核處理器上的調(diào)度,從而滿足多核分區(qū)操作系統(tǒng)的實(shí)時(shí)性要求.針對(duì)影響調(diào)度算法的參數(shù)設(shè)計(jì)了合理的評(píng)價(jià)函數(shù).本文的設(shè)計(jì)方法、仿真分析和研究結(jié)論有助于未來符合ARINC653標(biāo)準(zhǔn)的多核處理器分區(qū)實(shí)時(shí)任務(wù)的設(shè)計(jì)和分析.

參考文獻(xiàn)

1AEEC,Aeronautical Radio Inc.ARINC 653P0 Avionics application software standard interface.2551 RIVA ROAD,ANNAPOLIS,MARYLAND 21401-7435,2014.

2Lee YH,Kim D,Younis M,et al.Partition scheduling in APEX runtime environment for embedded avionics software.Proceedings of the Fifth International Conference on Real-Time Computing Systems and Application.Hiroshima,Japan.1998.103–109.

3Lim S,Hyun J,Shin SM,et al.A feasibility study for ARINC 653 based operational flight program development.Proceedings of the 31st Digital Avionics Systems Conference.Williamsburg,VA,USA.2012.6C2-1–6C2-7.

4Ruan WL,Zhai ZJ.Kernel-level design to support partitioning and hierarchical real-time scheduling of ARINC 653 for VxWorks.Proceedings of the 2014 IEEE 12thInternational Conference on Dependable,Autonomic and Secure Computing.Dalian,China.2014.388–393.

5Tindell KW,Burns A,Wellings AJ.Allocating hard realtime tasks: An NP-hard problem made easy.Real-Time Systems,1992,4(2): 145–165.[doi: 10.1007/BF00365407]

6何鋒,宋麗茹,熊華鋼.航空電子雙層任務(wù)分區(qū)調(diào)度設(shè)計(jì).北京航空航天大學(xué)學(xué)報(bào),2008,34(11): 1364–1368.

7Saidi S.On the benefits of multicores for real-time systems.Proceedings of 2017 Euromicro Conference on Digital System Design.Vienna,Austria.2017.383–389.

8Marko B,Michele C,Giuseppe L.Schedulability analysis of global scheduling algorithms on multiprocessor platforms.IEEE Transactions on Parallel and Distributed Systems,2009,20(4): 553–566.[doi: 10.1109/TPDS.2008.129]

9代聲馨,洪玫,郭兵,等.多處理器實(shí)時(shí)系統(tǒng)可調(diào)度性分析的 UPPAAL 模型.軟件學(xué)報(bào),2015,26(2): 279–296.[doi:10.13328/j.cnki.jos.004781]

10何翔,任曉瑞,劉帥.嵌入式多核操作系統(tǒng)確定性研究.航空計(jì)算技術(shù),2014,44(3): 96–100.

11劉鴿,葉宏,李運(yùn)喜,等.基于多分區(qū)操作系統(tǒng)的多核確定性調(diào)度方法設(shè)計(jì).航空計(jì)算技術(shù),2016,46(1): 99–102.

12黃金,許渤,凌云,等.機(jī)載波分復(fù)用網(wǎng)絡(luò)強(qiáng)實(shí)時(shí)性調(diào)度算法設(shè)計(jì).光學(xué)學(xué)報(bào),2013,33(4): 0406001.

13周立,丁凡,熊華鋼.航空電子WDM網(wǎng)絡(luò)多信道強(qiáng)實(shí)時(shí)調(diào)度設(shè)計(jì).北京航空航天大學(xué)學(xué)報(bào),2010,36(2): 1392–1395.

14石林勇,晏立.多處理器全局單調(diào)比率的可調(diào)度性分析.計(jì)算機(jī)應(yīng)用,2010,30(10): 2735–2737.

15Baruah S. Techniques for multiprocessor global schedulability analysis.Proceedings of the 28th IEEE International Real-Time Systems Symposium.Tucson,AZ,USA.2007.119–128.

16Bertogna M,Cirinei M.Response-time analysis for globally scheduled symmetric multiprocessor platforms.Proceedings of the 28th IEEE International Real-Time Systems Symposium.Tucson,AZ,USA.2007.149–160.