何鋒，張立，于思凡，周璇

北京航空航天大學 電子信息工程學院，北京 100191

航空電子系統(tǒng)的發(fā)展經歷了分立式、聯(lián)合式、綜合式、先進綜合式4 個階段，正朝著分布式綜合化架構發(fā)展。ARINC 653 規(guī)范是適用于航空軟件的實時操作系統(tǒng)接口標準，其規(guī)定了綜合模塊化航空電子系統(tǒng)（Integrated Modular Avionics，IMA）體系架構下的操作系統(tǒng)的行為邏輯和向應用程序提供的接口規(guī)范［1］。ARINC 653 規(guī)范定義了分區(qū)的概念，分區(qū)操作系統(tǒng)采用兩層調度機制，分區(qū)間通過時間輪轉調度的方式共享處理資源，處理任務在分區(qū)激活窗口內進行本地調度，與其他分區(qū)的任務在時間維度上相互隔離［2-3］。由于航空電子系統(tǒng)的高實時性要求，分區(qū)調度必須滿足實時性，探尋精確的最壞延遲計算方法則是保證實時性的必要條件。當前的分區(qū)系統(tǒng)可調度性分析方法無法對主時間框架下具有多窗口分區(qū)的系統(tǒng)進行任務最大響應時間（Worst-Case Response Time，WCRT）的精確計算。因而如何能夠實現多窗口分區(qū)下任務實時性的精確評估就成為當下分區(qū)調度研究的重點。

目前針對系統(tǒng)的可調度性分析已有多位國內外學者進行了研究。Bini和Buttazzo［4］針對單調速率調度算法從任務利用率函數的角度來分析，并給出相應的判定不等式。高曉光等［5］針對單分區(qū)任務響應時間上限的計算方法進行研究，將其他分區(qū)視為對某個分區(qū)的阻塞，推導出多分區(qū)雙層調度系統(tǒng)下的任務響應時間上限分析方法，但該算法只有在系統(tǒng)任務數量較小時才有較高精度。譚龍華等［6］基于負載請求與平臺資源提供能力的供需約束關系給出了系統(tǒng)可調度性的判定依據。Easwaran 等［7］基于資源模型分析技術，提出了考慮偏移、抖動和截止期限的可調度性分析模型。Chen 等［8］提出了一種多核處理器上分區(qū)可調度性判定方法，通過計算最大縮放因子來確定所有分區(qū)的可調度性。

這些方法基本都是從任務最壞響應時間的迭代計算或者任務負載利用率等角度實施系統(tǒng)的可調度性分析，同時還存在不適配一個主時間框架下分區(qū)包含多個激活窗口的最壞響應時間計算的問題。此外，對于IMA 系統(tǒng)的研究往往需要對計算模塊和網絡交換模塊組成的系統(tǒng)架構進行綜合演算分析。因此本文從網絡演算的視角下對分區(qū)任務的可調度性進行分析，將計算模塊和網絡交換模塊延遲計算模型進行統(tǒng)一，并發(fā)展出對任務系統(tǒng)可調度性分析的新思路。

網絡演算是一種對網絡性能分析的方法，該方法通過流量的到達曲線和端口的服務曲線之間的關系來對流量的最壞延遲進行精確計算。一方面，網絡流量的傳輸是交換機對于流量中消息數據幀的轉發(fā)；任務的執(zhí)行是處理器單元對于任務包含的指令進行運算。這兩者都可以抽象為對服務能力需求與對服務能力提供的關系，具有一定的相似性。另一方面，由于分區(qū)在主時間框架內的多個釋放抖動窗具備服務資源的獨立性，使用網絡演算中的服務曲線模型，能夠與每個激活窗口的具體偏置和持續(xù)時間進行匹配，可以解決傳統(tǒng)最壞響應時間算法無法計算主時間框架下多激活窗口分區(qū)的情況。基于此，可以將網絡演算的算法思想應用到任務的延遲計算中，以發(fā)展解決調度問題的新思路。

本文將適用于機載網絡系統(tǒng)通信確定性分析的方法拓展到系統(tǒng)任務可調度性分析的計算過程中，創(chuàng)建分區(qū)和任務的網絡演算模型，提出對基于固定優(yōu)先級調度策略下任務的最大響應時間計算計算方法，發(fā)展實現任務調度演算乃至IMA 系統(tǒng)性能一體化演算的新思路。

1 系統(tǒng)模型

