數據驅動的分布式工作流中的任務調度方法

許廣繁

[摘 ? ?要] 為使工作流中的任務能根據內外部因素的變化進行自適應調度，在分布式工作流模型的基礎上，通過基于數據驅動，引入流程版本信息和優化彈簧算法對工作流中的任務進行動態負載平衡調度，提出了一種數據驅動的柔性分布式工作流自適應任務調度方法，以支持工作流中的任務動態自適應調整，以使系統更好地適應環境、優化流程、提高效率。

[關鍵詞] 分布式工作流;任務調度;數據驅動;自適應調度

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2019. 19. 067

[中圖分類號] TP311 ? ?[文獻標識碼] ?A ? ? ?[文章編號] ?1673 - 0194（2019）19- 0157- 02

1 ? ? ?概 ? ?述

工作流是指業務流程完全或部分自動化運行[1]，它通過將工作活動分解成定義明確的任務、角色、規則和過程，來完成工作的整體執行和監控，是現實生活中各種工作活動在信息世界中的映像。同時，由于業務的發展、客戶需求的變更及科學技術的更新，工作流需要根據內外部因素的變化進行自適應調整以使系統適應環境、優化流程、提高效率和提升收益。

因工作流的任務調度在對任務的運行、管理、監控及分析執行過程等方面的作用較為重要。文獻[2]對柔性工作流理論方法進行全面的綜述，并對各種方法的優缺點和適用領域進行了對了對比分析。文獻[3]則提出了一種基于比例-積分-微分控制的自適應任務調度方法，以提高分布式工作流中實時任務調度的效率。文獻[4]則在業務流程模型的基礎上提出了一種業務流程變更自適應模型。但在最初的工作流程定義時就考慮到所有可能的業務流程，并完整精確地將流程模型中的每個細節都清晰地制定出來是極為困難的，因此傳統的工作流技術已不能滿足企業對日益增長的內外部資源的統一利用和企業間相互協作的迫切需求。而基于數據驅動的分布式工作流可有效克服傳統的工作流的局限性，從而能很好地對業務工作進行建模，具有良好的可擴展性及互操作性，實現自適應的任務調度，動態細化具體的執行路徑，帶來更強的柔性和可靠性。

2 ? ? ?數據驅動的分布式工作流模型

基于Petri網流程模型[5]，通過結合控制流和數據流建模與分析，引入工作流版本信息、業務流程圖、流程任務信息及優化彈簧算法，提出一種基于數據驅動的柔性分布式工作流自適應任務調度方法，實現工作流的可擴展性、柔韌性、動態性及自適應性，以適應大吞吐量要求的高性能及實現處理復雜業務流程的能力。

2.1 ? 工作流版本信息

工作流版本信息是服務單流程信息中一個簡化的數據集，可描述為：

F=（F_ID，FD，L）（1）

其中，F_ID是當前工作流版本號;FD是服務單數據子集，包括服務單ID和服務單當前狀態;L是業務流程，代表工作流任務及事件的邏輯關系，其是由事件和任務及其相關關系組成的有向無環圖，表示流程實例的執行方向;流程實例中的工作流程版本信息F包含業務流程L及流程實例狀態數據。

2.2 ? 工作流版本信息

工作流約束指的是在工作流定義時必須滿足且在運行及變更時也必須滿足的規則。為確保業務流程按給定的方向流轉和業務流程自適應調整時版本正確的決策及系統的穩定，防止業務流程進入死循環和出現未知的執行結果，業務流程需滿足相關約束。

（1）版本約束。任意流程實例在某一給定的時刻僅允許按照某一特定的流程執行。

（2）隔離約束。任意流程實例的執行都必須互相獨立，互不影響，流程實例對應的服務單據間沒有直接的訪問聯系。

（3）更新約束。不允許出現任務事件沖突、任務順序沖突和流程方向沖突，若出現則將禁止本次流程中的任務調度。任務事件沖突指的是兩個任務由一個事件引發或一個事件可有兩個任務相對應;任務順序沖突指的是某一任務的前序任務也是其后序任務，導致出現回路;流程方向沖突指的是存在路徑到達某一中間事件，但卻終止于該中間事件，導致該事件的后序任務無法執行。

2.3 ? 任務調整策略

