陳金東 王曉虎 吳星同 陳中育

（浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江 金華 321004）

基于FSM的工作流建模方法及其應(yīng)用

陳金東 王曉虎 吳星同 陳中育

（浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江 金華 321004）

傳統(tǒng)工作流建模工具大多是按照流程序列化思想進(jìn)行使用，關(guān)注的是業(yè)務(wù)的執(zhí)行順序和路徑，難以對跳轉(zhuǎn)、回退、循環(huán)等復(fù)雜的業(yè)務(wù)過程進(jìn)行建模。本文提出一種基于有限狀態(tài)機(jī)的工作流進(jìn)行建模的方法，該方法將業(yè)務(wù)過程看成是有限狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)移過程，給出工作流建模的幾個步驟，最后通過一個實(shí)例對該建模方法進(jìn)行分析說明。

有限狀態(tài)機(jī)；工作流技術(shù)；證書流轉(zhuǎn)；工作流模型

1．引言

隨著信息技術(shù)和網(wǎng)絡(luò)技術(shù)的快速發(fā)展，工作流技術(shù)在各個領(lǐng)域得到了廣泛應(yīng)用，它實(shí)現(xiàn)工作過程管理的自動化、智能化和整合化，很大程度提高業(yè)務(wù)人員的工作效率[1]。而工作流建模是工作流技術(shù)的關(guān)鍵，設(shè)計一個理想的工作流模型可以使得工作流系統(tǒng)有效地運(yùn)行[2]。傳統(tǒng)的工作流建模方法有多種，如：有向圖、面向?qū)ο?、?shí)體關(guān)聯(lián)建模、事務(wù)建模、Petri網(wǎng)等方法。這些傳統(tǒng)的建模思想存在著許多不足，文獻(xiàn)[3]中指出傳統(tǒng)的建模思想是基于流程序列化思想進(jìn)行的，按照業(yè)務(wù)執(zhí)行的順序?qū)I(yè)務(wù)過程按時序關(guān)系進(jìn)行排列，確定業(yè)務(wù)過程執(zhí)行的步驟，這種建模方式關(guān)注的是業(yè)務(wù)的執(zhí)行順序和路徑。然而在現(xiàn)實(shí)生活中，業(yè)務(wù)過程具有復(fù)雜和多變等特點(diǎn)，表現(xiàn)為眾多狀態(tài)之間的跳轉(zhuǎn)、回退、循環(huán)和聚合等。為了彌補(bǔ)傳統(tǒng)建模方法存在的這些不足，本文提出采用有限狀態(tài)機(jī)(Finite State Machine，F(xiàn)SM)的思想對工作流進(jìn)行建模的方法和步驟。

2．有限狀態(tài)機(jī)建模的優(yōu)勢

早期針對簡單的工作流，一般采用基于有向圖技術(shù)進(jìn)行建模，用圖形中的節(jié)點(diǎn)描述工作流過程中的活動或者狀態(tài)，而用有向弧表示節(jié)點(diǎn)的順序依賴關(guān)系。優(yōu)點(diǎn)在于簡單明了、建模速度快；缺點(diǎn)在于難以描述復(fù)雜工作流業(yè)務(wù)的過程邏輯。所以完全基于有向圖的建模方法沒有得到很好地應(yīng)用。

作為目前主流的建模工具，UML已成為一種事實(shí)上的工業(yè)標(biāo)準(zhǔn)，系統(tǒng)設(shè)計人員能夠利用UML提供的圖形化建模方法為軟件系統(tǒng)進(jìn)行全方位的建模，但是UML的許多概念都基于非形式化語義，不能對模型進(jìn)行精確的描述，構(gòu)建的模型也容易產(chǎn)生模糊和歧義。文獻(xiàn)[4-5]指出FSM的形式化描述語言恰好能在精確語義方面彌補(bǔ)UML的不足。FSM作為形式語言的分析工具，它提供了非常簡單的計算平臺，而且計算的額外開銷很小。此外，它還具有結(jié)構(gòu)清晰、邏輯關(guān)系明確和系統(tǒng)實(shí)現(xiàn)相對容易等優(yōu)點(diǎn)。

