第10期 颉斌等：基于模板的服务工作流的优化组合方法 ·1215· 确定和分布式等特点的系统进行图形化数学建模和 模板1 模板2 分析的工具，它注重表示系统的状态转换以及状态 转换关系，因此能够很好地描述系统的动态变化特 性.同时，WMC所定义的六种工作流原语都能很 oioioioio 好地映射成Petri网的表达形式，所以本文选用Petri 网对服务工作流进行建模分析.Petri网D-可以描 述成一个三元组PN=(P,T,F).其中：P={P, P2,…,Pn},是有穷位置集合；T={t1,2…,tm}, ololo1o1o 是有穷变迁集合；PnT≠O(二元性)；PUT≠O(网 图2任务回滚优化 非空)：FC(P×T)U(T×P),是弧的集合（弧仅在 Fig.2 Optimization of task rollback 于P与T的元素之间)；dom(F)Ucod(F)=PUT (没有孤立元素). 赖关系（见定义1）且模板的Rs相同的服务工作流 用Petri网的位置表示工作流任务发生的条件， 模板进行合并，这样可以节省任务交接的时间和成 用变迁表示任务的执行，用标识表示工作流实例，这 本，用Petri网表示如图3所示. 样就能够使用Petri网对服务工作流进行建模. 模板1模板2 下面，借助于基于Petri网的服务工作流模型， 对基于模板的服务工作流的优化组合算法进行介 绍，其具体步骤如下 12 (1)查看服务工作流模板集中各个模板 图3服务工作流模板合并 WFTemplate的服务集ServiceSet是否有相同的服 Fig.3 Mergence of the service workflow template 务，如有则合并.这样可以保证整个服务工作流的 一致性及防止某一服务在工作流中多次重复出 (4)查询当前网络服务状态，对于不存在输入/ 现，提高服务工作流的执行效率，用Petri网表示如 输出依赖关系（见定义2）且不存在资源依赖关系 图1. (见定义3和定义4)的服务工作流模板，并行执行 以节省执行时间，用Petri网表示如图4所示. 模板1 模板2 oioioioio 模板1模板2 Tv-1 图4服务工作流模板并行 Fig.4 Parallelization of the service workflow template 图1相同服务合并 Fig.I Mergence of the same services (5)在服务工作流执行任务过程中，扫描任务 定义，判断任务能否进行拆分回.如果能拆分，则根 (2)查看服务工作流模板集中各个模板是否含 据任务拆分服务工作流模板.若模板拆分所得的分 有任务回滚.任务回滚是指当任务的输入不正确导 支之间不存在输入/输出依赖关系且不存在资源依 致任务无法向下执行的情况，这样就需要回滚到输 赖关系，则并行执行这些模板分支以节省时间，用 入环节，返回执行前的状态.对于这种情况，任务不 Petri网表示如图5所示. 应仅仅回滚到本模板的输入环节，而是需要回滚到 (6)服务工作流执行过程中反复执行(1)~ 上一模板的执行环节，这样才能纠正上一模板的输 (5),直至服务工作流执行结束 出错误，也就能保证本模板输入的正确性，从而防止 总的来看，经过上述方法优化后，服务工作流的 自动生成的服务工作流执行时陷入死循环，用Petri 结构更为合理.下文将以制作网络流媒体课件服务 网表示如图2所示. 工作流为例来说明基于模板的服务工作流的优化组 (3)查询当前网络服务状态，对于存在输入依 合算法的有效性.第 10 期 颉 斌等: 基于模板的服务工作流的优化组合方法 确定和分布式等特点的系统进行图形化数学建模和 分析的工具，它注重表示系统的状态转换以及状态 转换关系，因此能够很好地描述系统的动态变化特 性． 同时，WfMC 所定义的六种工作流原语都能很 好地映射成 Petri 网的表达形式，所以本文选用 Petri 网对服务工作流进行建模分析． Petri 网［7--8］可以描 述成一个三元组 PN = ( P，T，F) ． 其中: P = { p1， p2，…，pm } ，是有穷位置集合; T = { t1，t2，…，tm } ， 是有穷变迁集合; P∩T≠$( 二元性) ; P∪T≠$( 网 非空) ; F( P × T) ∪( T × P) ，是弧的集合( 弧仅在 于 P 与 T 的元素之间) ; dom( F) ∪cod( F) = P∪T ( 没有孤立元素) ． 用 Petri 网的位置表示工作流任务发生的条件， 用变迁表示任务的执行，用标识表示工作流实例，这 样就能够使用 Petri 网对服务工作流进行建模． 下面，借助于基于 Petri 网的服务工作流模型， 对基于模板的服务工作流的优化组合算法进行介 绍，其具体步骤如下． ( 1) 查看服务工作流模板集中各个模板 WFTemplate的服 务 集 ServiceSet 是否有相同的服 务，如有则合并． 这样可以保证整个服务工作流的 一致性及防止某一服务在工作流中多次重复出 现，提高服务工作流的执行效率，用 Petri 网表示如 图 1． 图 1 相同服务合并 Fig． 1 Mergence of the same services ( 2) 查看服务工作流模板集中各个模板是否含 有任务回滚． 任务回滚是指当任务的输入不正确导 致任务无法向下执行的情况，这样就需要回滚到输 入环节，返回执行前的状态． 对于这种情况，任务不 应仅仅回滚到本模板的输入环节，而是需要回滚到 上一模板的执行环节，这样才能纠正上一模板的输 出错误，也就能保证本模板输入的正确性，从而防止 自动生成的服务工作流执行时陷入死循环，用 Petri 网表示如图 2 所示． ( 3) 查询当前网络服务状态，对于存在输入依 图 2 任务回滚优化 Fig． 2 Optimization of task rollback 赖关系( 见定义 1) 且模板的 Res 相同的服务工作流 模板进行合并，这样可以节省任务交接的时间和成 本，用 Petri 网表示如图 3 所示． 图 3 服务工作流模板合并 Fig． 3 Mergence of the service workflow template ( 4) 查询当前网络服务状态，对于不存在输入/ 输出依赖关系( 见定义 2) 且不存在资源依赖关系 ( 见定义 3 和定义 4) 的服务工作流模板，并行执行 以节省执行时间，用 Petri 网表示如图 4 所示． 图 4 服务工作流模板并行 Fig． 4 Parallelization of the service workflow template ( 5) 在服务工作流执行任务过程中，扫描任务 定义，判断任务能否进行拆分［9］． 如果能拆分，则根 据任务拆分服务工作流模板． 若模板拆分所得的分 支之间不存在输入/输出依赖关系且不存在资源依 赖关系，则并行执行这些模板分支以节省时间，用 Petri 网表示如图 5 所示． ( 6) 服务工作流执行过程中反复执行( 1) ～ ( 5) ，直至服务工作流执行结束． 总的来看，经过上述方法优化后，服务工作流的 结构更为合理． 下文将以制作网络流媒体课件服务 工作流为例来说明基于模板的服务工作流的优化组 合算法的有效性． ·1215·