信息物理系統(tǒng)可調(diào)度性分析的執(zhí)行時間優(yōu)化方法

張 晶，陳 垚，孫 俊，范洪博

(昆明理工大學(xué) 信息工程與自動化學(xué)院，昆明 650500)

1 概 述

信息物理系統(tǒng)(Cyber-Physical System，CPS)通過軟件的計算進(jìn)程控制外部環(huán)境的物理進(jìn)程，并由一系列傳感器組件與網(wǎng)絡(luò)節(jié)點完成搜集環(huán)境信息、系統(tǒng)間通信、反饋控制等任務(wù).為了獲取精確的環(huán)境信息并做出實時反應(yīng)，根據(jù)具體的不同任務(wù)，系統(tǒng)需要自動調(diào)整計算邏輯與資源配置，采用針對性的調(diào)度策略，實現(xiàn)計算世界與物理世界的高效融合[1].CPS系統(tǒng)的連續(xù)物理系統(tǒng)與離散計算系統(tǒng)相互作用、互相影響[2]，其中計算進(jìn)程由包含獨立控制線程、可異步傳遞消息與交流的執(zhí)行器(Actor)通過輸入、輸出含有特定信息的事件信號實時控制物理實體.然而物理環(huán)境的時間變量為連續(xù)信號，而計算系統(tǒng)為離散信號.計算進(jìn)程若要控制物理進(jìn)程，需要將物理連續(xù)變量由微分不變式計算得到一個收斂于離散變量中對應(yīng)的不動點收斂函數(shù)，求解該不動點即可使系統(tǒng)內(nèi)外環(huán)境在時間度量與表示上保持一致[3].

由于設(shè)計的不同需求，CPS系統(tǒng)的開發(fā)必須考慮系統(tǒng)時間信號、事件價值、執(zhí)行周期、資源消耗等約束條件，使開發(fā)過程可以得到一個詳實的性能評估與描述.對于CPS在復(fù)雜環(huán)境下的任務(wù)執(zhí)行要求，系統(tǒng)能否完成調(diào)度任務(wù)就顯得異常重要，這就要求對其可調(diào)度性進(jìn)行驗證，而CPS物理進(jìn)程與計算進(jìn)程實時交互過程中，對其任務(wù)集的可調(diào)度性進(jìn)行直接驗證非常困難，為此需要在保證系統(tǒng)正確性的前提下，能準(zhǔn)確分析可調(diào)度性的方法[4].此前，時間自動機(jī)被廣泛用于測試實時系統(tǒng)的調(diào)度性.其中Elena F等人[5]提出了一種稱為任務(wù)自動機(jī)的實時系統(tǒng)模型，其異步流程定位于自動機(jī)狀態(tài)位置，從而表達(dá)出任務(wù)到達(dá)與依賴模式.桂盛霖等人[6]實現(xiàn)了一種支持分布式系統(tǒng)任務(wù)實時調(diào)度分析工具SCT，其分析結(jié)果精確但分析時間偏長.M Stigge等人[7]基于有向圖模型提出一種pseudo-polynomial調(diào)度算法，對不同模型的工作類型、執(zhí)行條件與循環(huán)結(jié)構(gòu)的表達(dá)方式進(jìn)行優(yōu)化.然而這些方法并沒有提及計算世界與物理世界深度交互時，系統(tǒng)的調(diào)度性如何轉(zhuǎn)換為自動機(jī)的可達(dá)性進(jìn)行判定.

本文考慮在上述技術(shù)研究的基礎(chǔ)上，定義多元的CPS系統(tǒng)任務(wù)調(diào)度約束，以超致密時間模型(Superdense Time Model，SDT)計算離散變量不動點并表達(dá)系統(tǒng)全局時間信號.提出一種基于有限狀態(tài)機(jī)(Finite State Machine，F(xiàn)SM)的執(zhí)行器狀態(tài)自動機(jī)(Actor State Automata，ASA)分析方法對CPS調(diào)度性進(jìn)行分析，并基于此方法，提出一種基于決策樹的ASA狀態(tài)集分類搜尋策略(A classified search strategy of state set for ASA based on decision tree，DT-ASA*).最后通過PtolemyII平臺[8，9]建立模型，分析系統(tǒng)模型的精確性與性能.

