張 通，鄭 浩，朱長昊，張鳳登

（上海理工大學光電信息與計算機工程學院，上海 200093）

0 引言

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

本文提出了概率性需求邊界函數模型（probabilistic Demand Bound Function，pDBF），通過分析系統整體的資源需求過載概率來進行可調度性分析?？紤]任務執(zhí)行預算與pWCET 的聯系，說明在MCS 的不同模式下如何得到pDBF，豐富了MCS 模型；設計了針對混合關鍵級零星任務集的可調度性測試算法，分析了算法復雜度以及系統其他參數對可調度性的影響。

1 相關工作

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

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

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

2 符號與模型定義

2.1 符號定義與概念

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

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

隨機變量X1和X2間的比較，若對任意x 兩個隨機變量的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 任務系統模型

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

定義低關鍵級任務子集τL=｛τi∈τ|Li=LO｝，高關鍵級任務子集τH=｛τi∈τ|Li=HI｝。定義任務τi的平均利用率與系統τ的平均利用率為：

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

3 概率性需求邊界函數

3.1 概率性需求邊界函數定義

對于零星或周期任務，任意時間范圍Δ內，任務τi的需求邊界函數［27］（Demand Bound Function，DBF）為：

其中，Ci是任務WCET，從而系統τ的需求邊界函數為：

對于固定速率單處理器，任意時間范圍Δ內系統提供資源可用供給邊界函數［28］（Supply Bound Function，SBF）來描述，即：

定理1：若任務系統τ在任意時間范圍Δ內的需求邊界函數總是不大于系統的供給邊界函數，則在EDF 算法調度下任務系統τ是可調度的，即滿足：

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

通過例1 說明pDBF 暫時不設任務關鍵級。將DBF 分析中使用的WCET 設為表1 中黑色方框內數值，此時系統利用率大于1，在EDF 算法下不可調度［29］。

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

以Δ=10 為例，按式（1）和式（2），任務系統DBF 為11，任務系統不可調度；同樣對于Δ = 10，各個任務的pDBF 分別為：

整個任務系統的pDBF 為：

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

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

3.2 可調度性分析

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

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

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

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

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

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

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

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

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

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

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

綜上，DOP 比基于DMP 的分析更加可靠，由此得出可調度性結論：若在任意時間范圍Δ內，任務系統τ的概率性需求邊界函數pDBF 可以在其DOP 不大于某一閾值HT的條件下滿足Δ內的資源供給，則認為系統是可調度的。

4 混合關鍵級任務的概率性需求邊界函數

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

命題1：對于一個使用pWCET 參數的混合關鍵級系統任務集τ，在EDF 算法調度下，若系統在高關鍵級模式以及低關鍵級模式下，其資源需求過載概率都不大于給定的可調度性概率閾值HT，則認為任務系統是可調度的，即：

證明：若任務被允許以極其微小概率HT錯過其截止期，則等同于系統運行平均失效時間必須大于設計者給定的系統運行預期壽命。為保證高關鍵級任務在所有模式下都有相同程度的可靠性保證，HT的所有模式是統一的。基于這樣的系統可靠性保證，結合引理1，原命題為真。

4.1 根據任務執(zhí)行預算重構任務的pWCET

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

Fig.3 Reconstructing C LO i based on task pWCET for pDBF computation of task system圖3 根據任務的pWCET 重構C LO i 以用于任務系統的pDBF 計算

4.2 結轉作業(yè)資源需求分析

任何高關鍵級任務在系統發(fā)生模式切換時，都可能存在結轉任務J?i，可將J?i視為在模式切換時釋放的新作業(yè)。

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

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

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

Table 2 Model task τ2 of example 2-pDBF表2 例2-pDBF 模型任務τ2

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

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

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

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

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

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

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

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

4.3 不同模式下系統的pDBF

在低關鍵級模式下，系統成為標準的零星任務系統，其低關鍵級模式下任務系統的pDBF 為：

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

其中

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

5 實驗結果與分析

5.1 生成實驗任務集

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

5.2 算法復雜度實驗

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

對于臨界時刻釋放的周期或零星任務系統，盡管采用了pWCET 參數，但在一個超周期內分析同樣有效。測試范圍至少應為一個超周期，因為在DBF 模型分析下，lmax指DOP＞0 的最早時刻，而在pDBF 分析下，指DOP＞HT的最早時刻；另外算法是基于系統不同模式下的平均利用率判定，這利用了隨機過程中的更新報酬定理［32］。

算法1：可調度性測試算法

輸入：MCS 零星任務集τ=｛τ1，τ2，…，τn｝，可調度性概率閾值HT，任務系統超周期HP=lcm｛T1，T2，…，Tn｝；

輸出：可調度性分析結果（“schedulable or not schedulable”）。

Fig.7 Executing time of schedulability testing algorithm圖7 可調度性測試算法運行時間

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；/*最大剩余調度窗口長度*/

if Lr==DLO i then

pdbfLO τ←pdbfLO τ?CLO i；/*LO-模式系統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；/*結轉作業(yè)pDBF*/

end if

end if

end for

pdbfHI τ←pdbfHI_full τ?pdbfHI_?τ；/*HI-模式系統pDBF*/

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

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

end if

end for

return（“schedulable”）；

5.3 仿真實驗

所有任務的截止期等于其周期，下面分析pWCET 參數長度、系統可調度性概率閾值HT以及系統高關鍵級任務概率CP 等系統參數對可調度性性能的影響。任務集包含10個任務，系統平均利用率以0.05 的步長從0.05 變化到1.0，每個實驗數據點測試100 個隨機任務集。

（1）改變任務pWCET 參數長度。使用重抽樣技術［33］，在不降低參數可靠性前提下縮減任務的pWCET 參數長度，當長度抽樣為1 時使用傳統的DBF 方法分析。

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

Fig.8 Changing the pWCET parameter length of the task（by re-sampling）圖8 改變任務的pWCET 參數長度（通過重抽樣方法）

（2）改變系統可調度性概率閾值HT。施加越嚴格的可調度性概率閾值，系統越可靠。

圖9 中，HT越寬松，系統的可調度性越好，但是在系統平均利用率特別小（0.05～0.25）或特別大（0.95～1.00）時，這種表現并不突出。

Fig.9 Changing the probability threshold of system schedulability HT圖9 改變系統可調度性概率閾值HT

（3）改變系統高關鍵級任務概率CP。提高系統高關鍵級任務的比例會增大系統高關鍵級模式下的pDBF。

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

Fig.10 Changing the system high critical level task probability CP圖10 改變系統高關鍵級任務概率CP

6 結語

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