【Petri网导论学习笔记】Petri网导论入门学习（七） —— 1.5 并发与冲突

1.5 并发与冲突

Petri网的一大突出优点就是便于描述并发与冲突，其中同步与并发的概念紧密相连

以下从基本网系统入手进行讨论

1.5.1 并发

考察图 1.15 的基本网系统${\Sigma }_1=(B,E;F,c_0)$ ,其中 c 0 = { b 1 , b 2 } c_0=\{b_1,b_2\} c0​={b1​,b2​}。在情态$c_0$下事件$e_2$和$e_3$都有权发生。这是因为
∙ e 2 = { b 1 } ⊆ c 0   且 e 2 ∙ ∩ c 0 = { b 3 } ∩ {   b 1 , b 2   } = ∅ ∙ e 3 = { b 2 } ⊆ c 0   且 e 3 ∙ ∩ c 0 = { b 4 } ∩ {   b 1 , b 2   } = ∅ ^\bullet e_2=\{b_1\}\subseteq c_0\:\text{且}\quad e_2^\bullet\cap c_0=\{b_3\}\cap\{\:b_1,b_2\:\}=\emptyset\\^\bullet e_3=\{b_2\}\subseteq c_0\:\text{且}\quad e_3^\bullet\cap c_0=\{b_4\}\cap\{\:b_1,b_2\:\}=\emptyset ∙e2​={b1​}⊆c0​且e2∙​∩c0​={b3​}∩{b1​,b2​}=∅∙e3​={b2​}⊆c0​且e3∙​∩c0​={b4​}∩{b1​,b2​}=∅

$e_2$前集$b_1$是$c_0$且$e_2$后集与$c_0$有交集$b_3$且不是$b_1$与$b_2$

下面同理

假设$e_2$在情态$c_0$发生，变成新的情态 c 1 = { b 2 , b 3 } c_1=\{b_2,b_3\} c1​={b2​,b3​},易知$e_3$在情态$c_1$仍有发生权。反之，如果$e_3$在情态$c_0$发生，得到新的情态 c 2 = { b 1 , b 4 } c_2=\{b_1,b_4\} c2​={b1​,b4​},则$e_2$在情态$c_2$也仍有发生权。我们说$e_2$和$e_3$在情态$c_0$处于并发关系。
一般地说，如果两个事件在某情态下都有发生权，而且其中任何一个的发生都不会使另一个失去发生权，则称这两个事件在该情态下处于并发。

定义 1.14

设$\Sigma =(B,E;F,c_0)$ 为一个EN 系统，$e_1,e_2\in E,c$ 是$\Sigma$ 的一个情态。

如果

