航空電子核心處理分區(qū)優(yōu)化設計及仿真研究

宋麗茹，谷曉燕，陳 沫，董智明

(1.空軍航空儀器設備計量總站，北京 100070;2.北京信息科技大學信息管理學院，北京 100192)

0 引言

航空電子核心處理系統(tǒng)是一個具有嚴格實時保障和安全保障的系統(tǒng)［1］。實時保障是指系統(tǒng)能夠及時地響應內(nèi)/外部事件，并可以在預知的時間內(nèi)完成響應處理的能力，即任務關鍵保障能力;安全保障是指系統(tǒng)能夠提供不同級別敏感數(shù)據(jù)的物理或者邏輯上的隔離，從而保障整個系統(tǒng)的信息安全的能力。

針對新一代航空電子核心處理系統(tǒng)，為了構建任務關鍵和安全關鍵保障能力，分區(qū)管理概念應運而生，同時分區(qū)管理也是隨著航空電子軟件大量應用于航空電子核心處理系統(tǒng)而促成的。

在對分區(qū)管理應用于航空電子核心處理系統(tǒng)的研究中，主要包含分區(qū)調度設計問題。對于分區(qū)調度模型，其調度規(guī)則不同于單層調度情況，需要結合上下層調度器進行整體分析，同時需要合理安排分區(qū)參數(shù)，從而滿足任務和分區(qū)本身的可調度性。針對這些情況，文獻［2］提出了基于單調速率任務分配的調度模型，并得到了分區(qū)設計的關鍵參數(shù)表達式。文獻［3-5］擴展了文獻［2］的模型，使用了參數(shù)(Δ，α)來描述每個分區(qū)，其中Δ為分區(qū)執(zhí)行最大間隔時間，α為分區(qū)執(zhí)行系數(shù)，而文獻［2］的模型可以看作是文獻［3-5］模型的特例。文獻［6］采用了類似的分析方法，得到了相似的結論。在模型中都是依賴于虛擬處理器的概念，存在處理器利用率偏低的問題。本文從分區(qū)調度本質入手，仔細考察分區(qū)搶占影響，并利用文獻［7］在文中提到的任務時間需求函數(shù)為基礎，利用輪轉調度周期和分區(qū)任務執(zhí)行系數(shù)，建立可行的分區(qū)調度模型，并給出了分區(qū)參數(shù)優(yōu)化設計，最后給出了航空電子核心處理系統(tǒng)仿真方法。

1 核心處理系統(tǒng)的發(fā)展

迄今為止，航空電子系統(tǒng)經(jīng)歷了4個典型的發(fā)展階段:分立式航空電子系統(tǒng)、聯(lián)合式航空電子系統(tǒng)、綜合式航空電子系統(tǒng)和先進綜合式航空電子系統(tǒng)。隨著航空電子系統(tǒng)體系結構的發(fā)展，其核心處理系統(tǒng)的功能與結構也在不斷地發(fā)生變化。

在分立式航空電子系統(tǒng)中，各航空電子設備/分系統(tǒng)(如雷達、管道等)的控制、處理、顯示均為獨立系統(tǒng)，采用專用處理器，不存在核心處理系統(tǒng)的概念。在聯(lián)合式航空電子系統(tǒng)中，將原來各自獨立工作的航空電子設備通過1553B數(shù)據(jù)總線進行互聯(lián)，并通過任務軟件進行綜合控制顯示，實現(xiàn)信息資源共享，但是仍然使用專用處理器，比如F-15中使用了12種專用處理器，并且每個子系統(tǒng)采用專用的操作系統(tǒng)。

