一種不精確離散事件系統(tǒng)建模與仿真

李妮

(西安明德理工學(xué)院，通識教育學(xué)院，陜西，西安 710124)

0 引言

實(shí)時(Real Time,RT)系統(tǒng)通常由嵌入在硬件中的軟件組件構(gòu)建，這些軟件組件與環(huán)境以滿足時序約束的方式進(jìn)行交互。RT系統(tǒng)主要應(yīng)用于自動駕駛儀、電廠控制、運(yùn)輸和電信到客戶電子設(shè)備、醫(yī)療設(shè)備、智能和自動化系統(tǒng)等領(lǐng)域[1-2]。

近年來，RT系統(tǒng)在數(shù)量、復(fù)雜性、安全性、可靠性、容錯性、功耗等方面需求不斷增長，這對RT系統(tǒng)的設(shè)計提出了新的挑戰(zhàn)[3-4]。為此，眾多學(xué)者提出了不同的形式化方法來設(shè)計和開發(fā)RT系統(tǒng)。王高才等[5]基于隨機(jī)模型研究了軟實(shí)時系統(tǒng)中任務(wù)的可調(diào)度性特征，并提出了期望可調(diào)度性的概念。夏平等[6]基于安全分級思想，構(gòu)建了一個適應(yīng)動態(tài)安全需求的實(shí)時調(diào)度模型。吳堯輝等[7]針對供電綜合保護(hù)器任務(wù)多且前后臺系統(tǒng)實(shí)時性差的問題，提出了一種針對實(shí)時操作系統(tǒng)的中斷管理機(jī)制，同時進(jìn)行多任務(wù)中斷管理設(shè)計。上述方法設(shè)計時進(jìn)行了形式化說明和分析，這有助于提高最終系統(tǒng)的可靠性，但是增加了設(shè)計的復(fù)雜性及可靠性開發(fā)成本。此外，部分方法設(shè)計時未考慮系統(tǒng)溢出問題，由此高計算峰值將對系統(tǒng)性能產(chǎn)生嚴(yán)重影響。

本文形式化定義了含不精確計算(Imprecise Computing,IC)技術(shù)的離散事件模型，將系統(tǒng)的行為分為強(qiáng)制和可選兩部分，為用戶提供了靈活性，從而實(shí)現(xiàn)處理器更可靠的RT任務(wù)調(diào)度過程。

1 相關(guān)概念

1.1 實(shí)時系統(tǒng)及不精確計算

IC技術(shù)是處理瞬時過載下RT系統(tǒng)調(diào)度問題的有效方法[8]。該方法將任務(wù)的關(guān)鍵(強(qiáng)制)部分與其非關(guān)鍵(可選)部分分離，從而使RT系統(tǒng)能夠接受更多的任務(wù)，同時嘗試運(yùn)行盡可能多的可選子任務(wù)。這允許動態(tài)配置系統(tǒng)，以便在系統(tǒng)處理流量較大時，通過生成不太準(zhǔn)確的結(jié)果來接受更多的任務(wù)；另一方面，在系統(tǒng)負(fù)擔(dān)較低時，完全執(zhí)行任務(wù)以生成準(zhǔn)確的結(jié)果。

考慮到可搶占任務(wù)的任務(wù)集為T=(T1,T2,…,Tn)，針對每個任務(wù)Ti(i∈[1,n])定義以下參數(shù)：ri是任務(wù)Ti釋放的時間；di是任務(wù)Ti必須完成的截止日期；ti是任務(wù)Ti所需的處理時間；wi是任務(wù)Ti的權(quán)重，表示該任務(wù)的相對重要程度。

每個任務(wù)Ti由2個子任務(wù)組成：強(qiáng)制和可選,則有

mi+oi=ti

(1)

其中，mi為強(qiáng)制子任務(wù)Mi需要處理時間，ti為oi可選子任務(wù)Oi的需要處理時間。

