徐 珞，石 晶，樊志強(qiáng)，郝 博

（1.華北計算技術(shù)研究所，北京100083；2.中國電子設(shè)備系統(tǒng)工程公司研究所，北京100141）

0 引 言

實(shí)時系統(tǒng)中工作流的特殊性主要體現(xiàn)在時間約束上。國內(nèi)外現(xiàn)有關(guān)于工作流時間約束的研究因應(yīng)用情況的不同而有所差異，但基本上都認(rèn)為要在活動上增加時間約束［1－7］，嚴(yán)格限制活動的最短執(zhí)行時間和最長執(zhí)行時間，也有一些學(xué)者認(rèn)為應(yīng)該對遷移進(jìn)行時間約束［3，5，6］（前一活動結(jié)束到后一活動開始的時間），限制遷移的最短時間和最長時間。Hai等［6］還對活動增加了實(shí)際執(zhí)行時間的屬性，該屬性的值在活動具體執(zhí)行后才能確定，但要在最短執(zhí)行時間和最長執(zhí)行時間之間；Jin等［8］雖然也對活動增加了時間約束，但其將活動分為關(guān)鍵活動和非關(guān)鍵活動，對關(guān)鍵活動限制了執(zhí)行時間的范圍，對非關(guān)鍵活動進(jìn)行不精確的時間限制；Du Yanhua等［9］提出一種對工作流進(jìn)行模糊時間約束的方法。

按照對時間約束的嚴(yán)格程度，實(shí)時系統(tǒng)分為硬實(shí)時系統(tǒng)和軟實(shí)時系統(tǒng)，硬實(shí)時系統(tǒng)要求必須在規(guī)定時間內(nèi)完成活動，而軟實(shí)時系統(tǒng)則沒有這么嚴(yán)格［10］。對于硬實(shí)時系統(tǒng)中的工作流，除了上述文獻(xiàn)中提出的應(yīng)在活動和遷移有時間約束外，活動間傳遞的數(shù)據(jù)同樣需要進(jìn)行時間約束，用以表示數(shù)據(jù)的生命周期。因?yàn)樵谟矊?shí)時系統(tǒng)中，有些數(shù)據(jù)超過一定的時間后就會沒有意義或失效，如一些設(shè)備的狀態(tài)數(shù)據(jù)。此外，上述文獻(xiàn)還缺乏對數(shù)據(jù)與活動關(guān)系的明確描述，如不能說明對數(shù)據(jù)實(shí)例是引用還是消耗。因此，提出一種基于UML的硬實(shí)時工作建模技術(shù)以解決這些問題。

1 硬實(shí)時約束的工作流元模型

Chang E等［11］提到的大型復(fù)雜實(shí)時系統(tǒng)工作流描述需要考慮的5個因素：①可以預(yù)計環(huán)境的變化；②異常處理；③工作流的動態(tài)改變；④工作流的可組合性；⑤時間約束。結(jié)合硬實(shí)時系統(tǒng)中工作流的特點(diǎn)，給出如圖1所示的硬實(shí)時約束的工作流元模型。

圖1 硬實(shí)時約束的工作流元模型

1.1 基本元素

（1）活動：活動是工作流中最基本的元素，可以分為4種類型：①執(zhí)行活動：是不可再分的原子活動，代表一個具體的業(yè)務(wù)操作；②工作流：表示工作流的組合關(guān)系 （體現(xiàn)工作流的可組合性）；③標(biāo)志活動：標(biāo)志工作流的開始和結(jié)束，包括開始活動和結(jié)束活動；④邏輯活動：工作流管理聯(lián)盟定義了6 種基本邏輯關(guān)系，分別為串行、與分支（并發(fā)）、與連接 （同步）、或分支、或連接及循環(huán)，為了更好的表示這些邏輯關(guān)系，我們給出4種邏輯活動，分別是與分支活動、與連接活動、或分支活動及或連接活動，這些邏輯活動的組合能夠更好的表現(xiàn)工作流的動態(tài)情況 （體現(xiàn)對環(huán)境變化的預(yù)計及工作流的動態(tài)改變）。