隨著微電子技術和計算機技術的發(fā)展，航空電子系統(tǒng)設計技術得到了突飛猛進的發(fā)展，體系結構打破了傳統(tǒng)各分系統(tǒng)的界限，按功能分區(qū)，可以將整個航空電子系統(tǒng)劃分為一個核心處理區(qū)和幾個相應的綜合區(qū)。其中核心處理區(qū)可以說是航空電子系統(tǒng)的大腦，完成雷達、電子戰(zhàn)、光電等傳感器的信號處理和數(shù)據(jù)融合，并完成飛控管理、導航計算、火控計算、顯示控制管理等任務的處理功能，從而出現(xiàn)綜合處理器(CIP)的概念。CIP由多個許多現(xiàn)場可更換模塊(LRM)組成，綜合了CNI計算和管理、座艙顯示與圖形處理、系統(tǒng)任務調度、系統(tǒng)完好情況監(jiān)視等。這些任務動態(tài)分配給LRM，在不同的階段調用不同LRM實現(xiàn)指定功能。

在先進綜合式航空電子系統(tǒng)中，繼續(xù)使用通用化、模塊化和標準化的模塊系列，以減少成本并提高模塊的可支持性，廣泛采用了綜合程度更高的綜合核心處理器(ICP)，ICP總的處理能力比CIP的處理能力提高一個數(shù)量級，但所用模塊數(shù)量只為CIP的四分之一，ICP采用統(tǒng)一的軍用實時操作系統(tǒng)，模塊中的每個處理器通過光纖通道互聯(lián)，從而實現(xiàn)信息的交換。美國的F-35上已經(jīng)開始使用此種處理結構，在處理模塊的體積、重量、功耗和成本上將大大減少負擔，同時核心處理系統(tǒng)的結構變得更加簡單。

由此可見，采用高度綜合化、開放式標準接口的核心處理系統(tǒng)將成為新一代航空電子系統(tǒng)成功實施的關鍵。但與此同時為了提高核心處理系統(tǒng)的任務保障能力和安全保障能力，分區(qū)管理概念應運而生，同時分區(qū)管理也是隨著航空電子軟件大量應用于航空電子系統(tǒng)而促成的。分區(qū)管理的實施需要建立在綜合化、模塊化和集成化的航空電子系統(tǒng)基礎之上，分區(qū)管理的概念和作用也是在近十年內(nèi)得到定義和發(fā)展的。分區(qū)管理作為一種設計技術，用來將航空電子系統(tǒng)中不同的功能應用限制在其活動范圍內(nèi)，從而不對其他功能應用產(chǎn)生影響。分區(qū)實際上是系統(tǒng)設計概念中最小耦合的另外一種說法，組件之間耦合越小，那么系統(tǒng)遭遇不可預料的風險也越小，從而提高了系統(tǒng)可靠性。

2 分區(qū)調度模型

在ARINC 653［8］標準中，分區(qū)的定義指的是對運行在處理模塊上的航空電子應用軟件按照某種策略進行分組，使得每組應用軟件從時間上或者空間上相互獨立。一個分區(qū)由一個或多個并發(fā)執(zhí)行的進程組成，分區(qū)內(nèi)所有進程共享分區(qū)所占有的系統(tǒng)資源。操作系統(tǒng)對分區(qū)所占用的處理時間、內(nèi)存和其他資源擁有控制權。分區(qū)管理保證了同時運行的多個不同類型的應用軟件在時間和空間上的互不影響。

分區(qū)屬性定義了分區(qū)運行的基本特性［9］。每個分區(qū)有唯一的屬性說明，使用這些屬性，系統(tǒng)可以管理和控制分區(qū)的運行。典型的分區(qū)屬性包括:分區(qū)標識名、存儲區(qū)定義、分區(qū)激活周期、安全關鍵級別、入口地址等。在每個分區(qū)內(nèi)，進程按照本地調度策略進行調度。分區(qū)內(nèi)的任務只能在分區(qū)當前激活窗口內(nèi)運行，當某個分區(qū)處于激活狀態(tài)，但是分區(qū)內(nèi)沒有任務處于就緒狀態(tài)時，分區(qū)處于空閑狀態(tài)，即使其他分區(qū)有任務處于就緒狀態(tài)，也不能跨越分區(qū)的邊界在當前分區(qū)內(nèi)得到執(zhí)行。因此分區(qū)是不同安全級別的航空應用軟件有效隔離的重要手段。結合上下層調度，我們可以看出:分區(qū)管理模型實際是一個層次調度模型:在操作系統(tǒng)層，上層調度器通過分區(qū)的屬性來決定在何時激活某個分區(qū)，在每一個分區(qū)內(nèi)，下層調度器根據(jù)具體的調度策略對每個任務進行調度。

