T murata关于Petri网的性能分析及应用1

《T murata关于Petri网的性能分析及应用1》由会员分享，可在线阅读，更多相关《T murata关于Petri网的性能分析及应用1（25页珍藏版）》请在装配图网上搜索。

1、Petri网的性能，分析和应用这是一篇受邀而著的关于Petri网这种图形和数学建模工具的回顾教程的文章。Petri网在描述和研究信息处理系统方面是一种很有发展前景的工具，特点是并发，异步，分布式，平行，具有不确定性，和/或随机性。本文开始说的是它在文学领域中历史和应用方面的综合叙述。继而介绍了建模实例，方法和结构特性。三种分析方法，Petri网及其子网的分析。特别是， 一部分是用于阐述标记图并发系统的模型最适合的分析方法。此外，本文涉及了随机网的性能建模中的应用有关的的介绍性讨论，以及高级网的逻辑编程应用，还包括可达标准的最新研究结果。在进行基于Petri网的多学科领域的进一步阅读时提供一些建

2、议。、引言Petri网是一种适用于许多系统的图形和数学建模工具， 它们在描述和研究信息处理系统方面是一种很有发展前景的工具，这个特点是并发，异步，分布式，平行，具有不确定性，和/或随机性。作为一个图形化的工具，Petri网可以用来作为一种视觉传达的辅助工具，类似流程图，框图和网络。此外，托肯在网中用来表示动态系统的并发活动过程。作为一种数学工具，它通过建立状态方程，代数方程，和其他数学模型来控制系统的行为。Petri网可用于从业者和理论家。因此，它们提供了一个他们之间的强大的通信介质：从业者可以学习理论家如何使他们的模型更有条理，而理论家可以借鉴从业人员如何使模型更加逼真。从历史上看，Petr

3、i网的概念最初是由在1962年西德的Darmstadt大学数学和物理学院就读的Carl Adam Petri提交的论文中提出的。论文是当C.A.Petri在美国的Bonn大学作为科学家时就已经做了准备工作了，Petri的工作引起了后来在美国工程公司领导信息系统理论应用数据的研究的A.W.Holt的注意，Petri网的早期发展和应用（或前身）的报告就与这个项目有关，并在1970年的并行系统和并行计算的MAC会议中有相关的记录。从1970年到1975年，计算结构集团在麻省理工学院进行Petri网的相关的研究是最活跃的，并且产生了基于Petri网的大量的报告和论文。1975年七月，在麻省理工学院有一

4、个关于Petri网的会议，但没有出版相关的会议记录。1980年之前用英文写的与Petri网有关的大多数论文都被列举在了Petri网第一本书的参考注释里。更多最近的报告，直到1984年，这些在德国和欧洲其他国家完成的作品被注释在了另一本书里。有三篇教程文章用来提供对Petri网的补充，以便于更好的阅读和理解。从二十世纪七十年代末，欧洲人一直活跃于组织基于Petri网的研讨会和出版会议论文文集。1979年十月，大多数欧洲国家一共约135位研究学者聚集在了西德的汉堡，进行为期两周的关于过程和系统的通用网理论的高级教程的探讨。探讨过程中有17场讲座课程被出版，到目前为止还是绝版。影响力紧随其后的研讨会

5、是九月份在西德的Bad Honnef举行的。期间发表了34篇文章，包括了最近由C.A.Petri提出的两篇；一个是他的公理的并发理论，另一个是他进一步研究有关的建议。欧洲第一个Petri网的应用和理论的研讨会是1980年在法国Strasbourg举行的。从那以后，这一系列的研讨会每年在欧洲的不同地点举办：1981年，西德Bad Honnef；1982年，意大利的Varenna；1983年在法国的Toulouse；1984年，丹麦的Aarhus；1985年，芬兰Espoo；1986年在英国牛津；1987年在西班牙的Zaragoza；1988年，意大利威尼斯；1989年西德的Bad Honnef（

