截止時(shí)限為關(guān)鍵參數(shù)的混合關(guān)鍵級(jí)實(shí)時(shí)任務(wù)調(diào)度研究

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

(湖南大學(xué)信息科學(xué)與工程學(xué)院　長(zhǎng)沙　410082)

?

截止時(shí)限為關(guān)鍵參數(shù)的混合關(guān)鍵級(jí)實(shí)時(shí)任務(wù)調(diào)度研究

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

(湖南大學(xué)信息科學(xué)與工程學(xué)院長(zhǎng)沙410082)

(hld_jt@hnu.edu.cn)

摘要混合關(guān)鍵級(jí)系統(tǒng) (mixed criticality system)的研究源于在單一平臺(tái)上執(zhí)行多個(gè)重要級(jí)不同的功能,當(dāng)前混合關(guān)鍵級(jí)調(diào)度研究，一般考慮高關(guān)鍵級(jí)任務(wù)在不同關(guān)鍵級(jí)運(yùn)行模式表現(xiàn)為或周期或計(jì)算時(shí)間不同，即以任務(wù)釋放時(shí)間間隔和最差情況執(zhí)行時(shí)間為關(guān)鍵參數(shù).但截至?xí)r限(dendline)也是實(shí)時(shí)任務(wù)的重要時(shí)間參數(shù)，尤其是對(duì)硬實(shí)時(shí)任務(wù)，以截止時(shí)限作為關(guān)鍵參數(shù)進(jìn)行相應(yīng)混合關(guān)鍵級(jí)調(diào)度的研究尚是空白.針對(duì)此問題，以截止時(shí)限作為關(guān)鍵參數(shù)，以響應(yīng)時(shí)間分析為基礎(chǔ)，對(duì)單處理器平臺(tái)中的混和關(guān)鍵級(jí)任務(wù)的可調(diào)度性進(jìn)行分析，并提出了一種預(yù)提升關(guān)鍵級(jí)的調(diào)度算法RCLA(raising critical-level in advance)，在低關(guān)鍵級(jí)運(yùn)行模式下，高關(guān)鍵級(jí)低優(yōu)先級(jí)任務(wù)有限度地提前搶占低關(guān)鍵級(jí)高優(yōu)先級(jí)任務(wù)的執(zhí)行，既確保了滿足高關(guān)鍵級(jí)任務(wù)在不同關(guān)鍵級(jí)運(yùn)行模式下的截止時(shí)限，也讓盡可能多的任務(wù)可以被調(diào)度執(zhí)行，使得計(jì)算資源得以充分利用.仿真結(jié)果驗(yàn)證了RCLA算法的有效性.

關(guān)鍵詞混合關(guān)鍵級(jí)；實(shí)時(shí)調(diào)度；截止時(shí)限；關(guān)鍵參數(shù)；響應(yīng)時(shí)間

嵌入式領(lǐng)域中，在單個(gè)共享的計(jì)算平臺(tái)上執(zhí)行具有不同功能的多個(gè)實(shí)時(shí)任務(wù)，已成為能夠兼顧能耗、成本、散熱等多方面需求的解決之道[1].混合關(guān)鍵級(jí)系統(tǒng)(mixed criticality system)正是此類系統(tǒng)中的典型代表[2].所謂混合關(guān)鍵級(jí)意味著在單一平臺(tái)上同時(shí)執(zhí)行多種功能(多種任務(wù)),其中某些任務(wù)比其他任務(wù)更為“重要”，例如汽車控制系統(tǒng)中防抱死制動(dòng)系統(tǒng)的正確工作比車載收音機(jī)的正確工作要更關(guān)鍵，這里正確工作(或正確執(zhí)行)的含義對(duì)于實(shí)時(shí)任務(wù)而言就是要滿足其截止時(shí)限(deadline)[3].