考慮一個單處理器系統(tǒng)∏，不失一般討論性，處理器上包含K個分區(qū)，由這些分區(qū)組成的單處理器系統(tǒng)可以表示為

其中，Pk表示第k個分區(qū)。分區(qū)的屬性包括:分區(qū)周期ηk，分區(qū)執(zhí)行系數(shù)ηk等。因此在一個周期內(nèi)，分區(qū)執(zhí)行時間的總和為ηkαk。對于ARINC 653分區(qū)管理模型，分區(qū)有固定的時間設計窗口，分區(qū)沒有優(yōu)先級，因此其上層調度策略類似于輪轉調度策略，在這種考慮下，可以認為所有分區(qū)具有相同的分區(qū)周期η。

經(jīng)過系統(tǒng)分析和設計，可以將其ICP所實現(xiàn)的功能分解為若干獨立或者相互關聯(lián)的實體，這些實體稱為任務。

考慮單處理器上面的第k個分區(qū)Pk，包含nk個任務，這些任務組成的任務集為

若不考慮分區(qū)，則處理器上的任務集為

其中，Γ為單處理器上面的所有任務集合。

對于周期任務 τki，它可以用一個四元組(Jki，pki，eki，Dki)來描述。其中:Jki是釋放抖動;pki為周期;eki是任務執(zhí)行時間;Dki為時限，指任務由到達至完成的最大允許時間間隔。任務的實時性要求用任務的時限來進行定義，如果某任務的作業(yè)的響應時間超過其時限，則該作業(yè)破壞了其實時性要求。

考慮到上下兩層調度策略組合，分區(qū)調度模型如圖1所示。

圖1 分區(qū)調度模型Fig.1 Partition scheduling model

3 分區(qū)調度設計及優(yōu)化

分區(qū)調度模型在操作系統(tǒng)層采用輪轉調度策略實現(xiàn)分區(qū)的調度，在每個分區(qū)采用本地調度策略實現(xiàn)任務的調度。根據(jù)不同的本地調度策略，分區(qū)具有不同的調度能力。分區(qū)內(nèi)采用的優(yōu)先級調度策略包括固定優(yōu)先級和動態(tài)優(yōu)先級兩種。

3.1 固定優(yōu)先級

當下層調度器采用固定優(yōu)先級調度策略時，對于分區(qū)Pk，其有效執(zhí)行時間為η×αk，其他分區(qū)對本分區(qū)的阻塞為η×(1-αk)，可以把其他分區(qū)對Pk分區(qū)的阻塞看作是一周期任務 τk0(0，η，η(1-αk)，η(1-αk))對Pk分區(qū)中任務的搶占造成的，τk0具有最高優(yōu)先級，釋放抖動為0，周期為η，執(zhí)行時間和截至時限均為每一輪周期調度中分給其他分區(qū)的時間η×(1-αk)，其行為剛好模擬了其他分區(qū)對Pk的影響。

因此對這種調度策略下，分區(qū)內(nèi)任務的最大相應時間Rki可以根據(jù)Tindell［10］的整體求解思想通過迭代的方式進行計算。

其中，hp'(ki)為任務集Γk中優(yōu)先級高于τki的任務集合hp(ki)和虛擬任務τk0的組合，即:hp'(ki)=hp(ki)U{τk0}。由于Rki出現(xiàn)在方程的兩邊，可以采用迭代方式來計算，Tindell［10］證明了當處理器利用率小于1時，迭代方程必然會匯聚。

在給定η和αk下，可以通過式(1)來判斷分區(qū)任務的可調度性，對于給定的分區(qū)任務集Γk，需要找出合適的η和αk來滿足分區(qū)任務的正確調度。

定義:

