（电路与系统专业论文）基于petri网的一类并发程序死锁预防策略.pdf

浙江大学硕士学位论文摘要 摘要 随着计算机技术的发展，多核计算机系统应用日益广泛，也使并发编程有了 更多的需求，p e t r i 网作为计算机科学中的重要形式模型，能有效地对并发程序 进行建模分析。 当前，基于p e t r i 网的并发程序的研究热点之一是死锁控制问题。死锁在并 发程序中的具体表现就是进程等待永不可能发生的事件而产生阻塞的状态。死锁 问题会造成程序的崩溃和系统开销上升，尤其是在实时系统中，死锁会造成严重 的后果。为解决系统的死锁问题，保证并发程序正常运行，死锁控制成为了一项 重要的研究内容。 本文首先研究了具有同步信号的并发程序，定义了p e t r i 网的一种子网s 3 p s ( 简单连续信号进程系统) 网对其建模分析，主要证明了s 3 p s 网活性的充分必 要条件是其严格极小虹吸非空，而活性是非死锁的充分条件，p e t r i 网满足活性 就不会死锁。并在此基础上，进行死锁预防控制策略的设计，即添加控制连接弧 使每个严格极小虹吸在s 3 p s 网运行时的每个状态都非空，使形成的受控网满足 活性，保证受控网不会死锁。 本文又进一步扩展了研究内容，在具有同步信号的并发程序中引入共享资源 分配系统，定义了s 3 p r s ( 简单连续资源与信号进程系统) 网，并根据其无信号 子网是这种网的无信号子网属于s 4 p r 网的特性，用s 4 p r 网的虹吸计算方法计 算s 3 p r s 网的无信号极小虹吸，在此基础上，提出计算含有信号库所的极小虹 吸计算方法，从而得到s 3 p r s 网的极小虹吸集合而后证明了s 3 p r s 网活性的 充分必要条件是其严格极小虹吸非空，并设计了迭代地加入控制库所控制其严格 极小虹吸非空的死锁预防策略，使最终的受控网满足活性，系统不会死锁。 关键- y - - ：p e t r i 网，并发程序，死锁预防，虹吸计算，s 3 p s 网，s 3 p r s 网 l l 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t a st h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , m u l t i c o r ec o m p u t e rs y s t e mi s b e c o m i n gv e r yc o m m o na n db r i n g sm u c hm o r en e e df o rc o n c u r r e n tp r o g r a m m i n g p e t r in e ti sai m p o r t a n tf o r m a lm o d e li nc o m p u t e rs c i e n c ea n dc a l le f f i c i e n t l ym o d e l a n da n a l y s ec o n c u r r e n tp r o g r a m a tp r e s e n t ，o n eo ft h eh o ti s s u e sa b o u tc o n c u r r e n tp r o g r a mi st h ed e a d l o c kc o n t r o l p r o b l e m d e a d l o c ki nc o n c u r r e n tp r o g r a mi sas t a t eo fs o m ep r o c e s s e sb e i n gb l o c k e d f o rw a i t i n gf o rt h ee v e n t sw i l ln e v e rb eg e n e r a t e d d e a d l o c kw i l lc a u s et h ep r o g r a m c r a s ha n di n c r e a s es y s t e mc o s t s ，e s p e c i a l l yi nr e a l - t i m es y s t e m , t h ed e a d l o c kw i l l c a u s es e r i o u sc o n s e q u e n c e s t os o l v ed e a d l o c k so ft h es y s t e ma n de n s u r et h en o r m a l o p e r a t i o no fc o n c u r r e n tp r o g r a m s ，d e a d l o c kc o n t r o lh a sb e c o m ea l li m p o r t a n tr e s e a r c h c o n t e n t s t h i sp a p e rf i r s ts t u d i e dt h ec o n c u r r e n tp r o g r a m s 诮t l ls y n c h r o n i z a t i o ns i g n a l s ， d e f i n e dap e t r in e ts u b n e t ss 3 p s ( s y s t e mo fs i m p l es e q u e n t i a lp r o c e s sw i t hs i g n a l s ) n e t t om o d e la n d a n a l y s i st h ep r o g r a m an e c e s s a r ya n ds u f f i c i e n tc o n d i t i o no fl i v e n e s so f m es p sn e tw h i c hi si t ss t r i c tm i n i m a ls i p h o n sb e i n gn o n e m p t yw a sp r o v e d w h i l e l i v e n e s si sas u f f i c i e n tc o n d i t i o nf o rd e a d l o c k - f r e e ，p e t r in e t ss a t i s f y i n gl i v e n e s sw i l l n o tg e n e r a t ed e a d l o c k o nt h i sb a s i s ，ad e a d l o c kp r e v e n t i o np o l o c yw a sd e s i g n e d ， w h i c hw a sa c h i e v e db ya d d i n gc o n t r o la r ct om a k ee v e r ys t r i c tm i n i m a ls i p h o nb e i n g n o n e m p t yi ne v e r yo p e r a t i o ns t a t eo ft l l es p sn e ta n dt oe n s u r et h ec o n t r o l e dn e t f o r m e db ya d d i n gc o n t r o la r cs a t i s f y i n gl i v e n e s sa n dd e a d l o c k - f r e e t h i sp a p e rf u r t h e re x t e n d e dt h er e s e a r c h ，i n t r o d u c e dt h es h a r e dr e s o u r c e a l l o c a t i o n s y s t e mi n c o n c u r r e n tp r o g r a m sw i t hs y n c h r o n i z a t i o ns i g n a l s ，d e f i n e d s 3 p r s ( s y s t e mo fs i m p l es e q u e n t i a lp r o c e s sw i t hr e s o u r c e sa n ds i g n a l s ) n e t b e c a u s e t h en o n s i g n a ls u b n e to fs s p r sn e tb e l o n g st os 4 p rn e t , t h es i p h o nc o m p u t i n g m e t h o do fs 4 p rn e tw a su s e dt oc o m p u t en o n - s i g n a ls i p h o n s ，o nt h i sb a s i s ，am i n i m a l s i p h o nc o m p u t i n gm e t h o do fs i p h o n sc o n t a i n i n gs i g n a l sw a sp r o p o s e d ，s ot h a tt h e m i n i m a ls i p h o ns e to fs s p r sn e tw a sf r e e d t h e nt h ep a p e rp r o v e dan e c e s s a r ya n d i l i 堂江奎学硕士学位论文 a b s t r a c t s u f f i c i e n tc o n d i t i o no fl i v e n e s so ft h es 3 p sn e tw h i c hi s i t ss t r i c tm i n i m a ls i p h o n b e i n gn o n e 呐，a n dd e s i g n e dad e a d l o c kp r e v e n t i o np o l o c yb yi t e r a t i v e l ya d d m g c o n t r o lp l a c et om a k et h es t r i c tm i n i m a ls i p h o n sb e i n gn o n - e m p t y ，e n s u r e dt h ef i n a l c o n t r o l l e dn e tf o r m e db y a d d i n gc o n t r o lp l a c es a t i s f y i n gl i v e n e s sa n dt h es y s t e m b e c o m i n gd e a d l o c k f r e e k e y w o r d s ：p e t r in e t s ，c o n c u r r e n tp r o g r a m ，d e a d l o c kp r e v e m i o n , s i p h o nc o m p u t a t i o n ， s 3 p sn e t s 3 p r sn e t i v 浙江大学硕士学位论文 致谢 致谢 首先诚挚地感谢我的导师董利达副教授，在两年半的硕士生涯中，正是在董 老师的悉心教导和帮助下，才使我得以一窥p e t r i 网领域的深奥，并取得现有的 成果。从研究方向的确定、论文的选题一直到学位论文的完成，董老师都倾注了 大量的时间和精力。董老师严谨的学术作风、求是创新的工作精神深深影响了我， 并将使我终身受益。两年多来，董老师不仅在学业上给予我精心的指导，在日常 生活等方面，同样给予我无微不至的关怀 感谢电路与系统研究所的所有老师和同学在我硕士生涯中的关心和帮助。 感谢实验室的程曦浩，郑寒，朴云，傅健丰，华苗苗和徐珊珊等师兄弟妹， 跟他们在一起学习生活的时光让我倍加珍惜和怀念。 感谢我的父母和家人，是他们一直鼓励我、支持我，使我能够不断地学习， 不断地进步，希望他们健康快乐。 本文的研究得到了国家自然科学资金( 6 0 5 0 3 0 2 7 ) 、浙江省科技厅项目 ( 2 0 0 7 c 2 1 g 2 0 1 0 1 4 2 ) 和国家8 6 3 重点项目( 2 0 0 6 a a 0 4 0 3 0 9 ) 等基金的资助， 在此同样深表谢意。 弋为 2 0 1 1 年5 月 浙江大学硕士学位论文 第一章绪论 第一章绪论 本章主要介绍计算机科学中的建模工具p e t r i 网及并发程序的p e t r i 网模型， 分析p e t r i 网作为其中一种建模工具的特点和优点，着重介绍基于p e t r i 网的死锁 控制和虹吸计算方法的发展情况，最后概述本文的章节组织安排。 1 1p e t r i 网及并发程序概述 p e t r i 网是c a r la d a mp e t r i 于1 9 6 2 年在博士论文“k o m m u n i k a t i o n m i t a u t o m a t e n ”( 用自动机通信) 中首先提出来的，由于可以建模系统运行中异步并 发的事件，p e t r i 网在计算机科学技术等相关领域都获得了广泛的应用。p e t r i 网 特别便于描述系统中进程的顺序、并发、冲突等系统特性，不仅可以刻画系统的 结构，还可以描述系统的动态行为，十分适用于对并发进程系统的建模分析。 并发程序是指一个包含两个或多个并发运行和共同工作执行任务的进程( 线 程) 的程序。利用并发程序，可提高计算机系统的工作效率，比如当一个进程在 等待用户输入时，另一个进程可以在后台执行计算任务在实际的多处理器硬件 系统中，很多问题都是并发的，用并发程序来解决显得十分必要。如在一个网络 服务器系统中，同时需要多个单独的进程来同时处理不同登入用户的请求。目前， 主要有j a v a 、a d a 等语言对并发程序进行编程 基于p e t r i 网的并发程序研究，一个方向是a d a 程序语言的p e t r i 网建模。a d a 是一种结构的，静态类型的，必要的，广谱的和面向对象的高级计算机编程语言， 来自p a s c a l 和其他语言的扩展 p y l e ，1 9 8 1 m u r a t a 在文献 m u r a t a , 1 9 8 9 a 中详细 阐述了由a d a 程序到p e t r i 网模型的转换方法的过程，并把这种类型的p e t r i 网称 为a d a 网，而且研究了a d a 网的安全性，守恒性。a d a 网的结构特点是进程是 状态机结构，进程间通过同步信号相连接文献 s t a n s i f e r , 19 9 0 ；g e d e l a , 19 9 9 ；f u ，2 0 0 4 ；b a r k a o u i ，19 9 8 ；c h e n g ，2 0 0 6 1 都是对a d a 网的 研究。在近年来，又出现了具有共享资源的并发程序的研究。w a n g 在文献 【w a n g ，2 0 0 9 a 中将进程间的互斥锁作为共享资源，把这种具有共享资源的并发程 序转换为一种p e t r i 网模型，定义为g a d a r a 网，研究了g a d a r a 网的活性和可回 浙江大学硕士学位论文 第一章绪论 复性。a d a 网的结构特点是进程是状态机结构，进程间通过共享资源结合在一起 文献 w a n g ，2 0 0 9 c 也是对g a d a r a 网的研究。 1 2p e t r i 网死锁控制研究现状 现有的基于p e t r i 网处理死锁的文献主要可以分为三类：死锁检测与恢复， 死锁避免，死锁预防其中死锁预防和死锁避免是近几年来国际上研究的热点问 题，其主要成果集中在柔性制造系统( f m s ) 方面，也有对于并发程序死锁的研 究成果。死锁检测与恢复可以允许死锁的发生，一旦死锁发生，就立即被检测到， 然后系统会通过资源的重分配使系统回到非死锁状态。目前对于f m s 的死锁检 测与恢复的研究有文献【w y s k l 9 9 1 ；k u m a r a n ，1 9 9 4 等，而在并发程序方面， m u r a t a 在文献 m u r a t a , 1 9 8 9 b 中分析了a d a 网中静态死锁的类型和检测的方法； b a r k a o u i 等在文献 b a r k a o u i ，1 9 9 8 】中用p e t r i 网的虹吸结构理论分析了一类a d a 程序死锁检测的方法，给出了几种满足活性和非死锁的网结构；c h e n g 在文献 c h e n g ，2 0 0 6 中针对a d a 网的同步等待死锁问题，提出了一种以任务等待图 ( t w f g ) 为基础的在线检测器，它能检测程序实时运行中的死锁。死锁避免是 在每个系统状态，通过一种在线的控制策略决定系统下一步状态的演化以避免死 锁的发生目前对于 f m s的死锁避免的研究有文献 【b a n a s z a k ，19 9 0 ；h s i e n ，19 9 4 ；p a r k ，2 0 01 ；e z p e l e t a , 2 0 0 2 ；e z p e l e t a , 2 0 0 4 】等，而在并发 程序方面，w a n g 在文献【w a n g ，2 0 0 9 b 】中将p e t r i 网监控器方法引入并发程序的 p e t r i 网模型的死锁控制中，通过动态的控制逻辑延缓进程对互斥锁的请求避免 死锁的发生，且这种死锁避免算法是最大容许的，只有当死锁要发生时才会延缓 对对互斥锁的请求；w a n g 在文献【w a n g ，2 0 0 9 c 中利用 w a n g ，2 0 0 9 a - - 文中给出的 g a r a d a 网保证活性的标识集所满足的约束条件，将上文的最大容许的死锁避免 算法应用到g a d a r a 网中，通过控制互斥锁资源的分配来避免死锁的发生。死锁 预防可以通过两种方法实现，一种是有效地系统设计，另一种通过离线算法设计 受控网，控制资源的分配以确保死锁不会发生。系统设计的死锁预防方法在f m s 方面的研究成果有文献【j e n g ，1 9 9 9 a ；x i e ，1 9 9 9 等，在并发程序方面的研究成果 有【l o r d , a c h e ，2 0 1 0 】等离线控制的死锁预防方法在并发编程方面的应用尚未见报 道，然而在f m s 领域，离线控制的死锁预防方法已经有着广泛的研究：e z p e l e t a 浙江大学硕士学位论文第一章绪论 在文献 e z p e l e t a , 1 9 9 5 】中提出一种简单连续资源进程系统( s3 p r ) 网结构，通过 加入控制库所和连接弧控制虹吸非空来预防死锁。t r i c a s 在文献【t r i c a s ，2 0 0 5 】中 针对s 3 p r 网的扩展结构简单连续共享资源系统( s 4 p r ) 网定义了坏虹吸的概念， 用迭代的方法设计死锁预防监控器控制坏虹吸非空来预防死锁。“在文献 【l i ，2 0 0 4 】中提出基本虹吸的概念，证明了在s 3 p r 网中只需控制基本虹吸非空就 可预防死锁，简化了s 3 p r 网的监控器设计，同时基于基本虹吸的死锁预防方法 同样适用于s 4 p r 网【l i ，2 0 0 9 a ，此外还有文献 h u a n g ，2 0 0 6 ；l i ，2 0 0 7 a ；l i ，2 0 0 8 a ； l l 2 0 0 9 b ；u z a m ，2 0 0 6 】等研究成果。相比较死锁避免，死锁预防直接从结构上预防 死锁的发生的可能性，具有简单直观且计算量小等优点，但只针对特定结构有效， 具有很大的结构局限性。 现有的死锁预防研究基本上都是基于虹吸结构，防止死锁的发生是通过控制 极小虹吸非空实现，在p e t r i 网中，虹吸是输入变迁属于输出变迁的库所集，它 与p e t r i 网的死锁和活性密切相关，是分析系统死锁的重要结构。在实际研究中， 死锁预防的前提是确定p e t r i 网的极小虹吸，因此，对极小虹吸计算方法的研究 成为了p e t r i 网死锁预防研究领域的一个重要工作。c h u 在文献【c h u , 1 9 9 7 】提出了 检测死锁的m i p 算法，得到给定标识下标识为空的极大虹吸，再从极大虹吸中 得到标识可空的极小虹吸b o e r 在文献 b o e r , 1 9 9 4 提出了标志矩阵方法，利用 标志关联矩阵计算出基础虹吸，p e t r i 网的所有虹吸都是基础虹吸的组合。j e n g 在文献 j e n g ，1 9 9 9 b 提出了一种基于对不同库所组合的深度优先算法的虹吸计算 方法，利用关联矩阵计算可以组成虹吸的极小库所集合，从而得到极小虹吸。l i 在文献【l i ，2 0 0 8 b 】针对s 3 p r 网提出了资源环的概念，利用资源环合并的方法寻 找严格极小虹吸。c h a o 在文献 c h a o ，2 0 0 7 提出了强连通资源子网( s c r s ) ，通 过计算直接对应基本虹吸和严格极小虹吸的s c r s 找到s 3 p r 网的基本虹吸和严 格极小虹吸w a n g 在文献 w a n g ，2 0 1 1 】针对扩展线性简单连续资源进程系统 ( e l s 3 p r ) 网定义了资源有向图，利用强连通的资源有向图子图得到严格极小虹吸。 c h a o 在文献 c h a o ，2 0 1 0 通过核心环的组合及库所的修补来计算简单连续多重资 源进程系统( s 3 p m r ) 网的严格极小虹吸。c a n o 在文献【c a n o ，2 0 1 0 】针对s 4 p r 网 定义了修剪图，利用修剪图对单资源极小虹吸进行组合与修剪得到所有极小虹吸。 在已有的虹吸计算方法中，m i p 算法，标识关联矩阵算法和深度优先算法计 浙江大学硕士学位论文 第一章绪论 算时间很长，不适用于大型网结构，而其它高效率的算法只适用于特定网结构， 如s3 p r ，s 3 p m r ，s 4 p r 等。 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 r i 网的定义和基本性质，同时介绍几种常见的、应用比较广泛的p e t r i 网子类及其 具备的特定性质； 第三章提出了一种新的p e t r i 网子类一一简单连续信号进程系统( s 3 p s ) 网， 这种网结构可看成一种a d a 程序的模型，分析了s 3 p s 网活性的充分必要条件条 件是它的严格极小虹吸非空，设计了死锁预防控制器：通过加入控制弧控制严格 极小虹吸非空，使网系统保持活性以确保死锁不会发生。 第四章提出了一种新的p e t r i 网子类一一简单连续资源与信号进程系统 ( s 3 p r s ) 网，这种网结构可看成s 3 p r 网的扩展结构，利用s 4 p r 网的虹吸计算 方法计算s 3 p r s 网的无信号极小虹吸，并定义了信号扩展虹吸和信号独立极小 虹吸，提出了利用已知无信号极小虹吸计算信号扩展极小虹吸的方法和利用信号 环计算信号独立极小虹吸的方法，从而得到所有极小虹吸的集合。 第五章分析了s 3 p r s 网活性的充分必要条件条件是它的严格极小虹吸非空， 定义了s 3 p r s 网的信号对称条件，设计了死锁预防控制器：通过连接弧修补得 到满足信号对称条件的s 3 p r s 网，而后对满足信号对称条件的网迭代的加入资 源型和信号型控制库所及其连接弧最终得到能保持活性的受控网系统，确保死锁 不会发生 第六章主要总结了本文研究的内容以及取得的成果，同时对可以进一步深化 研究的内容做了一些展望。 4 浙江大学硕士学位论文第二章p e t r i 网理论 第二章p e t r i 网基础理论 本章主要为之后几章的研究内容做一些基础理论铺垫，首先介绍一般 p e t r i 网的定义和基本性质，然后着重介绍了p e t r i 网的几种非常重要的子类， 包括其结构特点和具备的特定性质。 2 1p e t r i 网概念 p e t r i 网的概念是1 9 6 2 年由德国科学家c a r la d a mp e t r i 在他的博士论 文( ( 用自动机通信中首先提出来的。随后，对p e t r i 网的各种性质的研 究，以及把p e t r i 网应用于各种实际系统的建模和性质分析的论文和研究 报告开始大量涌出 吴哲辉，2 0 0 6 。从形式上看，一个p e t r i 网的网结构就 是一个没有孤立节点的有向二分图。 定义2 1 m u r a t a ，1 9 8 9 a 】：一个p e t r i 网可定义为一个5 元组： p n = ( p ，t ，f ，w ，m o ) ，其中： j p = p 1 ，一，p 。) 是一个有限库所( p l a c e ) 集； - t = ，厶) 是一个有限变迁( t r a n s i t i o n ) 集； - f 冬( p 乃u ( t d 是连接弧集； w ：f 寸 1 , 2 ，3 ，) 是权函数； - m o ：p 一 激发后的 标识为m ，坳p ，m ( p ) = m o ( p ) + d ( p ，t ) ，记为m o 【r ) m 。盯= t o o ，n 表 示变迁序列，满足扰。i t 。 ，z 1 【f l 。肌i t h m t ，即m o p m i 。在p e t r i 网n 中，用r ( n ，慨) 表示m o 的所有可达标识集。 定义2 2 ：给定一个p e t r i 网，中的路径是由库所和变迁作为节点 前后有向连接而成的，形式上可表示为： 6 浙江大学硕士学位论文 第二章p e t r i 网理论 厂= ( n , n 2 n 3 墩) ，k 1 且满足如下的条件： ( 1 ) 路径中的节点玎put ； ( 2 ) 如果f j ，则n j ； ( 3 ) 对所有的f l ，k 一1 ) ，吩和+ l 中一个是库所，另一个变迁； ( 4 ) 对所有的f 2 ，k - 1 ) ，吐。n 刀川 路径厂由库所和变迁连接而成，因此也可以看成是相关库所和变迁的 集合，用p 厂，t 厂分别表示属于路径厂的库所和变迁。称确为起始节 点，为起始节点。当玎，n 。p ，称厂为p p 路径。当n a = 时，则称该 路径为闭合路径，简称为环。 定义2 3 ：给定一个p e t r i 网n = ( 尸，l 一，ip i _ m ，lt | = n ，d 是的 关联矩阵： ( 1 ) 如果存在非零的r n 维整数向量y 满足d y = 0 ，则称】，是网的 一个p - 不变量。记l i y i i + = p ，ply ( - ) o ) 为p - 不变量】，的正支集， i i y i i = p ，p i 】，( ，) 0 ，则称】，是p 半流。如果y l 是网的一个p - 不变量， 且不存在其它p 不变量】，满足i i i ：1 1 怫0 ，则称h 是网n 的一个极小p 一不 变量。 ( 2 ) 如果存在非零的n 维整数向量x 满足d ，x = 0 ，则称x 是网 的一个t - 不变量。记l i x l l + = m tix ( f ) o 为t - 不变量x 的正支集， i i x l l = f ，tx ( f ) 0 ，则称x 是t - 半流。如果蜀是网的一个t - 不变量， 且不存在其它t - 不变量x 满足i i x l i i i x - 0 ，则称五是网n 的一个极小t 不变量。 浙江大学硕士学位论文第二章p e 仃i 网理论 给定一个p e t r i 网系统( n ，m 。) 。n 在标识，l r ( n ，聊。) 是死锁的当且仅 当1 ，t ：m t 。( n ，m o ) 称为非死锁的当且仅当v m r ( n ，m o ) ，3 t t ： m t 。如果v m r ( n ，m o ) ，都3 m r ( n ，m ) ，使得m i t ，则称变迁为活 的。如果每个t t 都是活的，则称( n ，m o ) 是活的网系统。 定义2 4 ：给定一个p e t r i 网n = ( 只l 即，给定s 呈p ，s f 2 j ，s 是 一个虹吸当且仅当。s s 一个虹吸是极小的当且仅当不存在的虹吸是 s 的子集。若一个极小虹吸不含的p 半流的支集，则称极小虹吸是严格 的。严格极小虹吸简记为s m s 。 定理2 1 a b d a u a h ，1 9 9 8 1 ：给定p e t r i 网= ( 只l d 的一个虹吸s 尸， 若存在p 一不变量m o i o ，且正支集+ gs ，则s 是不变量可控的，不 变量可控的虹吸标识不会为空。 2 2p 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 网子类： 2 2 1s 图 定义2 s l m u r a t a ，1 9 8 9 a 1 ：给定一个p e t r i 网，如果所有变迁的输入输出 库所集的个数都为1 ，则称为s 图( 状态机) ，或者说该p e t r i 网具有s 图 结构，即： i ti = i t | - 1 ， v t t 定义2 6 ：给定一个p e t r i 网n = ( p u p o ) ，丁，) ，是一个强连通s - 8 浙江大学硕士学位论文 第二章p e t r i 网理论 图，的每个环路都包含d o ： ( 1 ) 给定的一个环c 和c 的两个节点x , y 。称x 是y 在c 中的前向 当且仅当在c 中存在一条从x 到y 的长度大于1 和不含p o 的路径，这种情 况记为x cy 。x y 表示x cy 或x = y 。 ( 2 ) 给定的两个节点x , y 。称x 是y 在n 中的前向当且仅当存在路 径c ，有x cy ( x - cy ) ，这种情况记为x j y ( x y ) 。 ( 3 ) 给定的一个节点x 和一个节点集么( p u 乃。x 彳( x a ) 当且仅当存在节点y a ，有x | y ( x y ) ；a 0 ，m 。( p ；) 0 ，其他库所初始 标识为零。 图3 1 一个s s 网系统( ，朋。) s 3 p r s 网虹吸非空是非死锁的充分条件，但非死锁不能保证s 3 p r s 网所模拟的 系统能正常运行。因此我们需要研究s3 p r s 网满足活性时的结构条件，以便寻找 适当的方法保持网的活性，使s 3 p r s 网所模拟的系统能正常运行 定理2 ：s 3 p s 网属于n v + 网。 证明：由定义3 1 的s3 p s 网定义可知，s 3 p s 网存在两种类型的极小p 一半流 的支集：每个进程网，本身是一种类型的极小p 一半流的支集( 它的i 一子网如图 3 2 - a 所示) ；由于空闲库所与信号库所及工作库所产生新的环结构替代极小p - 半流支集，的环结构，得到含信号库所的一种类型的极小p 一半流支集( 它的i 一 子网如图3 2 - b 所示) ；信号库所与工作库所产生的环结构，形成另一种类型的 极小p 一半流支集( 它的i 一子网如图3 3 - c 所示) 从这三种极小p 一半流支集i 一 子网的结构可知，这三种类型的网都是s 一图，由定义2 13 知，均不含v f o s 结 构，因此，s 3 p s 的极小p 一半流支集的i 一子网不含v f o s 结构，由定义2 1 4 知s 3 p s 网属于n v + 网。 浙江大学硕士学位论文第三章s 3 p s 网死锁预防策略 0 p abc 图3 23 种类型的极小p - 半流支集的i 一子网 6 推论3 1 ：给定一个s 3 p s 网系统( ，m 。) ，( ，研。) 是活的当且仅当没有标识 可空的虹吸。 证明：由定理3 1 可知( ，_ i ，；口) 是n v + 网，则由定理2 2 可得( ，朋。) 是- gv o 当 且仅当没有标识可空的虹吸。 3 2s 3 p s 网的死锁预防策略设计 从前面的推论3 1 可知s p s 网系统保持活性的充分必要条件是网中的虹吸非 空，而从s3 p s 网系统的定义可知，网系统的虹吸在初始标识下并不都是非空， 因此要设计死锁预防策略，首先需使所有的虹吸的初始标识非空。 定义3 3 ：给定一个s 3 p s 网系统( n ，m o ) ，c 称为s 3 p s 网n 的分配初始标 识当且仅当： ( 1 ) 跏尸oup ，m o c ( p ) = m o ( p ) ； ( 2 ) 对于任意含信号库所的虹吸s ，若t o o ( s ) 0 ，则m o c ( s ) = 确( 研；若( $ = o ， 则取任一信号库所g s ，m o c ( 6 9 = ，( g ) = 1 ； 称( n ，m 。c ) 是标识分配网系统。 定义3 3 条件( 1 ) 表示在标识分配网系统中，空闲状态库所的标识与原网 1 4 浙江大学硕士学位论文第三章s 3 p s 网死锁预防策略 系统的标识相同，工作库所的标识等于o 。根据s 3 p s 网的结构，不合信号库所的 虹吸是每个进程网，的库所集，含有库所矗，初始标识大于0 ，因此定义3 3 条件( 2 ) 分配任意含信号库所的虹吸的初始标识大于0 ，就可使s 3 p s 网的所有 虹吸的初始标识非空。条件( 2 ) 将帕( 回= o 的虹吸s 的任一信号库所g 标识置1 ， 表示进程间互相等待的信号中有一个信号被初始化为就绪状态，使等待此信号输 出的进程处于信号就绪状态。如图3 3 中s 3 p s 网的一个虹吸s = 协，a 。，9 5 ，9 6 ) ， 若将g ，的初始标识置1 ，则进程3 处于信号就绪状态，若将g 。的初始标识置1 ， 则进程2 处于信号就绪状态。 定理3 2 ：给定一个s 3 p s 网系统( ，m o ) ，它的标识分配网系统为( n ，m o c ) ， 则( n ，m 。c ) 是一个s 3 p s 网系统。 证明：( ，坍o c ) 中网结构未变，还是s 3 p s 网。因为v p p ou p ， 小o c ( p ) = m o ( p ) ，所以跏p o ，聊o c ( p ) 0 ，印p ，m o c ( p ) = 0 ，1 7 o c 符合 定义3 2 条件( 2 ) 的要求，( n ，m o c ) 是一个s 3 p s 网系统 本章的死锁预防策略设计，就是要通过控制弧的添加，使旧网的所有虹吸满 足标识非空，并且满足产生的新网还是s 3 p s 网，且不会有新的可空虹吸，使最 终的网系统保持活性。 图3 1 所示的s 3 p s 网中的s = p o ，g 。，9 2 ，p 2 ，p ，) 是一个严格极小虹吸( s m s ) 。 此结构是一个含信号库所的环，它存在库所输出的分支结构，所以环中的库所集 不包含一个p 一半流的支集，是一个严格极小虹吸。s 3 p s 网的严格极小虹吸都是 这种类型的s 3 p s 网的严格极小虹吸( s m s ) 集合用1 - i 表示 定义3 4 ：给定一个s3 p s 网系统( n ，朋。) ，其中= 伊u p u p g ，l d ，m ( f 厶) 是的进程网，它的标识分配网系统为( ，m o c ) ，i i 是的s m s 集， ( n c ，m o c ) 称为( n ，肌。) 的受控网系统当且仅当： c = ( 尸ou p u 尼，t ，f u 疋) ， e = u 。只，其中 15 浙江大学硕士学位论文第三章s 3 p s 网死锁预防策略 b = u ，。i 。 ( ，g ) j ，s 苫，z ，3 t ( 。，) 。；g s ，3 t i g ；， ，f ” 定义3 4 的受控网系统对信号库所添加连接弧表示可以使进程间互相传输 的信号间每次都能完成消息的互相传递，不会有消息泄漏。 引理3 1 ：给定一个s3 p s 网系统( ，m 。) ，它的受控网系统为( c ，m o c ) ，对 任意控制弧( f ，g ) ，f z ，v t 。g ，t f ，有t jf ，且，f 。 证明：首先证明t j ，( 反证法) 设3 t g ，f f ，t | ， 则存在只含工 作库所的p - p 路径g ，g 起始节点为p 舭终止节点为p 并满足。a 1 = f ，肌l = r 7 根据定义3 4 ，：i t ( 。，) 。，m ，若，”= ，则b i = ，屁l = ，”，存在2 个 输入库所，这与m 是s 一图矛盾；若f ”f ，则存在只含工作库所的p - p 路径易， g 起始节点为b 2 ，终止节点为热2 ，并满足。b ：= ，p e 2 = ，由，是s 一图可 知，i t f l p = 1 ，因此路径g 和g 有同一终止节点p 。= p 。：。设( f ，g ) 是虹吸s 的 控制弧，因为f 。s ，有f s ，所以p 。l s ，x c 于- t | 口p f j 口。s ，必有c 1 的库 所p ，p = f j p ，p s ，以此类推，c 1 的起始库所p ，s ，因此f 。s ，与f s 。v s 矛盾。综上所述，可知f _ 。f 再证明f ，t ，( 反证法) 设设b t 。g ，t 毒f ，f ，t ，根据定义3 4 ， j ( f ) 。，mf ，则有f f f mt ，这与f ”( f ) 。矛盾，因此f ff 。 定理3 3 ：给定一个s 3 p s 网系统( n ，m 。) ，它的受控网系统为( c ，c ) ，则 ( c ，m o c ) 是一个s 3 p s 网系统。 证明：首先证明c 是s 3 p s 网。根据定义3 4 中受控网系统的定义，在c 中的进程网仍符合定义3 1 条件( 1 ) 的要求，且空闲库所，工作库所和变迁与原 网n 相比也未改变，满足定义3 1 的条件( 2 ) ；在n c 中若有输入控制弧的信号 库所g ，根据定义3 4 ，。g z ，对于g 的控制弧( f ，g ) ，t z ，根据引理3 1 ， v t 。g ，f r ，有t mt ，且f ，f ，则v f ，f g ，f ，f 且f ，f ，且g 的输出 1 6 浙江大学硕士学位论文第三章s 3 p s 网死锁预防策略 变迁没有改变，仍满足定义3 1 条件( 3 ) 中信号库所的定义，其它没有输入控制 弧的信号库所没有变化肯定满足定义3 1 条件( 3 ) ；因此c 是一个s 3 p s 网 再证明( c ，m 。c ) 是s 3 p s 网系统。受控网系统的初始标识与标识分配网系统 相同，根据定理3 2 ，( n c ，m 。c ) 仍是一个s 3 p s 网系统。 引理3 2 ：给定一个p e t r i 网系统( ，m 。) ，其中n = ( p ，t ，f ) ，它的虹吸集 为n 。在( n ，m 。) 中添加连接弧( f ，p ) ，t t ，p p ，则产生的网系统( ，m o ) 的虹吸集n 2sn l 。 证明：( 反证法) 设在( ，m o ) 中，3 s h 2 ，在( ，m o ) 中有s 仨n 。不妨设 在( ，聊o ) 中。s = 口l ，s 。= 届， c 届，而在( ，t o o ) 中s = 口2 ，s = 历， 口2 垡局 1 ) 若p s ，则f 口1 ，口2 口l ，屈= 历，因为口l 届，所以口2 量岛， 与假设的a 2g 屈矛盾。 2 ) 若p 芒s ，则口1 = 口2 ，a = 局，因为口1c 届，所以口2 冬岛，与假设的