基于逻辑工作流网的有限无死锁组合

陈金栋，刘 伟，冯 新，刘 雷

（山东科技大学 计算机科学与工程学院，山东 青岛266590）

随着科学技术的发展，单一的流程往往不够灵活，难以满足人们的需求［1］，流程组合应运而生。流程组合体现在各个方面，例如因特网中双主机的信息传输过程组合，电子商务中买卖双方过程组合等［2］。流程组合可以协调多个目标的操作过程，并使其各自完成自己的任务［3］。但是，流程组合中出现的死锁是流程组合发展的障碍［4］。

Petri网是分布式系统的建模和分析工具。作为一种系统模型，Petri网既能描述系统的结构，又能描述系统的动态行为［5-8］。随着Petri网的广泛应用，目前已经提出逻辑Petri网［9］、时间Petri网［10］、颜色Petri网［11］和模糊Petri网［12］等扩展形式。逻辑Petri网是抑止弧Petri网和高级Petri网的抽象与扩展，其变迁的输入、输出受逻辑表达式的限制。与一般Petri网相比，逻辑Petri网能够更好地描述实时协同工作系统模型的网结构，便于系统设计人员掌握和使用［13］。

目前，基于Petri网的死锁与组合研究已经有了许多成果，但是较少使用逻辑Petri网来处理无死锁组合的工作。文献［14］使用了有色Petri网对服务组合系统行为进行验证。文献［15］提出了一种过渡控制方法，通过添加过渡来处理死锁。文献［16］展示了如何在消息位置的边界处将并行程序的整个Petri网模型拆分为进程网，以及如何将其用于死锁分析。文献［17］专注于防止资源不可靠的自动化制造系统的死锁。

本研究在相关研究的基础上，借助逻辑工作流网，建模具有批处理和传值不确定性的系统，提出了逻辑工作流网有限组合和状态转换图的概念。用状态转换图描述逻辑工作流网的活动序列，并用来进行组合，然后提出了状态映射和状态赋值用于判断死锁，之后提出了有限标准伙伴状态转换图的概念与计算方法，以描述无死锁组合允许的逻辑活动序列。最后使用一个电子商务实例说明了使用有限规范伙伴状态转换图判断有限组合死锁的方法。

1 基本概念

本部分介绍逻辑工作流网概念，定义状态转换图以及从逻辑工作流网到状态转换图的变换。

1.1 逻辑工作流网

定义1［18］（有限多重集） S 是一个集合，其上的多重集c是一个映射c∶S→N，记为c（s）。其中N表示一个自然数集合。C（S）表示集合S 上的所有多重集的集合。如果∀s∈S，c（s）≤g，其中g∈N，那么所有c（s）组成的集合称为g 限多重集，简写为Cg（S）。C0（S）表示一个空的多重集。

定义2［13］（逻辑工作流网） 一个六元组LWN=（P，T，F，I，O，M）称为逻辑工作流网，当且仅当：

1）P 是一个有限库所集，其中有两个互不相交的库所子集PC和PD，P=PC∪PD。PD为数据库所子集，PC为控制库所子集。PI∪PO=PD，其中PI 表示输入库所集，·PI∩PD=Ø；PO 表示输出库所集，PO·∩PD=Ø。

2）T=TC∪TI∪TO是一个有限变迁集，T∪P≠Ø，∀t∈TI∪TO，·t∩t·=Ø，且P，TC，TI和TO两两互不相交，其中：①TC表示T 的普通变迁集；②TI表示T 的逻辑输入变迁集，且∀t∈TI，t的所有输入库所受一个逻辑输入表达式fI的限制；③TO表示T 的逻辑输出变迁集，且∀t∈TO，t的所有输出库所受一个逻辑输入表达式fO的限制。

3）F⊆（P×T）∪（T×P）是一个有限弧集。

4）I是一个逻辑限制输入函数，使对∀t∈TI，I（t）=fI是一个逻辑输入表达式。

5）O 是一个逻辑限制输出函数，使对∀t∈TO，O（t）=fO是一个逻辑输出表达式。

6）M∶P→N 是一个标识函数，∀p∈P，M（p）表示库所p 中的托肯数，其中M0表示初始标识且对∀x∈PD，M0（x）=0。

