時間/事件觸發(fā)的安全關(guān)鍵系統(tǒng)調(diào)度研究

黃姝娟，劉白林，張 雅，茹 媛

(西安工業(yè)大學(xué)計算機(jī)科學(xué)與工程學(xué)院 西安 710021)

時間/事件觸發(fā)的安全關(guān)鍵系統(tǒng)調(diào)度研究

黃姝娟，劉白林，張 雅，茹 媛

(西安工業(yè)大學(xué)計算機(jī)科學(xué)與工程學(xué)院 西安 710021)

針對大多數(shù)實時操作系統(tǒng)只支持事件觸發(fā)的機(jī)制，該文提出了一種時間和事件雙重觸發(fā)的任務(wù)調(diào)度機(jī)制，并在μC/OS-II的內(nèi)核中進(jìn)行了實現(xiàn)。在該調(diào)度機(jī)制中，針對安全關(guān)鍵任務(wù)模型，提出了一種簡單、易操作的基于關(guān)鍵度(criticality degree based priority, CDBP)的調(diào)度算法，該算法不僅保證了系統(tǒng)處于高級別時，高關(guān)鍵級別任務(wù)的執(zhí)行，而且還保證了系統(tǒng)處于低級別時緊急任務(wù)的執(zhí)行，同時減少了不必要的任務(wù)切換開銷。實驗結(jié)果表明，該算法在提高系統(tǒng)效率方面優(yōu)于OCBP(own criticality based priority)算法。

嵌入式系統(tǒng); 事件觸發(fā); 混合關(guān)鍵; 調(diào)度算法; 時間觸發(fā)

時間或事件觸發(fā)作為操作系統(tǒng)設(shè)計的主流思想在很多領(lǐng)域中得到了廣泛應(yīng)用[1]，然而在航空、航天等領(lǐng)域，由于系統(tǒng)的高可靠性與硬實時性要求，單純的事件觸發(fā)方式無論在設(shè)計還是維護(hù)方面都存在較大困難[2]。而時間觸發(fā)方式在某種程度上會降低系統(tǒng)的靈活性，難以滿足系統(tǒng)需求。尤其在安全關(guān)鍵系統(tǒng)中，為了保證安全關(guān)鍵任務(wù)執(zhí)行的可靠性和確定性，以及整個系統(tǒng)的資源利用率，需要在完成時間觸發(fā)任務(wù)的同時，支持事件觸發(fā)任務(wù)[3]。

1 相關(guān)工作

時間觸發(fā)的操作系統(tǒng)通常按照時間順序分配時間槽來調(diào)度實時任務(wù)。文獻(xiàn)[4]提出了一種改進(jìn)型的Slot-shifting算法，在為時間觸發(fā)任務(wù)預(yù)留時間槽的基礎(chǔ)上，為事件觸發(fā)任務(wù)動態(tài)分配執(zhí)行時間。當(dāng)預(yù)留給時間觸發(fā)任務(wù)的時間槽沒有用完時，剩下的部分可以分配給事件觸發(fā)的任務(wù)；時間觸發(fā)任務(wù)的執(zhí)行時間還可以在預(yù)先定義的時間和離線計算的時間間隔內(nèi)前后移動，以此來提高任務(wù)調(diào)度的靈活性。然而，這種方法的任務(wù)可調(diào)度性分析高度復(fù)雜，系統(tǒng)實現(xiàn)很困難。文獻(xiàn)[5]為了在靜態(tài)調(diào)度中適當(dāng)安排事件觸發(fā)任務(wù)，提出了一種輪詢的方式在固定的時間點為事件觸發(fā)任務(wù)分配時間。文獻(xiàn)[6]和文獻(xiàn)[7]分別提出了基于“super loop”和“Sandwich Delay”的時間觸發(fā)合作式調(diào)度機(jī)制，可以加強系統(tǒng)的確定性并提高系統(tǒng)利用率，但對于非搶占式內(nèi)核顯然會降低系統(tǒng)的靈活性，且對安全關(guān)鍵任務(wù)的支持不夠。文獻(xiàn)[8]以時間觸發(fā)總線和時間觸發(fā)協(xié)議為基礎(chǔ)，研究了計算機(jī)系統(tǒng)架構(gòu)，探討了時間觸發(fā)操作系統(tǒng)的特點。文獻(xiàn)[9]通過對μC/OS-II操作系統(tǒng)的內(nèi)核進(jìn)行擴(kuò)展，在μC/OS-II的任務(wù)管理機(jī)制中增加了對時間觸發(fā)任務(wù)的支持。系統(tǒng)主要根據(jù)預(yù)先安排的時間槽進(jìn)行時間觸發(fā)任務(wù)的調(diào)度，在空閑時刻進(jìn)行基于原μC/OS-II系統(tǒng)的事件觸發(fā)任務(wù)的調(diào)度。這種設(shè)計很好地解決了時間/事件混合觸發(fā)機(jī)制的問題，但是這種擴(kuò)展只在時鐘中斷時進(jìn)行時間/事件觸發(fā)任務(wù)的切換，且時間觸發(fā)任務(wù)被搶占后只能在下一調(diào)度周期才能恢復(fù)，系統(tǒng)利用率較低。

