当前位置：文档之家 › Petri网基本概念和分析方法

Petri网基本概念和分析方法

  • 格式：pdf
  • 大小：416.77 KB
  • 文档页数：23

下载文档原格式

  / 23

合集下载

第七章Petri网基础

第七章Petri网基础

18
§7.2.1 共享资源模型6
p active1
p active 2
t request 1
prequesting 1
trequest2 pidle
p requesting 2
t start 1
pacces sin g 1
t start 2
pacces sin g 2 pbusy
事件之间的同步距离(synchronic distance)
公平性(fairness)
4
§7.1 Petri 网发展概述5
Petri网模型的主要分析方法依赖于： 可达树(reachability tree) 关联矩阵和状态方程(incidence matrix and state equation) 不变量(invariants) 分析化简规则 Petri网的的纵向扩展： 条件/事件(C/E)网
PetriNets-owner@daimi.au.dk]] PetriNets-request@daimi.au.dk]]
[[World Wide Web URL:
http://www.daimi.au.dk/PetriNets/pnl/]]
[[Read before posting:http://www.daimi.au.dk/PetriNets/pnl/faq.html]]
9
§7.2 Petri网模型简介1
直观理解什么是Petri网，它们如何应用。 一个PN的结构元素包括： 位置(place)：描述可能的系统局部状态(条件或状 况)，例如，队列、缓冲、资源等。 变迁(transition)：描述修改系统状态的事件、动 作，例如，信息处理、发送、资源的存取等。 弧(arc)：使用两种方法规定局部状态和事件之间 的关系：引述事件能够发生的局部条件状态；由 事件所引发的局部状态的转换。

Petri 网模型：性能分析,PetriSim,调研CORSAIR,软硬件协同设计

Petri 网模型：性能分析,PetriSim,调研CORSAIR,软硬件协同设计

第六次作业-SC11011042吴德云一、Petri网模型：性能分析，PetriSim1、Pretri网络概述Petri[1]网是对离散并行系统的数学表示。

Petri网是1960年代由卡尔·A·佩特里发明的，适合于描述异步的、并发的计算机系统模型。

Petri网既有严格的数学表述方式，也有直观的图形表达方式，既有丰富的系统描述手段和系统行为分析技术，又为计算机科学提供坚实的概念基础。

Petri网在数学上通常用符号的集合来表示,它可被描述为二元有向图。

Petri网包括四种基本元素:标记、位置、变迁和弧。

变迁描述改变系统状态的事件,分别用直线或矩形表示无延时的变迁和有延时的变迁。

变迁用于描述修改系统状态的事件,如计算机和通信系统的信息处理和发送、资源的存取等。

弧简单地连接一个位置和一个变迁或一个变迁和一个位置，由带箭头的直线来表示和描述对象通过系统的路径,弧尾部的箭头表示路径方向。

弧用两种方法确定局部状态和事件之间的关系:引述事件能发生的局部状态；由事件引起局部状态的转换。

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

Pet ri网以模型系统的组织结构和动态行为作为研究目标，它着眼于系统中可能发生的各种状态变化以及变化之间的关系，系统中状态的变化通过变迁的实施来完成。

变迁的可实施和实施规则是Petri网中最简单又最重要的规则,它规范了网络中各位置的标记点在变迁发生前后的变化规律，反映了网络状态的变化趋势使,Petri网能够有效地描述和模拟系统的动态特性。

2、基本Pertri网络模型图1基本pertri网络模型(1)顺序:如图1(a)所示，p1中包含一个标记,变迁t1启动,p1中的标记移到p2中,导致t2启动，p2中的标记移到p3中，也就是p1、p2和p3按照在图中出现的顺序执行。

用顺序执行可以模拟一个线性执行过程。

(2)同步:如图1(b)所示,变迁t1有多重输入弧,只有在p1和p2中都存在一个标记的时候,才能使t1启动,也就是p3在p1和p2执行结束之前不能开始执行。

petri网的原理及应用

petri网的原理及应用

Petri网的原理及应用1. 什么是Petri网Petri网是一种用于描述并发系统和并发性行为的图形化工具和形式化方法。

它由德国数学家Carl Adam Petri于1962年提出，被广泛应用于系统建模、并发系统分析、协议验证等领域。

Petri网可以模拟并发系统的并发行为、状态转换以及资源分配等关键方面，通过图形化的方式直观地展示系统的结构和行为，并支持形式化的数学分析。

2. Petri网的基本元素Petri网由以下基本元素组成：2.1. 位置（Place）位置表示系统中的状态或者条件，通常通过一个圆圈表示。

位置可以存储某种资源或者表示某种变量的取值。

2.2. 过渡（Transition）过渡表示系统中的某种事件或者操作，通常通过一个矩形表示。

过渡可以触发或消耗位置中的资源，改变系统的状态。

2.3. 弧（Arc）弧表示位置和过渡之间的联系，通常通过一条带箭头的线表示。

弧可以表示资源的流动或者触发条件的关系，连接位置和过渡。

2.4. 标识（Marking）标识是位置中的资源的数量，可以通过在位置内部的小圆圈中填写数字来表示。

标识表示系统的状态，在Petri网中可以不断变化。

3. Petri网的建模方法Petri网可以通过以下步骤完成建模：3.1. 确定系统的功能和行为首先，需要明确系统的功能和行为，清楚系统中的位置、过渡以及它们之间的关系。

例如，一个简单的交通信号灯系统中可以有位置表示红绿灯状态、过渡表示信号灯变换的事件或操作。

3.2. 绘制Petri网图根据系统的功能和行为，使用标识符绘制位置和过渡，并用弧表示它们之间的联系。

根据需要，可以使用不同的符号和颜色来表示不同类型的位置和过渡。

3.3. 设定初始标识确定初始状态下位置中的资源数量，填写在位置的小圆圈中。

这可以表示系统的初始状态，即Petri网的初始标识。

3.4. 定义触发条件和行为规则根据系统的功能和行为，定义位置和过渡之间的触发条件和行为规则。

Petri网详细介绍与学习

Petri网详细介绍与学习
随着技术的发展，Petri网模型也在不断演进和扩展，出 现了许多高级Petri网模型，如有色Petri网、时间Petri网 、概率Petri网等。这些模型在处理复杂系统方面具有更 强的表达能力和灵活性。
模型改进
针对传统Petri网的不足，研究者们不断尝试对其进行改 进和优化，以提高其适用性和性能。例如，通过引入新 的元素或规则，改进Petri网的表达能力；优化Petri网的 推理算法，提高其推理速度等。
有界性、安全性与死锁
01

03
有界性
Petri网中的每个库所至多 包含有限个标记，且每个 变迁最多可以消耗和产生 有限个标记。
安全性
Petri网中不存在死锁状态 ，即对于任意一个状态， 总存在一个后继状态。
死锁
当Petri网中存在一个状态 ，从该状态无法通过任何 变迁到达其他状态时，称 该状态为死锁状态。
Petri网与其他建模方法的融合
融合方法
为了更好地描述和分析复杂系统，研究者们尝试将 Petri网与其他建模方法进行融合。例如，将Petri网与 流程图、状态图等图形化建模方法相结合，可以更直 观地描述系统的结构和行为。
融合优势
通过融合不同的建模方法，可以取长补短，提高对复 杂系统的描述和分析能力。同时，这种融合也有助于 推动不同领域之间的交叉和融合，促进多学科研究的 开展。
实例分析学习
案例分析
分析不同类型Petri网的特点和适用场景，如同步Petri 网、时间Petri网和有色Petri网等。
通过学习经典的Petri网实例，深入理解Petri网的实际 应用和建模技巧。
对比不同Petri网实例的建模效果，提高对Petri网的实 际操作能力和应用水平。
实践应用学习

Petri网基本概念及介绍

Petri网基本概念及介绍

Petri网基本性能
• 有界性 通常，库所表示制造系统中的工件、工具、 托盘以及AGV的存放，还用于表示资源的可 利用情况，有界性是检查被Petri所描述的系 统是否存在溢出的有效尺度，防止确保不 会重复启动某一正在进行的操作。
Petri网基本性能
• 活性 • 对于一个变迁T，在任意标识m下，若存在 某一变迁序列Sr,该变迁序列的激发使得此 变迁T使能，责成该变迁是活的（Live）
Petri网基本概念及介绍
201512145
Petri网基本概念
• Petri网是一种网状模型，包括事件和条件两 个节点类型，在这样的图形中，分布着表 示状态资源或信息的托肯(Token)，按照触 发规则进行状态的演化，从而反映系统运 行的全部过程。事件一般用“变迁”表示， 条件用“库所”表示，托肯用库所内的小 黑点表示，库所和变迁之间用有向弧连接。
Petri网基本性能
• 可达性具体应用：
①系统按照一定轨迹运行，系统能否实现一 定状态，典型问题是生产调度计划的验证；
②要求达到一定状态，如何确定系统运行轨 迹； 第一个问题可描述为：给定Sr初始标识以及 期望达到标识Mr，验证之；
给定m0和mr,寻找sr使得m0[Sr>mr.
Petri网基本性能
• 有界性 有界性反映系统运行过程中对资源变量的 需求，它意味着，Petri网艺在其所有可能的 状态标识下，网的各位置节点中的托肯数 必为有界的。在理论分析时常可假定位置 容量为无穷，但在实际系统设计中，必须 使网络中的每个位置在任何状态下的标志 数小于位置的容量，这样才能保证系统的 正常运行，不至于产生溢出现象。
这是一个状态机
Petri网基本概念
Petri网基本概念
T2、T3 并发并且该网为一个标记图

第3章Petri网..

第3章Petri网..

（一） 基本定义
一个没有任何输入位置的迁移叫源迁 移，一个源迁移的使能是无条件的。 一个源迁移的引发只会产生令牌，而 不消耗任何令牌；一个没有任何输出 位置的迁移叫阱迁移，一个阱迁移的 引发只会消耗令牌，而不产生任何新 的令牌。
p2 t1 p3 t2 p4 t4
t3
p5
t5
位置/迁移Petri网---位置/迁移Petri网，简称为Petri网，形式上 定义为一个六元组PN=（P, T, F, K ,W, M0）= (N，K , W, M0)， 其中， ① N =（P，T，F）是一个Petri网结构； ② K：P→Z +{}是位置上的容量函数（Z +是正整数集合）， 规定了位置上可以包含的令牌的最大数目。对于任一位置p P, 以K(p)表示向量K中位置p所对应的分量，若K（p）= ， 表示位置p 的容量为无穷；
9
在Petri网的图形表示中，对于弧f ∈F，当W（f）>1 时，将W（f）标注在弧上，当W（f）= 1时，省略 W（f）的标注；当一个位置的容量有限时，通常将 K（p）写在位置p的圆圈旁。当K（p）= ∞时，通 常省略K（p）的标注。 容量函数和权函数均为常量1的Petri网称为基本 Petri网（简称基本网）或条件/事件网。容量函数 恒为无穷和权函数恒为1的Petri网称为普通Petri网， 简称为普通网。显然，基本网和普通网都是Petri网 的特殊情形。基本网和普通网可以用四元组PN= （P，T，F，M）来表示。
③ W：F→Z+，是流关系上的权函数，规定 了令牌传递中的加权系数。对于任一弧f ∈F， 以W (f)表示向量W中弧f所对应的分量； ④ M：PZ（非负整数集合）是位置集合 上的标识向量。对于任一位置pP, 以M(p) 表示标识向量M中位置p所对应的分量，并 且必须满足M(p)K(p)。M0是初始标识向 量。

自动制造系统的Petri网结构分析和控制器设计

自动制造系统的Petri网结构分析和控制器设计

自动制造系统的Petri网结构分析和控制器设计自动制造系统的Petri网结构分析和控制器设计摘要：自动制造系统是现代工业中一种高度智能化和自动化的生产方式。

Petri网作为一种形式化描述和分析系统行为的工具，被广泛应用于自动制造系统中的建模和控制。

本文介绍了自动制造系统中的Petri网结构分析方法和控制器设计技术，并通过一个实例说明了其在实际应用中的有效性。

关键词：自动制造系统；Petri网；结构分析；控制器设计1.引言自动制造系统是现代工业中应用广泛的一种高度智能化和自动化的生产方式。

其核心目标是提高生产效率、降低成本，并保障产品质量。

为了实现这一目标，自动制造系统通常需要一个有效的控制系统来监测和调度各个生产环节，以实现流程的自动化控制。

Petri网作为一种形式化描述和分析系统行为的工具，被广泛应用于自动制造系统中的建模和控制。

2.Petri网的基本概念Petri网是Petri于1962年提出的一种描述系统并发行为的图形工具。

它由一组标记、过渡和弧线组成。

标记表示系统在某一时刻的状态，过渡表示系统的活动，弧线则表示标记和过渡之间的关联关系。

Petri网描述了系统状态在不同活动之间的转换关系，并且能够对系统的行为进行形式化的分析。

3.Petri网在自动制造系统中的应用在自动制造系统中，Petri网广泛应用于系统的建模和控制。

通过将自动制造系统抽象为Petri网，可以清晰地描述系统的各个组成部分以及它们之间的关系。

特别是在多任务的情况下，Petri网能够有效地处理不同任务之间的并发和冲突关系，提高系统的并行处理能力。

同时，Petri网的结构分析方法也可以帮助我们深入理解自动制造系统的行为，发现系统中的潜在问题，并进行系统性能的评估和优化。

4.Petri网结构分析方法Petri网的结构分析方法主要包括有向图分析、路径分析和状态空间分析。

有向图分析是最简单直观的分析方法，可以帮助我们了解Petri网的结构特征和系统行为。

petri网课件第1章2

petri网课件第1章2

命题
权函数为１的Ｐ／Ｔ系统中两互补库所中的 托肯总数永远是一个常量。 •常量为Ｍ０（ｓ）＋Ｍ０（ｓ） •即不会增加新的托肯（当网系统动态变化， 即ｔ发生后） 证明
证明
证： ｓ＝ｓ ∧ｓ ＝ ｓ ． ． ． ． ⇒ｔ∈ ｓ⇔ｔ∈ｓ ∧ｔ∈ｓ ⇔ｔ∈ ｓ ⇒ｓ获得一个托肯，则ｓ失去一个托肯
ｓ失去一个托肯，则ｓ获得一个托肯 ｓ— 资源数 ｓ— 可用空间数
４．当∀ｓ∈Ｓ，Ｋ（ｓ）＝∞时，只要考虑第一个条件
．
例：
M0=(1,1,0,3,0,1,3) → (0,1,1,0,0,1,3) → (0,2,0,3,0,1,3)
t4
t2
t3
→ (0,2,0,2,1,0,3) →… …
三、网系统分类
根据Ｋ及Ｗ分成三类： １ ．基本网系统（ＥＮ系统） ２ ．库所／变迁网（Ｐ／Ｔ网） ３ ．库所／变迁系统（Ｐ／Ｔ系统）
２，４ — — 机器
３— — 工人
显然，网系统越高级，节点（库所或变迁）也就越 少。Σ４ 还可对应更简单的Ｐｒ／Ｔ系统。
解决节点爆炸
１ ．高级网系统 ２ ．分层模拟方法 ３ ．辅助工具
F-1={(x, y)|(y, x)∈ F}
定义１．４
•|X|<∞, N称为有限网 我们主要讨论有限网 •若(X, F)是个连通图，则N称为连通网 ↓ 表示N=(S, T; F)相应的有向图
定义１．５
N=(S, T; F) 设s∈S, 若有s′∈ S, 使得
1. s′ =s ∩s′ = s, 则s′和s是 互补库所 常用s表示s的互补库所
． ．
变迁规则
Ｍ（ｓ）－Ｗ（ｓ，ｔ） Ｍ（ｓ）＋Ｗ（ｔ，ｓ） Ｍ（ｓ）－Ｗ（ｓ，ｔ）＋Ｗ（ｔ，ｓ） Ｍ（ｓ） 若ｓ∈ ｔ－ｔ 若ｓ∈ｔ．－．ｔ ． ． 若ｓ∈ ｔ∩ｔ 若ｓ∉．ｔ∪ｔ．

Petri网详细介绍与学习

Petri网详细介绍与学习

P1
P2
P3
t1
t2
t6
P4
P5
Pห้องสมุดไป่ตู้0
t7
t8
t3
t4
P6 P8
P7
t5
P9
30
特殊Petri网

31
Petri网的行为性质

32
Petri网的行为性质

33
例子：
Petri网的行为性质
a图有界，b图无界，P5的令牌可以无限增多。
34
Petri网的行为性质
有界性是一个非常重要的特性,它保证系统在运行过程 中不会需要无限的资源.
(6)系统可靠性分析 系统的可靠性不仅包括硬件的可靠性、也包括软件可靠性.利用 随机Petri网对系统进行可靠性分析，对软件复用、软件可靠 性分析。
4
Petri网结构基本定义

5
Petri网结构基本定义
三元组N=（P，T；F）构成网（net）的充分必要条件：
① P∩T=ф ，规定了位置和变迁是两类不同的元素；
Remove from buffer Buf
consume
Producer
Consumer
28
实例二生产者、消费者问题的Petri网描述

produce
Put in buffer
Remove from buffer Buf
consume
Producer
Consumer
29
实例三 Petri网的变迁
21
Petri网模型结构
Petri网具有丰富的结构描述能力，下图给出了顺序、并发、 冲突、混惑结构下的Petri网模型。
22

第三部分Petri网的分析方法

第三部分Petri网的分析方法

变迁发生序列与Petri网语言
定义3.5.设PN=(P,T;F, M0)为一个Petri网。L是PN产生的L-型 （ G-型， T-型， P-型）语言。对于标注函数 : T→： （1）若=T，且tT: (t)=t，则称L是PN产生的L-型（ G型， T-型， P-型）无标注语言，记为Lf（ Gf， Tf， Pf） （2）若tT: (t)（表示空串），则称L是PN产生的L-型 （ G-型， T-型， P-型）无空标注语言，记为L（ G， T， P）； 否则称L是PN产生的L-型（ G-型， T-型， P-型）含空标注语言， 记为L （ G ， T ， P ）。
变迁发生序列与Petri网语言
终止符集
L-型 G-型 T-型 P-型
无标注类 Lf Gf Tf Pf
标注
无空标注类 L G T P
含空标注类 L G T P
变迁发生序列与Petri网语言
CFL
RL
PNL
CSL
PNL同Chomsky体系中各型语言的关系
每种正规语言（RL）都是Petri网语言（PNL） 每种Petri网语言都是上下文有关语言（CSL） Petri网语言类同上下文无关语言类（CFL）是两个相交但互不包含的语言类
Pref(L0(PN))=L0(PN)
变迁发生序列与Petri网语言
在形式语言理论中，Pumping引理是正规语言和上下文无关语言的一个重 要性质。
定理3.4.设PN=(P,T;F, M0)为一个有界Petri网， L0(PN)。如果 |||R(M0)|，则可写成=xyz的形式，其中x,y,zT*,|xy| |R(M0)|且|y|1，使得对任意非负整数i，都有xyiz L0(PN)。
定理3.4. 有界Petri网PN的两个变迁t1和t2处于公平关系的充分必 要条件是在RG(PN)的每条有向回路C中， t1是其中的一条弧的旁标 当且仅当t2也是其中一条弧的旁标。

petri网 (2)

petri网 (2)

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网的基本概念
p P：K(p)= f F：W(f)=1 那么，就变成形如定义1.4给出的网系统（原型Petri网）

对于一个P/T系统，如果规定各个库所的容量都为无穷大，即取消库所集上 的容量函数而保留有向边集上的权函数，就得到一种介于原型Petri网和 P/T系统之间的网系统模型Σ=(P,T;F,W,M0)，称这种模型为加权Petri网 （weighted Petri net） P/T系统并不比原型Petri网具有更强的模拟能力，凡是可以用P/T系统对 其建模的实际系统，也可以用原型Petri网对其建模。每一个P/T系统都可 以转换为一个行为等效的Petri网
（5.1）对于t T，M[t>的引发条件
p t t : M ( p ) W (t , p ) K ( p ) p t t : M ( p ) W (t , p ) W ( p, t ) K ( p) p t : M ( p) W ( p, t )


Petri网按引发规则使得事件驱动状态的演变，从而反映系统动态运 行过程
网与网系统
p1 c1
t1
t3
例：网N1=(P1,T1; F1)，其中
P1 = {p1, p2, c1, c2, B} T1={t1, t2, t3, t4} F1={(p1, t1),(t1, p2), }
B p2 c2
网与网系统

定义1.4. 四元组PN=(P,T;F,M0)称作Petri网（网系统）当且仅当
（1） N=(P,T;F)为一个网； （2）映射M:P →{0,1,2,}(非负整数集)称为网N的一个标识，其中，M0是初始 标识；
（3）引发规则：
（3.1）变迁t T称为使能的当且仅当： p •t：M(p)1，记作M[t>; （3.2）在M下使能的变迁t可以引发，引发后得到一个新的标识M’，记作M[t>M’,对 pP，有

Petri网：模型、理论与应用

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网可以应用于工作流管理中，用于描述任务分配、任务执行和任务完成的过程。

第二章 Petri网的基本概念及性质

第二章 Petri网的基本概念及性质

证：(1) 由于M R(M0)，所以M’ R(M): M’
R(M0) ，从而R(M) R(M0) 。 同理可证(2)。
可达性

定义2.3. 设PN=(P,T;F, M0)为一个Petri网，M R(M0)。如果M’ R(M0)，都有M R(M’ )，则 称M为PN的一个可返回标识或一个家态（home state）。 定义2.4. 设PN=(P,T;F, M0)为一个Petri网。如果M0 是一个家态，则称PN为可逆网系统（reversible net system），或称可回复系统。
j-1
#(σ, t2) =0→#(σ, t1) k1 t2 σj, j k1.
持续性

定义2.11.设PN=(P,T;F, M0)为一个Petri网。如果对 任意 M R(M0) 和任意t1,t2T (t1 t2)，有 ( M[t1> M[t2>M’)→ M’[t1> 则称PN为持续网系统。
可达性 有界性和安全性 活性 公平性 持续性
可达性

可达性是Petri网的最基本的动态性质，其余各种性质都要通过可达 性来定义 定义2.1. 设PN=(P,T;F,M)为一个Petri网。

如果存在tT，使M[t>M’，则称M’为从M直接可达的
如果存在变迁序列t1, t2, t3,,tk和标识序列M1,M2, M3,,Mk使 得
M[t1>M1[t2>M2,,Mk-1 [tk>Mk 则称Mk为从M可达的
从M可达的一切标识的集合记为R(M)，约定M R(M)
(2.1)
如果记变迁序列t1, t2, t3,,tk为，则(2.1)式也可记为M [ >Mk
可达性
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

(b) t1, t2 是并发的, 且若 t2 在 t1 前点火,
则 t1 与 t3 冲突.
图 1.5. 对称与非对称
Petri 网的可达图是其可能状态和使能迁移关系的图表示.
(a) 一个 Petri 网
(b) 上述网的可达图 图 1.6. 可达图
3
北京师范大学信息科学学院
知识工程研究中心
二. Petri 网的行为
M(p) § M £(p). 对一个迁移 t, 用 Mt 记可以使能的最小状态. 定理. Petri 网(N, M0)中的迁移 t 是 L1-活性的 ‹ Mt 是可覆盖的.
5
北京师范大学信息科学学院
知识工程研究中心
2.6 持续性 Petri 网(N, M)称为持续的, 如果(N, M)中任何两个使能迁移 t1, t2, t1 的点火不 会改变 t2 的使能性. 例如, 所有标记图都是持续的, 但持续的网不一定都是标记图.
北京师范大学信息科学学院
知识工程研究中心
Petri 网: 基本概念和分析方法
记号: N = {0, 1, 2, … }, N+ = {0, 1, 2, … }.
一. 基本概念
一个 Petri 网由五个部分组成 PN = (P, T, F, W, M0), 其中: P 是位置(place)的有限集合; T 是迁移(transition)的有限集合; P … T = «, P » T ∫ «; F Œ (P ä T) » (P ä T)是有向弧的集合; w : F ö N+是弧的权函数; M0 : P ö N 是初始标记(初始状态). 注. 不带初始状态的 Petri 网记为 N = (P, T, F, W), 带有初始状态 M0 的 Petri 网则记为(N, M0). 若 PN 是一个 Petri 网, 则映射 M : P ö N 称为一个状态. 对 p œ P, 若 M(p) = k, 则称位置 p 标记有 k 个符号(token).
M(p) - w(p, t)
若 p 是 t 的输入位置
M £(p) = M(p) + w(t, p)
若 p 是 t 的输出位置
M(p)
若 p 为其它位置
则称 t 被点火(击发), 且系统从状态 M 迁移到状态 M £, 记为 M t M £.
例 1. 化学反应 2H2 + O2 ö 2H2O 的 Petri 网表示.
且对" p œ P, M £(p) ¥ M ££(p), 则对满足 M £(p) > M ££(p)的 每个 p œ P, 用w代替 M £(p). Step 2.4.3) 将 M £做为一个新节点, 并从 M 到 M £画一条标记为 t 的 有向弧. 例 1. 考虑图 3.1 所表示的 Petri 网. 根据上述算法, 我们可以画出其可覆盖 树(图 3.2).
例 3. 迁移 t2, t3 是并发的, 而此网是一个标记图.
2
北京师范大学信息科学学院
知识工程研究中心
图 1.4. 并发
既有并发迁移又有冲突迁移的 Petri 网称为混合型的. 并发迁移与其它迁移 可以是对称的(同时冲突), 也可以是非对称的.
(a) t1, t2 是并发的, 而且都与 t3 冲突.
图 2.1. 活性网
活性概念可以分层. 设 t 是 Petri 网(N, M0)中的一个迁移. 则: (1) 若对 L(M0)中任何点火序列, t 都不能被点火, 则称 t 是 L0-活性的(死的);
4
北京师范大学信息科学学院
知识工程研究中心
(2) 若对 L(M0)中的某个点火序列, t 至少能被点火一次, 则称 t 是 L1-活性的 (潜在可点火的);
图 1.2. 饮料贩卖机的 Petri 网模拟.
若存在某个位置 p, p 是至少两个迁移的输入位置, 则称此网为非确定的, 或 者根据特定的应用领域, 称为冲突, 决策或者选择等.
图 1.3. 冲突, 决策, 选择
两个迁移 t1, t2 œ T 称为并发的, 如果 t1, t2 是因果独立的, 即两者都可以先后 点火或者并行点火.
同, 将 M 标记为“old”, 并继续再选一个标记为“new”的节点. Step 2.3) 若在状态 M 下, 没有任何使能的迁移, 将 M 标记为“dead-end”. Step 2.4) 对状态 M 下每个使能的迁移 t, 做:
Step 2.4.1) 得到状态 M 下迁移 t 点火后迁移的新状态 M £. Step 2.4.2) 在从根节点到 M 的道路上, 若存在 M ££, 使得 M £ ∫ M ££,
" n œ N, w > n, w ≤ n = w, w ¥ w. 设(N, M0)是 Petri 网, (N, M0)的可覆盖树 T 按照以下算法生成. 可覆盖树生成算法. Step 1) 将初始状态设为根节点, 并标记为上“new”. Step 2) 如果当前存在标记为“new”的节点, 做:
Step 2.1) 选择一个标记为“new”的节点 M. Step 2.2) 若状态 M 与从根节点到 M 的道路上的某个节点表示的状态相
Petri 网可达性问题. 对(N, M0)的任何状态 M, 是否 M œ R(M0) ? 2.2 有界性 设 k œ N. Petri 网(N, M0)称为 k-有界的, 如果对任何位置 p 和状态 M œ R(M0),
M(p) § k. (N, M0)称为安全的, 如果它是 1-有界的.
2.3 活性 Petri 网(N, M0)称为活性的, 如果在任何状态 M œ R(M0)下, 通过适当的点火 序列后, 每个迁移最终都可以被点火. 在活性 Petri 网中, 无论怎样选取点火序列, 都保证不会出现死锁. 例如, 下 面的通信协议的 Petri 网表示是活性的:
图 2.4. 同步距离 6
北京师范大学信息科学学院
知识工程研究中心
2.8 公平性 设(N, M)是 Petri 网, 称两个迁移 t1, t2 处于有界公平关系(bounded fair, B-fair) 下, 如果一个可点火而另一个不可点火的最大次数是有界的. Petri 网(N, M)称为 有界公平的(B-fair), 如果该网中的任何迁移对都处于有界公平关系. 一个点火序列s称为无条件公平的, 如果s是有限的, 或者网中的每个迁移 在s中出现无限次. Petri 网(N, M)称为无条件公平的, 如果每个点火序列s都是无 条件公平的. 定理. (1) 任何 B-fair 网是无条件公平的. (2) 任何有界无条件公平网是 B-fair 网. 例如, 图 2.4 中的网既不是 B-fair 网, 也不是无条件公平网, 因为 t3, t4 不出现 在无限点火序列s = t2 t1 t2 t1......中. 图 2.3 中的网是无条件公平网, 但不是 B-fair 网, 因为若 p2 中的符号个数无 界, 那么 t2 点火而其它迁移不点火的次数也无界. 下面的图 2.5 是一个 B-fair / 无条件公平网
7
北京师范大学信息科学学院
知识工程研究中心
三. Petri 网的分析方法
3.1 可覆盖树方法 Petri 网的可覆盖树表明了该网中所有可能到达的状态(树的节点)和使能的 迁移(弧的标记). 记号: 为了表示无界标记, 用w表示“无限”正整数, 即w满足条件:
(3) 若对任何 k œ N, 关于 L(M0)中的某个点火序列, t 至少能被点火 k 次, 则 称 t 是 L2-活性的;
(3) 若在 L(M0)中的某个点火序列中, t 可以不定地出现, 则称 t 是 L3-活性的; (4) 若对每个 M œ R(M0), t 都是 L3-活性的, 则称 t 是 L4-活性的(活性的). 对 k = 0, 1, 2, 3, 4, Petri 网(N, M0)称为 Lk-活性的, 如果该网中的每个迁移都 是 Lk-活性的. 显然有:
迁移(点火)法则. 设 M : P ö N 是 Petri 网(N, M0)的一个状态, t œ T. (1) 迁移 t 称为在状态 M 下使能的(enable), 如果对 t 的任何输入位置 p, 有:
M(p) ¥ w(p, t). (2) 设迁移 t 在状态 M 下为使能的, M £是如下定义的状态: 对 p œ P,
图 3.1. 一个 Petri 网(N, M0), M0 = (1 0 0).
8
北京师范大学信息科学学院
知识工程研究中心
图 3.2. 上述 Petri 网的可覆盖树
从 Petri 网(N, M0)的可覆盖树 T 出发, 可以研究该网的性质. 典型结果有: (1) (N, M0)是有界的(所以 R(M0)是有限的) ‹ w不出现在 T 的任何节点的标
L4-活性 fl L3-活性fl L2-活性 fl L1-活性 对 k = 1, 2, 3, Petri 网(N, M0)称为严格 Lk-活性的, 如果(N, M0)是 Lk-活性的, 但不是 Lk+1-活性的. 例如, 图 2.2 中的网不是活性的. 如果 t1 先点火, 任何迁移都不能再点火了.
图 2.2. 安全的, 严格 L1-活性的, 但非活性的 Petri 网.
2.7 同步距离
图 2.3. 持续的, 但非标记图
设(N, M)是 Petri 网, s是一个点火序列, t 是一个迁移. 用s-(t)记迁移 t 在s中点
火的次数. 对(N, M)中的两个迁移 t1, t2, t1, t2 之间的同步距离定义为:
d12
=
max s
|
s-(t1)
-
s-(t2)
|.
例如, 在下图 2.4 中, d12 = 1, d34 = 1, d13 = ¶.
号中. (2) (N, M0)是安全的 ‹ 只有 0 和 1 出现在 T 的任何节点的标号中. (3) 迁移 t 是死的 ‹ 在 T 的任何弧的标记上都不出现 t. (4) 若 M 是从 M0 可达的, 则 T 中存在一个节点 M £, 使得 M £ ¥ M. 对于有界的 Petri 网(N, M0), 其可覆盖树 T 也称为可达树, 因为 T 包含了(N, M0)的所有可达状态. 在这种情况下, 有关(N, M0)的所有行为分析问题都可以通 过可达树来完成. 可覆盖树方法本质上是一种穷举方法, 因此它的主要缺点是复 杂性问题. 若 Petri 网(N, M0)不是有界的, 则由于引进符号w时丢失了信息(同一个符号 可表示不同内容), 所以不能单独用可覆盖树方法求解可达性和活性问题. 例 2. 图 3.3 中的两个 Petri 网活性不同, (a)中的网是活的, 而(b)中的网在 t1, t2, t3 点火后, 再没有使能的迁移.