黃麗達(dá) 李仁發(fā)

(湖南大學(xué)信息科學(xué)與工程學(xué)院 長沙 410082)(hld_jt@hnu.edu.cn)

事件觸發(fā)關(guān)鍵級提升的實時任務(wù)可調(diào)度性分析

黃麗達(dá) 李仁發(fā)

(湖南大學(xué)信息科學(xué)與工程學(xué)院 長沙 410082)(hld_jt@hnu.edu.cn)

混合關(guān)鍵級(mixed criticality, MC)系統(tǒng)能夠同時保證高效地資源利用與高關(guān)鍵任務(wù)的正確執(zhí)行.當(dāng)前，對混合關(guān)鍵級系統(tǒng)的研究多認(rèn)為，從低關(guān)鍵級提升到高關(guān)鍵級的時機(jī)是高關(guān)鍵級任務(wù)執(zhí)行超過其低關(guān)鍵級模式下時間預(yù)算的時刻.但在實際應(yīng)用的嵌入式系統(tǒng)中，關(guān)鍵級模式的提升是由諸如所處環(huán)境變化、控制切換等系統(tǒng)外部事件觸發(fā)的，即關(guān)鍵級的提升可能發(fā)生在任務(wù)執(zhí)行過程中的任何時刻.在單處理器平臺上，針對使用固定優(yōu)先級調(diào)度策略的周期任務(wù)集，當(dāng)外部事件觸發(fā)關(guān)鍵級提升后，基于響應(yīng)時間分析得出了可調(diào)度高關(guān)鍵級任務(wù)的必要條件；并對關(guān)鍵級提升后，高關(guān)鍵級任務(wù)可能通過優(yōu)先級交換滿足截止時限的條件進(jìn)行了分析，得出了相應(yīng)的優(yōu)先級交換算法.仿真實驗驗證了事件觸發(fā)關(guān)鍵級提升時高關(guān)鍵級任務(wù)的可調(diào)度性及優(yōu)先級交換算法的有效性.

關(guān)鍵級；事件觸發(fā)；優(yōu)先級；響應(yīng)時間；截止時限

現(xiàn)代實時嵌入式系統(tǒng)，例如航空電子設(shè)備以及汽車系統(tǒng)的實際應(yīng)用，正向著功能不斷增加但所占空間更小、重量更輕、成本更低、能耗更少的方向發(fā)展.因此使用冗余硬件分層設(shè)計來實現(xiàn)任務(wù)之間隔離執(zhí)行[1]的傳統(tǒng)方法，正向著不同關(guān)鍵級的多種功能集成到一塊物理平臺上，共享硬件資源的研究方向轉(zhuǎn)變.但這種以提高資源利用率為目的的共享可能會使低關(guān)鍵級(low criticality, LO)任務(wù)對高關(guān)鍵級(high criticality, HI)任務(wù)的正確執(zhí)行產(chǎn)生干擾，導(dǎo)致HI任務(wù)錯過截止時限、造成非常嚴(yán)重的后果.例如從高效利用處理器計算能力的角度，可以將汽車的防抱死制動任務(wù)與導(dǎo)航任務(wù)放在同一個處理器上執(zhí)行，若導(dǎo)航任務(wù)未能按預(yù)設(shè)時間執(zhí)行完畢，防抱死任務(wù)很可能就無法得以及時執(zhí)行，從而導(dǎo)致重大安全事故[2].

既要確保HI任務(wù)的截止時限又要保證充分利用資源，是提出混合關(guān)鍵級(mixed criticality, MC)系統(tǒng)的初衷.文獻(xiàn)[3]首先對混合關(guān)鍵級系統(tǒng)的調(diào)度與驗證進(jìn)行了討論.無論是從過載角度考慮以增加系統(tǒng)運行的魯棒性[4]，還是從靜態(tài)驗證、遵循更保守國際統(tǒng)一標(biāo)準(zhǔn)的角度出發(fā)[5]，MC系統(tǒng)的執(zhí)行可分成若干關(guān)鍵級模式，處于不同關(guān)鍵級模式所確保執(zhí)行的任務(wù)子集和任務(wù)屬性均不同，即將待調(diào)度任務(wù)集劃分為不同關(guān)鍵級：在高關(guān)鍵級HI模式和關(guān)鍵級LO模式下總是滿足HI任務(wù)的截止時限；而LO任務(wù)只在低關(guān)鍵級模式下執(zhí)行，不確保其在HI模式下滿足截止時限.一般認(rèn)為系統(tǒng)是從LO模式開始運行，MC系統(tǒng)執(zhí)行從LO模式切換到HI模式的過程稱之為關(guān)鍵級提升.