7）LWN 具有以下的变迁发生规则：①∀t∈TC，若对p∈·t，M（p）＞0，则变迁t可引发，变迁引发后产生一个新标识M′，记做M［t＞M′。对p∈·t，M′（p）=0；对p∈t·，M′（p）=M（p）+1；对p∈·t∩t·：M′（p）=M（p）；②对t∈TI，若I（t）｜M=·T·，则逻辑输入变迁t可引发，记做M［t＞M′，且对p∈·t：M′（p）=0；对p∈t·，M′（p）=1；对p∉·t∪t·：M′（p）=M（p）；③对t∈TO，若对p∈·t，M（p）=0，则逻辑输出变迁t可引发，且对p∈·t：M′（p）=0；对所有p∈·t，需满足O（t）｜M′=·T·，记做M［t＞M′；对p∉·t∪t·：M′（p）=M（p）。

图1是一个简单的逻辑工作流网例子，t1为逻辑输入变迁，I（t1）=p1∧（p2∨p3）是t1的逻辑输入函数，表示t1触发条件是：p1中必须存在托肯，p2和p3中至少有一个存在托肯。t2为逻辑输出变迁，I（t2）=p7∧（p6∨p5）是t2的逻辑输出函数，表示t2引发后会有3种情况：①p7和p5中有托肯；②p7和p6中有托肯；③p7，p6和p5中都有托肯。

定义3（库所变化集） 对于标识M 到M'，数据库所变化集L（M，M′）={x∈PD｜M（x）≠M′（x）}。如果t·∩PD≠Ø，L（M，M′）是输入库所集；如果·t∩PD≠Ø，L（M，M′）是输出库所集。其中L（M，M′）=LI（M，M′）∪LO（M，M′），LI（M，M′）= {x∈L（M，M′）｜M（x）＞0}，LO（M，M′）={x∈L（M，M′）｜M′（x）＞0}。显而易见，从标识M 变化到标识M'过程中，在数据库所集LI（M，M′）中消耗了托肯，在数据库所集LO（M，M′）产生了托肯。

图1 一个简单的逻辑工作流网Fig.1 A simple logical network

定义4（伙伴逻辑工作流网） 对于逻辑工作流网A 和B，A 和B 互为伙伴逻辑工作流网，当且仅当

1）PIA=POB，PIB=POA。

2）A 与B 所有其它成分是不相交的。

如果两个LWN网互为伙伴逻辑工作流网，那么它们可以组合。组合主要包括合并接口位置。

定义5（逻辑工作流网的组合） 设A=（PA，TA，FA，IA，OA，MA）和B=（PB，TB，FB，IB，OB，MB）是伙伴LWN，A 与B 的组合为一个逻辑工作流网A⊗B=（PA⊗B，TA⊗B，FA⊗B，IA⊗B，OA⊗B，MA⊗B），其中PA⊗B=PA∪PB，TA⊗B=TA∪TB，FA⊗B=FA∪FB；IA⊗B=OA⊗B=Ø，MA⊗B=MA⊗MB；MA⊗B0=MA0⊗MB0；MA⊗MB：PA∪PB→N+；如果p∈PA，那么MA⊗B（p）=MA（p）；如果p∈PB，那么MA⊗B（p）=MB（p）。

如果存在g∈N，使得∑MA⊗B（x）≤g，其中x∈PD，MA⊗B可从标识MA⊗B0经过变迁序列到达，那么两个逻辑工作流网的组合称为g 限逻辑工作流网组合。

1.2 状态转换图

本节定义状态转换图用以模拟LWN网的运行，找出所有的状态，并将状态与消息分离讨论。

定义6（消息） PI∪PO 是消息接口库所集，一个消息c为其上的多重集c∶PI∪PO→N，N表示一个自然数集合，记为c（s）。C（PI∪PO）表示集合PI∪PO 上的所有多重集的集合，表示为消息集。如果∀s∈S，C（s）≤g，其中g∈N，那么此时C 称为g 限消息集，记为Cg（S）。

定义7（状态转换图） 状态转换图为一个五元组STN=（S，E，OP，s0，Z，c），其中：

1）S 是一个有限状态集，其中保存LWN中所有可能的状态，在图中表现为顶点集。

2）E 表示一组非确定性的状态转换关系，在图中表现为弧集，E=S×OP×S。

3）OP=OPI∪OPO∪{τ}为有限消息集且OPI∩OPO=Ø，表示状态转换时消息的变化，OPI 中元素为状态转换时接收的多集，OPO 中元素为状态转换时发送的多集，特殊的元素{τ}，表示状态转换时既没有产生也没有消耗消息。OP 在图中表现为弧上的标记。