6、计划）。确定这些研讨会的程序于大多数的研讨会的参与者有关系。然而，从这些研讨会和其他文章选择的论文都已经由Springer Verlag作为Petri网的发展被出版了。1987年卷包含了最全面的Petri网的参考书目，它列举了从1962年到1987年初出版的2074项有关研究。Petri网络通信的最近出版物这个部分列出了最近出版物的短的摘要，这样的部分一年有三次，是一个关于最近的Petri网文学的很好的信息来源。1985年七月，另一个系列的国际研讨会启动。该系列强调定时和随机网及其应用性能评价。基于时间Petri网的第一次国际研讨会在意大利的都灵举行；第二届是1987年八月在Wisconsin

7、的Madison举行；第三届是在1989年十二月在日本的京都；第四届是1991年计划在澳大利亚。两个研讨会的第一个程序都可从IEEE计算机社会新闻中获知。以上是Petri网的一个简短的历史。现在，我们看一下在一些文献中被提到的Petri网的应用领域。Petri网得到了很广泛的应用。这是由于Petri网固有的一般性和宽容性。它们可以用于非正式的任何可以用流程图这种方式生动描述的地方和系统，作为一种可以表示平行或并发活动的手段。然而，在建模的一般性和分析能力方面尤其要注意，那是因为，模型越是一般，对它的分析就越发经得起检验。事实上，Petri网的一大弱点就是并发的一些复杂的问题，即，进行基于Pet

8、ri网模型哪怕是适度规模的系统的分析都会非常大。在应用Petri网时，添加一些特定的修改或者是限制往往是必要的。Petri网的两个成功的应用领域是性能评价和通信协议。有前景的应用领域包括对分布式软件系统的建模和分析，分布式数据库系统，并发和并行程序，柔性制造/工业控制系统，离散事件系统，多处理内存系统，数据流计算系统，容错系统，可编程逻辑阵列和VLSI，异步电路和结构，编译器与操作系统，办公信息系统，形式语言，和逻辑程序。其他文献中提及的有趣的应用有局域网，法律系统，人为因素，神经网络，数字滤波器，和决策模型。计算机辅助工具的使用在Petri网的实际应用中是很必要的。大多数的Petri网研究机

9、构拥有自己的软件包和工具，以便于在各种应用时进行辅助绘图，分析，和/或模拟。1986年时最近的一篇文章对典型Petri网工具提供了一个很好的概述。有些工具和它们的应用方面的细节在很多文献中都有提及到。本文的其余部分包括以下主题。第节论述没有容量约束的非正式的变迁使能和发射规则。第节中的几个介绍建模的例子用来说明建模能力和概念，如冲突（选择或决策），并发，同步，等。第部分介绍了行为或对标记的依赖可以使用Petri网的性质进行研究。第节提出了三种分析理论：可覆盖树，矩阵方程，并简化技术。第部分是关注和分析Petri网的子类网。第节给出了它的深入分析和合成方法作为一个亚类称为标记图。第节讨论了结构或

10、标记的独立特性。第节介绍了定时网，随机网，和高层次的网，以及它们的应用。第节主要是结束语。、变迁的使能和发射在本节中，我们要学习Petri网理论的唯一规则：变迁的使能和发射规则。虽然这条规则看起来很简单，它在Petri网中的含义却是非常深刻和复杂的。Petri网是一个有向图的一种特殊形式，一个初始的状态称为初始标识M0。一个基础为N的Petri网是一个有向的，有加权值，双向的由两种节点图，称为库所和变迁，让弧从一个库所到一个变迁过渡，或者从一个变迁到库所的过渡。用图形进行表示，库所用一个圆圈表示，变迁用短线或者方框表示。弧上有标记的权值（正整数），其中，k权值的弧可以解释为k平行设置弧。单位权

11、值通常略。如果一个标记通过非负整数k指向库所p，我们就说p标有k个托肯。看上去就是，我们把k个黑点（托肯）置于库所p。一个标志是由M表示，一个m元向量，其中m是库所的总数。M中的p组件，表示为M（p），是库所p中的托肯的数量。在建模中，使用条件和事件的概念，库所代表条件，变迁代表事件。一个变迁（事件）有一定数量的输入库所和输出库所分别代表着一个事件的前置条件和后置条件。存有一个托肯的库所被表示为库所包含的条件为真。另一个解释，k个托肯被置于一个库所用来表示该库所有k个数据项目或者资源可用。关于变迁和它的输入库所和输出库所的一些典型的解释如表1所示。一个Petri网的形式化定义在表2中给出。表1