MC任務(wù)一個重要特點是除了截止時限(dead-line)、周期(period)、最差情況下執(zhí)行時間(worst case execution time, WCET)、釋放時間(release time)等傳統(tǒng)時間參數(shù)之外，還增加了關(guān)鍵級(criticality)這一參數(shù)，且部分或全部的時間參數(shù)值依賴于關(guān)鍵級，即所謂關(guān)鍵參數(shù)：相較于LO模式，HI任務(wù)在HI模式下WCET更長、執(zhí)行頻率更高、截止時限更短[6].雖然有以文獻(xiàn)[7]為代表的部分研究討論不同關(guān)鍵級模式下基于彈性模型的周期變化，但當(dāng)前以文獻(xiàn)[8-11]為代表的大多數(shù)MC調(diào)度研究，包括最早提出MC調(diào)度的文獻(xiàn)[3]，均是以WCET為關(guān)鍵參數(shù).與周期、截止時限等其他時間參數(shù)比較，雖然實時任務(wù)的實際執(zhí)行時間具有不確定性和動態(tài)持續(xù)性，但是作為實時任務(wù)時間參數(shù)之一的WCET則是可以通過預(yù)先估算獲得.典型MC系統(tǒng)對于關(guān)鍵級的提升通常是這樣描述的：HI任務(wù)在LO模式下執(zhí)行時，若執(zhí)行完畢其LO模式下預(yù)置的WCET時間預(yù)算，仍然沒有結(jié)束執(zhí)行，則認(rèn)為此時系統(tǒng)應(yīng)該切換到HI模式執(zhí)行，同時通過掛起或拋棄LO任務(wù)以確保HI任務(wù)獲得更多的處理器執(zhí)行時間.這是從任務(wù)本身執(zhí)行發(fā)生變化的角度來識別關(guān)鍵級模式提升時刻.

但實際上，與系統(tǒng)關(guān)鍵級回落[12]不同，系統(tǒng)關(guān)鍵級模式從低到高的切換并不是由正在執(zhí)行的任務(wù)引發(fā)的，而是由外部事件觸發(fā)的.文獻(xiàn)[13]中指出現(xiàn)代汽車系統(tǒng)隨著行駛環(huán)境的變化發(fā)生關(guān)鍵級變化，例如從Street(城市街道)執(zhí)行模式進(jìn)入Highway(高速公路)執(zhí)行模式時，其懸架控制功能從LO切換成HI模式執(zhí)行.又例如，從權(quán)威機(jī)構(gòu)標(biāo)準(zhǔn)認(rèn)證角度考慮MC系統(tǒng)時，經(jīng)常以無人機(jī)為典型實例，文獻(xiàn)[14]中指出當(dāng)軍用無人機(jī)飛入民航區(qū)域，涉及飛行安全的相關(guān)功能必須遵循更保守的時間限制，例如WCET增加等，可見關(guān)鍵級的提升也是由系統(tǒng)所處外部環(huán)境變化引起的.因此，系統(tǒng)執(zhí)行從LO模式提升到HI模式，不是由任務(wù)本身觸發(fā)這種關(guān)鍵級提升，而是由外部環(huán)境變化、人為控制等事件的發(fā)生才引發(fā)系統(tǒng)關(guān)鍵級提升.任務(wù)實際執(zhí)行時間超過低關(guān)鍵級WCET只是關(guān)鍵級提升的表現(xiàn)和需要.

