基于面向对象Petri-net的LWF建模方法

郑学恩, 许承东, 范国超, 赵 靖

(北京理工大学宇航学院, 北京 100081)

0 引 言

在20世纪90年代,事件流程管理成为计算机行业研究的热点之一。在软件工程邻域中,工作流管理系统的建立,使事件流程管理和程序自动化运行成为可能[1-2]。比较成功的工作流管理系统应用实例是荷兰国家税务局的Sagitta2000申报处理系统[3]。此项目在设计中将应用软件与事件逻辑成功分离,单独设计了工作流系统,以解决海关申报流程难以描述的问题。此后,研究人员针对工作流的死锁、活锁及合理性[4]进行了诸多改进,文献[5]提出工作流化简规则,来避免工作流出现死锁状态;文献[6]在工作流中加入时间特性,拒绝使用环形流程,以避免工作流出现活锁状态;文献[7-8]对工作流进行分块设计和分层设计,提高工作流的容错性和执行效率;文献[9]提出循环工作流优化方法,该方法改变原有工作流的结构,尽量减少环形工作流(loop workflow,LWF),避免因LWF造成的活锁。但诸如上述方法,其根本都是减少LWF的使用,以提高工作流程的安全性。

弹箭产品设计是典型的复杂系统工程,它由若干子系统组成,子系统之间存在着通信、继承、调用关系。每个子系统设计完成后,需要将方案汇总,进行方案评审。由于产品设计过程复杂,通常要经过3～5次的迭代设计，产品的各项性能才能满足技术指标。弹箭产品设计工作流程是事件迭代的过程,描述设计流程的工作流需要使用环形结构。通常情况下,基于公平性假设的环形结构是安全的,但产品设计工作流中,基于“评审”结果的任务选择已经不再满足公平性假设,这样的工作流程增加了模型陷入活锁状态的风险,为了避免设计工作流进入活锁状态,有必要设计一种扩展工作流网(expanded workflow network, EWF-net),对弹箭产品设计工作流程进行正确建模。

针对设计工作流的活锁问题,本文提出了基于面向对象Petri网(object-oriented petri-net, OPN)的EWF-net,它具有跃迁和虚拟托肯(虚托)2个重要标志。跃迁和虚托的联合使用,能够使陷入活锁的LWF跳出环形结构,从而避免了活锁的发生。为了正确表达工作流中虚托的状态,本文给出了描述虚托的标识方法,并对线性代数的可达性分析方法进行了扩展,使其能够对拥有虚托的工作流进行可达性分析。最后,以弹箭设计工作为背景,分别用传统工作流网 (workflow network, WF-net) 和EWF-net 2种方法对弹箭设计工作流进行建模,在活锁状态下对2个模型进行了可达性分析,分析的结果表明本文所提的EWF-net方法能够避免活锁,解决因非公平性假导致的活锁问题。

1 基础知识

1.1 OPN

Petri网反映事物之间的依赖关系,是一种描述事件分步、并发和异步的图形工具[10]。为了描述复杂系统工程中子系统之间的关系,面向对象技术与Petri-Net相结合[11-13],扩展成为OPN。它具有继承性。子类网可以通过继承,对父类网进行调用。这种继承性的应用,一定程度上避免Petri网出现状态空间爆炸的情况。

定义1OPN定义。N=(O,T;F,M)的四元组构成了网结构,其中:

(1)O={O1,O2,…Oi}是对象的有限集,对象用来描述系统的状态,i>0为对象的个数。

(2)T={T1,T2,…,Tn}是变迁的有限集,变迁用来描述系统的行为,n>0为变迁的个数。

(3)F代表对象与变迁之间的关系,F⊆O×T∪T×O。

(4)M0是网系统的初始状态标识。

定义2继承性定义。对象O1继承于对象O2的充分必要条件是:

(1)O1≠O2∧O1∈R(O)∧O2∈R(O),R(O)表示对象的全体集。继承关系的2个对象都属于全体类集,且对象O1不能自我继承。

(2) ∀O1,∃O1⟹O2⟹…⟹Ox,L(O1)={O2,O3,…,Ox},O1∉L(O1)。L(O1)表示对象O1的父类集。对象O1不能通过连续的继承,成为自身的父类。

图1描述O1与O2的继承关系及O2调用O1的过程。对象O2继承于对象O1,表示为在对象O2中可以通过托肯调用对象O1。

图1 对象的继承Fig.1 Inheritance of objects

1.2 工作流网

