（机械电子工程专业论文）基于mip算法的系统petri网模型中的死锁预防.pdf

摘要 自然世界及工程实际中的许多现象都可以归结为离散事件动态系统( d e d s ) ，这些 系统无一例外的要求具有无阻塞性，及系统运行无死锁。科学界针对这一问题提 出了许多先进的控制理论及方法，其中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 网模型具有最多的可达状态，这在实际中，意味着系统具有更大 的灵活性。但是上述理论虽然只需要控制基本信标即可以控制整个系统，但是由 于从属信标满足一定的可控性条件才能完全受控，这意味着在控制算法的生成过 程中所有的信标都要参与。从而大大增加了系统控制的复杂性。本文在基本信标 理论基础上，提出了一种基于m i p 算法的死锁预防策略，该策略指出了一种思路， 可以控制基本信标，而后利用m i p 算法给出的系统无死锁条件作为目标函数，可 以在多项式时间内计算出使得所有的从属信标受控系统需满足的条件，从而使得 整个系统的控制策略更加可行。 关键词：p e t r i 网；基本信标；死锁预防 a b s t r a c t m a n yp h e n o m e n a i nt h en a t u r ea n d e n g i n e e r i n gf i e l d sc a nb ev i e w e da sd i s c r e t ee v e n t d y n a m i cs y s t e m s ，w h e r e d e a d l o c k f r e e d o mi so n eo ft h e i m p o r t a n tp r o p e r t i e s ， a d v a n c e dc o n t r o lt h e o r ya n dh a e t h o d sh a v eb e e np r o p o s e db ys c i e n t i s t sa n d e n g i n e e r s i nt h ef i e l d s a m o n gt h e m ，p c t r in e t sa r ef l w i d e l yu s e da n dv e r ys u i t a b l em a t h e m a t i c a l t o o l sf o rs u c hs y s t e m sb e c a u s et h e i r d i s c r e t e n e s s ，c o n c u r r e n c e ，a n ds c h o l a s t i c n e s s n e a r l ya l lt r a d i t i o n a ld e a d l o c kp r e v e n t i o np o l i c i e sb a s e do np e t r in e t sc o m ef r o ms u c ha p o i n tt h a tc o n t r o l s a l ls t r i c tm i n i m a l s i p h o n s i nan e ts u c ht h a tt h en e t s y s t e m i s c o n t r o l l e dt ob e d e a d l o c k - f r e e h o w e v e r , t h e s ep o l i c i e sh a v eb e e np r o v e d t ob e u n f e a s i b l es i n c et h en u m b e ro fs t r i c tm i n i m a l s i p h o n s i nt h en e ti n c r e a s e s e x p o n e n t i o n a l l yw i t ht h es i z eo f t h en e t f o rt h i s ，an o v e ld e a d l o c kp r e v e n t i o np o l i c y b a s e do ne l e m e n t a r ys i p h o n si nan e ti s p r e s e n t e d a c c o r d i n gt ot h i sp o l i c y , n o ta l l s i p h o n si nt h en e ta r en e e d e dt ob ee x p l i c i t l yc o n t r o l l e de x c e p tt h es i p h o n sn a m e db y e l e m e n t a r yo n e sb e c a u s ei t h a sb e e np r o v e dt h a ta l ls t r i c tm i n i m a ls i p h o n sc a nb e c o n t r o l l e dt ob em a r k e dw h e no n l yt h ee l e m e n t a r yo n e sa r ec o n t r o l l e d d i f f e r e n tf r o m t h ec a s eo fs t r i c tm i n i m a ls i p h o n si nan e ts y s t e m ，t h en u m b e ro f e l e m e n t a r yo n e si s b o u n d e db yt h es m a l l e ro fp l a c ec o u n ta n dt r a n s i t i o nc o u n t b a s e do nt h ei d e a s m e n t i o n e da b o v e ，t h i st h e s i sp r o v e st h a tt h es e to fe l e m e n t a r ys i p h o n si sn o tu n i q u e ， w h i l ed i f f e r e n to n e sm a yl e a dt od i f f e r e n tc o n t r o lr e s u l t s a sar e s u l t ，t h ec o n c e p to fa n o p t i m a ls e to fe l e m e n t a r ys i p h o n si sp r o p o s e da n da l s ot h ea l g o r i t h mw h i c hc a nb e f i n i s h e di np o l y n o m i a lt i m et of i n ds u c has e t w i t ht h es e to fo p t i m a le l e m e n t a r y s i p h o n s ，n e ts u p e r v i s o r sc a l lg e n e r a l l yp r o d u c em a x i m a l r e a c h a b l es t a t e s 。a l s oi nt h i s t h e s i s ，ad e a d l o c kp r e v e n t i o np o l i c yb a s e do nm i p i si l l u s t r a t e db yt h i sa l g o r i t h m ，w h e r e a l l s i p h o n si nt h en e td o e sn o tn e e dt ob ef o u n dd u r i n gt h eg e n e r a t i o no f t h ec o n t r o l p o l i c y t h i sm a k e s t h e p o l i c y b a s e do ne l e m e n t a r ys i p h o n sm o r ef e a s i b l e k e y w o r d s ：p e t dn e t ；e l e m e n t a r ys i p h o n s ；d e a d l o c kp r e v e n t i o n 创新性声明 5 1 6 9 5 5 4 6 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证 毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 导师 笫一章绪论 第一章绪论 1 1 研究背景与意义 1 9 6 2 年，c a r la d a mp e t r i 先生在他的博士论文用自动机通信中，首次提出了 p e t r i 网的概念。之后的4 0 年里，p e m 网引起世界上许多科学家与工程师的研究热 情，其应用范围也随之扩展到通信以外的许多领域。这是由于p e t f i 网在描述系统 并发性及随机性方面的具有一般性。目前，p e t r i 网最为成功的应用领域当数系统 性能的评估与通信网络协议的分析。同时，自信息革命开始以来，p e t r i 网在许多 新兴的研究领域具有广泛的应用前景，如分布式软件系统的建模与分析，分布式 数据库系统，并行程序系统，柔性制造系统，工业控制系统，离散事件系统，多 处理器存储系统，容错系统，可编程逻辑阵列系统，编译及操作系统等等。不难 看出，p e t r i 网涉足的各个领域均与并发性及随机性见长，而理论及实践表明在此 类系统中，死锁是一个普遍存在的问题。因而，系统p e 砸网模型中的死锁控制问 题就受到许多学者的关注，许多方法及策略相继提出。具体说来，主要有以下三 种思路。 1 死锁避免 死锁避免通过不断的搜索系统的可达状态来取得死锁控制的目的。根据该算法 系统每运行一步，即由控制系统判断系统选择可达图的何种分枝不会导致死锁， 并沿该分支继续运行下去，反之，则不选择该分支，从而达到死锁避免的效果， 1 1 2 1 1 】【硎中即采用了该控制算法。死锁避免算法的优点在于系统可以具有最大许可 的控制效果，也就是说除了危险节点及死锁节点外，受控系统保留了全部的好的 状态，在实际的并发系统中，这意味着系统运行效率得到了最大程度的保留。但 是，死锁避免算法也具有必须事先计算系统的可达状态图的缺点。而在p e 硒网系 统中，系统的可达状态具有爆炸性的特点，也就是说。其可达状态数随网规模的 增大呈指数级的增长趋势。这使得即使在一些中等规模的网系统中，该算法的实 现都是极其不现实的。 2 死锁恢复 死锁恢复汲取了死锁避免算法的不足，该算法的实现不霈要事先得到系统的可达 状态图，系统可以p e 啊网的变迁发射机制任意运行，一旦发生死锁，控制系统采 用恢复策略，使得系统得以退出死锁状态，正常运行。死锁恢复算法具有不需要 计算系统的可达状态图的优点，同时也可以取得与其相媲美的受控系统运行效率， 但是，却也面临如何找到理想的死锁恢复算法这一现实问题。 3 死锁预防 死锁预防策略 l j 【2 】【3 】【4 】【5 】【6 l 【7 l 【8 i n 1 0 】【1 1 1 1 4 胪】【16 1 【1 7 】【2 】【2 2 粕l 是基于信标理论的一种死 基_ rm i p 算法的系统p e t r i 网模型中的死锁预防 锁控制思想。根据该思想，死锁是出于系统中的信标被清空而引起的，只要控制 该系统中的所有的严格极小信标使之不被清空则该网系统就不会出现死锁。为此， 如何控制系统中的严格极小信标使之不被清空成为人们关注的焦点，w 。m w o n h a m 提出的控制库所的方法给人们提供了一种思路。根据该思想，只要给系统 可被清空的严格极小信标添加适当的控制库所，使之与该极小信标构成不变式即 可保证该信标不被清空。然而不幸的是，即使控制了网系统中所有的严格极小信 标使之不被清空，仍不能确保新的网系统不会出现死锁，这是因为新添加的控制 库所之间有可能有构成了新的可被清空的严格极小信标，从而需要一个迭代算法。 p j 中，e z p e l e t a 提出的针对s 3 p r 网系统的死锁预防策略指出，对于某种特殊结构 的网系统，通过某种策略是可以通过一次添加控制库所使其实现无死锁的。死锁 预防算法具有不需要计算系统的可达状态的优点，但是其缺点也是十分明显的， 首先，通过添加控制库所。危险的尤其是死锁节点去除的同时，一部分好的节点 也会被去除，从而使得目标网系统的运行效率受到影响。其次，由于在网系统中， 严格极小信标的个数也是与网规模的大小成指数关系增加的，从而使得控制器的 设计变的复杂，甚至难以实现。本文着重于从死锁预防这一角度出发探讨系统中 的死锁预防问题，主要致力于完成基于基本信标的f m s 中的死锁预防策略的基础 性理论研究。论证控制任意一组基本信标即可使得整个系统受控的思想，研究基 本信标的个数不超过系统对应的库所或变迁的个数这一事实，从而使得死锁预防 所要添加的控制库所的个数大大减少。提出求解基本信标的算法，进而推演出基 于i d i p 算法及基本信标理论的柔性制造系统死锁预防策略。 1 2 本文完成的主要工作 本文的工作主要在以下几个方面展开： 1 研究基本信标的定义，概念以及重要性质。 a 探讨基本信标的不唯一性问题。 b 找出基本信标的个数与网规模的大小之间的关系。 2 设计寻找最优基本信标的方法，使得当该组基本信标受控时，网系统具有相 对最多的可达状态。 a 寻找一组基本信标，使其含有最少的令牌数。 b 寻找一组基本信标i 使得非基本信标全部为强从属信标： 4 设计一种控制算法，使得控制库所及其连接弧的添加可以在多项式时间内完 成。 f t 基于m i p 算法的p e t f i 网的活性检验 b 刑用m i p 算法，使得控制库所及其连接弧的添加可以自动完成。 c 在a 的基础上，进一步利用m i p 算法调整控制库所输出弧的指向使得受控网 系统具有相对最多的可达状态。 第二章p e t r i 网理论 第二章p e t r i 网理论 2 1 基本定义 【定义2 1 】库所变迁网( 简称尸r 网) 是一个四元组，n = ( 尸，t ，f ，聊，其中p 代表库所的集合，f 代表变迁的集合，并且p 和歹是有限非空和不相交的集合； f c _ c p 乃u ( 戤d 称为有向弧集；附n m o ) 称为，中弧上的权，肛 0 ，l ，2 ) 。 称n = ( p ，t ，f ，r e ) 为普通网( o r d i n a r yn e t ) ，当且仅当vf e f ，玎，仂= 1 。对于普通 网可以记做n = ( p ，t ，d 。v p e 尸，v t e t ，如果p ，t ) e f ，且氓p ，0 = 1 ，则称 为普通尸，r 网( 川t o r d i n a r y n e t ) 。一个普通网肯定是一个普通p ，7 网。当3 f = p ，0e f , 啪 l 时，称n = ( p ，t ，f ，聊为一般网( g e n e r a l n e t ) 。 【定义2 2 】令n = ( p ，lf ，即是一个p e t r i 网，节点x p u t 的前鼍集定义为 f 抄p u r i x ) e 毋。其后置集定义为，= 沙e 州o ，y ) e f 。节点的集合e r 的前置集( 后置集) 定义为h = u x 。片? x ( 矿= 。抖，) 。 【定义2 3 】如果n = 护， 机( s t a t em a c h i n e ) 。 【定义2 4 】如果= 标识i 琴l ( m a r k e dg r a p h ) 。 r ，f ，聊是普通网，且vt e t ，| t l = l t l = l ，则称是状态 nf ，叼是普通网，并且有v p 尸，i p l = 妇。卜1 ，则称n 是 【定义2 5 】如果一个p e t r i 网系统( ，m o ) 的任意一个节点和其它节点中的任意一 个之间总存在条连接路径则称该网是强连通的。 【定义2 6 】如果一个p e t r i 网系统( ，m o ) 既是一个状态机又是强连通的，则称其为 强连通的状态机。 【定义2 7 】网n = ( p ，t ，f ，聊称为纯的，当且仅当_ 1 弓o ，”e ( p x d u ( a 即：o ， 力e f o p , x ) e f 非纯网可以在保持动态性质不变的情况下化为纯网。下面要讨论的网都是纯 网。 【定义2 8 】令= c p ，t ，f ，聊是个网。 l 、的标识是映射肘：p 一； 2 ) 一个变迁t e t 在竹下称为使能的，记为m o ，当且仅当坳唁，：m p ) 阡q ，f ) ； 3 ) 若柳，) 成立，则，发射后，产生另一新标识肘谴为m f 膳，有 基于m i p 算法的系统p e t r i 网模拟中的多e 锁预防 m ( p ) = 肘( p ) 一( p , t ) 肘( p ) + w ( p , t ) m ( p ) 一( p , t ) + ( ，) m ( p ) 4 ) 网n 从标识慨开始的所有可达标识的集合记为月( ，m o ) 或 如【) 。它是一个 最小集，即慨尺( ，n o ) ，m e 且( ，m o ) a m 【，) m 划r ( n ，m o ) ； 5 ) 当t i ，t 2 ，t n 丁时，0 - = t t t 2 “称为出现序列，当且仅当存在标识m o ，m l i ， 满足m o 【tz ) 阶溉； 6 ) 对于网和标识m o ，( ，m o ) 称为一个网系统： 7 ) 网n = c 尸。t ，f ，叻的关联矩阵定义为以尸j f 丁为序标的矩阵【i v 】：p z o z ，z 是整数的集合，且 【】( p , t ) = 一矿( p , t ) 彤( p ) 一( p , t ) + ( p ) o p 小 p t 7 t p e t i t 其它 【定义2 9 】令n - - ( p ，t ，f ，叻是一个网，m o 是的一个标识 1 ) 一个变迁，在标识m o 下是活的，当且仅当v m er ( n ，m o ) ，j ”r ( ，肘o ) ： m f f ) 成立； 2 ) ( ，m o ) 是死锁的，当且仅当，3 t t ：m oi ，) 成立： 3 ) ( n ，m o ) 是无死锁( 弱活) 的，当且仅当v 膨r ( n ，1 t l o ) ，3 t t ：m 【，) 成立； 4 ) ( ，m o ) 是活的，当且仅当v t e t ：t 在标识m o 下是活的； 5 ) ( m o ) 是有界的，当且仅当j 拓m 0 ，v 肘毫r ( n ，m o ) ，v p p ：肘p ) 敛； 6 ) ( ，m o ) 是结构有界的，当且仅当对于任意的有限的初始标识，它都是有界的； 值得说明的是，对于资源有限的实际系统而言，它的p e t r i 网模型一般都是结 构有界的。所有元素均为0 ( 1 ) 的列向量记为0 ( 1 ) 。 【定义2 1 0 令= ( p ，t ，f 。聊是一个网。 1 ) 以p 为序标的列向量v ：p - - ) z 称为的p - 向量。 2 ) 以r 为序标的列向量，：z 兮z 称为的几向量。 3 ) 称只向量j 是一个p 不变式f 库所不变式1 当且仅当i 0 且，o n l = 0 7 。 i 田l - p p 咎酗) o 称为j 的支撑。 4 ) 称一个p - 不变式是极小的当且仅当它的支撑中不包含任何其它尸不变式的支 撑。本文中的p 不变式，如果没有特别声明，则都是极小p - 不变式。 5 ) 称t - 向量，是一个口不变式( 变迁不变式) 当且仅当脚且i n 户0 。 i i j l l = t 1 j ( o # o 称为，的支撑。 扩”n 砷州砷舵 第二章p e t r i 网理论 6 ) 称是被p 不变式x ( t - 不变式力覆盖的当且仅当v p e p ：l ( p ) * o ( v t e t ：以0 o ) 。 被p 不变式覆盖的的网也称为是保守的。 【定义2 。l l 】( a ，m o ) 是一个网系统，= ( 尸，t ，f ，叨。 1 ) 称一个非空集合s o p 是个信标( s i p h o n ) ，当且仅当留- r 成立： 2 ) 称一个非空集合s c p 是一个陷阱( t r a p ) ，当且仅当苫9 成立； 3 ) 称一个信标( 陷阱) 是极小的，当且仅当不存在其它信标( 陷阱) 是它的真子集； 4 ) 称p e p 是被标识m 标记的，当且仅当肘p ) o 。称一个集合踺p 是被标识肘 标记的，当且仅当s 中至少有一个元素被肘标记。s 中的令牌数肘( $ = e e 以妇) ： 5 ) 不包含任何p 一不变式支撑的信标称为严格信标。一个严格信标有可能被清空； 6 ) 一个既是极小又是严格的信标，称为严格极小信标( s m s ) 。 2 2 基本性质 【性质2 1 】网系统( m o ) ，i 是v = ( 尸。lf ，聊的一个卫不变式，v m e r ( n , 胁) ： 亡砖薯m a 。 【性质2 2 1 网系统( g o ) ，是n = ( p ，t ，f ，叻的一个弘不变式，i 州中所有 的变迁发射一次，可能会使网系统回到初始标识。 【性质2 3 】网系统( m o ) ，n 鼍尸，nf ，叼，s _ c p 是一个信标，若3 m e r ( n , 朋r o ) ： 心固= o ，则s 以后永远不会被标记，称为被清空。 【性质2 4 】网系统( ，g o ) ，= ( 尸。nf ，聊，s 基尸是个陷阱，若3 m e r ( n , m o ) ， 嬲s ) 0 ，则s 以后总是被标记。 【性质2 5 】网= ( p ，t ，f ，聊的p 不变式f 的支撑i ，6 既是一个信标又是一个 陷阱。 【性质2 6 】( ，m o ) 是一个网系统，其中 ，一沪，瓦只叻，j 是一个严不变式，s _ c - p 是 的一个信标，那么此信标s 是在矗如下被p 不变式j 控制的，当且仅当，m o o 且 对于所有的p 尸峪，喇蜘成立，或等同地，f m o o 且伽e g g ( p ) o _ c s 。如果s 是 一个在m o 下被p 不变式j r 控制的信标，则s 不可能被清空，也就是说，v m e r ( n , 蚴： s 在标识m o 下是被标记的。 【性质2 7 】( ，m o ) 是一个普通网系统， ，_ c p ，t 毋，若在肘下是死( 锁) 的，则 所有未被标记的库所形成一个信标；如果网中没有信标可能被清空，则称( ， m o ) 是无死锁的( d e a d l o c k - f r e e ) 。 【性质2 8 1 对于普通网系统( ， 旬， ，= ( p ，td ，死锁的必要条件是所有的极小信 标都被清空： 该性质是一般死锁分析方法的基础。需要说明的是。本中主要讨论普通有界 6 基tm i p 算法的系统p e t r i 网模型中的死锁预防 网。除非特别说明，下文提到的网模型是普通有界网。 第三章基于p e t r i 网的系统建棋与分析 第三章基于p e t r i 网的系统建模与分析 3 1 基于p e t r i 网的系统建模 图3 1 ，3 2 用一个我们常见的化学反应式2 h 2 + 0 2 = 2 h 2 0 演示了p e t r i 网的基本运行 规则，图3 1 表示在该时刻有两个h 2 和两个0 2 ，图3 2 表示t 发射后的系统状态。 对比3 1 ，3 2 可知两个h 2 和两个0 2 合成两个水分子h 2 0 。 如 图3 1 发射前 图3 2 发射后 下面以几个例子演示p e t r i 网模型在各个领域的应用。 1 通信协议 图3 3 用p e t r i 网描述了一个简单的通信系统，处理器1 用于发送信息，并接收 应答信息。处理器2 用于接收信息，并发送应答信息。通过对该网模型的分析 可以全面评估该通信协议。 图3 3 一个简单的通信系统 基于m i p 算法的系统p e t r i 网模型中的死锁预防 2 形式语言 图3 4 描述了一个简单的词法分析器，该系统可用来产生a b “c “( n o ) 。 s t a t t 图3 4 。一个简单的词法法分析器 f i n a l p l a c e 3 柔性制造系统 图3 5 用p e t r i 网描述了一个简单的柔性制造系统，该系统包含两个进程，分别 为p l p 2 一p 3 巾4 ，p l1 - p 1 0 - p 9 - p 8 ，三个加工工具p 5 ，p 6 ，p 7 ，每次可以加工一个工 件。 图3 5 一个柔性制造系统 3 2 基于p e t r i 网的系统分析 根据系统的物理含义建立起其p e t d 网模型之后，就可以根据网论的理论对该网进 行分析，一般来说分析方法有如下三种。 1 覆盖树 给定一个网系统( n ，m o ) ，从初始标示m o 开始，随着各个变迁的相继发射，可以产 生与变迁个数相同的新的标示，从各个新的标示开始，又可以得到更多的新的标 示。这样一个过程可以产生一个标示树，其根节点是m o ，该树一般称为覆盖树。 覆盖树完全描述了系统的行为特性，但是由于系统的覆盖树具有爆炸性的特点， 对于规模稍大的网系统，覆盖树方法就不实用了。 2 状态转移方程 第三章基于p e t r i 网的系统建模与分析 在工程中，系统的动念行为特性往往可以用差分方程或者微分方程来描述，类似 的，在p e t r i 网中，系统的行为特性可以用状态转移方程来描述。使用状态转移方 程可以避免生成系统的可达状态，但是遗憾的是由于系统的状态转移方程与系统 的动态行为之间具有不完全对应性，使得状念转移法只能应用于部分网的子类。 3 缩减技术 缩减技术是为了便于分析规模较大的网系统而采用的一种技术，应用该技术可以 达到缩减网系统的规模但同时却保留系统的部分行为特性，如活性，有界性等。 1 0 基于m i p 算法的系统p e t r i 网模型中的死锁预防 第四章常用p e t r i 网网络模型 本章介绍几种常用的p e t r i 网模型，s 3 p r ，e s 3 p r ，r c n 及其行为特性f 3 】【7 m 】，本文 中的控制策略将更多的以此类网模型为控制对象。 4 1s 3 p r 网 【定义4 1 1 - 个简单加工进程( s i m p l es e q u e n t i a l p r o c e s s ) s 2 p 是一个p e t r i 网n = ( p u 矿) ，ld ， 而是n 的初始标识，p o 称为闲置库所( 加工进程的丌始和结束工序状 态) ，p e p 称为工序状态库所。( m o ) 满足以下条件： ( 1 ) 辟中，p o 崔只慨秽) 1 ，v p e p ，m o ( p ) = 0 ； ( 2 ) 是一个强连通的状态机，p , j v t e7 = | t l = l t i = 1 ； ( 3 ) 的每一个回路包含矿。 图4 1 两个s 2 p 【定义4 2 1 一个拥有资源的简单加工进程( s 2 pw i t hr e s o u r c e s ) s 2 p r 是一个网 _ 啦，u 矿 w p r ，瓦毋，肘j 是的初始标识。( ，朋；) 满足以下条件：( 1 ) 令p o = p o ， 由x = u 矿 u t 生成的子网尸c p 肫z k 黝是一个s 2 p ，其中p a = p u 矿) ，t x = t , f m ( p 私z 曲；( 2 ) r e p r 称为资源，环是资源的集合，聃西，( p u 秽) ) 广、p 萨o ；( 3 ) 印e 只v t e p ，v f e p 。，9 r p e p r ，t c u t n = t ”n 尸萨 ) ；( 4 ) v r e p r ，m o ( r ) l ；v re p r ， ”r 1 p = r r - t p o ；v r e p n ，r n ，= m ；( 5 ) “( 矿) n 忙c 幽”n p r = m ；( 6 ) 对于一个给定的 r e p r , 月= ( 广巾称为资源r 的持有者集合。对予一个资源集合9 1 = r l ，r 2 ，r 。) ， 用w h ( r ) l r e g = i 或l ) r e 仉域，) 表示嘶i ) u h ( r 2 ) l ) u 4 ( r m ) 。 第五章p e t r i 网中的基本信标 图4 2 两个s 2 p r 【定义4 3 】一个拥有资源的简单加工进程系统( s y s t e mo f s 2 p r ) s 3 p r 是：k ( k e l n 0 ) 个s 2 p r 通过共享资源复合而成的p e t r i 网n = o f l * n u ( p u p o u p r ，ld 。记n k = f l ， 2 ，k ) 。s 3 p r 网系统( ，m 0 满足以下条件： ( 1 ) 一个s 2 p r 也是一个特殊的s 3 p r ； ( 2 ) v e m ，w 似 f ，( p n p o i ) n ( 只p 劬，且存在如| n p 旷p c 萨中，聊弓= m ； ( 3 ) p = u 产i 巾 p o = u 卢l 七p o bp n = u l t j ；7 生u 忙i 乃? f = u - 1 0 i ； ( 4 ) v i e m ，跏e p u p o ，m o ( p ) = m o l ( p ) ；v i e m ，凡 p c 帅( r ) = m o ，；v r e j p c f ， m o ( r ) 2 m 甜( 如l ( r ) ，m o k ( o ； ( 5 ) 符号再表示组成第i 个s 2 p r 网i 的s 2 p 。 图4 3 一个s 3 p r 【定义4 4 】设一个s 3 p r 网系统( m m o ) ，其中_ ( j p u p o u n ，t d ，s 是网的 一个信标。品表示信标s 中的资源，s 盱翳，、p r ：昂表示信标s 中的工序状态库所， s p = s c 、p 。明显地，s = - s r w s p 。 4 2 r c n 合并网 【定义4 5 】设( n ，m o ) = ( p t ，f ，m o ) 为一个强连通的状态机，如果在n 中存在且仅 存在一个资源库所p , e p , 并且m 0 | ) 0 。则称n 为r c n 网，称其他的库所为操作 2 基tm i p 算法的系统p e t r l 网模型中的死锁预防 库所。 【定义4 6 1 设g 为一个p e t r i 网，如果v p p 。的输入变迁和输出变迁都是l 的子 集，则称g a = ( p 。，t 。，f 。，m 。o ) 为g 的一个变迁子网。 【定义4 7 1 通过公共变迁和公共变迁子网合成n 个r c n 网形成网g 在g 中， p = p i u p 2 k 9 u p n ，t 5 t 1 w t 2 u u t 。，f = f l u f 2 u u f n ，如果p p s ，m o ( p ) = m s o f p ) ， 则g 成为r c n 合并网。 图4 4 一个r c n 合并网 4 3a c 网 【定义4 8 1 设n 是一个p e t f i 网，如果对于任意的p l ，p 2 p , 都有p l n p 2 中专 p l 。c u p 2 或p 2 。p i 。，则称n 为a c 网。 图4 5 一个a c 网 4 4f c 网 【定义4 8 】设n 是一个p e t r i 网，如果对于任意的p p 都有i p p l ( p ) = p 则称n 为f c 网。 第五章p c t d 网中的基本信标 第五章p c t r i 网中的基本信标 柔性制造系统( f m s ) 中资源分配不当时会导致死锁，死锁分析和控制是系统控 制实现所必须要解决的问题。p e t r i 网由于具有并发性，随机性，适于描述离散系 统，被广泛地应用于资源分配系统的死锁分析与控制。同时，用p e t r i 网建立的系 统模型也可以有效的检测系统的死锁状况及活性，这是因为系统的死锁及活性与 p e t r i 网模型中的信标直接相关。信标一旦被清空将永远保持清空，从而导致系统 出现死锁。相反，只要系统中没有信标被清空，就不会出现死锁。许多死锁预防策 略都是基于这思想的，其中以p 不变式控制策略最为典型。根据p 不变式控制 策略，只要给系统中的每个信标都添加控制库所，使得控制库所与其相应的信标 构成p 不变式，则在网系统的整个演化过程中信标就不会被清空。在这种控制方 式下，添加的控制库所与原网中的库所有可能组合成新的信标，也需要对其加以 控制。显然，p 不变式控制策略需要迭代算法来实现。e z p e l e t a 【3 j 提出的控制策略 仅适用于带资源的简单的顺序加工过程网( s 3 p r ) ，该策略汲取了p 不变式控制策略 的思想，通过添加控制库所使得信标与控制库所构成不变式，适当选取控制库所 的初始令牌数使得信标不可被清空。不同的是f 3 】中采用将控制库所输出弧指向源变 迁的方法避免了新的信标的产生，所以只要对原网中的信标添加控制库所即可使 得整个网系统受控。然而不幸的是，网模型中信标的个数是与网的规模成指数关 系的，这样就使得即使应用【2 】中的方法。控制时所要添加的控制库所也是非常多的。 同时，添加过多的控制库所在网模型上，也会大大限制系统的行为。 为此，l i 和z h o u 1 提出了一种新的控制思想，根据这种思想，信标被分为基本信 标和从属信标两种，控制基本信标可以使从属信标同时得到控制，进而使得整个 系统受控，这使得需要添加的控制库所的个数大大减少。本文在【i j 的基础上进一步 阐述了这种控制思想。首先指出了基本信标具有不唯一性t 控制任意一组基本信 标即可使得整个系统受控，而且基本信标的个数不会超过网系统中库所或变迁的 个数。控制时，可以根据具体要求适当的选择一部分信标作为基本信标，其余的 作为从属信标。 5 1p e t r i 网中的基本信标与从属信标 根据”，信标分为基本信标和从属信标两种。在下文中，n 用来表示严格极小信标 的集合，兀e ，n r 则分别用以表示基本信标和从属信标的集合。如无特殊说明，下 文中的信标均指的是严格极小信标。 【定义5 1 l 假设s 量p 是n 中的一个信标，h 被称作s 的特征p 向量当且仅当它 满足v p e s , k s ( p ) = l ，否则h ( p ) = o 。 基于m i p 算法的系统p e t d 网模型中的死锁预防 【定义5 2 】假设s c p 为n 的一个信标，1 1 s 被称作s 的特征t 向量当且仅当t 1 s 。= 九s 7 【n 】。 【定义s 。3 】假设s i ，s 2 ，s 。为n 中的信标，其所对应的t 特征向量”l ，1 1 2 ，q 。 构成了一个向量空间，这个向量空间的最大线性无关向量组为t l b = ( m1 1 j ，t 1 k ) 。 那么s 。，s j ，s k 就是n 中的基本信标。 【定义5 4 】假设s e r i f i e 是n 中的一个信标，s i ，s 2 ，s 。是其中的基本信标，s 被称作为关于s i ，s 2 ，s n 的强从属信标当且仅当1 1 s 。：i a i o r l i ，a l ，a 2 ， a e r n l 0 ，i 2 a 【定义5 5 l 假设s e r i 、_ f i e 是n 中的一个信标，s l ，s 2 ，s 。，s 。+ l ，s n * m f i e ( n 2 1 ， f 贬1 ) 是其中的基本信标。s 被称为关于s l ，s 2 ，s 。，s 。+ 1 ，s 。+ 。的弱从属信标当 且仅当t 1 i2 i a i e r l 扩墨l a i o r l s j , v k l ，2 n + m ) ，a k e i n 0 。 根据以往的基于p e t r i 网的f m s 死锁预防策略，包括基本信标和从属信标的所有信 标都要加以控制，可以证明在系统模型中，信标的个数是与网规模成指数关系的， 而基本信标的个数受限制于网系统的规模。 【定理5 1 】假设n 是一个网，其中库所的个数为吲，变迁的个数为i t i ，该网中信 标的个数为n ，基本信标的个数为m ，则 0 回顾信标不变式控制定理可知，s o 不变式可控。 【定理5 3 】假设( n o ，m o ) 是一个网系统，s l ，s 2 ，s 。sn + l ，s 。+ 。是其中的基本 信标，s o 是关于s 1 ，s 2 ，s 。sn + l ，s i l + 的弱从属信标即有r h = y ! ，a i t l 。i 一 5 7 + r 1 a # t i ”如果s t ，s 2 ，s 。，s n + l ，s i l + m 被v s l ，v s 2 v s 【。十m ) 不变式控制， 并且m o ( s o ) 苫a i m o ( s i )