当前位置：首页 > news >正文

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

news 文章来源：https://blog.csdn.net/tycer/article/details/143059736 2025/5/8 22:51:14

- - 1.5 并发与冲突
  - - 1.5.1 并发
    - - 定义 1.14
      - 定义 1.15
    - 1.5.2 冲突
    - - 定义 1.17
    - 1.5.3 一般Petri网系统中的并发与冲突
    - - 定义 1.18
      - 一般网系统中无冲撞概念
      - 阻塞（有容量函数K的P/T系统，类似于冲撞）
      - 一般Petri网中并发与冲突共存情况

1.5 并发与冲突

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

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

1.5.1 并发

考察图 1.15 的基本网系统 $\Sigma_1=(B,E;F,c_0)$ ,其中 $c_0=\{b_1,b_2\}$ 。在情态 $c_0$ 下事件 $e_2$ 和 $e_3$ 都有权发生。这是因为
$^\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$

$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\}$ ,易知 $e_3$ 在情态 $c_1$ 仍有发生权。反之，如果 $e_3$ 在情态 $c_0$ 发生，得到新的情态 $c_2=\{b_1,b_4\}$ ,则 $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{aligned}&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{aligned}$

$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\}>。$
并发不能简单地理解为“同时发生”,而是指事件之间因果上的无依赖性。按网论的观点 , 事件(变迁)的发生只依赖于它们的外延 , 而与全局情况无关。在图1.15 的基本网系统中，事件 $e_2$ 的外延是

$^\bullet e_2\cup e_2^\bullet=\{\:b_1,b_3\:\}$

事件 $e_3$ 的外延是

$^\bullet {e_3\cup e_3^\bullet}=\{\:b_2,b_4\:\}$

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

现在考察一下 $e_{2}$ 和 $e_{4}$ 两个事件之间的关系。前面已指出，在情态 $c_0=\{b_1,b_2\}$ 下 $e_{2}$ 有发生权，但 $e_4$ 在 $c_0$ 没有发生权。如果 $e_2$ 在 $c_0$ 发生，得到情态 $c_1=\{b_2,b_3\}$ ,易知 $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{aligned}&1)c[e_{i}>\text{ 但 }\neg c[e_{j}>\\&2)c[e_{i}>c^{\prime}\to c^{\prime}[e_{j}>\\&\end{aligned}$

则称事件 $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\}$ 并发。如果这时 $e_2$ 发生，得到情态 $c_1=\{b_2,b_3\}$ 。分析一下易知，事件 $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\}$ ,易知事件 $e_2$ 和 $e_5$ 在 $c_2$ 也处于并发关系。不难看出，这个EN 系统还存在情态 $c_3=\{b_3,b_4\}$ 使得 $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_2e_4$ 和事件串 $e_3e_5$ 在情态 $c_0$ 处于并发。

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

1.5.2 冲突

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

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

在这里插入图片描述

$\begin{aligned}&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{aligned}$

则称事件 $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\neq\emptyset$ 。下面考察另一种类型的例子。在图 1.17a)的基本网系统 $\Sigma_{3}$ 中，在情态 $c =$ ${b_1,b_2\}$ 下，事件 $e_1$ 和 $e_2$ 都是可以发生的。然而它们当中只能有一个发生，同时，其中的任一事件发生，都会使另一个失去发生权。因此 $e_1$ 和 $e_2$ 在情态 ${b_1,b_2\}$ 也处于冲突。然而，这种冲突同图 1.16 的 EN 系统 $\Sigma_{2}$ 中的冲突又有不同之处。在 $\Sigma_3$ 中，“ $e_1\cap$ $^{\bullet}e_2=\emptyset$ ,但 $e_1^\bullet\cap e_2^\bullet\neq\emptyset$ ,所以当其中一个事件如 $e_1$ 发生后， $e_2$ 失去发生权的原因不是 $^{\bullet}e_2$ 不满足条件，而在于 $e_2^\bullet$ 不满足条件。即 $c\left[e_1>c_1\to c_1\cap e_2^\bullet\neq\emptyset,如图\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{matrix}{e_{1}>}&{\text{且}c}\\\end{matrix}\right[\begin{matrix}{e_{2}>}&{\text{但}\neg c\left[\begin{matrix}{e_{1},e_{2}}\\\end{matrix}\right\}>}\\\end{matrix}$
则称 $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\rangle$ 且 $M[t_2\rangle$ ，那么：

若 $M[t_1\rangle M_1 \rightarrow M_1[t_2\rangle M_2$ 且 $M[t_2\rangle M_1 \rightarrow M_2[t_1\rangle$ ，则称 $t_1$ 和 $t_2$ 在 $M$ 并发，记为 $M\{t_1, t_2\rangle$ 。
若 $M[t_1\rangle M_1 \rightarrow \neg M_1[t_2\rangle$ 且 $M[t_2\rangle M_2 \rightarrow \neg M_2[t_1\rangle$ ，则称 $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\neq\emptyset$ 是变迁 $t_1$ 和 $t_2$ 可能发生冲突的一个必要条件，但不是充分条件。考察图 1.21 的 Petri 网系统。在该网系统中，“ $t_1\cap^{\bullet}t_2=\{s_2\}\neq\emptyset$ ,然而在当前标识下， $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_4t_1s_5t_2$ 形成一个控制回路。加上这样的控制装置后， $t_1$ 和 $t_2$ 的有效冲突已经消失。这个控制装置起到了使变迁 $t_1$ 和 $t_2$ 轮流分享它们的公共资源(库所 $s_{1}$ 的标志)的作用。

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

导航