4）s0∈S，表示唯一的初始状态。

5）Z⊆S，表示终止状态集。

如果状态集S是有限的，那么状态转换图STN 也是有限的。状态转换图对一个全局消息c∈C（∪（OPI∪OPO））进行操作，其中∪Y={x｜x∈y，y∈Y}。初始全局消息一般为空。

对于两个状态转换图STNA=（SA，EA，OPA，s0A，ZA）和STNB=（SB，EB，OPB，s0B，ZB），如果两个状态转换图满足以下条件，那么两个状态转换图互为伙伴状态转换图，简称为两个伙伴状态转换图。有

∪（OPIA∪OPOA）=∪（OPIB∪OPOB）。

与LWN 类似，两个伙伴状态转换图可以组合。

定义8（状态转换图的组合） 对于两个伙伴状态转换图STNA=（SA，EA，OPA，s0A，ZA）与STNB=（SB，EB，OPB，s0B，ZB），其组合被定义为状态转换图STNA⊗STNB=（SA⊗B，EA⊗B，OPA⊗B，s0A⊗B，ZA⊗BØ，其中SA⊗B=SA×SB×C，OPA⊗B= {τ}，EA⊗B=SA⊗B（{τ}×SA⊗B，s0A⊗B=（s0A，s0B，Ø），ZA⊗B=ZA×ZB×Ø，状态转换关系EA⊗B包含以下元素：

（（sA，sB，c），τ，（s′A，sB，c））如果（sA，τ，s′A）∈EA，其中c⊂C（A 的内部移动）；

（（sA，sB，c），τ，（sA，sB，c））如果（sB，τ，s′B）∈EB，其中c⊂C（B 的内部移动）；

（（sA，sB，c），τ，（s′A，sB，c-x））如果（sA，x，s′A）∈EA，其中x∈OPIA，x⊂C 且c⊂C（A 接收一个消息）；

（（sA，sB，c），τ，（sA，s′B，c-x））如果（sB，x，s′B）∈EB，其中x∈OPIB，x⊂C 且c⊂C（B 接收一个消息）；

（（sA，sB，c），τ，（s′A，sB，c+x））如果（sA，x，s′A）∈EA，其中x∈OPOA，c⊂C 且c+x⊂C（A 发送一个消息）；

（（sA，sB，c），τ，（sA，s′B，c+x））如果（sB，x，s′B）∈EB，其中x∈OPOB，c⊂C 且c+x⊂C（B 发送一个消息）。

定义9（等待状态） 对于状态转换图A，状态s是等待状态当且仅当满足∀s′∈S，（s，x，s′）∉E，其中x∈OPO∪{τ}，即s不能在没有消耗消息下离开。对于等待状态s，等待状态集stop（s）={x∈OPI｜∃s′∈S，（s，x，s′）∈E}。

定义10（死锁） 状态s为死锁当且仅当s为等待状态且s∉Z 和stop（s）=Ø。

文中给出的任意逻辑工作流网用A 或者A 的无下标表示，A 的伙伴逻辑工作流网用B 表示。A 的状态转换图用STNA 表示，B 的状态转换图用STNB 表示。STNB 一定为A 的伙伴状态转换图。

STN 单次状态转换只能接收或者发送消息，不能同时接受和发送消息。因此，如果LWN 中有单个变迁同时消耗库所集PI中的托肯和产生库所集PO 中的托肯，需要将此变迁拆分为两个新的变迁：只消耗PD中的托肯和只产生PD中的托肯。如果存在LI（M，M′）≠Ø 且LO（M，M′）≠Ø，其中M［t＞M′，那么变迁t需要拆分为t1和t2。拆分方法如下：

从P 中引入一个新的库所p 和从T 中引入两个新的变迁t1和t2。t1和t2需满足{p}，·t2={p}，t2·=t·，且需要根据t的变迁类型添加条件。如果t∈TC，那么不用添加条件；如果t∈TI，那么I（t1）=I（t）；如果t∈TO，那么O（t2）=O（t）。t2引发的库所后集变化与t相同，t1的库所后集变化与t2的前集变化合理即可。将t1，t2，p 看为一个变迁的话，则与原来的t相同。

图2（a）是一个需要拆分的逻辑工作流网，其中t1变迁发生需要从p3中消耗托肯和在p3中产生托肯。t1可以拆分为t2和t3，拆分后的LWN 如图2（b）所示。如果图2（b）中变迁引发产生的标识变化可以表示为M1［t2＞M2［t3＞M3，那么对应的图1中标识变化为M1［t2＞M3。显而易见，t拆分后LWN 相对于t拆分前的LWN 多了一个中间标识M2。