對于基于固定優(yōu)先級調度的分區(qū)Pk，當η和αk滿足如下方程組時，則分區(qū)可調度。

為了證明，可以將分區(qū)Pk內(nèi)任務τki的截止期限Dki代入式(1)中的wki公式中，并取hp'(ki)集合，有

注意到式(1)中的wki為遞增函數(shù)，因此wki必定在Dki-Jki值以下匯聚，有

因此分區(qū)Pk所有任務都可以調度。

3.2 動態(tài)優(yōu)先級

當下層調度器采用動態(tài)優(yōu)先級調度策略時，考慮某一個分區(qū)Pk，其他分區(qū)對本分區(qū)的阻塞，同樣可以看作是一周期任務 τk0(0，RL，RL(1-αk)，RL(1- αk))對Pk分區(qū)中任務的搶占造成的，由于EDF為動態(tài)優(yōu)先級調度策略，按照本模型，在分區(qū)Pk的具體執(zhí)行時刻T0，并不能保證τk0不被相對時限小于T0+RL(1-αk)的任務搶占，由于τk0的執(zhí)行時間和截止時限為同一個值，因此在時刻T0+RL(1-αk)，τk0執(zhí)行必然未完成。當用某種模型可以檢測所有必須時刻，任務集Γk中所有任務和τk0都能調度成功，則τk0剛好模擬了其他分區(qū)對Pk的周期搶占影響。

針對EDF調度，文獻［7］提到任務時間需求函數(shù)(DBF)來判斷任務的可調度性，如下所示。

對于任務集Γ'k=ΓkU{τk0}，需考察一段時間段內(nèi)任務的調度情況，文獻［7］給出只需要考察區(qū)間

即可，在考察的區(qū)間內(nèi)對于任意I，均應有式(9)成立，則按照EDF策略，任務集可調度。

通過這種方式能夠對下層調度器采用EDF策略的可調度性進行判斷。對于給定的分區(qū)任務集Γk，為了構造合理的分區(qū)參數(shù)，借助于空閑時間的思想，可以定義

其中，Ikey為設置的關鍵觀察時刻，在I∈［Dmink-Jk，Ikey］區(qū)間，精確考察每一個時刻任務時間處理需求，而對于I≥Ikey區(qū)間，構造一個擴大的時間需求邊界，從而保障區(qū)間I≥Ikey調度成功，即式(2)的意義所在。

在得到空閑時間的基礎上，對于虛擬任務τk0，有

因此為了滿足分區(qū)內(nèi)任務的調度性，分區(qū)參數(shù)需要滿足

從這里，Ikey的設置為分區(qū)參數(shù)的設計帶來了靈活性:當擴大Ikey的取值時，能夠觀察更多的任務處理時間需求，從而獲得更加精確的計算結果，但是同時也帶來了更多的計算量增加;當減小Ikey的取值時，降低了任務處理時間集合的元素數(shù)量，可以快速獲取分區(qū)參數(shù)計算結果。

3.3 評估與優(yōu)化

考察一個具體的算例，給定分區(qū)和任務如表1所示。

表1 分區(qū)參數(shù)及任務參數(shù)Table 1 Partition and task parameters

由表1所示，上層調度器的輪轉周期為5，即分區(qū)1和分區(qū)2的周期均為5。對比采用分區(qū)調度和不采取分區(qū)調度給任務的最大相應時間帶來的影響。

根據(jù)固定優(yōu)先級和動態(tài)優(yōu)先級任務最大響應時間算法，并考慮到虛擬任務τk0的搶占影響，可以得到采用分區(qū)管理模型前后任務的最大響應時間變化的情況，如圖2所示。

圖2 任務最大響應時間情況Fig.2 The maximum response time of task