本文基于文獻(xiàn)[9]設(shè)計了一種新的任務(wù)調(diào)度機(jī)制，將時間調(diào)度機(jī)制融入到μC/OS-II中，提出一種CDBP的調(diào)度算法，不僅滿足了時間和事件雙重觸發(fā)的任務(wù)，而且利用任務(wù)結(jié)束到時鐘中斷之間的時間來處理事件觸發(fā)任務(wù)，提高了系統(tǒng)的利用率，保證了安全關(guān)鍵任務(wù)的執(zhí)行。

2 調(diào)度器原型設(shè)計

時間/事件雙重觸發(fā)系統(tǒng)要求能夠同時支持TT(time triggered)任務(wù)和ET(event triggered)任務(wù)。為此，將系統(tǒng)調(diào)度器設(shè)計為時間觸發(fā)調(diào)度模塊和事件觸發(fā)調(diào)度模塊兩大部分，并以時間觸發(fā)調(diào)度部分為上層主要模塊，事件觸發(fā)調(diào)度部分為下層基礎(chǔ)模塊劃分為層次性架構(gòu)。當(dāng)系統(tǒng)只有TT任務(wù)而沒有ET任務(wù)時，系統(tǒng)調(diào)度器則可以關(guān)閉ET任務(wù)調(diào)度，在空閑時間執(zhí)行Idle任務(wù)。

調(diào)度器作為系統(tǒng)內(nèi)核的主要部分，時間觸發(fā)模塊和事件觸發(fā)模塊都向上提供系統(tǒng)服務(wù)API，向下都能和硬件通信交互。時間觸發(fā)模塊包括TT任務(wù)間的同步與通信、中斷管理以及任務(wù)超時等錯誤處理。事件觸發(fā)模塊包括ET任務(wù)間的同步與通信、中斷管理、資源管理、內(nèi)存管理與警報等。系統(tǒng)調(diào)度器原型如圖1所示。

圖1 時間/事件雙重觸發(fā)系統(tǒng)調(diào)度器原型

3 調(diào)度算法設(shè)計

3.1 安全關(guān)鍵任務(wù)模型設(shè)計

安全關(guān)鍵系統(tǒng)中的任務(wù)具有4個重要屬性：發(fā)布時間、時限、關(guān)鍵級別和最壞執(zhí)行時間。其中最壞執(zhí)行時間是1個多維向量，向量值與任務(wù)的關(guān)鍵級別相關(guān)，各元素表示任務(wù)在各個級別下的最壞執(zhí)行時間[10]。下面對多關(guān)鍵級別的安全關(guān)鍵任務(wù)模型進(jìn)行形式化的定義。

