（机械电子工程专业论文）petri网可达图的并行算法.pdf

摘要 死锁是柔性制造系统必须考虑和解决的问题。由于p e l r i 网具有可以检测死锁 并建立死锁控制策略来处理死锁的能力，它们适合建模和控制f m s 系统中的死锁 问题。可达图反映了一个网系统的所有动态行为，这使得它成为p e l r i 网死锁控制 的一种重要分析技术。可是，一个p e l r i 网可达图的规模和网结构及其初始标识的 大小成指数关系。这使得枚举网的所有可达状态变得困难，同时也是非常耗时的。 论文致力于p e t f i 网可达图的并行算法。传统的方法计算规模大的p e t r i 网时经 常遇到两个问题：过长的计算时间和内存溢出。为了克服以上问题，本文利用并 行算法求解一个给定网的所有可达状态，并通过一些例子验证了该算法的高效性。 在论文中，主要做了三方面的工作。 1 单进程的算法求出一个p e l r i 网的所有可达状态。这个算法比传统的算法在 求解所有可达状态有更高的效率。 2 多进程计算p e t r i 网所有可达状态。由于每个进程在一台独立的计算机上执 行任务，因此总的计算效率显然提高了并且计算时间明显减少。 3 由于每个进程都存储了所有的可达标识，使得并行算法可能会产生内存溢 出问题。因此，为了克服内存溢出，可达标识被划分成不同的集合并且每 个进程存储集合中的一个。这样，这个算法求解效率很高并且能够处理规 模大的p e t r i 网。 关键字：p e t r i 网死锁可达图并行算法内存 a b s t r a c t d e a d l o c k sa r eas e r i o u sp r o b l e mi nf l e x i b l em a n u f a c t u r i n gs y s t e m s ( f m s s ) p e t r i n e t sa r es u i t a b l et om o d e la n dc o n t r o lf m s si nt h o s es y s t e m sd u et ot h e i ra b i l i t i e st o d e t e c td e a d l o c k sa n dd e v e l o pp o l i c i e st oh a n d l et h e m r e a c h a b i l i t yg r a p h sa n a l y s i si sa n i m p o r t a n tp e t r in e ta n a l y s i st e c h n i q u ef o rd e a d l o c kc o n t r o ls i n c ear e a c h a b i l i t yg r a p h r e f l e c t st h ec o m p l e t eb e h a v i o ro fan e ts y s t e m h o w e v e r t h en u m b e ro fr e a c h a b l e m a r k i n g so fan e tm o d e li n c r e a s e se x p o n e n t i a l l yw i t hr e s p e c tt oi t s s i z ea n di n i t i a l m a r k i n g c o m p l e t es t a t ee n u m e r a t i o na l w a y ss u f f e r sf r o mas t a t ee x p l o s i o np r o b l e m t h ec o m p u t a t i o no far e a c h a b i l i t yg r a p hi sk n o w nt ob ev e r yt i m e c o n s u m i n g t i l i st h e s i sf o c u s e so nt h ep a r a l l e la l g o r i t h m sf o rc o m p u t i n gt h er e a c h a b i l i t yg r a p h o fap e t r in e t 1 1 1 et r a d i t i o n a lm e t h o d st oc o m p u t et h er e a c h a b i l i t yg r a p ho fal a r g e - s i z e d p e t r in e ta l w a y ss u f f e rf r o mt w op r o b l e m s ：l o n gc o m p u t i n gt i m ea n dm e m o r yo v e r f l o w i no r d e rt oo v e r c o m et h ea b o v ep r o b l e m s p a r a l l e la l g o r i t h m sa r ed e v e l o p e dt o e n u m e r a t et h er e a c h a b l em a r k i n g so fag i v e nn e tm o d e l an u m b e ro fe x a m p l e sa l eu s e d t os h o wt h ee 伍c i e n c yo ft h ep r o p o s e dm e t h o d s i ns u m m a r y , t h r e ea r em a i n l yt h r e e c o n t r i b u t i o n si nt h et h e s i s ，a sp r e s e n t e db e l o w 1 a na l g o r i t h mw i t hs i n g l ep r o c e s si sp r o p o s e dt of r e da l lr e a c h a b l em a r k i n g so fa p e t r in e t t h ea l g o f i t h r ni sa ni m p r o v e dv e r s i o no ft h et r a d i t i o n a lo n ef o rc o m p u t i n g r e a c h a b l em a r k i n g sa n di ti sm o r ee 伍c i e n tt h a nt h et r a d i t i o n a lo n e 2 ap a r a l l e la l g o r i t h mi sd e v e l o p e d , w h i c ha s s i g n st h ec o m p u t a t i o no fr e a c h a b l e m a r k i n g si n t od i f f e r e n tp r o c e s s e s s i n c ee a c hp r o c e s si sc a r r i e do u ti na ni n d e p e n d e n t c o m p u t e r , t h et o t a lc o m p u t a t i o n a le f f i c i e n c yi si m p r o v e da n dt h ec o m p u t a t i o n a lt i m ei s a c c o r d i n g l yr e d u c e d 3 1 1 1 ep a r a l l e la l g o r i t h mm a ys u f f e rf r o mt h em e m o r yo v e r f l o wp r o b l e ms i n c ee a c h p r o c e s ss a v e sa l lt h eg e n e r a t e dm a r k i n g s t h u s a ni m p r o v e dv e r s i o no ft h ep a r a l l e l a l g o r i t h mi sd e v e l o p e dt oo v e r c o m et h ep r o b l e m 啊1 er e a c h a b l em a r k i n g sa r ed i v i d e d i n t os e v e r a ls e t sa n de a c hp r o c e s ss a v e so n eo ft h e m i nt h i sc a s e 。t h ea l g o r i t h mi sr a t h e r e 伍c i e n ta n da l s oc a l ld e a l 、耐t hl a r g e s i z e dp e t r in e tm o d e l s k e yw o r d s ：p e t r in e t d e a d l o c k r e a c h a b i l i t yg r a p h p a r a l l e la l g o r i t h m m e m o r y 目录 第一章绪论1 1 1 研究背景与意义1 1 1 1p e t r i 网简介1 1 1 2 死锁和基于区域理论控制方法所产生的问题2 1 2 本文完成的主要工作4 第二章p e t r i 网的基本理论7 2 1p e t r i 网的基本定义7 2 2p e t r i 网变迁的发射规则8 2 3p e t r i 网的可达图一l1 第三章并行算法的基本理论1 5 3 1 并行算法的基本知识。1 5 3 1 1 并行问题的求解模型图1 5 3 1 2 并行计算机的类型15 3 1 3 并行算法分类17 3 2m p i 的基本知识理论18 3 2 1m p i 的六个基本函数介绍1 9 3 2 2m p i 消息发射规则2 0 3 2 3m p i 的通信分类2 l 3 2 4 避免死锁的通信调用次序2 2 3 2 5 计算7 r 的m p i 程序2 4 第四章p e t r i 网可达图并行算法2 7 4 1p e t r i 网可达图串行算法分析2 7 4 1 1 可达图的串行程序分析2 7 4 1 2 并行粒度粗细问题2 9 4 2p e t r i 网可达图并行算法3 0 4 2 1 可达图的并行算法3 0 4 2 2 可达图的改进并行算法3 4 4 2 3 分配存储标识的并行算法3 8 4 3 三种算法的并行程度的比较4 5 第五章可达图并行算法的实验结果与分析4 7 5 1 并行环境的设置和配置4 7 5 1 1 机群系统的原理和技术4 7 5 1 2 硬件的选择和安装4 7 5 1 3 系统的构建4 8 5 1 4 机群系统配置如下：4 8 5 1 5 软件的选择和安装4 9 5 - 2 并行算法性能分析4 9 5 2 1 加速系数4 9 5 2 2 并行算法中通信时间分析5 1 5 3p e t r i 网可达图并行算法的测试结果5 2 5 3 1p e t r i 网可达图并行算法4 2 与i n a 的测试结果5 2 5 3 2 分析算法4 3 与i n a 的测试结果5 8 第六章总结6 1 致谢6 3 参考文献。6 5 附录ap n t 文件6 9 第一章绪论 1 1 1p e t r i 网简介 第一章绪论 1 1 研究背景与意义 p e t r i 网的概念源于德国学者c a r l p e t r i 于1 9 6 2 年所发表的博士论文“自动 机通信”。它是根据系统事件之间的因果关系，经过理论抽象而形成的一种网图。 它是一种适用于多种系统的图形化、数学化的建模工具。为描述和研究具有并行、 异步、分布式和随机性等特征的信息加工系统提供了强有力的手段。通过对该图 用数学的、图论的方法进行分析和处理，就能搞清楚原系统的内在关系，并实施 对原系统的优化和控制。与传统的系统建模、分析和控制方法相比，p e t r i 网能够 提供一个集成的建模、分析和控制环境，为系统的设计提供了便利。经过四十多 年的发展，p e t r i 网理论已经成为具有严密数学模型，多抽象层次、多用途的通用 网论，并逐渐成为各相关学科的“通用语言”，并且在离散事件系统( d e s - d i s c r e t e e v e n ts y s t e m ) 控制领域得到广泛的应用。 p e t r i 网采用可视化图形描述，表达d e s 的静态结构和动态变化。它是一种结 构化的d e s 描述工具，可以描述系统异步、同步、并行逻辑关系。它既能够分析 系统运行性能( 如制造系统设备使用率、生产率、可靠性等) ，又可以用于检查与 防止诸如自动系统的死锁、资源冲突等不期望的系统行为性能；可用于d e s 的仿 真，从而对系统进行分析与评估；可以模块化与层次化地描述复杂的d e s ；可以 通过结构变化描述系统的变化等。正是由于上述特点，p e t r i 网已经成为描述、分 析和控制d e s 最有效和应用最广泛的方法之一。 如前所述，p e t r i 网是系统事件因果关系的一种抽象网图，具体的说，它是一 种双枝有向图。一个事件发生主要由三个部分组成条件、过程和结果。在p e t f i 网里，把条件和结果用同一类图形表示，因为一个事件的结果往往是另一个事件 的条件，从这个角度讲它们并没有本质的差别。而把过程用另一类图形表示，过 程有可能是瞬时的，也可能是漫长的，但对于这个过程中的东西是不需要被关注 的。通行的表示方法是用圆圈表示条件和结果，并称之为库所( p l a c e ) ；用矩形( 或 杠) 表示过程，并称之为变迁( t r a n s i t i o n ) 。库所内可有黑点( t o k e n ) 或数字，表示条件 或结果的持有数。库所和变迁统称为结点，它们之间的直接因果关系用有向弧来 表示。当然同一类结点间不会有弧连接，因为它们之间不会直接发生关系。事件 的发生对条件和结果的作用量用弧上的权值表示。一种条件或结果的持有数状况， 称之为一个状态。当一个过程的条件具备之后，这个过程就可能发生，称之为变 迁的发射。变迁发射后，一个网就会从一个状态跃迁到另一个状态。经过这样的 2p e t r i 网可达图的并行算法 模型构建后，一个因果系统就被抽象成为一个网图。 客观世界的很多过程都可以抽象成一个p e t r i 网，比如下面这个化学过程： 燃烧 电解 2 h 2 + 0 2 2 h 2 02 h 2 0 一2 h 2 + 0 2 可用p e t r i 网表示为： 屯 p a 图1 1 化学过程中的p e t r i 网建模 其中，a 、p 2p 3 分别表示h ：、o ：和h ：o ；f l 和乞分别表示燃烧和电解。 1 1 2 死锁和基于区域理论控制方法所产生的问题 死锁问题的研究起源于操作系统中的资源分配问题。死锁就是系统在某种状 态下，系统继续向下演化的条件不具备，从而使系统处于一种停滞状态。一般认 为，死锁产生的主要原因是：( a ) 系统资源不足；( b ) 进程允许推进的顺序不当；( c ) 资源分配不当。c o f f m a n 等给出了系统死锁的四个必要( 但非充分) 条件： 1 相互抑带s j ( m u t u a le x c l u s i o n ) ：一个资源每次只能被一个进程使用。 2 持有并等待( h o l da n dw a i t ) ：持有资源的进程允许申请其它资源。 3 非剥夺条件( n op r e e m p t i o n ) ：除非资源被释放，否则一个资源不允许被强行 剥夺。 4 循环等待( c i r c u l a rw a i 0 ：若干进程形成了一个进程链，该进程链中的每一 个成员等待着它的下一个进程持有的资源。 死锁在很多情况下是不希望发生的，它有时会带来非常严重的后果，如在自 动炼钢生产系统中，一旦出现死锁将可能使钢水凝固，从而使得某些设备报废， 造成重大生产事故。正因如此，死锁的研究和控制就显得十分重要。处理死锁的 方法一般分为四种。第一是忽略死锁，即所谓的鸵鸟算法( o s t r i c ha j g o r i t h m ) 。如果 避免死锁的代价比死锁造成的损失还要大，就可以忽略死锁，。第二种方法称为死 锁的检测与恢复( d e a d l o c kd e t e c t i o na n dr e c o v e r y ) 。这种方法允许死锁发生，并不断 检测。一旦检测到死锁，便采取相应的措施恢复系统的运行。第三种方法是死锁 避免( d e a d l o c ka v o i d a n c e ) ，就是在系统的运行过程中，对进程发出的每一个资源申 请进行动态检测，并根据检测结果决定是否分配资源。若分配后系统可能发生死锁， 第一章绪论 则不予分配，否则予以分配。最后一种方法是死锁预防( d e a d l o c kp r e v e n t i o n ) ，是使 以上发生死锁的四个必要条件之一不成立。因此可以看出第一种方法不需对系统 内部做过多分析，第二种和第三种方法需要在线控制，p e t r i 网则是第四种方法一 死锁预防的重要分析工具之一。基于p e t r i 网的死锁预防是一种静态方法，它使用离 线方式控制某些变迁的发射，从而保证系统不会发生死锁。 在p e t r i 网的监督器设计中，从基于理论的不同，主要有两种分析方法：可达图 分析法和结构分析法。结构分析法( 如信标) 往往控制策略比较简单，缺点是所得到 的监督往往不是最大许可的。而可达图分析法往往可求得最优的或次优的拥有高 许可行为的监督器。基于可达图的方法主要是找出那些危险的状态，因为从这些 状态出发，一个网可能会演化成死锁，也可能不会。因此对那些可能会引起死锁 的变迁的发射进行限制，就可以阻止其向死锁演化，从而保证受控系统没有死锁。 区域理论是这种方法的一个典型运用。但基于可达图的方法往往需要列举一个网 所有的可达状态，而可达状态又与网的规模成指数关系。对于规模较大的网，求 一个网的所有可达状态还是相当困难的。 针对以上问题，本文提出可达图并行的算法，当网的规模很大的时候，其可 达状态数急剧增加。此时，求解网的所有可达状态需要耗费大量的时间。当网的 状态增加到一定数量( 如上百万) ，此时会出现内存溢出问题，由此引发了两个问题： 1 怎么样更高效地求解网的所有可达状态； 2 当网的状态数较大的时候，能够解决内存溢出问题，并高效地计算出所有 可达状态； 基于以上两种情况，如果内存不足就可以增加多台计算机来增加可用内存， 从而在一定程度上解决内存溢出问题。并且现在很多研究者都在研究和使用并行 算法【6 】阴【8 1 1 9 1 1 0 l ，并行算法可以有效的利用多台计算机来协作完成同一任务。由此 利用并行算法来计算p e t r i 网的所有可达状态，不但可以有效解决计算时间复杂度 问题，也能够有效克服因状态爆炸所导致的内存溢出问题。现在并行算法比较通 用的平台是m p i 。因此，本文采用m p i 作为实验平台。 利用并行算法求解可达图问题，其关键是怎么样能够把可达图的求解问题划 分为几个独立的问题或者相关联的问题。如果可达图问题能够划分成独立的，那 么各个问题之间就不存在着相互依赖关系，这样避免了进程间的相互通信，从而 可以达到用最快的速度来求解网的所有可达状态。但是，p e t r i 网可达图的计算问 题并不能得到完全独立的划分方法。基于此，我们将该问题划分成几个相互依赖 的模块。为了叙述的更加清晰，根据文献f l 】中的算法2 1 ，定3 ( f i o l d 为有标号的 标识的集合，兀，删为没有标号的标识的集合，每次在n ，删中取出一个标识m 后， 在m 下每使能一个变迁都会有一个新的状态产生，兀一耐表示这些新产生的状态 的集合。首先，我们把n 。，府平分给所有的进程，让它们分别判断是否为好的标 4 p e t r i 网可达图的并行算法 识，这个算法比串行算法在速度上具有优越性。但是它的缺点是：在一个状态下 使能的变迁是有限的，产生新的标识( 即兀。，。中元素的个数) 也是有限的，从而限 制了进程数。基于这点，对以上的算法做了改进，让每个进程处理n ，中不同的 标识，并判断在该标识下是否有使能的变迁。由于兀，耐中元素的个数都比较大， 所以进程数不再受到限制，效率同样得到了提高。这个算法的缺点是：不能够解 决内存溢出问题，因为每个进程都存储相同的有标号的标识( 即n 删) 。多台计算 机最大的优越性是它比单计算机具有更大的总主存储器容量，针对p e t r i 网可达图 求解问题，可以将有标号的标识按照某种规则划分成不同的集合，并分别存储到 不同的进程中。如果并行算法所用的进程数为n ，那么并行算法能够存储的可达状 态数是串行算法的n 倍。 1 2 本文完成的主要工作 本文主要完成了以下几项工作： 1 分析了参考文献【1 】中的串行算法，编写了该串行算法的程序( 详细见2 2 ) ， 找出了这个算法中最耗时的地方，以便后面可达图问题的并行划分。并行算法是 在串行算法最优的基础上展开的，通过对编写的串行程序不断的优化，最终达到 了用传统的方法计算可达图的效率。 2 p e 仃i 网可达图并行算法的实验平台是m p i 。首先要搭建并行环境，然后分 析m p i 对外的接口函数。利用并行算法求解可达图问题，其关键是怎么样能够把 可达图的求解问题划分为几个独立的问题或者相关联的问题。如果可达图问题能 够划分成独立的，那么各个问题之间就不存在着相互依赖关系，这样避免了进程 间的相互通信，从而可以达到用最快的速度来求解网的所有可达状态。但是，p e l r i 网可达图的计算问题并不能得到完全独立的划分方法。基于此，我们将该问题划 分成几个相互依赖的模块。为了叙述的更加清晰，根据文献【l 】中的算法2 1 ，定义 n 。膨为有标号的标识的集合，n ，删为没有标号的标识的集合，每次在兀，删中取 出一个标识m 后，在m 下每使能一个变迁都会有一个新的状态产生，i 。i 。表 示这些新产生的状态的集合。首先，我们把r i 。，。平分给所有的进程，让它们分 别判断是否为好的标识，这个算法比串行算法在速度上具有优越性。但是它的缺 点是：在一个状态下使能的变迁是有限的，产生新的标识( 即i i 。耐中元素的个数) 也是有限的，从而限制了进程数。 3 基于这点，对以上的算法做了改进，让每个进程处理兀一，中不同的标识， 并判断在该标识下是否有使能的变迁。由于r i 。中元素的个数都比较大，所以 进程数不再受到限制，效率同样得到了提高。这个算法的缺点是：不能够解决内 第一章绪论 存溢出问题，因为每个进程都存储相同的有标号的标识( 即n 疗瞄) 。 4 多台计算机最大的优越性是它比单计算机具有更大的总主存储器容量，针 对p e t r i 网可达图求解问题，可以将有标号的标识按照某种规则划分成不同的集合， 并分别存储到不同的进程中。如果并行算法所用的进程数为n ，那么并行算法能够 存储的可达状态数是串行算法的n 倍。 通过上述工作，对p e t r i 网可达图的并行算法有了更为深入的理解，并为进一步 的研究打下了一点基础。 由于时间和作者水平有限，文中定有不足和错误之处，恳请批评指正。 6p e t r i 网可达图的并行算法 自p e t r i 网的提出至今已有四十多年的历史，其基本理论已十分成熟。本章只 涉及本文后续章节所要用到的概念、定义和定理等。本章内容主要来自文献【1 】。 2 1p e t r i 网的基本定义 【定义2 1 l p e t r i 网是一个四元组n = ( 尸，t ，f ，形) ，可表示为n = ( p ，t ，f ，w ) ， 其中： 1 ) p 代表库所的集合； 2 ) r 代表变迁的集合，且尸和r 是有限非空和不相交的集合； 3 ) ，g ( p x t ) u ( t p ) 称为有向弧集； 4 ) w ：f 专n o 称为尸中弧上的权，肼= o ，1 ，2 ， ； 当且仅当v f f ，w = 1 ，称n = ( p ，t ，f ，矿) 为普通网( o r d i n a r yn e t ) ，记作 n = ( p ，t ，f ，形) 。 从图论上来讲，p e t r i 网是一种双枝有向图，库所( p l a c e ) 和变迁( t r a n s i t i o n ) 称为 p e t r i 网的节点( n o d e ) 。用图形表示p e t r i 网时，变迁用矩形或者杠( b a r ) 表示。库所 和变迁之间用有向弧连接，同一类型的接点之间不能用有向弧连接。 l 定义2 2 lp e t r i 网n = ( p ，t ，f ，w ) 的标识m 是一个从尸到n 的映射。( ，眠) 网系统和标识网，眠称为的初始标识。在不引起混淆的情况下，可以简单地称 ( ，) 为p e t d 网。( n ，m o ) 有时候写成( p ，丁，f ，形，) 。 库所中的标识用称之为托肯( t o k e n ) 的小黑点表示。当托肯的数量比较大时，可 直接用数字表示。 【定义2 3 】令p p 是p e t r i 网n = ( 尸，t ，f ，w ) 的库所。称p 在膨下是被标记的 当且仅当m ( p ) 0 。称库所集d p 在m 下是被标记的当且仅当d 中至少有一个 库所被标记。称m ( d ) = 脚m ( p ) 为库所子集d 在m 下的托肯数总和。 l 定义2 4 l 令n = ( p ，t ，f ，w ) 是一个p e t r i 网，节点x p u t 的前置集定义为 。x = y p u tl ( y ，x ) f ) ，其后置集定义为x = y p u ti ( x ，y ) f ) 。节点的集 合片p u t 的前置集( 后置集) 定义为。日= u ，。z 。x ( h = u ，。j x 。) 。 若x 是库所，其前置集中的元素成为其输入变迁，后置集中的元素称为输出变 迁。若x 是变迁，其前置集中的元素称为其输入库所，后置集中的元素称为其输出 库所。 【定义2 5 】令n = ( p ，t ，f ，w ) 是一个纯网，是纯的或者是无自环的网当且仅 当不存在( x ，y ) ( p x t ) u ( t x p ) 使得( x ，y ) f 和( y ，x ) f 同时成立。 8 p e t r i 网可达图的并行算法 2 2p e t r i 网变迁的发射规则 i 定义2 6 1 令n = ( p ，t ，f ，形) 是一个网， 1 ) 一个变迁f t 在m 下称为使能的，记为m t ，当且仅当v p f ： m ( p ) w ( p ，) ； 2 ) 若m t 成立，n t 发射后，产生另一新标识m ，记为m t ) m ，有 im ( p ) - g ( p ，) p t t m ，( p ) = m ( p ) + 形( p ，f ) p 广。r “7 lm ( p ) 一w ( p ，f ) + 形o ，p ) p n 广 【m ( p ) d t h p 船 3 ) 网从标识眠开始的所有可达标识的集合记为r ( n ，) 或眠d 。它是一个最 小集，即m o r ( ，m o ) ，m r ( n ，m o ) m p m jm r ( u ，眠) ； 4 ) 当且仅当存在标识眠，m ，鸠满足心【) 阮 鸠，仃= 他厶为发射序列； 5 ) 若存在标识m 使得m a ) m ，m = m o + c y ，其中c 为关联矩阵，】，为发射序 列矢量，其第i 个数值代表第f 个变迁在序列盯中出现的次数。 【定义2 7 】令( ，) 是一个p e t r i 网。从心可达的所有标识的集合称为( ，心) 可达集，记为r ( u ，坛) 。 i 定义2 8 l 令n = ( p ，t ，f ，形) 是一个纯网。的关联矩阵【】是一个以p xt 为 序列的整数矩阵，【】( p ，) = w ( t ，p ) - w ( p ，f ) 。库所p 对应的行向量称为p 的关联 矩阵，记做【】( p ，) 。变迁，对应的列向量称为f 的关联向量，记做【】( ，f ) 。 【定义2 9 】令n = ( p ，t ，f ，矿) 是一个p e t r i 网，仃是一个有限变迁序列。盯的 p a r i k h 向量孑定义为孑：r 专肼，使得v t 丁，孑( f ) 等于变迁f 在仃中出现的次数。 对于p e t r i 网n 中的一个变迁f 而言，有【】( ，) = 【】；，这里f 是单个变迁，的 p a r i k h 向量。根据变迁的发生规则，m t ) m 7 ，m = m “】( ，f ) ，也就是说， m = m + 【p 。相应地，对于p e t r i 网( ，) 的任一有限的变迁序列仃，若 m o p ) m ，则有 m = “p ( 2 1 ) ( 2 1 ) 称为p e t r i 网的状态方程，它给出了p e t r i 网标识变化的一种紧凑代数 描述。状态方程表达了标识和发射序列中变迁出现次数的相互关系，使得基于线 形代数的p e t r i 网分析技术成为可能。 任何一个可达标识都满足状态方程，但满足状态方程的标识并不一定就是可 达的。在这种意义下，状态方程提供了m 从初始标识坛可达的必要条件，也就 是说，若m 是从坛可达的，必存在一个发射序列向量仃使得m = 眠+ 【p 成立， 第二章p e t r i 网的基本理论 9 若状态方程m = m o + n f f 是不可解的，则m 7 必然是从心不可达的。 【定义2 1 0 1 令n = ( 尸，t ，f ，形) 是一个纯网，n 的关联矩阵朋是一个以a 丁为 序列的整数矩阵，朋积砂= 吼一w ( p , o 。库所p 对应的行向量称为p 的关联向量， 记做 n i ( p ，) 。变迁t 对应的向量称为f 的关联矩阵向量，记做 】( ，t ) 例2 1 图2 1 所示的p e t r i 网是纯普通网，其关联矩阵【】如下： 图2 - 1 一个普通p e t r i 网( ，坂) 【】是一个1 2 行、9 列的整数矩阵，因为该p e t r i 网含有1 2 个库所和9 个变 迁，它的关联矩阵如下： 【】= l o l 0 oo o一1 11 11 lo 根据关联矩阵的定义，库所p 的关联向量【】( p ，) 有明确的物理含义，对于 o 0 o 0 o o o o o l 0 0 o 0 0 o o l 0 l o o o 1 o l 0 0 o l _ o o 0 0 1 1 o o 0 o ll o o 0 1 o o 一 0 0 o o i i o l o o 0 l o o 0 o o o o o o o o o o o 。 1 0 p e t r i 网可达图的并行算法 ，z ： 1 ) 【】( p ，f ) = 0 意味着f 的发射不会改变p 中的托肯数； 2 ) 【】( p ，t ) o 意味着f 的发射会向p 中移入【】( p ，r ) 个托肯； 因此，库所p 的关联向量【】( p ，) 实际上给出了每个变迁发射对p 中托肯数的 影响。令d 是一个库所子集艇d 【】( p ，) 表示每个变迁的发射对d 中托肯数的影 响。 如上图所示，d l = p 4 ，p 5 ，风 是一个库所子集。库所致，死，见关联向量的多集 形式分别是，【】( 仇，) = t 6 - t 4 ， 】( 见，) = t 4 - t 5 ，【】( 见，) = t 5 - t 6 。可以看 到睢d 。【】( p ，) = 0 t ，意味着任何变迁的发射不会影响d l 中的托肯数的变化，也 就是说，v m r ( n ，心) ，m ( d i ) = m o ( q ) 。 根据需要，【】可以进一步分为两部分 n = p o s t - p r e , p o s t 称为后置关联矩阵( 也 称输出矩阵或函数) ，p r e 称为前置关联矩阵( 也称输入矩阵或函数) ，其中 p r e 颤o = w ( p , o ，p o s t ( p , 砂= 眦。假定p e t r i 网有n 个库所和m 个变迁，觑 ( 尸，r ) = ( 矿( a ，) ，w ( p 2 ，f ) ，0 0 9 形( 见，f ) ) 1 ，【】( p ，r ) = ( 【】( p ，t o ，【】( p ，t i n ) ) p o s t = ： p r e = 容易验证，对后置关联矩阵p o s t 和前置关联矩阵p r e 进行运算可以得到上述 例子的关联矩阵。 【定义2 1 0 】令n = ( p ，t ，f ，w ) 是一个网，眠是的一个标识， 1 ) 一个变迁f 在标识m o 下是活的，当且仅当跏r ( n ，眠) ，3 m r ( n ，) 使 得m ，【r 成立； 2 ) ( ，心) 是死锁的，当且仅当不存在r t m o l t ) 成立； 3 ) ( ，心) 是无死锁( 弱活) 的，当且仅当v m r ( n ，m o ) ，3 t t ：m 【f ) 成立； 0 o o 0 o 0 0 0 o 1 0 0 0 0 o 0 o o 0 o l 0 1 0 l 0 o o 0 o 0 0 o 0 0 1 o o 0 0 0 1 o 0 0 0 o 0 0 o 0 0 1 0 l o 0 0 o o 0 o 0 1 o o 0 1 0 0 0 o 0 0 l 0 0 0 o 0 0 0 0 0 0 1 0 o 0 0 o l o o 0 0 o o 0 o o 0 l 0 1 o 0 0 1 0 0 0 o o o 0 o 0 1 0 o o o 0 0 o o o o l 0 1 0 o 0 0 0 0 o 0 1 o o 0 o 0 0 1 0 o l 0 o o 0 o 0 o o 0 0 1 o 1 o 0 o o o 0 o 0 l 0 0 0 0 0 0 o l 0 0 0 o o 0 1 o o o o o o 1 o 0 0 l o 0 0 0 o 0 l 0 0 o 0 0 0 o o 0 l 第二章p e t r i 网的基本理论 4 ) ( ，眠) 是活的，当且仅当v t t ：f 在标识坛是是活的； 【定义2 1 l l 令n = ( p ，t ，f ，形) 是一个网，坛是的一个标识， 1 ) ( ，眠) 是有界的，当且仅当3 k n 0 ，v m r ( n ，) ，跏p ：m ( p ) 后； 2 ) ( ，坛) 是结果有界的，当且仅当对于任意的有限的初始标识，它都是有界的； 值得说明的是；对于资源有限的实际系统而言，它的p e t r i 网模型一般都是结构有 界的。所有元素均为o ( 1 ) 的列向量记为o ( 1 ) 。 2 3p e t r i 网的可达图 可达图( r e a c h a b i l i t yg r a p h ) 是p e t r i 网分析的一种重要手段，对于各类网系统都适 用。p e t r i 网的可达图可以表示标识和变迁发射的关系。假如p e t r i 网是有界的，其可 达图则为有界图，且这个性质很容易得到验证。如果p e t r i 是无界的，其可达图就是 无限的，这时可构造称为覆盖i 蛩( c o v e r a b i l i t yg r a p h ) 的有限图来分析有关性质。从 能上来说，基于可达图和可覆盖图( c o v e r a b i l i t yg r a p h ) 的分析方法功能确实很强，但“ 是它们的计算非常复杂，从理论上，一个p e t r i 网可达图的规模和网结构及其初始标 识的大小成指数关系。关于有界p e t r i 网可通过下列算法来得到： 算法2 1 ：可达图生成算法 l n p u t ：p e t r i 网( ，眠) 。 o u t p u t ：可达图r g ( n ，坂) 。 ( 1 ) ：可达图的根顶点为眠，该顶点没有标号 ( 2 ) ：1 d 1 i e ( 存在没有标号的顶点) d o ( 3 ) ：考虑没有标号的顶点m ( 4 ) ： 对于m 下使能的每个变迁r ，令m = m “】( ，f ) ( 5 ) ：i f ( 可达图中不存在顶点肘7 ) t h e n ( 6 ) ：在图中添加顶点m ( 7 ) ：从m 到m 7 添加弧t ( 8 ) ： e n di f ( 9 ) ：给肘加标号“旧 ( 1 0 ) ：e n dw h 1 0 现在用一个例子来简单的说明该算法的执行过程，图2 2 为一个简单的p e t r i 网 n = ( 尸，t ，f ，形) ： 1 2 p e t r i 网可达图的并行算法 图2 - 2 一个p e t d 网( ，m o ) ，n = ( p ，t ，f ，形) ，m o = ( 4 ，0 ，0 ，3 ，o ) r 依据算法2 1 该网所有可达状态数的求解过程为：同样兀删标识有标号的标 识的集合，n ，删为没有标号的标识的集合，显然在开始状态下心= ( 4 ，0 ，0 ，3 ，o ) r 。 兀一= m ，鸠) ，兀删= ) 。 fj j 鸠 ( 2 ) ：m j b 心，n 一= 鸠，鸠，心，鸠) ，兀删= 眠，m ) 。 i 与鸠 i 山恤 ( 3 ) ：鸠 卫一心，其中眠是有标号的标识，坞在兀，删中存在，更新后得 ij o 眠 到新的状态是：n 懈卅，= 鸩，心，坞，心) ，1 - i o z d = m o ，m ，鸠) 。 h k 鸠 三麓，坞，眠不在兀，删和n 删中，都是好的标识，更新后得到的 新的状态是：n 一= 心，坞，心，坞，心) ，n 。埘= m o ，m ，鸠，必) 。 ( 5 ) ：心寸m o ，其中m o 是是有标号的标识，兀一= 坞，心，坞，眠) ， r l o , a = m o ，ml ，m 1 ，m 2 ，m o k 坞 三瓮，其中m 是有标号的标识，饩是在n ，删中存在，更新后得到： 兀一= 尥，坞，眠) ，1 - i o 膳= m o ，m ，鸠，鸩，鸩，坞) 。 m 鸩 n 专“专 ，j、 靠 m 第二章p e t r i 网的基本理论 1 3 i 山鸠 ( 7 ) ：地 专m o ，其中鸠是在n ，删中存在，鸠，m o 是好的，更新后： 【j 鸟鸠 n = 心，心，鸠，m o ) ，n 删= 眠，m ，鸠，心，心，鸠，坂) 。 ( 8 ) ；坞下没有使能的变迁，所以坞是死状态，即发生了死锁，更新后的状态： n 一= 眠，鸠，m o ) ，兀。埘= ，m ，鸠，鸩，心，坞，坞，坞) 。 ( 9 ) ：眠专鸩，显然心是有标号的标识，更新得到的新的状态是： 兀一= 鸠，m o ) ，n 删= ，m ，鸠，鸠，心，鸠，心，坞，心) 。 ( 1 0 ) ：鸠专坞，显然鸠是有标号的标识，更新后得到的状态是：n 一= m o ) ， f i o , a = m o ，m l ，m 7 ，m 2 ，m4 ，ms ，m ，m 3 ，m6 ，m 0 o ( 1 1 ) ：m o 专心，显然心是有标号的标识，更新后得到的状态是：n