張 通，鄭 浩，朱長(zhǎng)昊，張鳳登

（上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093）

0 引言

混合關(guān)鍵級(jí)系統(tǒng)［1-4］（Mixed-Criticality Systems，MCS）在運(yùn)行資源寬裕的條件下，系統(tǒng)不再單純?yōu)楸ＷC安全關(guān)鍵性任務(wù)（高關(guān)鍵級(jí)任務(wù)）運(yùn)行，而是盡力保證非安全關(guān)鍵性任務(wù)（低關(guān)鍵級(jí)任務(wù)）的服務(wù)質(zhì)量。任務(wù)在MCS 中運(yùn)行一般通過執(zhí)行預(yù)算［5-6］（Execution Budgets）控制，所有任務(wù)運(yùn)行時(shí)都不會(huì)超過預(yù)算。任務(wù)執(zhí)行預(yù)算通常根據(jù)任務(wù)的最壞情況執(zhí)行時(shí)間（Worst Case Execution Time，WCET）進(jìn)行安排，這導(dǎo)致低關(guān)鍵級(jí)任務(wù)不必要地被賦予了一定的安全關(guān)鍵性。本文將概率性最壞情況執(zhí)行時(shí)間［7-8］（probabilistic Worst Case Execution Time，pWCET）引入傳統(tǒng)的MCS 模型，通過概率性實(shí)時(shí)分析方法研究系統(tǒng)的可調(diào)度性［9］。概率性實(shí)時(shí)分析中將任務(wù)資源調(diào)度失敗視為系統(tǒng)失效，高關(guān)鍵級(jí)任務(wù)錯(cuò)過截止期概率可設(shè)定在某個(gè)極其低的水平（如10-9/h）；低關(guān)鍵級(jí)任務(wù)則允許更高的水平（如10-6/h）?，F(xiàn)實(shí)中安全關(guān)鍵性系統(tǒng)也存在隨機(jī)性行為，如在先進(jìn)硬件架構(gòu)多級(jí)緩存中的數(shù)據(jù)隨機(jī)替換策略或倒車泊車?yán)走_(dá)中的隨機(jī)頻率聲波［10］。

本文提出了概率性需求邊界函數(shù)模型（probabilistic Demand Bound Function，pDBF），通過分析系統(tǒng)整體的資源需求過載概率來進(jìn)行可調(diào)度性分析。考慮任務(wù)執(zhí)行預(yù)算與pWCET 的聯(lián)系，說明在MCS 的不同模式下如何得到pDBF，豐富了MCS 模型；設(shè)計(jì)了針對(duì)混合關(guān)鍵級(jí)零星任務(wù)集的可調(diào)度性測(cè)試算法，分析了算法復(fù)雜度以及系統(tǒng)其他參數(shù)對(duì)可調(diào)度性的影響。

1 相關(guān)工作

文獻(xiàn)［11］提出了概率性時(shí)間需求分析方法（Probabilistic Time Demand Analysis，PTDA），針對(duì)弱實(shí)時(shí)或混合實(shí)時(shí)系統(tǒng)進(jìn)行研究；文獻(xiàn)［12］開創(chuàng)性地針對(duì)WCET 采用概率性分析方法，以避免系統(tǒng)資源過度預(yù)置；以概率性最壞情況響應(yīng)時(shí)間分析為代表，文獻(xiàn)［13-15］針對(duì)固定任務(wù)優(yōu)先級(jí)調(diào)度策略下的周期性任務(wù)系統(tǒng)采用不同于pWCET 的設(shè)定，這里假設(shè)任務(wù)所有可能執(zhí)行時(shí)間的概率分布已知。在考慮任務(wù)間概率性搶占下，計(jì)算概率性最壞情況響應(yīng)時(shí)間。相關(guān)文獻(xiàn)中任務(wù)模型拓展至包含pWCET 與pMIT。另外就是一類以實(shí)時(shí)接口（real-time interface）分析模型為基礎(chǔ)的研究，文獻(xiàn)［16］基于此提出了概率性實(shí)時(shí)演算框架（probabilistic real-time calculus），同時(shí)考慮了pWCET 與pMIT，并同樣基于需求邊界函數(shù)提出了針對(duì)EDF 調(diào)度的可調(diào)度性充分條件，但該框架僅僅從pWCET 或pMIT 的最極端部分分析出發(fā)，從而得到的是可調(diào)度性的下界。本文主要關(guān)注任務(wù)最壞情況執(zhí)行時(shí)間，用pWCET 表示，采用類似已有文獻(xiàn)的計(jì)算原理。

