Petri网

Petri网是对离散并行系统的数学表示。Petri网是1960年代由卡尔·A·佩特里发明的，适合于描述异步的、并发的计算机系统模型。Petri网既有严格的数学表述方式，也有直观的图形表达方式，既有丰富的系统描述手段和系统行为分析技术，又为计算机科学提供坚实的概念基础。

由于Petri网能够表达并发的事件，被认为是自动化理论的一种。研究领域趋向认为Petri 网是所有流程定义语言之母。

* 经典Petri网

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

o Petri网的结构

(1) Petri网的元素：

+ 库所（Place）圆形节点

+ 变迁（Transition）方形节点

+ 有向弧（Connection）是库所和变迁之间的有向弧

+ 令牌（Token）是库所中的动态对象，可以从一个库所移动到另一个库所。

(2) Petri网的规则是：

+ 有向弧是有方向的

+ 两个库所或变迁之间不允许有弧

+ 库所可以拥有任意数量的令牌

o 行为

如果一个变迁的每个输入库所（input place）都拥有令牌，该变迁即为被允许(enable)。一个变迁被允许时，变迁将发生(fire)，输入库所(input place)的令牌被消耗，同时为输出库所(output place)产生令牌。

+ 变迁的发生是原子的

+ 有两个变迁都被允许的可能，但是一次只能发生一个变迁

+ 如果出现一个变迁，其输入库所的个数与输出库所的个数不相等，令牌的个数将发生变化

+ Petri网络是静态的

+ Petri网的状态由令牌在库所的分布决定

o Petri网的形式化定义

一个经典的Petri网由四元组（库所，变迁，输入函数，输出函数）组成。任何图都可以映射到这样一个四元组上，反之亦然。

o Petri网流程建模

一个流程的状态是由在场所中的令牌建模的，状态的变迁是由变迁建模的。令牌表示事物（人，货物，机器），信息，条件，或对象的状态；库所代表库所，通道或地理位置；变迁代表事件，转化或传输。

一个流程有当前状态，可达状态，不可达状态。

o 经典Petri网的局限性

+ 没有测试库所中零令牌的能力

+ 模型容易变得很庞大

+ 模型不能反映时间方面的内容

+ 不支持构造大规模模型，如自顶向下或自底向上

* 高级Petri网

为了解决经典Petri网中的问题，研究出了高级Petri网，在以下方面进行了扩展：

o 令牌着色

一个令牌通常代表具有各种属性的对象，因此令牌拥有值（颜色）代表由令牌建模的对象的具体特征，如一个令牌代表一个工人（张三，28岁，经验3级）。

o 时间

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

o 层次化

构造一个复杂性与数据流图相当的Petri网的机制。子网是由库所，变迁和子网构成的网络。

o 时序

增加时序逻辑的定义，更好的描述行为过程。

* Petri网的应用

Petri网的应用非常广泛，以下是Petri网比较常用的几种应用：

o 软件设计

o 工作流管理

o 工作流模式

o 数据分析

o 并行程序设计

o 协议验证

背景

卡尔·A·佩特里是一名物理学家，他发明Petri网主要是从物理的角度去描述并发现象的。据佩特里本人所述，他认为60年代计算机

科学的概念构架由于缺乏并发不适合于描述物理系统。其中一个重要的概念，就是Petri网里面不存在所谓的“全局时间”的概念，因为这跟狭义相对论是冲突的。相反，Petri网可以描述每一个节点的时序。

从狭义相对论的观点出发，两个时空点之间如果没有因果关系把它们连接起来（或者说“类空”的），它们就是独立的，不能说其中一个发生在前另一个在后或者相反。因此，Petri网里面的两种变迁（见下文）如果都有发生的条件，则不能认为其执行顺序有任何关系。然而，Petri网旨在描述变迁之间的因果关系，并由此构造时序。[编辑]经典Petri网

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

[编辑]结构

Petri网的元素：

?库所（Place）圆形节点

?变迁（Transition）方形节点

?有向弧（Connection）是库所和变迁之间的有向弧

?令牌（Token）是库所中的动态对象，可以从一个库所移动到另一个库所。

Petri网的规则是：

?有向弧是有方向的

?两个库所或变迁之间不允许有弧

?库所可以拥有任意数量的令牌

[编辑]行为

如果一个变迁的每个输入库所（input place）都拥有令牌，该变迁即为被允许(enable)。一个变迁被允许时，变迁将发生(fire)，输入库所(input place)的令牌被消耗，同时为输出库所(output place)产生令牌。

注意：

?变迁的发生是原子的，也就是说，没有一个变迁只发生了一半的可能性。

?有两个或多个变迁都被允许的可能，但是一次只能发生一个变迁。这种情况下变迁发生的顺序没有定义。