在混合關(guān)鍵級(jí)系統(tǒng)中，待執(zhí)行任務(wù)集里的各個(gè)任務(wù)按照關(guān)鍵程度會(huì)被分配相應(yīng)的關(guān)鍵級(jí)，即相對(duì)更為重要的，或者對(duì)生命、重大財(cái)產(chǎn)的安全影響更大的任務(wù)就會(huì)有相對(duì)更高的關(guān)鍵級(jí)，稱之為高關(guān)鍵級(jí)任務(wù)，反之則稱為低關(guān)鍵級(jí)任務(wù).運(yùn)行中的混和關(guān)鍵級(jí)系統(tǒng)總是處于某一個(gè)關(guān)鍵級(jí)狀態(tài)，此時(shí)不低于系統(tǒng)當(dāng)前關(guān)鍵級(jí)的任務(wù)均可以被調(diào)度執(zhí)行；當(dāng)由于外界事件觸發(fā)系統(tǒng)關(guān)鍵級(jí)提升時(shí)，相對(duì)于系統(tǒng)當(dāng)前關(guān)鍵級(jí)更低的任務(wù)就不再保證其正確執(zhí)行，換而言之不再保證滿足其截止時(shí)限.混和關(guān)鍵級(jí)系統(tǒng)既實(shí)現(xiàn)了在同一物理平臺(tái)上最大可能地利用資源，盡可能調(diào)度執(zhí)行多種任務(wù)充分使用平臺(tái)的計(jì)算能力，也總是能夠滿足高關(guān)鍵任務(wù)的時(shí)間截止時(shí)限，從而同時(shí)確保高資源利用率和高安全性.

本文對(duì)混和關(guān)鍵級(jí)系統(tǒng)中不同關(guān)鍵級(jí)相應(yīng)截止時(shí)限不同的待調(diào)度任務(wù)集模型進(jìn)行定義，在單處理器平臺(tái)上為了保證高關(guān)鍵級(jí)任務(wù)的截止時(shí)限在不同關(guān)鍵級(jí)執(zhí)行總能被滿足，基于固定優(yōu)先級(jí)的響應(yīng)時(shí)間分析，對(duì)以截止時(shí)限為關(guān)鍵參數(shù)的混和關(guān)鍵級(jí)系統(tǒng)的可調(diào)度性進(jìn)行了分析，并提出了一種預(yù)關(guān)鍵級(jí)提升算法(raising critical-level in advance, RCLA)，分離任務(wù)被分配的優(yōu)先級(jí)和關(guān)鍵級(jí)，具有低優(yōu)先級(jí)的高關(guān)鍵級(jí)任務(wù)有限度地提前搶占具有高優(yōu)先級(jí)的低關(guān)鍵級(jí)任務(wù)的執(zhí)行，從而總能保證高關(guān)鍵級(jí)任務(wù)的截止時(shí)限，同時(shí)將對(duì)低關(guān)鍵級(jí)任務(wù)正確執(zhí)行的影響控制在一個(gè)有限的范圍內(nèi).

1任務(wù)模型與定義

在單處理器平臺(tái)上，待調(diào)度任務(wù)集τ由互不相關(guān)、允許搶占的有限個(gè)同步周期任務(wù)組成，τ={τ1,τ2,…,τn}，其中n表示任務(wù)個(gè)數(shù).任務(wù)τi定義為τi(Ci,Pi,Di,li)，其中Ci是最差情況下的執(zhí)行時(shí)間WCET；Pi是任務(wù)τi的周期；li表示任務(wù)τi的關(guān)鍵級(jí)屬性；Di為一向量，表示不同關(guān)鍵級(jí)有不同截止時(shí)限值Di=(Di(L1),Di(L2),…,Di(Li))，L1表示系統(tǒng)最低關(guān)鍵級(jí)，通常是從數(shù)值1開始.為討論方便，暫時(shí)僅考慮系統(tǒng)只有高低2個(gè)關(guān)鍵級(jí)的情況，即有τi(Ci,Pi,{Di(LO),Di(HI)},li)，若任務(wù)為低關(guān)鍵級(jí)任務(wù)(下文簡(jiǎn)稱之為L(zhǎng)O任務(wù))，則li=LO且其截止時(shí)限D(zhuǎn)i(LO)=Di(HI)；若任務(wù)是高關(guān)鍵級(jí)任務(wù)(下文簡(jiǎn)稱之為HI任務(wù))，那么li=HI且其截止時(shí)限D(zhuǎn)i(LO)>Di(HI).?i，Ci