2 系統(tǒng)模型

CPS系統(tǒng)由物理設(shè)備與計算系統(tǒng)組合而成，通過傳感器、制動器與網(wǎng)絡(luò)節(jié)點相互作用.如圖1所示，計算系統(tǒng)在PtolemyII平臺仿真時被定義為一種基于面向執(zhí)行器(Actor-oriented)的并發(fā)性模型與通信交流策略構(gòu)成的并發(fā)計算模型(Model of Computation，MoC)[10]，利用事件驅(qū)動結(jié)構(gòu)，通過異步回調(diào)操作(asynchronous callbacks) 函數(shù)可將所有事件信號按事件時間戳順序處理.

圖1 基于面向執(zhí)行器模型的基本等級架構(gòu)Fig.1 Basic level architecture based on actor-oriented model

2.1 CPS系統(tǒng)執(zhí)行約束條件

·SA是執(zhí)行器A狀態(tài)集合，且SA≠?；

基于面向執(zhí)行器的并發(fā)計算模型，是一種具有層次感的程序組件組成的系統(tǒng)模型，不同層次的模型或同一層次的組件通過執(zhí)行器進(jìn)行通信，其方式即通過輸入、輸出端口接收或送出執(zhí)行事件.

定義2.(事件)事件信號標(biāo)簽為一個五元組E=，其中：

·C代表事件所處信道集合，其單值子集c代表某個輸入行為或輸出行為，并且{e1，e2|e1∈Ein∨e2∈Eout}，則f(sinit，e1，cin)=u(sinit，e1)×e2，其中e2∈cout；

·Φe是事件e∈E的約束條件集合；

·T是執(zhí)行器處理事件的系統(tǒng)全局時間；

·SE是事件E的狀態(tài)集合，se∈SE是事件e的時間戳確定的事件狀態(tài).

由于不同的設(shè)計需求，CPS的事件考慮多種約束條件，如Φe=δe×Re×Ve.

δe為事件時間戳所確定的時序約束，時序約束內(nèi)部元素是時鐘集合X?T到非負(fù)實數(shù)+的映射，并且是系統(tǒng)預(yù)計執(zhí)行器處理事件e的時間，即：；t是系統(tǒng)當(dāng)前運(yùn)行時間，y為影響參數(shù)[11].

Re為執(zhí)行事件e所消耗的資源，該約束由事件等待時產(chǎn)生的能耗，執(zhí)行任務(wù)的消耗，及是否正常執(zhí)行等因素決定.令de為事件e截至?xí)r間，re為事件就緒準(zhǔn)備被執(zhí)行的時間，εe為完成處理fA任務(wù)的時間，對于當(dāng)前時間t∈T，事件e處于等待時間或執(zhí)行時間有如下狀態(tài)：