?如果出现一个变迁，其输入库所的个数与输出库所的个数不相等，令牌的个数将发生变化，也就是说，令牌数目不守恒。

?Petri网络是静态的，也就是说，不存在发生了一个变迁之后忽然冒出另一个变迁或者库所，从而改变Petri网结构的可能。

?Petri网的状态由令牌在库所的分布决定。也就是说，变迁发生完毕、下一个变迁等待发生的时候才有确定的状态，正在发

生变迁的时候是没有一个确定的状态的。

两个变迁争夺一个令牌的情形被称之为冲突。当发生冲突的时候，由于Petri网的时序是不确定的，因此具体哪个变迁得以发生也是不确定的。实际应用中，往往需要避免这种情形。用于描述现象的Petri 网也可能自然出现冲突，这表明我们对于变迁发生的条件没有完全了解。

多个弧连接两个节点的情况。在输入库所和变迁之间的弧的个数决定了该变迁变为被允许需要的令牌的个数。弧的个数决定了消耗／产生的令牌的个数。

[编辑] Petri网的形式化定义

一个经典的Petri网由四元组（库所，变迁，输入函数，输出函数）组成。任何图都可以映射到这样一个四元组上，反之亦然。

被允许的形式化变迁发生的形式化 Petri网到变迁系统的映射可达性图

Petri 是一个三元组（P,T,F） F(P X T)U(T X P)是弧的集合

[编辑]流程建模

一个流程的状态是由在场所中的令牌建模的，状态的变迁是由变迁建模的。令牌表示事物（人，货物，机器），信息，条件，或对象的状态；库所代表库所，通道或地理位置；变迁代表事件，转化或运输一个流程（Flow）有当前状态，可达状态，不可达状态。

[编辑]经典Petri网的局限性

?没有测试库所中零

?模型容易变得很庞大

?模型不能反映时间方面的内容

?不支持构造大规模模型，如自顶向下或自底向上

[编辑]高级Petri网

为了解决经典Petri网中的问题，研究出了高级Petri网，在以下方面进行了扩展：

?令牌着色 -- 令牌具有属性

?时间-- 变迁有延迟时间

层次化 -- 一个变迁可以是一个子Petri网

[编辑]令牌着色

一个令牌通常代表具有各种属性的对象，因此令牌拥有值（颜色）代表由令牌建模的对象的具体特征，如一个令牌代表一个工人（张三，28岁，经验3级）。

[编辑]时间

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

[编辑]层次化

构造一个复杂性与数据流图相当的Petri网的机制。子网是由库所，变迁和子网构成的网络。

[编辑]时序

增加时序逻辑的定义，更好的描述行为过程。

Petri网发展综述