（2）數(shù)據(jù)：數(shù)據(jù)是指工作流中的執(zhí)行活動產(chǎn)生的信息，根據(jù)不同的用途，分為應(yīng)用數(shù)據(jù)和控制數(shù)據(jù)，應(yīng)用數(shù)據(jù)在其它執(zhí)行活動執(zhí)行時使用，而控制數(shù)據(jù)在或分支活動執(zhí)行時使用。

（3）數(shù)據(jù)池：數(shù)據(jù)池是工作流中應(yīng)用數(shù)據(jù)實(shí)例存儲的地方，可以存儲多種類型的數(shù)據(jù)實(shí)例，當(dāng)數(shù)據(jù)實(shí)例到達(dá)生命周期的時間約束后將被刪除。

（4）控制流：控制流是連接活動的有向線，表示了活動的執(zhí)行順序。控制流可以攜帶多種類型的控制數(shù)據(jù)實(shí)例。異常流 （體現(xiàn)異常處理）作為一種特殊控制流，表示發(fā)生異常時活動的轉(zhuǎn)移情況，本文只考慮了超時異常。

（5）對象輸出／輸入流：對象輸出流是連接執(zhí)行活動至數(shù)據(jù)池的有向線，對象輸入流程是連接數(shù)據(jù)池至執(zhí)行活動的有向線，二者都攜帶了一種或多種類型的應(yīng)用數(shù)據(jù)實(shí)例。對象輸入流又分為對象引用流程和對象消耗流，分別表示對應(yīng)用數(shù)據(jù)的引用和消耗。

（6）應(yīng)用系統(tǒng)：應(yīng)用系統(tǒng)是指參與工作流執(zhí)行，完成執(zhí)行活動的硬實(shí)時系統(tǒng)。

（7）硬實(shí)時約束：元模型中對活動、控制流和應(yīng)用數(shù)據(jù)增加了硬實(shí)時約束 （體現(xiàn)時間約束）。時間約束的方式有6種［12］：①基本時序約束；②流延遲和時差；③有限延遲約束；④截止期限；⑤時間距離約束；⑥固定日期約束。相比而言，基本時序約束更適于表示硬實(shí)時約束，因此本文采用基本時序約束。

硬實(shí)時約束有4個屬性：最短持續(xù)時間 （Tmin）、最長持續(xù)時間 （Tmax）、實(shí)際持續(xù)時間 （Trun）及時間單位（Unit）。其中，Tmin、Tmax 和Trun 為大于零的實(shí)數(shù)，Unit為枚舉類型 （有毫秒、秒、分、時等）。Tmin、Tmax、和Unit在工作流建模時確定，Trun在工作流執(zhí)行后才能確定，但Tmin≤Trun≤Tmax。需要特別說明的是應(yīng)用數(shù)據(jù)的硬實(shí)時約束表示數(shù)據(jù)實(shí)例的生命周期，即數(shù)據(jù)實(shí)例產(chǎn)生后在多長時間范圍內(nèi)有效，用Tmax來表示，對于應(yīng)用數(shù)據(jù)，Tmin和Trun沒有意義。

1.2 約束規(guī)則

元模型有幾點(diǎn)約束規(guī)則：①工作流中至少要有一個初始活動和結(jié)束活動，當(dāng)有多個開始活動和結(jié)束活動時，工作流從所有的開始活動開始，到所有的結(jié)束活動結(jié)束為止；②工作流中所有的活動都通過控制流連接在一起，不能存在孤立的活動；③工作流中若存在循環(huán)的邏輯關(guān)系，則要通過控制流的 “條件信息”保證不存在死循環(huán)的情況；④只有或分支活動后引出的控制流才有條件信息，并且有且僅有一個控制流的條件能滿足。

2 硬實(shí)時約束的工作流建模方法