(a)runninge=(re

(b)readye=((t=re∧t

(c)suspende=(t≤re∨(t

(d)sleepe=(t

Ve為事件價值量約束，由事件e產(chǎn)生的數(shù)據(jù)質(zhì)量Qe與對應(yīng)的執(zhí)行器A的信息冗余度χA決定，H(A)為執(zhí)行器A輸出事件時的信息熵[12]，滿足：

2.2 全局時間信號的表達(dá)

CPS中計算進(jìn)程為離散的，物理進(jìn)程為連續(xù)的，若T為任意小常數(shù)的倍數(shù)，則無法表達(dá)其語義，故不能以時鐘計數(shù)表達(dá)執(zhí)行器輸出事件的時間戳排序.考慮集合×代替+作為時鐘集合X?T的映射，表示執(zhí)行器處理事件的系統(tǒng)全局時間T，此時時間值為數(shù)組(?，n)∈T，其中?為時間長度，n為離散時間瞬間的某一序列值[13].

定義3.超致密時間(SDT)表示為(?，n)∈(T=×)，?∈表示離散步長，n∈表示離散步數(shù).若(?，n)≥ (?′，n′)，則有?≥?′∨(?=?′∧n≥n′).對于SDT有如下性質(zhì)[14]：

·對于(?，n)在集合T上有如下的下降集：

·T的下降集由T本身表示；

定理1.在超致密時間中，若Y為實時規(guī)則集合，Y′為非實時規(guī)則集合，對于?e∈E，當(dāng)且僅當(dāng)?t∈(?，n)，有(e，t)∈Y，則e∈Y′.

證明：1)根據(jù)定義3，(?，n)∈T，則T的下降集為Ζ[?，n]或Ζ(?，n)，其中，若?∈，則T的下降集為Ζ(?，∞).故若?t∈(?，n)，使得(e，t)∈Y，說明e的執(zhí)行序列為排序的.

2)若t為任意實數(shù)值的時間序列，則?(e，t)∈Y，若?q∈，使X內(nèi)部元素x為q的整數(shù)倍，則?n∈，0≤i′≤i，使xi=xi′+nq.由t∈(?，n)，得ti=ni?.由于存在延遲，故總有q′≤q，使?i-?i′=nq′≤nq，由證明1)可知(ti-ti′)與?i-?i′滿足相同約束Φe，故構(gòu)造(e，(?，n))作用于執(zhí)行器，其事件輸出路徑滿足與輸出Cr=f×u相同的運(yùn)行路徑.故當(dāng)(e，t)∈Y，有e∈Y′.

得證.

2.3 帶約束條件的執(zhí)行器行為

對于集合H(A，E)，有如下屬性：

·e∈E為執(zhí)行器A在time(?，n)控制下的輸出事件：

(a)?e=ep為周期事件(periodic events)，其輸出事件時間間隔p1為固定常數(shù)；

(b)?e=ea為非周期事件(aperiodic events)，其輸出事件時間間隔p2是以需求確定的最小下界;

·若?se∈SA，E=sleepe∨suspende，則執(zhí)行器A的執(zhí)行周期p→∞；

·執(zhí)行器A中任意事件e順序執(zhí)行的必要條件為?t=(e，(?，n))≥p(me，(?，n))|m=1，2，，…，n-1}，即每個事件由狀態(tài)readye→runninge需要前n-1個事件執(zhí)行完成才能開始；

·執(zhí)行器A中任意事件e必須滿足Φe=δe×Re×Ve.

圖2 執(zhí)行器內(nèi)部狀態(tài)轉(zhuǎn)移任務(wù)示例圖Fig.2 Sample figure of state transition tasks in an actor

3 執(zhí)行器狀態(tài)自動機(jī)

3.1 有限狀態(tài)機(jī)語義

系統(tǒng)狀態(tài)被定義為在某個特定的時刻，系統(tǒng)對應(yīng)的條件狀況.狀態(tài)變量表示為s∈Σ，Σ為系統(tǒng)所有可能狀態(tài)的集合，有限狀態(tài)機(jī)(FSM)是一種Σ為有限集合的狀態(tài)機(jī)，在FSM中，系統(tǒng)行為被表達(dá)為狀態(tài)集合，并在其中通過某種規(guī)則管理各個狀態(tài)間的轉(zhuǎn)移.

定義4.(有限狀態(tài)機(jī))有限狀態(tài)機(jī)為六元組<Σ，CI，CO，s0，Δ，F(xiàn)>，其中：

·Σ為狀態(tài)機(jī)內(nèi)所有可能狀態(tài)的集合；

·CI為函數(shù)：CI=Cin→Ein∪{absent}，{absent}表示信道Cin可用；

·CO為函數(shù)：CO=Cout→Eout∪{absent}；

·s0為初始狀態(tài)，s0∈Σ；

·Δ為變量值；

·F為函數(shù)：F=Σ×CI×Δ→Σ×CO×Δ.

對于一個確定的有限狀態(tài)機(jī)，若任意狀態(tài)，最多有一個輸入值可以激活一個轉(zhuǎn)移，則稱其具有確定性；若任意狀態(tài)，每個輸入值都至少能激活一個轉(zhuǎn)移，則稱其為可接受的.狀態(tài)間的轉(zhuǎn)移為有限狀態(tài)空間離散動態(tài)與輸入到輸出的映射.

FSM可并列異步組合，對于a、b狀態(tài)機(jī)組合成的c狀態(tài)機(jī)，其執(zhí)行過程中有如下語義：

1)c的響應(yīng)為a或b其中的一個的響應(yīng)，并且選擇是不確定的；

2)c的響應(yīng)可能為a或b其中的一個的響應(yīng)，也可能為a、b的共同響應(yīng)，并且選擇是不確定的，執(zhí)行結(jié)果可能導(dǎo)致沒有響應(yīng)；