除了圍繞pWCET 分析外，還涉及任務(wù)概率性最小到達(dá)間隔或概率性截止期［17］；文獻(xiàn)［18］將一段時(shí)間內(nèi)任務(wù)到達(dá)次數(shù)用隨機(jī)變量表示，缺點(diǎn)是系統(tǒng)模型信息不如其他模型參數(shù)豐富。pWCET 的獲取可以使用靜態(tài)概率性時(shí)間分析（Static Probabilistic Timing Analysis，SPTA）方法。上述研究假設(shè)任務(wù)與任務(wù)之間的概率性參數(shù)獨(dú)立；pWCET 一般以整數(shù)值的離散分布形式給出，本文同樣遵循該設(shè)定。

針對(duì)固定任務(wù)優(yōu)先級(jí)調(diào)度的MCS，文獻(xiàn)［19］采用了類似文獻(xiàn)方法，通過計(jì)算每個(gè)超周期（hyperperiod）內(nèi)所有任務(wù)的錯(cuò)過截止期概率得到可調(diào)度的分析結(jié)果；此外文獻(xiàn)［20］改進(jìn)混合關(guān)鍵級(jí)系統(tǒng)中SMC 與AMC 策略，計(jì)算所有模式下任務(wù)的錯(cuò)過截止期概率；針對(duì)EDF 調(diào)度，文獻(xiàn)［21］根據(jù)pWCET 設(shè)定了預(yù)算超出概率，改善了系統(tǒng)的可調(diào)度性；部分研究將概率性實(shí)時(shí)分析引入能耗約束的MCS 調(diào)度設(shè)計(jì)中，文獻(xiàn)［22］提出了基于測(cè)量估計(jì)的概率性分析來估計(jì)任務(wù)最壞情況下的能量消耗（Worst-Case Energy Consumption，WCEC），但沒有結(jié)合具體的能耗資源管理算法；Bhuiyan 等［23］基于概率性方法提出了能耗影響的速率控制，并結(jié)合動(dòng)態(tài)電壓頻率調(diào)節(jié)技術(shù)（Dynamic Voltage and Frequency Scaling，DVFS）實(shí)現(xiàn)了系統(tǒng)能耗最小化；關(guān)于多核處理器平臺(tái)MCS，文獻(xiàn)［24］基于概率性的DAG 分析量化MCS 中低關(guān)鍵級(jí)任務(wù)；Zeng 等［25］在同構(gòu)多核處理器平臺(tái)上，提出了概率性混合關(guān)鍵級(jí)任務(wù)模型，得到相應(yīng)的任務(wù)分區(qū)算法PPDC，使低關(guān)鍵級(jí)任務(wù)運(yùn)行得到提升。本文提出的概率性需求邊界函數(shù)模型，可計(jì)算任務(wù)系統(tǒng)在調(diào)度周期內(nèi)的資源需求過載概率，在避免資源過度預(yù)置的同時(shí)改善系統(tǒng)可調(diào)度性。

2 符號(hào)與模型定義

2.1 符號(hào)定義與概念

pWCET 為整數(shù)取值的離散型隨機(jī)變量，可用概率質(zhì)量函數(shù)（Probability Mass Function，PMF）表示，即f（ici）=P（Ci=ci）=pi，i=0，1，…，k，或記為：

規(guī)范假設(shè)c0＜c1＜…＜ck，Ci的范圍為［cmin，cmax］。pi須滿足pi≥0，i=1，2，…，k，且Σk i=1pi=1。概率分布函數(shù)（Cumulative Distribution Function，CDF）表示隨機(jī)變量小于某個(gè)值的概率和，即F（ix）=Σx y=xminf（iy），x∈［cmin，∞）。兩個(gè)相互獨(dú)立隨機(jī)變量X 與Y 的卷積和定義為P（Z=z）=Σ∞k=-∞P（X=k）P（Y=z-k），記為Z=X?Y；相應(yīng)卷積差記為Z=X?Y=X?（-Y）；若干部分概率和為1 的隨機(jī)變量分布的合并稱為聯(lián)合，記為Z=X⊕Y。

隨機(jī)變量X1和X2間的比較，若對(duì)任意x 兩個(gè)隨機(jī)變量的CDF 滿足FX（1x）≤FX（2x），則稱X1大于等于X2，記為X1?X2，在CDF 曲線上X1始終位于X2下方；反之稱X1小于等于X2，記為X1?X2。約定x 與y 最大值為?x?y，x 與y 最小值為?x?y。

2.2 任務(wù)系統(tǒng)模型

在單處理器硬件平臺(tái)上，任務(wù)系統(tǒng)由一組個(gè)數(shù)為n 的零星任務(wù)集τ=｛τ1，τ2，…，τn｝構(gòu)成。單個(gè)任務(wù)τi用（Ti，Di，Ci，Li）元組定義，分別表示任務(wù)周期、概率性最壞情況執(zhí)行時(shí)間、相對(duì)截止期以及任務(wù)關(guān)鍵級(jí)。系統(tǒng)實(shí)際運(yùn)行是通過設(shè)置執(zhí)行預(yù)算的方式，所有任務(wù)在低關(guān)鍵級(jí)模式下執(zhí)行預(yù)算為Bi。本文限制為雙關(guān)鍵級(jí)系統(tǒng)，即Li=｛LO，HI｝。任務(wù)τi的 第j個(gè) 作 業(yè) 記 為Ji，j。任 務(wù)Di≤Ti，cmax≤Di。任 務(wù) 與 任務(wù)之間不存在順序或互斥關(guān)系；任務(wù)不同作業(yè)之間相互獨(dú)立。