任務調節策略使用的是優化的彈簧算法。彈簧算法的思想是通過將系統中的每一個任務負載當成一根單獨的彈簧，將系統中的任務集當作具有前后續關聯的彈簧集，通過對每根彈簧的彈性系數進行調整來實時反映每個任務的負載變化，進而實現對整個系統任務負載調節。

記實時任務T=（D，Zmin，Zmax，Q，Vmin，Vmax），其中D表示任務到達時間，Zmin表示任務最小的執行時間，Zmax表示任務最大的執行時間，Q表示任務的截止時間，Vmin表示任務最小到達時間間隔，Vmax表示任務最大到達時間間隔。其中任務必須要在到達時間D之后的截止時間Q內完成，任務負載W=Z/V，其取值范圍為W∈[Wmin，Wmax]，其中Wmin=Zmin/Vmax，Wmax=Zmax/Vmin。則單個任務的負載調整策略為：

Ci=Ci0-（Cv0+Cf-Cq）■（2）

其中，Ci為任務Ti調節前的負載值，Ci0為任務Ti調節后的負載值，Cv0表示所有可調節任務的負載值之和，Cf表示所有不可調節任務的負載值之和，Cq為期望調節負載值，Ev為所有可調節任務的彈性系數之和，其任務的彈性系數為Ei=max■

2.4 ? 任務分配策略

負載平衡調度方法是一種解決流程引擎負載過重的調度方法，通過在以數據驅動的分布式工作流中引進彈簧算法調整策略，假定每個任務結點都是動態產生的，本任務分配策略僅考慮動態負載平衡調度，對工作流中的任務進行分配時，考慮所有的流程引擎資源，且只有當某一任務完全執行成功后方能去調整流程狀態，當某一任務的絕對最早開始時間和絕對最晚開始時間確定時，則僅考慮能為此任務提供最小執行時間的流程引擎，而當任務被分配到指定的流程引擎時，則其執行時間和傳輸時間也同步進行更新。

如果任務調度時的絕對最早開始時間和絕對最晚開始時間相等，則該任務處于流程的關鍵路徑上，且在每次任務分配時，將關鍵路徑上的任務按絕對最早開始時間從小到大進行順序選擇，在確定了關鍵路徑上的關鍵任務后，檢查流程引擎上任務負載狀態與其他狀態的信息是否一致。若一致，則選擇能為該任務提供最小執行時間的流程引擎來執行該任務;若不一致，則把該任務送到負載指數最小的臨近任務中，根據工作流版本信息和流程任務信息，按任務執行時間和負載信息根據彈簧算法對任務進行重新計算，并根據最優路徑對任務調整。

2.5 ? 任務調度策略

基于數據驅動的分布式工作流對當前的活動、事件及狀態相關參數進行處理，當任務及事件分配到特定的流程引擎后，流程引擎根據工作流版本信息和優化彈簧算法進行任務調度，在該負載均衡調度算法中，任務的權重和優先級是動態調整和變更的，系統中的任務和事件在任意時刻按其截止時間從早到晚進行順序排列，版本信息越新和任務截止時間越早，則優先級越高，反之則越低。流程引擎在任務調度時，會對滿足條件的任務進行動態排序，并選擇具有最早截止時間的任務及事件進行調度。

3 ? ? ?結 ? ?語

實時任務調度是保證系統實時處理的關鍵，而處理實時任務工作流兼顧分布式和實時性等特點，為提升系統的吞吐量和相應時間，本文對在分布式工作流研究的基礎上，通過基于數據驅動，引入流程版本信息和優化彈簧算法對任務進行動態負載均衡調度，提出了一種數據驅動的柔性分布式工作流自適應任務調度方法，以支持工作流中的任務動態自適應調整以使系統更好地適應環境、優化流程、提高效率。

主要參考文獻

[1]Nathanid Palmer.Workflow Management Coalition[M].NewYork，NY：Springer，2016.

[2]李競杰，王維平，楊峰. 柔性工作流理論方法綜述[J]. 計算機集成制造系統，2010，16（8）： 1569-1577.

[3]譚宜甬，王銳，范玉順，等. 分布式工作流中的自適應實時任務調度方法[J] . 計算機集成制造系統， 2010， 16（9）： 1887-1895.

[4]李帥，于守健. 以數據為中心的業務流程變更自適應技術研究[J]. 智能計算機與應用， 2016， 6（1）： 36-43.

[5]袁崇義. Petri網原理與應用[M]. 北京：電子工業出版社， 2005： 58-62.