Petri网建模技术基础入门学习

以自然规律刻画变迁及变迁间的关系，使Petri网具有区别于其它模型的许多优点。”表达了Petri网就是直接给物理世界的自然规律建立的计算模型。

最好的两个建模技术，自动机模型和Petri网模型（我觉得跟非确定性自动机差不多），其实我觉得还有图论里的图。下面总结了一下比较浅显易懂的文章，看完对Petri网就明白了。关于自动机，可以看我这篇文章，形式语言与自动机总结。

文章一

Petri net graph:
Petri网用于描述和分析系统中的控制流和信息流，尤其是那些有异步和并发活动的系统。
圆圈表示位置( place )，圆圈中有标识( token )表示条件( condition )满足。线段( bar)表示变迁( transition )。一个Petri net graph如下图所示

因为petri网中的弧是有方向的，所以petri网图是有向图。又因为petri网中的节点可以分为两个集合：place和transition，并且每条弧都是从一个集合中的元素连到另一个集合中的元素，所以petri网图是一个有向二分图。

Petri网的结构：
用四元组表示：位置的集合P，变迁的集合T，输入函数I，输出函数O。C = ( P, T, I, O)。下面是一个例子：
C = ( P, T, I, O)
P = {p1, p2, p3, p4, p5}
T = {t1, t2, t3, t4 }
I(t1) = {p1}    O(t1) = {p2, p3, p5}
I(t2) = {p2, p3, p5}   O(t2) = {p5}
I(t3) = {p3}    O(t3) = {p4}
I(t4) = {p4}    O(t4) = {p2, p3}

上面是petri网的形式化描述，通常使用简明直观的petri net graph来阐明petri网的许多概念。

Marked Petri net:
一个petri网的标识可以用一个向量表示μ= (μ1, μ2, …μn)。μi代表pi的token数目。一个标识的petri网叫做marked Petri net，M = ( P, T, I, O, μ)。
任何时候，在任何位置( place )有不多于一个的标识的Petri网，叫做安全网( safe net )。推广之，在任何位置同时不多于k个标识的Petri网，叫做k-bounded net。如果不知道k的值，简单地叫做bounded net。“有界”代表着petri网在物理上的可实现。
如果Petri网中token的总数保持不变，称这个petri网是保守( conservative )的。它隐含着，每个可触发的变迁( transition )输入的数目等于它输出的数目。

Petri网的执行和可达性问题：
如果一个变迁的每个输入都至少有一个token，则这个transition被enabled。变迁发生时，会从它的每个输入移去一个token，在它的每个输出放置一个token。
一个petri网的状态是它的所有标识的集合（向量μ）。当一个变迁发生时引起的状态变化由一个局部函数δ来定义，叫做下一状态函数。
从一个标识μ可以同时发生一组变迁。如果从μ同时发生一些变迁可以得到μ’，称μ’是立即可达( immediately reachable )的。可达集合( reachability set )R(M)被定义为M = (P, T, I, O, μ)从μ出发可以得到的所有状态的集合。
给定一个标识的petri网，标识记作u。给定一个标识u’。是否可以从u得到u’是petri网的可达性问题。可以看作集合可达性问题的一个特例，很多问题都可以归约到可达性问题。
如果没有一个变迁激活序列可以触发一个变迁，我们称这个变迁是死的( dead )；反之，变迁是活的( live )。为了研究操作系统的死锁问题，在Perti网中定义了变迁的deadness和liveness。

用Petri网建模的例子：
Petri网适合对存在并发、并行的事件的离散事件系统进行建模。一般用位置( place )表示条件，用变迁表示事件。看下面的图，是一个简单计算机系统的例子：

文章2

介绍Petri网的元素：

(1)库所（place）：圆形节点
(2)变迁（transition0）：方形节点
(3)有向弧（connection）：库所与变迁之间的有向弧线
(4)托肯（token）：库所中的动态对象，可以从一个库所移动到另一个库所
Petri网规则：
如果某一个变迁的所有前驱库所都有托肯，则这个变迁满足发射条件；变迁发射时，从它所有的前驱库所里分别取出1个托肯，同时往它所有的后继库所里面分别放置1个托肯，以此类推；