定義低關(guān)鍵級(jí)任務(wù)子集τL=｛τi∈τ|Li=LO｝，高關(guān)鍵級(jí)任務(wù)子集τH=｛τi∈τ|Li=HI｝。定義任務(wù)τi的平均利用率與系統(tǒng)τ的平均利用率為：

系統(tǒng)從低關(guān)鍵級(jí)模式開始運(yùn)行，當(dāng)任務(wù)作業(yè)實(shí)際執(zhí)行時(shí)間未超過執(zhí)行預(yù)算Bi時(shí)，系統(tǒng)處于低關(guān)鍵級(jí)模式；當(dāng)高關(guān)鍵級(jí)作業(yè)執(zhí)行超過其Bi時(shí)，提升系統(tǒng)關(guān)鍵級(jí)模式。上述系統(tǒng)模式切換是基于內(nèi)部觸發(fā)的機(jī)制，還有一種外部觸發(fā)機(jī)制［26］，后者認(rèn)為外部事件也能導(dǎo)致系統(tǒng)被動(dòng)地提升關(guān)鍵級(jí)。模式切換后所有低關(guān)鍵級(jí)任務(wù)作業(yè)會(huì)被拋棄，并且在高關(guān)鍵級(jí)模式下不會(huì)釋放；系統(tǒng)運(yùn)行在高關(guān)鍵級(jí)模式時(shí)，若出現(xiàn)調(diào)度空閑，則系統(tǒng)關(guān)鍵級(jí)回落。

3 概率性需求邊界函數(shù)

3.1 概率性需求邊界函數(shù)定義

對(duì)于零星或周期任務(wù)，任意時(shí)間范圍Δ內(nèi)，任務(wù)τi的需求邊界函數(shù)［27］（Demand Bound Function，DBF）為：

其中，Ci是任務(wù)WCET，從而系統(tǒng)τ的需求邊界函數(shù)為：

對(duì)于固定速率單處理器，任意時(shí)間范圍Δ內(nèi)系統(tǒng)提供資源可用供給邊界函數(shù)［28］（Supply Bound Function，SBF）來描述，即：

定理1：若任務(wù)系統(tǒng)τ在任意時(shí)間范圍Δ內(nèi)的需求邊界函數(shù)總是不大于系統(tǒng)的供給邊界函數(shù)，則在EDF 算法調(diào)度下任務(wù)系統(tǒng)τ是可調(diào)度的，即滿足：

定義1：若任務(wù)的最壞情況執(zhí)行時(shí)間使用pWCET 描述，則任意時(shí)間范圍Δ內(nèi)，該任務(wù)的需求邊界函數(shù)簇可以用概率性需求邊界函數(shù)（pDBF）描述如下：

通過例1 說明pDBF 暫時(shí)不設(shè)任務(wù)關(guān)鍵級(jí)。將DBF 分析中使用的WCET 設(shè)為表1 中黑色方框內(nèi)數(shù)值，此時(shí)系統(tǒng)利用率大于1，在EDF 算法下不可調(diào)度［29］。

Table 1 Model task set of example 1-pDBF表1 例1pDBF 模型任務(wù)集

以Δ=10 為例，按式（1）和式（2），任務(wù)系統(tǒng)DBF 為11，任務(wù)系統(tǒng)不可調(diào)度；同樣對(duì)于Δ = 10，各個(gè)任務(wù)的pDBF 分別為：

整個(gè)任務(wù)系統(tǒng)的pDBF 為：

圖1 表示一個(gè)超周期內(nèi)任務(wù)系統(tǒng)的DBF 和pDBF。任務(wù)系統(tǒng)pDBF 所有可能值如圖中灰度部分所示，對(duì)應(yīng)概率越大則灰度越深。隨著時(shí)間范圍的增大，出現(xiàn)極端資源需求情況的概率越來越小。pDBF 模型仍然包含了DBF 模型中所有信息，任務(wù)系統(tǒng)在Δ=10 時(shí)發(fā)生資源需求過載的概率（Demand Overload Probability，DOP）為0.000 2，如果允許任務(wù)系統(tǒng)以不大于某個(gè)概率閾值HT發(fā)生資源需求過載，如0.001，那么例1 的可調(diào)度性將放寬。

Fig.1 The pDBF of the example task set and the compared DBF圖1 示例任務(wù)集的pDBF 和與其相比較的DBF

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