定義 1 在1個有K個關(guān)鍵級別的安全關(guān)鍵系統(tǒng)中，關(guān)鍵級別最低為1，最高為K，任務(wù)表示為Ji，則有Ji=(Xi,Ai, Di,Ci)。其中，Xi表示任務(wù)Ji的關(guān)鍵級別；iA表示任務(wù)的發(fā)布時間；Di表示任務(wù)的時限；Ci表示任務(wù)的最壞執(zhí)行時間，Ci是一個向量，Ci=(Ci(1),Ci(2),…,Ci(K ))，Ci(1)表示任務(wù)Ji在關(guān)鍵級別為1時的最壞執(zhí)行時間，Ci(2)表示任務(wù)Ji在關(guān)鍵級別為2時的最壞執(zhí)行時間，Ci(K )表示任務(wù)Ji在關(guān)鍵級別為K時的最壞執(zhí)行時間。若K＞Xi時，有Ci(K)=Ci(Xi)。本文的方法是基于狀態(tài)切換的，研究的對象只限定在兩個關(guān)鍵級別的系統(tǒng)中，即任務(wù)只具有一高一低兩種安全關(guān)鍵級別。在一個具有2個關(guān)鍵級別的系統(tǒng)中，低關(guān)鍵級別為1，高關(guān)鍵級別為2，任務(wù)表示為Ji=(Xi,Ai, Di, Ci(1),Ci(2))。

設(shè)想系統(tǒng)中有兩個任務(wù)，其中J1的關(guān)鍵級別為1，J2的關(guān)鍵級別為2。當(dāng)系統(tǒng)處于1級關(guān)鍵級別而J2未能在C2(1)時間內(nèi)執(zhí)行完時，系統(tǒng)會提升至2級關(guān)鍵級別，以保證J2在C2(2)時間內(nèi)能完成執(zhí)行，這時J1的執(zhí)行情況則不再重要。因此，對于低關(guān)鍵級別的任務(wù)J1來說，系統(tǒng)不會允許它的執(zhí)行時間超過C1(1)。

上述筆者分析了現(xiàn)階段我國企業(yè)財務(wù)內(nèi)控精細(xì)化管理當(dāng)中存在的一系列的問題，為了提高企業(yè)財務(wù)管理和企業(yè)整體的經(jīng)營管理水平，有必要對財務(wù)內(nèi)控精細(xì)化管理工作進(jìn)行強化和改善，如此才能有效促進(jìn)企業(yè)在行業(yè)發(fā)展當(dāng)中獲得更多、更好的發(fā)展，促進(jìn)企業(yè)經(jīng)濟(jì)效益提高。下面將對強化企業(yè)財務(wù)內(nèi)控精細(xì)化管理的要點進(jìn)行分析。

由上述分析，可以得出兩點結(jié)論：

1) 對于所有的任務(wù)Ji，都有Ci(2)≥Ci(1)；

2) 如果任務(wù)Ji的Xi= 1，那么Ci(2)=Ci(1)。

對于兩級安全關(guān)鍵任務(wù)的系統(tǒng)I，需要設(shè)計關(guān)鍵級別不同的兩張調(diào)度表，低關(guān)鍵級別狀態(tài)下的S1和高關(guān)鍵級別狀態(tài)下的S2。兩張調(diào)度表的時間均從第一個任務(wù)的發(fā)布時間開始，到最后一個任務(wù)的時限結(jié)束，即[minJi∈I{Ai},maxJi∈I{Di}]。對于任意時刻t∈[minJi∈I{Ai},maxJi∈I{Di}]，S1(t)和S2(t)分別表示調(diào)度表中t時刻應(yīng)該運行的任務(wù)。在系統(tǒng)運行過程中，對任務(wù)的調(diào)度執(zhí)行遵循下列規(guī)則：

1) 系統(tǒng)當(dāng)前所處的關(guān)鍵級別用Γ表示，而系統(tǒng)剛開始運行時，Γ=1。

2) 當(dāng)Γ=1時，在每一時刻t，任務(wù)Si(t)執(zhí)行。

如果當(dāng)前運行的任務(wù)Ji在Ci(1)時刻還未結(jié)束，那么系統(tǒng)在低關(guān)鍵級別下的調(diào)度表已經(jīng)無法按計劃完成了，這時系統(tǒng)需要提升關(guān)鍵級別，令Γ=2，也就是說此時將進(jìn)行狀態(tài)切換。

3) 當(dāng)Γ=2時，在每一時刻t，任務(wù)S2(t)執(zhí)行。

如果對于兩級安全關(guān)鍵任務(wù)系統(tǒng)I，能設(shè)計出滿足上述規(guī)則的兩張調(diào)度表S1和S2，則說I是時間觸發(fā)可調(diào)度的(TT schedulable)[11]。