$\begin{array}{rl}& 1)c[e_1>\wedge c[e_2>\\ & 2)c[e_1>c_1\to c_1[e_2>\wedge c[e_2>c_2\to c_2[e_1>\end{array}$

$e_1$与$e_2$在情态$c$上有发生权

$e_1$发生后的情态可以继续发生$e_2$且$e_2$发生后的情态可以继续发生$e_1$

则称$e_1$和$e_2$在情态$c$并发 , 或者说 $e_1$和$e_2$在情态$c$有一步发生权，记作 c [ { e 1 , e 2 } > 。 c[\{e_1,e_2\}>。 c[{e1​,e2​}>。
并发不能简单地理解为“同时发生”,而是指事件之间因果上的无依赖性。按网论的观点 , 事件(变迁)的发生只依赖于它们的外延 , 而与全局情况无关。在图1.15 的基本网系统中，事件$e_2$的外延是

∙ e 2 ∪ e 2 ∙ = {   b 1 , b 3   } ^\bullet e_2\cup e_2^\bullet=\{\:b_1,b_3\:\} ∙e2​∪e2∙​={b1​,b3​}

事件$e_3$的外延是

∙ e 3 ∪ e 3 ∙ = {   b 2 , b 4   } ^\bullet {e_3\cup e_3^\bullet}=\{\:b_2,b_4\:\} ∙e3​∪e3∙​={b2​,b4​}

由于$e_2$和$e_3$的外延之间没有公共部分，所以它们是两个互相独立的事件。这是基本网系统中两个事件处于并发的必要条件。

现在考察一下$e_2$和$e_4$两个事件之间的关系。前面已指出，在情态 c 0 = { b 1 , b 2 } c_0=\{b_1,b_2\} c0​={b1​,b2​}下$e_2$有发生权，但$e_4$在$c_0$没有发生权。如果$e_2$在$c_0$发生，得到情态 c 1 = { b 2 , b 3 } c_1=\{b_2,b_3\} c1​={b2​,b3​},易知$e_4$在$c_1$有发生权。也就是说，$e_4$的发生权是通过$e_2$ (在$c_0$)发生获得的。我们说$e_2$和$e_4$的发生是一种顺序关系。

定义 1.15

设$(B,E;F,c_0)$为一个EN系统,$e_i,e_j\in E$,$c$是$\Sigma$ 的一个情态。如果

$\begin{array}{rl}& 1)c[e_i>\text{ 但 }\neg c[e_j>\\ & 2)c[e_i>c^{\prime }\to c^{\prime }[e_j>\\ & \end{array}$

则称事件$e_i$ 和$e_j$有顺序关系(sequential relation)。

在情态$c$当中，$e_i$可以发生但是$e_j$不能发生，

但是$e_i$发生之后$e_j$可以发生，所以称为有顺序关系。

下面继续考察并发关系的一些性质。前面已经指出，在图1.15 的 EN 系统中，事件$e_2$和$e_3$在 c 0 = { b 1 , b 3 } c_0=\{b_1,b_3\} c0​={b1​,b3​}并发。如果这时$e_2$发生，得到情态 c 1 = { b 2 , b 3 } c_1=\{b_2,b_3\} c1​={b2​,b3​}。分析一下易知，事件$e_3$和$e_4$在$c_1$处于并发关系。这就是说，在该 EN 系统中，既存在情态$c_0$使$e_2$和$e_3$处于并发关系，也存在情态$c_1$使$e_3$和$e_4$处于并发关系。然而，在该系统的任意情态下，$e_2$和$e_4$都不可能处于并发关系。这说明，并发关系没有传递性。

如果在情态$c_0$发生事件$e_3$,得到情态 c 2 = { b 1 , b 4 } c_2=\{b_1,b_4\} c2​={b1​,b4​},易知事件$e_2$和$e_5$在$c_2$也处于并发关系。不难看出，这个EN 系统还存在情态 c 3 = { b 3 , b 4 } c_3=\{b_3,b_4\} c3​={b3​,b4​}使得$e_4$和$e_5$在$c_3$并发。也就是说，在这个系统中，事件对$e_2$ 和$e_3,e_3$ 和$e_4,e_2$ 和$e_5$ 以及$e_4$ 和$e_5$,都有可能处于并发关系。然而，在事件$e_2$和$e_4$之间以及$e_3$和$e_5$之间，都是一种顺序关系。在这种情况下，我们也可以说，事件串(序列)$e_2{e}_4$和事件串$e_3{e}_5$在情态$c_0$处于并发。

假如从情态$c_0$ 发生事件串 $e_2{e}_4$,得到的情态为 { b 2 , b 5 } \{b_2,b_5\} {b2​,b5​}。这时只有等待事件串$e_3{e}_5$ 发生后，事件$e_6$才有发生权。反之，如果从$c_0$发生事件串$e_3{e}_5$,得到情态 { b 1 , b 6 } \{b_1,b_6\} {b1​,b6​}。这时也要等待另一事件串$e_2{e}_4$ 发生后，事件$e_6$才有发生权。可见，事件$e_6$起到了使两个并发的事件串$e_2{e}_4$和$e_3{e}_5$同步的作用。同步(synchronous)的概念是同并发关系紧密相联的。它也是并发系统中的一个重要概念。

1.5.2 冲突

考察图 1.16 的基本网系统${\Sigma }_2=(B,E;F,c_0)$ ,其中 c 0 = { b 2 } c_0=\{b_2\} c0​={b2​}。事件$e_1$和$e_3$在情态$c_0$都可能发生。但如果$e_1$发生，产生新的情态 c 1 = { b 1 } c_1=\{b_1\} c1​={b1​},$e_3$在$c_1$失去了发生权。反过来也是这样，如果在情态$c_0$下$e_3$发生，得到新的情态 c 2 = { b 3 } c_2=\{b_3\} c2​={b3​},$e_1$在情态$c_2$失去了发生权。这种情况称为冲突。

因为只能选一个变迁发生，所以$e_1$与$e_3$不能同时发生。

$\begin{array}{rlrl}& e_2\text{ 和 }{e}_4\text{ 的发生是一种顺序关系。}& & \\ & \text{定义 1.15 设 }(B,E;F,c_0)\text{ 为一个 EN 系统,}{e}_i,e_j\in E\text{,}c\text{ 是 }\Sigma \text{ 的一个情态。如果}& & \\ & \text{1)}c[e_i>\text{ 但 }\neg c[e_j>& & (1.38)\\ & \text{2)}c[e_i>c^{\prime }\to c^{\prime }[e_j>& & (1.39)\end{array}$

则称事件$e_1$和$e_2$在情态$c$处于冲突关系。

$e_1$与$e_2$在情态$c$上有发生权

$e_1$发生后的情态可以继续发生$e_2$且$e_2$发生后的情态可以继续发生$e_1$

在图 1.16 的这种 EN 系统中，$e_1$ 和$e_3$在$c_0$ 冲突，是因为$c_0{\supseteq }^{\bullet }{e}_1{\cup }^{\bullet }{e}_3$ 而且${}^{\bullet }{e}_1\cap$ ${}^{\bullet }{e}_3\ne \varnothing$。下面考察另一种类型的例子。在图 1.17a)的基本网系统${\Sigma }_3$中，在情态$c=$ { b 1 , b 2 } \{b_1,b_2\} {b1​,b2​}下，事件$e_1$和$e_2$都是可以发生的。然而它们当中只能有一个发生，同时，其中的任一事件发生，都会使另一个失去发生权。因此$e_1$ 和$e_2$ 在情态 { b 1 , b 2 } \{b_1,b_2\} {b1​,b2​} 也处于冲突。然而，这种冲突同图 1.16 的 EN 系统${\Sigma }_2$中的冲突又有不同之处。在${\Sigma }_3$中，“$e_1\cap$ ${}^{\bullet }{e}_2=\varnothing$,但$e_1^{\bullet }\cap e_2^{\bullet }\ne \varnothing$,所以当其中一个事件如$e_1$发生后，$e_2$失去发生权的原因不是${}^{\bullet }{e}_2$不满足条件，而在于$e_2^{\bullet }$不满足条件。即$c\left[e_1>c_1\to c_1\cap e_2^{\bullet }\ne \varnothing ,如图\text{ 1.17b)所}\right]$
示。这种情况称为冲撞(contact)。

定义 1.17

在基本网系统$(B,E;F,c_0)$中，$c$是$\Sigma$的一个情态。若存在$b\in B$和$e\in E$,使得

${}^{\bullet }e\subseteq c\text{ 且 }b\in e^{\bullet }\cap c$

则称该系统在情态$c$下条件$b$处有冲撞。

多个事件都可以导致一个条件满足，但是其中一个事件发生后后置条件被填满所以不能发生了（因为基本网系统中库所容量上限为1），即为冲撞。

冲突是一个条件能发生多个事件，但是只能发生一个。

冲撞是多个事件能满足一个条件，但是只能发生一个事件后其他不能发生了。

在任何情态下，任一个条件都不存在冲撞的基本网系统称为无冲撞系统(contact-free system)。
冲突关系也可以这样给出定义：在 EN 系统$(B,E;F,c)$中，若$e_1,e_2\in E$满足
$$c\left[\begin{array}{cc}{e}_1>& \text{且}c\end{array}\right[\begin{array}{cc}{e}_2>& \text{但}\neg c\left[\begin{array}{c}{e}_1,e_2\end{array}\right\}>\end{array}$$
则称$e_1$和$e_2$在$c$处于冲突。

冲突关系描述了系统的非确定性：在某情况下有两个(或多个)事件都有权发生，但在实际运行过程中，只有一个能真正发生。系统存在冲突之处，正是外界环境可以对其施加控制(加以选择)。
有时候，一个网系统，在某个情态下同时存在并发和冲突，但由于并发事件中的某些事件的发生，会使冲突自动消失。另外还有一种情况，系统在某个情态下存在并发， 而并发事件中不同的事件发生，使得系统可能出现冲突，也可能不出现冲突。上面两种现象称为混惑(confusion)。

混惑：

在某个情态下同时存在并发和冲突，但由于并发事件中的某些事件的发生，会使冲突自动消失。

系统在某个情态下存在并发， 而并发事件中不同的事件发生，使得系统可能出现冲突，也可能不出现冲突。

冲突的出现无法确定！尽量避免ta！

第一种混惑的例子如图 1.18 所示。在这个系统中，既有$e_1$和$e_2$的冲突以及$e_2$和$e_3$的冲突，又有$e_1$和$e_3$的并发。在$e_1$和$e_2$冲突中，如果选择$e_1$发生，则$e_2$和$e_3$的冲突也就自动消失。

第二种混惑的例子如图 1.19 所示。在该系统中，在当前状态下事件$e_1$和$e_2$处于并发。如果事件$e_2$先于$e_1$发生，那么就会产生$e_1$和$e_3$的冲突。反之，若$e_1$先于$e_2$发生，这种冲突就不会出现。

存在混惑的网系统不是好的系统模型，因为在这种网系统的运行中，冲突是否出现无法确定，不便于对系统施加外部控制。在建立实际系统的 Petri 网模型时，应尽量避免出现混惑。

1.5.3 一般Petri网系统中的并发与冲突

之前的讨论在基本网系统，现在引入到一般Petri网当中

从基本网系统引入的并发与冲突等概念，在一般 Petri 网中也存在，而且含义基本相同。但由于不同的网系统的变迁发生规则有所不同，因此有些概念在不同的网系统中表现也略有区别。下面先给出在一般 Petri 网中的并发和冲突的定义。

定义 1.18

设 $\Sigma$ 为一个网系统，$t_1$ 和 $t_2$ 是 $\Sigma$ 中的两个变迁。如果 $\Sigma$ 的一个标识 $M$ 使得 $M[t_1⟩$ 且 $M[t_2⟩$，那么：

1. 若 $M[t_1⟩M_1\to M_1[t_2⟩M_2$ 且 $M[t_2⟩M_1\to M_2[t_1⟩$，则称 $t_1$ 和 $t_2$ 在 $M$ 并发，记为 M { t 1 , t 2 ⟩ M\{t_1, t_2\rangle M{t1​,t2​⟩。
2. 若 $M[t_1⟩M_1\to \neg M_1[t_2⟩$ 且 $M[t_2⟩M_2\to \neg M_2[t_1⟩$，则称 $t_1$ 和 $t_2$ 在 $M$ 冲突（或说在 $M$ 处于有效冲突）。

$t_1$发生后的新标识$M_1$可以发生$t_2$，对偶亦然。

$t_1$发生后的新标识$M_1$可以不发生$t_2$，对偶亦然。

就是把情态$c$换成了标识$M$。

从定义上看，一般网系统的并发和冲突概念同基本网系统中的定义是一致的，但在实际表现上，却有一些区别。

一般网系统中无冲撞概念

首先，一般 Petri 网中没有冲撞的概念。这是因为 Petri 网中的库所容量为无限大， 因此，在 Petri 网中，只要一个变迁的前集各库所有足够的标志，该变迁就可以发生。即使该变迁的后集中某些库所含有标志，也不影响变迁的发生。

阻塞（有容量函数K的P/T系统，类似于冲撞）

对于有容量函数$K$的 P/T 系统，由于对库所容量有一定的容量限制，有时也会出现类似于冲撞的情况，但情况又不完全相同。考察图 1.20 的 P/T 系统，为便于观察，我们把各库所的容量函数值标在表示该库所的小圆圈旁。在这个PT 系统中，变迁$t_1$的前集只有一个元素$s_1$。在当前标识下，$s_1$中含有 3 个标志，等于弧$(s_1,t_1)$上的权。但由于$t_1$的后集库所$s_2$中已有 3 个标记，如果$t_1$发生将向$s_2$送入 2 个标记，标记总数(5) 将超过$s_2$的容量($K(s_2)=4$),因此在当前标识下，$t_1$不能发生。然而，如果在当前状态下，$t_2$先发生，$t_2$发生后，$s_2$中只剩余一个标志。这时，虽然作为$t_1$的后集库所$s_2$中非空，但其容量足以容纳$t_1$发生后送到$s_2$的标志，所以在这种情况下$t_1$就可能发生。这种情况反映了实际系统中的阻塞现象。因此，有人直接把这种情况称之为阻塞。

在 Petri 网中，${}^{\bullet }{t}_1{\cap }^{\bullet }{t}_2\ne \varnothing$是变迁$t_1$和$t_2$可能发生冲突的一个必要条件，但不是充分条件。考察图 1.21 的 Petri 网系统。在该网系统中，“ t 1 ∩ ∙ t 2 = { s 2 } ≠ ∅ t_1\cap^{\bullet}t_2=\{s_2\}\neq\emptyset t1​∩∙t2​={s2​}=∅,然而在当前标识下，$t_1$和$t_2$非但不处于有效冲突，而且地地道道处于并发。

总之，对各种网系统中的并发和冲突的分析，其根本依据是定义 1.18 和各类网系统的变迁发生规则，切不可只看到一点局部结构就轻易下结论。

一般Petri网中并发与冲突共存情况

在一般 Petri 网中，也存在并发与冲突共存的情况，除了图 1.17 和图 1.18 那样的混惑的情况外，图 1.22a)的网系统是一个有趣的例子。

在当前标识下，变迁$t_1$和$t_2$处于并发。但如果$t_1$或$t_2$有一个先发生，在新的标识下$t_1$和$t_2$便处于有效冲突。不过，对于这种情况，可以施加外部控制。图 1.22b) 便是对其施加控制后的一个例子。在这里，我们在网系统中加入库所$s_4$和$s_5$使$s_4{t}_1{s}_5{t}_2$形成一个控制回路。加上这样的控制装置后，$t_1$和$t_2$的有效冲突已经消失。这个控制装置起到了使变迁$t_1$和$t_2$轮流分享它们的公共资源(库所$s_1$的标志)的作用。

加了一个控制回流，让他们轮流发生，共同分享$s_1$