1． Petri 网发展综述 Petri 网模型时C 。A 。petri 博士于1962年提出来的，他的提出专门应用这样一类系统，即系统中国含有相互作用的并行分支。作为研究系统的一种工具，petri 网理论用一个petri 网作为以恶系统的模型——系统的数学表示。从petri 网的观点来看待一个系统，集中地表现为两个本原的概念，即事件和条件。事件是系统中大声地动作，条件即系统的状态。系统中的动作的发生是由系统的状态来决定的，协调的状态演变是由系统的事件来驱动的。而这些状态可以用一组条件来描述。条件满足动作即可发生，动作发生后达到下一状态，它可以揭示出被模拟的系统的结构和动态行为方面的重要信息。这些信息可以用来对被模拟的系统进行估价并提出改进系统的建议。六十年代petri 网的研究以孤立的网系统为对象，以分析技术和应用方法为目标，通过网论丛七十年代开始研究，主要内容为网系统的分类及各网类之间的关系，包括：并发论，同步论，网逻辑和网拓扑，八十年代petri 网的研究在世界及中国有了较大的发展，近年来国内的主要研究集中在petri 网的语义，公平性，活性，网运算，网化简，PN 机理论等等。 当今计算机技术的发展日新月异，计算机计算能力的发展促进了模拟技术的应用和发展，用一个数学模型，比如petri 网来表示一个系统，然后，通过一定的算法让计算机对模型分析，就可以得到有关系统的性质。由于计算机计算的高速性和准确性，这就使得对巨大，复杂人工难以胜任的系统的模拟成为可能。 随着科学技术的发展出现了许多大规模的信息处理系统，如：并行程序，分布式操作系统，大规模的通信网络系统等等。由于petri 网可以精确描述系统事件之间的顺序并发关系，所以它是分析并发系统的强有力的工具。 Petri 网的研究工作沿着两个方向发展。第一，纯petri 网理论；第二，应用petri 网理论。 纯petri 网理论是为发展应用petri 网理论所需要的基本概念，技术和手段所做的研究。近年来petri 网理论的研究取得了不少研究成果，如petri 网的结构性质；petri 网语言：随机网，颜色网；谓词变迁系统等等。有国内吴哲辉教授和美国的T 。Murata 教授共同提出的petri 网的公平性取得了十分完整的结果，对于解决网系统中两个变迁（变迁组）的发生的关系提出了理论依据。蒋昌俊教授建立了PN 机理论构架，在交叠语义和偏序语义下获得反映真并发行为的文法及其PN 机结构，揭示它们的计算能力及其相互关系。 应用petri 网理论主要从事用petri 网模拟，分析和洞察系统的研究。这方面不单要求对petri 网及其模拟技术有深厚的知识，而且必须对应用领域相当熟悉。结合当今技术的发展越来越多地应用到通讯系统，分布式系统，并行计算机系统及自然科学社会科学的很多方面。 应用petri 网理论的一个重要方面就是并发系统petri 网分析工具的构造。Petri 网被应用于分析和设计系统时，如果系统规模较大则其对应模型必将十分复杂。人工分析显然是低效且不十分可靠的。因此，分析中若能有效地使用计算机则可十分迅速可靠的得到petri 网的性质。 2．Petri 网 Petri 网是用于描述分布式系统的一种模型。它既能描述系统的结构，又能模拟系统的运行。描述系统结构的部分称为网。从形式上看，一个网就是一个没有孤立结点的有向二分图。 定义1 满足下列条件的三元组N=（S ，T ；F ）称作一个网： 1） φ≠T S （1.1）

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网的两个特别之处:令牌是有颜色的，变迁的发生可以改变令牌的颜色。 12. 13.Petri网的归纳分析技术 归纳分析技术是针对Petri网的状态复杂性而提出的。一般来说，一个规模不大的系统，可能会出现状态组合爆炸的危险，从而给分析带来困难，对此人们提出化简和分解的思想。 化简是将一个较复杂的Petri网简化成一个比较简单Petri网而又要保留一些性质不变的同态变换过程，这个过程减少了可达状态空间，通过对简单网的分析，能为理解原网性质提供充分的信息。 分解的思想即是分而治之，是将一个复杂的网系统分解成若干较为简单的网系统，分解过程也要保持一些性质不变。这样，通过分析简单的子网系统便可以了解复杂的网系统。

petri网入门

petri网入门 最近需要学习一个大系统，其中涉及到了petri网的知识，发现这东西非常好用，在这分享给大家吧！了解一些，总会用得上的:) 文章引自：学习空间 =========================== Petri网是对离散并行系统的数学表示。Petri网是1960年代由C.A.佩特里发明的，适合于描述异步的、并发的计算机系统模型。Petri网既有严格的数学表述方式，也有直观的图形表达方式。 由于Petri网能表达并发的事件，被认为是自动化理论的一种。研究领域趋向认为Petri网是所有流程定义语言之母。 经典的Petri网是简单的过程模型，由两种节点：库所和变迁，有向弧，以及令牌等元素组成的。 petri网图 Petri网的元素： ?库所（Place）圆形节点 ?变迁（Transition）方形节点 ?有向弧（Connection）是库所和变迁之间的有向弧 ?令牌（Token）是库所中的动态对象，可以从一个库所移动到另一个库所。 Petri网的规则是： ?有向弧是有方向的 ?两个库所或变迁之间不允许有弧 ?库所可以拥有任意数量的令牌

行为 如果一个变迁的每个输入库所（input place）都拥有令牌，该变迁即为被允许(enable)。一个变迁被允许时，变迁将发生(fire)，输入库所(input place)的令牌被消耗，同时为输出库所(output place)产生令牌。 注意： ?变迁的发生是原子的； ?有两个变迁都被允许的可能，但是一次只能发生一个变迁； ?如果出现一个变迁，其输入库所的个数与输出库所的个数不相等，令牌的个数将发生变化； ?Petri网络是静态的； ?Petri网的状态由令牌在库所的分布决定。 两个变迁争夺一个令牌的情形被称之为冲突 多个弧连接两个节点的情况。在输入库所和变迁之间的弧的个数决定了该变迁变为被允许需要的令牌的个数。弧的个数决定了消耗/产生的令牌的个数。

Petri网

