支持動態調度的工作流Ｄ—Ｆｌｏｗ Ｅｎｇｉｎｅ的設計與實現
2007-01-01 00:00:00施勇尹建偉周勇軍董金祥
計算機應用研究 2007年3期
摘 要：基于流程與活動兩個級別考慮，提出支持動態調度的工作流D—Flow Engine；從動態路由和流程多版本方面分析了其動態調度特性。通過在流程建模階段擴展工作流管理聯盟的工作流元模型相關定義，重點分析了動態路由和多版本流程遷移在流程運行階段的調度實現。實踐表明，D—Flow Engine提高了工作流的適應性，滿足了企業對工作流動態性的需求。
關鍵詞：工作流； 動態性； 元模型； 路由
中圖分類號：TP391文獻標志碼：A
文章編號：1001—3695(2007)03—0173—04
隨著工作流技術的快速發展以及在實際應用中的不斷深入，人們對工作流系統提出了更多的功能要求，其中一個主要問題是工作流系統的靈活性和動態性。傳統工作流的工作過程分為建模階段和運行階段。建模階段是對一個工作流程進行模型定義；運行階段是工作流執行服務對工作流定義進行解釋執行。由于現實的工作流系統可能無法事先確定所有過程，并且過程之間的關系在執行期間并不是一成不變的，工作流系統缺乏柔性和動態性。如何使工作流系統具有靈活的動態性和自適應能力，已經成為目前工作流管理系統研究的一個熱點。
在可適應動態工作流方面，研究者們進行了廣泛的探索研究。文獻[1]討論了工作流實際運行中可能出現的各種異常；根據其影響大小進行分類，分析了如何預防、檢測和恢復異常，并應用在工作流系統Endeavors中。文獻[2]描述了一個具有動態路由和操作控制機制的工作流實現框架，提出了其構成三要素，即工作流控制表、約束序列和基于事件的管理規則。文獻[3]利用繼承思想提出了工作流繼承保留轉換規則，以此來解決流程動態遷移帶來的一系列問題。文獻[4]采用一個正確性評價來確保流程運行時能夠在流程定義規則改變的情況下順利地進行動態遷移。文獻[5]介紹了一個有改善性能的工作流路由調度算法。文獻[6]中的Reflection 方法采用工作流執行過程中人機不斷交互來完成一個具有動態執行的工作流程。
以上各種研究方法從適應性、動態性等角度出發，采用各種具體方法試圖使工作流系統具備動態柔性特征。但另一方面，工作流的基本特征就是業務邏輯與應用相分離，可以從模型方面出發改善其動態適應能力。本文設計并實現了一個支持動態調度的工作流引擎D—Flow Engine，給出了其工作流元模型，重點研究了工作流的流程動態調度服務，最后結合應用實例進行了研究并給出結論。
1 D—Flow Engine工作流元模型
如圖1所示，D—Flow Engine工作流元模型有兩個層次，即核心模型和支撐模型。核心模型是以流程、活動等過程模型為中心，另外還包含數據模型和應用模型；支撐模型主要包括組織模型、資源模型、權限模型和時間模型。
圖1 D—Flow Engine工作流元模型
支撐模型是任何一個工作流模型所必需的，但同時它們又經常與企業中其他應用系統有所關聯，為了實現工作流系統的集成性和柔性，有必要將它們分為獨立的一類。
D—Flow Engine的動態性主要體現在兩個方面：①流程的適應性，即一個流程定義能夠根據用戶的不同需求而實例化出滿足不同需求的流程實例；②活動任務的分配，即每次活動激活分配任務時能夠根據當時的實際需要來分配合適的任務執行人。文獻[7]中詳細討論了活動任務的動態分配，不在本文論述之列。D—Flow Engine在流程動態調度方面支持動態路由和多版本流程，可以根據時間分為兩個方面，即建模階段和運行階段。建模階段的動態性是指工作流定義時能夠定義一個流程的動態特性；運行階段的動態性是指工作流程實例能夠修改預先定義的流程或一些不可預測的變化。
2 流程動態調度
2.1 工作流建模階段對動態調度的支持
一個工作流程由活動（Activity）和遷移（Transition）組成，根據兩者之間的關系，傳統工作流系統提供了串行、分叉、合并、循環等基本路由調度。但企業的實際應用往往比較復雜，用戶在結束一個活動任務后，有可能需要跳過某個（些）活動節點繼續執行；或者用戶認為目前任務狀態沒有滿足需求，需要重新反饋到前面某個活動節點重復執行。由于人為等不確定因素的存在，在流程建模定義時很難對這些動態路由直接用遷移清晰地表明出來。D—Flow Engine在提供了串行等基本路由的基礎上還支持跳躍和反饋路由。
定義1 跳躍路由：某活動A的活動實例執行完成后不激活后續活動而跳躍激活后面某個活動B使流程繼續執行，而在A、B之間不存在直接遷移，則活動A到B的路由為跳躍路由。
定義2 反饋路由：某活動A的活動實例執行完成后，在不存在遷移的情況下，激活其前面一個活動節點B，則活動A到B的路由為反饋路由。
D—Flow Engine通過擴充活動的屬性定義來支持動態路由。WfMC雖然對一般活動屬性進行了基本的定義，如ID、Name等，但要支持動態調度，就有必要對其進行擴充。在傳統工作流中，一個活動出現在一個流程中意味著當流程到達該活動時活動就要執行，活動之間分不出哪些是關鍵的，哪些是可以變通的。為了使整個流程具有靈活性，將活動分成以下幾個類別：必須執行、可被跳過執行、可反饋執行、需要人工干預，每類活動分別對應執行的不同行為。
定義3 活動Activity:={AID，Name，T，Data，State，Attribute，Condition}。其中AID為活動的標志信息，包括活動標志號和版本號，構成二維變量唯一地確定一個活動；Name為活動名稱；T是一個謂詞邏輯表達式，T∷=f(O)表示該活動要完成具體的一個動作或功能， f是一個邏輯謂詞，O是f操作的對象，如WriteDoc(a.doc)表示書寫名為a.doc的文檔；State是當前活動的狀態；Attribute描述了該活動在執行時的行為屬性，包括可被跳過執行、可反饋執行、必須執行、需要人工干預等，其中可反饋有發出（Out）和接收（In）兩種類型；Condition代表活動的激活條件和完成條件，其中有活動的合并方式（AND，OR）和分裂方式（AND，OR）。
工作流D—Flow Engine建模階段對動態調度支持另一個方面的表現是流程的多版本。工作流是企業經營過程重組的一個重要使能方式。在企業過程重組和結構優化中，一個工作流程往往需要不斷更新，從而造成新舊版本流程共存。D—Flow Engine支持新舊多個版本的流程，采用與面向對象語言類似的單根繼承體系，分別實現流程定義間與活動間的繼承關系。在流程定義間的繼承關系中將活動、遷移和流程相關數據作為流程定義的可繼承屬性；在活動中就是相關數據作為可繼承屬性。工作流模型繼承體系中提供了虛流程定義的概念。
定義4 虛流程定義：不具有完整信息集合、不能直接被實例化的流程定義。例如可以不具有開始、結束活動，可以有單個孤立活動節點等可實例化流程定義不能出現的情況。
D—Flow Engine模型繼承關系中支持以下兩種繼承特性：
（1）公用（Public）——父流程定義中某個可繼承屬性的繼承特性為Public，則任何繼承該父流程定義的子流程定義都可以擁有該屬性。
（2）私有（Private）——父流程定義中某個可繼承屬性的繼承特性為Private，則任何繼承該父流程定義的子流程定義都不能看見該屬性，即不擁有該屬性。同時由于工作流模型屬性的關聯性，如活動A是私有的，則所有與其關聯的遷移都必須是私有的。
定義5 流程標志WFID:={ID，Versiton，Valid，PID，PVersion}。其中，ID是父子系列流程定義的標志；Version表示此流程定義的版本序列號，與ID構成一個具體流程定義的唯一標志；Valid有效性標志表示該版本流程是否還可以實例化執行，是一個布爾型值；PID是父流程的ID，沒有父流程則為空；PVersion是父流程的版本序列號，沒有父流程則為空。
定義6 流程ProcessDefinition:={WFID，Dr，Ao，To，MA，MA，Rules}。其中，WFID為流程標志；Dr是流程的數據信息；Ao、To是流程自定義的所有活動集合和所有遷移集合；MA、MT分別是父子流程中活動和遷移的替代映射關系；Rules是流程定義的一組規則和策略，如任務分配的方式（推式和拉式）、路由分支的選擇策略、流程新舊版本遷移策略等。
2.2 工作流運行階段對動態調度的處理
工作流運行階段對動態調度的處理可以分為三類：①處理在建模階段預先定義的有動態調度行為的活動或流程；②修改原來定義的流程實例，并根據新的流程實例形成新的流程定義；③只修改運行的流程實例而不改變流程定義（適合臨時改變流程實例的情況下），這個流程實例運行完成后不影響原來的流程定義。
因此，可以將運行階段工作流的動態調度分為兩種：①可預測的處理（如前面提到的建模階段中動態路由和多版本流程的處理），即工作流引擎從流程定義中已知流程和活動的意義是什么，只是具體的操作要由人工干預或由不同規則來處理；②不可預測的操作（如一個活動正在執行時或已執行完畢，因為其他活動修改或執行失敗導致該活動的重新執行或撤銷等；人工干預在何時進行操作原語，何時提交給工作流引擎也是不可預測的）。
2.2.1 流程實例的動態路由
流程實例執行的過程中，路由的動態調度實質上可以看成是由一個活動節點定向路由到另一個活動節點，而不用去關心間隔的活動節點。下面是跳躍路由的運行步驟：
（1）完成活動實例A后，判斷其后續活動是否有可被跳過行為屬性。沒有，則不發生跳躍路由直接激活后續活動，返回；有則轉（2）。
（2）詢問用戶是否需要進行跳躍路由。不需要則不發生跳躍路由，返回；需要則轉（3）。
（3）尋找流程定義的規則策略集Rules中是否存在從活動A開始的跳躍規則。有則自動根據規則進行跳躍路由，返回；無則轉（4）。
（4）列出從活動A開始可跳躍路由到的所有活動節點集合，讓用戶選擇一個活動節點進行跳躍路由。
（5）詢問用戶是否需要將此跳躍規則添加到流程定義的規則策略集中以實現自動跳躍路由。不需要則完成跳躍路由；需要則添加跳躍規則并完成路由。
反饋路由與此類似，只是在步驟（1）中判斷的是活動A是否具有可發出反饋的行為屬性。無論是跳躍還是反饋，在路由過程中都需要越過某些活動。而這些被越過的活動與其他活動必然存在著一定的關系，動態路由的執行將會影響到活動任務存在的環境。因此，在執行動態路由時需要避免或消除路由操作帶來的不利影響。這種影響主要來源于活動之間的依賴關系，可將其分為以下兩種：
（1）數據依賴。流程定義中各個活動之間可能存在數據的相互依賴，依賴活動的數據值需要被依賴活動的數值。在這種依賴關系下，進行動態路由必須解決路由中跳過的活動間的數據依賴性。如圖2所示，從活動“送審1”定向路由到活動“送審6”，活動“送審6”對活動“送審2”和活動“送審4”有數據依賴，則定向路由成功的必要條件是活動“送審6”的依賴數據可以通過取缺省值或人工賦值等方式代替數據依賴。
（2）路由依賴。如果不考慮路由依賴關系，通過動態路由可能會導致兩種不希望的后果。假設活動“送審1”和“送審2”的分裂為“AND”，活動“送審6”的合并也為“AND”，則：
①遷移實例無限等待。例如活動“送審6”反饋路由到活動“送審3”，則最后結果由于活動“送審5”和活動“送審4”無法到達，造成從活動“送審3”到活動“送審6”的遷移實例無限等待而無法激活“送審6”。
②活動實例無限等待。例如活動“送審4”反饋路由到活動“送審1”，由于“送審1”的分裂是“AND”，此時如果“送審2”活動實例仍處于激活狀態，則將造成“送審2”活動實例處于無限等待狀態。
圖2 流程定義示例圖
為了避免上述兩種異常情況的出現，D—Flow Engine工作流采用了配對活動方法對動態路由目標進行過濾。通過配對活動法過濾后的活動均可作為動態路由的目標活動節點。
定義7 前驅（后繼）活動：如果從活動A到活動B存在一條通路（不考慮循環路由），則稱活動A為活動B的前驅活動，活動B為活動A的后繼活動。
定義8 配對活動：活動節點A和活動節點B符合如下三條規則，則稱活動A和活動B是配對活動。
（1）活動A和活動B至少存在一條通路（為便于敘述將以下規則活動B設為活動A的后繼活動）。
（2）設Ps為從活動B到開始節點的所有路由活動節點集合，則P∈Ps均滿足A∈P。
（3）設Pe為從活動A到結束節點的所有路由活動節點集合，則P∈Pe均滿足B∈P。
那么，設從活動A到活動B欲進行動態路由，過濾方法如下：
(1)活動A和活動B之間至少存在一條通路。
(2)如果從活動A到活動B之間存在一條通路，并且活動A和活動B是配對活動，則過濾成功。
(3)如果從活動B到活動A之間存在一條通路，則活動A的合并條件是“OR”；活動A和活動B是配對活動，則過濾成功。
如圖2所示，如果活動節點“送審6”的合并條件是“AND”，則從活動節點“送審6”動態路由到活動節點“送審1”是合法的；而動態路由至活動節點“送審2”或“送審3”則是非法的。
2.2.2 多版本流程的動態遷移
多版本流程的實質是工作流運行過程中對原有流程定義的修改，主要有以下幾個方面：①流程基本屬性與其相關數據的修改；②活動基本屬性與其相關數據的修改；③遷移基本屬性的修改；④活動和遷移的增加或刪除，以及所造成的路由更改。
與流程動態路由調度僅造成流程實例自身執行的修改不同的是，流程定義的修改可能會對屬于該流程定義的所有流程實例的執行造成影響。傳統的處理策略有以下幾種方式：
（1）重起。對屬于該流程定義的所有未完成流程實例均執行重起操作，并通過回滾（Rollback）機制來處理由已運行流程實例帶來的影響。該策略處理簡單，但不適合無法通過回滾來消除影響的情況。
（2）繼續。繼續執行該流程定義的未完成流程實例，新起流程實例按照更改后的流程定義執行。該策略處理簡單，但不能滿足用戶的一些需求。
（3）遷移。通過一定的策略，將該流程定義的未完成流程實例的執行由老流程定義遷移至新流程定義，按照新流程定義執行。
D—Flow Engine通過流程定義版本管理實施的流程定義級更改處理策略，以流程定義有效性為開關，實現繼續和遷移兩種處理策略的動態選擇。如果舊版本流程定義還有效，則舊版本流程定義的所有未完成流程實例采用繼續策略，按照舊版本流程定義執行；否則采用遷移的處理策略。與動態路由調度一樣，流程間遷移也存在數據依賴和路由依賴的問題，所以遷移并不一定成功。一旦發現遷移失敗，則應立即采用重起策略。
可將流程動態遷移的過程歸納為五個步驟：暫停執行、流程遷移、遷移后提交、正確性驗證、繼續執行。暫停執行是當一個流程實例在運行過程中接到一個流程遷移的工作流內部操作消息時，該流程實例要保持的一種狀態。這是流程定義中已明確規定的，以便系統進行處理。流程動態遷移的基本策略是：若當前活動或遷移是Private的，則沿用老版本流程的活動或遷移；當前活動或遷移是Public的，則按照新流程定義中的活動遷移替代映射關系用新版本活動或遷移代替老版本活動或遷移。提交過程是按照修改后的流程定義來執行流程實例的。這時要考慮兩方面問題：①新流程會不會影響原先的運行狀態，包括撤銷已執行的部分活動、回退到先前某個活動（可能需要補償）、跳到另一個活動執行；②新流程中的活動與原先活動是否存在數據關聯和路由關聯、其相應的關聯內容是什么、活動之間的關聯關系是否會影響該流程與其他流程的關聯關系等。這些必須有相應的關聯規則來約束。動態遷移后的工作流需要對其進行驗證，驗證的內容包括在結構和語義上是否正確、是否破壞了數據一致性和控制一致性等。這需要通過活動間、遷移間的相應關聯規則來解決，從而保證遷移后工作流的正確性。
工作流在執行階段進行動態調度時，必須有一組規則和相應算法來保證調度后工作流的正確性。這些規則包括提交規則和驗證規則等。
3 應用研究
流程在實際運行過程中，當結束“送審1”后可直接跳過“送審2”激活“送審3”，如圖4所示。
圖4 “送審2”被跳過之后
活動“送審3”可以選擇繼續執行下去直到流程結束；或者選擇反饋，到可接收反饋節點“送審1”，如圖5所示。由于業務流程的調整，需要從流程一遷移到新版本流程二。由流程一定義可知活動“送審3”及其關聯的“遷移3”和“遷移4”都是私有的。新版本流程二的定義如下：
若同時設置流程一的有效性WFIDA·Valid=False，在流程運行過程中就會實現動態遷移。流程定義二會繼承除“送審2”“遷移3”“送審3”和“遷移4”以外定義一的所有其他活動和遷移；同時“會簽”“遷移3′”“審核”和“遷移4′”分別覆蓋了“送審2”“遷移3”“送審3”和“遷移4”。所有流程實例都會按照新版本流程定義二來運行，如圖6所示。
4 結束語
本文所提出的支持動態調度的工作流D—Flow Engine已經得到實際應用，基本滿足了企業應用中調度分配的動態性需求。流程級調度服務的動態路由調度和多版本流程動態遷移的目的就是在恰當的時間激活合適的活動實例。在按照所執行流程實例的流程模式規則前提下，提供最大限度的柔性和動態性，是流程實例執行的關鍵服務，也是工作流系統性能和動態性的關鍵所在。在融合流程繼承機制和動態路由基礎上，D—Flow Engine具備了很高的柔性和動態性。但是還有很多工作尚未完成，如繼承遷移的事務性處理、高性能調度算法等都是有待進一步解決的問題。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
