第一章 背景知识
第一章 背景知识
§1.1 历史与发展
Petri网的概念最早在1962年Carl Adam Petri 的博士论文中提出来[1]。网论从一开始就以物理为基础，当时的理论计算机科学包括自动机模型和形式语言理论，其概念构架不适合描述物理系统，它缺少重要的并发概念。Petri网是一个状态变迁模型，可用来描述系统中各异步成分之间的关系，同时允许同时发生多个状态变迁，也是一个并发模型。当时的计划是要用一种兼容物理和计算机科学两者的语言和概念构架来形式化描述制约通信进程的所有“自然法则”[11]。1970至1975年，MIT的计算结构研究小组积极参与Petri网的相关研究，在1975年7月在MIT举行第一次Petri网和相关方法的研讨会。从1980年召开第一次Petri网理论和应用的国际研讨会以来，每年一次的国际研讨会连续不断，Petri网理论和应用的研究成果也不断涌现，到1987年已有2074篇重要的相关论文发表[12]。
随着研究的不断深入，Petri网理论也在不断地充实和完善，其抽象和描述能力也不断的朝着横向纵向发展。它的纵向扩展表现为：从基本的条件/事件(C/E)网，位置变迁(P/T)网，发展到谓词/变迁网和着色网等高级网。它的横向扩展表现为：从无参数的网，发展到时间Petri网和随机Petri网。
§1.2 研究方法及应用
Petri网模型就是一个基于图的数学形式化描述模型，用来分析离散的并发系统，或者说Petri网模型用来描述非同步的因果和非因果行为，包括并行和不确定选择。Petri网理论研究的主要内容是系统模型的行为特征，包括：可逆性(reversibility)、有界性(boundedness)、活性(liveness)、可达性(reachability)、可覆盖性(cover)、公平性(fairness)等。Petri网以研究模型的组织结构和动态行为为目标，着眼于系统中可能发生的各种状态变化及变化之间的关系。Petri网模型的主要分析方法依赖于对诸如关联矩阵、可达树、状态方程、位置不变量、变迁不变量等的研究与分析。
在Petri网研究与应用的发展历史中，它的应用范围已经远远超出了计算机科学的领域，成为研究离散事件动态系统的一种有用工具。如今，Petri网模型在众多方面得以应用。两个成功的应用领域是性能评价和通信协议，其他很有前景的应用领域包括分布式软件系统，分布式数据库系统，并发并行计算，柔性制造系统，多处理机系统，逻辑推理，办公自动化系统，形式语言，神经元网络和决策模型等。以协议工程形式化方法为例：协议的验证是基于对Petri网模型分析而进行的。概括地讲，协议工程形式化方法是要为协议设计的整个阶段提供规范化的指导，这包括描述(Specification)、验证(Verification)、实现(Implementation)和测试(Testing)等几个主要阶段，每一阶段都有相应的方法和技术。通过位置/变迁（P/T）网模型就可以很好的描述并分析整个系统。
1
Petri网系统的可达性研究
§1.3 Petri网的直观理解
用Petri网描述的系统有一个共同的特征：系统的动态行为表现为资源(物质资源和信息资源)的流动。在提供Petri网(PN)形式描述之前，通过分布系统几个基本行为模型描述的例子，先对Petri网作一个直观的说明。
一个Petri网的结构元素包括：位置(place)、变迁(transition) 、弧(arc)。位置用于描述可能的系统局部状态，例如：计算机和通信系统的对列、缓冲、资源等。变迁用于描述修改系统状态的事件，例如：计算机和通信系统的信息处理、发送、资源的存取等。弧通过其指向来规定局部状态和事件之间的关系：它们引述事件能够发生的局部状态；由事件所引发的局部状态的转换。
在Petri网模型中，标记包含在位置中，它们在位置中的动态的变化表示系统的不同状态。如果一个位置描述一个条件，它能包含或不包含一个标记，当一个标记表现在这个位置中，条件为真；否则为假。如果一个位置定义一个状态，在这个位置中的标记个数用于规定这个状态。例如：在计算机和通信系统中，标记可以用于表示处理的信息单元、资源单元和顾客、用户等对象实体。
一个Petri网模型的动态行为是由它的实施规则规定的，当使用等于1的弧权时，如果一个变迁的所有输入位置(这些位置连接到这个变迁，弧的方向是从位置到变迁)至少包含一个标记，那么这个变迁可能实施(相关联的事件发生)。对这种情况，这个变迁称为可实施的。一个可实施的变迁导致从它所有的输入位置中清除一个标记，在它的每一个输出位置(这些位置连接到这个变迁，弧的方向从标迁到位置)中产生一个标记。当使用大于1的弧权时，在变迁的每一个输入位置中都要包含至少等于连接弧权的标记个数，它才可以实施；这个变迁的实施 将清除在该变迁的每一个输入位置的相应的标记个数，并在变迁的每一个输出位置产生相应的标记个数。变迁的实施是一个原子操作，清除输入位置的标记和在输出位置产生标记是一个不可分割的完整操作。 §1.4 Petri网的形式化描述
本节的目的是把上一节的概念形式化。 一．网及其图形表示
定义 1-1 三元组N=(S, T ; F) 称为有向网的充要条件是：
1. S∩T=? (二元性)； 2. S∪T≠? (网非空); 3. F?S×T∪T×S;
4. dom(F)∪cod(F) = S∪T ;
其中 dom(F) ={x| ?y : (x,y)?F}，cod(F) ={y| ?x : (x,y)?F}
S和T分别称为N的位置集和变迁集，F为流关系(flow relation)。位置集和变迁集是有向网的基本成分，流关系是从它们构造出来的。位置和变迁是两类不同的元素，所以S∩T=? ，而S∪T≠? 表示网中至少有一个元素。每一个位置
2
第一章 背景知识
表示一种资源，变迁是资源的流动，由流关系规定，所以变迁只能与位置有直接关系： F?S×T∪T×S。dom(F)∪cod(F) = S∪T表示不存在不参加任何变迁的资源和不引起资源流动的变迁。
二．网系统定义
有向网是系统的结构框架，活动是框架上的是系统中流动的资源。网系统必须需指明资源的初始分布，规定框架上的活动规则，即位置的容量和变迁与资源之间的数量关系。
记: N={1,2,3,?}, N0={0}∪N, ω：+∞,对于有向网N=(S, T；F)。 定义 1-2
1．K: S?N∪{ω}称为N的容量函数（capacity function） 2．对于给定的容量函数k
M: S? N0 称为N的一个标识（marking）的条件是：
? s∈S M(s)≤K(s)
3．W：F?N 称为N上的权函数，对(x,y)∈F
W(x,y)=W((x,y)) 称为(x,y)上的权。权函数规定每个变迁发生一次引起的资源量上的变化，显然对任何(x,y)∈F，有 0< W(x,y) < ω
在此基础之上我们定义Petri网系统。 定义 1-3
六元组∑=(S,T；F, K,W, M0)构成Petri网系统的条件：
1．N=(S,T; F) 构成有向网，称为∑的基网
2．K, W, M0依次为N上的容量函数，权函数和初始标识(initial marking) 以上的是Petri网系统从结构到资源的静态特征。下面给出变迁发生的条件和结果，这种动态规律称为变迁规则。 定义1-4 可实施与实施(enabling and firing) 令∑=（S, T；F, K, W, M0）是一个P/T系统。
1．函数M:S?N叫做Σ的标识??s∈S: M(s)≤K(s)。 2．一个变迁t∈T在M下是可实施的??s∈S: W(s,t)≤M(s)≤K(s)- W(t,s).
T在M有发生权记作M[t>。
3．如果t∈T在标识M下是可实施的，那么t可以实施并产生一个新的后
继标识M’,M’可由下列方程给出：
?s∈S: M’(s)=M(s)－W(s,t)＋W(t,s)。
4．系统标识M经过t的实施得到新的标识M’，可以表示成M[t>M’
或者M?M’。
定义1-5 实施序列
令∑=(S,T；F, K,W, M0)是一个P/T系统，σ=M0t1M1t2?tnMn是∑的一个有限实施序列??i,1≤i≤n:Mi-1[ti>Mi ;σ的长度 ?=n ，t1t2?tn叫变迁实施序列。 定义1-6 可达标识
令∑=(S, T；F, K,W, M0)是一个有限的P/T系统，标识M是由M0可达的当且仅当存在一个变迁实施序列σ，使得M0经σ实施得到M，亦即，M0[σ>M。
3
Petri网系统的可达性研究
三．网系统分类
C、A、Petri1962年使用的系统模型实际上是K=Ω和W=1的网系统，70年代A、Holt把这种系统称为Petri网，于是Petri网由此得名。按网系统的容量函数K和权函数ω可分为三类：
1．K=1, W=1
这时每个S元只有“有token”和“无token”两种状态，可理解为只有“真”和“不真” 两种状态的布尔变量。网论中把这种s元称为条件，与条件关联的变迁称为事件。这种由条件和事件构成的网系统称为EN系统(条件/事件网)。 2．K=ω, W=1
这是传统上称为Petri网系统，又称为P/T网。 3．K，W为任意函数
这种系统通常称为P/T系统，下面将着重介绍
四．可达标识集
许多应用问题都关心系统可能的状态，可达标识集是解决这类问题的关键。可达标识集是Petri网任何可能发生序列所能进入的全部状态的集合。Petri网可达性的分析对于协议验证十分必要，因为用Petri网模拟协议的正确性的许多问题都可转化为可达性问题。P/T系统的若干重要性质可以用可达标识集来定义。 定义1-7 可达标识集
P/T系统∑=(S,T,F,K,W, M0)的可达标识集[M0>是满足下列条件的最小集合：
1. M0∈[M0>
2. 若有M’∈[M0>，t∈T,使M’[t>M,则M∈[M0>。
由以上定义可得：
定理1-1 M∈[M0>,则存在序列σ=M0t1M1t2M2…tnMn,使得? i: 0 Mi-1[ti>Mi,且Mn=M 。反之已然。 定义1-8 可达树 首先定义一记号ω：对于所有n∈N，n<ω；n+ω=ω+ω=ω-n=ω。 令∑=(S,T；F, K,W, M0)是一个P/T系统。∑的可达树是由标识（标记值可能由ω表示）为结点构成的树，其弧度由T元素标注。可达树由下列递归算法构成。(在第六章应用实例分析的最后，我们将给出该实例的可达树。) 算法1：P/T系统可达树构造 1．根结点r由M0标注。 2．一个标注M的结点x是一个叶结点当且仅当，不存在t∈T：t在M是可实施的或者在从r到x的路上存在一个结点y≠x，但结点y也是由M标注的。 3．如果一个标注M的结点x不是一个叶结点，那么对于所有t∈T使得在M下可实施的t实施而产生一个新的结点y，且在从x到y新产生的 M1?满足于M[t>M1?,弧上标注t。 y结点标注的标识M?可由M1?来计算， 即?s∈S，M1?(s)= M(s)－W(s,t)＋W(t,s)。M?的计算可区分为两种情况： 1) 从r到y的路上，如果存在标注M??的结点z≠y且?s∈S：M1?(s) 4 第一章 背景知识 ?M1?(s),≥M??(s)，那么 M?(s)= ???如果M1?(s)?M??(s)其他 2) 其它情况，M?=M1?。 一个P/T系统有界，指的是它所有的元素都是有界的，很自然它的可达树也是有界的。 定义2-8 可达图 令∑=（S, T；F, K,W, M0）是一个有限的P/T系统，∑的可达图是由标识(标记值可能由ω表示)为结点的图，其弧线由T元素标注。可达图有下列算法构成。 算法2：可达图构成 1．两个可达树的结点是等价的当且仅当它们有相同的标注M。 2．可达图的结点是它的可达树结点的等价类。从结点Y到结点Z的弧线 标注为t，当且仅当存在y∈Y且存在z∈Z，使得在可达树中从y到z由弧线t。 可达图是可达树中相同结点的相重叠。 五．系统模型的行为特征 1. 若对于所有的M∈[M0>，存在正整数k，使得对所有s∈S，M(s)≤k，就说Σ是有界P/T系统，或k_为界P/T_系统。Petri网模型的有界性是指网中任何位置的标记数是有界的，无界的Petri网模型表示相应的协议层上有无限多的标记数，这样的协议显然是很不公平的。k=1时也称Σ为安全系统。k为界系统也称k安全系统，k是这种系统的界。 2． t∈T，若对任一可达标识M∈[M0>,均有从M可达的,存在标识M?∈[M>，使得M?[t>，就说变迁t是活的。若所有t∈T都是活的，就说系统Σ是活的。Petri网具有活性表明该协议是无死锁的。有些系统的界有时不易或无法确定，但可以证明其存在性，这时也可以笼统的说该系统是有界的。定义中的[M>为从M出发有限步可到达的标识集，也就是以M为初始标识时的可达标识集。 M?[t>是t在M?有发生权。T的活性要求它在任何可达标识M∈[M0>均有潜在的发生权，即有限步即可获得的发生权。 3. Petri网模型的可覆盖性：在一个P/T系统中，标识M称为可覆盖的，当且仅当系统可达集中存在标识M′，使得对系统中任一位置P，M′(P)?M(P)成立。 4．Petri网模型的可逆性：在一个P/T系统中，若对于所有的M∈[M0>，都有从M可达到M0 。如果M0[σ> M’，M’[t>M，我们可以得到，从M可达到M’。 六．Petri网模型的主要分析方法 定义2-11 关联矩阵和不变量 令∑=(S,T;F,K,W,M0)是一个有限的P/T系统，且S={s1,s2,?,sn},T={t1,t2,?,tm}。 1．矩阵C=[cij](1≤i≤n，1≤j≤m)是∑的关联矩阵当且仅当 cij =W(tj，si)－W(si，tj)。 2．一个n元整数列向量x叫作∑的一个S-不变量当且仅当 CT×x=0，其中CT 为C的转置矩阵。 3．一个m元整数列向量y叫作∑的一个T-不变量当且仅当 C×y=0。 5