定義1. 關(guān)鍵參數(shù).實(shí)時(shí)任務(wù)的時(shí)間參數(shù)包括執(zhí)行時(shí)間、周期、截止時(shí)限等，在混合關(guān)鍵級(jí)系統(tǒng)中，HI任務(wù)在不同系統(tǒng)關(guān)鍵級(jí)會(huì)有相應(yīng)的不同時(shí)間參數(shù)，稱這種對(duì)應(yīng)不同關(guān)鍵級(jí)執(zhí)行具有不同值的時(shí)間參數(shù)為關(guān)鍵參數(shù).

定義2. 調(diào)度窗口.一個(gè)實(shí)時(shí)任務(wù)的調(diào)度窗口是指從其釋放時(shí)間到其絕對(duì)截止時(shí)限的這一段時(shí)間間隔,其中絕對(duì)截止時(shí)限di=ai+Di.

系統(tǒng)處于不同關(guān)鍵級(jí)執(zhí)行時(shí)，可調(diào)度執(zhí)行的任務(wù)屬性或者任務(wù)數(shù)量也會(huì)不同，這與文獻(xiàn)[13]中模式的概念吻合，即稱系統(tǒng)處于不同關(guān)鍵級(jí)模式.一般認(rèn)為系統(tǒng)從低關(guān)鍵級(jí)模式開始執(zhí)行，由于外界事件觸發(fā)[14]，產(chǎn)生關(guān)鍵級(jí)提升，亦稱為發(fā)生關(guān)鍵級(jí)切換，因此關(guān)鍵級(jí)提升時(shí)刻對(duì)于混和關(guān)鍵級(jí)系統(tǒng)本身是不能預(yù)先可知的.

在實(shí)際實(shí)時(shí)嵌入式應(yīng)用中多使用固定優(yōu)先級(jí)調(diào)度[15]，本文使用截止時(shí)限單一調(diào)度(deadline-monotonic, DM)算法對(duì)某一個(gè)系統(tǒng)關(guān)鍵級(jí)模式下的任務(wù)進(jìn)行調(diào)度，使得所有任務(wù)均能在低關(guān)鍵級(jí)模式下被調(diào)度執(zhí)行，HI任務(wù)在高關(guān)鍵級(jí)模式下均能被調(diào)度執(zhí)行.

2截止時(shí)限作為關(guān)鍵參數(shù)的任務(wù)可調(diào)度性

如圖1所示，a是HI任務(wù)τi的釋放時(shí)刻，Ri是其響應(yīng)時(shí)間，若時(shí)刻t*是系統(tǒng)由低關(guān)鍵級(jí)提升到高關(guān)鍵級(jí)的時(shí)刻，由于Di(HI)

Fig. 1　HI-task at the time of raising critical-level.圖1　關(guān)鍵級(jí)提升時(shí)刻對(duì)任務(wù)的影響

1) 在時(shí)刻t*時(shí)，之前所釋放的所有HI任務(wù)已經(jīng)執(zhí)行完畢，即Xi<0.此種情況下無需考慮HI任務(wù)由于系統(tǒng)關(guān)鍵級(jí)提升所受到的影響.在該調(diào)度窗口內(nèi)繼續(xù)執(zhí)行完畢時(shí)刻t*時(shí)未執(zhí)行完的LO任務(wù).至少a+Pi后才進(jìn)入高關(guān)鍵級(jí)模式調(diào)度.

2) 在時(shí)刻t*時(shí)，如果正在執(zhí)行HI任務(wù)τi,即如圖1所示情況，或者尚有HI任務(wù)沒有執(zhí)行完畢，那么就需要關(guān)注已經(jīng)或正在執(zhí)行的高優(yōu)先級(jí)LO任務(wù)對(duì)相對(duì)低優(yōu)先級(jí)的HI任務(wù)是否能滿足提前的截止時(shí)限影響，即在時(shí)刻t*進(jìn)入高關(guān)鍵級(jí)模式后，HI任務(wù)的相對(duì)截止時(shí)限提前，應(yīng)分析是否HI任務(wù)在當(dāng)前調(diào)度周期內(nèi)可保證滿足Di(HI)，即在(a+Di(HI)-t*)這一段時(shí)間內(nèi)是否足以提供HI任務(wù)尚未完成的計(jì)算時(shí)間.