在可調(diào)度RT系統(tǒng)中，當(dāng)相關(guān)作業(yè)中包括的每個任務(wù)Ti的至少所有強(qiáng)制子任務(wù)被執(zhí)行時(作業(yè)是在執(zhí)行期間發(fā)生的任務(wù)的實(shí)例)，則每個任務(wù)Ti處于正在執(zhí)行階段。任務(wù)Ti的可選子任務(wù)只有在Ti的強(qiáng)制子任務(wù)正確執(zhí)行時才可執(zhí)行。調(diào)度器可以在可選子任務(wù)執(zhí)行期間的任何時間終止該子任務(wù)?；谶@個定義，完美硬RT系統(tǒng)是所有任務(wù)都由強(qiáng)制子任務(wù)組成的系統(tǒng)，完美軟RT系統(tǒng)是所有子任務(wù)都是可選的系統(tǒng)。RT系統(tǒng)中的一個常見問題是，當(dāng)系統(tǒng)沒有足夠的處理資源來完成所有請求進(jìn)程時，會出現(xiàn)溢出情況。這個問題將給被控機(jī)器帶來嚴(yán)重威脅，并可能導(dǎo)致災(zāi)難性的后果。

1.2 離散事件系統(tǒng)模型

離散事件系統(tǒng)(Discrete Event System,DEVS)模型[9-10]可描述為一組基本的原子模型和復(fù)合模型。原子模型仍然是最基本的結(jié)構(gòu)，它可以與其他模型組合成復(fù)合模型。DEVS原子模型具有以下結(jié)構(gòu)，

AM=〈XM,YM,S,δext,δint,δcon,λ,ta〉

(2)

假定在任意時間內(nèi)，基本模型處于s狀態(tài)。在沒有外部事件的情況下，它將在ta(s)定義的一段時間內(nèi)保持該狀態(tài)。當(dāng)發(fā)生內(nèi)部狀態(tài)轉(zhuǎn)換時，系統(tǒng)輸出值為λS，此時狀態(tài)更新為δint(S)。如果外部事件E={x1,x2,…,xn/x∈XM}在ta(s)過期之前發(fā)生，即當(dāng)系統(tǒng)處于e≤ta(s)的狀態(tài)(s,e)時，新的狀態(tài)將由δext(s,e,E)給出。假設(shè)一個外部轉(zhuǎn)移和一個內(nèi)部轉(zhuǎn)移同時到達(dá)，即當(dāng)e=ta(s)時，一個外部事件E發(fā)生，新系統(tǒng)的狀態(tài)可以由δext(δint(s),e,E)或δint(δext(s,e,E))給出。需注意，可采用δcon函數(shù)定義模型最合適的行為。因此，新系統(tǒng)的狀態(tài)將由δcon(s,E)定義。

復(fù)合模型指將基本模型連接在一起形成的新模型。這個模型本身可以作為一個更大的復(fù)合模型組成更加復(fù)雜的模型層次結(jié)構(gòu)。復(fù)合模型定義為

CM=〈X,Y,D,EIC,EOC,IC〉

(3)

其中，X是輸入端口和值的集合，Y是輸出端口和值的集合，D是組件名稱的集合，EIC(外部輸入復(fù)合)將復(fù)合模型本身的輸入事件連接到其組件的一個或多個輸入事件，EOC(外部輸出復(fù)合)將組件的輸出事件連接到復(fù)合模型本身的輸出事件，IC(內(nèi)部復(fù)合)將組件的輸出事件連接到其他組件的輸入事件。

2 不精確離散事件系統(tǒng)

本文在RT任務(wù)調(diào)度中引入不精確離散事件模型，結(jié)合離散事件的動態(tài)優(yōu)勢和形式化建模方法的嚴(yán)密性，同時利用不精確計算用來處理由于系統(tǒng)中發(fā)生過載溢出情況產(chǎn)生的錯誤問題。

2.1 RT-DEV

