李妮

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

0 引言

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

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

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

1 相關(guān)概念

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

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

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

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

mi+oi=ti

(1)

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

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

假定在任意時(shí)間內(nèi)，基本模型處于s狀態(tài)。在沒(méi)有外部事件的情況下，它將在ta(s)定義的一段時(shí)間內(nèi)保持該狀態(tài)。當(dāng)發(fā)生內(nèi)部狀態(tài)轉(zhuǎn)換時(shí)，系統(tǒng)輸出值為λS，此時(shí)狀態(tài)更新為δint(S)。如果外部事件E={x1,x2,…,xn/x∈XM}在ta(s)過(guò)期之前發(fā)生，即當(dāng)系統(tǒng)處于e≤ta(s)的狀態(tài)(s,e)時(shí)，新的狀態(tài)將由δext(s,e,E)給出。假設(shè)一個(gè)外部轉(zhuǎn)移和一個(gè)內(nèi)部轉(zhuǎn)移同時(shí)到達(dá)，即當(dāng)e=ta(s)時(shí)，一個(gè)外部事件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ù)合模型指將基本模型連接在一起形成的新模型。這個(gè)模型本身可以作為一個(gè)更大的復(fù)合模型組成更加復(fù)雜的模型層次結(jié)構(gòu)。復(fù)合模型定義為

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

(3)

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

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

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

2.1 RT-DEV

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

實(shí)時(shí)系統(tǒng)的最關(guān)鍵特性是在規(guī)定的截止日期內(nèi)輸出的可用性[12]。RT-DEVS為原子組件中的每個(gè)輸出指定一個(gè)截止日期，并驗(yàn)證相關(guān)輸出生成時(shí)的截止日期。因此，將概念引入形式化模型，并在抽象的仿真機(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)的開(kāi)銷(xiāo)，那么RT-DEVS系統(tǒng)中的任務(wù)集由轉(zhuǎn)換和輸出函數(shù)組成。此信息用于將實(shí)時(shí)系統(tǒng)模擬器運(yùn)行的DEV函數(shù)(δext，δint，δcon和λ)映射到實(shí)時(shí)系統(tǒng)內(nèi)核和調(diào)度器中。RT-DEVS系統(tǒng)中的一組任務(wù)由狀態(tài)轉(zhuǎn)移和實(shí)時(shí)系統(tǒng)模擬器運(yùn)行的輸出函數(shù)(δext，δint和λ)組成。圖1顯示了在狀態(tài)轉(zhuǎn)換期間一個(gè)RT-DEVS系統(tǒng)中原子組件的處理任務(wù)示意圖。假設(shè)每個(gè)轉(zhuǎn)換函數(shù)占用1個(gè)時(shí)間單位，且各函數(shù)之間的上下文本切換忽略不計(jì)，圖中顯示了將DEV轉(zhuǎn)換函數(shù)映射到調(diào)度時(shí)間表的具體過(guò)程。

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

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

圖2 一個(gè)典型的多輸入過(guò)載場(chǎng)景

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

為了避免這種過(guò)載情況，將任務(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ù)可以在瞬時(shí)重載下終止。換句話(huà)說(shuō)，在超限情況下，系統(tǒng)跳過(guò)可選輸出以節(jié)省時(shí)間和資源。例如，在有大量偵察和控制任務(wù)的緊急任務(wù)情況下，飛機(jī)或汽車(chē)控制系統(tǒng)可以放棄信息娛樂(lè)任務(wù)以響應(yīng)緊急控制命令。類(lèi)似的情況也可以發(fā)生在任何實(shí)時(shí)系統(tǒng)中，即可以跳過(guò)一系列非關(guān)鍵輸出，通過(guò)保持所需的輸出按時(shí)產(chǎn)生來(lái)減輕過(guò)載情況。

2.2 I-DEVS

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

在RT-DEV模型基礎(chǔ)上，I-DEVS為每個(gè)狀態(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ī)級(jí)別定義強(qiáng)制性任務(wù)和可選任務(wù)時(shí)，這種抽象允許建立不精確的模型，而不涉及較低級(jí)別任務(wù)系統(tǒng)的細(xì)節(jié)。這個(gè)工件允許實(shí)現(xiàn)一個(gè)執(zhí)行模型的實(shí)時(shí)引擎，使執(zhí)行機(jī)制(在模擬模式下運(yùn)行的“模擬器”，或在實(shí)時(shí)模式下運(yùn)行的“實(shí)時(shí)引擎”)獨(dú)立于模型規(guī)范，使這些執(zhí)行工件和相關(guān)可調(diào)度性測(cè)試更容易實(shí)現(xiàn)。

3 案例與分析

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

原子組件遵循圖3(b)中的DEVS圖。模型由初始狀態(tài)、可選狀態(tài)和強(qiáng)制狀態(tài)組成。每當(dāng)有輸入時(shí)，模型就從“空閑”狀態(tài)轉(zhuǎn)換到“強(qiáng)制”狀態(tài)，在500 ms(狀態(tài)生存期)之后，它產(chǎn)生一個(gè)輸出并轉(zhuǎn)換到“可選”狀態(tài)(因?yàn)檫@是一個(gè)復(fù)合模型，輸入和輸出值也是復(fù)合的；在示例中的DEVS圖中，它接收并發(fā)送一個(gè)值1)。該模型在“強(qiáng)制”和“可選”狀態(tài)之間切換，每500 ms產(chǎn)生一次輸出，用于進(jìn)行綜合性能測(cè)試，比較不精確執(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)時(shí)間，其中執(zhí)行時(shí)間分別為20 s、50 s、70 s、120 s和180 s，處理時(shí)間為10 s(對(duì)于Tλ)，處理時(shí)間為5 s(對(duì)于TI)。可以看出，由于丟棄可選任務(wù)作為防止一次溢出的措施，非精確模式下的平均響應(yīng)時(shí)間小于精確模式。此外，圖4還顯示了丟棄的可選Tλ任務(wù)的數(shù)量。結(jié)果表明，早期檢測(cè)策略在減少?gòu)?qiáng)制性任務(wù)的響應(yīng)時(shí)間方面是有效的。

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

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

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

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

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

4 總結(jié)

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

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