應(yīng)用響應(yīng)時(shí)間的概念[3]對(duì)上述情況1進(jìn)行分析討論.由于使用DM調(diào)度算法，那么任務(wù)τi的響應(yīng)時(shí)間Ri可計(jì)算為

(1)

其中,hp(τi)表示優(yōu)先級(jí)高于任務(wù)τi的任務(wù)集.由于相對(duì)截止時(shí)限是關(guān)鍵參數(shù)，所以由式(1)可知，任務(wù)響應(yīng)時(shí)間的計(jì)算結(jié)果不受關(guān)鍵級(jí)變化的影響.

對(duì)于前述情況2進(jìn)行2點(diǎn)討論：

① 若ai+Di(HI)≥ai+Ri，那么在當(dāng)前調(diào)度窗口[ai,ai+Di(HI))，正在執(zhí)行的調(diào)度方案仍然有效，無需進(jìn)行其他操作；

② 若ai+Di(HI)

Ci,0=

(2)

其中，條件Con(aj,t*)表示較高優(yōu)先級(jí)任務(wù)τj的釋放時(shí)間需滿足aj>t*，即較高優(yōu)先級(jí)任務(wù)在提升時(shí)刻t*之后還有釋放.那么在系統(tǒng)處于低關(guān)鍵級(jí)運(yùn)行模式時(shí)，已經(jīng)開始執(zhí)行的較低優(yōu)先級(jí)的HI任務(wù)仍然可能在執(zhí)行過程中被搶占.由此可得，HI任務(wù)τi未完成的執(zhí)行時(shí)間可定義為

(3)

即，若滿足：

(4)

那么就可以通過簡(jiǎn)單丟棄在Xi這段時(shí)間內(nèi)將要執(zhí)行的LO任務(wù)即可滿足高關(guān)鍵級(jí)模式下的截止時(shí)限；若不滿足式(4)，那么就需要從時(shí)刻t*前的高優(yōu)先級(jí)LO任務(wù)“剝奪”計(jì)算時(shí)間，因?yàn)檫@些LO任務(wù)對(duì)于HI任務(wù)而言就是導(dǎo)致HI任務(wù)不能滿足Di(HI)的干擾任務(wù).

3預(yù)先提升關(guān)鍵級(jí)

若從關(guān)鍵級(jí)提升時(shí)刻之后無法獲得足夠的計(jì)算時(shí)間完成WCET，滿足Di(HI)，可以從2種方案考慮保證HI任務(wù)調(diào)度問題：

方案1. 調(diào)整任務(wù)優(yōu)先級(jí)分配方案.為防止LO任務(wù)被分配高優(yōu)先級(jí)，從而對(duì)HI任務(wù)正確執(zhí)行產(chǎn)生可能的干擾，總是先執(zhí)行HI任務(wù)，即優(yōu)先級(jí)與關(guān)鍵級(jí)一致.這樣的調(diào)度方法實(shí)際已經(jīng)退化成完全基于關(guān)鍵級(jí)的調(diào)度方案CrMPO[7]，對(duì)資源利用率的提升沒有益處.

(5)

(6)

其中，Phi表示比任務(wù)τi優(yōu)先級(jí)高的任務(wù)子集在任務(wù)τi執(zhí)行完畢之前的執(zhí)行時(shí)間，Phi由2部分組成：

(7)

(8)

(9)

Table 1　An Example of Mixed-Criticality Task Set

依據(jù)DM，表1中任務(wù)集的調(diào)度序列如圖2所示:

Fig. 2　Scheduling in Low-Criticality with DM.圖2　低關(guān)鍵級(jí)時(shí)使用DM調(diào)度任務(wù)集