1.1 分區(qū)任務調度模型

ARINC653 分區(qū)操作系統(tǒng)采用兩層調度策略。在操作系統(tǒng)層，上層調度器采用輪轉調度的方式執(zhí)行每一個分區(qū)；在每個分區(qū)內部，下層調度器根據設計的任務調度策略進行任務調度，分區(qū)內的任務只有在所屬分區(qū)處于執(zhí)行狀態(tài)時才有機會被執(zhí)行。分區(qū)調度具有嚴格的確定性，每個分區(qū)都有自己的周期和窗口時間，分區(qū)基于周期時間序列進行計算資源的確定性分配，并按照主時間框架分配給它的時間窗口依次激活執(zhí)行。任務在分區(qū)內進行調度執(zhí)行，任務之間根據調度策略進行調度運行。分區(qū)內任務調度策略主要包含固定優(yōu)先級調度策略和動態(tài)優(yōu)先級調度策略，本文主要探討單核系統(tǒng)固定優(yōu)先級搶占式調度下的任務可調度性分析問題。對于多核系統(tǒng)分區(qū)調度的情況可以簡化為多個單核系統(tǒng)［9］。

考慮單處理器系統(tǒng)，系統(tǒng)包含有K個分區(qū)，每個分區(qū)可以用Pk(1 ≤k≤K)來表示，分區(qū)屬性可由〈周期Tk，窗口時長Lk〉兩元組合來表示。系統(tǒng)對K個分區(qū)采用輪轉調度策略來進行訪問執(zhí)行，主時間框架TRL為所有分區(qū)周期的最小公倍數。分區(qū)內包含nk個任務，任務集合為Γk={τki|1 ≤i≤nk}，所有任務都為周期任務，任務之間相互獨立。任務τki可由〈釋放抖動Jki，周期Tki，計算時間Cki，截至期限Dki，優(yōu)先級Oki〉五元組合來表示。系統(tǒng)對分區(qū)內的任務集采用固定優(yōu)先級調度策略進行調度，任務之間允許搶占。系統(tǒng)中分區(qū)任務的調度模型如圖1 所示。

圖1 分區(qū)任務調度模型Fig.1 Scheduling model of partitions and tasks

1.2 網絡演算模型

網絡演算是對網絡性能進行定量分析的一種基于最小加代數的排隊理論。網絡演算可以分為確定性網絡演算［10-11］和隨機網絡演算［12-13］2 類，本文將重點討論確定性網絡演算模型。確定性網絡演算的基本思想是利用替換代數，即最小加代數和最大加代數的數學演算理論，把復雜的非線性系統(tǒng)轉換為簡單的線性系統(tǒng)，將網絡中的節(jié)點作為建模的目標，通過對流經節(jié)點的數據流的排隊計算，實現整個網絡性能的分析。

確定性網絡演算中定義到達曲線α(t)［14-15］來表示到達數據的上包絡，定義服務曲線β(t)［16-17］來表示某一節(jié)點對于數據流的最小服務能力，到達曲線和服務曲線的最大水平截距h(α，β)表示數據流在該節(jié)點的最壞延遲dmax，最大垂直截距v(α，β)表示數據流在該節(jié)點的最大數據積壓wmax［18］，σ為突發(fā)度，T為技術延遲，如圖2 所示。

圖2 確定性網絡演算模型Fig.2 Deterministic network calculus model

確定性網絡演算被廣泛應用于航空網絡系統(tǒng)確定性分析中［19］，其中包括對于時間觸發(fā)以太網（Time Triggered Ethernet，TTE）的實時性分析。時間觸發(fā)以太網在以太網的基礎上添加了全局時鐘同步機制和時間觸發(fā)機制。TTE 包含時間觸發(fā)（Time-Triggered，TT）、速率約 束（Rate-Constrained，RC）、盡力傳輸（Best-Effort，BE）3 種不同類型的流量，其中TT 流量的傳輸具有嚴格的周期性和確定性［20］。TT 流量按照離線設計好的固定時刻進行發(fā)送，網絡中的節(jié)點對于TT流的轉發(fā)時刻也是離線設定。TT 流量具有嚴格周期性的特點，其到達曲線模型和服務曲線模型也與RC 流量、BE 流量有所不同。圖3 給出了單個TT 流的到達曲線和服務曲線以及最壞延遲時間，其中，lTT為TT 流量的數據幀長；pTT為TT 流量的周期；Dmax為最壞延遲時間。