先給出幾個(gè)相關(guān)定義。某個(gè)任務(wù)τi=（Ti，Di，Ci）的第j次作業(yè)記為Ji，j=（ti，j，ri，j），ti，j表示作業(yè)釋放時(shí)刻，ri，j表示作業(yè)響應(yīng)完成時(shí)刻，如果Ji，j完成時(shí)刻大于其絕對(duì)截止期時(shí)刻，即ri，j＞ti，j+Di，則所有可能的ri，j對(duì)應(yīng)的概率之和稱為Ji，j錯(cuò)過截止期概率（Deadline Miss Probability，DMP），即DMPi，j=P（Ri，j＞ti，j+Di），Ri，j表示作業(yè)Ji，j所有可能最壞響應(yīng)完成時(shí)刻所構(gòu)成的隨機(jī)變量。

定義2：對(duì)任意時(shí)間范圍Δ，若任務(wù)系統(tǒng)τ的需求邊界函數(shù)大于供給邊界函數(shù)，則稱任務(wù)系統(tǒng)發(fā)生需求過載；任務(wù)系統(tǒng)pDBF 大于SBF 這部分概率和的最大值，稱τ為在Δ內(nèi)的需求過載概率，記為DOPτ，Δ，即：

下面證明一個(gè)引理，將DOPτ，Δ與任務(wù)作業(yè)的DMPi，j聯(lián)系起來。

引理1若任務(wù)系統(tǒng)τ在任意時(shí)間范圍Δ內(nèi)的需求過載概率DOPτ，Δ不大于某個(gè)概率閾值HT，則在該時(shí)間范圍Δ內(nèi)所有任務(wù)作業(yè)錯(cuò)過截止期概率也一定不大于HT，即滿足：

其中任務(wù)作業(yè)須滿足ti，j+Di≤Δ。

證明：首先考慮Δ≥max｛D1，D2，…，Dn｝=Dmax的情況。設(shè)τ在Δ內(nèi)的DOPτ，Δ≤HT但大于0，根據(jù)定理1，任務(wù)作業(yè)錯(cuò)過截止期的可能性是必然存在的。將系統(tǒng)報(bào)告出現(xiàn)調(diào)度失效的最早時(shí)刻記為tf∈（Dmax，Δ］，則HT≤DOPτ，tf≤DOPτ，Δ。在tf時(shí)刻之前根據(jù)EDF 調(diào)度策略，以tf為絕對(duì)截止期的任務(wù)作業(yè)將在所有之前已釋放作業(yè)中被調(diào)度。設(shè)這部分作業(yè)為Jri,j=tf=｛J1，J2，…，Jm｝（來自不同任務(wù)省去作業(yè)序號(hào)下標(biāo)），此時(shí)錯(cuò)過截止期的作業(yè)全部或至少一個(gè)來自Jri,j=tf。以tf之前時(shí)刻為絕對(duì)截止期的任務(wù)作業(yè)，自然在tf之前就完成調(diào)度或者報(bào)告調(diào)度失敗，這里分兩種情況討論：

情況1：只有作業(yè)J1在tf時(shí)刻可能錯(cuò)過截止期，J1錯(cuò)過截止期的概率為DMP1，顯然DOPτ，tf=DMP1。

情況2：可能錯(cuò)過截止期的作業(yè)有k（≤m）個(gè)，錯(cuò)過截止期概率分別為DMP1，DMP2，…，DMPk。由于作業(yè)絕對(duì)截止期都相同，所以任務(wù)ID 最小的作業(yè)盡管已經(jīng)被優(yōu)先調(diào)度，但仍可能以DMP1概率錯(cuò)過截止期，其他優(yōu)先級(jí)更低的任務(wù)將肯定得不到調(diào)度而錯(cuò)過截止期，所以有DMP1≤DMP2≤…≤DMPk。任何無法完成調(diào)度的作業(yè)最后都會(huì)造成DOP不為0，所以DOPτ，tf=max｛DMP1，DMP2，…，DMPk｝=DMPk。

Δ＜max｛D1，D2，…，Dn｝相當(dāng)于縮小任務(wù)集范圍，上述分析同樣適用。綜上所述，HT≥DOPτ，Δ≥DOPτ，tf≥DMPi，j，?Δ≥0，?τi∈τ。

將例1 中任務(wù)截止期進(jìn)一步設(shè)值為D1=3，D2=7，D3=7。圖2 考慮Δ=8 這一情況，t7時(shí)刻就是該情況下的tf，此時(shí)任務(wù)Jri,j=tf=｛J1，J2｝，分別屬于τ2與τ3。此時(shí)DMP2=0，DMP3=0.02，DOPτ，Δ=0.0226。

Fig.2 An example of the relationship between system DOP and task DMP圖2 系統(tǒng)DOP 與任務(wù)作業(yè)DMP 的關(guān)系說明示例

綜上，DOP 比基于DMP 的分析更加可靠，由此得出可調(diào)度性結(jié)論：若在任意時(shí)間范圍Δ內(nèi)，任務(wù)系統(tǒng)τ的概率性需求邊界函數(shù)pDBF 可以在其DOP 不大于某一閾值HT的條件下滿足Δ內(nèi)的資源供給，則認(rèn)為系統(tǒng)是可調(diào)度的。