12、 关于变迁和库所的几种典型的解释输入库所变迁输出库所前置条件事件后置条件输入数据计算步骤输出数据输入信号信号处理输出信号所需资源任务或工作资源发布条件逻辑子句结论缓存处理器缓存表2 Petri网的正式定义Petri网是一个五元组，pN =（p，T，F，W，M0）：p=p1，p2，pm是一组库所的有限集，T=t1，t2，tn是一个变迁的有限集，F（PT）（TP）是弧的集（流动关系），W：F1，2，3是权值数，M0：P0，1，2，3是主动标记，PT=且PT。Petri网结构，N=（P，T，F，W）没有任何特定的初始标记由N表示。给定的初始标记用（，M0）表示。许多系统的行为可以用系统自身状态及其变

13、化来表示。为了模拟一个系统的动态行为，Petri网的状态或标记根据下面的变迁（发射）规则来过渡变化：1） 变迁t表示在使能状态下t的每一个输入库所p至少有w（p，t）来表示的托肯，其中w（p，t）从p到t的弧的权值。2） 一个使能的变迁可以不发射（取决于事件是否真正发生过）。3） 变迁t发射一次就要从t的输入库所p中移除w（p，t）个托肯，并添加w（t，p）到它的输出库所p中，其中，w（t，p）表示从t到p的弧的权值。一个没有任何输入库所的变迁叫做源变迁，一个没有任何输出库所的变迁叫做汇变迁。这里要注意，源变迁为无条件使能，而一个汇变迁的发射只消耗托肯，却不会产生任何托肯。一对一的库所p和变迁

14、t的过渡叫做自环，即p既是变迁t的输入库所，同时也是它的输出库所。没有自环的Petri网叫做纯网。如果一个Petri网中的所有弧的权值都为1的话，这个Petri网就叫做一般网。例1：上述的转换规则可以用图1中最常见的化学公式来表示： 2H2+ O2 2H2O。图1（a）中表示每个输入库所中都有两个托肯意味着有两个单位的H2和O2可用，变迁t是使能的。当t发射后，标记就会改变，如图1（b）所示，其中变迁t不再使能。图1 例1：一个变迁（发射）规则的表示：（a）发射前t是使能时的标记，（b）发射后t不再使能时的标记。对于上述变迁使能时的发射规则，它是假定每一个库所可以容纳无限多的托肯。这样一个Pe

15、tri网被称为无限网。对于许多物理系统的建模，很自然的会考虑到每个库所可以容纳的托肯的数量上限。这样的网叫做有限容量网。对于一个有限容量网（，M0），每个库所p都有一个有关的容量K（p），表示在任何时间里p所能容纳的托肯的最大数量。对于有限容量网，当变迁t使能时，有一个附加条件，即，变迁t的输出库所p中的托肯的数量在t发射后不能超过p的容量即K（p）的值。有容量约束的规则叫做严格变迁规则，无容量约束的被称作（弱）变迁规则。给定一个有限容量网（，M0），它既可以应用严格变迁的规则，同样也可以应用弱变迁规则成为（N，M0），网可以从（，M0）通过以下的互补库所变换，前提是N必须是纯网。第一步：为每

16、个库所p添加一个互补库所p，p的初始标识由M0（p）=（p）-M0（p）。第二步：在每个变迁t和一些互补库所p之间，画新的有向弧（t，p）或者（p，t），其中w（t，p）=w（p，t），w（p，t）=w（t，p）， 这样，对于每个库所p，在变迁t发射前后，它和它的互补库所的容纳的托肯的总数等于它的容量K（p）。例2：当我们把严格变迁规则应用于图2（a）所示的有限容量网（，M0）中。在初始标识M0=（1 0）的情况下，只有变迁t1是使能的。当t1发射后，会得到M1=（2 0），这时只有t2和t3是使能的。t2发射后，M1就会变为M2=（0 0），或者t3发射后变成M3=（0 1）。继续这个过程，

