petri网基础知识

PETRI NET一、网和网系统一般系统模型均由两类元素构成：表示状态的元素和表示变化的元素。

例如用于描述程序系统的程序设计语言用变量表示状态，用语句，特别是赋值语句，表示变化，Petri网也不例外。

Petri网的状态元素和变化元素分别称为S_元素和T_元素，也简称为S_元和T_元。

怎样把两类元素联系起来构成完整的系统呢？不同的模型采用不同的方法。

控制流是人脑思维方式的反映，分时系统则是对意识流的模拟。

人脑的思维方式（远比控制流的方式复杂）是人脑固有的，控制流却并不是物理系统固有的，所以不应该以任何方式把控制流作为固有成引入系统模型。

Petri网对S_元和T_元同等结待，两者是“分体”的，平等的。

实际上，S_元由T_元改变，而T_元由S_元描述，两者互相依赖。

Petri网起源于对信号传输的描述，所以适合于描述以资源流动为特征的系统。

T_元引起S_元中资源的流动。

联系T_元和S_元的是两者之间的流关系，用F表示。

Petri网中没有任何形式的固有控制，既不含冯.诺依曼式的控制流，也不用全局状态或全局时间变相控制。

自然规律决定了每个变迁与哪些状态元素有关，也决定其相关方式。

变迁是Petri网对T_元的称呼。

变迁之间通过共享的S_元联系在一起，构成网状的系统结构。

只有在全局或局部控制是应用问题的组成部分时，控制信息才作为资源出现在Petri网中。

以自然的依赖关系描述变迁之间的联系(从下而的例子中去体会这句话)，使Petri网具有区别于其他模型的许多特点。

除可实现性外，最突出的是Petri网适合于在各种抽象级别上描述并分析异步并发系统，而且由此产生了一整套理论。

为应用系统建立Petri网模型，首要的就是决定什么是系统的变迁，什么是系统的库所。

但变迁和库所的划分有时并不总是这么明确。

变迁和库所的概念有时能帮助我们认清事物的本质。

正确区分变迁和库所，有时能对问题的求解起重要作用。