3)c的響應(yīng)如何決定，由外部環(huán)境選擇.

如圖3為一組并列異步組合FSM，通過不同約束條件(guard)選擇轉(zhuǎn)移狀態(tài).其中，狀態(tài)b可分層為狀態(tài)c與狀態(tài)d，當(dāng)處于狀態(tài)b時表示處于狀態(tài)c或狀態(tài)d.框圖3-Ⅱ為框圖3-Ⅰ的等效表示.

圖3 并列異步組合FSM示例圖Fig.3 Sample figure of side-by-side composition FSM

3.2 執(zhí)行器狀態(tài)自動機(jī)語義

本節(jié)定義一種帶約束條件有限狀態(tài)機(jī)的特定子類，命名為執(zhí)行器狀態(tài)自動機(jī)，與以往技術(shù)原理相同，本文采用基于自動機(jī)理論，將系統(tǒng)可調(diào)度性問題轉(zhuǎn)換為可達(dá)性問題進(jìn)行分析.帶約束條件有限狀態(tài)機(jī)為<Σ，E，L，L0，X，Φ，Δ，f>，與上述符合含義相同的，Σ為狀態(tài)機(jī)內(nèi)所有可能狀態(tài)的集合，E是有限事件集合，L為位置的有限集合L0為初始位置集合，并有L0?L，X?T為時鐘集合，Φ為E的約束條件集合，Δ為變量值，f為狀態(tài)轉(zhuǎn)移函數(shù).

定義5.(執(zhí)行器狀態(tài)自動機(jī))執(zhí)行器狀態(tài)自動機(jī)為十二元組<Σ，E，L，L0，ρ，σ，X，δ，R，V，Δ，f>，其中：

·Σ為狀態(tài)機(jī)內(nèi)所有可能狀態(tài)的集合，存在Σre表示可執(zhí)行狀態(tài)集，Σerr表示不可執(zhí)行狀態(tài)集，并且Σre，Σerr∈Σ；

·E為有限事件集合，存在E=En∪Ew，En為內(nèi)部事件集合，Ew為外部事件集合，其行為與定義3第1子句(c)相符；

·L為位置的有限集合，存在L=Lbasic∪Lcom，其中Lbasic為基礎(chǔ)位置集合，Lcom為異步組合位置集合；

·L0?Lbasic為初始位置集合；

·l0，l1∈Lcom，e∈E，s∈Σ，l1=l0(s×e)→ρ(l0)，?l∈Lcom，ρ(l)表示l的子位置，而ρ-1(l)表示l的父位置；

·σ={&&，‖，?}表示每個位置間的關(guān)系，若父子位置為&&關(guān)系，則?l1=ρ(l0)=Sact，其中Sact表示活躍狀態(tài)，若父子位置為‖關(guān)系，則只存在一個l1=ρ(l0)=Sact，&&關(guān)系與‖關(guān)系組合成的位置集合為Lcom，對于L0?Lbasic=?說明其沒有父子關(guān)系的位置；

·時鐘集合X?time(?，n)為時鐘集合，滿足超致密時間表達(dá)：(?，n)∈(T=×)；

·δ×R×V為約束條件，其定義與2.1節(jié)對δe、Re及Ve的描述相符；

·Δ為變量值，每個變量的值域都為有限的；

·f=Σ×E×L×2X×Φ(δ)×Φ(R)×Φ(V)×Δ表示狀態(tài)轉(zhuǎn)移關(guān)系.

3.3 執(zhí)行器狀態(tài)自動機(jī)判定性證明

由定義5第6子句可知，若位置l=Sact且σ(l)=||，則?!l′∈ρ(l)使得l′=Sact；若位置l=Sact且σ(l)=&&，則?!l′∈ρ(l)使得l′=Sact.