如圖2所示，在低關(guān)鍵級(jí)模式，任務(wù)優(yōu)先級(jí)是按照DM進(jìn)行分配，低關(guān)鍵級(jí)的任務(wù)τ2的優(yōu)先級(jí)是最高的.設(shè)若關(guān)鍵級(jí)提升時(shí)刻以整數(shù)倍時(shí)間單元進(jìn)行[16].以相對(duì)截止時(shí)限作為關(guān)鍵參數(shù)，對(duì)關(guān)鍵級(jí)提升的時(shí)刻分別進(jìn)行討論：

1) 若關(guān)鍵級(jí)提升發(fā)生在(5,8]期間，不滿足式(4)，尚未執(zhí)行完畢的高關(guān)鍵級(jí)任務(wù)τ1是沒有辦法滿足其D1(HI)，解決方案只有預(yù)關(guān)鍵級(jí)提升.

2) 若關(guān)鍵級(jí)提升發(fā)生在(4,5]期間，對(duì)于HI任務(wù)τ2也無法滿足式(4)，相應(yīng)D2(HI)亦無法滿足，解決方案只有預(yù)關(guān)鍵級(jí)提升.

3) 若在其它時(shí)刻進(jìn)行關(guān)鍵級(jí)提升，對(duì)調(diào)度HI任務(wù)滿足截止時(shí)限沒有影響，無需考慮.

Fig. 3　Scheduling with RCLA.圖3　使用預(yù)關(guān)鍵級(jí)提升的調(diào)度方案

依據(jù)圖3所示調(diào)度方案，形成預(yù)關(guān)鍵級(jí)提升算法RCLA(raising critical-level in advanced)，算法表述如下：

算法1. 預(yù)關(guān)鍵級(jí)提升RCLA.

輸入：有限個(gè)同步周期任務(wù)集τ={τ1,τ2,…,τn}，其中τi(Ci,Pi,{Di(LO),Di(HI)},li)；

輸出：調(diào)度任務(wù)執(zhí)行序列.

Step1. 按照DM排序待調(diào)度任務(wù)集τ={τ1,τ2,…,τn}，此時(shí)任務(wù)調(diào)度序列僅依據(jù)相對(duì)截止時(shí)限升序排列；

Step2. 根據(jù)式(1)計(jì)算HI任務(wù)的響應(yīng)時(shí)間，若τi∈?！膌i=HI，且Ri≤Di(HI)，則該高關(guān)鍵級(jí)任務(wù)無需提前執(zhí)行；

Step5. 在最后一個(gè)執(zhí)行的HI任務(wù)的響應(yīng)時(shí)間之后，若沒有發(fā)生系統(tǒng)關(guān)鍵級(jí)提升則繼續(xù)依據(jù)DM順序調(diào)度LO任務(wù)；否則進(jìn)入高關(guān)鍵級(jí)運(yùn)行模式，基于DM調(diào)度HI任務(wù).

在待調(diào)度任務(wù)數(shù)目有限的情況下，由于響應(yīng)時(shí)間分析的時(shí)間復(fù)雜度是偽多項(xiàng)式時(shí)間的，因此基于響應(yīng)時(shí)間分析的RCLA算法的時(shí)間復(fù)雜度也是偽多項(xiàng)式時(shí)間的，若以z表示發(fā)生關(guān)鍵級(jí)提升時(shí)刻的調(diào)度窗口長(zhǎng)度，那么RCLA算法的時(shí)間復(fù)雜度可表示為O(n2×z)，其中n為待調(diào)度任務(wù)數(shù)，即RCLA算法的時(shí)間復(fù)雜度是多項(xiàng)式時(shí)間的.

雖然在前文中，RCLA算法對(duì)于相對(duì)低和相對(duì)高的2種關(guān)鍵級(jí)任務(wù)進(jìn)行討論獲得的，RCLA很容易被擴(kuò)展到多于2級(jí)關(guān)鍵級(jí)的多關(guān)鍵級(jí)混合系統(tǒng)，且對(duì)跨關(guān)鍵級(jí)執(zhí)行關(guān)鍵級(jí)提升的情況同樣適用.

4仿真結(jié)果與分析