采用FSM的思想建模將建模的關(guān)注點(diǎn)從業(yè)務(wù)執(zhí)行過程轉(zhuǎn)移到需要處理的業(yè)務(wù)實(shí)體上。根據(jù)業(yè)務(wù)過程對業(yè)務(wù)實(shí)體建立狀態(tài)模型，同時定義業(yè)務(wù)實(shí)體在某個狀態(tài)上可以接收的輸入，根據(jù)接收的輸入和當(dāng)前狀態(tài)決定業(yè)務(wù)實(shí)體流轉(zhuǎn)的下一個狀態(tài)。這樣，無論業(yè)務(wù)過程如何繁瑣，只需為業(yè)務(wù)實(shí)體建立有限個狀態(tài)，在發(fā)生輸入驅(qū)動時改變業(yè)務(wù)實(shí)體的狀態(tài)，此時跳轉(zhuǎn)、回退、循環(huán)等復(fù)雜操作就可以通過業(yè)務(wù)實(shí)體的狀態(tài)轉(zhuǎn)移來實(shí)現(xiàn)。使用FSM建模，用簡單的狀態(tài)轉(zhuǎn)移就能清晰地描述整個業(yè)務(wù)的規(guī)則，文獻(xiàn)[3]中指出利用FSM的建模方式可以極大地降低二次開發(fā)人員的開發(fā)難度，減少硬編碼業(yè)務(wù)路徑所帶來的風(fēng)險，對于最終用戶來說，通過業(yè)務(wù)實(shí)體的狀態(tài)，就很明顯看出業(yè)務(wù)流程執(zhí)行的情況。

因此采用基于FSM的工作流建模方法，將大大降低建模的難度，更能簡單清晰的體現(xiàn)業(yè)務(wù)的執(zhí)行過程和狀態(tài)的事件驅(qū)動，同時對模型也有準(zhǔn)確的描述，有利于掌握系統(tǒng)的動態(tài)特性和結(jié)構(gòu)，方便代碼產(chǎn)生和優(yōu)化[6]。

3．基于FSM的工作流建模方法

3．1 FSM的模型定義

FSM是實(shí)時系統(tǒng)設(shè)計中的一種離散的數(shù)學(xué)模型，它具有有限數(shù)目的內(nèi)部狀態(tài)，每個狀態(tài)可以遷移至零個或多個狀態(tài)，系統(tǒng)可以根據(jù)當(dāng)前所處的狀態(tài)和面臨的輸入決定系統(tǒng)的后繼行為。一般可以將有限狀態(tài)機(jī)模型定義為五元組：

定義1[7]：有限狀態(tài)機(jī)是一個五元組：

M=(Q，∑ ，δ，q0，F(xiàn))

其中，Q是內(nèi)部狀態(tài)的有限集合，

∑是輸入集合，

δ：Q×∑→Q是狀態(tài)轉(zhuǎn)移函數(shù)，

q0∈Q是初始狀態(tài)，

F∈Q是終止?fàn)顟B(tài)集合。

圖1 有限狀態(tài)機(jī)的工作原理

圖1給出了有限狀態(tài)機(jī)的工作原理，可解釋如下：給定一組內(nèi)部狀態(tài)的有限集合Q和輸入集的條件下，一旦輸入集合∑(t)和狀態(tài)Q(t)確定，在映射的作用下可以確定有限狀態(tài)機(jī)的下一狀態(tài)Q(t+1)，這一工作原理可以用狀態(tài)轉(zhuǎn)移圖(通過圖形化的方式描述狀態(tài)機(jī)各個狀態(tài)之間的轉(zhuǎn)換關(guān)系)或狀態(tài)轉(zhuǎn)換表(用列表的方式描述狀態(tài)機(jī)是數(shù)字邏輯電路常用的設(shè)計方法之一，經(jīng)常被用于對狀態(tài)化簡)來表示。

3．2 可利用FSM建模的系統(tǒng)特點(diǎn)