定理2.帶約束條件有限狀態(tài)機(jī)是可判定的，則執(zhí)行器狀態(tài)自動機(jī)一定也是可判定的.

證明：設(shè)K=<Σ，E，L，L0，X，Φ，Δ，f>為帶約束條件有限狀態(tài)機(jī)，按如下條件可編碼為對應(yīng)的特定子類K′=<Σ′，E′，L′，L0′，ρ，σ，X′，δ，R，V，Δ′，f′>：

1)K中活躍狀態(tài)位置集合{L|Sact}中任意位置l∈L都對應(yīng)K′中某一位置l′∈L′.若l的初始位置為L0?Lbasic?K，則l′的初始位置為L0′?Lbasic′?K′，其中E′=E；

2)K中的時鐘集X對應(yīng)K′中的時鐘集X′，且滿足X=X′，f′(δ)=f；

3)若{L|Satc，?l∈L}對應(yīng)K′中的位置l′∈L′，則狀態(tài)轉(zhuǎn)移關(guān)系為f′(l′)=∧{L|Satc，l∈L}f(l)；

4)若在K中有從li到lj的狀態(tài)轉(zhuǎn)移f(si×cin×ei)，與一組從Lm到Ln的狀態(tài)轉(zhuǎn)移行為集合H(A，E)?F，且狀態(tài)為li∈{Li|Sact}，Lm∈{Li|Sact}，lj∈{Lj|Sact}，ln∈{Lj|Sact}，其中{Li|Sact}，{Lj|Sact}?{L|Sact}，li，lj∈Lbasic，Lm，Ln?L.那么在K′中同時對應(yīng)狀態(tài)轉(zhuǎn)移f′(si′×cin′×ei′)={L|Satc}，u(si′×cin′×ei′)={Lj|Satc}，u∈F，且f′(δ×R×V)=∧E?H(A，E)f(Φ).

通過編碼后，K中?s∈∑=({L|Sact}，X)對應(yīng)K′中某一狀態(tài)s′∈∑′=(l′，X′)，并且l′={L|Sact}.若K中?si∈∑=({Li|Sact}，Xi)可由s到達(dá)，則si在K′中對應(yīng)的si′也可由s′到達(dá).由定義6與定義7可知，執(zhí)行器狀態(tài)自動機(jī)的可達(dá)性是可判定的.

得證.

3.4 DT-ASA*策略

對于ASA的模型檢測，需要計算ASA的可到達(dá)狀態(tài)集合，檢測ASA是否滿足超致密時間邏輯描述的系統(tǒng)規(guī)格，并使用調(diào)度策略進(jìn)行驗證.考慮一種基于決策樹的ASA狀態(tài)集分類搜尋策略(A classified search strategy of state set for ASA based on decision tree，DT-ASA*)，并且在PtolemyII平臺上基于此策略建模，用于分析ASA方法的精確度、執(zhí)行時間及內(nèi)存使用率.

DT-ASA*策略實質(zhì)是個遞歸的過程，若在下列情況發(fā)生時產(chǎn)生遞歸返回：

1)屬性集中的樣本全屬于同一類別，即全可達(dá)或不可達(dá)，則無需分類；

2)屬性集為空，或樣本屬性取值完全相同，則無法分類：此情況下將此結(jié)點作為葉結(jié)點，其類別為樣本中最多的類別；

3)結(jié)點內(nèi)樣本集為空，無法分類：此情況下將其父結(jié)點作為葉結(jié)點，其類別為樣本中最多的類別.

作為每個結(jié)點劃分的關(guān)鍵，參考著名的C4.5決策樹算法，使用增益率(gain ratio)選擇最優(yōu)劃分屬性，由狀態(tài)集s=中計算出信息增益高于平均水平的條件，再從中計算出增益率最高的作為此結(jié)點劃分的最佳考量變量.最后檢測所有可達(dá)或不可達(dá)類別的葉結(jié)點，考慮將不可達(dá)結(jié)點剪枝或歸納所有可達(dá)結(jié)點，所述策略的偽代碼如算法1所示.