4 混合關(guān)鍵級(jí)任務(wù)的概率性需求邊界函數(shù)

MCS 的任務(wù)調(diào)度常采用EDF-VD［30］的調(diào)度策略。利用縮短后的虛擬截止期DLO i 來弱化模式切換給系統(tǒng)DBF帶來的影響。對(duì)于τi∈τH，有DLO i≤Di，DLO i?Ci。首先提出MCS 的可調(diào)度性命題：

命題1：對(duì)于一個(gè)使用pWCET 參數(shù)的混合關(guān)鍵級(jí)系統(tǒng)任務(wù)集τ，在EDF 算法調(diào)度下，若系統(tǒng)在高關(guān)鍵級(jí)模式以及低關(guān)鍵級(jí)模式下，其資源需求過載概率都不大于給定的可調(diào)度性概率閾值HT，則認(rèn)為任務(wù)系統(tǒng)是可調(diào)度的，即：

證明：若任務(wù)被允許以極其微小概率HT錯(cuò)過其截止期，則等同于系統(tǒng)運(yùn)行平均失效時(shí)間必須大于設(shè)計(jì)者給定的系統(tǒng)運(yùn)行預(yù)期壽命。為保證高關(guān)鍵級(jí)任務(wù)在所有模式下都有相同程度的可靠性保證，HT的所有模式是統(tǒng)一的?；谶@樣的系統(tǒng)可靠性保證，結(jié)合引理1，原命題為真。

4.1 根據(jù)任務(wù)執(zhí)行預(yù)算重構(gòu)任務(wù)的pWCET

圖3 為重構(gòu)任務(wù)的pWCET 概率分布，在低關(guān)鍵級(jí)模式下pDBF 中使用C LO i，在高關(guān)鍵級(jí)模式下仍使用完整的Ci，這體現(xiàn)預(yù)算Bi對(duì)系統(tǒng)的控制作用。對(duì)于τi∈τL，一但運(yùn)行超過Bi就會(huì)被調(diào)度器中止，所以重構(gòu)將超出Bi部分的概率堆疊到Bi處；對(duì)于τi∈τH，運(yùn)行超過Bi會(huì)使系統(tǒng)提升關(guān)鍵級(jí)，但這部分需求考慮在高關(guān)鍵級(jí)模式分析中，所以重構(gòu)將這部分概率堆疊到0。任務(wù)Bi的設(shè)置存在天然矛盾性：Bi設(shè)置過小，低關(guān)鍵級(jí)任務(wù)運(yùn)行的服務(wù)質(zhì)量將惡化，高關(guān)鍵級(jí)任務(wù)更易預(yù)算超支；Bi設(shè)置過大將損害低關(guān)鍵級(jí)模式的可調(diào)度性。

Fig.3 Reconstructing C LO i based on task pWCET for pDBF computation of task system圖3 根據(jù)任務(wù)的pWCET 重構(gòu)C LO i 以用于任務(wù)系統(tǒng)的pDBF 計(jì)算

4.2 結(jié)轉(zhuǎn)作業(yè)資源需求分析

任何高關(guān)鍵級(jí)任務(wù)在系統(tǒng)發(fā)生模式切換時(shí)，都可能存在結(jié)轉(zhuǎn)任務(wù)J?i，可將J?i視為在模式切換時(shí)釋放的新作業(yè)。

在保證高關(guān)鍵級(jí)作業(yè)在可調(diào)度條件下，必須進(jìn)行最壞情況分析。假設(shè)J?i 會(huì)被盡可能遲地釋放，即J?i 在原來低關(guān)鍵級(jí)模式下調(diào)度時(shí)恰好在截止期前完成，但J?i 在系統(tǒng)切換為高關(guān)鍵級(jí)模式后其執(zhí)行時(shí)間大于Bi的概率一定大于0，即τi超過執(zhí)行預(yù)算Bi的概率。

如圖4 所示，J?i 可能包含的情況有3 部分：①作業(yè)在模式切換前可能已經(jīng)執(zhí)行；②在剩余調(diào)度窗口l?i 內(nèi)為原低關(guān)鍵級(jí)模式下剩余的執(zhí)行需求；③由于模式切換而導(dǎo)致突然增加的執(zhí)行需求（這種情況一定存在）。下面將例1 中任務(wù)τ2拓展為例2（見表2），并分析J?i 的執(zhí)行需求C?2。

Fig.4 Worst case scenario of carry-over job圖4 結(jié)轉(zhuǎn)作業(yè)可能出現(xiàn)的最壞情況

Table 2 Model task τ2 of example 2-pDBF表2 例2-pDBF 模型任務(wù)τ2