17、很容易画出图2（c）所示的（可达性）图，该图在每个标识上表示所有可能的标识和所有可能的发射。现在，让我们看一下图2（a）的网（，M0）是怎样通过互补库所的变换转换成图2（b）所示的网（N，M0）。第一步是添加两个互补库所p1和p2以及它们的初始标识M0（p1）=K（p1）-M0（p1）=2-1=1，M0（p2） =K（p2）-M0（p2）=1-0=1。第二步是在每个变迁t和一些互补库所之间添加新的有向弧，使得在变迁t发射前后可以保持每对库所pi和pi中托肯的总数相同并且等于K（pi），i=1，2。例如，当w（t1，p1）=1，有w（p1，t1） =1。相同的，w（t3，p1） =w（p1，t3

18、）=2，并且w（p2，t3）=w（t3，p2）=1，当变迁t3发射时从p1中移除两个托肯，其中一个托肯添加到库所p2中（我们画一个从t3指向p1权值为2的有向弧，再画一个从p2指向t3的单位权值的有向弧），同样的，添加两个有向弧的弧（t2，p1）和（t4，p2）便可以得到图2（b）所示的网（N，M0）。以类似的方式，对于网（，M0）的图释很容易画出网（N，M0）的可达图，也很容易确定两个可达图是同构的，而且这两个网（，M0）和（N，M0）在发射序列的行为上是等价的。以上的讨论可以总结为以下的定理。图2 例2：对于互补库所转换的图释：（a）一个有限容量网（，M0）。（b）转换后的网（N，M0）。

19、（c）图（a）中网（，M0）的可达图。定理1：定义网（，M0）是一个纯的有限容量网，即严格变迁规则可以适用。定义网（N，M0）是网（，M0）通过互补库所转换得到，即弱变迁规则适用于网（N，M0）。那么这两个网（，M0）和（N，M0）在意义上是一样的，即它们拥有相同的可能的发射序列。通过定理1，我们知道每个纯的有限容量网（，M0）都可以通过转换得到它的等价网（N，M0），使得弱变迁规则可用，这样我们只需要考虑弱变迁规则。因此，除非另有说明，否则在本文的其余部分，我们只考虑适用弱变迁规则的无限容量网。这是因为，所有与有限容量网有关的属性都可以通过互补库所转换这种方法转换成无限容量网来进行讨论。在定

20、理1中，我们假定Petri网是纯网来避免混乱，这是因为在一个有限容量网中对于自环的使能条件有许多不同的解释。但这不是一个真正的限制，原因在于自环可以通过引入一对虚拟的变迁和库所进行“简化”或者转换成一个环，如图3所示。图3 自环变成一个环的转换、介绍建模实例在这一部分中，给出了几个简单的例子来向读者介绍Petri网的一些基本概念，这些概念在建模中都是很有用的。A有限状态机有限状态机和状态图可以用Petri网的一个子类等效表示。用一个有限状态机的例子来说明，考虑一个售货机接受任何五分和一角的硬币，卖15或20的糖果。为简单起见，假设售货机只能容纳20。那么，售货机的状态图就可以通过Petri网用

21、图4来表示，它的五个状态就可以用标记了0，5，10，15，20的五个库所来代表，从一个状态到另一个状态的转换可以通过标记了输入条件的变迁来表示，例如“存入5”。这个例子中的初始状态是通过把一个托肯放入标记为0的库所p1来表示。注意到，这个网的的每个变迁都有一个确定的输入弧和一个确定的输出弧。有此属性的Petri网的子类网称为状态机。任何状态机（或其状态图）都可以用一个状态机建模。库所p1的结构里，有两个（或者更多）输出变迁t1和t2，如图5所示，被称为冲突，决策，或选择，取决于实际应用。状态机允许决策的代表，但不允许并行活动的同步性。图4 代表退币环节被已省略的自动售货机状态图的Petri网（

22、状态机）图5 冲突，决策，或选择的Petri网结构。该结构具有不确定性。B并行活动并行或并发活动在Petri网里可以很容易地表达。例如，图6所示的Petri网，并行或并发活动用变迁t2和t3表示，它们在t1发射时开始，在t4发射时结束。一般情况下，如果两个变迁的因果关系独立就被称为并行，例如，一个变迁的发射可能在别的变迁发生之前，也可能在之后，还可能并行发射，就如图6中t2和t3的情况。已经指出，并行可以作为一个二元关系（通过c0在一系列事件A=e1，e2）有比如1）反射性（e1，c0，e1）和2）对称性（e1，c0，e2包含e2，c0，e1），3）不可变迁（e1，c0，e2和e2，c0，e3

