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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1 任務(wù)模型

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

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

(1)

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

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

算法1. OPA算法.

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

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

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

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

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

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

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

1.2 動(dòng)機(jī)示例

如表1所示，待調(diào)度的混合關(guān)鍵級(jí)任務(wù)集共包括4個(gè)任務(wù)，分別屬于HI和LO兩個(gè)關(guān)鍵級(jí).其中，τ1和τ2是HI任務(wù)，其在HI模式和LO模式有不同的WCET值；τ3和τ4是LO任務(wù)，僅在LO模式時(shí)確保執(zhí)行.設(shè)系統(tǒng)最開始運(yùn)行于LO模式，使用前述OPA算法，這4個(gè)任務(wù)的優(yōu)先級(jí)分配結(jié)果為p3>p4>p1>p2，在LO模式時(shí)調(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個(gè)HI任務(wù)的優(yōu)先級(jí)即可以確保滿足截止時(shí)限.這需要在時(shí)刻12之前獲知關(guān)鍵級(jí)需要提升才能對(duì)優(yōu)先級(jí)交換進(jìn)行預(yù)計(jì).由此可見，一個(gè)HI任務(wù)的截止時(shí)限是否能夠得到滿足，會(huì)受到相對(duì)較高優(yōu)先級(jí)任務(wù)，包括較高優(yōu)先級(jí)的HI任務(wù)以及較高優(yōu)先級(jí)的LO任務(wù)的影響，也會(huì)受到關(guān)鍵級(jí)模式切換時(shí)刻的影響.

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

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

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

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

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

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

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

(2)

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

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

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

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

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

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

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

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

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

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

4 仿真與評(píng)估

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

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

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

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

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

3) 對(duì)相對(duì)截止時(shí)限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模式時(shí)的WCET，即認(rèn)為是關(guān)鍵級(jí)提升的時(shí)刻出現(xiàn)，其混合關(guān)鍵級(jí)調(diào)度算法AMC的結(jié)果將作為我們主要的比對(duì)、分析對(duì)象.

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

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

分別使用AMC和MC-et對(duì)上述任務(wù)集進(jìn)行可調(diào)度測試，圖3顯示了可調(diào)度任務(wù)比率的對(duì)比.可以觀察到同樣是只關(guān)注關(guān)鍵級(jí)提升后的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)先級(jí)對(duì)可調(diào)度任務(wù)比率的影響

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

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

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

5 結(jié) 論

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

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

在后續(xù)工作中，將對(duì)動(dòng)態(tài)優(yōu)先級(jí)調(diào)度方案和多處理器平臺(tái)上事件觸發(fā)關(guān)鍵級(jí)提升的混合關(guān)鍵級(jí)任務(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é)基金項(xiàng)目(61173036) This work was supported by the National Natural Science Foundation of China (61173036).

TP316.2