工作流描述了工作流程的逻辑关系。使用Petri网这种过程形式化体系对工作流建模和分析,避免工作流出现模糊性、不确定性和矛盾性。Aalst提出的工作流网是建立在Petri网的基础上的。

定义3WF-net定义。传统Petri网被称为WF-net的充要条件是:

(1) 存在一个源库所Pi∈P,使得·Pi=∅;

(2) 存在一个终止库所Po∈P,使得Po·∈∅;

(3) 每个节点x∈P∪T都位于从Pi到Po的路径上。

在基于OPN的WF-net中,条件对应Petri网中的对象,任务对应Petri网中的变迁。

2 EWF-net

2.1 非公平性LWF

定义4LWF定义。在工作流中,如果某个任务被反复执行,直到满足其后面的“要求”结果为止,称为LWF。

在工作流网中,LWF的安全性建立在公平性假设的基础上。公平性假设认为如果一个任务有可能被执行,就不会无限期地推迟[14]。LWF只在原则上可能无限地循环,因为一个任务有可能被执行,就不会让这个任务永远地“饥饿”。但在设计工作中,如果设计结果无法满足设计指标,LWF不可能在不满足设计指标的情况下,提交设计结果,因此设计工作流模型有可能陷入活锁,无法进行下一步设计。为了解决上述问题,下面给出EWF-net的定义。

2.2 EWF-net的定义

定义5EWF-net定义。EN=(P,T,O;F,OI,OO,TI,TO,W,M)称为EWF-net的充分必要条件是:

(1)P≠Φ,T≠Φ,T∩P=Φ,F=P×T∪T×P∪T×O∪O×T,其中P表示条件,T表示任务,O表示对象,F表示他们之间的关系,其中P、T和O都是有限集。

(2) OI表示对象的源节点,OO表示对象的汇节点,·OI≠∅,OO·≠∅。

(3) TI表示任务输入,TO表示任务输出。

(4)W:F→N,W为权函数,将关系F映射到一个自然数。

(5)M是网的标识,M0为初始标识。

(6) 存在一个源节点Pi∈P,使得·Pi=∅;

(7) 存在一个汇节点Po∈P,使得Po·=∅;

(8) 每个节点a∈P∪T,都位于从Pi到Po的路径上,没有孤立节点。

基于OPN和WF-net的EWF-net,具有继承性和描述工作流的能力,适合用于复杂系统的工作流建模。为了解决LWF的活锁问题,EWF-net引入了跃迁的状态转移规则。

2.3 跃迁的定义

定义6跃迁定义。在EWF-net中,如果任务输出TO具有计数能力,且计数的上限值为n,且n∈N,则称该TO为跃迁,记为TOn,计数的上限值n为迭代数。

当标记了跃迁的任务T被执行一次,条件TOn·增加一个虚托用来记录任务T被执行的次数,当T的执行次数等于迭代数n时,TOn被执行,结束LWF程。每个任务中只能存在一个跃迁,原则上如果任务序列足够长,跃迁一定会被执行。图2描述了EWF-net的跃迁。

图2 EWF-net跃迁示意图Fig.2 Schematic diagram of EWF-net jump-turning

2.4 虚托的定义

定义7虚托定义。在EWF-net中,当标记了跃迁的任务被执行一次后,没有得到托肯的条件P(即TOn·)将得到一个虚托,用符号“○”表示。在标识中表示为M(P)=1/n,n∈N,P∈P。标识中自然数n表示生成虚托的上限值。

虚托具有以下2点性质:

(1) 虚托不代表资源;

(2) 虚托不能触发任务。

定理1虚托触发定理。n∈N,虚托在标识中表示为M(P)=1/n,则∀P∈·T,任务T触发的充要条件是条件P的虚托数m等于虚托上限值n。