不同于當(dāng)前以HI任務(wù)超出低關(guān)鍵級WCET作為關(guān)鍵級提升時刻的思路，本文基于外部事件觸發(fā)(event-trigger)系統(tǒng)關(guān)鍵級提升的觀點，對關(guān)鍵級提升期間HI任務(wù)的可調(diào)度性進(jìn)行分析.由于在不同關(guān)鍵級下需確保執(zhí)行的任務(wù)集在系統(tǒng)設(shè)計時就已經(jīng)確定好了，即可以離線確定系統(tǒng)靜態(tài)處于某一關(guān)鍵級模式下的調(diào)度策略，保證具有相應(yīng)關(guān)鍵級參數(shù)的任務(wù)截止時限[15].所以要確保HI任務(wù)的正確執(zhí)行，問題聚焦在從LO提升到HI這個模式動態(tài)切換期間如何滿足HI任務(wù)的截止時限.本文基于響應(yīng)時間分析，針對在單處理平臺上執(zhí)行的混合關(guān)鍵級實時周期任務(wù)集，討論了其從LO模式切換到HI模式的關(guān)鍵級提升期間的可調(diào)度性，得出了相關(guān)必要的可調(diào)度條件.

在已公開發(fā)表的文獻(xiàn)中，涉及關(guān)鍵級提升后優(yōu)先級是否可交換的研究僅有文獻(xiàn)[16]從抖動的觀點進(jìn)行了討論.本文針對事件觸發(fā)關(guān)鍵級提升后，MC任務(wù)可能通過優(yōu)先級交換獲得正確調(diào)度的條件進(jìn)行了分析，并設(shè)計了相應(yīng)的優(yōu)先級交換算法.

1 任務(wù)模型與示例

本節(jié)對本文所使用的MC任務(wù)模型及相關(guān)術(shù)語進(jìn)行定義.引入一個MC任務(wù)集運行示例，為后文的優(yōu)先級可交換分析做準(zhǔn)備.

1.1 任務(wù)模型

為討論方便，暫時僅考慮系統(tǒng)只有HI和LO兩個關(guān)鍵級的情形.在單處理器平臺上，MC任務(wù)集τ由互不相關(guān)、允許搶占的有限個同步周期任務(wù)組成：τ{τ1,τ2,…,τm}，其中m表示任務(wù)個數(shù).以執(zhí)行時間為關(guān)鍵參數(shù)，定義任務(wù)τi,Ti,Di,li)，其中是任務(wù)τi在LO模式時的是在HI模式時的WCET.從保守驗證的角度而言，和分別是任務(wù)τi在LO和HI模式下能夠獲得的最大執(zhí)行時間預(yù)算.雖然一個實時任務(wù)的實際執(zhí)行時間是無法預(yù)知的，但總是不超過其WCET.即，對于LO任務(wù)而言有，對于HI任務(wù)則有在LO模式時，在HI模式時且.Ti和Di分別是任務(wù)τi的周期和相對截止時限，其值在任何關(guān)鍵級均不變化，且Di≤Ti.當(dāng)任務(wù)τi的關(guān)鍵級li=HI時，表示其為HI任務(wù)，其≤Di；若li=LO，則表示任務(wù)τi是LO任務(wù).當(dāng)系統(tǒng)處于HI模式，不確保其正確執(zhí)行，因此LO任務(wù)的不設(shè)確定值.任務(wù)τi的利用率通常使用計算獲得.顯然在不同關(guān)鍵級模式下，HI任務(wù)有不同利用率，LO模式下，有；HI模式下，有.

響應(yīng)時間是指任務(wù)從釋放到執(zhí)行完畢這一段時間間隔[17].常用于分析固定優(yōu)先級任務(wù)可調(diào)度性.一般實時任務(wù)τi的響應(yīng)時間為

(1)

其中hp(τi)是指優(yōu)先級高于任務(wù)τi的所有任務(wù).稍后將討論關(guān)鍵級對于任務(wù)響應(yīng)時間的影響.

在實際嵌入式應(yīng)用中，尤其是涉及硬實時的應(yīng)用，具有可預(yù)測性的固定優(yōu)先級調(diào)度被使用得更為廣泛[11].在無模式切換發(fā)生的靜態(tài)LO模式和HI模式下，可采用Audsley的最佳優(yōu)先級分配(optimal priority assignment, OPA)算法[18]分配任務(wù)的優(yōu)先級，算法描述如下：

算法1. OPA算法.

輸入：系統(tǒng)模式χ、n個待分配優(yōu)先級的周期任務(wù)集τ；