1.2.2高级Petri网 1.2.2.1多层次Petri网 虽然可以用着色Petri网等描述非常复杂的过程，但是得到的Petri网可能是一个平铺直叙的“大网”。虽然它正确的反映了业务流程，但却无法清楚的看清它的结构关系，无法观察到Petri网建模的过程层次结构。层次扩展可以帮助克服以上的那些缺点。在层次Petri网中，每一个结点不再是一个原子结点，可能其中的某一个结点代表着一个子网，这个子网也是一个带有库所、变迁、更深层次子网的Petri网。所以可以选择自底而上或自顶而下层次化地构造Petri网。自底而上的方法是首先从最底层开始，详细地描述基本组件，这些组件被组合成过程，众多的子过程再组合成更大的过程，最终得到过程的详尽描述。自顶而下的方法则正好相反，从最高层次开始，过程不断地被分解为子过程，直到最底层只包括变迁和库所。反复的分解以得到层次化的描述。 1.2.2.2时间Petri网 时间Petri网使得库所和变迁具有了时间性。时间Petri网可以分为随机时间Petri网和确定性时间Petri网。时间Petri网是指变迁发生时间和时间延时大小是时间的，又分为时间延时的时间Petri网和发生时间的时间Petri网(或称广义时间Petri网)。时间延时的时间Petri网是指其变迁的延时时间是时间的，一般按指数规律分布；发生时间的时间Petri网是指变迁发生时间是时间的，变迁延时时间为零。确定性时间Petri网是指设定库所和变迁的时间是确定的，它又分为库所的时间Petri网和变迁的时间Petri网，库所的时间Petri网是对库所设定延时时间；变迁的时间Petri网是对变迁设定时间，进一步，变迁时间Petri网又分为；时间延时Petri网和时间间隔Petri网；时间延时Petri网是指变迁发生的延时时间，指变迁授权后经过时间延时r后才发生；时间间隔Petri 网是变迁发生的时间间隔(授权时间a1，撤消授权时间a2)。变迁只能在这个时间间隔(a1，a2)内发生，错过这个时间间隔则不能发生。 定义1-5时间Petri网是一个五元组TPN=(P，T；F，T，τ，M0，它满足1．(P，T；F)为Petri网，称为TPN的基网，M0是初始标识。 2．τ是一个时间映射函数，τ：T→0 ∪Q+(Q+是正有理数集合)，规定网中每个变迁的持续时间，当持续时间为0的时候，称之为瞬间变迁，不为0的称之为时延变迁。

petri网的理论及应用

Petri网的综述及应用 蔡振宇 摘要： 一、Petri网的发展 Carl Adam Petri于1962年在他的博士论文中首次提出了有关Petri网的概念。自上世纪八十年代第一次Petri网理论和应用的国际研讨会的召开以来,与之相关研讨会在世界范围内就开始以一年一度的频率召开。人们通常称赞Petri网描述异步并发与图形表示的能力，而这两个特点来源于其网状结构。世间万物皆由网构成，只是这个网是有形的或是无形的，万事万物在这些网上发生着变化。事物间依赖关系，正是Petri网的完美体现。描述物理世界的客观存在，使客观存在成为论文的研究对象，同时还必须保证凡是用其描述的系统都能转换为客观存在。前者称为系统模型的仿真性，后者则是系统模型的可实现性。目前Petri 网己扩展成多种形式，如基础Petri网、时间Petri网、层次Petri网、有色Petri网等等[}z6-3 y。 一个Petri网的结构元素包括:库所(place)、变迁(transition)和弧(acr)。库所也称位置，它是一个抽象的词语，不是具体指哪个确定位置，而是建模中恰巧画的位置，它主要的作用是描述网中的一个局部资源状态或者是条件。变迁是用于描述变化着的系统事件，它表示的是一种资源相互作用的事件发生关系。弧的意义是描述资源的使能转化方向，是库所中消耗和产生的依据。如图2-1中，以红点来显示的是托肯(token)或者称为标记，它存在于库所中，呈现库所的资源数量，是Petri网中的一个重要概念。托肯在网中的动态变化意味着网的不同状态。一个简单的网系统模型，如图2-1所示。 -+Petri网从客观的角度对系统的发生进行定性和定量的描述，并能呈现出有规律的定性和定量的改变。在Petri网中，把对象统称为资源。定性相同的资源定为一类，用一个状态元素P来表示。托肯的数量代表了库所P的状态。尸的定性和定量的改变也就是上面所称的变迁T。在建模中库所P用圆圈来表示，变迁T用方框来表示，有向弧用箭头来表示。建模中箭头由圆圈指向方框意味着消

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模型的基本关系

Petri网学习报告

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 =的节点。x 的前置集x ?定义为 }{F x y T P y x ∈∈=?),( ，x 的后置集?x 定义为}{F y x T P y x ∈∈=?),( 。相应地，令T P X ?是节点的集合，X 的前置集定义为x X X x ?∈?= ，X 的后置集定义为?∈?=x X X x 。 若x 是库所，其前置集中的元素称为其输入变迁，后置集中的元素称为其输出变迁。 若x 是变迁，其前置集中的元素称为其输入库所，后置集中的元素称为其输出库所。