FSM可以表示為一個有向狀態(tài)圖，主要用于描述被抽象系統(tǒng)的對象在其生命周期內(nèi)所經(jīng)歷的狀態(tài)序列，以及如何響應(yīng)來自外界的各種驅(qū)動事件；同時，F(xiàn)SM具有離散性，它在任何時刻，都處于一個特定狀態(tài)。當(dāng)它在某一狀態(tài)下有事件發(fā)生時，根據(jù)當(dāng)前狀態(tài)和輸入事件的不同，選擇如何處理該事件以及是否需要轉(zhuǎn)換到下一個狀態(tài)。依據(jù)以上FSM特性可知，一個系統(tǒng)要抽象為FSM，必須具備以下特點(diǎn)[8]：

(1)系統(tǒng)會處于某個狀態(tài)下；

(2)系統(tǒng)的狀態(tài)數(shù)量是有限的；

(3)狀態(tài)的改變必須有輸入的發(fā)生；

(4)輸入會觸發(fā)一系列的處理過程，包括執(zhí)行特定的功能、產(chǎn)生相應(yīng)的輸出等；

(5)輸入結(jié)束后，系統(tǒng)狀態(tài)會轉(zhuǎn)移到一個新的相對穩(wěn)定的狀態(tài)。

在工作流建模中，一個關(guān)鍵的問題就是如何根據(jù)事件的變化以及自身的狀態(tài)來決定下一步所要采取的動作，以此達(dá)到自主推理和決策的目的。結(jié)合上面所介紹FSM的工作原理和特點(diǎn)，不難發(fā)現(xiàn)工作流與FSM之間存在著許多共性，因此在明確了行為模型的各個狀態(tài)以及一些觸發(fā)事件與不同狀態(tài)之間轉(zhuǎn)換關(guān)系的基礎(chǔ)之上，完全可以用FSM實(shí)現(xiàn)工作流的建模過程。

3．3 基于狀態(tài)機(jī)的工作流建模方法

FSM建模是將業(yè)務(wù)過程看成是FSM的狀態(tài)轉(zhuǎn)移過程。通常一個完整FSM的設(shè)計，應(yīng)該包括3個元素的設(shè)計：狀態(tài)、事件和狀態(tài)轉(zhuǎn)移函數(shù)。這三要素之間又存在密切的關(guān)系，系統(tǒng)在任一個給定的時刻只能處于其中的一個狀態(tài)；狀態(tài)的變化由事件的發(fā)生來驅(qū)動，事件可以是系統(tǒng)內(nèi)部或外部的輸入信號；系統(tǒng)在當(dāng)前狀態(tài)下接收到事件，執(zhí)行相應(yīng)的動作，即狀態(tài)轉(zhuǎn)移函數(shù)。因此利用FSM建模的關(guān)鍵就是將業(yè)務(wù)過程抽象成FSM的3元素：狀態(tài)、事件、動作，基本步驟如下：

第1步：針對建模的系統(tǒng)，首先進(jìn)行需求分析，正確理解要解決的問題，畫出詳細(xì)的活動流程圖。

第2步：抽象狀態(tài)。這一步是建模的核心，需要分析業(yè)務(wù)處理過程中要經(jīng)歷的步驟，針對每一個具體的工作流環(huán)節(jié)，結(jié)合其所處的狀態(tài)，將其行為模型劃分成可獨(dú)立表示而又相互聯(lián)系的不同任務(wù)，最后把這些任務(wù)抽象成狀態(tài)機(jī)的狀態(tài)。其表示方法是多樣的，有狀態(tài)圖、算法狀態(tài)機(jī)、以及用偽碼描述等，通常采用的是狀態(tài)圖表示法。

第3步：狀態(tài)最小化。在第2步中，可能會產(chǎn)生重復(fù)的狀態(tài)，這些狀態(tài)的輸入和輸出已經(jīng)被其他功能等價的路徑覆蓋了，這時需要合并這些路徑和狀態(tài)，以達(dá)到狀態(tài)最小化，從而降低建模的難度。

第4步：確定各個狀態(tài)間的轉(zhuǎn)移事件。由于業(yè)務(wù)執(zhí)行過程抽象成了工作流的狀態(tài)，那么使業(yè)務(wù)狀態(tài)流轉(zhuǎn)的人物活動或操作就模擬成相應(yīng)的狀態(tài)驅(qū)動事件，這些事件可以驅(qū)動工作流中各個狀態(tài)的相互轉(zhuǎn)移。