輸出：系統(tǒng)模式為χ時，依據(jù)優(yōu)先級從高到低排列的可調(diào)度任務(wù)序列.

Step1. 總是從最低優(yōu)先級k開始分配；

Step2. 任取一個li≥χ的任務(wù)τi∈τ；

Step3. 若除τi之外，所有l(wèi)j≥χ的任務(wù)τj均先于τi執(zhí)行，τi的響應(yīng)時間不遲于其截止時限，即Ri≤Di，則最低優(yōu)先級k分配給τi，即pi=k，且將τi移出τ，其他任務(wù)重復(fù)本步驟依次分配從k-1到1的優(yōu)先級；

Step4. 否則，從τ中重新選擇任務(wù)重復(fù)Step3.

在每一個關(guān)鍵級模式內(nèi)使用如上OPA算法對任務(wù)進(jìn)行固定優(yōu)先級分配.OPA算法將確定優(yōu)先級分配序列的可調(diào)度性測試復(fù)雜度從n!降低到n(n+1)2.

1.2 動機(jī)示例

如表1所示，待調(diào)度的混合關(guān)鍵級任務(wù)集共包括4個任務(wù)，分別屬于HI和LO兩個關(guān)鍵級.其中，τ1和τ2是HI任務(wù)，其在HI模式和LO模式有不同的WCET值；τ3和τ4是LO任務(wù)，僅在LO模式時確保執(zhí)行.設(shè)系統(tǒng)最開始運行于LO模式，使用前述OPA算法，這4個任務(wù)的優(yōu)先級分配結(jié)果為p3>p4>p1>p2，在LO模式時調(diào)度序列如圖1所示.

Table 1 An Example of Scheduling Mixed Criticality Task Set

Fig. 1 Scheduling MC tasks in Table 1 in low criticality mode圖1 表1示例MC任務(wù)集在LO模式的部分調(diào)度序列

在此例中，可以發(fā)現(xiàn)若能在發(fā)生模式切換的當(dāng)前周期內(nèi)交換2個HI任務(wù)的優(yōu)先級即可以確保滿足截止時限.這需要在時刻12之前獲知關(guān)鍵級需要提升才能對優(yōu)先級交換進(jìn)行預(yù)計.由此可見，一個HI任務(wù)的截止時限是否能夠得到滿足，會受到相對較高優(yōu)先級任務(wù)，包括較高優(yōu)先級的HI任務(wù)以及較高優(yōu)先級的LO任務(wù)的影響，也會受到關(guān)鍵級模式切換時刻的影響.

2) 對于HI任務(wù)τ2，在執(zhí)行完畢其低關(guān)鍵級時間預(yù)算的時刻，恰好也達(dá)到了其截止時限，已獲得相對質(zhì)量較低的執(zhí)行結(jié)果，由于T≥D，在當(dāng)前周期內(nèi)任務(wù)τ2的此次執(zhí)行已經(jīng)結(jié)束.

因此，在以執(zhí)行時間為關(guān)鍵參數(shù)的MC系統(tǒng)中，當(dāng)前常用的以高關(guān)鍵級任務(wù)執(zhí)行時間超過其低關(guān)鍵級WCET的時刻即為關(guān)鍵級提升時刻的設(shè)定，可視為是一種延遲關(guān)鍵級模式切換，即直到HI任務(wù)達(dá)到其CLO時間預(yù)算后才進(jìn)行關(guān)鍵級模式從LO到HI的提升.

下面從外部事件觸發(fā)關(guān)鍵級提升的觀點，對關(guān)鍵級提升期間HI任務(wù)的可調(diào)度問題以及HI任務(wù)之間優(yōu)先級可交換的問題進(jìn)行探討.

2 關(guān)鍵級提升期間的響應(yīng)時間分析

圖2所示是一個HI任務(wù)τi的執(zhí)行示例.

Fig. 2 A HI task executing example during a period圖2 一個HI任務(wù)的執(zhí)行示例

因此，以上2種情形HI任務(wù)τi在最差情況下的響應(yīng)時間為

(2)

3 關(guān)鍵級提升期內(nèi)優(yōu)先級可交換