本節(jié)對(duì)以截止時(shí)限為關(guān)鍵參數(shù)的混合關(guān)鍵級(jí)系統(tǒng)使用RCAL算法調(diào)度任務(wù)集的有效性進(jìn)行仿真評(píng)估.根據(jù)文獻(xiàn)[17]，錯(cuò)過截止時(shí)限比率(miss deadline ration, MDR)是比較調(diào)度算法有效性的重要指標(biāo)，即對(duì)相同待調(diào)度任務(wù)集滿足截止時(shí)限的任務(wù)數(shù)目越多，則認(rèn)為相應(yīng)的調(diào)度算法更優(yōu).本文采用的評(píng)價(jià)指標(biāo)為系統(tǒng)可接受任務(wù)比率(acceptance ration,A)，A=1-MDR=(滿足截止時(shí)限的任務(wù)數(shù))(任務(wù)集中待調(diào)度任務(wù)總數(shù)).

由于目前對(duì)混合關(guān)鍵級(jí)中以截止時(shí)限為關(guān)鍵參數(shù)的調(diào)度研究極少，在現(xiàn)有公開發(fā)表的文獻(xiàn)中，以截止時(shí)限作為關(guān)鍵參數(shù)的混合關(guān)鍵級(jí)的調(diào)度至今仍是空白，使用CrMPO(criticality monotonic priority order)調(diào)度算法用作比對(duì)分析對(duì)象，并依據(jù)仿真結(jié)果討論待調(diào)度任務(wù)集的特性對(duì)調(diào)度結(jié)果的影響.

仿真實(shí)驗(yàn)中用到的任務(wù)集參數(shù)按照5個(gè)過程隨機(jī)生成：

2)設(shè)定最大執(zhí)行時(shí)間Cmax，則Ci在{1,2,…,Cmax}范圍內(nèi)服從均勻分布隨機(jī)生成；

4)Di(LO)=CF×Di(HI)，其中參數(shù)CF(criticality factor)為一個(gè)固定倍增數(shù)，由于Di(HI)

5) 隨機(jī)生成任務(wù)li=HI，即為HI任務(wù)的可能性由參數(shù)CP確定，例如CP=0.5

仿真實(shí)驗(yàn)選取任務(wù)集利用率U∈[0.025,0.975]，步進(jìn)間隔為0.025.每一個(gè)利用率值，生成任務(wù)數(shù)量為1 000個(gè)，選取Cmax=10.圖4顯示了在CP=0.5即有50%的任務(wù)為HI任務(wù)、每個(gè)HI任務(wù)的高關(guān)鍵級(jí)時(shí)截止時(shí)限是低關(guān)鍵級(jí)時(shí)截止時(shí)限的0.6倍即CF=0.6時(shí)，RCLA與CrMPO可調(diào)度任務(wù)比率隨著任務(wù)利用率增長(zhǎng)可接受任務(wù)比率的變化情況.由圖4可知，使用RCLA算法，混和關(guān)鍵級(jí)的可接受任務(wù)數(shù)目，即可調(diào)度的任務(wù)數(shù)目遠(yuǎn)好于使用CrMPO，尤其是在輕負(fù)載，即利用率小于50%的情況下，使用RCLA可調(diào)度的任務(wù)數(shù)目平均比使用CrMPO的多出了4.8倍.

Fig. 4　Percentage of schedulable tasks.圖4　可調(diào)度任務(wù)比率

下面我們研究調(diào)整參數(shù)CP和CF對(duì)可調(diào)度任務(wù)數(shù)目的影響.使用加權(quán)可調(diào)度任務(wù)比率(或稱之加權(quán)可接受任務(wù)比率)[19]作為以前述可調(diào)整參數(shù)為變量的函數(shù),加權(quán)可調(diào)度任務(wù)比率

(10)

其中,p是可變參數(shù);y表示某一種可調(diào)度性算法;Sy(τ,p)是當(dāng)參數(shù)值為p時(shí)使用調(diào)度算法y任務(wù)集τ的可調(diào)度性，其為1或0的二元值.使用加權(quán)可調(diào)度任務(wù)比例，可以降低問題的維度[17]，還可以覆蓋到更大的利用率的值.

圖5所示為隨著HI任務(wù)的數(shù)目增加，即參數(shù)CP值增加，對(duì)可調(diào)度任務(wù)比率的影響.圖6所示為隨著參數(shù)CF值增加，即D(HI)與D(LO)逐漸接近時(shí)，對(duì)可調(diào)度任務(wù)比率的影響，總體上看，RCLA可調(diào)度的任務(wù)數(shù)目均優(yōu)于CrMPO.