图2 t拆分前后的LWNFig.2 LWN before and after t-splitting

算法1：STN 的生成

输入：LWN=（P，T，F，I，O，M）

输出：STN=（S，E，OP，s0，Z）

Step 0：s0=M0.在S 中新建一个状态s0，并标记为“新”

Step 1：While∃s∈S 并且它的标签为“新”Do

从S 中任取一个标签为“新”的状态，并命名为s

Step 2：对每一个t∈T IF M［t＞Do

Step 2.1：根据M［t＞M'，计算所有的M'

Step 2.2：对每一个M'Do

Step 2.2.1：IF M'∉S Then

在S 中新建一个状态s=M'

Step 2.2.2：在E 中新建一个转换关系（M，L（M，M′），M′）

Step 2.2.3：IF L（M，M′）∉OP Then

IF LI（M，M′）=L（M，M′）Then在OPI中新建一个消息LI（M，M'）

Else IF LI（M，M′）=L（M，M′）Then在OPO 中新建一个消息LO（M，M'）

Step 2.3：返回Step 2

Step 3：返回Step 1

该算法实现了从LWN到STN的映射。

2 状态转换图组合研究

本部分将从伙伴逻辑状态转换图的角度理解两个状态转换图的组合。首先引入组合状态的概念，这些概念允许仅通过考虑伙伴状态转换图来表示组合逻辑工作流网的死锁。随后定义状态映射与状态赋值。

定义11（组合状态） 对于STNA=（S，E，OP，s0，Z），组合状态是一个二元组（s，c），其中s是STNA 中的一个状态，c是一个消息。

定义12（g 限死锁） （s，c）是g 限死锁当且仅当满足stop（s）=Ø和｜c｜=g。

定义13（可达状态集） 对于组合状态（s，c），将（s，c）的可达状态集表示为R（s，c），其归纳定义为：

基础：（s，c）∈R（s，c）

步骤：如果（s，c）∈R（s，c）且∃s′∈S，（s，x，s′）∈E，那么

如果x=τ，（s′，c）∈R（s，c）；或者

如果x∈OPO 且｜c｜-｜x｜＜g，（s′，c（x））∈R（s，c）；或者

如果x∈OPI且x⊆c，（s′，c（x））∈R（s，c）。

定义14（单步可达状态集） 对于组合状态集SS= {（s，c）｜s∈S，c∈C}，将SS 的单点可达状态集表示为R（SS），其归纳定义如下：

基础：SS∈R（SS）

步骤：如果（s，c）∈R（SS）且∃s′∈S，（s，x，s′）∈E，那么

如果x=τ，（s′，c）∈R（SS）；或者

如果x∈OPO 且｜c｜-｜x｜＜g，（s′，c（x））∈R（SS）；或者

如果x∈OPI且x⊆c，（s′，c-x））∈R（SS）。

定义15（状态单步可达状态集） 对于组合状态（s，c），R（（s，c），x）为状态单步可达状态集，其定义为：

如果x=τ，R（（s，c），x）=R（s，c）；或者

如果x∈OPO 且（s，c+x）不是g 限死锁，R（（s，c），x）=R（s，c+x）；或者

如果x（OPI且x⊆c，R（（s，c），x）=R（s，c-x）。

定义16（状态集单步可达状态集） 对于组合状态集SS={（s，c）｜s∈S，c∈C}，R（（s，c），x）为其状态集单步可达状态集，其定义为：

如果x=τ，R（SS，x）={y∈R（s，c）｜（s，c）∈SS}；或者

如果x∈OPO，R（SS，x）={y∈R（s，c+x）｜（s，c）∈SS}；或者

如果x∈OPI且x⊆c，R（SS，x）= {y∈R（s，c-x）｜（s，c）∈SS}。

定义17（状态映射） 对于STNA 和STNB，K：SB→2x，x=SA×C 为从STNB 到STNA 的状态映射，K（sB）={（sA，c）｜（sA，sB，c）能够从A 和B 的组合状态转换图STNA⊗STNB 中可达}。

定义18（动态和静态） 组合状态（s，c）是动态当且仅当存在s′∈S 使得（s，x，s′）∈E 成立，其中

如果x=τ且（s′，c）∈R（s，c）；或者