在關(guān)鍵級提升期內(nèi)，一個RLO→HI>d的HI任務(wù)通過與鄰近較高優(yōu)先級任務(wù)交換優(yōu)先級，正如1.2節(jié)中例子所示，可能使二者的截止時限均能得到保證.根據(jù)固定優(yōu)先級調(diào)度的特點：若較低優(yōu)先級p=k的任務(wù)和較高優(yōu)先級p=k-1的任務(wù)交換優(yōu)先級執(zhí)行，對其他任務(wù)的調(diào)度執(zhí)行沒有影響[19].據(jù)此關(guān)鍵級提升期內(nèi)的優(yōu)先級交換可嘗試在優(yōu)先級相鄰的2個任務(wù)間進(jìn)行.

算法2. 優(yōu)先級交換(PE)算法.

輸入：依據(jù)優(yōu)先級遞減順序排列的在關(guān)鍵級提升期未滿足調(diào)度條件的HI任務(wù)子集τ′、可調(diào)度的HI任務(wù)子集τo；

輸出：依據(jù)優(yōu)先級降序排列的可調(diào)度的HI任務(wù)子集new_τo.

Step1. 取τo中優(yōu)先級最低的任務(wù)τk，其優(yōu)先級pk=k；

Step2. 取τ′中優(yōu)先級最高的任務(wù)τi，則其優(yōu)先級為pi=k+1；

Step5. 更新τi的響應(yīng)時間為

Step6. 更新τk的響應(yīng)時間為

Step8. 否則，取優(yōu)先級為p=k-1的HI任務(wù)重復(fù)Step3～Step7.

4 仿真與評估

本節(jié)對第2節(jié)和第3節(jié)基于外部事件引發(fā)關(guān)鍵級提升的MC系統(tǒng)的可調(diào)度性進(jìn)行測試，并對優(yōu)先級可交換的算法進(jìn)行了仿真驗證.

4.1 生成測試任務(wù)集

借鑒當(dāng)前MC調(diào)度研究的大多數(shù)仿真所采用的任務(wù)生成方式，使用文獻(xiàn)[8]的方法，測試中所使用的待調(diào)度MC任務(wù)如下隨機(jī)產(chǎn)生：

1) 對于任務(wù)利用率Ui，使用UUnifast算法[21]在0.025～0.975之間產(chǎn)生均勻分布的利用率值；

2) 對任務(wù)周期Ti，根據(jù)對數(shù)正態(tài)分布生成任務(wù)周期，最小和最大任務(wù)周期相差100倍，例如最小任務(wù)周期為10 ms，最大任務(wù)周期為1 s，大部分是硬實時應(yīng)用的任務(wù)均有類似屬性；

3) 對相對截止時限D(zhuǎn)i，設(shè)定Di=Ti；

6) 生成的任務(wù)由參數(shù)cp確定其可能為HI任務(wù)的可能性，例如cp=0.5.

4.2 可調(diào)度性測試

文獻(xiàn)[9]認(rèn)為一旦HI任務(wù)執(zhí)行超過LO模式時的WCET，即認(rèn)為是關(guān)鍵級提升的時刻出現(xiàn)，其混合關(guān)鍵級調(diào)度算法AMC的結(jié)果將作為我們主要的比對、分析對象.

1) AMC.某一個HI任務(wù)超出LO模式WCET時，即認(rèn)為系統(tǒng)關(guān)鍵級提升的時刻出現(xiàn).

依據(jù)4.1節(jié)中的方法共計產(chǎn)生1 000個待調(diào)度的任務(wù)，其中一半為HI任務(wù)(cp=0.5)，每個HI任務(wù)在HI模式時的WCET是其LO模式時WCET的2倍(cf=2.0).

分別使用AMC和MC-et對上述任務(wù)集進(jìn)行可調(diào)度測試，圖3顯示了可調(diào)度任務(wù)比率的對比.可以觀察到同樣是只關(guān)注關(guān)鍵級提升后的HI任務(wù)的正確執(zhí)行，MC-et可調(diào)度的HI任務(wù)比率要高于AMC，且AMC能夠調(diào)度的任務(wù)MC-et均能夠調(diào)度，反之卻不一定.

Fig. 3 Percentage of schedulable tasks圖3 可調(diào)度任務(wù)占總?cè)蝿?wù)數(shù)的百分比