证明(必要性):假设m为条件P获得的虚托数,∀m∈N。当库所获得m个虚托后,根据定义6可知,M(P)=1/n1+1/n2+…+1/nm,当m=n时,M(P)=1,即M[T>。

(充分性):假设变迁T被触发时的状态标识M(P)=1,式中P∈·T。根据定义6可知,M(P)=1/n1+1/n2+…+1/nm,且M(P)=1,能够推导出m=n,即虚托数m等于迭代次数n。

证毕

图3描述了跃迁和虚托跳出活锁的工作流程。如图3(a)所示,条件P1触发任务T1执行,经过任务T1的选择,托肯经由任务输出TO1回到条件P1,P1再次触发任务T1,当任务T1无法选择TO2时,模型将不断重复由任务输出TO1到条件P1的流程。无限循环的任务流程为σ=TO1…TO1…。在图3(b)中,使用跃迁TO13取代TO2,每次T1执行后,跃迁指定的条件P2会得到一个虚托。图3(b)和图3(c)给出了虚拟托肯的状态标识。当P2得到的虚托个数达到迭代数3时,托肯将会通过跃迁TO13到达P2。如图3(d)所示,此时活锁状态结束,LWF运行了3次。

2.5 EWF-net可达性分析方法

传统可达性分析方法,无法描述虚托的状态标识。为了描述WF-net存在虚托时的状态,需要构建适用于EWF-net的关联矩阵和状态方程。

图3 LWF中虚托的状态标识图Fig.3 State identification of virtual-token in LWF

称A为EN的关联矩阵。

给出EWF-net系统的状态方程，即

M=M0+A×U+B

式中,U为发生数向量;B为虚托状态标识。U中一个位置的值对应网模型中的一个任务(或对象O)在变迁序列中出现的次数。如果任务有跃迁,在向量U中会有2个位置分别对应该任务的输出量和跃迁。B=B1+B2+…+Bm-k是描述虚托状态标识的方程,由m-k个向量组成,每个向量对应一个跃迁。Bi的维度与M相同,每个位置对应一个条件，或者对象O的源节点和汇节点。向量B的构建方法如下:

准备将模型中的跃迁添加到向量组C中,C中含有组元m-k个,每个组元用C[i]表示,i的初始值为1。

步骤1与C[i]同属一个任务T的任务输出记为Vi;

步骤2在任务序列σ(有限序列)中,逆序查找C[i]。

步骤3当第1次查找到C[i]后,计算从此位置到任务序列结束这一段中,Vi出现的次数,记为yi。如果序列中没有出现C[i],那么计算整个序列σ中Vi出现的次数,同样记为yi。

步骤4在向量Bi中,C[i]·所对应的条件位置的值设为yi/mi,其他位置设为0,式中mi对应跃迁C[i]的迭代数。

步骤5如果i=m-k,完成向量B构建,否则i=i++,返回步骤1。

根据工作流的任务序列,建立模型的状态方程用于计算工作流的可达状态。通常情况下,模型的可达性分析按以下步骤进行[15]:

步骤1构建关联矩阵;

步骤2给出工作流的任务序列;

步骤3构建状态方程;

步骤4工作流可达性计算。

用于网模型可达性分析的任务序列应该具有普遍性,它需要满足以下要求:

(1) 任务序列应该由源节点Pi开始,以汇节点Po结束;

(2) 在任务序列中网中每个任务都至少被执行一次,确保网中没有不起作用的任务。

跃迁和虚托的引入,为解决LWF活锁问题提供一种新方法。下面以弹箭设计工作流程为例,分别利用WF-net和EWF-net两种方法为弹箭设计建立工作流模型,并进行可达性对比分析。

3 弹箭设计工作流建模及分析

弹箭产品设计工作是权衡和迭代的过程。产品的设计

流程复杂,需要清晰的工作流程图描述设计工作的逻辑关系。在工程中,通常以单向网络流图描述产品的研发周期。这种方法适用于描述设计工作的时间节点,并不适合描述工作之间的逻辑关系,也无法与软件结合,应用在弹箭设计平台中。在软件程序设计中,EWF-net建立的工作流模型描述工作事件的逻辑关系更清晰、更严谨,也更适合与应用程序和数据库之间进行交互通信,将物理进程与计算机程序连接[16]。

3.1 弹箭数字化设计平台

弹箭数字化设计平台集成多种设计资源,是弹箭产品建模及分析的设计软件。它将弹箭产品设计工作划分为4个子模块,子模块之间是相互联系与制约的关系。弹箭设计工作流作为设计工作调度的核心,描述各子系统之间的数据交互流程,将设计流程的逻辑关系可视化。在弹箭数字化设计平台中,工作流是产品数字化设计工作能够顺利进行的保障[17]。系统在调度数据时,将按照工作流的逻辑关系进行。

图4描述了弹箭数字化设计平台的总体结构:资源层、通信层、功能层和服务层。功能层包括工作流系统、应用程序系统和数据库系统,是实现设计平台主要功能的核心层。在功能层内部,工作流系统、应用程序系统与数据库系统之间互相通信,形成环状结构。工作流系统主要的功能是管理工作流模型,安排产品设计工作的逻辑关系;数据库系统负责存储和管理工作流系统与应用程序系统产生的数据;应用程序系统负责定义算法模块,根据工作流系统建立的逻辑关系,处理任务。3个系统的联合运行实现弹箭设计工作流程化和自动化。

图4 弹箭数字化设计平台结构图Fig.4 Structure map of the missile digital design platform

3.2 弹箭设计工作流建模及可达性分析

在方案阶段设计中,设计平台将弹箭产品设计工作划分为弹体模块、战斗部模块、动力模块和控制模块。图5展示了利用WF-net建立的工作流模型,它使用OR-split结构对评审事件进行建模。当设计结果没有达到设计指标时,工作流将进行下一次的迭代设计;当设计结果满足设计指标后,工作流将结束设计工作。图6展示了利用EWF-net建立的工作流模型,它使用跃迁对评审事件进行建模。

图5 基于WF-net的弹箭产品设计工作流模型Fig.5 Workflow model for missile design based on WF-net

图6 基于EWF-net的弹箭产品设计工作流模型Fig.6 Workflow model for missile design based on EWF-net

表1分别介绍了2个模型中变迁所对应的工作事件。

表1 工作流中任务对应的工程事件

以图5的工作流模型为例,当状态M0(Pi)=1时,工作流系统开始运行,首先任务T1被触发,下达研制任务。当节点OI1得到托肯后,O1运行,完成弹箭总体的设计工作。O1结束后将托肯传递给汇节点OO1。∃M∈R(M0),M(OO1)≥1→M[T2>,任务T2将托肯传递给条件P1和源节点OI2,OI3和OI4。条件P1表示弹体系统设计已经完成,等待反馈迭代被触发。另外3个模块O2、O3、O4的源节点得到托肯后,将分别触发各自的模块进入工作状态。∃M∈R(M0),M(OO2)≥1→M[T3>,任务T3将托肯传递给条件P1,战斗部系统设计工作完成,等待反馈迭代被触发。T4、T5具有相同的作用,当动力系统和控制系统被设计完成后,托肯将进入条件P1,等待进行弹箭迭代设计被执行。条件P1得到4个系统反馈的托肯后,根据评审结果触发T6或T7中的一个,选择的依据是设计结果能否满足设计指标。这种选择依据不再满足公平性假设,增加了工作流陷入活锁风险。如果设计指标一直没有达到,工作流将进入活锁状态。利用线性代数的方法对图5的工作流模型进行可达性分析。首先,建立工作流的关联矩阵为

AWF-net=

给出活锁状态的任务序列，即

式中,n∈∞;σWF-net是变迁的多重集。UWF-net是σWF-net的重数,即

给出系统初始状态为

应用状态方程，即

M=M0+AWF-net×UWF-net

求解弹箭产品设计工作流的终止状态为

结果表明托肯无法达到Po,工作流处在活锁状态,弹箭数字化设计平台不能为用户输出一个设计结果。

利用EWF-net建立的弹箭设计工作流模型如图6所示,任务T6的输出TO6表示设计结果没有满足设计指标,需要开始下一轮迭代设计;TO63表示设计结果满足研制任务要求,通过评审,托肯传递给汇节点Po。引入跃迁后,任务T6被执行的次数达到迭代数3的上限时,将会触发跃迁TO63,结束设计工作。他的工程意义表现为现有的设计手段和方法,无法满足预定的技术指标。假设设计结果一直无法满足设计指标,根据虚托触发定理得到的任务序列为

σEWF-net=T1,O1,T2,O2,T3,O3,T4,O4,T5,TO6,

O1,T2,O2,T3,O3,T4,O4,T5,TO6,O1,T2,

O2,T3,O3,T4,O4,T5,TO63

根据图6的工作流模型建立关联矩阵为

AEWF-net=

T1T2T3T4T5TO6TO63O1O2O3O4

根据给出的任务序列求得σEWF-net的重数，即

给出系统初始状态为

计算标识虚托的状态向量为

应用状态方程，即

M=M0+AEWF-net×UEWF-net+B

求解弹箭产品设计工作流系统的终止状态为

状态方程的计算结果表明，利用EWF-net构建的弹箭产品设计工作流能够避免活锁,使汇节点Po具有可达性,在任务序列结束后,除Po外其他条件中没有托肯。这个结果表明系统描述的工作流可以正常运行。

4 结 论

产品设计自动化一直是科研设计部门提高设计能力的一个发展方向。弹箭设计平台集成了知识、经验和方法等设计要素,利用工作流模型实现产品设计任务的自动调度。工作流模型是设计自动化的核心部分，对设计工作流的安全性提出高标准的需求。本文为解决设计工作流模型的活锁问题,提出了EWF-net建模方法,该方法依靠跃迁和虚托的状态转移规则,避免WF-net陷入活锁状态。在弹箭设计工作流建模实例中,将传统WF-net方法和EWF-net方法进行了对比分析,结果表明EWF-net方法能够使汇节点可达。

参考文献：

[1] MAYER B, KILLIAN M, KOZEK M. Modeling workflow for a building model for control purposes[C]∥Proc.of the IEEE International Conference on Systems and Control,2013:551-556.

[2] WINKLER D, SCHOENBAUER M, BIFFL S. Towards automated process and workflow management: a feasibility study on tool-supported and automated engineering process modeling approaches[C]∥Proc.of the 40th Euromicro Conference on Software Engineering and Advanced Applications, 2014: 102-110.

[3] VAN DER AALST W, VAN HEE K. Workflow management models,methods,and systems[M].London:MIT Press,2002.

[4] YAMAGUCHI S, WU H. Protocol inheritance preserving soundizability problem and its polynomial time procedure for acyclic free choice workflow nets[J]. IEICE Trans.on Information and Systems, 2014, 97(5): 1181-1187.

[5] ZHAO W, YUAN C Y, LIU G, et al. Workflow process model verification using reduction method based on P/T System[J]. Journal of Software, 2004, 15(10): 1423-1430.

[6] CICIRELLI F, FURFARO A, NIGRO L. Using time stream Petri-nets for workflow modelling analysis and enactment[J]. Simulation, 2013, 89(1): 68-86.

[7] RUTLE A, WANG H, MACCAULL W. A formal diagrammatic approach to compensable workflow modelling[C]∥Proc.of the 2nd International Symposium foundations of Health Information Engineering and Systems, 2013: 194-212.

[8] NAZARLOU M M. Research on application of hierarchy Petri-net in dynamic workflow modeling[J].Life Science Journal-Acta Zhengzhou University Overseas Edition,2013,10(1):821-825.

[9] CHOI Y S, KONGSUWAN P, JOO C M, et al. Stepwise structural verification of cyclic workflow models with acyclic decomposition and reduction of loops[J]. Data & Knowledge Engineering, 2015, 95: 39-65.

[10] MURATA T. Petri nets: properties, analysis and applications[J]. Proceedings of the IEEE, 1989, 77(4): 541-580.

[11] 朱锦泉, 苑森淼. 支持动态修改的可适应工作流模型[J]. 兵工学报, 2004, 25(5): 649-652.

ZHU J Q, YUAN S M. An adaptive workflow model supporting dynamic modification[J].Acta Armamentarii,2004,25(5): 649-652.

[12] RIBAS M, FURTADO C G, SOUZA J N D, et al. A Petri net-based decision-making framework for assessing cloud services adoption: the use of spot instances for cost reduction[J]. Journal of Network & Computer Applications, 2015, 57(C):102-118.

[13] 徐剑,叶文华,杨斌,等.基于扩展Petri网的飞机装配线建模及平衡方法[J].计算机集成制造系统,2015,21(10):2596-2603.

XU J, YE W H, YANG B, et al. Assembly line modeling and balancing of aircraft based on extended Petri-net[J]. Computer Integrated Manufacturing Systems,2015,21(10):2596-2603.

[14] TIPLEA F L, LEAHU I. The reversible released form of Petri nets and its applications to soundness of workflow nets[J]. IEEE Trans.on Systems, Man and Cybernetics: Systems, 2014, 46(2): 303-304.

[15] 许玉堂,殷永峰,孙静,等.基于时间扩展Petri网的实时嵌入式软件体系结构建模及可靠性评估[J].兵工学报,2015,36(2): 363-373.

XU Y T, YIN Y F, SUN J, et al. Real-time embedded software architecture modeling and reliability estimation based on time-extended Petri-net[J].Acta Armamentarii,2015,36(2): 363-373.

[16] 鲁法明, 曾庆田, 段华, 等. Petri网不可达标识的判定方法研究及其在死锁检测中的应用[J]. 计算机集成制造系统, 2016, 22(2): 465-475.

LU F M, ZENG Q T, DUAN H, et al. Decidability method of Petri-net non-reachability marks and its application in deadlock detection[J]. Computer Integrated Manufacturing Systems, 2016, 22(2): 465-475.

[17] LEVI M, PASHA P, HENRY P, et al. Small spacecraft software modeling: a petri net-based approach[J]. Journal of Aerospace Information Systems, 2014, 11(10): 679-690.