数据驱动的分布式工作流中的任务调度方法

许广繁

[摘    要] 为使工作流中的任务能根据内外部因素的变化进行自适应调度，在分布式工作流模型的基础上，通过基于数据驱动，引入流程版本信息和优化弹簧算法对工作流中的任务进行动态负载平衡调度，提出了一种数据驱动的柔性分布式工作流自适应任务调度方法，以支持工作流中的任务动态自适应调整，以使系统更好地适应环境、优化流程、提高效率。

[关键词] 分布式工作流;任务调度;数据驱动;自适应调度

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.