Fig. 4 Varying cf to change the value of affecting schedulable tasks圖4 調(diào)整參數(shù)cf來改變值的可調(diào)度任務(wù)比率

Fig. 5 Varying cp to change the number of HI tasks affecting schedulable tasks圖5 調(diào)整參數(shù)cp來改變HI任務(wù)數(shù)目的可調(diào)度比率

Fig. 6 Exchanging the priorities between MC tasks affecting schedulable tasks圖6 交換優(yōu)先級對可調(diào)度任務(wù)比率的影響

4.3 優(yōu)先交換算法的有效性測試

Fig. 7 Exchanging the priorities between varying cf of MC tasks affecting schedulable tasks圖7 交換優(yōu)先級對調(diào)整cf值的可調(diào)度任務(wù)比率影響

Fig. 8 Exchanging the priorities between varying cp of MC tasks affecting schedulable tasks圖8 交換優(yōu)先級對調(diào)整cp值的可調(diào)度任務(wù)比率影響

5 結(jié) 論

對于混合關(guān)鍵級系統(tǒng)而言，由低關(guān)鍵級模式到高關(guān)鍵級模式的轉(zhuǎn)換不是由任務(wù)執(zhí)行地變化產(chǎn)生，而是由外部事件引發(fā)的，關(guān)鍵參數(shù)的變化只是關(guān)鍵級提升的表現(xiàn).在以任務(wù)執(zhí)行時間為關(guān)鍵參數(shù)的混合關(guān)鍵級系統(tǒng)中，不論是從確保高關(guān)鍵級任務(wù)正確執(zhí)行的魯棒性角度考慮，還是從滿足保守的統(tǒng)一標(biāo)準(zhǔn)驗證的要求考慮，關(guān)鍵級提升可能發(fā)生在高關(guān)鍵級任務(wù)在低關(guān)鍵級模式下釋放后直至當(dāng)前周期結(jié)束的任何時刻.

對于固定優(yōu)先級的調(diào)度方案，基于外部事件觸發(fā)關(guān)鍵級模式切換的考慮，本文僅關(guān)注高關(guān)鍵級任務(wù)截止時限的確保，尤其是系統(tǒng)關(guān)鍵級模式提升期間，基于響應(yīng)時間分析得出了高關(guān)鍵級任務(wù)的可調(diào)度條件；并對關(guān)鍵級提升期間，可能發(fā)生優(yōu)先級相鄰任務(wù)交換優(yōu)先級滿足截止時限的條件進(jìn)行了討論分析，并設(shè)計了優(yōu)先級交換算法.仿真實驗驗證了前述分析與算法的有效性.

在后續(xù)工作中，將對動態(tài)優(yōu)先級調(diào)度方案和多處理器平臺上事件觸發(fā)關(guān)鍵級提升的混合關(guān)鍵級任務(wù)調(diào)度進(jìn)行研究.

[1]Burns A, Davis R. Mixed criticality systems—A review[R]. Yorkshire, UK: Department of Computer Science, University of York, 2013

[2]Niz D d, Lakshmanan K, Rajkumar R. On the scheduling of mixed-criticality real-time task sets[C]Proc of IEEE RTSS 2009. Piscataway, NJ: IEEE, 2009: 291-300

[3]Vestal S. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[C]Proc of IEEE RTSS 2007. Piscataway, NJ: IEEE, 2007: 239-243

[4]Lakshmanan K, Niz D d, Rajkumar R. Mixed-criticality task synchronization in zero-slack scheduling[C]Proc of IEEE RTAS 2011. Piscataway, NJ: IEEE, 2011: 47-56

[5]Baruah S, Li H, Stougie L. Towards the design of certifiable mixed-criticality systems[C]Proc of IEEE RTAS 2010. Piscataway, NJ: IEEE, 2010: 13-22

[6]Burns A, Baruah S. Timing Faults and Mixed Criticality Systems[M]. Berlin: Springer, 2011

[7]Su H, Zhu D. An elastic mixed-criticality task model and its scheduling algorithm[C]Proc of DATE 2013. San Jose, CA: EDAA, 2013: 147-152

[8]Baruah S, Burns A, Davis R I. Response-time analysis for mixed criticality systems[C]Proc of IEEE RTSS 2011. Piscataway, NJ: IEEE, 2011: 34-43

