（计算机软件与理论专业论文）面向对象petri网的约简和系统死锁的检测.pdf

山东大学硕士学位论文 皇曼罾| 曼曼曼曼曼曼曼曼曼曼量鲁量曼曼曼曼量皇曼皇邑曼鼍皇皇置量量曼舅曼量量量曼舅目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 网综合了普通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 网系统的完整死锁检测研究过程中，论文总结和归纳 了许多有用的概念和结论，而且这些概念和结论对于网系统其他相关分析也是普 遍使用的。 关键字： o o p n ：人机交互；死锁；可达；约简 山东大学硕士学位论文 a b s t r a c t b e c a u s et h eo b je c t - o r i e n t e dp e t r in e t sa p p l i c a t i o ni sg e t t i n gm o r ea n dm o r e w i d e s p r e a d ，a sw e l la st h ei m p o r t a n c e o fm a n m a c h i n ei n t e r a c t i o nb e h a v i o ri n s o f t w a r ed e v e l o p m e n tp r o c e s sa n dp r a c t i c a la p p l i c a t i o n ，t h e r e f o r et h ep a p e rd e v o t e si n t h ed e a d l o c ke x a m i n a t i o nr e s e a r c ht h r o u g ha n a l y z e st h eo b j e c t - o r i e n t e dp e t r in e t s s t r u c t u r a lp r o p e r t y , u s i n ga l g e b r a i ca n a l y s i sm e t h o dju d g e sm a n - m a c h i n ei n t e r a c t i o n s y s t e m so b je c t - o r i e n t e dp e t r in e tm o d e lw h e t h e rt oh a v et h ed e a d l o c k a l t h o u g ht h ed e a d l o c k sr e s e a r c hi nt h ep e t r in e tm o d e la l r e a d yi sv e r ym a n y , b u t g e n e r a l l ya i m i n ga tt h eo r d i n a r yp e t r in e t ，c o u l dn o tb es u i t a b l e w e l li nt h e o b je c t - o r i e n t e dp e t r in e ta n di nt h em a n - m a c h i n ei n t e r a c t i o ns y s t e m b e c a u s et h e o b je c t o r i e n t e dp e t r in e ts y n t h e s i z e dt h ea d v a n t a g e so fb o t ho r d i n a r yp e t r in e ta n d o b j e c t - o r i e n t e dt e c h n o l o g yt h i s a r t i c l eh a sd e e p l yr e s e a r c h e dt h ee x i s t i n gm e t h o d s ， a n dp r o p o s e do n ed e a d l o c ke x a m i n a t i o na l g o r i t h mb e i n gs u i t a b l ei nt h e o b je c t o r i e n t e dp e t r im o d e l t h i sa l g o r i t h ma c t sa c c o r d i n gt ot h ee n c a p s u l a t i o no fo b j e c t - o r i e n t e dt e c h n o l o g y ，c a r r i e so n t h el a m i n a t i o nt ot h eo b j e c ts u b n e t , a n dc o n d u c t st h er e s e a r c hb ya n a l y t i ch i e r a r c h i e st h o u g h tt o e a c ho b j e c ts u b n e t ，l i k et h i sg r e a t l yr e d u c e dt h ec o m p l e x i t y i no r d e rt of u r t h e rr e d u c i n gt h e c o m p l e x i t ya n de f f e c f i v e l yr e s o l v es t a t es p a c ee x p l o s i v ep r o b l e m , a c c o r d i n gt ot h eo r d i n a r yp e t r i f i s h i n gg e a rh a sc h a r a c t e r i s t i c si nf i g u r e sa n dd i a g r a m sa n ds t r i c tm a t h e m a t i c ss i g n i f i c a n c e ， p r o p o s e st h es i xr e d u c t i o nm l em a i n t a i n i n gt h ed e a d l o c kp r o p e r t y ，t h e s er e d u c t i o nr u l ee f f e c t i v e l y r e d u c e dt h ep o i n tn u m b e rw h i c hm u s ta n a l y z e ，a n dr a i s e dt h en a t u r ea n a l y s i se f f i c i e n c y t h ee x i s t i n ga c c e s s i b i l i t yj u d g m e n t sm e t h o d sa r em a i n l yb a s e do nt h ep l a c e i n v a r i a n ta n dt h ee q u a t i o no fs t a t e ，b u tt h ep l a c ei n v a r i a n tm e t h o dh a sn o tc o n t a i n e d n e ts y s t e mi n i t i a lm a r k i n gc o m p l e t e l y , a n dt h ep e t r in e te q u a t i o no fs t a t em e t h o di s u n a b l et od e s c r i b et h eo r d e ro ft r a n s i t i o n sf i r e t h i sa r t i c l ep r o p o s e so n ek i n do fn e w a l g o r i t h mo fp e t r in e t sa c c e s s i b i l i t y , n o to n l yt h i sa l g o r i t h mh a sm a d eu pt h ea b o v e l i 山东大学硕士学位论文 t w om e t h o d ss h o r t c o m i n g ，m o r e o v e rm a ye f f e c t i v e l yd i s c o v e rt h ew a yf r o mi n i t i a l m a r k i n gr e a c h i n gt og o a lm a r k i n g ，o rj u d g e sg o a lm a r k i n gn o tt ob ep o s s i b l e r e a c h e d a n dt h e n p r o p o s e s a l l a l g o r i t h mt os o l v ed e a d l o c k sm a r k i n g f i n a l l y s y n t h e s i z e sa l la n a l y s i sc o n c l u s i o na n dt h es u b - a l g o r i t h m , o b t a i n st h eo b je c t - o r i e n t e d p e 仃in e ts y s t e m 。sc o m p l e t ed e a dl o c ke x a m i n a t i o na l g o r i t h m i nt h ee n t i r er e s e a r c hp r o c e s s ，t h ep a p e rh a ss u m m a r i z e da n di n d u c e dm a n y u s e f u lc o n c e p t sa n dt h ec o n c l u s i o n ，m o r e o v e rt h e s ec o n c e p t sa n dc o n c l u s i o n sa r ea l s o u n i v e r s a lu s i n gt oo t h e rc o r r e l a t i o na n a l y s e s k e yw o r d s ：o o p n ；m a n m a c h i n ei n t e r a c t i o n ；d e a d l o c k ；a c c e s s i b i l i t y ；r e d u c t i o n 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：斟圭蛰 日 期：必：绝 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：音土兰些 导师签名： 山东大学硕士学位论文 曼曼曼曼曼量曼曼曼曼曼曼曼曼量曼量量量罾| 皇曼曼蔓曼曼曼曼皇邑皇曼量皇量量量曼曼鲁曼曼曼置曼曼曼曼量 1 1 研究背景和意义 第一章绪论 人机交互系统是以实现自然、高效、和谐的使用为目的，具有并发、异步 以及资源共享等特性。人机交互行为的抽象描述在整个软件开发过程中非常重 要，并且实际应用中的人机交互系统必须是活的，不能存在死锁的操作。一旦系 统中由于资源调配不合理，或者某些操作占有系统资源不释放而出现死锁，而没 有人为干预，系统就会一直处于锁定状态，无法继续运行，从而严重的影响系统 的应用和友好性。因此人机交互系统中死锁状态的检测与控制是一个很重要问 题。 如何在人机交互系统的设计过程中及早地发现影响系统使用的死锁现象， 对整个系统的构成是非常重要的。面向对象p e t r i 网( o o p n ，o b j e c t o r i e n t e d p e t r i n e t s ) 由于综合了基本p e t r i 网的系统分析特性和面向对象的建模思想，因此可以 用来描述人机交互系统的静态结构和动态行为，并以此来分析和检测系统的特 性。 在系统设计和开发过程中利用p e t r i 网进行死锁检测，其复杂性主要依赖于系 统状态的空间大小，算法的复杂度往往是指数数量级的。对中等规模的系统进行 分析的时候，p e t r i 网的模型就已经变得非常大了，常常使人感到无从下手，更 不用说分析复杂的大系统了。状态空间爆炸是死锁检测所面临的主要问题，因此 简化系统模型、降低死锁分析复杂度是解决该问题的关键。本文针对上述问题， 提出了一套保持网系统性质的约简规则和分析方法。 自p e t r i 网的概念形成以来，有关性质的研究就非常活跃n 刊，可达性和死锁 的是否存在密不可分。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 网标识可达性的方法，此 方法可以找出从初始标识到目标标识的可达路径，或者判断出从初始标识到目标 标识式不存在可达路径，即目标标识是不可达的。 利用对象子网的分层、约简规则、可达算法，采用分而治之和层次分析的思 想，给出一种综合的死锁检测算法，这种算法非常有效地解决了状态空间爆炸问 题和人机交互系统的死锁检测问题。 1 2 面向对象p e t ri 网系统的现状分析 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 ) 理论鲥，从此以后得到了迅速 发展n 纠羽。p e t r i 网作为一种形式化的数学工具，能简洁地描述系统的动态特性( 如 并发、同步、冲突等) 和系统中的资源及约束条件，并有相应的分析方法( 如可达 树分析、不变量分析等) ，而且p e t r i 网是一种图形工具，易于理解和描述，在多 个系统中得到广泛应用n 9 。2 引。面向对象方法具有可重用、易维护、稳定性好等特 点，它提供了抽象的封装、多态以及继承机制，面对庞大而复杂的系统描述提供 了更有效的简化手段，可有效的提高系统的开发效率。因此，将面向对象和p e t r i 网结合，可以有效地对系统进行动态建模和性质分析，已广泛地应用在在多种系 统中。 1 2 1 系统约简的研究现状 1 9 8 9 年，t a d a om u r a t a 提出了保持活性、安全性、有界性的七条约简规则乜7 3 。 在国外相关研究的基础上，蒋昌俊提出了加权t 一图的几种约简运算，研究了这些 运算对结构性质的保持条件乜引，许安国对p t 网即加权p e t r i 网进行了研究，提出 了串约简、并行约简、分叉约简和回路约简四种运算，并分析了它们对结构性质、 公平性、及库所不变式的保持条件瞳9 。但这些约简规则，一般都只是针对于普通 p e t r i 网的应用，本文基于面向对象p e t r i 网的死锁检测，给出适用于面向对象 2 山东大学硕士学位论文 量曼曼曼曼皇曼曼詈量曼量奠曼曼曼舅量曼曼曼皇曼曼曼曼曼曼舅曼曼曼曼曼曼曼曼曼曼曼曼曼量罾鲁皇曼曼曼曼曼喜曼曼曼曼皇鲁量曼曼量_ p e t r i 网的约简规则，并保持其死锁性质。 1 2 2 系统死锁研究现状 基于p e t r i 网来处理系统中的死锁问题。一般可分为四类：死锁预防方法、 死锁避免方法、死锁校正方法、综合法。 死锁预防方法啪3 1 矧是一种回避死锁的方法，其目标是设计一个系统，该 系统所对应的p e t r i 网模型本身就是无死锁的或者是活的。这种方法从逻辑关系 上就保证了系统中是不会出现死锁的，因而也就没有必要再去控制系统运行过程 中对资源的申请。其思路是通过控制系统中的托肯( 对于网系统而言，就是控制 网系统的初始标识) ，使系统的p e t r i 网模型是活的，从而在原则上保证系统不会 陷入死锁。这种方法从确保系统不存在任何死锁的角度出发，相应地静态调配资 源( 设置初始标识) 。尽管系统存在死锁，但只要在系统动态运行时绕过这些死锁， 就不会出现死锁。因此没有必要为了预防可能出现但能回避的死锁而不配置某些 资源，从而提高资源的利用率。应该指出，这种方法尽管保证了系统的全局活性， 但具有较大的保守性，从而降低了系统的生产率和资源的利用率。 死锁避免方法一b 司分为两类：一类是通过控制对资源的申请使系统避免产 生死锁，其思路是如果许可一个资源的请求会导致死锁， 那么就不能允许该申 请有效。对于网模型而言，这种方法实际上是有意地控制某些使能的变迁发射， 以免p e t ri 网系统陷入死锁。这种限制资源分配的策略也具有一定的保守性。另 一类死锁避免方法是通过改变p e t ri 网的结构，使系统不会产生死锁。做法是为 系统p e t ri 网模型中的每一个极小的信标增加一个所谓的控制库所，使得该信标 成为一个受控信标，然后保证网模型中的所有信标都不会被清空。这种做法的缺 点是其资源分配策略具有较高的保守性，并且使得p e t ri 网模型更加复杂( 增加了 很多库所节点) 。 死锁校正方法m 瓠3 不刻意去追求系统的无死锁性或活性，而是一旦检测到 系统发生了死锁，通过自动或人工的方法解锁。这种方法往往会达到较高的生产 率和资源利用率，但要求控制器必须对可能发生死锁的环节有充分的认识，在设 计控制器时，需要设计相应的的控制程序以便解锁时应用。此外，可能还需要一 些附加的设备供解锁时使用，其结果又是要加大投入。 综合法的思路是建立一些具有某种性质的p e t r i 网模型，使得在某类p e t r i 3 山东大学硕士学位论文 薯量曼量量量量量量曾量量皇量量量皇| 曩量曼曼量量曼舅蔓蔓皇量| 量曼量量曼曼曼奠 网中，针对这些特殊的性质，可以采用特定的控制策略来消除死锁m 叫1 ，它的优 点在于控制策略简单实用，但只能用在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 网模型是否有无死锁。根据死 锁检测的结果，可以对系统进行死锁预防、死锁避免、死锁校正等。 1 3 本文的主要工作和创新点 虽然现在已经有很多研究是针对网系统的约简和死锁分析，但这些研究大多 都是只适用于柔性制造系统和普通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 网用于人机交互系统建模中是否存 在死锁。具体开展了以下方面的工作。 1 ) 建立面向对象p e t r i 网子网的分层概念。根据对象子网的初始托肯，和对 象子网之间的输入、输出流关联关系，确定每个对象子网的层次。在这个分层的 基础上，对对象子网进行约简和死锁检测分析。 2 ) 建立面向对象p e t r i 网的约简规则。根据网系统的结构和特性，建立适用 于对象子网和整合网的约简规则，大大减少了网系统中的节点，极大地提高了性 质分析的效率。 3 ) 深入研究面向对象p e t r i 网的可达分析算法。可达性分析在p e t r i 网系统 中非常重要，并且和死锁的是否存在紧密相关。本文给出基于变迁不变式对可达 性研究分析的算法，并且可以求出从初始标识到目标标识的可达路径，或者判断 出目标标识是从初始标识不可达的。 4 ) 提出面向对象p e t r i 网的一种死锁检测算法。在不穷举网系统所有标识的 前提下求解死锁标识。根据一些性质，用代数方法求出网系统中存在的可能死锁， 4 山东大学硕士学位论文 由状态方程、库所不变式、可达算法分析死锁的真假性。 5 ) 提出面向对象p e t r i 网的完整死锁检测算法。综合对象子网分层、面向对 象p e t r i 网的约简规则、可达算法、检测算法，给出面向对象p e t r i 网系统的完整 死锁检测算法。 6 ) 实例验证。以人机交互系统用户界面图形编辑器的面向对象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 网的完整死锁检测算法，此算法先对对象子网进行分层、约简、 死锁检测，然后对整合网进行约简和死锁检测。 1 4 本文的组织结构 本文共分为六章，第一章提出了本文所研究的问题、背景、意义以及国内外 相关研究现状，并概括了本文的主要工作和创新点。第二章介绍了面向对象p e t r i 网基本定义和性质。第三章给出了面向对象p e t r i 网系统的分层方法和约简规则， 并以一个示例阐述了分层思想和约简规则的应用。第四章主要分析了可达性的实 质问题，针对现有可达性分析方法的缺点，给出一个用变迁不变式求解可达路径 的算法。第五章给出一种死锁检测算法，并综合前面的理论，提出面向对象p e t r i 网系统的完整死锁检测算法。第六章以一个人机交互系统的实例为模型，说明了 面向对象p e t r i 网系统的完整死锁检测算法的实用性和有效性。最后一章为本文 的结束语，总结了全文所作的工作和下一步应当改进和完善的工作。 山东大学硕士学位论文 第二章面向对象p e t ri 网的基本理论 2 1 面向对象p e t ri 网的定义和性质 此小节详细介绍了面向对象p e t r i 网的定义，以及本文以下章节中所要用到 的活性、死锁、不变式、信标、陷阱等性质。 2 1 1 面向对象p e t ri 网的定义 定义1o o p n 4 5 t4 6 1 s 由子网以及子网之间的消息传递关系组成，是一个二 元组s = ( d ，d ) 。其中： ( 1 ) 0 = 鸱l i z + ) 是非空有限对象子网集合，每个对象子网都是一个七元组 q = 叱，正，m i i ，e ，e ，置，m o ) ，只为子网内部的库所集合，巧为子网内部的变迁集 合，崛为对象的消息接口集合，包括输入消息接l i 和输出消息接口，曩为流关 系集合，c f 为颜色集合，置为流关系上的权值集合，眠为初始标识。 ( 2 ) d = d ui f 工z + 是子网间关系的非空有限集合，d 抒表示的是子网q 和。之间的关系，用一个五元组磅= ：，q ，蚂，与，玛) 表示，q 是门集合，o m i i 和幽是输入和输出消息接口集合，厶是用来连接门与相应消息接口的流关系集 合，置，是子网间流关系上的权值集合。 为分析讨论方便，约定在2 1 节的以下部分和3 2 1 小节部分p = 曰l i e z + 是 所有子网内部库所的非空有限集合；m = 她l i z + ) 是所有消息接l i 的非空有限 集合；丁= 巧l i z + ) 是所有子网内部变迁的非空有限集合：g ：眠l i ly ，f ，j ez + 是 所有子网间门的非空有限集合；f = 识i f z + ) 是所有子网内部流关系的非空有限 集合；l = 饵l i z + 是所有子网间流关系的非空有限集合：q = q i f z + 是所有对 象库所节点的非空有限集合，q f 是对象库所节点：y = p u 尥u q ，对坳y ， ( p ) 为节点p 内的托肯集合：r = 】，u t u g 为所有节点的集合：w = f u l 为所 有流关系的集合。 定义2由约简规则进行约简后的网称为简化网。 定义3由死锁检测算法进行检测后的对象子网，若是无死锁的，则将此对 6 山东大学硕士学位论文 象子网抽象成的节点称为对象库所。 定义4o o p n 的网系统s ：( d ，d ) 称为一般网，当且仅当所有流关系上的权值 为1 ，即v p y ，v t ( r u g ) ，x ( t ，p ) = 1 。 定义5 在o o p n 的网系统s = ( d ，d ) 中，令r r ，则d n ( r ) 为节点r 的输入度， d o u t ( r ) 为节点r 的输出度；f l i n ( r ) = f wit a i l ( f ) = r ) 为指向节点r 的输入流 关系集合，f l o u t ( r ) = f wh e a d ( f ) = r ) 为从节点r 发出的输出流关系集合： = r i r i f w ，h e a d ( f ) = e , r a i l ( f ) = r 为 r 的前集， 一= r rf w ，h e a d ( f ) = r ，r a i t ( f ) = r i 为r 的后集。其中t a i l ( f ) 表示流关系 的尾节点，h e a d ( f ) 表示流关系厂的头节点。 定义6 在o o p n 的网系统s ：( o 。d ) 中， ( 1 ) s 的标识膨：】，专i n ，i n 是非负整数； ( 2 ) 一个t ( t u g ) 在标识m 下是使能的，记为mt ) ，当且仅当印f ： m 。x ( p ，z ) ： ( 3 ) 若m 。x ( p ，t ) 成立，t 可发射，产生另一标识m ，则 m ( p ) = m ( p ) 一x ( p ，f ) m ( p ) + x ( t ，p ) m ( p ) 一y ( p ，f ) + x o ，p ) m ( p ) ( 4 ) 网s 或子网d 的关联矩阵4 定义为 a ( t ，p ) = p t p t p 。f 且p t 。 f 且p 其它 一x ( p ，t ) p x ( t ，p ) p t 一x ( p ，f ) + r o ，p ) p f 且p t 。 0其它 ( 5 ) 从标识m 可达的所有标识的集合称为r e a c h ( s ，m ) ； ( 6 ) 如果标识m 是从初始标识m 。可达的，则状态方程m = 眠+ 仃彳有解， 且至少存在一个标识序列= m o m 卜m ，使m ，= m ，并且存在变迁发射序列 f = t i l ：，所有变迁发射的次数组成的向量仃称为变迁发射向量。发射变迁序 列和标识序列都关联与状态方程峨= m + p 【珐】。a ，k 2 1 ，2 ，p 阮】。是 ( i 珑) 的变迁发射向量，其中m 一1 个项是0 ，第k 项是1 ，即变f f ：t , k 在第k 步发射， m 是网系统中的变迁个数。序列和f 可以组合为相关标识和激发变迁的一个混 7 山东大学硕士学位论文 皇曼曼量曼曼罾量量曼曼曼曼量笪量量量量曼量曼量量皇薯| 毫量曼量量量| 崮 合序列，称为从初始m 。到标识m ，的可达路径：m 。山m 。山与m ，。 2 1 2 面向对象p e t r i 网的活性、死锁、不变式 定义1 在o o p n 的网系统s = ( d ，d ) 中，m 是s 的一个标识， ( 1 ) 一个t ( t u g ) 在标识m 下是使能的，当且仅当v m r e a c h ( s ，m ) ，有 m 。l t ) 成立： ( 2 ) 标识m 是死锁的，当且仅当对于任意f ( t u g ) ，m i f ) 不成立； ( 3 ) 标识m 是死锁的，当且仅当跏r e a c h ( s ，m ) ，3 t 仃u g ) ，m l t ) 成 立： ( 4 ) 标识m 是活的，当且仅当对于任意t 仃u g ) ，t 是活的： 定义2 在o o p n 的网系统s = ( d ，d ) 中， ( 1 ) 称行向量j 是网s 的一个p 一不变式或库所不变式，p y ，当且仅当 彳i r = 0 ： ( 2 ) 称行向量，是一个t 一不变式或变迁不变式，t 仃u g ) ，当且仅当 j a = 0 。 网系统s 中的p 一不变式意义为：p 一不变式向量，对应库所集合中的托肯数 在网系统中是不变的。 t 一不变式的意义为：发射一个t 一不变式对应的变迁序列，则产生一个重复 标识，即在当前的标识下，发射f 一不变式j 对应的变迁序列f = 岛乞0 则回到当 前标识。 ( 3 ) 称乃= l l j i if f ；jt 一不变式，的支撑，j i j i i = f 仃u g ) i 歹( f ) o ) ； ( 4 ) 称只= i i l l i 为p 一不变式，的支撑，i i l l i = p yf ( p ) o 。 定义3 在o o p n 的网系统s = p ，d ) 中， ( 1 ) 称一个非空集合日】，是一个信标，当且仅当臼日成立； ( 2 ) 称一个非空集合h y 是一个陷阱( t r a p ) ，当且仅当h 臼成立： ( 3 ) 称一个信标( 或陷阱) 是极小的，当且仅当不存在其它的信标( 或陷阱) 是 它的子集； ( 4 ) 若日】，是个信标，则称巧= h 为日的受控变迁集，毛= t u g 一巧 称为日的不受控变迁集。 山东大学硕士学位论文 | 量曼鼍量曼曼曼曼量| 量量曼曼曼舅量鼍曼曼罾曼曼罾曼皇| 曼量曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼暑曼皇量一 2 1 3 面向对象p e t r i 网的其它一些基本性质 性质1 j 是一个p 一不变式，则，的支撑既是一个信标也是一个陷阱， 在网系统中，j 中的托肯总数是不变的； 性质2 日是一个信标，则在网系统中信标一旦被清空就不再会有托肯： 性质3 日是一个陷阱，则其中的托肯数只能增加不会减少； 性质4 对于一般o o p n 系统，如果是标识m 是死的，则所有未被标记的库 所组成一个信标； 性质5 对于一般o o p n 系统，网系统死锁的必要条件是所有的极小信标都 被清空。 2 2 面向对象p e t r i 网的示例 用o o p n 描述的系统中，各元素的图示表示如图2 一l 所示。 o 库所流关系弧 变迁托肯消息接口门 图2 1o o p n 元素的图形表示 厂 - 对象 为了说明说明节点的前集、后集，网的关联矩阵，信标，p 一不变式，f 一不 变式等概念，以图2 - 2 为侈f j ，给出一个包括三个对象子网q 、d 2 、d 3 的o o p n 模型，并以对象子网d 2 来说明相关概念。 ( 1 ) 关联矩阵。设行向量对应为【p ：。) 2 2p ：，p 2 4o m l 2 。】，列向量对应为 【乞。乞乞，幺r ，则其关联矩阵为； a = 一1 0 11 10 0 1 o一1 00 00l 一1o一1 l oo 011 一l1o l一1l ( 2 ) 前集、后集。p 2 l 、p 2 2 、如、p 2 4 、o m l 2 1 的前集为：p 2 1 = f 2 2 ) ，p 2 2 = 乞 ， 9 山东大学硕士学位论文 量舅舅置量曼量曼量曼曼曼皇曼曼量| 薯量曼曼曼曼量| 詈量皇量曼曼曼曼曼量量量皇量量喜量舅曼曼量曼量 p 趋= f 2 3 ，乞6 ，p 2 4 = t 2 4 ，t 2 5 ，o m l 2 l = 2 1 ；p 2 l 、p 2 2 、如、p 2 4 、o m l 2 l 的 后集为：p 2 。= f ：。，t 疋= 乞，t 2 5 ，p 乏= t 2 2 , t 2 ，) ，p 二= f 2 6 ) ，o a a ：, = t 2 2 ，t 2 4 。 ( 3 ) p 一不变式。由于+ p 2 1 + p 2 2 + 。p 2 3 + 2 p 2 4 + * o m i ：l = t 2 1 , t 复，t 2 a ，匕，t 2 5 ，t 2 6 ) ， 苡1 + 菇+ 以+ 2 p ：4 + o m i ；l = 乞1 ，乞，t 2 3 ，t 2 4 ，t 2 5 ，t 2 6 ) ，则，- - 1 1 11 2 】是一个 p 一不变式，4 i r = 0 。 ( 4 ) 信标、极小信标。又由p 2 l + 。p 2 3 + p 2 4 + * o m l 2 1 苡l + p 三3 + p 二+ o m i t l ， 所以 p ：，p 2 ，p 2 。，o m i ：。 是一个信 p 2 l ，p 2 2 ，p 2 3 ，o m l 2 1 )都是信标， 标同样 且 p 2 l ，p 2 3 ，p 2 4 ，o m l 2 1 ) p 2 l ，p 2 2 ，p ：3 ，o m l 2 l 都是极小信标。 仍1 ，如，p 2 4 ，o m 2 l 和 、 耽l ，玩，助，o m l 2 l 、 ( 5 ) f 一不变式。同理，分析变迁的前集和后集得，= 【0 1101 1 】， j 2 = 【l 1 010 1 】是f 一不变式，且是极小t 一不变式，a = 0 ，j 2 a = 0 。 2 3 小结 图2 - 2 一个面向对象p e t r i 网模型 本章给出了面向对象p e t r i 网的定义和性质，并用一个示例进行了说明。 1 0 山东大学硕士学位论文 量量曼鲁量曼曼曼量| 曼曼曼曼曼曼曼曼曼曼曼曼皇皇量曼曼曼曼曼曼暑曼曼舅舅量| 量量曼曼曼曼曼曼曼曼曼曼曼曼量量量曼曼基罾量一 第三章分层方法和约简规则 在系统设计和开发过程中利用p e t r i 网进行死锁检测，其复杂性主要依赖于 系统状态的空间大小，状态空间爆炸是死锁检测所面临的主要问题。因此简化系 统模型、降低死锁分析复杂度是解决该问题的关键。为了有效地对系统进行死锁 检测，本章给出对象子网的分层方法和网系统的约简规则，并用例子说明。 3 1 对象子网分层的概念及方法 对于规模较大的系统，其面向对象p e t r i 网的模型就已经很大了，死锁的检 测变的很困难，为了有效地对面向对象p e t r i 网系统进行死锁检测，降低其分析 复杂度，本文提出了层次分析的思想，通过对对象子网的分层和层层对象子网的 分析，来简单化死锁的检测。 对象子网分层的方法是，把具有初始托肯的对象子网作为第一层；把第一层 内子网作为直接输入的对象子网分为第二层，此时第一层内相应子网称为第二层 子网的低层输入流关联网；把第二层子网作为直接输入的对象子网分为第三层， 此时，第二层以及第二层的低层输入流关联网统称为第三层的低层输入流关联 网；同理，依次划分下去，直到所有的对象子网都分层完毕。第一层为最低层， 依次为高层。如果对象子网的某直接输入子网层次比较高，则将其称为高层输入 流关联网。 以图3 1 为例，根据分层方法，因对象子网q 、d 3 具有初始托肯，所以为 第一层；因对象子网d 2 、q 的直接输入为子网d 1 ，d 5 的直接输入为子网q ， 所以0 2 、q 、d 5 为第二层对象子网，d 2 、d 4 的低层输入流关联网为第一层的 对象子网d 1 ，q 的低层输入流关联网为第一层的对象子网d 3 。 3 2 约简规则 为了有效地对面向对象p e t r i 网系统进行死锁检测，降低其分析复杂度，解 决状态空间爆炸等问题，本文给出了保持网系统死锁性质的约简规则，尽可能的 减少网系统中要分析的节点。此小节，给出六条保持死锁性质的约简规则，然后 山东大学硕士学位论文 量| 曼曼皇舅| 量曩曼皇皇邑蔓鲁舅舅置量曼舅曼曼置曼曼皇i i 曼皇曼曼曼曼曼量曼曼墨量量| 量皇量量 验证其适用性，并以一个示例说明约简规则应用。 d d 2 0 4 图3 - 1 一个面向对象p e t r i 网模型 3 2 1 约简规则描述 约简规则1 ：令节点p puq 。如果p 的前集和后集中均只有一个节点， 且p 的输入输出度均为1 ，后集中节点的输入度也为1 ，则将节点p 及其输入输 出流关系删除，并根据系统语义和点火规则【2 7 1 将p 中的托肯转移到相应节点， 同时将p 的前集和后集中的两个节点合并，并调整相应的流关系。形式化描述为： 对即puq ，若d i n ( p ) = d o u t ( p ) = 1 ，并且设掌p = f 1 ) 和p 木= t 2 ) ，d i n ( t o = 1 ， f 2 堆= p l ，p 2 ，岛) ， 则f = n t 2 ，( 岛) = n ( p 2 ) = = ( 以) = n ( p ) ， w = w - f l i n ( p ) 一f l o u t ( p ) ， f l i n ( t 3 = 厂w l t a i l ( f ) = f i ， ， f l o u t ( t ) = 厂wjh e a d ( f ) = t 2ut i ) ，r = r 一 p ，毛，t 2 ) + p 。 。 约简规则2 ：令节点f t u g 。如果t 的前集和后集中均只有一个节点，并 且t 的输入输出度均为1 ，前集中节点的输出度也为1 ，则将节点t 及其输入输出 流关系删除，并将t 的前集和后集中的两个节点合并，然后根据系统语义调整相 应的托肯和流关系。形式化描述为：对v t t u g ，若d i n ( t ) = d o u t ( t ) = l ，设 t = p l ，t 奎= p 2 ) ，且d o u t ( p 1 ) = l ，则p = p 。np ：，( p