J?2在未發(fā)生模式切換時(shí)，其截止期前至多滿足B2個(gè)單位的資源需求。l?2 滿足0≤l?2＜Di=8，以l?2=2 為例，對(duì)C2各個(gè)部分分別分析。對(duì)于c1=1＜l?2，從最壞情況考慮，把它歸類到如圖4 所示的第②部分，得到C ，?，head2；對(duì)于l?2＜c2=3≤B2，由于在剩余執(zhí)行窗口內(nèi)至多執(zhí)行l(wèi)?2 個(gè)單位，則至少有1 個(gè)單位已經(jīng)被執(zhí)行了，即包含了圖4 中的①、②部分，得到C ，?，mid2；對(duì)于l?2＜B2＜c3=5，由于至多保證B2個(gè)單位執(zhí)行需求被滿足，所以有c3-B2= 2 個(gè)單位無法得到滿足，包含在第①、②、③部分中。得到C，?，tail2如下：

但無論l?2 多長(zhǎng)，肯定包含第③部分，這導(dǎo)致無法滿足HT的約束，而EDF-VD 調(diào)度算法可緩解這一問題。

為了給第③部分執(zhí)行預(yù)留空間，采用EDF-VD 調(diào)度算法為每個(gè)高關(guān)鍵級(jí)任務(wù)設(shè)置虛擬截止期DLO （iCi?DLO i≤D）i。如圖5所示，使用虛擬截止期后J?i獲得更長(zhǎng)調(diào)度窗口。

引理2（結(jié)轉(zhuǎn)作業(yè)的執(zhí)行需求）：對(duì)于高關(guān)鍵級(jí)任務(wù)τi∈τH的作業(yè)，其在低關(guān)鍵級(jí)模式以及高關(guān)鍵級(jí)模式下的EDF調(diào)度分別根據(jù)DLO i 與Di進(jìn)行。若在低關(guān)鍵級(jí)模式下，系統(tǒng)的資源需求可以得到滿足，則模式切換后其結(jié)轉(zhuǎn)作業(yè)J?i 的剩余調(diào)度窗口長(zhǎng)度為l?i≥0，則有：

（1）若l?i＜Di-DLO i，表示該作業(yè)在模式切換前已經(jīng)完成，不用進(jìn)行作業(yè)結(jié)轉(zhuǎn)。

（2）若l?i≥Di-DLO i，表示該作業(yè)必然為一個(gè)結(jié)轉(zhuǎn)作業(yè)，即在模式切換后該作業(yè)仍有執(zhí)行需求C?i，且C?i 如式（19）、式（20）所示，其中l(wèi)?’i=l?i-（Di-DLO i）。

證明：對(duì)于l?i＜Di-DLO i，表示模式切換發(fā)生在虛擬截止期DLO i 之后，所以作業(yè)在模式切換前已完成，不用作業(yè)結(jié)轉(zhuǎn)；對(duì)于l?i≥Di-DLO i，當(dāng)0≤l?i′＜Bi時(shí)，由于l?i′不足以完成Bi個(gè)執(zhí)行需求，所以必然有部分需求已執(zhí)行，C?i 須扣除這部分，所以C?i 包含①、②、③部分；對(duì)于Bi≤l?i′＜DLO i，須把整個(gè)執(zhí)行預(yù)算內(nèi)的需求放在l?i′內(nèi)考慮，不包含第①部分，C?i 包含第②、第③部分。如圖5 所示。

Fig.5 By using virtual deadline to left more scheduling windows for J ?2圖5 通過使用虛擬截止期為J?2 空出更多的調(diào)度窗口

4.3 不同模式下系統(tǒng)的pDBF

在低關(guān)鍵級(jí)模式下，系統(tǒng)成為標(biāo)準(zhǔn)的零星任務(wù)系統(tǒng)，其低關(guān)鍵級(jí)模式下任務(wù)系統(tǒng)的pDBF 為：

l?i 越長(zhǎng)表示越可能存在結(jié)轉(zhuǎn)作業(yè)。如圖6 所示，為了更多地考慮任務(wù)作業(yè)，可將完整的任務(wù)作業(yè)在Δ內(nèi)盡可能往后排，以空出盡可能大的l?i，長(zhǎng)度為Δ modTi。當(dāng)l?i＜Di-DLO i 時(shí)，J?i 不存在；Bi+（Di-DLO i）≤l?i＜Di時(shí)，l?i 可以容納一個(gè)完整作業(yè)，J?i 等同一個(gè)正常作業(yè)；Di-DLO i≤l?i＜Bi+（Di-DLO i）時(shí)，須考慮有一個(gè)結(jié)轉(zhuǎn)作業(yè)情況。綜上，高關(guān)鍵級(jí)模式下pDBF 可表示為：

其中

Fig.6 The worst case distribution of high critical job圖6 高關(guān)鍵級(jí)任務(wù)作業(yè)的最壞排布情況

5 實(shí)驗(yàn)結(jié)果與分析

5.1 生成實(shí)驗(yàn)任務(wù)集

