一種不精確離散事件系統建模與仿真

李妮

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

0 引言

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

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

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

1 相關概念

1.1 實時系統及不精確計算

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

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

每個任務Ti由2個子任務組成：強制和可選,則有

mi+oi=ti

(1)

其中，mi為強制子任務Mi需要處理時間，ti為oi可選子任務Oi的需要處理時間。

在可調度RT系統中，當相關作業中包括的每個任務Ti的至少所有強制子任務被執行時(作業是在執行期間發生的任務的實例)，則每個任務Ti處于正在執行階段。任務Ti的可選子任務只有在Ti的強制子任務正確執行時才可執行。調度器可以在可選子任務執行期間的任何時間終止該子任務。基于這個定義，完美硬RT系統是所有任務都由強制子任務組成的系統，完美軟RT系統是所有子任務都是可選的系統。RT系統中的一個常見問題是，當系統沒有足夠的處理資源來完成所有請求進程時，會出現溢出情況。這個問題將給被控機器帶來嚴重威脅，并可能導致災難性的后果。

1.2 離散事件系統模型

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

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

(2)

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

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

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

(3)

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

2 不精確離散事件系統

本文在RT任務調度中引入不精確離散事件模型，結合離散事件的動態優勢和形式化建模方法的嚴密性，同時利用不精確計算用來處理由于系統中發生過載溢出情況產生的錯誤問題。

2.1 RT-DEV

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

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

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

(4)

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

圖1 原子組件的處理任務示意圖

如圖1所示，外部轉換(δext)映射到TX任務中，該任務啟動狀態S。此時任務的釋放時間等于輸入到達系統的時間。需注意，由于TX是一個可以隨時到達的輸入，因此不設截止日期。考慮到DEVS中的輸出總是緊跟著內部轉換，故輸出任務Tλ和內部轉換δint任務TI將同時執行，形成了TλTI任務。任務TλTI的釋放時間等于狀態S的結束時間，且由ta(s)指定(即圖2中的T)。

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

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

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

2.2 I-DEVS

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

在RT-DEV模型基礎上，I-DEVS為每個狀態添加強制或可選條件，具體描述為

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

(5)

原子模型的狀態分為強制狀態和可選狀態。強制狀態將具有強制輸出函數(表示為輸出任務)，而可選狀態將生成可選輸出任務。在狀態機級別定義強制性任務和可選任務時，這種抽象允許建立不精確的模型，而不涉及較低級別任務系統的細節。這個工件允許實現一個執行模型的實時引擎，使執行機制(在模擬模式下運行的“模擬器”，或在實時模式下運行的“實時引擎”)獨立于模型規范，使這些執行工件和相關可調度性測試更容易實現。

3 案例與分析

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

原子組件遵循圖3(b)中的DEVS圖。模型由初始狀態、可選狀態和強制狀態組成。每當有輸入時，模型就從“空閑”狀態轉換到“強制”狀態，在500 ms(狀態生存期)之后，它產生一個輸出并轉換到“可選”狀態(因為這是一個復合模型，輸入和輸出值也是復合的；在示例中的DEVS圖中，它接收并發送一個值1)。該模型在“強制”和“可選”狀態之間切換，每500 ms產生一次輸出，用于進行綜合性能測試，比較不精確執行和精確執行的結果。在精確執行的情況下，系統默認所有的值都是強制性的。此外，假定輸入在執行1 s后注入到模型中，以便觸發狀態變換和輸出信息。

圖3 復合模型基本結構

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

圖4 不同模式下任務平均響應時間及可丟棄任務數量

圖5所示為強制任務的平均響應時間以及可選丟棄的Tλ任務的數量:對于TI任務，處理時間為零；對于Tλ任務，處理時間為100 ms、10 ms、1 ms和100 μs，執行時間為20 s。同樣，圖5表明當不精確處理生效時，強制任務響應時間隨之下降。可以看出，Tλ任務的處理時間越長，平均響應時間下降的幅度越大。

圖5 強制任務平均響應時間及可丟棄任務數量

圖6所示為在20 s執行時間內CPU利用率與Tλ的處理時間的關系。可以看出，在不精確模式下CPU利用率顯著下降，這是由于丟棄可選Tλ節省了部分時間。同時，隨著Tλ任務的處理時間減少，CPU利用率也隨之降低。分析其原因是系統的空閑時間(500 ms狀態生存期)的增加與其處理時間成正比。因此，運行所提方案后，CPU的使用大大減少，降低了超限情況的概率。

圖6 CPU利用率對比結果

4 總結

本文研究了基于離散事件模型的實時系統任務模型，該模型與不精確計算相結合，對模型行為進行優先級排序，實現系統中高效的動態任務調度，從而減少系統計算開銷，提高系統運行效率。

未來的研究方向包括引入優先級模型，從而優化可選/強制任務執行順序。此外，未來可將所提方法應用于實際，進一步增加系統普適性及可移植性。