[9]Baruah S, Bonifaci V, D’Angelo G, et al. Mixed-Criticality Scheduling of Sporadic Task Systems[M]. Berlin: Springer, 2011

[10]Schneider R, Goswami D, Masrur A, et al. Multi-layered scheduling of mixed-criticality cyber-physical systems[J]. Journal of Systems Architecture, 2013, 59(10): 1215-1230

[11]Buttazzo G C. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications[M]. New York: Springer Science & Business Media, 2011

[12]Santy F, George L, Thierry P, et al. Relaxing mixed-criticality scheduling strictness for task sets scheduled with FP[C]Proc of IEEE ECRTS 2012. Piscataway, NJ: IEEE, 2012: 155-165

[13]De-Niz D, Phan L T X. Partitioned scheduling of multi-modal mixed-criticality real-time systems on multiprocessor platforms[C]Proc of IEEE RTAS 2014. Piscataway, NJ: IEEE, 2014: 111-122

[14]Triquet B. Mixed criticality in avionics[COL]Proc of European Commission Workshop on Mixed-Criticality Systems. 2012 [2012-09-11]. http:cordis.europa.eufp7ictembedded-systems-engineeringpresentationstriquet.pdf

[15]Barhorst J, Belote T, Binns P, et al. A research agenda for mixed-criticality systems[R]. Brookings, Washington DC: Department of Computer Science and Engineering, Washington University in St Louis, 2009

[16]Baruah S, Burns A, Davis R I. An extended fixed priority scheme for mixed criticality systems[C]Proc of IEEE RTCSA 2013. Piscataway, NJ: IEEE, 2013: 18-24

[17]Joseph M, Pandya P. Finding response times in a real-time system[J]. The Computer Journal, 1986, 29(5): 390-395

[18]Audsley N C. Optimal Priority Assignment and Feasibility of Static Priority Tasks with Arbitrary Start Times[M]. York, England: University of York, Department of Computer Science, 1991

[19]Burns A. System mode changes-general and criticality-based[C]Proc of the 2nd WMC 2014. Piscataway, NJ: IEEE, 2014: 3-8

[20]Liu J W S. Real-Time Systems[M]. Upper Saddle River, NJ: Prentice Hall, 2000

[21]Bini E, Buttazzo G C. Measuring the performance of schedulability tests[J]. Real-Time Systems, 2005, 30(12): 129-154

[22]Bastoni A, Brandenburg B, Anderson J. Cache-related preemption and migration delays: Empirical approximation and impact on schedulability[C]Proc of OSPERT 2010. Duesseldorf, Germany: Euromicro, 2010: 33-44

Huang Lida, born in 1978. Lecturer and PhD candidate. Her main research interests include real time scheduling and embedded software.

Li Renfa, born in 1956. Professor and PhD supervisor. His main research interests include computer architecture and computer application technology.

The Schedulable Analysis of Real-Time Tasks After Event-Triggered CriticalityLevel Transition

Huang Lida and Li Renfa

(CollegeofComputerScienceandElectronicEngineering,HunanUniversity,Changsha410082)

Both effective resource utilization and meeting the deadlines of high-criticality tasks are objectives of mixed-criticality systems. Currently, it is considered the moment that any of high-criticality tasks execute for their low-critical worst case execution time without completing the system switch from low to high-criticality mode immediately. However, in real embedded applications, the increasing criticality is event-triggered which includes outer circumstance changing, control switching, and so on. That is why the time of raising criticality level can be occurred before, during, or after a task implementation. In this paper we center on that the time of event-triggered increasing criticality is how to influent the scheduling of high-criticality and fixed priority periodic tasks, which is based on the response time analysis. A sufficient condition of scheduling high criticality tasks is derived. Then we discuss when and how to exchange priorities between two high-critical tasks in order to meet their deadlines at the same time, and propose an algorithm of exchanging priorities. Evaluations illustrate the benefits of the schedulable condition and the priority exchanging algorithm.

criticality; event-trigger; priority; response time; deadline

2015-09-30；

2016-02-23

國家自然科學(xué)基金項目(61173036) This work was supported by the National Natural Science Foundation of China (61173036).

TP316.2