（机械电子工程专业论文）petri网死锁迭代控制中若干问题研究.pdf

摘要 迭代控制算法是一种p e t r i 网死锁预防方法。本文对三种基于关键标识的极小 信标覆盖集的p e t r i 网迭代控制算法进行了分析。由于这三种算法同时考虑信标和 状态，因此通常可以得到最优的控制器。 析网的转化与网控制的转化之间的关系， 在对第三种算法改进的基础上，通过分 得出了一种可以用控制普通网的方法来 控制一般网的迭代控制算法。在这些算法的实现过程中涉及到基于划分和库所约 束的极小信标的求解问题、一般网向普通网的转化及返回转化问题、关键标识的 极小信标集合覆盖问题、关键标识的生成问题、死锁检测问题、冗余控制库所的 检测及删除问题，以及极小信标和关键标识的交替生成问题等。在这些问题的解 决过程中，大量使用到整数线性规划。 关键词：死锁预防迭代控制信标网的转化整数线性规划 a b s t r a c t t h i st h e s i sf o c u s e so nd e a d l o c kp r e v e n t i o ni np e t r in e t s t h r e ea l g o r i t h m so f s i p h o ni t e r a t i v ec o n t r o la r ef i r s ta n a l y s i z e da n de x a m i n e d t h et h r e ea l g o r i t h m s b a s e d o nc o v e r i n gs e to fu n c o n t o l l e dm i n i m a ls i p h o n s ，c o m b i n em a r k i n g sw i t hm i n i m a l s i p h o n s t h es t a t e so fap e t r in e ta r ec o n s i d e r a t e da sw e l l ，w h i c hm a k e sap e t r in e t ，b y m e a n si nt h ea l g o r i t h m s ，c a l lb eu s u s a l l yc o n t r o l l e do p t i m a l l y ，a f t e rt h et h r e ea l g o r i t h m s ， an e wo n ei sp r o p o s e d ，i nw h i c ham e t h o df o rc o n t r o lo fa no r d i n a r yp e t r in e ti su s e df o r ag e n e r a l i z e do n e ，v i at r a n s f o r m a t i o nf r o mag e n e r a l i z e dp e t r in e tt oa no r d i n a r yo n e a n db a c k t r a n s f o r m a t i o nf r o mac o n t r o l l e do n et oa l lo r d i n a r yn e t i nt h ea l g o r i t h m s a b o v e ，m a n yp r o m b l e m s a r ei n v o l v e d ，s u c ha sm i n i m a l s i p h o ne n u m e r a t i o n ， t r a n s f o r m a t i o nf r o mag e n e r a l i z e dp e t r in e tt oa no r d i n a r yo n ea n db a c k - t r a n s f o r m a t i o n f r o mac o n t r o l l e do n et oag e n e r a l i z e d ，c o v e r i n gs e to fu n c o n t r o l l e dm i n i m a ls i p h o n s ， g e n e r a t i o no fc r i t i c a lm a r k i n g s ，d e a d l o c kg e n e r a t i o np r o b l e m ，r e m o v i n gr e d u n d a n t c o n t r o lp l a c e s ，e t c a n dt os o l v et h ep r o b l e m s ，i n t e g e rl i n e a rp r o g r a m m i n gi su s e f u l k e y w o r d s ：d e a d l o c kp r e v e n t i o n i t e r a t i v ec o n t r o l s i p h o n t r a n s f o r m a t i o no fp e t r in e t i n t e g e rl i n e a rp r o g r a m m i n g 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 日朔二口，0 ，多矿 日期圭竺：之：f 矿 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 日期至堡f 翌：墨! j 7 日期二剑纽量么歹 第一章绪论 1 1 1p e t r i 网简介 第一章绪论 1 1 研究背景与意义 p e t r i 网【7 】这个概念源于德国学者c a r la p e t r i 于1 9 6 2 年所发表的博士论文“自 动机通信”。它是根据系统事件之间的因果关系，经过理论抽象而形成的一种网 图【9 】。是一种适用于多种系统的图形化、数学化的建模工具，为描述和研究具有 并行、异步、分布式和随机性等特征的信息加工系统提供了强有力的手段。通过 对该图用数学的、图论的方法进行分析和处理，就能搞清楚原系统的内在关系， 并实施对原系统的优化和控制。与传统的系统建模、分析和控制方法相比，p e t r i 网作为一种图形化和数学化的建模工具，能够提供一个集成的建模、分析和控制 环境，为系统的设计提供了便利。经过四十多年的发展，p e t r i 网理论已经成为具 有严密数学模型，多抽象层次、多用途的通用网论，并逐渐成为各相关学科的“通 用语言”，并且在离散事件系统( d e s d i s c r e t ee 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 网是系统事件因果关系的一种抽象网图，具体的说，它是一 种双枝有向副l 】【9 】。一个事件发生主要由三个部分组成条件、过程和结果。在 p e t r i 网里，把条件和结果用同一类图形表示，因为一个事件的结果往往是另一个 事件的条件，从这个角度讲它们并没有本质的差别。而把过程用另一类图形表示， 过程有可能是一刹那的，也可能是慢长的，但对于这个过程中的东西是不需要被 关注的。通行的表示方法是用圆圈表示条件和结果，并称之为库所( p l a c e ) ：用矩形 ( 或杠) 表示过程，并称之为变迁( t r a n s i t i o n ) 。库所内可有黑点( t o k e n ) 或数字，表示 条件或结果的持有数。库所和变迁统称为结点，它们之间的直接因果关系用有向 2 p 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 l 夕2 图1 1 化学过程中的p e t r i 网建模 其中，p l 、p 2 和优分别表示h 2 、0 2 和h 2 0 ；t t 和t 2 分别表示燃烧和电解。 1 1 2 死锁及其控制方法 死锁问题的研究起源于操作系统中的资源分配问题【l 6 1 。死锁就是系统在某 种状态下，系统继续向下演化的条件不具备，从而使系统处于一种停滞状态。一 般认为，死锁产生的主要原斟l 】是：( a ) 系统资源不足；( b ) 进程允许推进的顺序不 当；( c ) 资源分配不当。c o f f m a n 等给出了系统死锁的四个必要( 但非充分) 条件【1 】【1 0 】： 1 相互抑制( 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 t ) ：若干进程形成了一个进程链，该进程链中的每一 个成员等待着它的下一个进程持有的资源。 死锁在很多情况下是不希望发生的，它有时会带来非常严重的后果，如在自 动炼钢生产系统中，一旦出现死锁将可能使钢水凝固，从而使得某些设备报废， 造成重大生产事故。正因如此，死锁的研究和控制就显得十分重要。处理死锁的 方法一般分为四种i l j 。第一是忽略死锁，即所谓的鸵鸟算法( o s t r i c ha l 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 网则是第四种方法 死锁预防的重要分析工具【1 7 】【1 8 】。基于p e t r i 网的死锁预防是一种静态方法，它 使用离线方式控制某些变迁的发射，从而保证系统不会发生死锁。只要控制住了 一个p e t r i 网的死锁，相应系统的死锁也就得到了控制。 在p e t r i 网的死锁控制中，从基于理论的不同，主要有三种控制方法：基于状态 的1 9 2 5 1 、基于信标的 2 6 。3 1 1 以及基于联合信标和状态的 2 1 1 4 1 控制方法。基于状态的方 法主要是找出那些危险的状态，因为从这些状态出发，一个网可能会演化成死锁， 也可能不会，那么对那些可能会引起死锁的变迁的发射进行限制，就可以阻断其 向死锁演化。区域理论【了7 3 9 】是这种方法的一个典型运用。但基于状态的方法往往 需要列举一个网所有的状态，而状态又与网的规模成指数关系，对于规模较大的 网，还是有相当困难的。信标理论在p e t r i 网死锁控制中的作用至关重要。信标一旦 清空，将永远不可能再获得资源，使某些或全部变迁不能发射，从而系统将可能 死锁。研究发现，系统的死锁总是和信标有着必然的联系。因此就产生了基于信 标的死锁预防策略，目前的控制方法大多都与信标有关。然而信标的数量也是和 网的规模成指数关系，若对每一个信标都加一个控制器也是不现实的。基本信标 理论对这个问题的解决有着重大贡献【lj 。它通过分析信标间的关系，提出基本信标 和从属信标的概念，通过对基本信标的控制从而达到对所有信标的控制。将信标 和状态结合起来【2 】【4 】，可以更为精准的控制网的死锁，往往可以得到最优的控制器， 但它的算法是相当复杂的。 从控制的步数来讲，p e t r i 网的死锁控制又分为非迭代的控制方法和迭代的控制 方法【3 2 3 6 l 。前者是对一个网一次性控制，后者是在对一个网添加控制器的基础上 多次进行控制，直到所有的死锁都被控制住为止。 对于普通网和一些特定的子类，可以说已经有比较好的控制方法，但对于一 般网的控制，还没有太好的办法【l j 。 意大利学者p i r o d d i 等人2 0 0 8 年在其所发表的论文【4 】中将信标、状态和迭代控制 结合起来，提出“选择信标”的控制策略。在该理论中提出了主导信标( e s s e n t i a l s i p h o n ) 、受导信标( d o m i n a t e ds i p h o n ) 、关键标识( c r i t i c a lm a r k i n g ) 、支配标识 ( d o m i n a t i n gm a r k i n g ) 以及受支配标识( d o m i n a t e dm a r k i n g ) 的概念。利用集合覆盖的 方法，在每步迭代中选出一些信标来控制，从而使所有信标受控，并使控制库所 最少。尽管没有能够形式化地证明这种方法所得到的一定是最优的控制器，但也 4 p e t r i 网死锁迭代控制中若干问题研究 还没有人证明它一定会限制某些好的状态，至少形式上它是可以得到最优控制器 的。值得一提的是，文【4 首次给出了一个典型柔性制造系统【2 6 】的优化活性p e t r i 网 控制器。 文【4 】中方法的最大缺点是计算复杂性问题。在迭代的每一步，需要计算所有 的极小信标，所有的支配标识以及求解集合覆盖问题。以上每种计算都是指数复 杂性的【1 1 。 针对于以上问题，2 0 0 9 年p i r o d d i 等人又在其选择信标控制算法的基础上提出 了两种联合信标和标识生成的迭代控制算法【2 j 。在这两种算法中，利用信标和死标 识之间的关系，通过求解整数线性规划，避免了列举所有的极小信标和死标识， 从而大大地缩短了算法求解的时间。并且，用这种算法，为那个2 6 个库所的典型 p e t r i 网实例找到了最优的活性控制器。其中第一种算法的基本步骤是：首先找到一 个极小信标，通过求解整数线性规划，依次找出这个信标被清空的死标识，再依 次找出这些死标识下所有清空的信标，再通过求解整数线性规划，依次找出这个 信标被清空的死标识，直到找不到死标识为止，然后再找出一个新的极小信标， 重复上述步骤，直到找不到新的极小信标，然后求出所有已找到的极小信标的覆 盖集，用基于尸不变式的广义互斥约束控制覆盖集中的极小信标，剔除冗余控制 库所，转入下一次迭代，直到找不到清空的极小信标为止。这个算法复杂度相当 高，其中求一个新的极小信标、求一个标识下所有清空的极小信标、求解线性规 划，剔除冗余控制库所，求极小信标的覆盖集等都不是一项简单的工作。 应该说p i r o d d i 等人的联合信标和标识生成的迭代控制算法的结果是让人兴奋 的。其大大地缩短了计算时间，对于2 6 个库所那个典型例子，只用了三、四秒的 时间就使其得到了控制，并且只添加了1 3 个控制所就达到了最优控制。对一个4 8 库所3 8 变迁且超过2 5 0 0 万个状态的网，其也只用了不至o 1 0 0 秒就将其控制住了。 然而，由于其算法相当复杂，至今尚未有他人对其算法进行仿真验证。为了 更好的在p i r o d d i 等人的研究成果的基础上做更为深入的研究，对其算法进行分析 并编程仿真验证就显得极为紧迫。 对于普通网和一些特定的子类，可以说已经有比较好的控制方法，但对于一 般网的控制，还没有太好的办法。文 2 在对2 6 个库所的例子的控制过程中，在第 二步迭代后，已变成了一个一般网，但最后仍得出了正确的结果。如果对此进行 深入分析，或许可以得出一个控制一般网的算法。 正是在这个背景下，本文对p i r o d d i 等人2 0 0 9 年在文【2 】提出的第一种联合信标 和标识生成的迭代控制算法进行了分析和研究，并进行了编程仿真验证，希望找 到更好的控制算法。 第章绪论 1 2 本文完成的主要工作 本文主要完成了以下几项工作： 1 分析了p i r o d d i 等人2 0 0 9 年论文【2 1 中所提到的3 种迭代控制算法( 包含其2 0 0 8 年所提出的两种 4 1 ) 和该算法所涉及到的c o r d o n e 等人所提出的求解极小信标的算 法 3 1 ，以及l a u t e n b a c h 和i o r d a e h e 等人提出的把一般网转化为p t - 普通网的算法【5 】【6 】。 2 编程验证了p i r o d d i 等人2 0 0 9 年论文1 2 】中的第三种迭代控制算法( s c i s c 3 ， 包括极小信标的求解、网的转化、解整数线性规划、g m e c 、求极小信标的覆盖集、 剔除冗余控制库所等) 。通过实例验证了上述算法是基本正确的，同时也发现如 下问题： ( 1 ) 文【2 】和【4 】对迭代控制算法和网的转化及返回转化的结合阐述得不够清 楚。s c i s c 3 只能用于那些在迭代控制中始终保持是p t 普通网的网，因为该算法 的步骤中没有用到网转化，一旦网在控制中变成了一般网，它将无能为力。 ( 2 ) 文 3 】声称求解极小信标的g p m s e 方法和l p m s e 方法在速度上差不多， 但根据程序运行结果看，前者比后者慢很多。 ( 3 ) s c i s c 3 算法仍然是一个指数复杂度的算法，对于较大规模的p e t r i 网， 求解仍有相当难度，其时间仍主要消耗在求极小信标上。 ( 4 ) 文【2 】称s c i s c 3 不用列举所有极小信标，但在实施中是有困难的。 3 对求解极小信标的算法进行了改进。通过增加判断条件，排除了一些得不 到极小信标的情况。另外根据信标间的包含关系，使得每次求出的信标都是一个 极小信标。这使得求解一个网所有极小信标的时间在平均意义上有所减小，尤其 是对于极小信标密度( 极小信标的数量和网的规模之比) 比较小的网有相当优势。 例如，对于个别实例，其求解时间仅为原算法的千分之一。不仅如此，更为重要 的是这为s c i s c 3 的实现提供了便利。在s c i s c 3 中需要每次求出一个新的极小信 标，用文献 3 d 尸l p m s e 方法在不求出所有极小信标的情况下，不可能确保找到的 信标是一个极小信标。如果先找到所有极小信标，再从中取出一个，这显然有悖 于s c i s c 3 不用列举所有极小信标的要旨。用文献 3 】中g p m s e 方法是可以每次求 出一个极小信标，但通过验证，其速度相当慢，不实用。 4 对网的转化以及返回转化进行了比较深入的探讨，得出了原始变迁使能不 变、极小信标不变和状态包含等结论，并对网转化过程中，控制转化的原因进行 了初步探讨，使得用控制普通网的方法来控制一般网的算法得以实现。 5 提出了一种新的迭代控制算法基于网转化和集合覆盖的信标迭代控制 算法t s c i s c 。该算法不但继承了s c i s c 3 的优点，而且对s c i s c 3 不合理的地方 进行了改进，最为重要的是它利用了网的转化，用控制普通网的方法实现了对一 6 p e t d 网死锁迭代控制中若干问题研究 般网的控制。 通过上述工作，对迭代控制算法有了更为深入的理解，并为进一步的研究打 下了一点基础。 由于时间和作者水平有限，文中定有不足和错误之处，恳请批评指正。 第二章p e t r i 网基本理论 7 第二章p e t r i 网基本理论 自p e t r i 网的提出至今已有四十多年的历史，其基本理论已十分成熟。本章只 涉及本文后续章节所要用到的概念、定义和定理等。本章内容主要来自文献【1 】。 2 1 基本定义 【定义2 1 】p e t r i 网是一个四元组= ( 尸，ze 聊，其中尸代表库所的集合，丁 代表变迁的集合，并且p 和丁是有限、非空且不相交的集合；匙妒t ) u ( t x p ) 为 有向弧的集合；阢n 肌 0 ) 称为f 中弧上的权，n = o ，1 ，2 ，) 。当斥，则 w o o o ；否则，职乃= o 。 称= ( 尸，l 只聊为普通( o r d i n a r yn e t ) ，当雎f ，= 1 。 称= 俨，e 叨为p t - 普通网( p t - o r d i n a r yn e t ) ，当即p ，v f r ，若 ，o e f ， 有w ( p ，0 = 1 。 当只考虑网结构而忽略其弧上的权值时，一个p e t r i 网可记为= ( 尸正d 。 从基于信标的控制理论上讲，p t - 普通网和普通网是相同的，本文对这两个概 念不作区分。 从图论上讲，p e t r i 网是一种双枝有向图( 如图1 1 ) ，库所( 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 砌表示。库所和变迁之间用有向弧连接，同一类型的节点之间不能用有向弧 连接。 【定义2 2 】p e t r i 网= ( 尸，l 只叨的标识m 是一个从尸到肼的映射。( ，m o ) 称为 网系统或标识网，称为的初始标识。在不引起混淆的情况下，可以简单地称( ， m o ) 为p e t r i 网。( ，m o ) 有时写成( 尸，正e 形m o ) 。 库所中的标识用称之为托肯( t o k e n ) 的小黑点表示。当托肯的数量比较大时，可 直接用数字表示，如图1 1 中m o = ( 5 ，3 ，0 ) 1 。 【定义2 3 】令 7 一俨，l 只叨是一个p e t r i 网，节点x p u 确前置集定义 为 x = y e p u t i ，功毋，其后置集定义为，= 钞p u r i ，力毋。节点的集合 h e p u t 的前置集( 后置集) 定义为h - - - u x 办( 盯= u e l 4 x 。) 。 【定义2 4 】称忡，乃e 即是纯的或无自环的，若不存在o ，力( p x t ) u ( t x p ) 使得 ，力聊，功f 同时成立。 【定义2 5 】若网忡，正e 即是纯的，其关联矩阵啪定义为以p 和功序标的 8 p e t r i 网死锁迭代控制中若干问题研究 整数矩阵，m d = 职tp ) r ) 。库所p 对应的行向量称为p 的关联向量，记为 m 慨) 。变迁，对应的列向量称为r 的关联向量，记为【 ( ，f ) 。 【定义2 6 】网- 俨，ze 聊的输入关联矩阵阴定义为以尸和丁为序标的整 数矩阵，四 ，) = d 。 【定义2 7 】网- 妒，兀e 叨的输入关联矩阵 d 定义为以尸和丁为序标的整 数矩阵， d 】d = 职，力。 从以上三个定义，对于纯网，显然有m = 刎一明。 【例2 1 】图1 1 所示的网，其【加、 刎和明为： r - 2 i n ：i _ 1 i 2 l 【定义2 8 】令- ( 尸，正e 叻是一个网， 1 ) 一个变迁，丁在m 下是使能的，记为m ，) ，当且仅当跏。f ：坳) ，) ； 2 ) 若m ，) 成立，则，发射后，产生另一新标识m ，记为m d m ，有 m ( p ) = m ( p ) 一( 口t ) m ( p ) + 形( t p ) m ( p ) 一形( 刃f ) + w ( tp ) m ( p ) p 。t i t p t 。， p 。，n 广 其它 3 ) 网从标识m o 开始的所有可达标识的集合记为r ( ，m o ) 或尺妒，兀e 形m o ) 。 它是一个最小集，即m o o r ( n , m o ) ，m e r ( n m o ) a m t ) m = m e r ( n , ) ； 4 ) 若存在标识，尬，尥和发射序列0 = t l ，t 2 ，岛满足m o 【t 1 ) ) m ， 则称m 是从m o 可达的； 5 ) 若存在标识m 使得【m 则+ m l 其中m 为关联矩阵，】，为发射 序列矢量，其第f 个数值代表第f 个变迁在序列仃中出现的次数。 方程+ 【加y 称为p e t r i 网的状态方程。它给出了p e t r i 网标识变化的一种紧凑 代数描述。状态方程表达了标识和发射序列中变迁出现次数的相互关系，使得基于 线性代数的p e t r i 网分析技术成为可能。 【定义2 9 】令- 俨，ze 聊是一个网，是的初始标识， 1 ) 一个变迁，是活的，当且仅当v m r ( n m o ) ，s m e r ( n 蚴使得m 【d 成立； 2 ) ( m o ) 是死锁的，当且仅当3 m e r ( n m o ) 使得：不存在，乃a c t ) 成立； 3 ) ( m o ) 是无死锁( 弱活) 的，当且仅当v m e r ( n m o ) ，3 t e 乃m ，) 成立： 4 ) ( ，m o ) 是活的，当且仅当v t e t ，是活的； 【定义2 1 0 令- 俨，l 只聊是一个网，是的初始标识， 1 ) ( ，m o ) 是有界的，当且仅当3 k e n 0 ) ，v m e r ( n m o ) ，v p e p ：般p ) 鱼； 1j o o 2 2 l o 。l = 1 i l jh r 1_ 2 1 o 0 o 2 l = p 第二章p e t r i 网基本理论 9 2 ) ( g o ) 是结构有界的，当且仅当对于任意有限的初始标识，它都是有界的。 对于资源有限的实际系统而言，它的p e t r i 网模型一般都是结构有界的。 2 2 结构不变式 【定义2 1 1 】令_ 妒，瓦e 叨是一个网， 1 ) 以尸为序标的列向量1 ，：尸专z 称为的p 向量，其中z 是整数的集合。 2 ) 以丁为序标的列向量w ：n z 称为的正向量。 【定义2 1 2 1 令，和j 分别为网- 妒，le 叻的尸一向量和弘向量， 称e - ：司l ，是一个尸不变式，当且仅当# 0 且，【加= o t 。俐= 仞p i 坳) o ) 称为， 的支撑。 称弘向量，是一个d 不变式，当且仅当j # 0 且嗍j = 0 。l m | _ ，啾d 0 ) 称为 j 的支撑。 【性质2 i i 网系统( ，g o ) ，是= ( 尸，瓦e 叻的一个n 不变式，v m e r ( n , ) ： p m = p m o o 2 3 信标与陷阱 【定义2 1 3 ( mm o ) 是一个网系统，- ( 尸，瓦e 叨， 1 ) 称一个非空集合s _ c p 是一个信标( s i p h o n ) ，当且仅当。s _ c s 成立； 2 ) 称一个非空集合s _ c p 是一个陷阱( t r a p ) ，当且仅当。s 终成立； 3 ) 称一个信标( 陷阱) 是极小的，当且仅当不存在其它信标( 陷阱) 是它的真子集； 4 ) 信标s 所对应的p 向量称为s 的特征p 向量； 5 ) 称p 尸是被标识m 标记的，当且仅当坳) o 。称一个集合s _ c _ e 是被标识m 标记的，当且仅当s 中至少有一个元素被m 标记。s 中的托肯数m $ = 岛s 坳) ； 6 ) 不包含任何p 不变式支撑的信标称为严格信标，一个严格信标有可能被清空； 一个既极小又严格的信标，称为严格极小信标( s m s ) 。 【性质2 2 】网系统( mg o ) ， 俨，乃只叻，s _ c _ p 是一个信标，若3 m r ( n , ) ： m 固= o ，则s 以后永远不会被标记，称为被清空。 【性质2 3 】网系统( m o ) ，肛( 尸，乃e 叨，s _ c _ p 是一个陷阱，若3 m e r ( n , m o ) ， m 固 0 ，则s 以后总是被标记。 【性质2 4 1 网_ ( 尸，ee 聊的尸- 不变式，的支撑8 川既是信标又是陷阱。 【性质2 5 1 ( mm o ) 是一个网系统，其中_ ( 尸，le 叻，i 是一个只不变式， s 堂是的一个信标，那么此信标s 是在下被尸不变式，控制的，当且仅当 ，： o 且对于所有的p 尸遇坳) o 且p p l l ( p ) 0 s 。 1 0 p e t f i 网死锁迭代控制中若干问题研究 如果s 是一个在下被尸不变式，控制的信标，则s 不可能被清空，也就是说， v m e r ( n , m o ) ，s 在标识m 下是被标记的。 【性质2 6 】( mm o ) 是一个普通网系统，胪妒，ld ，若在m 下是死锁的， 则所有未被标记的库所形成一个信标。 【性质2 7 1 ( mm o ) 是一个普通网系统，_ 妒，正刃，如果网中没有信标可 能被清空，网( mm o ) 是无死锁的( d e a d l o c k - f r e e ) 。 显然，一个死锁的普通p e t r i 网至少包含一个空信标。 【性质2 8 】( ，m o ) 是一个p t - 普通网系统，( p ，正d ，如果所有极小信标在 所有可达状态下都不被清空，则网( ，m o ) 是无死锁的( d e a d l o c k f r e e ) 。 【定义2 1 4 1 令s 是网系统( ，) 的一个信标。称s 在标识m 下是最大标记 的当且仅当劲s 使得m ( p ) m a x p ，这里m a x p 。= m a x 矽 t ) l t p ) 。 【性质2 9 】若网系统( ，) 的所有极小信标在网的所有可达状态下都是最大 标记的，nn ( n , m o ) 是无死锁的( d e a d l o c k - f r e e ) 。 2 4 广义互斥约束 广义互斥约束( g m e c g e n e r a l i z e dm u t u a le x c l u s i o nc o n s t r a i n t s ) 是离散事件系 统监督控制理论中的一种重要控制需求，很多其它形式的控制要求也可以转化为 g m e c 问题。 【定义2 1 s 令( ，m o ) 是一个p e t r i 网，其库所集合为尸。( ，) 的一个广义 互斥约束( ，6 ) 定义为标识的集合拟，b ) = m ei l c el r m b ，胜r ( ，) ) ，其中 z 是非负的p 向量，b n 称为约束常数。 。 令( ，6 ) 是施加于p e t r i 网a 讥m o ) 的一个g m e c ，其中n = 俨，t ，f ，叨，且初 始标识满足，7 1 m o ， 则s l 、和岛为s 一个全划分。 集合往往是事件( 问题) 的处理对象和结果，根据事件的对象和条件的不同， 可以把一个事件( 问题) 划分为若干子事件( 子问题) ，再把这些子事件( 子问题) 的结果合并起来，便得到原事件的结果。 【例3 2 】令事件e 为查找1 0 0 以内的质数，就可以把查找的对象分为三段： o 到5 0 ，5 0 到8 0 和8 0 到1 0 0 ，从而把划分为e l 、易和历，其中e l 为查找0 到5 0 内的质数，易为查找5 0 到8 0 内的质数，历为查找8 0 到1 0 0 内的质数。 【定义3 2 】令s 为一个全集，彳签，逛s ，若aub 爷，彳n 庐夙则称b 为彳 在s 下的补集，记为a = b 。 【定理3 1 】令s 为一个全集，4 $ ，召$ ，则有彳ub = anb ，anb = aub 。 1 4 p e t r i 网死锁迭代控制中若干问题研究 【例3 3 】令( mm o ) 是一个p e t r i 网，试设计一种求解其全部极小信标的算法。 思路：先找出一个极小信标，再根据s + 对问题进行划分【3 1 。 首先，分析一下网( m o ) 全部极小信标和s 的关系。 令为网( ) 全部极小信标的集合，为不包含s 的所有极小信标的集合， 则有z = z u 毋 。令p l ，p 2 ，p m 为s + 的全部元素，a f 为包含p ，的所有极小 信标的集合，i = l ，2 ，m ，则 s + ) = a l n a 2 + n n a 恻， = s + = a ? n 彳：r 、a ；n 厂、彳： = a ? ua ；n 彳；r 、n 么： = 彳f - u - ? u 么j n4 ：n 彳；n 厂、彳： ：万u 陌n 石可百丽) u0 m 石砑i 丽) ) = 彳? u0 7n4 ：n 彳；n r 、彳：j u0 7n 彳：n 彳；n r 、彳：j = 彳? u0 7n4 ：n 彳；n r 、彳：j = 彳? u0 7n 乜；ur 、彳；n n 彳：” ：彳u0 7n 医ub ；n 天j l i _ 7 i 虿) ) ) ：a - t u _ 1 ，a ；n 虿) ub m4 ：n 鬲万j 巧) ) = 彳? ui 彳? na ：j u0 7n 彳；nr 、么；r 、r 、么：j = 彳i iu0 7n 彳：j u u0 ：- n 彳；n n 彳：j 令研= a 0b ：= a ：r la ：，或= a ：na ：n na m ， 则。= b ? ub ：u ub l ：| ， 又。b ? nb ：= 夙u = i ，2 ，m ，f 勘 所以b - b ：b ：为+ 的一个全划分， 再令：为包含p l ，见，矽扣l ，但不包含a 的极小信标的集合， 则有b ? ，i = 1 ，2 ，m ， 所以= ：u ：u u ：l ， ：，：也是的一个全划分。 有了上面的分析，就可以看出，只要已知一个极小信标，就可以把求这 个问题分解成若干子问题，令这些子问题为n ：，f 1 ，2 。再对每一个子问题n ： 求出一个极小信标( 如果存在) ，再根据这个极小信标，把该子问题划分，直到所 有子问题都得到解决。这是一个递归过程，如果用计算机编程，可以让计算机自 己记住这些问题的序列，也可以人为设定一个序列来存贮这些问题。 令兀为问题求解网( ，) 的全部极小信标，令人为一个序列，如果人为 空，记为人= ( ) 。下边给出求解网( ，) 的全部极小信标的算法【3 1 。 步骤1 )= 刃，人= ( 兀) ； 步骤2 )i f ( 人( ) ) ，兀= p o p ( 人) ；e l s e 结束； 第三章基于全划分和库所约束的极小信标求解法 1 5 步骤3 ) 求解n ，得到一个极小信； 步骤4 ) 给增加一个元素，； 步骤5 ) 根据s 把r i 。分解成子问题n ：，i = 1 ，2 ； 步骤6 ) 把n ：，卢1 ，2 压入人，转到步骤2 。 这里p o p ( a ) 是指从人中取出一个元素。 3 2 基本定义和理论 本节主要讨论与求解极小信标直接相关的定义、性质和理论。一个p e t r i 网的 信标只与其库所、变迁和输入输出弧有关，而与其初始标识和弧的权值无关，故 本章的p e t r i 网都指的是_ ( 尸，矿) 。根据信标的定义，可以得出很多关于信标的 性质，本节也进行了讨论。 3 2 1 信标求解中的基本理论【3 】 在求解信标过程中，有时并不是在全部库所集中去寻找，而只是在特定的某 些库所集内去求解，这就需要把无关的库所、变迁和弧除去，从而把原网简化成 一个更小的网，以便降低求解复杂度。 【定义3 3 】令g _ ( p ，zf ) 是一个p e t r i 网，尸e p ，则g = r e d ( g ，p ) = ( p ，t ，f ) ， 其中： 1 ) r = f t l ( t u 广) n p 回； 2 ) f 力= 地d ，f ( 纠坝纠跏p ，v t et 。 【性质3 1 】令g - ( p ，乃f ) 是一个p e t r i 网，尸c p ，g - - - r e d ( g ，p ) = ( p ，t ，) ， 为g 的全部信标，主为吞的全部信标，1 = s i s c _ 尸，s ) ，则= 主。 证明：从定义3 3 可知，在从网g = ( p ，冗f ) 简化为g - - r e d ( g , p ) = ( p ，t ，f ) 的过程中，p 中任何一个p 的前置集和后置集都没有发生变化，因此如果v p t p 在g 中是一个信标，尸十在g 中仍然是一个信标，反之亦然。而尸是g 全部库所的 集合，所以有= z 。 【性质3 2 】令g = ( p ，正，) 是一个p e t r i 网，丁且。f = 历p l = t 。，尸2 p ， 则对于v p p i ，若p 尸2 ，如将不是一个信标。 证明：用反证法。假设上述性质不成立，即满足上述性质条件，但b 是一个 信标，则 尸2 _ c - p z 。 又。，乜 f 。 1 6 p e t r i 网死锁迭代控制中若干问题研究 那么jp p 2 ，使得p = 。f 这与。，= 彦矛盾 因些，假设不成立，原性质成立。 【性质3 3 】令g = ( p ，l f ) 是一个p e t r i 网，丁= f j r l r = 四，p = t 。，p = p p ， g - - - r e d ( g , ) ，为g 全部信标的集合，至为吞全部信标的集合，则z = 2 。 证明：根据性质3 1 和3 2 ，vp p 都不会是一个信标的元素，从而可以把p 从 尸中移走，而不会丢失g 中的任何一个信标。 【性质3 4 】令g = ( 尸，矿) 是一个p e t r i 网，p i n c p ，p i n 刃，若3 p p - p i n 和 ，。p i n p i n 。，满足。f = p ) ，那么v s s 3 _ p i 。l s 童r ，p s 。 证明：r 。p i n p i n 。 对于vs s d _ p i nl s o _ 9 ) ，ja s 使得，仇。，即p x e 。， 又。，= p ) 仇2 p p s 【性质3 5 】令g = ( 尸，驴) 是一个p e t