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

（浙江師范大學(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)移過程，給出工作流建模的幾個(gè)步驟，最后通過一個(gè)實(shí)例對該建模方法進(jìn)行分析說明。

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

1．引言

隨著信息技術(shù)和網(wǎng)絡(luò)技術(shù)的快速發(fā)展，工作流技術(shù)在各個(gè)領(lǐng)域得到了廣泛應(yīng)用，它實(shí)現(xiàn)工作過程管理的自動(dòng)化、智能化和整合化，很大程度提高業(yè)務(wù)人員的工作效率[1]。而工作流建模是工作流技術(shù)的關(guān)鍵，設(shè)計(jì)一個(gè)理想的工作流模型可以使得工作流系統(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ù)過程按時(shí)序關(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)描述工作流過程中的活動(dòng)或者狀態(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è)計(jì)人員能夠利用UML提供的圖形化建模方法為軟件系統(tǒng)進(jìn)行全方位的建模，但是UML的許多概念都基于非形式化語義，不能對模型進(jìn)行精確的描述，構(gòu)建的模型也容易產(chǎn)生模糊和歧義。文獻(xiàn)[4-5]指出FSM的形式化描述語言恰好能在精確語義方面彌補(bǔ)UML的不足。FSM作為形式語言的分析工具，它提供了非常簡單的計(jì)算平臺(tái)，而且計(jì)算的額外開銷很小。此外，它還具有結(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)模型，同時(shí)定義業(yè)務(wù)實(shí)體在某個(gè)狀態(tài)上可以接收的輸入，根據(jù)接收的輸入和當(dāng)前狀態(tài)決定業(yè)務(wù)實(shí)體流轉(zhuǎn)的下一個(gè)狀態(tài)。這樣，無論業(yè)務(wù)過程如何繁瑣，只需為業(yè)務(wù)實(shí)體建立有限個(gè)狀態(tài)，在發(fā)生輸入驅(qū)動(dòng)時(shí)改變業(yè)務(wù)實(shí)體的狀態(tài)，此時(shí)跳轉(zhuǎn)、回退、循環(huán)等復(fù)雜操作就可以通過業(yè)務(wù)實(shí)體的狀態(tài)轉(zhuǎn)移來實(shí)現(xiàn)。使用FSM建模，用簡單的狀態(tài)轉(zhuǎn)移就能清晰地描述整個(gè)業(yè)務(wù)的規(guī)則，文獻(xiàn)[3]中指出利用FSM的建模方式可以極大地降低二次開發(fā)人員的開發(fā)難度，減少硬編碼業(yè)務(wù)路徑所帶來的風(fēng)險(xiǎn)，對于最終用戶來說，通過業(yè)務(wù)實(shí)體的狀態(tài)，就很明顯看出業(yè)務(wù)流程執(zhí)行的情況。

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

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

3．1 FSM的模型定義

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

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

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ī)各個(gè)狀態(tài)之間的轉(zhuǎn)換關(guān)系)或狀態(tài)轉(zhuǎn)換表(用列表的方式描述狀態(tài)機(jī)是數(shù)字邏輯電路常用的設(shè)計(jì)方法之一，經(jīng)常被用于對狀態(tài)化簡)來表示。

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

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

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

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

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

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

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

在工作流建模中，一個(gè)關(guān)鍵的問題就是如何根據(jù)事件的變化以及自身的狀態(tài)來決定下一步所要采取的動(dòng)作，以此達(dá)到自主推理和決策的目的。結(jié)合上面所介紹FSM的工作原理和特點(diǎn)，不難發(fā)現(xiàn)工作流與FSM之間存在著許多共性，因此在明確了行為模型的各個(gè)狀態(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)移過程。通常一個(gè)完整FSM的設(shè)計(jì)，應(yīng)該包括3個(gè)元素的設(shè)計(jì)：狀態(tài)、事件和狀態(tài)轉(zhuǎn)移函數(shù)。這三要素之間又存在密切的關(guān)系，系統(tǒng)在任一個(gè)給定的時(shí)刻只能處于其中的一個(gè)狀態(tài)；狀態(tài)的變化由事件的發(fā)生來驅(qū)動(dòng)，事件可以是系統(tǒng)內(nèi)部或外部的輸入信號；系統(tǒng)在當(dāng)前狀態(tài)下接收到事件，執(zhí)行相應(yīng)的動(dòng)作，即狀態(tài)轉(zhuǎn)移函數(shù)。因此利用FSM建模的關(guān)鍵就是將業(yè)務(wù)過程抽象成FSM的3元素：狀態(tài)、事件、動(dòng)作，基本步驟如下：

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

第2步：抽象狀態(tài)。這一步是建模的核心，需要分析業(yè)務(wù)處理過程中要經(jīng)歷的步驟，針對每一個(gè)具體的工作流環(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步中，可能會(huì)產(chǎn)生重復(fù)的狀態(tài)，這些狀態(tài)的輸入和輸出已經(jīng)被其他功能等價(jià)的路徑覆蓋了，這時(shí)需要合并這些路徑和狀態(tài)，以達(dá)到狀態(tài)最小化，從而降低建模的難度。

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

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

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

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

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

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

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

在明確了資質(zhì)證書流轉(zhuǎn)的各個(gè)狀態(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)注的是證書的位置，及時(shí)了解證書的動(dòng)態(tài)，方便及時(shí)調(diào)用，這是建模的目標(biāo)。

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

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

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

(4)圖3中只是給出了一個(gè)簡單行為模型的FSM的表示，但不能完全表達(dá)復(fù)雜的業(yè)務(wù)需求的細(xì)節(jié)情況，這里使用嵌套的有限狀態(tài)機(jī)來解決這個(gè)問題，即一個(gè)FSM可以作為另一個(gè)FSM中某一狀態(tài)的工作進(jìn)程而存在，當(dāng)外層FSM被觸發(fā)到某一狀態(tài)時(shí)，相對應(yīng)的內(nèi)層FSM便啟動(dòng)，完成操作后又重新回到外部的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)就可以及時(shí)了解證書的動(dòng)態(tài)，方便及時(shí)調(diào)用。

圖5 嵌套模型

5．結(jié)束語

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

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

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

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

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

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

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

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

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

[9]劉秀羅，黃柯棣．有限狀態(tài)機(jī)在CGF行為建模中的應(yīng)用[J]．系統(tǒng)仿真學(xué)報(bào)，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é)基金資助項(xiàng)目，項(xiàng)目編號：LY12F02009。