隨機(jī)實(shí)驗(yàn)任務(wù)集生成參數(shù)設(shè)置如下：①任務(wù)關(guān)鍵級(jí)Li：CP 表示生成任務(wù)為高關(guān)鍵級(jí)任務(wù)的概率，默認(rèn)為CP = 0.5；任務(wù)周期Ti設(shè)置為25·ω，汽車或航空器中常見的實(shí)時(shí)任務(wù)周期一般為20～1 000ms，所以ω隨機(jī)選擇［1，40］范圍的整數(shù)；②任務(wù)平均利用率Uavgτi基于UUnifast 算法［31］生成；③任 務(wù)Ci：根據(jù)=Ti·Uavgτi以及隨機(jī)生成的WCET參數(shù)cmaxi∈［1.1i，2Cˉ］i，按內(nèi)推插值法生成序列（c0，c1，…，cmax）；Ci沒有具體分布，唯一的限制是在分布上呈遞減趨勢(shì)，這里按指數(shù)型衰減生成；④任務(wù)執(zhí)行預(yù)算Bi：根據(jù)任務(wù)執(zhí)行概率閾值PT選擇，即滿足P（Ci≥Bi）=PT，PT默認(rèn)為10-5；⑤任務(wù)截止期Di、虛擬截止期DLO i：Di=Ti；DLO i 在［Bi，Ti］內(nèi)隨機(jī)選取。

5.2 算法復(fù)雜度實(shí)驗(yàn)

為盡可能徹底測(cè)試所提出的可調(diào)度性測(cè)試算法的時(shí)間復(fù)雜度，將任務(wù)集的任務(wù)個(gè)數(shù)在2～15 范圍內(nèi)變化，任務(wù)pWCET 長(zhǎng)度在2～15 范圍內(nèi)變化。任務(wù)集平均利用率Uavgτ 從0.05～1.05 隨機(jī)產(chǎn)生；可調(diào)度性概率閾值HT在實(shí)驗(yàn)開始時(shí)從［10-6，10-5］中隨機(jī)選擇，實(shí)驗(yàn)結(jié)果如圖7 所示。z軸表示算法測(cè)試所用時(shí)間，空間中每個(gè)實(shí)驗(yàn)數(shù)據(jù)點(diǎn)取100個(gè)隨機(jī)任務(wù)集平均測(cè)試時(shí)間；算法運(yùn)行時(shí)間與任務(wù)集個(gè)數(shù)以及pWCET 參數(shù)長(zhǎng)度呈指數(shù)關(guān)系，任務(wù)集個(gè)數(shù)對(duì)運(yùn)行時(shí)間影響更突出，這是因?yàn)闇y(cè)試算法的外循環(huán)次數(shù)為HP+1，內(nèi)循環(huán)次數(shù)為任務(wù)集中任務(wù)個(gè)數(shù)，基本運(yùn)算操作為對(duì)隨機(jī)變量的卷積和，所以前者影響更大。綜上所述，當(dāng)測(cè)試任務(wù)集平均利用率大于1 時(shí)，算法運(yùn)行在線性時(shí)間復(fù)雜度上，其他情況下則運(yùn)行在偽多項(xiàng)式時(shí)間復(fù)雜度上。所以應(yīng)盡量減小超周期，比如通過取冪值方式。

對(duì)于臨界時(shí)刻釋放的周期或零星任務(wù)系統(tǒng)，盡管采用了pWCET 參數(shù)，但在一個(gè)超周期內(nèi)分析同樣有效。測(cè)試范圍至少應(yīng)為一個(gè)超周期，因?yàn)樵贒BF 模型分析下，lmax指DOP＞0 的最早時(shí)刻，而在pDBF 分析下，指DOP＞HT的最早時(shí)刻；另外算法是基于系統(tǒng)不同模式下的平均利用率判定，這利用了隨機(jī)過程中的更新報(bào)酬定理［32］。

算法1：可調(diào)度性測(cè)試算法

輸入：MCS 零星任務(wù)集τ=｛τ1，τ2，…，τn｝，可調(diào)度性概率閾值HT，任務(wù)系統(tǒng)超周期HP=lcm｛T1，T2，…，Tn｝；

輸出：可調(diào)度性分析結(jié)果（“schedulable or not schedulable”）。

Fig.7 Executing time of schedulability testing algorithm圖7 可調(diào)度性測(cè)試算法運(yùn)行時(shí)間

ULO avg←CalcuTaskUavg（τL）；/*LO-模式平均利用率*/

UHI avg←CalcuTaskUavg（τH）；/*HI-模式平均利用率*/

ifULO avg＞1||UHI avg＞1 then return（“not schedulable”）；

end if

fort：= 0 ToHPdo

fori：= 1 To ndo

Lr ←tModTi；/*最大剩余調(diào)度窗口長(zhǎng)度*/

if Lr==DLO i then