現(xiàn)有一個兩級混合關(guān)鍵系統(tǒng)I，系統(tǒng)中有3個任務(wù)，其相關(guān)屬性如表1所示。

對于這個安全關(guān)鍵系統(tǒng)來說，圖2為一種可行的任務(wù)調(diào)度表。開始系統(tǒng)處于低關(guān)鍵級別，根據(jù)調(diào)度表S1來進(jìn)行任務(wù)調(diào)度：時刻0，任務(wù)J1到達(dá)，即可觸發(fā)調(diào)度器進(jìn)行調(diào)度；時刻1，任務(wù)J2觸發(fā)，此時任務(wù)J1尚未執(zhí)行完畢即被J2搶占，J2開始執(zhí)行；時刻2，任務(wù)J3觸發(fā)，如果J2完成執(zhí)行(即J2運行時間小于等于C2(1))，那么J3即可按時執(zhí)行；到時刻3，當(dāng)J3執(zhí)行完時，此時系統(tǒng)處于空閑，可恢復(fù)之前因被搶占而掛起的任務(wù)J1。所有任務(wù)均正常執(zhí)行，沒有超過時限。

表1 示例任務(wù)屬性表

這是系統(tǒng)運行順利情況下的任務(wù)調(diào)度。如果到時刻2，J2運行時間已等于低關(guān)鍵級別的最壞執(zhí)行時間C2(1)，仍未執(zhí)行完時，系統(tǒng)會將關(guān)鍵級別從1提升至2，并進(jìn)行狀態(tài)切換，調(diào)度器使用的調(diào)度表由S1切換到S2。J2會保持運行直到時刻3。在系統(tǒng)處于高關(guān)鍵級別時，不再對低關(guān)鍵級別的任務(wù)J3提供任何保障。到時刻3，J2運行時間達(dá)到高關(guān)鍵級別下最壞執(zhí)行時間C2(2)，完成運行后，系統(tǒng)恢復(fù)之前因被搶占而掛起的任務(wù)J1。

圖2 示例任務(wù)調(diào)度表

3.2 調(diào)度表的創(chuàng)建

本文研究的是時間/事件觸發(fā)的安全關(guān)鍵任務(wù)的調(diào)度，時間觸發(fā)要求系統(tǒng)確定性好，使用資源預(yù)留的方法提前創(chuàng)建調(diào)度表，有利于提高系統(tǒng)的確定性。而事件觸發(fā)則希望調(diào)度過程可以發(fā)生任務(wù)搶占，以此來保證高關(guān)鍵級別任務(wù)和緊急任務(wù)。為此，本文研究的調(diào)度方法，將時間預(yù)留和優(yōu)先級搶占方法結(jié)合起來。創(chuàng)建調(diào)度表的時候首先根據(jù)任務(wù)在該級別下的最壞執(zhí)行時間，為各個任務(wù)分配好時間槽；然后再給各個任務(wù)分配優(yōu)先級，允許高優(yōu)先級任務(wù)對低優(yōu)先級任務(wù)進(jìn)行搶占。

OCBP算法[12]的思想是如果調(diào)度可以順利進(jìn)行，每次找出剩余任務(wù)中優(yōu)先級最低的任務(wù)，當(dāng)所有任務(wù)都被指派優(yōu)先級或者剩余的任務(wù)在當(dāng)前的優(yōu)先級都不能被調(diào)度時，算法終止。該算法的缺陷有兩個：一是任務(wù)分配過程中主要考慮任務(wù)的關(guān)鍵級別，與任務(wù)優(yōu)先級無關(guān)；二是如果找不到最低優(yōu)先級任務(wù)時，該算法就失敗了。而本文提出的CDBP算法則全面考慮了任務(wù)的關(guān)鍵級別和緊急程度，且調(diào)度表的創(chuàng)建不會因為找不到最低優(yōu)先級任務(wù)而終止。

定義 2 相對關(guān)鍵度iρ，是指在具有n個任務(wù)的系統(tǒng)I中，任務(wù)Ji相對于其他任務(wù)的關(guān)鍵級別的重要程度。用來表示，其中xi和xj是各任務(wù)在系統(tǒng)某個統(tǒng)一時刻的關(guān)鍵級別[13]。

