转载

Petri网介绍

Petri网是一种可以用网状图形表示的系统模型。并发系统中遇到的一个主要问题是定时问题。这个问题可以表现为多种形式，如同步问题、竞争条件以及死锁问题。定时问题通常是由不好的设计或有错误的实现引起的，而这样的设计或实现通常又是由不好的规格说明造成的。如果规格说明不恰当，则有导致不完善的设计或实现的危险。用于确定系统中隐含的定时问题的一种有效技术是 Petri 网，这种技术的一个很大的优点是它也可以用于设计中.

Petri 网是由 Carl Adam Petri 发明的。最初只有自动化专家对 Petri 网感兴趣，后来 Petri 网在计算机科学中也得到广泛的应用，例如，在性能评价、操作系统和软件工程等领域， Petri 网应用得都比较广泛。特别是已经证明，用 Petri 网可以有效地描述并发活动。

Petri 网包含 4 种元素：一组位置 P 、一组转换 T 、输入函数 I 以及输出函数 O 。上图举例说明了 Petri 网的组成。其中：

一组位置 P 为｛ P1,P2,P3,P4｝，在图中用圆圈代表。在P中还可以驻留标记,说明Petri网转移的运行条件,用一个黑色小圆点表示。
一组转换 T 为｛ t1,t2 ｝，在图中用短直线表示转换。
两个用于转换的输入函数，用由位置指向转换的箭头表示，它们是：

$ I(t1)= {P2,P4}$$ I(t2)= {P2}$

两个用于转换的输出函数，用由转换指向位置的箭头表示，它们是:

$O(t1)= {P1}$$O(t2)= {P3,P3}$

注意. 输出函数 O(t2) 中有两个 P3 ，是因为有两个箭头由 t2 指向 P3 。

更形式化的 Petri 网结构，是一个四元组 C=(P,T,I,O) 。其中:

$P = {P1, … ,Pn}$是一个有穷位置集,$n ≥ 0$ 。
$T = {t1, … ,tm}$是一个有穷转换集,$m ≥ 0$ ,且 T 和 P 不相交,$P land T = emptyset$。
$I:T → P$ 为输入函数，是由转换到位置无序单位组(bags) 的映射。
$O:T → P$ 为输出函数，是由转换到位置无序单位组的映射。

在用Petri网进行系统建模时,经常使用P来表示系统的状态,用T来模拟系统的行为,T 的输入P所用来表示变迁启动的条件,变迁的输出P所表示变迁启动的结果,各个P所代表的系统状态用Token来表示。若变迁的所有输入P都驻留一个Token,则该变迁就可以启动;启动后, 变迁的所有输入P置空,而所有输出P放入Token。