第5步：狀態(tài)機(jī)的嵌套。針對復(fù)雜的業(yè)務(wù)流程，一個單獨(dú)的狀態(tài)機(jī)無法完整地表達(dá)業(yè)務(wù)需求，這就需要對狀態(tài)進(jìn)行不同角度、層面的劃分，設(shè)計多個狀態(tài)機(jī)，然后通過嵌套關(guān)系完整地表達(dá)業(yè)務(wù)需求。在嵌套關(guān)系中，外部狀態(tài)機(jī)達(dá)到某一特定狀態(tài)就會觸發(fā)內(nèi)層的狀態(tài)機(jī)的運(yùn)行[8-9]。

從上述步驟中可以看出FSM建模方法的特點(diǎn)是易于建立、過程清晰明了、以描述控制特性為主，它可以應(yīng)用于系統(tǒng)需求分析到實(shí)現(xiàn)的各個階段。

4．建筑企業(yè)資質(zhì)證書流轉(zhuǎn)模型的建模

現(xiàn)以課題組開發(fā)的某建筑企業(yè)招投標(biāo)過程中資質(zhì)證書的借用流轉(zhuǎn)為例，來說明FSM在工作流建模中的具體應(yīng)用。

通常在建筑企業(yè)資質(zhì)證書流轉(zhuǎn)管理的過程中會包含多個狀態(tài)的跳轉(zhuǎn)，假定輸入信息是角色操作的驅(qū)動事件，輸出是控制證書流轉(zhuǎn)的方向，根據(jù)當(dāng)前證書的狀態(tài)和事件的驅(qū)動可以了解證書的下一步的流轉(zhuǎn)狀態(tài)，以此達(dá)到自主推理和決策的目的，這就是證書流轉(zhuǎn)模型的核心問題，有限狀態(tài)機(jī)就是對這一流轉(zhuǎn)模型進(jìn)行建模的。圖2給出了建筑企業(yè)資質(zhì)證書流轉(zhuǎn)業(yè)務(wù)過程中的部分操作活動流程圖。

圖2 企業(yè)證書流轉(zhuǎn)操作流程圖

在明確了資質(zhì)證書流轉(zhuǎn)的各個狀態(tài)以及一些觸發(fā)事件和不同狀態(tài)轉(zhuǎn)換之間的關(guān)系的基礎(chǔ)上，借鑒基于FSM的工作流建模方法的基本步驟，下面給出利用FSM對建筑企業(yè)資質(zhì)證書流轉(zhuǎn)模型進(jìn)行建模的過程如下：

(1)在證書流轉(zhuǎn)的業(yè)務(wù)模型中，總公司最關(guān)注的是證書的位置，及時了解證書的動態(tài)，方便及時調(diào)用，這是建模的目標(biāo)。

(2)根據(jù)業(yè)務(wù)流程圖，在證書申請、借用和調(diào)配的過程中，不難抽象出證書具有以下狀態(tài)：在總公司、在分公司、在郵寄中、在使用中等狀態(tài)。假設(shè)該公司有N個分公司和一個總公司，我們用Xi表示證書在第i個公司，用X0表示在總公司，Y表示證書在郵寄中狀態(tài)，這時就可以得到FSM的狀態(tài)集合Q={X0，X1，X2···Y}。

(3)結(jié)合不同狀態(tài)下角色操作的事件驅(qū)動，可以得出FSM的輸入集合：∑={借用，歸還，調(diào)配}。這樣就可以畫出證書位置的FSM狀態(tài)轉(zhuǎn)換圖，如圖3所示，其中箭頭上的文字是狀態(tài)轉(zhuǎn)換的驅(qū)動事件。

圖3 FSM狀態(tài)轉(zhuǎn)換圖