二、Petri 网的基本定义定义1：三元组(,;)N S T F =称为有向网(directed net ，简称为网(net))的充分必要条件是：（1）∅=⋂T S ；（2）∅≠⋃T S ；（3）S T T S F ⨯⋃⨯⊆；（4）T S F cod F dom ⋃=⋃)()(,其中}),(:|{)(F y x y x F dom ∈∃=}),(:|{)(F y x x y F cod ∈∃=它们分别为F 的定义域和值域。

8.4.1 Petri网基本知识简介Petri网库所 place 变迁 transistionPetri网由两类元素组成：库所（place）和变迁（transistion），前者表示状态，后者反映状态的变化。

变迁的作用是改变系统的状态，库所的作用则是决定变化能否发生。

两者的这种相互依赖关系用有向弧（流关系）表示。

网是系统的静态结构。

图8-22给出了一个Petri网和网系统的例子。

图中用圆圈表示库所，用短横表示变迁（也有用方框表示的）。

库所中的黑点称为托肯（token），用以表示某类资源，反映了系统的局部状态，托肯在库所中的分布，给出了各状态元素的初态，称为初始标识（initial marking），反映出系统初始情况下的全局状态。

如果库所中的托肯数不多于一个，与布尔型变量类似的库所只有两种状态：有托肯（成真）和无托肯（成假）。

我们把这样的网系统称为条件（condition）/事件（event）系统，简称C/E系统。

当网系统中的托肯在网中流动时，就反映了网的动态行为。

托肯是沿有向弧指示的方向流动的。

图8-22中，对于变迁e3来说，从库所b1有一条指向它的有向弧，用（b1，e3）表示，称为输入弧；同时还有另外两条输出弧，用（e3，b3）、（e3，b4）表示。

网论中将b1称为e3的输入库所，b3、b4称为它的输出库所，由输入库所组成的集合叫输入库所集，又称为前集，记为*e3={b1}；由输出库所组成的集合叫做输出库所集，又称后集，记为e3*={b3，b4}。

同理，对于库所b1，它的输入变迁集（前集）为*b1={e2}，输出变迁集（后集）为b1*={e1，e3}。

一个变迁，如果它的每一个输入库所都包含至少一个托肯时，则这个变迁有发生权，当这个变迁发生时，将导致在其每个输入库所中减少一个托肯，而在每个输出库所中增加一个托肯。

图8-22中，变迁e3的发生将“消耗”b1中的一个资源，同时产生b3类和b4类各一个资源，这就是变迁规则。

Petri 网的基本理论1. 基本定义定义1.1 一个Petri 网（结构）N 是一个四元组),,,(W F T P ，P 和T 分别成为库所和变迁的集合，P 和T 非空、有限且不相交。

即φφφ≠≠T ,≠T P P ,。

φ≠⨯⨯⊆)()(P T T P F 称为流关系或有向弧的集合。

N →⨯⨯)()(:P T T P W 是一个映射，该映射为每一条弧分配一个权值，即若,F f ∈0)(>f W 若F f ∉，0)(=f W 。

称W 为Petri 网N 的权函数。

从图论上讲，Petri 网是一种双枝有向图，库所和变迁成为Petri 网的节点。

用图形表示Petri 网时，库所用圆圈表示，变迁用矩形或杠表示。

库所和变迁之间用有向弧连接，同一类型的节点间不能用有向弧连接。

定义1.2 若1)(,=∈∀f W F f ，Petri 网),,,(W F T P N =成为普通网。

否则N 称为一般网。

一个普通网可记作),,(F T P N =。

定义1.3 若1),(,),(=∈∀t p W F t p ，Petri 网称为PT-普通网。

定义1.4 Petri 网),,,(W F T P N =的标识M 是一个从P 到N 的映射。

),(0M N 称为网系统或标识网，0M 称为N 的初始标识。

在不引起混淆的情况下，简单称),(0M N 为Petri 网，),(0M N 有时也写成),,,,(0M W F T P 。

库所中的标识用称之为托肯的小黑点表示。

当托肯数较多时直接用数字表示。

定义1.5 令P p ∈是Petri 网),,,(W F T P N =的库所。

当且仅当0)(>p M 时称p 在M 下是被标记的。

当且仅当D 中至少有一个库所被标记时，称库所集P D ⊆在M 下是被标记的。

称∑∈=D p p M D M )()(为库所子集D 在M 下的托肯总和。

定义 1.6 令T P x ∈是Petri 网),,,(W F T P N =的节点。

petri⽹基础知识Petri⽹的概念：Petri⽹是对离散并⾏系统的数学表⽰。

经典Petri⽹：经典的Petri⽹是简单的过程模型，由两种节点：库所和变迁，有向弧，以及令牌等元素组成的。

Petri⽹的结构：（⼀）、形式化的定义：1.petri⽹的元素：库所（place）圆形节点变迁（transition）⽅型节点有向弧（connection）它是具有⽅向的，是库所和变迁之间的有向弧令牌（token）它是库所中的动态对象，可以从⼀个库所移动到另⼀个库所。

2.Petri⽹的规则：1.有向弧是有⽅向的2.两个库所之间变迁是不允许有弧的。

3.库所可以拥有然⼀数量的令牌。

4.O⾏为如果⼀个变迁的每个输⼊库所（input place）都拥有令牌，该变迁即为被允许(enable)。

⼀个变迁被允许时，变迁将发⽣(fire)，输⼊库所(input place)的令牌被消耗，同时为输出库所(output place)产⽣令牌。

5. 变迁的发⽣是原⼦的，也就是说，没有⼀个变迁只发⽣了⼀半的可能性。

6. 有两个或多个变迁都被允许的可能，但是⼀次只能发⽣⼀个变迁。

这种情况下变迁发⽣的顺序没有定义。

7. 如果出现⼀个变迁，其输⼊库所的个数与输出库所的个数不相等，令牌的个数将发⽣变化，也就是说，令牌数⽬不守恒。

8.petri⽹事静态的也就是说，不存在发⽣了⼀个变迁之后忽然冒出另⼀个变迁或者库所，从⽽改变Petri⽹结构的可能。

9. Petri⽹的状态由令牌在库所的分布决定。

也就是说，变迁发⽣完毕、下⼀个变迁等待发⽣的时候才有确定的状态，正在发⽣变迁的时候是没有⼀个确定的状态的。

3.petri⽹的类型：（1）基本petri⽹：每个库所容量为1，这样库所可称为条件，变迁可称为事件。

故⽽⼜称为条件/事件系统C/E CE模型的基本关系顺序关系：并发关系互斥冲突关系：异或关系：死锁关系：（2）低级petri⽹：库所容量和权重>=1的任意整数，称为库所/变迁⽹P/T（3）定时petri⽹：将各事件的持续时间表在库所旁边，库所中新产⽣的标记经过⼀些事件后加⼊到⽹中，或时标在变迁上，经过时间延迟后发⽣。

1.一个经典的Petri网由四元组（库所，变迁，输入函数，输出函数）组成。

2.如果一个变迁的每个输入库所（input place）都拥有托肯，该变迁即为被允许(enable)。

一个变迁被允许时，变迁将发生(fire)，输入库所(input place)的托肯被消耗，同时为输出库所(output place)产生托肯。

3.高级模型：为了解决经典Petri网中的问题，研究出了高级Petri网，在以下方面进行了扩展：o 令牌着色一个令牌通常代表具有各种属性的对象，因此令牌拥有值（颜色）代表由令牌建模的对象的具体特征，如一个令牌代表一个工人（张三，28岁，经验3级）。

o 时间为了进行分析，我们需要建模期间，延迟等，因此每一个令牌拥有一个时间戳，变迁决定生产出的令牌的延迟。

（这类Petri网模型规定每个变迁都具有有限的引发时延，其触发规则被修改为:每一个触发变迁都有一个时延过程;一个变迁一旦使能必须立即触发。

）o 层次化构造一个复杂性与数据流图相当的Petri网的机制。

子网是由库所，变迁和子网构成的网络。

o 时序增加时序逻辑的定义，更好的描述行为过程4.两个库所或变迁之间不允许有弧5.有两个变迁都被允许的可能，但是一次只能发生一个变迁6.Petri网络是静态的7.Petri网的状态由托肯在库所的分布决定8.两个变迁争夺一个托肯的情形被称之为冲突9.多个弧连接两个节点的情况。

在输入库所和变迁之间的弧的个数决定了该变迁变为被允许需要的令牌的个数。

弧的个数决定了消耗/产生的令牌的个数10.petri网基本概念：Petri网是一种用有向图及称为初始标识的初始状态表示的特殊的系统模型其中有向图由库所变迁以及从库所到变迁或者从变迁到库所的有向弧组成，称为Petri网结结构。

标识是一个m维数组(m为库所个数)，它的一元素对应一库所，取值为非负整数。

标识代表系统的状态。

11.不同类型的资源相应地，变迁的发生就可能不只是简单地复制和传递令牌，而是要对从输入库所取来的令牌经过加工，变成新颜色的令牌后再传递给输出库所这就是有色Petri网的两个特别之处:令牌是有颜色的，变迁的发生可以改变令牌的颜色。

Petri网Petri网是一种图形模型，用于描述并发系统中的并发过程和状态迁移。

它由物理学家Carl Adam Petri在1962年提出，是一种形式化的工具，用于模拟和分析各种并发系统。

1. Petri网的基本概念Petri网由两种基本元素组成：库所（Place）和变迁（Transition）。

库所可以看作是存储资源的位置，变迁表示发生的事件。

这两种元素都是用圆圈表示，并使用有向弧线连接。

•库所：用一个圆圈表示，通常用于存储资源或表示系统的状态。

每个库所都有一个或多个标记（token），表示资源的数量或状态。

•变迁：用矩形或虚线矩形表示，表示一个事件或活动。

变迁可以使得库所中的资源发生变化，即在库所之间转移标记。

此外，Petri网还有一些辅助元素：•弧线：表示库所和变迁之间的关系。

用于指示资源的流动或变迁的触发条件。

•权重：用于限制资源的流动或变迁的触发条件。

2. Petri网的特性Petri网具有以下几个重要的特性：2.1 可视化Petri网通过图形化的方式描述并发系统，并使用直观的图形元素表示资源和事件之间的关系。

这种可视化的特性使得Petri网更容易理解和分析，并且可以有效地交流和共享。

2.2 模块化Petri网可以进行模块化设计，即将一个复杂的系统分解为多个简单的子系统，并使用库所和变迁进行连接。

这样可以方便地对子系统进行分析和调试，并且可以更好地理解整个系统的结构和功能。

2.3 并发性Petri网能够描述并发系统的行为。

通过在变迁周围放置多个库所，可以实现多个资源之间的并发操作。

这样可以提高系统的并发性，提高系统的性能和效率。

2.4 死锁检测Petri网可以用于检测系统中的死锁问题。

当库所和变迁之间的资源流动形成闭环时，可能会导致死锁的发生。

通过分析Petri网的结构和标记状态，可以检测到潜在的死锁情况，并采取相应的措施解决问题。

3. Petri网的应用领域Petri网在各个领域都有广泛的应用，以下是其中一些典型的应用领域：3.1 并发系统分析Petri网可以用于描述和分析各种并发系统，如操作系统调度算法、并行计算系统、通信协议等。