工作流的主要建模理論有流程圖、狀態(tài)圖、活動網(wǎng)絡(luò)圖、IDEF、Petri網(wǎng)［13］及UML 活動圖［14］。流程圖、狀態(tài)圖、活動網(wǎng)絡(luò)圖的優(yōu)點(diǎn)是簡單、直觀、易理解，但卻難以表達(dá)較復(fù)雜的邏輯關(guān)系，IDEF、Petri網(wǎng)和UML 活動是3種常用的過程建模方法，IDEF和UML 簡單、易懂、容易使用且可以表達(dá)復(fù)雜的邏輯關(guān)系，但不支持不確定信息的表示，Petri網(wǎng)在這方面有明顯的優(yōu)勢，但其可讀性較差，不利于理解和交流。鑒于本文的目的是提供一種簡單、直觀、易理解的工作流描述方法，且UML 活動圖與IDEF相比，UML具有良好的擴(kuò)展機(jī)制，并在實(shí)時系統(tǒng)的建模中得到認(rèn)可［12］。因此，本文選用UML 活動圖作為基礎(chǔ)。通過UML的Profile機(jī)制對UML元素進(jìn)行擴(kuò)展，定義硬實(shí)時約束的工作流建模語言 （hard real－time constrained workflow description language，HRT－WDL）。

2.1 HRT－WDL

HRT－WDL首先利用了UML的＜＜Merge＞＞關(guān)系重用了UML2.0中活動圖和類圖的部分元素，然后使用Profile機(jī)制進(jìn)行擴(kuò)展。HRT－WDL中包含Data和Workflow 兩個子包，分別定義了數(shù)據(jù)和工作流的建模元素。Data包中的元素有應(yīng)用數(shù)據(jù)、控制數(shù)據(jù)、泛化關(guān)系、聚合關(guān)系、組成關(guān)系。Workflow 包中的元素有工作流、開始活動、結(jié)束活動、與分支活動、或分支活動、與連接活動、或連接活動、執(zhí)行活動、數(shù)據(jù)池、控制流、異常流、對象輸出流、對象引用流、對象消耗流和應(yīng)用系統(tǒng)。

表1給出HRT－WDL的建模元素對應(yīng)的擴(kuò)展型、基元素及擴(kuò)展屬性。擴(kuò)展分為兩部分：工作流的擴(kuò)展和數(shù)據(jù)的擴(kuò)展。工作流的擴(kuò)展主要體現(xiàn)為硬實(shí)時約束，工作流、執(zhí)行活動、開始活動、結(jié)束活動、與分支活動、或分支活動、與連接活動、或連接活動、控制流和異常流都擴(kuò)展了硬實(shí)時約束的4個屬性。此外，控制流、對象流輸出流、對象引用流、對象消耗流還擴(kuò)展了DataType屬性，用來表示攜帶的數(shù)據(jù)實(shí)例的類型。應(yīng)用數(shù)據(jù)和控制數(shù)據(jù)的元類是Class，但約束二者沒有操作，應(yīng)用數(shù)據(jù)還擴(kuò)展了硬實(shí)時約束的Tmax和Unit兩個屬性。

表1 硬實(shí)時約束工作流的擴(kuò)展型

2.2 HRT－WDL多視圖建模

使用HRT－WDL可以從數(shù)據(jù)和工作流兩個視角進(jìn)行建模。采用UML的類圖來描述工作流中使用的數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系，稱為數(shù)據(jù)視圖；使用UML的活動圖來描述有硬實(shí)時約束的工作流，稱為工作流視圖。兩個視圖通過控制流、對象輸出／輸入流和數(shù)據(jù)池中的DataType屬性聯(lián)系起來。

此外，在多視圖建模中，工作流中使用的數(shù)據(jù)類型必須要在數(shù)據(jù)視圖中有描述。

3 應(yīng)用實(shí)例

船舶指控系統(tǒng)是一種對實(shí)時性要求較高的系統(tǒng)，很多任務(wù)有嚴(yán)格的執(zhí)行時間限制，我們選取對空作戰(zhàn)中的部分流程，使用HRT－WDL進(jìn)行描述。如圖2所示。具體執(zhí)行過程如下：對空指揮系統(tǒng)下達(dá)艦空彈目指命令 （艦空彈目指活動），輸出應(yīng)用數(shù)據(jù)TargetIndication，艦空彈系統(tǒng)根據(jù)接收到的目指數(shù)據(jù)對目標(biāo)進(jìn)行解算 （艦空彈目標(biāo)結(jié)算活動），并輸出控制信息TargetResolve，若結(jié)算成功，對空作戰(zhàn)指揮系統(tǒng)下達(dá)艦空彈允許發(fā)射命令 （艦空彈允許發(fā)射活動），艦空彈系統(tǒng)發(fā)射艦空彈打擊目標(biāo) （艦空彈發(fā)射）；若解算失敗或結(jié)算超時，則工作流結(jié)束。圖3是工作流中使用到的應(yīng)用數(shù)據(jù)和控制數(shù)據(jù)的模型，表2是工作流中部分元素擴(kuò)展屬性的值。

