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″不满足发射条件，由一个前驱库所中托肯数目为0.

文章3

图灵机在已知输入输出情况下研究处理和数据的实现问题，即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年后才有可能研究成熟并公开的“虚计算模型”。

文章4

Petri网的主要应用：

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