如果x∈OPO 且（s′，c+x）∈R（s，c），或者

如果x∈OPI∧x⊆c且（s′，c（x）∈R（s，c），

否则（s，c）是静态。

仅从STNB 的角度来看，死锁定义如下：

（sA，sB，c）是组合状态转换图A⊗B 并且满足以下条件：

sA∉ZA，或sB∉ZB，或者c≠Ø；

SB是B 的停止状态并且x∉stop（sB）∧x⊆c；

且（sA，c）是一个静态。

定义19（状态赋值） 对于组合STNA⊗STNB 中STNB 的状态sB，死锁的三个定义可以使用逻辑表达式来表示，称为sB的状态赋值，表示为live（sB），其定义如下：

live（sB）=final∨output∨input，其中：

final是真需满足sA∈ZA且c=Ø，否则final是假赋值；

output是真需满足∃（sA，x，s′A）∈EA，其中s′A∈SA且x∈stop（sB），否则output是假赋值；

input是真对每个x∈stop（sA），需满足∃（sB，x，s′B）∈EBi，其中s′B∈SB，否则input是假赋值。

∀sB∈SB，（sA，c）是K（sB）中的一个静态。

其中，live（sB）表达式为sB对应组合状态集K（sB）中静态（sA，c）的条件final∨output∨input的合取式；final表示sA是否是最终状态；input和output分别表示STNA 和STNB 可以进行信息接收。

当且仅当库所B 中状态SB，所有状态赋值中的live（sB）的值为真时，STNA⊗STNB 是无死锁的。

3 伙伴状态转换图生成

本节根据一个逻辑工作流网计算其伙伴状态转换图。由于这个伙伴转换图可以表示伙伴逻辑工作流网的无死锁逻辑序列，将其称为规范伙伴转换图。

定义20（规范伙伴转换图）SPN

对于LWN=（P，T，F，I，O，M），其伙伴转换图SPN=（S，E，OP，s0，Z）递归定义如下

步骤0：SPN0=（S0，E0，OP0，s00，Z0）其中S0={x∈2y，y=S×（OPI∪OPO）｜x=R（x）}；E0={（s，x，s′）｜s∈S0，x∈OP，s′∈S0，s′=R（s，x）}；OP0=OPI0∪OPO0∪{τ}，其中OPI0=OP0且OPO0=OPI；s00=R （s0，Ø）且s0=M0；Z0={（x，Ø）｜x∈Z，（x，Ø）∈S0}。

步骤i：SPNi=（Si，Ei，OPi，s0i，Zi）。

步骤i+1：SPNi+1=（Si+1，Ei+1，OPi+1，s0i+1，Zi+1），其中Si+1={s∈Si｜∀x∈s，live（x）=true}；Ei+1={（s，x，s′）｜s，s′∈Si+1，x∈OP，s′=R（s，x）}；OPi+1=OPI0∪OPO0∪{τ}，OPIi+1=OPO，OPOi+1=OPI；s0i+1=R （s0，Ø）；Zi+1={（x，Ø）｜x∈Z，（x，Ø）∈Si+1}；

直到SPNi+1=SPNior s0i+1∉Si+1。

对于最小的i+1，使SPN 等于SPNi+1。如果s0i+1∉Si+1，那么SPN 不存在，说明这个逻辑工作流网没有无死锁伙伴逻辑工作流网。在计算SPN 时，SP 的所有状态live（s）的值都为真（不为真的被删除），根据死锁的定义得出，SPN 描述了组合时伙伴逻辑工作流网的无死锁活动序列。在计算消息集C时，由于C 是一个无限集合，无法全部计算出来。所以引入一个常数g，用g 限消息集Cg代替无限大的集合C，此时规范伙伴转换图称为g 限规范伙伴状态转换图，记为SPNg。g 限规范伙伴状态转换图的生成算法如下。

算法2：SPNg的计算

输入：LWN=（P，T，F，I，O，M）

输出：SPN=（S，E，OP，s0，Z）

Step 0：s0=R（s0，Ø），从S 中引入一个新的组合状态s0，并标记为“新”；

Step 1：While∃s∈S 并且标识是“新”Do

从S中任取一个标识为“新”的状态，并将其赋值给s

Step 1.1：对于每个op∈OP，Do

Step 1.1.1：计算R（s，op）

Step 1.1.2：IF R（s，op）=ØThen返回Step 1.1

Step 1.1.3：IF R（s，op）∉S Then