假設(shè)系統(tǒng)中有4個任務(wù)，關(guān)鍵級別分別為1，2， 1，2，則iρ分別為。

定義 3 關(guān)鍵額度iδ，是指在具有K個關(guān)鍵級別的系統(tǒng)I中，Ji當(dāng)前所處級別在當(dāng)前系統(tǒng)的關(guān)鍵級別k下所具有的關(guān)鍵份數(shù)。用來表示，其中xi是任務(wù)的當(dāng)前關(guān)鍵級別。假設(shè)系統(tǒng)中有兩個任務(wù)J1和J2，其中X1=1，X2=2，則K=2。當(dāng)系統(tǒng)關(guān)鍵級別k=1時，任務(wù)J1和J2的當(dāng)前關(guān)鍵級別x1和x2也都是1，則；當(dāng)系統(tǒng)關(guān)鍵級別k=2時，x1=1和x2=2，則，δ2=1。

定義 4 時限緊急度di是指任務(wù)時限的先后對任務(wù)的緊急程度的影響，用來表示。在同等情況下，時限更早到來的任務(wù)應(yīng)該具有更高的優(yōu)先級。

根據(jù)CDBP算法為任務(wù)分配優(yōu)先級的流程如圖3所示。

圖3 CDBP算法優(yōu)先級分配流程圖

在CDBP的算法中，在K關(guān)鍵級別下關(guān)鍵度越大的任務(wù)具有的優(yōu)先級越高。在兩個任務(wù)關(guān)鍵度相同的情況下，若系統(tǒng)處于低關(guān)鍵級別或者兩個任務(wù)的關(guān)鍵級別相同時，時限越早的任務(wù)優(yōu)先級越高；若兩個任務(wù)關(guān)鍵級別不同且系統(tǒng)處于高關(guān)鍵級別，則關(guān)鍵級別高的任務(wù)優(yōu)先級高。

4 實驗結(jié)果

本文是在嵌入式應(yīng)用的開發(fā)平臺Xilinx Virtex-5 FXT FPGA ML507上進(jìn)行的實驗，所設(shè)計的調(diào)度器也最終移植到該平臺上進(jìn)行了測試。

測試用例任務(wù)集有3個ET任務(wù)和4個時間觸發(fā)的安全關(guān)鍵任務(wù)，其中ttTask2和ttTask4是高安全關(guān)鍵級別任務(wù)，ttTask1和ttTask3是低關(guān)鍵級別任務(wù)。圖4和圖5顯示了往ttTask2添加額外負(fù)載前后的運行情況對比，從圖中可看出，開始ttTask2能夠在低關(guān)鍵級別下的1個單位的時間內(nèi)執(zhí)行完畢，添加額外負(fù)載后，ttTask2無法按時完成，這時為了保證ttTask2能正常執(zhí)行完，系統(tǒng)提升關(guān)鍵級別，ttTask1和ttTask3的執(zhí)行不再得到保證，最終系統(tǒng)保證ttTask2、ttTask4和etTask1、etTask2、etTask3順利執(zhí)行完畢。該實驗說明實現(xiàn)的多級調(diào)度表達(dá)到了設(shè)計要求，調(diào)度表成功切換，為高關(guān)鍵級別任務(wù)提供了保障。

圖4 低關(guān)鍵級別調(diào)度示意圖

圖5 高關(guān)鍵級別調(diào)度示意圖

[1] HEEMELS W, DONKERS M C F, TEEL A R. Periodic event-triggered control for linear systems[J]. IEEE Journal of Transactions on Automatic Control, 2013, 58(4): 847-861.

[2] KOPETZ H. The complexity challenge in embedded system design[C]//The 2008 IEEE 11th International Symposium on Object OrientedReal-Time Distributed Computing (ISORC). Orlando: IEEE Computer Society, 2008, 5: 3-12.

[3] MARTIJN M H P, BRIL R J, LUKKIEN J J, et al. RTOS support for mixed time-triggered and event-triggered task sets[C]//The 2012 IEEE 15th International Conference on Computational Science and Engineering. Washington, USA: IEEE Computer Society, 2012, 12: 578-585.