23、不是必须包含e1，c0，e3）。例如，一个人可以开车（事件e1）或行走（事件e3）同时在唱歌（事件e2），但他不能开车同时又在走。图6 一个Petri网（一个标记图）表示的确定的并行活动注意，在图6所示的网中每个库所都有一个确定的输入弧和一个确定的输出弧。用此类属性的Petri网的子类别称为标记图。标记图可以表示并发但不选择（冲突）。两个事件e1和e2，如果它们可以出现但不能同时出现，那它们是冲突的，如果它们能在任何情况下同时出现时也没有冲突，那它们是并发事件。冲突和并发混合的情况称作混乱。图7展示了混乱的两个类型。图7（a）显示的是一个对称的混乱，因为其中两个事件t1和t2是并行的，但它们均

24、与事件t3冲突。图7（b）显示的是一个非对称的混乱，其中t1和t2是并行的，但当t2先发射时，t1将会和t3冲突。图7 混乱的两种类型。（a）对称的混乱：事件t1和t2是并行的，但它们均与事件t3冲突。（b）非对称的混乱：中t1和t2是并行的，但当t2在t1前发射时，t1将会和t3冲突。C数据流计算Petri网不仅可以用来表示控制流，还可以表示数据流。图8中的Petri网就表示了数据流计算。数据流计算机是一个在它的操作数到来之前执行指令就启用的，并可同时执行。在Petri网里表示一种数据流计算，托肯表示的是此时的数据以及数据的可用性。在图8所示的网中，通过变迁t1和t2表示的指令可以并行执行并

25、把产生的结果数据（a+b）或者（a-b）存入各自的输出库所中。图8 对于x=（a+b）（a-b）的数据流计算的Petri网D通信协议 通信协议是另一个可以用Petri网来表示和指定基本特征的系统。在通信协议中Petri网性能的活性与安全性（见第部分）是经常要使用的正确性标准。图9所示的Petri网是两个进程之间的一个非常简单的通信协议模型。图10表示一个不确定等待过程的Petri网，其中在规定时间（tout）内，如果响应1，或者响应2被收到，或者没有响应，那么相应的tr1，tr2，tout就会对应发射。 图9 一个通信协议的简单模型 图10 一个不确定等待过程的Petri网表示E同步控制在一个

26、多处理器或分布式处理系统中，资源和信息在几个处理器中共享。为了确保整个系统的正确操作，这种共享必须是可控或者同步的。Petri网模型已被用于各种各样的同步机制，包括相互排斥，读写过程，生产消费的问题。图11所示的是一个读写同步的Petri网，其中库所p1中有k个托肯，表示有k个进程（程序）可以被读取和写入由库所p3所代表的共享内存中。最多有k个进程可以被同时读取，但当一个进程被写入时，其它进程就不能被读取或写入。容易证明，如果库所p4中没有托肯，那么就有k个托肯（进程）在库所p2中（读取），并且只有一个托肯（进程）可以在p4中（写入），因为当t2发射一次时，库所p3中的所有k个托肯都将通过权值

27、为k的有向弧被移除。这个Petri网将会在第部分的例21中具体分析。图11 一个读写过程的Petri网表示F具有优先级的生产者消费者系统图12所示的是具有优先级的生产者消费者系统，例如，消费者A相对于消费者B有优先权，就意味着如果A缓存里有项目（即托肯）那么A就可以消费，但此时B不行，除非A缓存是空的而B缓存有项目（即托肯）。已经证实，该系统如果不引入一个叫作抑制弧的有向弧就不能进行建模。从一个库所到一个变迁的抑制弧通过一段虚线和一个小圆圈来表示终止，而不是在变迁上画一个箭头，例如图12中的从p3指向t7的有向弧。当输入库所中有一个托肯时抑制弧禁用变迁，当输入库所中没有托肯和其它（正常的）输入