圖3 TT 流到達曲線和服務曲線Fig.3 Arrival curve and service curve of a TT flow

2 任務可調度性分析

流量的傳輸是交換機對輸入流量提供服務的過程，本質上是服務需求和服務能力之間的關系，通過分析這兩者之間的關系可以計算流量的延遲。而任務的執(zhí)行也可以看作是處理器單元為任務提供服務的過程。對于任務，其對計算的需求可以表示為任務需求函數，如考慮一段時間內（通常為周期），任務需要得到處理器完成的計算量。借助于網絡演算中到達曲線的定義，可以將這種計算的需求看作是任務處理需求的一種到達模型。因此，可以定義任務的到達曲線為任務對計算資源的需求函數；定義平臺對任務的服務曲線為處理平臺對該任務所能提供計算資源的服務能力，由此可以借助網絡演算的理念發(fā)展任務最大響應時間計算方法。

定義1 對于某一任務τki，設αki(t)為任務τki的到達曲線函數，βki(t)為處理平臺對τki提供的服務曲線函數，那么任務τki的最大響應時間Wki為αki(t) 與βki(t) 的最大水平截距，即h(αki(t)，βki(t))。

證明 考慮一周期性任務τki，該任務對計算資源的需求會隨著任務周期性的到達而遞增，系統(tǒng)對任務τki所提供的計算資源隨時間呈非遞減，所以任務的到達曲線和服務曲線都是非遞減函數。

若任務到達曲線和服務曲線不相交，那么任意時刻t必有αki(t)＞βki(t)，此時系統(tǒng)不可調度。

若任務到達曲線和服務曲線相交，那么兩曲線的交點即為任務需求與系統(tǒng)提供服務能力的平衡點。在平衡點之前，假設任務τki的p次到達時刻為，則任務到達時刻對計算資源的需求為，假設在時刻，滿足，即系統(tǒng)在時刻所提供的服務恰好滿足任務在時刻所需求的服務，則任務第p次到達時的響應時間為假設平衡點之前任務到達N次，則任務的最大響應時間為這N次到達的響應時間最大值，即

因此任務的最大響應時間即為任務到達曲線與服務曲線的最大水平截距。

2.1 分區(qū)任務到達曲線模型

考慮操作系統(tǒng)的整體服務能力，假設處理器的處理速率為V，單位為每秒百萬指令（MIPS），從整個系統(tǒng)來看，其服務曲線可定義為

系統(tǒng)總服務曲線如圖4 所示。

圖4 系統(tǒng)總服務曲線Fig.4 Service curve of system

2.1.1 分區(qū)到達曲線模型

按照ARINC 653 規(guī)范中分區(qū)調度的特點，分區(qū)在主時間框架中進行具有嚴格周期的輪轉調度?？紤]一分區(qū)Pk的周期為Tk，時間窗口長度為Lk，假設其第1 次到達時刻為Ak，那么該分區(qū)的調度時刻如圖5 所示。

圖5 分區(qū)調度時刻Fig.5 Partition scheduling timeline

分區(qū)Pk在操作系統(tǒng)上的到達是1 個周期為Tk的過程，其到達曲線可由階梯函數給出

分區(qū)到達曲線如圖6 所示。

圖6 分區(qū)到達曲線Fig.6 Arrival curve of partition

證明 對于任意時間間隔[s，t)，在操作系統(tǒng)上共有nk(s，t)個分區(qū)Pk的時間窗口，有

假設使用Rk(t)表示分區(qū)Pk在操作系統(tǒng)上的到達過程，則有

根據網絡演算中關于到達曲線與流量累計曲線的定義可知，分區(qū)Pk在操作系統(tǒng)上的到達曲線為，其中t＞0。

2.1.2 任務到達曲線模型

考慮一分區(qū)Pk內的任務τki，其周期為Tki，任務執(zhí)行時長為Cki，假設第1 次到達時間為Aki，從分區(qū)到達曲線的模型可以類似推出任務τki的到達曲線模型，如圖7 所示。

圖7 任務到達曲線Fig.7 Arrival curve of task

參考分區(qū)到達曲線函數的證明過程，可以類似得出任務的到達曲線函數

2.2 分區(qū)任務服務曲線模型

2.2.1 分區(qū)服務曲線模型