pdbfLO τ←pdbfLO τ?CLO i；/*LO-模式系統(tǒng)10.pDBF*/

end if

ifLi==HI&&Di-DLO i≤Lr ≤Bi+Di-DLO i then

if Lr==Bi+Di-DLO i then

pdbfHI_full τ←pdbfHI_full τ?C i；

else

pdbfHI_?τ←pdbfHI_?τ?C ?i；/*結(jié)轉(zhuǎn)作業(yè)pDBF*/

end if

end if

end for

pdbfHI τ←pdbfHI_full τ?pdbfHI_?τ；/*HI-模式系統(tǒng)pDBF*/

DOPτ，t←FindMaxDop（pdbfLO τ，pdbfHI τ）；

if DOPτ，t＞HTthen return（“not schedulable”）；

end if

end for

return（“schedulable”）；

5.3 仿真實(shí)驗(yàn)

所有任務(wù)的截止期等于其周期，下面分析pWCET 參數(shù)長(zhǎng)度、系統(tǒng)可調(diào)度性概率閾值HT以及系統(tǒng)高關(guān)鍵級(jí)任務(wù)概率CP 等系統(tǒng)參數(shù)對(duì)可調(diào)度性性能的影響。任務(wù)集包含10個(gè)任務(wù)，系統(tǒng)平均利用率以0.05 的步長(zhǎng)從0.05 變化到1.0，每個(gè)實(shí)驗(yàn)數(shù)據(jù)點(diǎn)測(cè)試100 個(gè)隨機(jī)任務(wù)集。

（1）改變?nèi)蝿?wù)pWCET 參數(shù)長(zhǎng)度。使用重抽樣技術(shù)［33］，在不降低參數(shù)可靠性前提下縮減任務(wù)的pWCET 參數(shù)長(zhǎng)度，當(dāng)長(zhǎng)度抽樣為1 時(shí)使用傳統(tǒng)的DBF 方法分析。

如圖8 所示，Uavgτ 較小時(shí)（0.05～0.55），pWCET 長(zhǎng)度對(duì)于可調(diào)度性沒有顯著改善。而當(dāng)利用率增大時(shí)，確定性分析（虛線）的可調(diào)度性狀況迅速惡化，但在不同pWCET 長(zhǎng)度下的可調(diào)度性仍有較大提升。但是當(dāng)pWCET 長(zhǎng)度大于8后，這種提升就變得十分有限。

Fig.8 Changing the pWCET parameter length of the task（by re-sampling）圖8 改變?nèi)蝿?wù)的pWCET 參數(shù)長(zhǎng)度（通過重抽樣方法）

（2）改變系統(tǒng)可調(diào)度性概率閾值HT。施加越嚴(yán)格的可調(diào)度性概率閾值，系統(tǒng)越可靠。

圖9 中，HT越寬松，系統(tǒng)的可調(diào)度性越好，但是在系統(tǒng)平均利用率特別?。?.05～0.25）或特別大（0.95～1.00）時(shí)，這種表現(xiàn)并不突出。

Fig.9 Changing the probability threshold of system schedulability HT圖9 改變系統(tǒng)可調(diào)度性概率閾值HT

（3）改變系統(tǒng)高關(guān)鍵級(jí)任務(wù)概率CP。提高系統(tǒng)高關(guān)鍵級(jí)任務(wù)的比例會(huì)增大系統(tǒng)高關(guān)鍵級(jí)模式下的pDBF。

從圖10 可以發(fā)現(xiàn)，在改變Uavgτ 的同時(shí)，不同的CP可調(diào)度性性能之間相對(duì)地位幾乎沒有改變，說明CP對(duì)于可調(diào)度性的影響比較獨(dú)立。

Fig.10 Changing the system high critical level task probability CP圖10 改變系統(tǒng)高關(guān)鍵級(jí)任務(wù)概率CP

6 結(jié)語(yǔ)

傳統(tǒng)MCS 默認(rèn)依據(jù)任務(wù)的WCETs 來安排執(zhí)行預(yù)算，這種方法會(huì)產(chǎn)生資源過度預(yù)置問題，而一般MCS 低關(guān)鍵級(jí)任務(wù)執(zhí)行的可靠性要求不像高關(guān)鍵級(jí)任務(wù)要求那么高。本文首先分析并提出了概率性需求邊界函數(shù)（pDBF）模型，分析了MCS 不同模式下的pDBF，尤其是系統(tǒng)模式切換時(shí)結(jié)轉(zhuǎn)作業(yè)的執(zhí)行需求。實(shí)驗(yàn)表明，通過對(duì)Ci重采樣或者選擇合適的HT，可調(diào)度接受率可以提高32%，同時(shí)降低了pDBF模型下分析算法的復(fù)雜度。未來可采用實(shí)時(shí)接口分析（real-time interface analysis）方法，將本文方法拓展至固定任務(wù)優(yōu)先級(jí)調(diào)度系統(tǒng)中。