28、库所中至少有一个托肯在每个弧权上时抑制弧让变迁使能。当变迁发射时，托肯不能通过抑制弧移动。带有抑制弧的这类Petri网叫做扩展Petri网。抑制弧的引入增加了测试“零”网（即，库所中不存在托肯）的能力，同时在图灵机层面上增加了Petri网的建模能力。图12 具有优先级的生产者消费者的扩展的Petri网G形式语言当一个Petri网中的变迁用一组不同的符号来标记，一个序列的变迁发射时产生的符号串。用所有可能的发射序列生成的字符串的集合定义了一个正式的语言称为Petri网语言。例如，考虑再一个标记Petri网中所有可能的变迁发射序列，如图13所示。很容易看到，（无符号），abc，aabbcc，aaa

29、bbbccc是通过所有可能的发射序列从在“初始库所”中的一个托肯表示的初始标记和当所有变迁都不使能的终止状态生成的字符串。从这个例子可以看出，这个网的语言通过L（M0）=anbncn|n0（一种上下文敏感的Petri网语言）。因为每个有限状态机都可以通过Petri网进行建模，每一个正则语言是一种Petri网语言。已经证明，所有的Petri网语言都是上下文敏感语言。图13 通过有标记的Petri网生成的上下文敏感的语言L（M0）=anbncn|n0H多处理器系统图14所示的Petri网就是一个有着五个处理器，三个公共存储器和两条总线的多处理器系统的模型，库所p1中有托肯表示处理器在它的私有存储器

30、中正在执行，库所p2中有托肯表示空闲的总线。变迁t1表示发出的访问请求，而p3中存储的是尚未送达的请求。p4中的托肯表示处理器正在访问公共存储器。p5中的托肯表示处理器请求访问一个正在被p4中的托肯（处理器）访问的公共存储器。t5的发射表示对p5中的处理器在排队的存储器访问的结束。t4的发射表示对没有突出要求的存储器的访问的结束（例如，当M（p4）-UM（p5）0，其中Ux=1当x0，Ux =0当x0时t4是使能的）。两个变迁t2和t3模拟存储器的选择：t3发射表示选择响应已经被p4中的处理器访问过的存储器。t2发射时表示选择响应其它任何一个存储器。实际上，图14所示的网模型也可以表示有着任意

31、多个处理器和存储器的双总线的多处理器系统。其中广义随机网和更详细的模型已被用于多处理器体系结构的性能研究。图14 一个多处理器系统的Petri网模型，其中p1中的托肯表示活动的存储器，p2是可用的总线，p3，p4和p5处理器分别表示正在等待，正在访问和对公共存储器的排队。、行为特性用Petri网对系统进行建模之后，一个明显的问题就出来了“我们可以用这个模型做什么？”Petri网的一个主要功能是能对与并行系统有关的特性和问题进行协助和分析。两种类型的特性可以用Petri网模型进行研究：那些依赖于初始标识，和那些独立于初始标识的特性。前一种类型的特性被称为标记的依赖或者行为特性，而后一种类型的特性

32、叫做结构特性。在本节中，我们只讨论基本的行为特性和它们的分析问题。结构特性和对它们的分析将会在第节才进行考虑。A可达性可达性对于研究任何系统的动态特性都是最基本的基础原则。一个使能的变迁根据第节说过的变迁规则进行都将改变一个网中托肯的分配（标记）。一个发射序列将决定着一个标记序列。假如存在一个发射序列使得标记M0转换到Mn，那么就说标记Mn从标记M0是可达的。一个发射或事件序列可以通过=M0 t1 M1 t2 M2tn Mn或者用简单的=t1 t2tn来表示。在这个例子中，Mn通过从M0是可达的，我们写成M0 Mn。在网（N，M0）中所有从M0可达的可能的标记集合可以写成R（N，M0）或者简单

33、的R（M0）。在网（N，M0）中所有从M0可能的发射序列可以通过L（N，M0）或者简单的L（M0）来表示。现在，假如在网（N，M0）中对于给定的标记Mn并且有MnR（M0），那么对于Petri网的可达性问题就是寻找的问题。在一些应用方面，你可能只对库所子集的标记感兴趣，而不关心其它的库所。这就会导致子标记的可达性问题，即假如MnR（M0）时寻找的问题，其中Mn对于一个给定的子集跟随一个给定的标记Mn的限制的任何标记。已经证实可达性问题是可以决定的虽然一般情况下它至少需要指数的空间（和时间）来进行验证。然而，等价性问题却是不可决定的，例如，对于任意两个网N和N，假如L（N，M0）=L（N，M0）

