事件觸發關鍵級提升的實時任務可調度性分析

黃麗達 李仁發

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

事件觸發關鍵級提升的實時任務可調度性分析

黃麗達 李仁發

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

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

關鍵級；事件觸發；優先級；響應時間；截止時限

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

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

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

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

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

在已公開發表的文獻中，涉及關鍵級提升后優先級是否可交換的研究僅有文獻[16]從抖動的觀點進行了討論.本文針對事件觸發關鍵級提升后，MC任務可能通過優先級交換獲得正確調度的條件進行了分析，并設計了相應的優先級交換算法.

1 任務模型與示例

本節對本文所使用的MC任務模型及相關術語進行定義.引入一個MC任務集運行示例，為后文的優先級可交換分析做準備.

1.1 任務模型

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

響應時間是指任務從釋放到執行完畢這一段時間間隔[17].常用于分析固定優先級任務可調度性.一般實時任務τi的響應時間為

(1)

其中hp(τi)是指優先級高于任務τi的所有任務.稍后將討論關鍵級對于任務響應時間的影響.

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

算法1. OPA算法.

輸入：系統模式χ、n個待分配優先級的周期任務集τ；

輸出：系統模式為χ時，依據優先級從高到低排列的可調度任務序列.

Step1. 總是從最低優先級k開始分配；

Step2. 任取一個li≥χ的任務τi∈τ；

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

Step4. 否則，從τ中重新選擇任務重復Step3.

在每一個關鍵級模式內使用如上OPA算法對任務進行固定優先級分配.OPA算法將確定優先級分配序列的可調度性測試復雜度從n!降低到n(n+1)2.

1.2 動機示例

如表1所示，待調度的混合關鍵級任務集共包括4個任務，分別屬于HI和LO兩個關鍵級.其中，τ1和τ2是HI任務，其在HI模式和LO模式有不同的WCET值；τ3和τ4是LO任務，僅在LO模式時確保執行.設系統最開始運行于LO模式，使用前述OPA算法，這4個任務的優先級分配結果為p3>p4>p1>p2，在LO模式時調度序列如圖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任務集在LO模式的部分調度序列

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

2) 對于HI任務τ2，在執行完畢其低關鍵級時間預算的時刻，恰好也達到了其截止時限，已獲得相對質量較低的執行結果，由于T≥D，在當前周期內任務τ2的此次執行已經結束.

因此，在以執行時間為關鍵參數的MC系統中，當前常用的以高關鍵級任務執行時間超過其低關鍵級WCET的時刻即為關鍵級提升時刻的設定，可視為是一種延遲關鍵級模式切換，即直到HI任務達到其CLO時間預算后才進行關鍵級模式從LO到HI的提升.

下面從外部事件觸發關鍵級提升的觀點，對關鍵級提升期間HI任務的可調度問題以及HI任務之間優先級可交換的問題進行探討.

2 關鍵級提升期間的響應時間分析

圖2所示是一個HI任務τi的執行示例.

Fig. 2 A HI task executing example during a period圖2 一個HI任務的執行示例

因此，以上2種情形HI任務τi在最差情況下的響應時間為

(2)

3 關鍵級提升期內優先級可交換

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

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

輸入：依據優先級遞減順序排列的在關鍵級提升期未滿足調度條件的HI任務子集τ′、可調度的HI任務子集τo；

輸出：依據優先級降序排列的可調度的HI任務子集new_τo.

Step1. 取τo中優先級最低的任務τk，其優先級pk=k；

Step2. 取τ′中優先級最高的任務τi，則其優先級為pi=k+1；

Step5. 更新τi的響應時間為

Step6. 更新τk的響應時間為

Step8. 否則，取優先級為p=k-1的HI任務重復Step3～Step7.

4 仿真與評估

本節對第2節和第3節基于外部事件引發關鍵級提升的MC系統的可調度性進行測試，并對優先級可交換的算法進行了仿真驗證.

4.1 生成測試任務集

借鑒當前MC調度研究的大多數仿真所采用的任務生成方式，使用文獻[8]的方法，測試中所使用的待調度MC任務如下隨機產生：

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

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

3) 對相對截止時限Di，設定Di=Ti；

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

4.2 可調度性測試

文獻[9]認為一旦HI任務執行超過LO模式時的WCET，即認為是關鍵級提升的時刻出現，其混合關鍵級調度算法AMC的結果將作為我們主要的比對、分析對象.

1) AMC.某一個HI任務超出LO模式WCET時，即認為系統關鍵級提升的時刻出現.

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

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

Fig. 3 Percentage of schedulable tasks圖3 可調度任務占總任務數的百分比

Fig. 4 Varying cf to change the value of affecting schedulable tasks圖4 調整參數cf來改變值的可調度任務比率

Fig. 5 Varying cp to change the number of HI tasks affecting schedulable tasks圖5 調整參數cp來改變HI任務數目的可調度比率

Fig. 6 Exchanging the priorities between MC tasks affecting schedulable tasks圖6 交換優先級對可調度任務比率的影響

4.3 優先交換算法的有效性測試

Fig. 7 Exchanging the priorities between varying cf of MC tasks affecting schedulable tasks圖7 交換優先級對調整cf值的可調度任務比率影響

Fig. 8 Exchanging the priorities between varying cp of MC tasks affecting schedulable tasks圖8 交換優先級對調整cp值的可調度任務比率影響

5 結 論

對于混合關鍵級系統而言，由低關鍵級模式到高關鍵級模式的轉換不是由任務執行地變化產生，而是由外部事件引發的，關鍵參數的變化只是關鍵級提升的表現.在以任務執行時間為關鍵參數的混合關鍵級系統中，不論是從確保高關鍵級任務正確執行的魯棒性角度考慮，還是從滿足保守的統一標準驗證的要求考慮，關鍵級提升可能發生在高關鍵級任務在低關鍵級模式下釋放后直至當前周期結束的任何時刻.

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

在后續工作中，將對動態優先級調度方案和多處理器平臺上事件觸發關鍵級提升的混合關鍵級任務調度進行研究.

[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

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

TP316.2