从S中引入一个新的状态R（s，op）并标记为“新”

Step 1.1.4：从E 中引入一个新的状态转换关系（s，op，R（s，op））

Step 1.2：返回Step1

Step 2：对于每个s∈S Do

IF∀（s，op，s′）∉E 对所有op∈OP 成立，其中s′∈S 和s≠s0 Then标记S为“死锁”

Step 3：While∃s∈S 且它的标签是“死锁”Do

Step 3.1：对于每个s Do

IF标识是“死锁”Then从S 中移除s

Step 3.2：对于每个（s，op，s′）∈S Do

IF s∉S 或s′∉S Then从E 中移除（s，op，s'）

Step 3.3： 对于每个s∈S Do

IF∀（s，op，s′）∉E 对所有op∈OP 成立，其中s′∈S 和s≠s0，Then标记s为“死锁”

Step 3.4： 返回Step 3

对于计算出的g 限规范伙伴转换图，一般是进行死锁预判。在不进行组合前，判断伙伴逻辑工作流网与本逻辑工作流网的组合后会不会出现死锁。下面将给出一个简单的实例进行说明。

图3是一个逻辑工作流网，表示两位用户分别购买两件不同的商品。其中，p1和p2分别表示两位用户对商品购买确认，p3和p4表示商品付款，p5和p6表示商品，p1和p2表示商品的退款；t1表示接收订单，I（t1）=p9∧（p1∨p2）；t2表示确认付款，I（t2）=p10∧（p13∨p14）；t3表示处理结果，O（t3）=p12∧（（（p7⊕p5）⊕p1）∨（（p8⊕p6）⊕p2））），且O（t2）≠p12∧p1∧p2。⊕表示异或操作。

根据算法1，其状态转换图如图3所示。其中初始状态为s0；初始全局消息为空；使用操作-x 表示从全局消息中接收消息；操作+y 表示往全局消息中发送消息；多集符号被简写，比如-［p1］，简写为p1，表示从全局消息中接收消息［p1］。

根据算法2，其2限规范伙伴转换图如图3所示。其中，不同状态都用数字来区分，0表示初始状态。

对于g 限规范伙伴转换图，简略分析其算法时间复杂度。组合状态的数目最多为x×yg，其中x=｜S｜，y=｜∪（OPI∪OPO）｜，组合状态集的数目与组合状态大约呈正相关，所以可以认为算法的时间复杂度与组合状态数目呈正相关。可以看出，如果状态转换图状态过多或者g 过大，算法计算时间将会很大。

对于上面的网上购物系统和它的2限规范伙伴转换图，分别用A 和SPNA2表示。图5（a）是A 的伙伴逻辑工作流网，用B 表示。其中I（t7）=p5⊕p7。图5（b）是B 的状态转换图，用STNB 表示。使用SPNA2来预测2限组合逻辑工作流网A⊗B 有无死锁。判断过程如下。

STNB 没有孤立状态，说明STNB 本身不存在死锁。然后将STNB 对应到SPNA2上，s0对应状态0，s1对应状态1，s2对应状态8，并且所有对应的两个状态，其消耗信息一致。因此，逻辑工作流网A 与B的2限组合没有死锁。

4 总结

图3 一个简易网上购物系统Fig.3 A simple online shopping system

图4 实例的状态转换图Fig.4 State transition diagram

图5 2限规范伙伴转换图Fig.5 2-limit standard canonical partner transition diagram

本研究使用逻辑工作流网建模相关系统，使用逻辑变迁替代普通变迁，简化了普通petri网的结构，可建模具有批处理和传值不确定的系统。最终得到一个逻辑工作流网的g 限标准伙伴状态转换图，此状态转换图描述了伙伴逻辑工作流网的无死锁逻辑活动序列。只要是能被g限标准伙伴状态转换图完全描述的伙伴逻辑工作流网，组合后不会出现死锁。根据死锁的充分条件，提出状态映射用以判断两个工作流网组合后出现的死锁。通过删除进入死锁的逻辑活动序列，计算出可与其无死锁组合的伙伴状态转换图。由于伙伴逻辑工作流网的无死锁逻辑活动过多，导致伙伴状态转换图状态过多。即使是简单的系统，如果g 的取值过大，其伙伴状态转换图的状态也会特别多。因此，本方法不适用于太过巨大的系统。

图6 A的一个伙伴逻辑工作流网及其状态转换图Fig.6 A partner logical workflow net of A and its state transition graph