當不采用分區(qū)管理策略時，任務調度為單層調度行為;當采用分區(qū)管理策略時，任務調度為雙層調度行為。圖2中，F(xiàn)P和EDF分別代表單層采用固定優(yōu)先級調度策略和動態(tài)優(yōu)先級調度策略的模型;RR-FP和RR-EDF分別代表采用固定優(yōu)先級和動態(tài)優(yōu)先級的分區(qū)管理調度模型。由圖2可知，在采用分區(qū)調度策略和不采用分區(qū)調度策略下，每個任務的最大延遲時間均不超過其最大允許延時，任務集滿足實時性要求。從實時性上來說，采用分區(qū)管理模型的任務延時將比不采用分區(qū)管理模型大，但是，分區(qū)管理將任務限制在各自的分區(qū)內(nèi)執(zhí)行，保證了同時運行的多個不同類型的任務在時間上和空間上互不影響，這對于構建安全關鍵的航空電子系統(tǒng)有著重要意義，因此采用分區(qū)管理帶來的延遲擴大是為了保障系統(tǒng)安全的一種時間成本的付出。

在對分區(qū)參數(shù)進行設計的過程中，式(6)和式(11)分別給出了在固定優(yōu)先級和動態(tài)優(yōu)先級策略下符合任務可調度性的分區(qū)參數(shù)的取值條件。圖3給出了固定優(yōu)先級策略下分區(qū)參數(shù)的取值空間。

圖3 分區(qū)參數(shù)取值范圍Fig.3 The scope for partition parameters

在圖3中，橫坐標為分區(qū)周期，縱坐標為分區(qū)執(zhí)行系數(shù)，黑色區(qū)域為分區(qū)1執(zhí)行系數(shù)的取值范圍，在這里考慮到了分區(qū)1和分區(qū)2任務的可調度性。因此對于給定的任務和分區(qū)，存在多個合理參數(shù)對其進行配置。為了對求解結果進行集中和優(yōu)化，對于每個任務，定義了其最大響應延時率為

則對于整個處理器上的分區(qū)調度系統(tǒng)，可以定義系統(tǒng)的最大響應延時率為

系統(tǒng)的最大響應延時率與任務的最大響應時間有關，同時也與任務的個數(shù)有關，但對于一個給定任務個數(shù)和參數(shù)，以及分區(qū)劃分的系統(tǒng)，可以通過d來對分區(qū)參數(shù)的優(yōu)劣性進行對比。同時在分區(qū)設計的過程中，需要考慮到多個分區(qū)本身的可調度性，對于輪轉調度策略，對于分區(qū)的執(zhí)行系數(shù)，需要滿足

對于其輪轉周期越大越好，從而減小由于操作系統(tǒng)進行分區(qū)切換帶來的額外開銷，因此一個合理的優(yōu)化指標為:其中w為分區(qū)切換操作影響權重，對于優(yōu)化指標F來說，取值越小越符合優(yōu)化的方向。在這種優(yōu)化角度上，可以繪出在固定優(yōu)先級和動態(tài)優(yōu)先級調度策略下，系統(tǒng)評價指標與輪轉調度周期的關系。

圖4 分區(qū)參數(shù)優(yōu)化設計Fig.4 The optimization design for partition parameters

圖4中，紅色線為下層調度器采用固定優(yōu)先級情況下的分區(qū)參數(shù)設計情況;藍色線為采用動態(tài)優(yōu)先級情況下的設計情況。由此看出在動態(tài)優(yōu)先級下，可以設計的輪轉周期最大長度要大于固定優(yōu)先級，同時獲得的最佳分區(qū)參數(shù)也要優(yōu)于固定優(yōu)先級所對應的設計。在動態(tài)優(yōu)先級調度策略下，最佳輪轉調度周期為2.76，此時的價值函數(shù)值為3.01;對于固定優(yōu)先級調度策略下，最佳輪轉調度周期為1.5，此時的價值函數(shù)值為3.2。

4 ICP仿真模型

在對航空電子ICP功能和分區(qū)管理機制分析的基礎上，我們開發(fā)了ICP仿真工具，實現(xiàn)了網(wǎng)絡拓撲構建、ICP任務分配、分區(qū)調度模擬、可調度性分析，以及分區(qū)參數(shù)設計等功能，從而完整地支持ICP功能開發(fā)、仿真和驗證需求，在這里面，ICP仿真引擎為工具的核心。在基于分區(qū)調度的仿真引擎中，采用兩層調度的方式對分配在處理器上的任務進行調度執(zhí)行:上層調度對分區(qū)進行調度，采用時間輪轉的方式;下層調度采用優(yōu)先級驅動的方式對當前激活分區(qū)內(nèi)的任務進行調度。調度仿真模型如圖5所示。