在ARINC653 規(guī)范中，操作系統(tǒng)對于分區(qū)采用輪轉調度策略，所以對于分區(qū)Pk的服務則為系統(tǒng)所提供的總服務能力減去對其他分區(qū)占用窗口后的剩余服務?？紤]到主時間框架中的空閑時間部分并不能為其他分區(qū)提供服務，所以可以將主時間框架中的空閑時間段看作是周期為TRL的空閑分區(qū)，在計算分區(qū)服務曲線時減掉。分區(qū)Pk的服務曲線為

式中：V為處理器速率；sup 為取上確界。

證明 假設使用Rk(t)表示分區(qū)Pk的累計服務函數，令s表示忙周期的起始位置，在忙周期[s，t)內其他分區(qū)的總的服務為

式中：αj(t)為分區(qū)Pj的到達曲線。

在忙周期[s，t)內對于分區(qū)Pk的服務為總服務能力減去對其他分區(qū)Pj的服務，即

又由于Rk(t)為廣義增函數，因此有

則式（12）可簡化為

依據最小加代數卷積定義有

式中：?為極小加代數中的卷積運算；inf 為取下確界。

根據網絡演算中服務曲線與累計服務曲線的定義可知，分區(qū)Pk在操作系統(tǒng)上的服務曲線為，分 區(qū)Pk的服務曲線如圖8 所示。

圖8 分區(qū)服務曲線Fig.8 Service curve of partition

2.2.2 任務服務曲線模型

考慮下層調度器采用固定優(yōu)先級調度策略對分區(qū)內的任務進行調度，因而對于分區(qū)內任務τki的服務曲線為分區(qū)所提供的總的服務能力減去優(yōu)先級高于τki的任務τkj(Okj＜Oki)后的剩余服務

式中：Oki為任務τki的優(yōu)先級。

詳細證明可以參考對分區(qū)服務曲線的證明過程。任務τki的服務曲線與分區(qū)Pk的服務曲線如圖9 所示。

圖9 分區(qū)和任務服務曲線Fig.9 Service curves of partition and task

2.3 任務可調度性判定

任務的可調度性分析可根據任務的最大響應時間Wki和任務截止期限Dki的關系來進行判定，若任務τki的最大響應時間Wki滿足Wki≤Dki，則任務可調度。任務可調度性分析轉化為求任務的最大響應時間問題。任務的最大響應時間依據定義1 可以通過任務的到達曲線和服務曲線的最大水平截距h(αki，βki)計算得到。

對于任務τki，其最大響應時間的發(fā)生條件為τki的任務實例與分區(qū)Pk內所有其他任務實例在同時刻釋放，并且剛好錯過其所在分區(qū)的調度窗口，基于此來計算任務τki的到達曲線和服務曲線。算法1 給出了計算任務最大響應時間的偽代碼。

3 案例分析

設計2 個包含若干分區(qū)和任務的系統(tǒng)案例，對本文提出算法的計算結果和優(yōu)缺點進行驗證分析。

案例1 驗證本文提出的網絡演算視角下的最壞延遲分析具有與傳統(tǒng)通過迭代方式進行最壞響應時間分析的同等精度。

假設系統(tǒng)提供的總處理速率V為1 000 MIPS，系統(tǒng)共包含5 個分區(qū)以及1 個空閑時間分區(qū)，分區(qū)的參數信息如表1 所示。

表1 案例1 分區(qū)參數Table 1 Parameters of partitions in Case 1

主時間框架的長度為所有分區(qū)周期的最小公倍數［6］，結合表1 的分區(qū)參數信息，可以得出主時間框架的長度為120 ms，在主時間框架中，各分區(qū)的調度時刻如圖10 所示。

圖10 主時間框架中各分區(qū)窗口Fig.10 Partition windows within a main frame

系統(tǒng)中分區(qū)包含的任務信息如表2 所示，所有任務的釋放抖動為0，截止期限Dki等于任務周期Tki，忽略分區(qū)任務切換開銷。

使用MATLAB 中的rtc 工具箱對表2 中的分區(qū)和表3 中的任務參數信息進行建模，并生成分區(qū)和任務的到達曲線。任務到達曲線如圖11所示。

圖11 任務到達曲線Fig.11 Arrival curves of tasks

表2 案例1 任務參數信息Table 2 Parameters of tasks in Case 1

表3 案例1 所有任務的最大響應時間Table 3 WCRT for all tasks in Case 1

