基于網(wǎng)絡(luò)演算的多窗口分區(qū)可調(diào)度性分析

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

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

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

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

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

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

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

1 系統(tǒng)模型

1.1 分區(qū)任務(wù)調(diào)度模型

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

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

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

1.2 網(wǎng)絡(luò)演算模型

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

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

圖2 確定性網(wǎng)絡(luò)演算模型Fig.2 Deterministic network calculus model

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

圖3 TT 流到達(dá)曲線和服務(wù)曲線Fig.3 Arrival curve and service curve of a TT flow

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

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

定義1 對(duì)于某一任務(wù)τki，設(shè)αki(t)為任務(wù)τki的到達(dá)曲線函數(shù)，βki(t)為處理平臺(tái)對(duì)τki提供的服務(wù)曲線函數(shù)，那么任務(wù)τki的最大響應(yīng)時(shí)間Wki為αki(t) 與βki(t) 的最大水平截距，即h(αki(t)，βki(t))。

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

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

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

因此任務(wù)的最大響應(yīng)時(shí)間即為任務(wù)到達(dá)曲線與服務(wù)曲線的最大水平截距。

2.1 分區(qū)任務(wù)到達(dá)曲線模型

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

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

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

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

按照ARINC 653 規(guī)范中分區(qū)調(diào)度的特點(diǎn)，分區(qū)在主時(shí)間框架中進(jìn)行具有嚴(yán)格周期的輪轉(zhuǎn)調(diào)度。考慮一分區(qū)Pk的周期為Tk，時(shí)間窗口長度為Lk，假設(shè)其第1 次到達(dá)時(shí)刻為Ak，那么該分區(qū)的調(diào)度時(shí)刻如圖5 所示。

圖5 分區(qū)調(diào)度時(shí)刻Fig.5 Partition scheduling timeline

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

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

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

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

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

根據(jù)網(wǎng)絡(luò)演算中關(guān)于到達(dá)曲線與流量累計(jì)曲線的定義可知，分區(qū)Pk在操作系統(tǒng)上的到達(dá)曲線為，其中t＞0。

2.1.2 任務(wù)到達(dá)曲線模型

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

圖7 任務(wù)到達(dá)曲線Fig.7 Arrival curve of task

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

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

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

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

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

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

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

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

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

則式（12）可簡(jiǎn)化為

依據(jù)最小加代數(shù)卷積定義有

式中：?為極小加代數(shù)中的卷積運(yùn)算；inf 為取下確界。

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

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

2.2.2 任務(wù)服務(wù)曲線模型

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

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

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

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

2.3 任務(wù)可調(diào)度性判定

任務(wù)的可調(diào)度性分析可根據(jù)任務(wù)的最大響應(yīng)時(shí)間Wki和任務(wù)截止期限D(zhuǎn)ki的關(guān)系來進(jìn)行判定，若任務(wù)τki的最大響應(yīng)時(shí)間Wki滿足Wki≤Dki，則任務(wù)可調(diào)度。任務(wù)可調(diào)度性分析轉(zhuǎn)化為求任務(wù)的最大響應(yīng)時(shí)間問題。任務(wù)的最大響應(yīng)時(shí)間依據(jù)定義1 可以通過任務(wù)的到達(dá)曲線和服務(wù)曲線的最大水平截距h(αki，βki)計(jì)算得到。

對(duì)于任務(wù)τki，其最大響應(yīng)時(shí)間的發(fā)生條件為τki的任務(wù)實(shí)例與分區(qū)Pk內(nèi)所有其他任務(wù)實(shí)例在同時(shí)刻釋放，并且剛好錯(cuò)過其所在分區(qū)的調(diào)度窗口，基于此來計(jì)算任務(wù)τki的到達(dá)曲線和服務(wù)曲線。算法1 給出了計(jì)算任務(wù)最大響應(yīng)時(shí)間的偽代碼。

3 案例分析

設(shè)計(jì)2 個(gè)包含若干分區(qū)和任務(wù)的系統(tǒng)案例，對(duì)本文提出算法的計(jì)算結(jié)果和優(yōu)缺點(diǎn)進(jìn)行驗(yàn)證分析。

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

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

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

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

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

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

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

圖11 任務(wù)到達(dá)曲線Fig.11 Arrival curves of tasks

表2 案例1 任務(wù)參數(shù)信息Table 2 Parameters of tasks in Case 1

表3 案例1 所有任務(wù)的最大響應(yīng)時(shí)間Table 3 WCRT for all tasks in Case 1

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

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

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

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

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

文獻(xiàn)［5］所提出的響應(yīng)時(shí)間上限快速算法公式為

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

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

案例2 在主時(shí)間框架下分區(qū)有多個(gè)激活窗口的情況下，驗(yàn)證任務(wù)的可調(diào)度性分析。

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

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

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

表5 案例2 任務(wù)參數(shù)信息Table 5 Parameters of tasks in Case 2

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

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

表6 案例2 任務(wù)的最大響應(yīng)時(shí)間Table 6 WCRT of tasks in Case 2

4 結(jié)論

1）針對(duì)ARINC653 規(guī)范的分區(qū)操作系統(tǒng)的任務(wù)可調(diào)度判定問題，提出了一種基于網(wǎng)絡(luò)演算思想的可調(diào)度性判斷方法。通過實(shí)驗(yàn)分析表明，該方法能夠?qū)Ψ謪^(qū)任務(wù)兩層調(diào)度模型下任務(wù)的最大響應(yīng)時(shí)間進(jìn)行精確計(jì)算，計(jì)算結(jié)果的精確度與傳統(tǒng)的任務(wù)最大響應(yīng)時(shí)間算法相同，為任務(wù)可調(diào)度性判定提供了數(shù)據(jù)基礎(chǔ)。

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