34、没有算法可以确定。B有界性如果一个Petri网（N，M0）里每个库所中的托肯都不超过一个有限数k对于M0到任何可达的标记那我们就说这个网是k有界的或者简单地说是有界的，例如，对于每个库所p都有M（p）k，对于每个标记M都有MR（M0）。一个Petri网是1有界的那么就说该网是安全的。例如，图2（b）中所示的网，4，6，和9全都是有界的；很明显，图2（b）所示的网是2有界的，其它的网都是安全的。Petri网中的库所经常用来表示缓存和寄存器用来存储中间数据。通过验证，网有界或者安全，这可以保证缓存或者寄存器没有溢出，不管发射顺序是什么。C活性在操作系统中，活性的概念往往与完全没有死锁密切相关。如果

35、一个Petri网（N，M0）是活的（或者等价于说M0对于网N来说是活的），不管从M0到达哪个标记，通过一些之前的发射序列逐步直到发射最后的变迁都是有可能的。这就意味着一个活的Petri网能保证无死锁的操作，不管选择了哪样的发射序列。例如图4，6和9所示的活的Petri网。另一方面，图15和图16所示的Petri网就是不活的。这些网是不活的原因在于如果t1先发射，在这两种情况下都没有变迁可以发射。图15 一个安全，不活的Petri网，但它是严格的L1活性活性是许多系统的理想特性。不过，对于大型计算机操作系统这种系统来说，验证这个特性却是不切实际而且非常耗资源的。因此，我们放宽活性的条件，按照下面

36、说的来重新定义不同程度的活性。在一个Petri网（N，M0）中一个变迁t可以是下列几种情况：0）不活的（L0活性），如果t在L（M0）中在任何发射序列中都不能发射。1）L1活性（有发射的潜在性），如果t在L（M0）的一些发射序列下至少可以发射一次。2）L2活性，对于给定的正整数k，t在L（M0）的一些发射序列下至少可以发射k次。3）L3活性，如果t出现无界，通常是在L（M0）的一些发射序列里。4）L4活性或者活的，如果t对于每一个R（M0）中的标记M都是L1活的。如果Petri网（N，M0）里的每一个变迁都是Lk活的，其中k=0，1，2，3，4，那么就说这个Petri网（N，M0）是Lk活的。

37、 其中L4活性最强对应于先前定义的活性。容易看出下列的含义：L4活性L3活性L2活性L1活性，库所意味着“包含”。如果一个变迁是Lk活性的但不是L（k+1）活性，其中k=1，2，3，我们就说这个变迁是严格Lk活性。例3：图15所示的Petri网是严格L1活性的，因为网里的每个库所都跟t2，t4，t5，t1和t3一样恰好都只能发射一次。图16中的变迁t0，t1，t2和t3是分别是L0活性（不活的），L1活性，L2活性，和L3活性，并且全都是严格的。图16 变迁t0，t1，t2和t3分别是不活的（L0活性），L1活性，L2活性和L3活性D可逆性和家态Petri网（N，M0）的可逆性是说，对于R（M

38、0）的每一个标记M，M0从M都是可达的。因此，一个可逆的Petri网随时都可以回到初始标识和状态。在许多应用中，回到初始状态跟回到某些状态（家态）一样都不是必须的。这样，我们放宽可逆的条件然后重新定义一个家态。如果标记M定义为家态，那么对于R（M0）里的每一个标记M，M从M都是可达的。例4：注意上述的三种特性（有界性，活性，和可逆性）是相互独立的。例如，一个可逆的网可以是活的也可以是不活的，同样可以是有界的也可以是无界的。图17所示的八个Petri网的例子是这三种特性的所有可能的排列组合，其中B， L和R分别表示有界性（B），活性（L），和可逆性（R）的取反。E可覆盖性对于一个Petri网（N