算法1.DT-ASA*策略

輸入： 訓(xùn)練集K={s0,s1,…,sm}

屬性集Γ={reachable,error}

1.初始化： s0={e0,I0,x0,δ0,R0,V0}

2. Re:={s0},Error=[]

3.DT-ASA*(K,Γ):

4. 生成結(jié)點node

5.while∑≠?

6.ifK中的樣本屬于同一類別reachableORerror

7. 將nodfe標(biāo)記為reachableORerror

8.return

9.endifΓ=?

10.if或K中的樣本在Γ取值相同，then

11. 將node標(biāo)記為葉結(jié)點，其類別標(biāo)記為K中樣本最多類

12.return

13.endif

17. 選擇gain_ratio(K,s)較大的屬性作為最優(yōu)劃分屬性Γ*

18.forΓ*的每個取值a*

19.為node生成一個分支

20.令Ka表示K在Γ*上取值為a*的樣本子集

21.ifKa為空，then

22.將分支節(jié)點標(biāo)記為葉結(jié)點，其類別標(biāo)記為K中樣本最多的類

23.return

24.else

25.以DT-ASA*(K,Γ、{Γ*})為分支結(jié)點

26.end

27.if存在s′屬于reachableands′不屬于Re

28. Re:=Re∪{s′}

29.else

30. Error.extend(s′)

31.end

DT-ASA*策略的輸入為系統(tǒng)狀態(tài)及屬性集合，輸出為系統(tǒng)狀態(tài)分類后的狀態(tài)屬性分類集合.

測試DT-ASA*策略：本測試使用處理器為1.6GHz雙核Intel Core i5，RAM為8.00GB的MacBook Air PC機(jī)，其系統(tǒng)為macOS Sierra，以系統(tǒng)自帶的Python 2.7編程運(yùn)行，使用加州大學(xué)伯克利分校[15]的數(shù)據(jù)集作為訓(xùn)練集.

由于數(shù)據(jù)需要作為4.2節(jié)所建立模型的變量輸入，故測試的決策樹結(jié)果為字典模式保存，其中可達(dá)狀態(tài)集存入字典Re，不可達(dá)狀態(tài)集存入列表Error：

>>> DT-ASA*Tree

{′states′：{‘disabled’：′error′，′act′：{′timing sequence′：{‘overrun’：′error′，′x：=0′：{′quantity of value′：{′satisfy′：{′clock constraint′：{′satisfy′：{′energy consumption′：{′equality′：{′events′：{′ready′：′reachable′，′running′：′reachable′，′suspend′：′reachable′，′sleep′：′error′}}，′low′：{′events′：{′ready′：′reachable′，′running′：′reachable′，′suspend′：′reachable′，′sleep′：′error′}}，′higher′：′error′}}，′dissatisfy′：′error′，′equality′：{′energy consumption′：{′equality′：{′events′：{′ready′：′reachable′，′running′：′reachable′，′suspend′：′reachable′，′sleep′：′error′}}，′low′：′events′：{′ready′：′reachable′，′running′：′reachable′，′suspend′：′reachable′，′sleep′：′error′}}，′higher′：′error′}}}}，′dissatisfy′：′error′}}}}}}

其中′reachable′表示可達(dá)狀態(tài)，′error′表示不可達(dá)狀態(tài)，事件約束條件有runninge、readye、suspende以及sleepe，時序約束若不是‘overrun’則在狀態(tài)轉(zhuǎn)移時重置時鐘′x：=0′，約束條件集合Φe為′clock constraint′，′energy consumption′和′quantity of value′.測試結(jié)果符合數(shù)據(jù)集運(yùn)行結(jié)果.

4 性能驗證

4.1 建立DT-ASA*策略模型

UC Berkeley的PtolemyII平臺由Edward Ashford Lee教授團(tuán)隊研發(fā)，用于驗證包含時間和行為類型屬性的組件交互過程，并支持分層設(shè)計實時嵌入式異構(gòu)系統(tǒng)[8].本節(jié)建立的DT-ASA*策略模型，使用4.1節(jié)所述MacBook Air PC開發(fā)環(huán)境，平臺版本使用PtolemyⅡ10.0.1Mac OS X版.

