第一章1.引言2.网与网系统2.1网与子网2.2标识网与网系统2.3库所/变迁系统与加权Petri网2.4基本网系统与条件事件系统2.5并发与冲突2.6系统的Petri网模型本系列主要是参考吴哲辉老师的《Petri网导论》这本书记录本人学习笔记主要用于自己后续翻看学习。1.引言Petri网是分布式系统的建模和分析工具它特别便于描述系统中进程或部件的顺序、并发、冲突以及同步并行的A和B互相等对方到齐了之后才继续等关系。同其他系统模型相比较对真并发的恰切描述是Petri网的独特优势。作为一种系统模型Petri网不仅可以刻画系统的结构又可以引入许多数字方法对其性质进行分析。对于复杂的系统Petri网可以对其进行分层描述便于同面向对象的思想方法相沟通。2.网与网系统2.1网与子网Petri网是用于描述分布式系统的一种模型。它既能描述系统的结构又能模拟系统的运行。描述系统结构的部分称为网。从形式上看一个网就是一个没有孤立结点的二分图。X的前集即所有指向X的节点的集合后集即所有X指向的节点的集合。公式注解如果一个网不存在自环自环对于两个节点x和y既存在x指向y的边又存在y指向x的边即为纯网。公式注解节点x和节点y的前集和后集完全相同即可推出x和y是同一个节点。不存在两个不同的节点它们拥有完全相同的前集和后集这样的网称为简单网。公式注解T图中库所的前后集为1库所是单进单出的S图中变迁的前后集为1变迁是单进单出的。公式注解自由选择网中如果两个变迁共享一个输入库所那么每个变迁都只能有这一个输入库所变迁的输入集是1。扩充的自由选择网中如果两个变迁共享一个输入库所那它们的输入集必须完全相同拥有一模一样的前集。自由选择网是扩充的自由选择网的一种特殊情形。公式注解把一个网中的全体库所改换成变迁全体变迁改换为库所就得到这个网的对偶网一个网的逆网就是把网中的全体有向边的方向倒置所得到的网。公式注解子网的概念同图论中的子图的概念有区别对于子图可以任意选取图中的任意节点和边但一个网的子网是由其结点子集库所子集和变迁子集完全确定的不能随意取舍。下面通过网N2为例来说明几种分类注解对偶图将变迁变为库所库所变为变迁即t1变为s1s1变为t1逆图即将所有流关系的箭头转向关于库所子集的外延子网即以给定的库所结点为原始结点将所有与这些库所相连的变迁结点都包含进去保留这些结点间的流关系关于库所子集的内连子网即以给定的库所结点为原始结点分别列出这些库结点的前集和后集集合找出前集和后集中的相交的变迁结点保留这些结点间的流关系关于变迁子集的外延子网即以给定的变迁结点为原始结点将所有与这些变迁相连的库所结点都包含进去保留这些结点间的流关系关于变迁子集的内连子网即以给定的变迁结点为原始结点分别列出这些变迁结点的前集和后集集合找出前集和后集中的相交的库所结点保留这些结点间的流关系。2.2标识网与网系统上节定义的网是Petri网的结构部分另一个要素是标识标识的部分用于反应系统的状态。用图形来表示一个标识网(S,T,F,M ) 时对s ∈ S若M(s) k则在表示库所s 的小圆圈内加上k 个小黑点当数值k 很大时也可以直接写上数字k并说库所s 中有k 个标志token或标记。一个网系统Σ (N,M0) 的全部可能的运行情况由它的基网N和初始标识M0完全确定。因此给出了基网N和初始标识M0就确定了一个网系统。注解这样的一个映射也是网N的一个标识称它为空标识。2.3库所/变迁系统与加权Petri网注解一个变迁的发生其前后集库所的标志数的改变量也同原型Petri 网不一样。Σ 就变成一个原型Petri 网。从这一点看原型Petri 网似乎是P/T 系统的一个子类。然而P/T 系统并不比原型Petri 网有更强的模拟能力。凡是可以用P/T 系统对其建模的实际系统也可以用原型Petri 网对其建模。因为每一个P/T 系统都可以转换为一个行为等效的Petri 网。对于一个P/T 系统如果规定各个库所的容量都为无穷大即取消库所集上的容量函数而保留有向边集上的权函数就得到一种介于原型Petri 网和P/T 系统之间的网系统模型Σ (S,T,F,W,M)。称这种模型为加权Petri 网。模型容限函数K权函数W原型Petri网无容量无限没有弧权1加权Petri网无容量无限有弧可以标注权值P/T系统有有2.4基本网系统与条件事件系统基本网系统简记为EN 系统是最简单的分布式系统模型。由于在EN 系统中对任意标识M 和∀s ∈ SM (s) 的值只有两种可能M (s) 0 或M(s) 1可把每个s ∈ S 看作一个条件M (s) 1 表示条件s 成立M (s) 0 表示条件s 不成立。相应地可把每个t ∈ T 看作一个事件•t 和t• 分别称为事件t 的前置条件集和后继条件集。事件t 有发生权当且仅当它的每个前置条件都成立但每个后继条件都不成立。事件t 的发生使得它的每个前置条件消失而每个后继条件都变成成立。在EN系统中习惯上用B 表示条件集用E 表示事件集。注解**从任意一个已知的状态往前推一步谁变的和往后走一步变到谁都要加进来反复这个过程直到不能再加为止。完全情态集既包含了事件向前发生所产生的新情态也包含了向后追索得到的各个情态。注解前提网B,E,F必须是简单网即不存在两个不同的节点拥有完全相同的前集和后集。每个条件b都有机会成真也有机会成假。每个事件e都有机会发生。2.5并发与冲突同其他网系统模型相比较Petri网的突出优点之一是它们特别便于描述并发和冲突。一般地说如果两个事件在某情态下都有发生权而且其中任何一个的发生都不会使另外一个失去发生权则称这两个事件在该情态下处于并发。如上图所示e2和e3在情态c0处于并发关系。并发关系没有传递性。注解条件一在当前情态c,e1能触发同时e2也能触发两个事件都拿到发生权。条件二如果我先执行e1,得到新状态c1,执行完e1之后e2依然可以触发如果我先执行e2得到新状态c2,执行完e2之后e1依然还可以触发。注解条件1在当前情态c下ei可以发生但ej还不能发生。条件2如果ei在情态c下发生到达新情态c’,那么在新情态c’下ej就可以发生了注解事件e1 和e3 在情态c0 都可能发生。但如果e1 发生产生新的情态c1 {b1}e3 在c1 失去了发生权。反过来也是这样如果在情态c0 下e3 发生得到新的情态c2 {b3}e1 在情态c2 失去了发生权。这种情况称为冲突。注解条件1在当前情态c下两个事件都有发生权。条件2如果e1发生了到达新情态c’那么在新情态下e2就失去了发生权反过来如果e2发生了到达了新情态c’,那么在新情态下e1也失去了发生权。在任何情态下任一个条件都不存在冲撞的基本网系统称为无冲撞系统。有时候一个网系统在某个情态下同时存在并发和冲突但由于并发事件中的某些事件的发生会使冲突自动消失。另外还有一种情况系统在某个情态下存在并发而并发事件中不同的事件发生使得系统可能出现冲突也可能不出现冲突上面两种现象称为混惑。注解第一种混惑的例子在这个系统中既有e1 和e2 的冲突以及e2 和e3 的冲突又有e1和e3 的并发。在e1和e2冲突中如果选择e1发生则e2和e3的冲突也就自动消失。第二种混惑的例子在该系统中在当前状态下事件e1和e2处于并发。如果事件e2先于e1发生那么就会产生e1和e3 的冲突。反之若e1先于e2发生这种冲突就不会出现。存在混感的网系统不是好的系统模型因为在这种网系统的运行中冲突是否出现无法确定不便于对系统施加外部控制。一般Petri网中的并发与冲突一般Petri 网中没有冲撞的概念。这是因为Petri 网中的库所容量为无限大因此在Petri 网中只要一个变迁的前集各库所有足够的标志该变迁就可以发生。即使该变迁的后集中某些库所含有标志也不影响变迁的发生。2.6系统的Petri网模型理论研究的目的在于应用。为了应用Petri 网分析实际系统的性质首先要建立实际系统的Petri 网模型。一般地说Petri 网可以描述的系统是那些由离散事件组成的系统事件之间有一定的相互依赖关系这种依赖关系通过系统的状态来反映。在系统的某个状态下一个些事件可能发生事件的发生将会改变系统的状态。在新的状态下另一个些事件又可能发生。事件的接连发生和状态的不断变化的过程便是系统的运行。好啦关于Petri网初识的学习到这里就先结束啦后期会继续更新相关知识欢迎大家持续关注、点赞和评论❤️❤️❤️