實(shí)時系統(tǒng)離散事件驅(qū)動模型(RT-DEVS)運(yùn)行時引擎中的主要計算發(fā)生在狀態(tài)轉(zhuǎn)換函數(shù)(即模型者在原子模型中定義的函數(shù))以及調(diào)度和消息傳輸[11]。該模型為實(shí)時系統(tǒng)提供了一種基于建模與仿真的設(shè)計方案方法，可以在實(shí)際開發(fā)和部署之前對系統(tǒng)組件進(jìn)行仿真，并進(jìn)行形式化分析。

實(shí)時系統(tǒng)的最關(guān)鍵特性是在規(guī)定的截止日期內(nèi)輸出的可用性[12]。RT-DEVS為原子組件中的每個輸出指定一個截止日期，并驗(yàn)證相關(guān)輸出生成時的截止日期。因此，將概念引入形式化模型，并在抽象的仿真機(jī)制中實(shí)現(xiàn)。RT-DEVS具體定義如，

AMRT=〈X,S,δext,δint,δcon,λ,ta,d〉

(4)

假設(shè)消息傳輸具有與系統(tǒng)中標(biāo)準(zhǔn)任務(wù)之間的上下文切換相關(guān)的開銷，那么RT-DEVS系統(tǒng)中的任務(wù)集由轉(zhuǎn)換和輸出函數(shù)組成。此信息用于將實(shí)時系統(tǒng)模擬器運(yùn)行的DEV函數(shù)(δext，δint，δcon和λ)映射到實(shí)時系統(tǒng)內(nèi)核和調(diào)度器中。RT-DEVS系統(tǒng)中的一組任務(wù)由狀態(tài)轉(zhuǎn)移和實(shí)時系統(tǒng)模擬器運(yùn)行的輸出函數(shù)(δext，δint和λ)組成。圖1顯示了在狀態(tài)轉(zhuǎn)換期間一個RT-DEVS系統(tǒng)中原子組件的處理任務(wù)示意圖。假設(shè)每個轉(zhuǎn)換函數(shù)占用1個時間單位，且各函數(shù)之間的上下文本切換忽略不計，圖中顯示了將DEV轉(zhuǎn)換函數(shù)映射到調(diào)度時間表的具體過程。

圖1 原子組件的處理任務(wù)示意圖

如圖1所示，外部轉(zhuǎn)換(δext)映射到TX任務(wù)中，該任務(wù)啟動狀態(tài)S。此時任務(wù)的釋放時間等于輸入到達(dá)系統(tǒng)的時間。需注意，由于TX是一個可以隨時到達(dá)的輸入，因此不設(shè)截止日期?？紤]到DEVS中的輸出總是緊跟著內(nèi)部轉(zhuǎn)換，故輸出任務(wù)Tλ和內(nèi)部轉(zhuǎn)換δint任務(wù)TI將同時執(zhí)行，形成了TλTI任務(wù)。任務(wù)TλTI的釋放時間等于狀態(tài)S的結(jié)束時間，且由ta(s)指定(即圖2中的T)。

圖2 一個典型的多輸入過載場景

假設(shè)系統(tǒng)接收大量輸入，因此系統(tǒng)需要執(zhí)行許多轉(zhuǎn)換并生成相應(yīng)的輸出，從而使輸出任務(wù)延遲，嚴(yán)重時將超過某些狀態(tài)截止日期。圖2所示為一個典型的包含4個輸入的過載場景，系統(tǒng)在不同的原子組件上開始執(zhí)行外部轉(zhuǎn)換。Ti(i∈[1,4])為每個任務(wù)的時間推進(jìn)函數(shù)ta(s)觸發(fā)的任務(wù)發(fā)布時間。di(i∈[1,4])為每個任務(wù)的相關(guān)截止日期。假定系統(tǒng)中只有一個處理器執(zhí)行轉(zhuǎn)換函數(shù)(時間線下顯示為黃色/綠色/紅色)。可以看出，Tλ1、Tλ2和Tλ4滿足了截止日期期限；與之相反，Tλ3和Tλ2(在系統(tǒng)時間18時由內(nèi)部轉(zhuǎn)換產(chǎn)生的第二個實(shí)例)并沒有滿足截止日期期限。內(nèi)部轉(zhuǎn)換任務(wù)TI2生成一個新狀態(tài)，其ta(s)為4個時間單位，超過了時間17的截止日期。如果連續(xù)發(fā)生多個內(nèi)部轉(zhuǎn)換任務(wù)，則可以避免這種情況。然而，如果系統(tǒng)能夠盡早檢測到過載情況，從而應(yīng)用基于不精確的調(diào)度，則可以防止這種情況的發(fā)生。

