黃麗達　　　李仁發(fā)

(湖南大學信息科學與工程學院　長沙　410082)

?

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

黃麗達李仁發(fā)

(湖南大學信息科學與工程學院長沙410082)

(hld_jt@hnu.edu.cn)

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

關鍵詞混合關鍵級；實時調(diào)度；截止時限；關鍵參數(shù)；響應時間

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

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

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

1任務模型與定義

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

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

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

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

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

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

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

Fig. 1　HI-task at the time of raising critical-level.圖1　關鍵級提升時刻對任務的影響

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

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

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

(1)

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

對于前述情況2進行2點討論：

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

② 若ai+Di(HI)

Ci,0=

(2)

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

(3)

即，若滿足：

(4)

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

3預先提升關鍵級

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

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

(5)

(6)

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

(7)

(8)

(9)

Table 1　An Example of Mixed-Criticality Task Set

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

Fig. 2　Scheduling in Low-Criticality with DM.圖2　低關鍵級時使用DM調(diào)度任務集

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

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

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

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

Fig. 3　Scheduling with RCLA.圖3　使用預關鍵級提升的調(diào)度方案

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

算法1. 預關鍵級提升RCLA.

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

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

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

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

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

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

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

4仿真結果與分析

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

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

仿真實驗中用到的任務集參數(shù)按照5個過程隨機生成：

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

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

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

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

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

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

(10)

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

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

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

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

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

5結束語

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

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

參考文獻

[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

基金項目：國家自然科學基金項目(61173036)

中圖法分類號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).