圖5 基于分區(qū)調度的仿真模型Fig.5 The simulation model for partition scheduling

上層調度采用時間輪轉的方式對分區(qū)進行調度。分區(qū)狀態(tài)的改變不依賴于系統(tǒng)中的事件(如作業(yè)完成、作業(yè)釋放)，可以預先計算好一個調度表，表中的每個條目給出一個決策時刻ti和就緒分區(qū)P(ti)。下層調度采用基于優(yōu)先級驅動的算法對分區(qū)內(nèi)的任務進行調度。下層調度的主要仿真事件有:作業(yè)釋放、調度CPU、作業(yè)執(zhí)行、作業(yè)被搶占、作業(yè)完成、消息產(chǎn)生、消息傳輸、消息到達等。與單層調度中基于優(yōu)先級驅動算法的仿真模型所不同的是，在兩層調度的模型中，下層調度并非對處理器上的所有任務進行調度處理，而只對當前活動分區(qū)中的任務進行調度處理。

5 結束語

本文針對航空電子核心處理系統(tǒng)分區(qū)管理技術，詳細研究了分區(qū)調度模型，并針對下層調度器采用固定優(yōu)先級和動態(tài)優(yōu)先級兩種策略下，詳細討論了分區(qū)參數(shù)設計的過程，以及相應的公式推導，并結合任務響應最大延遲率及分區(qū)切換開銷，給出了分區(qū)參數(shù)優(yōu)化設計方向，通過實際算例對本文中提到的方法進行了評估，最后給出了ICP仿真工具的設計方法，特別是給出了分區(qū)調度引擎的設計模型。

本文的結論將有助于航空電子核心處理系統(tǒng)構架的實施，以及其仿真工具的設計。后續(xù)工作可以考慮更加復雜的網(wǎng)絡傳輸模型，實現(xiàn)核心處理和網(wǎng)絡傳輸延遲的更加緊密結合設計。

［1］宋麗茹，何鋒，熊華鋼.航空電子藍圖系統(tǒng)實時性設計［J］.電光與控制，2010，17(6):5-8.

［2］LEE Y H，KIM D，YOUNIS M，et al.Resource scheduling in dependable integrated modular avionics［C］//Dependable Systems and Networks.NY:IEEE，2000:14-23.

［3］LIPARI G，BINI E.Resource partition among real-time application［C］//The 15th Euromicro Conference on Real-Time Systems.NY:IEEE，2003:151-158.

［4］LIPARI G，BINI E.A methodology for designing hierarchical scheduling systems［J］.Journal of Embedded Computing，2004，1(2):257-269.

［5］CIRINEI M，BINI E，LIPARI G.A flexible scheme for scheduling fault-tolerant real-time tasks on multiprocessor［C］//Parallel and Distributed Processing Symposium.NY:IEEE，2007:1-9.

［6］AIMEIDA L，PEDREIRAS P.Scheduling within temporal partitions:Response-time analysis and server design［C］//The 4th ACM international conference on Embedded software.Italy:Pisa，2004:95-103.

［7］BARUAH S K.Dynamicand staticpriority scheduling of recurring real-time tasks［J］.Real-Time Systems，2003，24(1):93-128.

［8］ARINC Specification 653:Avionics Application Software Standard Interface(ARINC 653-1-2003)［S］.2003.

［9］李昕穎，顧健，何鋒.硬實時系統(tǒng)在強分區(qū)約束下的雙層分區(qū)調度［J］.計算機學報，2010，33(6):1032-1039.

［10］TINDELL K.Holistic schedulability analysis for distributed hard real-time systems［J］.Microprocessor and Microsystems，1994，50:117-134.