為了避免這種過載情況，將任務(wù)分為強(qiáng)制部分和可選部分。原子模型的狀態(tài)分為強(qiáng)制狀態(tài)和可選狀態(tài)。強(qiáng)制狀態(tài)將導(dǎo)致強(qiáng)制輸出函數(shù)(表示為輸出任務(wù))，而可選狀態(tài)將導(dǎo)致可選輸出任務(wù)。假設(shè)輸入TX任務(wù)始終是強(qiáng)制性的(以避免丟失任何輸入)，由Tλ表示的非關(guān)鍵輸出是可選的?？蛇xTλT1任務(wù)的Tλ子任務(wù)可以在瞬時重載下終止。換句話說，在超限情況下，系統(tǒng)跳過可選輸出以節(jié)省時間和資源。例如，在有大量偵察和控制任務(wù)的緊急任務(wù)情況下，飛機(jī)或汽車控制系統(tǒng)可以放棄信息娛樂任務(wù)以響應(yīng)緊急控制命令。類似的情況也可以發(fā)生在任何實(shí)時系統(tǒng)中，即可以跳過一系列非關(guān)鍵輸出，通過保持所需的輸出按時產(chǎn)生來減輕過載情況。

2.2 I-DEVS

本節(jié)目的是為工作到達(dá)時間未知的應(yīng)用程序提供一個不精確離散事件系統(tǒng)(I-DEVS)框架。該方法試圖在系統(tǒng)繁忙時平衡計算，另一方面又不降低其性能，同時盡可能降低實(shí)現(xiàn)的運(yùn)行時開銷。該方法思路是將不精確理論概念與DEVS建模相結(jié)合。

在RT-DEV模型基礎(chǔ)上，I-DEVS為每個狀態(tài)添加強(qiáng)制或可選條件，具體描述為

AM=〈X,Y,δext,δint,δcon,λ,ta,d〉

(5)

原子模型的狀態(tài)分為強(qiáng)制狀態(tài)和可選狀態(tài)。強(qiáng)制狀態(tài)將具有強(qiáng)制輸出函數(shù)(表示為輸出任務(wù))，而可選狀態(tài)將生成可選輸出任務(wù)。在狀態(tài)機(jī)級別定義強(qiáng)制性任務(wù)和可選任務(wù)時，這種抽象允許建立不精確的模型，而不涉及較低級別任務(wù)系統(tǒng)的細(xì)節(jié)。這個工件允許實(shí)現(xiàn)一個執(zhí)行模型的實(shí)時引擎，使執(zhí)行機(jī)制(在模擬模式下運(yùn)行的“模擬器”，或在實(shí)時模式下運(yùn)行的“實(shí)時引擎”)獨(dú)立于模型規(guī)范，使這些執(zhí)行工件和相關(guān)可調(diào)度性測試更容易實(shí)現(xiàn)。

3 案例與分析

本節(jié)將以實(shí)際案例建立一個復(fù)雜實(shí)時系統(tǒng)模型，該系統(tǒng)包含20個原子組件，每個組件都配有輸入端口和輸出端口。復(fù)合模型基本結(jié)構(gòu)如圖3(a)所示，系統(tǒng)連接原子組件將輸入傳播到其他組件，由此頻繁創(chuàng)建Tλ和TI任務(wù)群將導(dǎo)致溢出情況。當(dāng)I-DEVS執(zhí)行引擎檢測此類情形時，系統(tǒng)可根據(jù)提出的基于IC方法進(jìn)行計算處理。