Fig. 5　The number of high criticality tasks affecting schedulable tasks.圖5　HI任務(wù)數(shù)目對(duì)可調(diào)度任務(wù)比率的影響

Fig. 6　Varying CF affecting schedulable tasks.圖6　不同參數(shù)CF對(duì)可調(diào)度任務(wù)比率的影響

不論隨著HI任務(wù)比率的增加，還是D(HI)與D(LO)差異增加，從實(shí)驗(yàn)數(shù)據(jù)看，二者對(duì)于RCAL的影響相當(dāng)，當(dāng)HI任務(wù)超過一半，或D(HI)D(LO)<0.6，可調(diào)度任務(wù)集中基本上包含的LO任務(wù)已經(jīng)不足13%，且可調(diào)度HI任務(wù)數(shù)目幾乎是呈直線下降趨勢(shì)，即調(diào)度成功的難度會(huì)大大增加.

5結(jié)束語

相對(duì)截止時(shí)限是實(shí)時(shí)任務(wù)最關(guān)鍵的時(shí)間參數(shù)之一，尤其對(duì)硬實(shí)時(shí)任務(wù)而言.在混合關(guān)鍵級(jí)系統(tǒng)中，很多時(shí)候高關(guān)鍵級(jí)任務(wù)需要被更緊急地正確執(zhí)行，即高關(guān)鍵級(jí)時(shí)的截止時(shí)限相較于低關(guān)鍵級(jí)時(shí)的截止時(shí)限更小，即截止時(shí)限是混和關(guān)鍵級(jí)系統(tǒng)的關(guān)鍵參數(shù).但據(jù)現(xiàn)有公開發(fā)表的文獻(xiàn)，從提出混合關(guān)鍵級(jí)系統(tǒng)概念至今，關(guān)鍵級(jí)之間以任務(wù)計(jì)算時(shí)間或周期為關(guān)鍵參數(shù)的混合關(guān)鍵級(jí)系統(tǒng)調(diào)度算法被研究的較多，但是以(相對(duì))截止時(shí)限作為關(guān)鍵參數(shù)的混合關(guān)鍵級(jí)系統(tǒng)的調(diào)度則被研究的極少.本文針對(duì)混和關(guān)鍵級(jí)調(diào)度需求，在單處理器平臺(tái)，基于固定優(yōu)先級(jí)，針對(duì)作為關(guān)鍵參數(shù)的截止時(shí)限的特點(diǎn)，對(duì)以截止時(shí)限為關(guān)鍵參數(shù)的混和關(guān)鍵級(jí)任務(wù)調(diào)度進(jìn)行了任務(wù)建模，應(yīng)用響應(yīng)需求時(shí)間分析，進(jìn)行了以截止時(shí)限為關(guān)鍵參數(shù)的混和關(guān)鍵級(jí)可調(diào)度分析，并提出了預(yù)關(guān)鍵級(jí)提升算法，使得在不同系統(tǒng)關(guān)鍵級(jí)下以及在關(guān)鍵級(jí)切換期間，高關(guān)鍵級(jí)任務(wù)的截止時(shí)限總能得到保證，同時(shí)盡可能讓更多的低關(guān)鍵級(jí)任務(wù)得以執(zhí)行，保證了平臺(tái)計(jì)算資源安全、高效地使用，實(shí)驗(yàn)評(píng)估結(jié)果提供了良好的佐證.

在多處理器平臺(tái)下，尤其是在允許任務(wù)在不同處理器之間遷移時(shí)，保證截止時(shí)限的情況更加復(fù)雜，尤其在混合關(guān)鍵級(jí)系統(tǒng)運(yùn)行在多處理器平臺(tái)時(shí)，計(jì)算能力得到提升，若沒有良好調(diào)度算法的支持，高關(guān)鍵任務(wù)的正確執(zhí)行并不會(huì)得到相應(yīng)的保證，這是我們后續(xù)將繼續(xù)研究的問題.