39、，M0）中的标记M，假如在R（M0）中存在一个标记M，对于网里的每一个p都有M（p）M（p），那么我们就说这个标记M是可覆盖的。可覆盖性与L1活性（有发射的潜在性）密切相关。设M为最小标记需要变迁t是使能的。当且仅当M是不可覆盖时t是不活的（不是L1活性）。相反的，当且仅当M是可覆盖时，t是L1活性。F持久性对于一个Petri网（N，M0）来说，假如其中任意两个使能的变迁，一个变迁的发射不会导致另一个变迁不使能，那么就说这个Petri网是持久的。一个持久的网中的一个变迁，一旦它是使能的，就会一直保持使能状态直到它发射。持久的概念在并行程序图式和速度独立的异步电路的情况下是很有用的。持久的概念与

40、自由冲突网密切相关，一个安全的持久网可以通过重复一些变迁和库所转换成一个标记图。注意到所有的标记图都是持久的，但不是所有的持久网都是标记图。例如，图17（c）所示的网就是一个持久的网，但不是一个标记图。图17 有着以下特性的所有可能的排列组合的Petri网例子：B（有界的），B（无界的），L（活的），L（不活的），R（可逆的），R（不可逆的）。（a）BLR （t1不活，p1无界）。（b）BLR（t1不活，p1无界）。（c）BLR（p2无界）。（d）BLR（t1，t2，t3，t4都不是L4活性）。（e）BLR（p1无界）。（f）BLR（t1不活）。（g）BLR。（h）BLR。G同步距离在C.A.

41、Petri介绍的同步距离的概念是一个基本概念。在一个条件/事件系统中，同步距离是与两个事件之间相互依赖的关系密切相关的度量。我们通过以下的公式来定义Petri网（N，M0）中两个变迁t1和t2之间的同步距离 d12=max|（t1）-（t2）| （1）其中在R（M0）从任意标记M开始的发射序列，（ti）表示变迁ti在中发射的次数，i=1，2。例如，图17（d）所示的Petri网中d12=1，d34=1，d13=，等等。在图6所示的Petri网中变迁t2和t3代表两个并行的事件，其中d23=2，因为在t3发射后就会出现一个发射序列=t2 t4 t1 t2，其中（t2）=2，（t3）=0。通过公式

42、（1）给出的同步距离在条件/事件网和标记图中代表了一个明确的度量。然而，当它应用于一些更为一般层次的Petri网时也会出现一些问题。关于同步距离的更多信息，读者可以参考注释105，181186去了解。H公平性在关于Petri网的文献中已经提出了很多不同的有关公平性的概念。在这里我们提出两个基本的公平性概念：有界公平和无条件公平（全局公平）。两个变迁t1和t2如果一个变迁所触发的最大次数有限，而另一个变迁没有触发，那么就说这个变迁对满足于有界公平关系（或B公平）。如果一个Petri网（N，M0）中所有的变迁对都满足于B公平关系，那么就说该网是B公平的。对于一个发射序列，如果它是有限的或者网中的每

43、一个变迁在序列中触发无限次，那么就称这个发射序列是无条件公平（全局公平）的。如果一个Petri网（N，M0）中从M到R（M0）的每一个发射序列都是无条件公平的，那么就说这个Petri网是无条件公平的。在这两种类型的公平性之间还有一些联系。例如，每一个B公平的网都是一个无条件公平的网，同时每一个有界无条件公平的网都是B公平的网。图17（h）所示的网就是一个B公平的网同时也是一个无条件公平的网。图17（d）所示的网既不是一个B公平的网也不是一个无条件公平的网，因为t3和t4并没有出现在一个有限发射序列=t2 t1 t2 t1中。图17（c）所示的无界网就是一个无条件公平的网但不是B公平的网，因为当p2中的托肯数量是无限时t2单独发射的次数没有约束。关于公平性的更多信息，读者可以参照注释187197，211。V分析方法对Petri网的分析方法可以分为以下三个组：1）可覆盖（可达）树方法，2）矩阵方程法，和3）简化分解法。第一种方法基本上涵盖了所有可达标识或者它们覆盖的标记的枚举。它应该可以应用于所有类别的网，但仅限于“小”网，因为考虑到状态空间爆炸的复杂性。另一方面，矩阵方程和简化技术非常强大，但在许多情况下，它们只适用于Petri网的特殊子类网或者特殊情况。