原子組件遵循圖3(b)中的DEVS圖。模型由初始狀態(tài)、可選狀態(tài)和強(qiáng)制狀態(tài)組成。每當(dāng)有輸入時，模型就從“空閑”狀態(tài)轉(zhuǎn)換到“強(qiáng)制”狀態(tài)，在500 ms(狀態(tài)生存期)之后，它產(chǎn)生一個輸出并轉(zhuǎn)換到“可選”狀態(tài)(因?yàn)檫@是一個復(fù)合模型，輸入和輸出值也是復(fù)合的；在示例中的DEVS圖中，它接收并發(fā)送一個值1)。該模型在“強(qiáng)制”和“可選”狀態(tài)之間切換，每500 ms產(chǎn)生一次輸出，用于進(jìn)行綜合性能測試，比較不精確執(zhí)行和精確執(zhí)行的結(jié)果。在精確執(zhí)行的情況下，系統(tǒng)默認(rèn)所有的值都是強(qiáng)制性的。此外，假定輸入在執(zhí)行1 s后注入到模型中，以便觸發(fā)狀態(tài)變換和輸出信息。

圖3 復(fù)合模型基本結(jié)構(gòu)

圖4所示為不同模式下的強(qiáng)制任務(wù)平均響應(yīng)時間，其中執(zhí)行時間分別為20 s、50 s、70 s、120 s和180 s，處理時間為10 s(對于Tλ)，處理時間為5 s(對于TI)。可以看出，由于丟棄可選任務(wù)作為防止一次溢出的措施，非精確模式下的平均響應(yīng)時間小于精確模式。此外，圖4還顯示了丟棄的可選Tλ任務(wù)的數(shù)量。結(jié)果表明，早期檢測策略在減少強(qiáng)制性任務(wù)的響應(yīng)時間方面是有效的。

圖4 不同模式下任務(wù)平均響應(yīng)時間及可丟棄任務(wù)數(shù)量

圖5所示為強(qiáng)制任務(wù)的平均響應(yīng)時間以及可選丟棄的Tλ任務(wù)的數(shù)量:對于TI任務(wù)，處理時間為零；對于Tλ任務(wù)，處理時間為100 ms、10 ms、1 ms和100 μs，執(zhí)行時間為20 s。同樣，圖5表明當(dāng)不精確處理生效時，強(qiáng)制任務(wù)響應(yīng)時間隨之下降?？梢钥闯?，Tλ任務(wù)的處理時間越長，平均響應(yīng)時間下降的幅度越大。

圖5 強(qiáng)制任務(wù)平均響應(yīng)時間及可丟棄任務(wù)數(shù)量

圖6所示為在20 s執(zhí)行時間內(nèi)CPU利用率與Tλ的處理時間的關(guān)系?？梢钥闯觯诓痪_模式下CPU利用率顯著下降，這是由于丟棄可選Tλ節(jié)省了部分時間。同時，隨著Tλ任務(wù)的處理時間減少，CPU利用率也隨之降低。分析其原因是系統(tǒng)的空閑時間(500 ms狀態(tài)生存期)的增加與其處理時間成正比。因此，運(yùn)行所提方案后，CPU的使用大大減少，降低了超限情況的概率。

圖6 CPU利用率對比結(jié)果

4 總結(jié)

本文研究了基于離散事件模型的實(shí)時系統(tǒng)任務(wù)模型，該模型與不精確計算相結(jié)合，對模型行為進(jìn)行優(yōu)先級排序，實(shí)現(xiàn)系統(tǒng)中高效的動態(tài)任務(wù)調(diào)度，從而減少系統(tǒng)計算開銷，提高系統(tǒng)運(yùn)行效率。

未來的研究方向包括引入優(yōu)先級模型，從而優(yōu)化可選/強(qiáng)制任務(wù)執(zhí)行順序。此外，未來可將所提方法應(yīng)用于實(shí)際，進(jìn)一步增加系統(tǒng)普適性及可移植性。