參考文獻(xiàn)

[1]Homan D. Designing future systems for airworthiness certification[OL]. 2009[2012-01-19]. http:www.cse.wustl.edu～cdgillCPSWEEK09 MCARMCAR%20overview%20BoF%20CPS%20PA%20approved.pdf

[2]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

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

[4]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

[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]Sebastian M, Axer P, Ernst R, et al. Efficient reliability and safety analysis for mixed-criticality embedded systems, PB 2011-01-0445 [R]. Detroit, Michigan: SAE Internatinal, 2011

[7]Guan N, Ekberg P, Stigge M, et al. Improving the scheduling of certifiable mixed-criticality sporadic task systems, PB 2013-008 [R]. Uppsala, Sweden: Department of Information Technology, Uppsala University, 2013

[8]Baruah S, Burns A. Fixed-priority scheduling of dual-criticality systems[C]Proc of the 21st ACM Int Conf on Real-Time Networks and Systems. New York: ACM, 2013: 173-181

[9]Fleming T. Extending mixed criticality scheduling [D]. York, UK: Department of Computer Science, University of York, 2013

[10]Hsiung P A, Lin C Y. Synthesis of real-time embedded software with local and global deadlines[C]Proc of the 1st IEEEACMIFIP Int Conf on HardwareSoftware Codesign and System Synthesis. New York: ACM, 2003: 114-119

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

[12]Baruah S, Burns A. Implementing mixed criticality systems in Ada[C]Proc of the 16th Int Conf on Reliable Software Technologies. Edinburgh, UK: Ada-Europe, 2011: 174-188

[13]Real J, Crespo A. Mode change protocols for real-time systems: A survey and a new proposal[J]. Real-Time Systems, 2004, 26(2): 161-197

[14]Ng C K, Vyas S, Cytron R K, et al. Scheduling challenges in mixed critical real-time heterogeneous computing platforms[J]. Procedia Computer Science, 2013, 18: 1891-1898

[15]Baruah S, Pruhs K. Open problems in real-time scheduling[J]. Journal of Scheduling, 2010, 13(6): 577-582

[16]Ekberg P, Yi W. Bounding and shaping the demand of generalized mixed-criticality sporadic task systems[J]. Real-Time Systems, 2014, 50(1): 48-86

[17]Xiong M, Ramamritham K. Deriving deadlines and periods for real-time update transactions[J]. IEEE Trans on Computers, 2004, 53(5): 567--583

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

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

Huang Lida, born in 1978. PhD candidate and lecturer at Hunan University. Her main research interests include real-time scheduling and embedded software.

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

收稿日期：2015-04-29；修回日期：2015-10-19

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61173036)

中圖法分類號(hào)TP316.2

Scheduling of Mixed Criticality Real-Time Tasks Set with Deadline as the Critical Parameter

Huang Lida and Li Renfa

(CollegeofComputerScienceandElectronicEngineering,HunanUniversity,Changsha410082)

AbstractAn increasing trend in real-time systems is to integrate multiple functionalities of different levels of criticality, or importance, on the same platform, which leads the research of mixed criticality systems. In the current mixed criticality scheduling research, worst-case execution times or periods of high critical-level tasks are critical parameters, which are different between in high-critical mode and low-critical mode. Deadline is also an important time-parameter, especially in hard real-time systems, whereas how to schedule mixed criticality tasks using deadline as the critical parameter is still lack of discussion. This paper considers the mixed criticality scheduling in which deadlines of tasks are the critical parameter on a uniprocessor platform. Towards satisfying schedulability of high-criticality tasks in both modes, we use response time analysis to get timing-demand of fixed priority tasks and propose the raising critical-level in advance (RCLA) scheduling algorithm. RCLA gets high-critical tasks with lower priority to preempt low-critical tasks with higher priority earlier and limitedly. As well as meeting the deadlines of high criticality tasks in high-criticality mode and low-criticality mode, RCLA can schedule mixed criticality tasks as many as possible. Simulation results illustrate the benefits of this scheme.

Key wordsmixed criticality; real-time scheduling; deadline; critical parameter; response time

This work was supported by the National Natural Science Foundation of China (61173036).