[4] BARUAH S K, BURNS A, DAVIS R I. Response-time analysis for mixed criticality systems[C]//The 2011 IEEE 32nd Real-Time Systems Symposium (RTSS). Vienna: IEEE Computer Society, 2011, 11: 34-43.

[5] THEIS J, FOHLER G. Transformation of sporadic tasks for off-line scheduling with utilization and response time trade-offs[C]//The 19th Conference on Real-Time and Network Systems. Nantes, France: [s.n.], 2011, 9: 119-128.

[6] NAHAS M. Employing two ‘sandwich delay’ mechanisms to enhance predict-ability of embedded systems which use time-triggered co-operative architectures[J]. Journal of Software Engineering and Applications, 2011, 4(7): 411-417.

[7] PONT M J, KURIAN S, BAUTISTA Q R. Meeting realtime constraints using “Sandwich Delays”[M]. Lecture Notes in Computer Science, 2009(5770): 94-102.

[8] 蘇羅輝, 牛萌, 劉坤. 時間觸發(fā)系統(tǒng)體系結(jié)構(gòu)研究[J]. 計算機(jī)工程與設(shè)計, 2014, 35(6): 1956-1961.

SU Luo-hui, NIU Meng, LIU Kun. Study on time-triggered system architecture[J]. Computer Engineering and Design, 2014, 35(6): 1956-1961.

[9] 陳曦, 呂偉杰, 劉魯源. 事件/時間觸發(fā)嵌入式操作系統(tǒng)內(nèi)核的設(shè)計[J]. 計算機(jī)工程與應(yīng)用, 2009, 44(16): 87-89.

CHEN Xi, Lü Wei-jie, LIU Lu-yuan. Design of eventtriggered and time-triggered embedded operating system kernel[J]. Computer Engineer and Appllications, 2009, 44(16): 87-89.

[10] VESTAL S. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[C]//The IEEE 28th International on Real-Time Systems Symposium (RTSS). Washington, USA: IEEE Computer Society, 2007, 12: 239-243.

[11] BARUAH S, FOHLER G. Certification-cognizant timetriggered scheduling of mixed-criticality systems[C]//The 2011 IEEE 32nd Real-Time Systems Symposium (RTSS). Vinenna：IEEE Computer Society, 2011, 11: 3-12.

[12] GU C, GUAN N, DENG Q, et al. Improving OCBP-based scheduling for mixed-criticality sporadic task systems[C]// The 2013 IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA). Seoul: IEEE Computer Society, 2013, 10: 247-256.

[13] 朱怡安, 黃姝娟, 段俊花, 等. 新的混合關(guān)鍵任務(wù)調(diào)度算法的研究[J]. 電子科技大學(xué)學(xué)報, 2014, 43(2): 268-271.

ZHU Yi-an, HUANG Shu-juan, DUAN Jun-hua, et al. New scheduling algorithm for mixed-criticality real-time task sets[J]. Journal of University of Electronic Science and Technology of China, 2014, 43(2): 268-271.

編 輯 蔣 曉

Study on Scheduling Mechanism in Time-Triggered and Event-Triggered Safety Critical System

HUANG Shu-juan, LIU Bai-lin, ZHANG Ya, and RU Yuan

(School of Computer Science and Engineering, Xi’an Technological University Xi’an 710021)

For most real-time operating systems, only the event-triggered mechanism is supported. This paper proposes a scheduling mechanism which can support not only time-triggered but also event-triggered tasks in μC/OS-II. For safety critical tasks in this embedded system, a simple and easy scheduling algorithm is also presented based on criticality degree based priority (CDBP). This algorithm ensures the execution of the emergency tasks at a low level and the execution of the higher critical tasks at the high level while reducing the unnecessary task switching overhead. Experimental results show that the proposed algorithm is better than own criticality based priority(OCBP) algorithm in improving the system efficiency and provides better support for the criticality tasks and emergency tasks.

embedded system; event-triggered; mixed-criticality; scheduling algorithm; time-triggered

TP319

A

10.3969/j.issn.1001-0548.2017.03.025

2015 ? 12 ? 29；

2016 ? 09 ? 27

陜西省工業(yè)科技攻關(guān)項目(2015GY031)

黃姝娟(1975 ? )，女，博士，主要從事嵌入式與分布式計算方面的研究.