petri网基础知识

Petri⽹预备知识死锁产⽣原因（1）互斥：同时争夺唯⼀资源（2）占⽤且等待（3）⽆抢占（4）循环等待死锁产⽣的原因及四个必要条件产⽣死锁的原因主要是：（1）因为系统资源不⾜。

（2）进程运⾏推进的顺序不合适。

（3）资源分配不当等。

如果系统资源充⾜，进程的资源请求都能够得到满⾜，死锁出现的可能性就很低，否则就会因争夺有限的资源⽽陷⼊死锁。

其次，进程运⾏推进顺序与速度不同，也可能产⽣死锁。

产⽣死锁的四个必要条件：（1）互斥条件：⼀个资源每次只能被⼀个进程使⽤。

这个资源只能是空闲待⽤或者分配给确定的任务，不可被两个或两个以上任务同时使⽤。

（2）请求与保持条件：⼀个进程因请求资源⽽阻塞时，对已获得的资源保持不放，更导致其他进程想获得资源⽽得不到资源，更导致进程瘫痪。

（3）不剥夺条件:进程已获得的资源，在末使⽤完之前，不能强⾏剥夺。

只有当正在使⽤这个资源的任务进程结束后，此资源才能被释放，被其他任务占⽤。

（4）循环等待条件:若⼲进程之间形成⼀种头尾相接的循环等待资源关系。

这四个条件是死锁的必要条件，只要系统发⽣死锁，这些条件必然成⽴，⽽只要上述条件之⼀不满⾜，就不会发⽣死锁。

死锁的解除与预防：理解了死锁的原因，尤其是产⽣死锁的四个必要条件，就可以最⼤可能地避免、预防和解除死锁。

所以，在系统设计、进程调度等⽅⾯注意如何不让这四个必要条件成⽴，如何确定资源的合理分配算法，避免进程永久占据系统资源。

此外，也要防⽌进程在处于等待状态的情况下占⽤资源。

因此，对资源的分配要给予合理的规划。

因此，前三个条件通常是满⾜的，⽽第四个条件可因资源的请求、分配和释放等因素，随时间⽽变化。

只要发⽣死锁，这四个条件必然都满⾜。

反之，只要有⼀个条件不满⾜，系统就不会发⽣死锁。

因此想要控制系统死锁的发⽣，必须破坏第四个条件即循环等待条件。

Petri⽹建模优势对系统中的并发、资源共享、冲突、相互抑制以及⾮确定性等有简单表⽰；（1）可以使⽤⾃顶向下和⾃底向上的设计⽅法，使系统具有不同的抽象层次；（2）从Petri ⽹模型可以直接⽣成控制代码；（3）良好定义的语义能够为系统的确认提供定性和定量的分析；（4）图形界⾯可给出系统的直观视图；（5） 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网是一种图形模型，用于描述并发系统中的并发过程和状态迁移。

它由物理学家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网可以用于描述和分析各种并发系统，如操作系统调度算法、并行计算系统、通信协议等。

Petri网：模型、理论与应用Petri网，也称为Petri图，是一种用来描述系统事件并发性、同步性和序列性的有向图。

Petri网模型被广泛应用于计算机科学、系统工程、控制工程和化学工程等领域，成为了目前最流行的并发系统建模工具之一。

Petri网的基本元素Petri网由一组有向弧和节点组成，包括以下几个基本元素：1.库所（Place）：代表系统中的状态或原料库存等。

2.变迁（Transition）：代表系统中的事件或操作，用于改变状态或消耗库存。

3.有向弧（Arc）：连接库所和变迁，表示状态之间的转移或原料的消耗。

4.标志（Marking）：库所内的标志表示库存的数量或状态。

Petri网的基本形式Petri网可以表示为二元组N=(P, T, F)，其中：1. P为库所的集合；2. T为变迁的集合；3. F为弧集合，由以下两种类型的弧组成：a)输入弧（Inhibitor arc）：表示一个库所是变迁的前置条件，但是库所中的标志数量必须为零。

b)常规弧（Regular arc）：表示一个库所是变迁的前置条件，库所中的标志数量可以为任意值。

Petri网的理论Petri网理论主要研究Petri网的语法、分析和应用。

Petri网具有以下特点：1. 易于可视化：Petri网可以用于描述具有并发性、同步性和序列性的系统，比传统的文本模型更直观。

2. 模型简单：Petri网只包含库所、变迁和有向弧三种基本元素，是一种简单、易于理解的模型。

3. 通用性强：Petri网模型可以表示各种类型的系统，例如工作流、协作系统、并发系统和控制系统等。

Petri网的应用Petri网在计算机科学、系统工程、控制工程和化学工程等领域的应用非常广泛。

1. 生产调度：Petri网可以应用于生产调度中，用于描述生产流程中的各个节点及其状态转移。

2. 工作流管理：Petri网可以应用于工作流管理中，用于描述任务分配、任务执行和任务完成的过程。