如图：图中变迁"1"不满足发射条件，由一个前驱库所中托肯数目为0.

    有两个或多个变迁都被允许的可能，但是一次只能发生一个变迁。随机数确定发生的变迁
    如果出现一个变迁，其输入库所的个数与输出库所的个数不相等，令牌的个数将发生变化，即就是，消耗托肯数目=前驱库所数目-后继库所数目
两个变迁争夺一个托肯的情形被称之为冲突。当发生冲突的时候，由于Petri网的时序是不确定的，因此具体哪个变迁得以发生也是不确定的。实际应用中，往往需要避免这种情形。用于描述现象的Petri网也可能自然出现冲突，这表明我们对于变迁发生的条件没有完全了解。
Petri是静态的，也就是说，不存在发生了一个变迁之后忽然冒出另一个变迁或者库所，从而改变Petri网结构的可能。Petri网的状态由托肯在库所的分布决定。也就是说，变迁发生完毕、下一个变迁等待发生的时候才有确定的状态，正在发生变迁的时候是没有一个确定的状态的。
编程：
Place类(库所)：序号，托肯数目
Transition类（变迁）：序号，前驱库所数组，后继库所数组
Main主程序：全局变量：Petri网中的Place数组和Transition数组
      a.初始化Place数组；
      b.初始化Transition数组；
      c.判断当前状态下是否存在满足发射条件的变迁，并随机选择一个满足发射条件的变迁执行d；
    d.对一个指定的变迁进行发射，内容是将这个变迁的所有前驱库所中的托肯数目均减1，所有后继库所中的数目均加1，消耗的托肯数目是前驱库所数目-后继库所数目，完成
      e.若要继续进行c

文章3

计算模型的统一分析
    人类所有的计算模型都包括如下四个要素：
         1）输入集合或者输入变量（I）；
         2）输出集合或者输出变量（O）；
         3）处理或者变化（P）；
         4）数据或者状态（D）。
即ComputingModel =（I，O，P，D）–注意其中用的是逗号（，），其中的输入输出是处理或者变化元素的输入输出。有系统应用价值的计算模型包括图灵机和Petri网两个。

图灵机在已知输入输出情况下研究处理和数据的实现问题，即Turing’s machine = （I，O；P，D）–注意其中用的是分号（；），处理就是算法、程序Programming，数据是DataStructure。图灵机的工程化技术已经成熟，包括从汇编语言到UML语言在内的全系列软件工程和程序设计语言，核心是结构化程序设计语言。

Petri网在已知变化状态条件下研究输入和输出的网络结构问题，即Petri nets =（P，D；I，O）–注意其中用的是分号（；）。

图灵机是“从蛋（I，O）开始研究蛋（I，O）孵鸡（P，D）”问题，而Petri网是“从鸡（P，D）开始研究鸡（P，D）生蛋（I，O）”问题。两者精确对偶，统一起来就可以完全解决了“蛋（I，O）孵鸡（P，D）、鸡（P，D）生蛋（I，O）”的自然循环，因此被我统称为自然（或实）计算模型，目的是区别于我预计10年后才有可能研究成熟并公开的“虚计算模型”。

对偶定律告诉我们，对偶模型可以相互解决它俩各自所不能解决的问题。Petri网的实践（语用网）可以解决Turing机所不能解决的“软件模块复用（也就是计算协作）”问题；而 Turing机的实践（算法分析-也就是软件工程）解决了Petri网所不能解决的“节点爆炸”问题。这就是我把它俩统一起来研究的原因。

文章4

Petri网的主要应用：

工作流，物流等建模。
离散系统的建模和仿真，Petri网既是图形工具，又是数学工具，对于非专业人员直觉上容易理解，对于专业人员又提供了强大而又形式化的描述能力。高级Petri网可以方便的进行层次化建模，这适合于自顶向下的建模及各个阶段的独立验证和确认。
网络通讯协议中的描述、验证和设计。
计算机系统中系统的资源的共享，进行管理建模，还有实现控制系统的并发性建模，所以基于Petri网的并行控制器的研究比较热门。
难点：