（机械电子工程专业论文）基于petri网的自动制造系统的死锁分析.pdf

基于p e t r i 网的自动制造系统的死锁分析 摘要 论文针对自动制造系统的一般特点，提出了一种基于p e t r i 网的死锁避免算法。该算 法在不穷举网系统的全部可达标识的前提下，首先计算出网系统的一些特殊标识，即所 谓的死锁标识、坏标识和危险标识。由于在坏标识下，系统将必然发生死锁：而在危险 标识下，系统只是有可能死锁。所以论文中提出的死锁避免算法通过控制危险标识下使 能变迁的发射，来保证整个系统是无死锁的。新算法只是计算出网系统的部分可达标识 图，它在保证系统是无死锁的前提下最大限度的降低了对系统的约束并且适用于一般网 的情况，因而它比现有的方法具有更大的实用性。 正如论文中所提到的，如何判定标识的可达性是新的死锁避免算法中所要解决的关 键问题。因此论文提出了用矩阵方法求解p e t r i 网的库所不变式、变迁不变式和状态方程 的新方法：并将g r o b n e r 基理论引入p e t r i 网的分析领域：而且还对非循环网的可达性问题 作了深入的分析。垛合这些方法，文章最后总结了一套系统的方法用以解决p e t r i 网的标 识可达性问题。在整个的研究过程中，论文总结和归纳了许多有用的概念和结论，而且 这些概念和结论对于其它的p e t r i 网分析也是普遍适用的。 关键词：p e t r i 网；自动制造系统i 死锁避免；可达性问题；g r 曲n e r 基；非循环网。 苎垦! ! ! 塑塑皂塑型堕墨簦箜垄塑坌堑 a b s 仃a c t d e v e l o p e d i nt h i st h e s i si san e wd e a d l o c ka v o i d a n c e s t r a t e g y f o ra u t o m a t e d m a n u f a c t u r i n gs y s t e m s ，w h i c ha r eb a s e do np e t r in e t s w i t h o u tt h ec o m p u t a t i o nf o rt h e w h o l e r e a c h a b i l i t yg r a p h ，t h ed e a d l o c ka v o i d a n c ea p p r o a c hi sf i r s tt oc o m p u t es o m es p e c i a l m a r k i n g s ，s u c ha sd e a d l o c km a r k i n g s ，b a dm a r k i n g s ，a n dd a n g e r o u sm a r k i n g sw ec a l l i na b a dm a r k i n g ，t h es y s t e mw i l l i n e v i t a b l yr e a c hd e a d l o c k w h i l e ，i nad a n g e r o u ss t a t e ，t h e s y s t e mw i l lp o s s i b l yb ed e a d l o c k e di ft h ef i d n g so f e n a b l e dm u l t i t r a n s i t i o n sa r en o t p r o p e r l y c o n t r o l l e d t h ed e a d l o c ka v o i d a n c eh e r ei si nf a c tt om a k et h es y s t e mn e v e rr e a c hab a ds t a t e t h ed e a d l o c ka v o i d a n c ep o l i c yp r e s e n t e di nt h i st h e s i su s e sp a r t i a lr e a c h a b i l i t yg r a p ho ft h e p e t r in e ta n dt h em a j o ra d v a n t a g eo ft h e s et e c h n i q u e si st h a tt h e ya r es u i t a b l ef o ram u c h l a r g e rc l a s so fo r d i n a r yp e t r in e t st h a n t h a to ft h em o s t e x i s t i n gd e a d l o c ka v o i d a n c ep o l i c i e s a n dt h es u p e r v i s o r yc o n t r o li sm a x i m a l l y p e r m i s s i v e a sr e f e r r e dt ot h et h e s i s ，t h e r e a c h a b i l i t yd e c i s i o ni s t h em a j o rp r o b l e mt h a tt h en e w d e a d l o c ka v o i d a n c ea p p r o a c hm u s ts o l v e s ot h em a t r i xm e t h o d sa l eu s e dt od e a lw i t ht h e c o m p u t a t i o n o f t h e p l a c ei n v a r i a n t s ，t r a n s i t i o ni n v a r i a n t sa n d t h es t a t ee q u a t i o nf o rp e t r in e t s f o rt h es a m ea i m ，w ea p p l yt h eg r t b n e rb a s ea l g o r i t h ma n dt h ea c y c l i cn e tt h e o r yt o d e t e r m i n et h em a r k i n g sr e a c h a b i l i t yi ns o m ee x t e n t c e r t a i n l y ，t h ec o n c l u s i o n sa r r i v e da t f i n a l l yi nt h i st h e s i sa l s oc a n b ea d a p t e dt ot h ea n a l y s i so fo t h e rk i n d so fp e t r in e t s k e y w o r d s ：p e t r in e t s ；a u t o m a t e dm a n u f a c t u r i n g s y s t e m s ；d e a d l o c ka v o i d a n c e ； r e a e h a b i l i t yp r o b l e m ；g r f i b n e rb a s ea l g o r i t h m ；a c y c l i en e t s 第l 章绪论 第l 章绪论 1 1 研究背景与意义 1 9 6 2 年，c a p e t r i 提出了p e t r i 网( p n - p e t r in e t s ) 理论。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 ) 建模、分析、性能评价和控 制设计中得到了广泛的应用。作为一种控制系统的设计手段，从2 0 世纪7 0 年代 开始，p e t r i 网以其能够模拟系统的并发和冲突行为以及反映出系统的动态特性而 受到了广泛的关注。自动制造系统作为一种典型的离散事件系统一直是p e t r i 网的 重要应用领域。而实际的自动制造系统必须是活的，不能存在死锁的操作。一旦 系统中由于资源调配不合理，或者某些操作占有系统资源而不释放( 耗尽资源) 而出现死锁，并且没有人为干预，系统就会一直处于锁定状态，无法继续运行， 从而严重的影响系统的生产率和控制实现。因此对系统中死锁状态的检测与控制 是自动制造系统设计和仿真的一个重要问题。 基于p e t r i 网人们研究了很多方法来处理自动制造系统中的死锁问题。 大致可归为以下几类： 1 死锁预防方法 2 死锁避免方法 3 死锁校正方法 4 综合法 首先是死锁预防方法，如【1 、 2 】、【4 。这种方法的目标是设计一个系统，该 系统所对应的p e t r i 网模型本身就是无死锁的或者是活的。这种方法从逻辑关系上 就保证了系统中是不会出现死锁的，因而也就没有必要再去控制系统运行过程中 对资源的申请。其思路是通过限制进入系统工件的数量( 对于网系统而言，就是控 制网系统的初始标志) ，使系统的p e t r i 网模型是活的，从而在原则上保证系统不会 陷入死锁。这种方法从确保系统不存在任何死锁的角度出发，相应地静态调配资 源( 设置初始标识) 。尽管系统存在死锁，但只要在系统动态运行时绕过这些死锁， 就不会出现死锁。因此没有必要为了预防可能出现但能回避的死锁而不配置某些 资源，从而提高资源的利用率。应该指出，这种方法尽管保证了系统的全局活性，但 具有较大的保守性，从而降低了系统的生产率和资源的利用率。 近些年来出现的死锁预防方法，大都采用在已有的p e t r i 网模型中增加新的库 所的方法。这类方法通过增加控制库所限制网系统的行为，从而保证网系统是无 死锁的。【1 】中提出的死锁预防方法可以应用于一种称之为s 3 p r ( s y s t e mo fs i m p l e 基于p c t r i 网的自动制造系统的死锁分析 s e q u e n t i a l p r o c e s s e sw i t hr e s o u r c e s ) 的特殊的自动制造系统，该系统主要是基于 p e t r i 网的结构分析理论。这种死锁预防方法通过对每一个严格极小信标增加一个 控制库所，从而使其成为受控信标；如果系统的无死锁性不能得到保证时，就可 以通过改变控制库所中的初始托肯数来使系统是无死锁的。显然，这种方法对一 般网而言，不是普遍适用的。【2 】中定义了一类保守的p e 订i 网子类，并且只对属于 该子类中的p e t r i 网模型进行研究。它同样采用对极小信标增加控制库所的方法， 但它的目的与其说是预防死锁倒不说是增强系统的活性。这种方法的优点是简单 并且肯定是可以达到目的的：其缺点同样是只能应用于某一类p e t r i 网中，并且这 种方法过多的约束了网系统的行为使p e t r i 网系统的可达标识大幅减少。 其次是死锁避免方法。这种方法可分为两类：一类是通过控制对资源的申请 使系统避免产生死锁，其思路是如果许可一个资源的请求会导致死锁，那么就不 能允许该申请有效。对于网模型而言，这种方法实际上是有意地控制某些使能的变 迁发射，以免p e t r i 网系统陷入死锁。这种限制资源分配的策略也具有一定的保守 性。 另一类死锁避免方法是通过改变p e t r i 网的结构，使系统不会产生死锁。做法 是为系统p e t r i 网模型中的每一个极小的信标增加一个所谓的控制库所，使得该信 标成为一个受控信标，然后保证网模型中的所有信标都不会被清空。这种做法的缺 点有两个：一是与第一类方法相比其资源分配策略具有较高的保守性；二是使得 p e t r i 网模型更加复杂( 增加了很多库所节点) 。 最著名的死锁避免算法就是银行家算法，如【5 】。但它不适合在自动制造系统 中应用。 4 】中的方法是通过向前搜索来避免死锁的。当给定一个网系统的当前标识后， 算法就会确定所有规定搜索长度内的标识状态；通过判断这些标识是否死锁，就 可以找到那些发射后会导致系统死锁的变迁。在网系统运行的时候，只要不使能 这类变迁就可以避免系统死锁。这种方法可以使系统有限度避免死锁，但确定搜 索步数有很大困难；而且还必须提供系统出现死锁时的修复策略。 f 6 1 中提供了一种针对自动制造系统的死锁避免算法，即d d a 算法。这种方法 通过执行以下两个策略来避免系统死锁。其一是使p e t r i 网系统中的某个库所集合 中的托肯数不能超过该库所集合末占用的资源中的托肯总数；其二是当该库所集 合中的库所同时申请多个资源并且这些资源都可以申请到时，它只能占用一个资 源。d d a 算法在每一工步开始申请共享资源时，通过有意的不使能某些变迁，来 保证以上两条策略的实施。 f 7 1 中的死锁避免算法是建立在最小资源需求的概念的基础之上，即使系统中 占用拭享资源最少的工步优先发射。这种算法具有多项式复杂度并且放松了对系 统的约束，因而比【6 】中的方法具有更广泛的应用。 第1 章绪论 【8 、 9 】中的方法比较类似。它们都是从死锁结构的概念出发明确了死锁产 生的条件，即当系统的死锁结构中占用的资源等于资源的总数时，系统就会陷入 死锁状态；并在此基础上形成了自身的死锁避免算法。 由于需要考虑大型的自动制造系统，f l o 在p e t r i 网模型的基础上针对资源分 配系统( r a s ) 开发了一种专门的新颖的建模和分析方法。它用整数规划的方法 来避免系统死锁。但是由于它考虑了r a s 系统中的大部分情况，从而使得网模型 不再是适用于一般网的，这就大大限制了它的应用。 第三种是死锁校正方法，如【“】、【1 2 】。它并不刻意去追求系统的无死锁性或 活性，而是一旦检测到系统发生了死锁，通过自动或人工的方法解锁。这种方法往 往会达到较高的生产率和资源利用率，但控制工程师必须对可能发生死锁的生产 环节有充分的认识，在设计单机( 如机器人，机床) 控制器时，需要设计相应的的控制 程序以便解锁时应用。此外，可能还需要一些附加的设备供解锁时使用， 其结果 又是要加大投入。 综合法的思路是建立一些具有某种性质的p e t r i 网模型，使得在某类p e t f i 网中， 针对这些特殊的性质，可以采用特定的控制策略来消除死锁，直h 1 3 、【1 4 、【1 5 】a 它的优点在于控制策略简单实用，但只能用在p e t r i 网的特定子类中。 目前基于网论的方法研究系统的死锁问题取得了不少成果，但是仍然有许多 问题需要进一步研究和解决。如i c 的生产系统与机械生产自动化系统有许多不同 之处。而目前的研究成果一般都是针对机械生产的自动化系统有效的。此外许多 控制方法和策略对系统的行为施加了过多的限制，降低了系统的性能。 论文致力于死锁避免方法的研究，通过分析p e t r i 网的结构特性运用代数的 方法保证系统的p e t r i 网模型是无死锁的。 1 2 本文完成的主要工作 论文系统地分析了现有的各类典型的死锁检测和排除算法，提出了一种新的 死锁避免算法，并有针对的解决了p e t r i 网领域内的一些基础性的问题： 提出了一种在不穷举网系统所有标识的前提下，计算网系统死锁标识的 算法。 改进了一种除去p e l x i 网伪标识的算法。 利用矩阵理论计算p e t f i 网的库所不变式、变迁不变式、求解状态方程并 对解进行分析，得出了有用的结论，并给出了证明。 把g r 6 b n e r 基与p e t r i 网分析相结合，写出了p e t r i 网状态方程和变迁使能 发射规则的多项式表达形式，并利用g r 6 b n e r 基对p e t r i 网的可达性问题 4基于p e t r i 网的自动制造系统的死锁分析 进行了分析，得出了结论并给出了证明。 提出了一种针对非循环网的可达性分析方法，提出了若干相关的定理和 推论并给出了证明：并通过将循环网转化为非循环网，而将这些结论扩 展到对一般网的可达性问题的分析。 最后针对一般网的可达性问题，提出了一套系统的解决方案。而可达性 问题正是解决系统死锁避免问题的关键。 总之，全文结合p e t r i 网的死锁避免算法，解决了p e t r i 网领域里的一些基本问 题，完善了p e t r i 网的理论体系，得到了一定的成果。相信这一工作对p e t r i 网理论 的进一步应用和发展都是十分有益的。限于时间、条件和个人的认识，文中很多 方面一定有所欠缺，恳请指正。 第2 章p e t r i 网的基本理论 第2 章p e t ri 网的基本理论 在本章中，将给出p e t r i 网( p n ) 的基本概念和形式定义，以及后面所要用到的 一些定理和推论。详细的证明和例子可参考 1 5 、 1 6 。 2 1p e t r i 网的基本理论 2 1 1p e t r i 网的基本定义 【定义2 1 】：库所变迁网是一个四元组，= ( s ，t ，f ，缈) ，其中s 代表所有 库所的集合，代表所有变迁的集合，并且s 、r 是相互不交的有限非空集合； 埏涔x d u ( a 称为有向弧集；w ：f - n 称为f 中弧上的权函数，肛 0 ，l ，2 ，) 。 称= ( s 只聍为一般网，当且仅当可f e f ，w ( f ) = l ：当可s e s ，v t e t ， 如果( s ，t ) e f ，那么( s ，t ) = l ，则称为一般p t 网。 【定义2 2 】：令= ( sn 只聊是一个网，节点x e s u t 的前置集定义为 x = y e s w t i ( y ，x ) e 毋。后置集定义为x = y e s w t i ( x ，y ) e 毋a 【定义2 3 1 ：令n = ( slr 聊是一个网， 1 ) n 的标识肘：s - n o ，n o _ 0 1 ，2 ) ； 2 ) 一个变迁t r 在肘下称为使能的，记为| 舡t ，当且仅当v s e t ： m ( s 沦w ( s ，t ) ； 3 ) 若脚协成立，则t 可发射，产生另一标识m ，记为蛳t m ，则 m ( j ) = 肘( s ) 一矿( j ，t ) m ( j ) + ( s ，t ) ( s ) 一( s ，) 4 - w ( ，j ) m ( s ) 4 1 从标识肘i 开始的所有可达标识的集合记为r ( ，m o ) 。它是一个最小集，即 “er 叫，g o ) ，m er ( ，g o ) a m t ) 删r ( n 胁) ； 5 1 当t 。，t ：，t n e t 时，a = t t t ：t 。被称为出现序列，当且仅当存在标识 g o ，满足m o f t 。) ； 6 1 对于p e t r i 网和某一标识慨，( 。m o ) 称为一个网系统； 7 ) 网n = ( sl 只聊的关联矩阵时】定义为s n z ，z 是整数的集合 r n 八r 距住距砷 基于p e t r i 同的自动制造系统的死锁分析 - w ( s , ，) s t t 俨雠- w ”( s ，f ) 州舢)：0 【0否则 2 1 2p e t r i 网的活性、不变式 【定义2 4 1 ：令n = ( sl 一聊是一个网，是的一个标识 1 ) 一个变迁在标识m o 下是活的，当且仅当v m r ( ，m o ) ，有m r ( 肘i ) ：m 【t ) 成立； 2 ) ( ，m o ) 是死锁的，当且仅当对于任意的t t ，胁i t ) 不成立； 3 ) ( ，m o ) 是无死锁的，当且仅当v m er ( n ，m o ) ，3 t t ：m 【t ) 成立； 4 ) ( ，m o ) 是活的，当且仅当对于任意的t e t ：t 是活的； 5 ) ( n ，m o ) 是有界的，当且仅当存在k 正m 口) v 肘r ( n ，m o ) ，vs 璺t 是活的： 6 ) ( ，m o ) 是结构有界的，当且仅当对于任意的有限的初始标识，它都是有界的； 值得说明的是，对于资源有限的实际系统而言，它的p e t r i 网模型一般都是结 构有界的。 【定义2 5 】：令= ( 只 只肋是一个网， 1 ) 称列向量1 是p e t r i 网的一个p 不变式( 库所不变式) 当且仅当，i n = 0 t ； 2 ) 称列向量，是一个，_ 不变式( 变迁不变式) 当且仅当 n 】o j = 0 7 。 对于网系统( ，g o ) ，v m m o ) ，o m = i t - 8 4 0 。t - 不变式对应于网系统有这 样个性质，发射一个f - 不变式对应的变迁序列，则产生一个重复标识，即在当前 标识下发射f - 不变式j 对应的变迁序列口= t l t ：t 。则回到当前标识。同样对于 p 一不变式而言，它对应的库所的集合中的托肯数在网系统中是不变的。f 不变式 和p 不变式在p e t r i 网的特性分析中有着极其广泛的应用。 【定义2 6 】：令n = ( s 兀只肿是一个网，由不变式- ，产生的子网h = 岱， 巧，局) 定义为码= i u l i ，昌乃u 毛。，f j = 彳h ( ( s j 乃) u ( 乃x 岛) ) ，其中1 1 j l t e r i j ( t ) o ) 称为，的支撑。 【定义2 7 】：令= ( 舅n 聊是一个网， 1 ) 称一个非空集合h cs 是一个信标( s i p h o n ) ，当且仅当日仁f 成立； 2 ) 称一个非空集合日s 是一个陷阱( t r a p ) ，当且仅当日j f 成立； 3 ) 称一个信标( 或陷阱) 是极小的，当且仅当不存在其它的信标是它的子集； 【定义2 8 】：令n = ( sl 力是一个网，h c s 是它的一个信标，则称 无= h 为h 的受控变迁集；而无( 正的补集) 称为日的不受控变迁集。 【定义2 9 1 ：令( ，m o ) 是一个网系统。称一个标识膨为伪标识是指它是 系统状态方程脑+ l = 脑+ n 】仃的解，但却不属于r ( ，m o ) 。 第2 章p e t r i 网的基本理论 2 1 3p e t r i 网的一些基本性质 【性质2 1 】：i 是一个p 不变式，则，的支撑l l 川既是一个信标也是一个陷阱。 在网系统中，i 中的托肯总数是不变的。 【性质2 2 】：h 是一个信标，则在网系统中它一旦被清空就不在会有托肯； 【性质2 3 】：日是一个陷阱，则其中的托肯数只能增加不会减少； 【性质2 4 】：对于一般p r 网，如果( ，加是死的，则所有未被标记的库所组 成一个信标； 【性质2 5 】：对于一般p r 网，网系统死锁的必要条件是所有的极小信标都被 清空； 注意【性质2 5 】，它是一般死锁分析方法的基础。 特别需要说明的是，在本文中主要讨论一般有界网。所以下文中提到的网模 型如无特别说明，都指的是一般有界网。 2 2p e r t i 网的实例分析 作为一个例子，考察图2 1 中带有初始标识的p e r t i 网。 图2 1 一个初始标识为 000 20 1 的p e t r i 网模型 8 基于p e t r i 网的自动制造系统的死锁分析 首先来分析它的结构特性。观察图2 1 所示的网结构。 对于库所：p l = t 5 ，t 6 p l 。= ( t 1 ) p 2 = f t l ，t 3 p 2 弋f t 2 ，t 5 ) 。p 3 = t l ，t 4 ) p 3 = t 2 ，t 6 】 p 4 = t 2 ) p 4 = t 3 ，t 4 ) p 5 = t 2 ) p 5 。= t 5 ，t 6 ) 由于2 p l + p 2 + 。p 3 + p 4 + p 5 = t l ，t 2 ，t 3 ，t 4 ，t 5 ，t 6 ) 并且2 p i + p 2 + p 3 + p 4 + p 5 = t l ，t 2 ，t 3 ，t 4 ，t 5 ，t 6 ) 所以，= 2l l1 1 1 是一个库所不变式。 而且图2 1 所示网系统的关系矩阵为 n 【】= l1 10 0一l 00 一ll 且有， n = 口 同样，由于p l + p 2 + 。p 3 + p d c p l 。+ p 2 + p 3 + p 4 。 所以 p 1 ，p 2 ，p 3 ，p 4 是网结构中的一个信标 同理 p l ，p 3 ，p 4 ，p 5 ) 和 p 1 ，p 2 ，p 4 ，p 5 ) 都是网结构中的信标 并且 p 1 ，p 2 ，p 3 ，p 4 、 p 1 ，p 3 ，p 4 ，p 5 ) 和 p l ，p 2 ，p 4 ，p 5 ) 都是网结构 中的极小信标。 对于变迁：t l = p 1 ) t i o = p 2 ，p 3 ) t 2 = p 2 ，p 3 ) t 2 = p 4 ，p 5 ) t 3 = p 4 ) t 3 = p 2 ) 。t 4 = p 4 t 4 = p 3 。t 5 = p 2 ，p 5 t 5 = ( p l t 6 = f p 3 ，p 5 ) t 6 = f p l 因为t l + t 2 + t 3 + 。t 5 = p 1 p 2 ，p 3 ，p 4 ，p 5 并且t 1 + t 2 。+ t 3 。+ t 5 = p l ，p 2 ，p 3 ，p 4 ，p 5 ) 以及t l + 。t 2 + t 4 + t 6 = ( p l ，p 2 ，p 3 ，p 4 ，p 5 = t l + t 2 + t 3 + t 5 所以= 1 ll010 7 和序 1l0l01 7 是网结构中的变迁不变式。 同时 n = 口年口 n 正= 口 0 o o o 0 ，o o o o o 一 1 o o 第2 章p e t r i 网的基本理论 下面再来分析它的运行情况。 在图2 1 标识状态下有初始标识m o = 00020 t i 变迁是t 3 和“使能的。 因为t 3 和t 4 的输入库所p 4 中有托肯：其它变迁不是使能的，因为t l 、t 2 、t 5 和 t 6 的输入库所中都没有托肯。由于t 3 和“都是使能的，它们当中的任一个都可以 发射如果发射t 3 ，便从它的每一个输入库所中移走该输入弧的权个托肯，使它 的每一个输出库所的输出弧的权数个托肯，即从p 4 中移走一个托肯，在p 2 中加 入一个托肯，这样产生的新的标识就如图2 2 所示。 图2 2 从图2 1 的p e t r i 网系统发射t 3 而产生的标识 初始标识状态下发射t 3 可得到新的标识m = 0 1o1o 1 ，在新的标识 下变迁是b 和“使能的，这时若继续发射t 3 ，可到达新的标识m 2 - - - - - 0 20 00 t ， 如图2 3 所示。 在标识 如下没有变迁是使能的，网系统陷入死锁。如果在标识胁下不发射 变迁t 3 而改为发射变迁t 4 ，则可到达另一个新的标识m 3 = 01 1 00 1 ，如图2 4a 在标识尬下又有变迁是使能的，所以网系统可继续运行。 1 0基于p e t r i 网的自动制造系统的死锁分析 图2 3 从图2 2 的p e t r i 网发射t 3 而产生的标识 图2 4 从图2 2 的p e l 】 i 网发射“而产生的标识 2 3 小结 本章主要介绍了p e t r i 网的一些基本概念和结论，并通过一个例子对以后要用 到的一些概念进行了说明。 第3 章一种死锁避免算法 第3 章一种死锁避免算法 在本章中将给出一种死锁避免算法，以及如何在不穷举网系统所有标识的前 提下求解死锁标识的方法。 3 1 概述 第l 章中已经分析过，在现有的死锁处理方法中：死锁预防的方法降低了系 统的生产率和资源的利用率；死锁校正方法对控制工程师的要求较高，并且需要 一些附加的设备供解锁时使用，所以又要加大投入；综合法只能用在p e t r i 网的特 定子类中；现有的一些死锁避免方法都是以【性质2 5 】为基础，通过构造一类特 殊的p e t r i 网模型，使得【性质2 5 】的充分性也成立，或者是通过改变p e t r i 网的 结构保证网模型中的所有信标都不会被清空。其结果要么限制了p e t r i 网的应用， 要么使得p e t r i 网模型更加复杂，而且都过分约束了网系统的行为。可见现有的这 些算法都有其自身不可避免的缺陷，因而大大的限制了它们的应用范围。 那么真正解决死锁问题的理想方案应该是怎么样的呢? 9 图3 1 一个简单的网系统的可达标识图 下面看一个例子。如图3 1 是一个简单的网系统的可达标识图，网系统在处于 m s 、m s 、胁的标识状态时死锁。为了避免死锁又不过分限制网系统的行为，就必 须在标识尬下不发射变迁t 1 在标识尬下不发射变迁t 5 。把类似心、脶的标 识称为危险标识。这样通过控制危险标识下变迁的发射就能以最小的代价保证系 统的活性。观察图3 1 ，虽然标识眠不是一个死锁标识，但是在慨下无论发射那 个变迁系统都将陷入死锁。所以把类似肘i 的标识称为坏标识。在网系统的运行中， 坏标识也是必须避免的。 由于求出可达图就意味着要穷举系统所有的状态。对于实际的系统而言，系 统的状态往往相当庞大，穷举系统所有的状态就会要求有相应的存储空间，同时 计算的难度和复杂度也随系统规模的增太而大幅度提高，实现这类穷举算法可能 要花费相当大的代价，有时甚至是不可能。那么对任意的p e t r i 模型，在不知道网 ! 三一一一一 垂王堡生旦盟鱼垫型童墨堕笪錾塑坌堑 系统的可达图的前提下预知在某一标识状态那些变迁应该发射，那些变迁不应该 发射，从而使系统是无死锁这就是解决死锁问题的理想目标。 3 2 一种死锁避免算法 本节中将给出一种死锁避免算法。它是通过寻找网系统中危险标识状态下需 要控制的变迁，并通过施加控制策略人为的使某些危险标识状态下的变迁不被发 射，从而达到避免系统死锁的目的。 3 2 1 算法描述 算法的基本思路如下： 在不遍历网系统所有状态的前提下，根据己知模型先求出网系统的死锁标识； 然后，由这些死锁标识出发，找到需要控制的危险标识；晟后针对需要控制的 危险标识生成相应的控制策略。算法如下： 算法3 1 ：死锁避免算法 s t e p1 ：求出系统的死锁标识； s t e p2 ：对每一个死锁标识，先求其上一级的父标识： s t e p3 ：若其父标识的子标识都是死锁标识，将其父标识也看作是一个死锁标 识转到s t e p 2 ； s t e p4 ：若其父标识的子标识不是都是死锁标识，将该标识记为危险标识。并 将该标识和其标识状态下使能的变迁中发射后会导致系统死锁的变迁记为一个序 对 ，存入由该序对构成得集合k ( m ，0 ： s t e p5 ：如果所有的死锁标识都已经转变为危险标识，那么转到s t e p6 ；否则， 转到s t e p2 ； s t e p6 ：系统运行时，在集合k ( m ，t ) 中查找是否遇到危险标识：遇到危险标识 时，不发射该标识在序对中对应的会导致死锁标志的使能变迁，从而保证系统是 无死锁的。 e n d 3 2 2 算法说明 仔细分析以上算法可以看出，这种算法不但可以适用于一般网，并且能在不 遍历网系统的所有标识状态的前提下，自下而上的得到在网系统运行过程中需要 加以控制的危险标识，在网系统运行时通过有意识的禁止危险标识下某些使能变 迁的发射，来保证整个网系统是无死锁的。该算法尽可能的减小了对网系统本身 的约束，同时又使得网系统是完全无死锁的，从而在理论上保证了网系统的最大 的灵活性。 第3 章种死锁避免算法 同样可以看出，在该算法中有以下几个问题需要重点解决 如何求出死锁标识 如何判断某一标识是否是网系统的可达标识 3 3 求解p e t r i 网系统死锁标识的方法 在本节中给出求解网系统的死锁标识的方法。它主要利用两个性质：一个是利 用第二节中的【性质2 4 】，即网系统发生死锁时必然有信标被清空；另一个是从 死锁的定义出发，即系统发生死锁时所有的变迁部不使能。 算法3 2 ：求解网系统死锁标识的算法 给定一个网系统( ，m o ) s t e pl ：求出网结构中的极小信标隅，玩，矾和p 一不变式，1 ，m ： s t e p2 ：分别求出每一个极小信标儡的不受控变迁集； s t e p 3 ：令髓= 0 ，即令h i 中对应的库所中的托肯数等于0 ；再利用的不使 能条件：然后利用第二节中提到的【性质2 1 】，即不变式，j ，如，j n 中的托 肯数为常数，这几个性质，联合求解，求出所有符合死锁定义条件的可能的死锁 标识m d s ，( 注意，这里说的是“可能的死锁标识”) 。 s t e p4 ：从s t e p3 中产生的可能的死锁标识集m d s 中除去不可达的假死锁标识， 得到网系统的死锁标识集 埘； e n d 下面举一个例子，如图3 2 。网系统的初始标识m o = 40 000040 0 o001 l1 11 1 1 。由算法3 2 可得： s t e pl ：求出给定网结构中的极小信标对应的向量 肌5 0 0 0l010100 01 11ol l 】 飓= 【0 0 00 0l00 0 0 01 l1 1l 1 凰= 【0 0 00 0lo0 0l0 0 0 0l0 1 】 求出给定网结构中的p 不变式 ，l = 【o000 000000 100 100 0 1 1 1 2 = 【0 00o001 l 11 11o0000 1 3 = 【0 l0000 000001o001 0 1 4 = 【0 00010 001000 0o10 0 】 1 5 = 【0 00101o1010000001 】7 j 62 0 01000o0 00001o00 0 】 1 7 = 1 l1 1 11o000000 0000 】7 4基于p e t d 网的自动制造系统的死锁分析 图3 2 一个_ 【 j 丁计算死锁标识的例子 s t e p2 ：分别求出每一个极小信标的不受控变迁集 t s l 2 d r s 2 = 西 t s 3 = t l ，t 2 ，t 1 1 ，t 1 2 ) s t e p3 ：分别解方程组 得 f = p 6 = p 8 = p 1 2 = p 1 3 = p 1 4 = p 1 6 = p 1 7 = 0 l 0 1 1 + p 1 4 = 1 l p 7 + p 8 + p 9 + p 1 0 + p l l + p 1 2 = 4 i p 2 + p 1 2 + p 1 6 = l l p 5 + p 9 + p 1 5 = 1 i p 4 + p 6 + 邡+ p 1 0 + p 1 7 = 1 i p 3 + p 1 3 = 1 l 口+ p 2 + p 3 + p 4 + p 5 + p 6 = 4 m s d l = f 2 1l000 20 01 1 00010 o 】2 m s d 2 = 21 100 010111000000 】1 m s d 3 = 【11 1010 2001 1000000 】 ( 式3 1 ) 蔓! 童= 塑噩壁鲤鱼蔓鎏 坚 ( 2 ) 得 ( 3 ) i p 6 = p 1 2 = p 1 3 = p 1 4 = p 1 5 = p 1 6 = p 1 7 = 0 f p l l + p 1 4 = 1 j p 7 + p 8 + 矽+ p l o + p l l + p 1 2 = 4 l p 2 + p 1 2 + p 1 6 = 1 f p 5 + 毋十p 1 5 = 1 i p 4 + p 6 + p 8 + p l o + p 1 7 = 1 l 邸+ p 1 3 = 1 【p 1 + p 2 + p 3 + p 4 + p 5 + p 6 = 4 m s d j = f 2 1 1000101 i1000000 1 1 胁如2 【11 1 0102001 1000000 1 1 m s 西= 【21 1 00 01 1 101000000 1 胁比2 11 1010 210o100000 0 1 m s d 5 = 11 1 100 2010100000 0 1 1 m s d 6 = 【01 1 1 1030 001000000 1 1 p 6 = p l o = p 1 5 = p 1 7 = p 1 2 = 0 p 1 = 0 v p l 6 = 0 p 2 = 0 v p l 3 = 0 p l l = 0 v p l 6 = 0 p 1 1 + p 1 4 = 1 p 7 + p 8 + p 9 + p l o + p l l + p 1 2 = 4 ( 式3 3 ) p 2 + p 1 2 + p 1 6 = l p 5 + p 9 + p 1 5 = 1 p 4 + p 6 + p 8 + p l o + p 1 7 = 1 p 3 + p 1 3 = i p l + p 2 + p 3 + p 4 + p 5 + p 6 = 4 得：m s d l = 【0 11 1 10 40000001000 1 1 m s d 22 【21 1000 21 100001000 1 。 m s d 3 = 2 1100 01 1 1 01000000 1 1 m s d 4 = 11 1010310 00001000 1 1 m s d 5 = 11 1 010 21001000000 1 1 m s d 6 = 【1 1110020101000000 】1 m s d 7 2 【1 1110030100001000 】1 m s d 8 = 【01 1 11030 00100000 o 】。 ( 式3 2 ) 6 基。t - p e t r i 网的自动制造系统的死锁分析 s t e p4 ：除去不可达的的伪标识，得到网系统的死锁标识为 m d l = 01 l l10400000010o0 。 m d 2 = 【o1 11 l030o01 000000 】1 m d 3 - i1 1 l o03010o0o100 o 】。 刎4 = 1l l01 031000o0l000 】。 m d 52 11 lo1o2l00l000o00 】 m d 62 【1 11 l00201o1000000 】1 m d 7 = 【21 10o 01 110 10o000 o m d 8 = 【21 10 o0 2l10000 1000 。 m d 9 = 【2 1 1o00 2001 1000lo0 由附录可对计算结果加以验证。 3 4 小结 本章主要介绍了一种新的死锁避免方法，并且也提出了如何在不遍历系统所 有可能标识的前提下，求解系统死锁标识的方法。可以看出，这种新的死锁避免 方法适用于一般网，并且对网系统的约束最小；但是其中所涉及的关键问题就是 如何判断网系统的标识的可达性。 第4 章p e t r i 网状态方程和不变式的求解 第4 章p e t ri 网状态方程和不变式的求解 4 1 概述 p e t r i 网的状态方程是描述p e t r i 网可达标识与初始标识之间关系的一个重 要方程。求解状态方程是p e t r i 网理论分析中的一个基本问题，但尚未见到有完 备的求解方法见诸文献。目前常用的一些解法，如 1 9 ，忽视了p e t r i 网结构中 的循环、并发和选择结构，求解出固定的发射向量，这显然是不对的。因为对于 一般的网系统而苦，可能存在循环、并发或选择结构因此发射向量并不唯一。 所以根据状态方程求解发射向量，得到的不应该是一个固定解而应该是一个解的 集合。 在求解p e t r i 网的不变式时现有的方法，如 1 8 ，需要手工的运算并且很 难用计算机实现。又由于p e t r i 网的关系矩阵一般是不满秩的，而且p e t r i 网的 不变式可以相互组合构成新的不变式，因此根据定义求解不变式，依然有很大的 困难。 本章将矩阵理论的一些结论和方法 2 0 引入p e t r i 网的特性分析领域，得到一 些新的结论，并且大幅度的简化了p e t r i 网状念方程的求解和不变式的计算。 4 2p e t r i 网中不变式的求解 42 1 矩阵论的基本概念 【定义4 1 】对于m 以维矩阵c ，设其秩r a n k ( c ) - ，则有当，气州时称该矩 阵是行满秩的：当r = l , t 时称该矩阵是列满秩的。 对于行满秩矩阵c ，( c c 7 ) ( c c 7 ) 1 = e 。，e 为单位阵，c 7 是c 的转秩。 【定义4 2 】称c + = c t ( c c r ) 。为行满秩矩阵c ，。的右逆，即c c = ； 同样，对于列满秩矩阵c ，( c r c ) j ( c r c ) = e 。，e 为单位阵，一是c 的转秩， 则称c _ ( c r c ) 1 ，为列满秩矩阵c 的左逆，即c c _ e 。 无论左逆还是右逆都是矩阵广义逆的一种特殊形式。 【定义4 3 】设ae c ( ， o