以任務task2-2 為例，計算任務的最大響應時間。對于任務的最大響應時間計算條件為分區(qū)內所有任務均在同一時刻到達，且剛好錯過分區(qū)窗口。假設所有任務均在0 時刻到達，那么任務分區(qū)窗口將在Tk-Lk后到達。根據各分區(qū)到達曲線計算利用式（7）、式（18）可以計算得到任務task2-2 的服務曲線，task2-2 的最大響應時間即為task2-2 的到達曲線和服務曲線的最大水平截距，如圖12 所示。

從圖12 可得task2-2 的到達曲線和服務曲線的最大水平截距為102，也即task2-2 的最大響應時間102 ms，小于截止期限120 ms，task2-2 可調度。與任務實際執(zhí)行情況是一致的。對系統(tǒng)中所有任務的最大響應時間使用本文算法進行計算并與文獻［21］所提出的精確計算任務最大響應時間的傳統(tǒng)算法、文獻［5］提出的響應時間上限快速算法的計算結果進行比較，結果如表3所示。

圖12 到達曲線和服務曲線最大水平截距Fig.12 Maximum horizontal intercept between arrival curve and service curve

文獻［21］所提出的傳統(tǒng)算法公式為

式中：Wi為任務τi的最大響應時間；Ji為釋放抖動；Ci為任務執(zhí)行時長；Ti為任務周期；hp(i)為優(yōu)先級高于τi的任務集合。

文獻［5］所提出的響應時間上限快速算法公式為

式中：Wki為任務τki的最大響應時間；Cki為任務執(zhí)行時長；TRL為主時間框架長度；ηk為分區(qū)的執(zhí)行系數。

通過表3 可以發(fā)現，本文提出的算法與傳統(tǒng)算法具有相同的精確度，相較于文獻［5］提出的響應時間上限快速算法具有更加緊湊的邊界。

案例2 在主時間框架下分區(qū)有多個激活窗口的情況下，驗證任務的可調度性分析。

假設系統(tǒng)條件與案例1 相同，修改分區(qū)參數信息如表4 所示。從分區(qū)參數信息可以看出，主時間框架為240 ms，P1、P2、P5在1個主時間框架內有2 個調度窗口，而P3，P4 在主時間框架內有一個調度窗口，在主時間框架中，各分區(qū)的調度時刻如圖13所示。任務參數信息如表5 所示。

圖13 主時間框架中各分區(qū)窗口Fig.13 Partition windows within a main frame

表4 案例2 分區(qū)參數Table 4 Parameters of partitions in Case 2

表5 案例2 任務參數信息Table 5 Parameters of tasks in Case 2

按照案例1 計算過程，分別使用本文算法、文獻［21］的傳統(tǒng)算法、文獻［5］的快速算法，計算各任務的最大響應時間，如表6 所示。

從表6 可看出3 種方法對主時間框架中只有1 個窗口的單窗口分區(qū)（P3、P4）內任務的WCRT計算結果是比較接近的，其中本文方法與傳統(tǒng)方法計算結果相同，比文獻［5］的快速算法更準確，但對多窗口分區(qū)的計算結果相差較多。文獻［21］的傳統(tǒng)算法和文獻［5］的快速算法將其他分區(qū)視為最高優(yōu)先級任務對本分區(qū)內任務的阻塞，這就會在計算時將多窗口分區(qū)的多個窗口合并，導致計算結果遠大于實際結果，而基于網絡演算的最大響應時間算法解決了這一問題。

表6 案例2 任務的最大響應時間Table 6 WCRT of tasks in Case 2

4 結論

1）針對ARINC653 規(guī)范的分區(qū)操作系統(tǒng)的任務可調度判定問題，提出了一種基于網絡演算思想的可調度性判斷方法。通過實驗分析表明，該方法能夠對分區(qū)任務兩層調度模型下任務的最大響應時間進行精確計算，計算結果的精確度與傳統(tǒng)的任務最大響應時間算法相同，為任務可調度性判定提供了數據基礎。

2）該分析方法將航空電子系統(tǒng)的網絡傳輸系統(tǒng)延遲計算模型和處理系統(tǒng)延遲計算模型進行了統(tǒng)一，使用一套計算模型即可完成對消息的端到端、任務到任務之間的延遲進行精確計算。其能夠計算分區(qū)在主時間框架中有多個激活窗口的情況，彌補了當前可調度分析算法在這一方面的不足。后續(xù)將進一步優(yōu)化算法的時間復雜度。