(4)圖3中只是給出了一個簡單行為模型的FSM的表示，但不能完全表達(dá)復(fù)雜的業(yè)務(wù)需求的細(xì)節(jié)情況，這里使用嵌套的有限狀態(tài)機(jī)來解決這個問題，即一個FSM可以作為另一個FSM中某一狀態(tài)的工作進(jìn)程而存在，當(dāng)外層FSM被觸發(fā)到某一狀態(tài)時，相對應(yīng)的內(nèi)層FSM便啟動，完成操作后又重新回到外部的FSM。下面對上一示例更進(jìn)一步說明，每一次證書的借用或調(diào)配都要經(jīng)歷“郵寄”到“簽收”到“使用”的過程，圖4給出了證書每次流轉(zhuǎn)過程中經(jīng)歷的狀態(tài)轉(zhuǎn)換圖。

圖4 證書流轉(zhuǎn)狀態(tài)轉(zhuǎn)換圖

如果將圖4中的狀態(tài)機(jī)看成M，將其融合到圖3的狀態(tài)機(jī)中，就可得到嵌套的狀態(tài)機(jī)模型，如圖5所示，這樣就簡單清晰地表達(dá)了復(fù)雜的業(yè)務(wù)流程，完成了FSM的工作流建模。根據(jù)FSM的工作流模型，只要記錄FSM的每次流轉(zhuǎn)狀態(tài)就可以及時了解證書的動態(tài)，方便及時調(diào)用。

圖5 嵌套模型

5．結(jié)束語

本文提出一種采用FSM進(jìn)行工作流建模的設(shè)計方案，據(jù)此方法建立的工作流模型具有易于理解、結(jié)構(gòu)清晰和維護(hù)方便的優(yōu)點(diǎn)，還有利于后期系統(tǒng)的代碼實(shí)現(xiàn)。文中的建模案例已經(jīng)成功應(yīng)用于某建筑公司的項目與證件管理系統(tǒng)中，并確保了證書流轉(zhuǎn)的正常運(yùn)行。

[1]施雅賢，王繼偉等．面向協(xié)同審批的工作流模型構(gòu)建[J]．電子設(shè)計工程，2011，19(18)：60-62

[2]徐俊，鄔少飛，胡和平．一個結(jié)構(gòu)化的工作流模型建模方法[J]．計算機(jī)與數(shù)字工程，2006，34：94-96．

[3]孫雪峰．基于有限狀態(tài)機(jī)的工作流引擎的設(shè)計和實(shí)現(xiàn)[D]．北京：北京郵電大學(xué)，2008．

[4]朱晟仁．有限狀態(tài)機(jī)在動畫角色行為中的建模應(yīng)[J]．計算機(jī)技術(shù)與發(fā)展，2007，17(6)：130-132．

[5]李弘彥．UML協(xié)作圖到自動機(jī)觀測模型轉(zhuǎn)化方法的研究[D]．西安：西安理工大學(xué)，2008．

[6]王欣．基于狀態(tài)機(jī)的移動終端應(yīng)用軟件設(shè)計[D]．上海：上海交通大學(xué)，2007．

[7]Rich，Elaine．Automata，computability，and complexity：theory and applications[M]，2011．

[8]黃楊明．基于有限狀態(tài)機(jī)理論的導(dǎo)航軟件設(shè)計與實(shí)現(xiàn)[D]．長沙：國防科學(xué)技術(shù)大學(xué)，2006．

[9]劉秀羅，黃柯棣．有限狀態(tài)機(jī)在CGF行為建模中的應(yīng)用[J]．系統(tǒng)仿真學(xué)報，2001，13(5)：663-665．

Workflow Modeling Method Based on FSM and ItsApplication

Chen Jindong Wang Xiaohu Wu Xingtong Chen Zhongyu
(Zhejiang Normal University,Jinhua 321004,Zhejiang)

tract】 Traditional workflow modeling tool is carried out in accordance with the process of serialization and focuses on the execution sequence and path of business,which is difficult to model the complex business processes of jump,fallback and circulation.Thus,this paper proposes a workflow modeling method based on the finite state machine which regards the business process as the transition process of the finite state machine.Then,this paper gives the building process of the workflow modeling and finally illustrates the modeling method through a living example.

words】 finite-state machine;workflow technology;certificate of circulation;workflow model

陳金東，男，安徽安慶人，碩士研究生，研究方向：軟件工程。

浙江省自然科學(xué)基金資助項目，項目編號：LY12F02009。