圖2 工作流模型

圖3 數(shù)據(jù)模型

表2 擴(kuò)展屬性的值

4 結(jié)束語

針對實(shí)時系統(tǒng)中工作流描述需要考慮的因素，提出了一種硬實(shí)時約束的工作流元模型，并重點(diǎn)分析了硬實(shí)時系統(tǒng)中工作流的時間約束。在此基礎(chǔ)上分析比較了多種建模理論，使用UML 的Profile機(jī)制對UML 的部分元素進(jìn)行擴(kuò)展定義了一種硬實(shí)時約束的工作流描述語言HRT－WDL。使用HRT－WDL可以直觀、有效的對硬實(shí)時系統(tǒng)中的工作流進(jìn)行建模，便于相關(guān)人員進(jìn)行交流，為系統(tǒng)中工作流的設(shè)計和開發(fā)提供了基礎(chǔ)。本文的研究是進(jìn)行硬實(shí)時約束工作流時間分析以及工作流管理系統(tǒng)開發(fā)的基礎(chǔ)。

［1］Lu B，Xin Z，Yu Z.A workflow model based on extended multi－dimensional workflow net and performance analysis［C］／／International Conference on Earth Science and Remote Sensing，2012，291－296.

［2］Huaiqing W，Qingtian Z.Modeling and analysis for workflow constrained by resources and nondetermined Time：An approach based on petri nets ［J］.IEEE Transactions on Systems，Man and Cybernetics，Part A：Systems and Humans，2008，38 （4）：802－817.

［3］Jianqiang L，Yushun F，Mengchu Z.Timing constraint workflow nets for workflow analysis ［J］.IEEE Transactions on Systems，Man and Cybernetics，Part A：Systems and Humans，2003，33 （2）：179－193.

［4］Lin F，Hao J.Analysis of workflow schedulability based on time constraint petri nets［C］／／10th International Conference on Computer Supported Cooperative Work in Design，2006：1－5.

［5］De Maria E，Montanari A，Zantoni M.An automaton－based approach to the verification of timed workflow schemas［C］／／Thirteenth International Symposium on Temporal Representation and Reasoning，2006：87－94

［6］Hai Z，Pung HK，Cheung TY.Timed workflow：Concept，model，and method ［C］／／Proceedings of the First International Conference on Web Information Systems Engineering，2000：183－189.

［7］Tiplea FL，Macovei GI.Timed workflow nets［C］／／Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing，2005.

［8］Jin HS，Jung HK，Myoung HK.Hard／soft deadline assignment for high workflow throughput［C］／／International Sym－posium on Database Applications in Non－Traditional Environments，1999：359－365.

［9］Du Yanhua，Yushun F.Modeling and Simulation of extended fuzzy timing workflow nets based on possibility theory ［C］／／Fourth International Conference on Fuzzy Systems and Knowledge Discovery，2007：190－195.

［10］Ping Z，F(xiàn)umin Y，Gang T.Fault－tolerant rate－monotonic compact－factor－driven scheduling in hard－real－time systems［J］.Wuhan University Journal of Natural Sciences，2010，15 （3）：217－221.

［11］Chang E，Gautama E，Dillon TS.Extended activity diagrams for adaptive workflow modelling ［C］／／Fourth IEEE International Symposium on Object－Oriented Real－Time Distributed Computing，2001：413－419.

［12］LI Huifang，F(xiàn)AN Yushun.Overview on managing time in workflow systems［J］.Journal of Software，2002，13 （8）：1552－1558 （in Chinese）.［李慧芳，范玉順.工作流系統(tǒng)時間管理 ［J］.軟件學(xué)報，2002，13 （8）：1552－1558.］

［13］Guoyin J，Lihong D.Comparative research of modeling methods for workflow process［C］／／International Symposium on Electronic Commerce and Security，2008：976－980.

［14］OMG.OMG unified modeling language （OMG UML），superstructure，V2.1.2［EB／OL］.［2008－01－10］.http：／／www.omg.org／docs／formal／07－11－02.pdf.