基于FSM的工作流建模方法及其應用

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

（浙江師范大學數理與信息工程學院，浙江 金華 321004）

基于FSM的工作流建模方法及其應用

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

（浙江師范大學數理與信息工程學院，浙江 金華 321004）

傳統工作流建模工具大多是按照流程序列化思想進行使用，關注的是業務的執行順序和路徑，難以對跳轉、回退、循環等復雜的業務過程進行建模。本文提出一種基于有限狀態機的工作流進行建模的方法，該方法將業務過程看成是有限狀態機的狀態轉移過程，給出工作流建模的幾個步驟，最后通過一個實例對該建模方法進行分析說明。

有限狀態機；工作流技術；證書流轉；工作流模型

1．引言

隨著信息技術和網絡技術的快速發展，工作流技術在各個領域得到了廣泛應用，它實現工作過程管理的自動化、智能化和整合化，很大程度提高業務人員的工作效率[1]。而工作流建模是工作流技術的關鍵，設計一個理想的工作流模型可以使得工作流系統有效地運行[2]。傳統的工作流建模方法有多種，如：有向圖、面向對象、實體關聯建模、事務建模、Petri網等方法。這些傳統的建模思想存在著許多不足，文獻[3]中指出傳統的建模思想是基于流程序列化思想進行的，按照業務執行的順序將業務過程按時序關系進行排列，確定業務過程執行的步驟，這種建模方式關注的是業務的執行順序和路徑。然而在現實生活中，業務過程具有復雜和多變等特點，表現為眾多狀態之間的跳轉、回退、循環和聚合等。為了彌補傳統建模方法存在的這些不足，本文提出采用有限狀態機(Finite State Machine，FSM)的思想對工作流進行建模的方法和步驟。

2．有限狀態機建模的優勢

早期針對簡單的工作流，一般采用基于有向圖技術進行建模，用圖形中的節點描述工作流過程中的活動或者狀態，而用有向弧表示節點的順序依賴關系。優點在于簡單明了、建模速度快；缺點在于難以描述復雜工作流業務的過程邏輯。所以完全基于有向圖的建模方法沒有得到很好地應用。

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

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

因此采用基于FSM的工作流建模方法，將大大降低建模的難度，更能簡單清晰的體現業務的執行過程和狀態的事件驅動，同時對模型也有準確的描述，有利于掌握系統的動態特性和結構，方便代碼產生和優化[6]。

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

3．1 FSM的模型定義

FSM是實時系統設計中的一種離散的數學模型，它具有有限數目的內部狀態，每個狀態可以遷移至零個或多個狀態，系統可以根據當前所處的狀態和面臨的輸入決定系統的后繼行為。一般可以將有限狀態機模型定義為五元組：

定義1[7]：有限狀態機是一個五元組：

M=(Q，∑ ，δ，q0，F)

其中，Q是內部狀態的有限集合，

∑是輸入集合，

δ：Q×∑→Q是狀態轉移函數，

q0∈Q是初始狀態，

F∈Q是終止狀態集合。

圖1 有限狀態機的工作原理

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

3．2 可利用FSM建模的系統特點

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

(1)系統會處于某個狀態下；

(2)系統的狀態數量是有限的；

(3)狀態的改變必須有輸入的發生；

(4)輸入會觸發一系列的處理過程，包括執行特定的功能、產生相應的輸出等；

(5)輸入結束后，系統狀態會轉移到一個新的相對穩定的狀態。

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

3．3 基于狀態機的工作流建模方法

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

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

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

第3步：狀態最小化。在第2步中，可能會產生重復的狀態，這些狀態的輸入和輸出已經被其他功能等價的路徑覆蓋了，這時需要合并這些路徑和狀態，以達到狀態最小化，從而降低建模的難度。

第4步：確定各個狀態間的轉移事件。由于業務執行過程抽象成了工作流的狀態，那么使業務狀態流轉的人物活動或操作就模擬成相應的狀態驅動事件，這些事件可以驅動工作流中各個狀態的相互轉移。

第5步：狀態機的嵌套。針對復雜的業務流程，一個單獨的狀態機無法完整地表達業務需求，這就需要對狀態進行不同角度、層面的劃分，設計多個狀態機，然后通過嵌套關系完整地表達業務需求。在嵌套關系中，外部狀態機達到某一特定狀態就會觸發內層的狀態機的運行[8-9]。

從上述步驟中可以看出FSM建模方法的特點是易于建立、過程清晰明了、以描述控制特性為主，它可以應用于系統需求分析到實現的各個階段。

4．建筑企業資質證書流轉模型的建模

現以課題組開發的某建筑企業招投標過程中資質證書的借用流轉為例，來說明FSM在工作流建模中的具體應用。

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

圖2 企業證書流轉操作流程圖

在明確了資質證書流轉的各個狀態以及一些觸發事件和不同狀態轉換之間的關系的基礎上，借鑒基于FSM的工作流建模方法的基本步驟，下面給出利用FSM對建筑企業資質證書流轉模型進行建模的過程如下：

(1)在證書流轉的業務模型中，總公司最關注的是證書的位置，及時了解證書的動態，方便及時調用，這是建模的目標。

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

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

圖3 FSM狀態轉換圖

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

圖4 證書流轉狀態轉換圖

如果將圖4中的狀態機看成M，將其融合到圖3的狀態機中，就可得到嵌套的狀態機模型，如圖5所示，這樣就簡單清晰地表達了復雜的業務流程，完成了FSM的工作流建模。根據FSM的工作流模型，只要記錄FSM的每次流轉狀態就可以及時了解證書的動態，方便及時調用。

圖5 嵌套模型

5．結束語

本文提出一種采用FSM進行工作流建模的設計方案，據此方法建立的工作流模型具有易于理解、結構清晰和維護方便的優點，還有利于后期系統的代碼實現。文中的建模案例已經成功應用于某建筑公司的項目與證件管理系統中，并確保了證書流轉的正常運行。

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

[2]徐俊，鄔少飛，胡和平．一個結構化的工作流模型建模方法[J]．計算機與數字工程，2006，34：94-96．

[3]孫雪峰．基于有限狀態機的工作流引擎的設計和實現[D]．北京：北京郵電大學，2008．

[4]朱晟仁．有限狀態機在動畫角色行為中的建模應[J]．計算機技術與發展，2007，17(6)：130-132．

[5]李弘彥．UML協作圖到自動機觀測模型轉化方法的研究[D]．西安：西安理工大學，2008．

[6]王欣．基于狀態機的移動終端應用軟件設計[D]．上海：上海交通大學，2007．

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

[8]黃楊明．基于有限狀態機理論的導航軟件設計與實現[D]．長沙：國防科學技術大學，2006．

[9]劉秀羅，黃柯棣．有限狀態機在CGF行為建模中的應用[J]．系統仿真學報，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

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

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