建立的模型如圖4所示，Director為系統(tǒng)調(diào)度器，使用2.2節(jié)所述的SDT時間控制系統(tǒng)全局時間.Director調(diào)度器右側(cè)為Δ變量值，引號左邊為變量名，引號右邊為變量初始值.State Model為狀態(tài)產(chǎn)生模塊，內(nèi)部隨機(jī)產(chǎn)生初始狀態(tài)s0，由不同的調(diào)度策略產(chǎn)生狀態(tài)序列并輸入Modal Model模塊分析檢測，生成result實時反饋回State Model，使其更新更優(yōu)的狀態(tài)序列.Modal Model內(nèi)部結(jié)構(gòu)為執(zhí)行器狀態(tài)自動機(jī)模型，其左端輸入不可達(dá)狀態(tài)集列表Error.模型輸出結(jié)果表現(xiàn)在曲線生成器reachableState與Rate中.

圖4 DT-ASA*策略模型Fig.4 Model of DT-ASA* strategy

Modal Model中黑色箭頭s與Error表示輸入?yún)?shù)，result表示輸出參數(shù).虛線狀態(tài)轉(zhuǎn)移邊為默認(rèn)轉(zhuǎn)移(default transition)，其優(yōu)先級僅低于普通轉(zhuǎn)移.加粗的邊表示經(jīng)歷轉(zhuǎn)移(history transition)，為復(fù)位轉(zhuǎn)移的一種形式，目標(biāo)狀態(tài)會停留于它最后所處的狀態(tài)或最初狀態(tài).RelationParameter為轉(zhuǎn)移關(guān)系，圖中以u表示，具體如下：

u1：(output：s = reachableRate)；

u2：(guard：error，output：s = 0，set：count = 0)；

u3：(guard：count < 10 && s0<= ScheOn，output：s = reachableRate，set：count = count + 1)；

u4：(guard：count < 10&& s0> ScheOn，output：s = errorRate，set：count = count + 1);

u5：(guard：!error &&s0>= ScheOff，output：s =errorRate);

u6：(output：s = 0);

u7：(guard：count < 10，output：s = errorRate，set：count + 1);

u8：(guard：error，output：s = 0，set：count = 0);

u9：(guard：!error &&s0<= ScheOff，output：s = reachableRate);

u10：(output：s = 0);

u11：(guard：count < 10，output：s = reachableRate，set：count + 1);

u12：(output：s = errorRate);

u13：(output：s = errorRate);

4.2 仿真結(jié)果

測試所涉及的調(diào)度策略包括單調(diào)速率(RM)調(diào)度策略、最早交貨期(EDD)調(diào)度算法、優(yōu)先級最早時限優(yōu)先(EDF*)算法、Hu級調(diào)度(Hu level scheduling)算法.其中RM策略為一種簡單的搶占式調(diào)度策略，為周期較小的任務(wù)分配較高的優(yōu)先級；EDD算法也稱為Jackson算法，它只根據(jù)時限順序執(zhí)行，與任務(wù)間相對順序無關(guān)，時限最早的優(yōu)先級最高；EDF*算法為簡單的EDF改進(jìn)方法，是一種支持任務(wù)到達(dá)并且將最大延遲最小化的簡單優(yōu)先級最優(yōu)算法；Hu級調(diào)度算法為多處理器調(diào)度最簡單的方法，作為關(guān)鍵路徑(critical path)算法的一種，根據(jù)最長完成時間制定優(yōu)先級圖的路徑.

模型中不同調(diào)度策略的狀態(tài)轉(zhuǎn)移都處于執(zhí)行狀態(tài)或就緒狀態(tài)間相互轉(zhuǎn)換.首先不使用Modal Model產(chǎn)生的result進(jìn)行反饋，而由不同的調(diào)度策略直接將狀態(tài)序列輸入reachableState得到實際值，然后使用4.2節(jié)描述的系統(tǒng)模型，將結(jié)果輸入reachableState與Rate得到預(yù)測值，通過對比得到DT-ASA*策略模型的精確性.分析結(jié)果如圖5(a)-圖5(d)所示.對比獲得實際狀態(tài)序列與預(yù)測狀態(tài)序列的執(zhí)行時間以及內(nèi)存使用率，結(jié)果如表1所示.

圖5 DT-ASA*策略模型的精確性分析Fig.5 Analysis of accurateness for DT-ASA* strategy Model

由圖5所示，使用調(diào)度策略實際產(chǎn)生30次狀態(tài)轉(zhuǎn)移，在圖5(a)與圖5(b)中，DT-ASA*策略模型能很好地預(yù)測出最終狀態(tài)轉(zhuǎn)移次數(shù)，其中可達(dá)不可達(dá)圖為DT-ASA*策略得出的二分類結(jié)論，即在迭代過程中，若當(dāng)前位置為可達(dá)狀態(tài)輸出1.0，若為不可達(dá)狀態(tài)則輸出0.0.狀態(tài)序列圖與可達(dá)不可達(dá)圖互相對應(yīng)，明顯看出，位置狀態(tài)為1.0時，狀態(tài)轉(zhuǎn)移過程中增加狀態(tài)序列，位置狀態(tài)為0.0時，狀態(tài)轉(zhuǎn)移停滯，直到搜索到下一可達(dá)狀態(tài).圖5(c)、圖5(d)與圖5(a)、圖5(b)相似，預(yù)測值與實際值基本一致，但可以看出在狀態(tài)序列穩(wěn)定后，圖5(c)、圖5(d)的預(yù)測值要比實際值略高，即仍然存在過度匹配的現(xiàn)象.

表1 DT-ASA*策略模型的性能分析Table 1 Analysis of performance for DT-ASA* strategy Model

分析不同測試算法在系統(tǒng)模型中的性能，將算法在模型中得到實際值的執(zhí)行與得到預(yù)測值的執(zhí)行分別運(yùn)行20次，得到平均執(zhí)行時間與平均內(nèi)存使用率.由表1所示，可以看出4種不同的調(diào)度策略在模型中的執(zhí)行情況，其中迭代次數(shù)為圖5中橫坐標(biāo)的迭代次數(shù).當(dāng)使用DT-ASA*策略模型時，對于RM調(diào)度策略，執(zhí)行時間提高33.33%，同時多消耗45.16%內(nèi)存資源；對于EDD調(diào)度算法，執(zhí)行時間提高45.32%，同時多消耗23.53%內(nèi)存資源；對于優(yōu)先級EDF算法，執(zhí)行時間提高37.01%，同時多消耗45.95%內(nèi)存資源；對于Hu級調(diào)度算法，執(zhí)行時間提高33.80，同時多消耗32.56%內(nèi)存資源.

表2 關(guān)鍵符號列表Table 2 Key compliance list

由仿真結(jié)果可以得出結(jié)論，DT-ASA*策略模型所得到的預(yù)測值與實際值基本一致，但仍然存在過度匹配的現(xiàn)象，需要進(jìn)一步改進(jìn)，雖然使用模型預(yù)測任務(wù)狀態(tài)能極大減少執(zhí)行時間，但同時也會消耗更多內(nèi)存資源.

5 總 結(jié)

本文針對CPS系統(tǒng)可調(diào)度性分析問題.首先定義了CPS系統(tǒng)執(zhí)行約束條件，然后以SDT表達(dá)系統(tǒng)全局時間，在定義了帶約束條件的執(zhí)行器行為后，提出了一種基于有限狀態(tài)機(jī)的執(zhí)行器狀態(tài)自動機(jī)分析方法，并對執(zhí)行器狀態(tài)自動機(jī)判定性問題進(jìn)行證明.最后提出一種基于決策樹的執(zhí)行器狀態(tài)自動機(jī)狀態(tài)集分類搜尋策略，通過可包含時間和行為類型屬性組件交互過程進(jìn)行驗證的PtolemyII平臺建立策略模型.通過仿真得出結(jié)論，該策略得到的預(yù)測值基本符合實際值，并且明顯降低執(zhí)行時間，但策略仍然存在不足，例如會消耗更多內(nèi)存資源以及存在過度匹配的現(xiàn)象，需要在今后的工作中加以改進(jìn).