（机械电子工程专业论文）一种资源分配系统广义相互抑制的简化控制器设计.pdf

摘要 在柔性制造系统中对有限资源的竞争会使系统产生死锁现象。p e t f i 网作为一 种建模工具，能有效地对柔性制造系统进行建模分析，并较好地解决系统的死锁 问题。其中一种重要的死锁预防的方法是通过给每一个严格极小信标添如一个控 制库所和相应的连接弧，以保证每一个严格极小信标不会被清空。但是在面对大 规模网系统模型时，计算严格极小信标是十分费时的，而且对所有的严格极小信 标进行控制会使网结构变得异常复杂。 因此，相关学者又提出了一些不同的死锁避免的策略，而其中的r u n ( r e s o u r c e u p s t r e a mn e i g h b o r h o o d ) 控制策略提供了一种非常有效的办法，它避免了求取所有的 严格极小信标和混合整数规划问题，极大地便利了死锁避免方面的工作，并且这 种方法不但适用于普通网，还适用于一般网，因此它具有更加广泛的应用价值。 但是这种方法有时添加了一些冗余的控制库锁，也会使网系统变得更加复杂。在 本文中，我们提出了一种基于r u n 的简化的死锁避免策略，用一系列简化后的控 制库所有效地控制了一类网系统。 关键词：p c t r i 网死锁避免策略基本信标柔性制造系统r u n 策略 a b s t r a c t t h ec o m p e t i t i o nf o rl i m i t e dr e s o u r c e sc a np r o d u c ed e a d l o c k s i nf l e x i b l e m a n u f a c t u r i n gs y s t e m s ( f m s ) p e t r in e t sa l ea ne f f e c t i v et o o lt om o d e l ，a n a l y z e ，a n d c o n t r o ld e a d l o c k si nf m s av a r i e t yo fi m p o r t a n tp e t r in e t - b a s e dm e t h o d st op r e v e m d e a d l o c k sa r i s i n gi nf m sa l et oa d ds o m ec o n t r o lp l a c e sa n dr e l a t e da r c st os t r i c t m i n i m a ls i p h o n s ( s m s ) s u c ht h a tn os i p h o nc a l lb ee m p t i e d b u to n c et h en e t sm o d e l b e c o m e sl a r g e ，i ti sv e r yt i m e - c o n s u m i n gt oc a l c u l a t ea l lt h es m s ，a n dt h er e s u l t i n gn e t s u p e r v i s o rw i l lb em o r ec o m p l e xt h a nt h eo r i g i n a lo n e s o m er e s e a r c h e r sh a v ep r o p o s e ds o m ed i f f e r e n td e a d l o c ka v o i d a n c ep o l i c i e s r e s o u r c eu p s t r e a mn e i g h b o r h o o d ( r u n ) c o n t r o lp o l i c yp r o v i d e sav e r yu s e f u lm e t h o d i ta v o i d ss o l v i n ga l lt h es i p h o n s ，s t r i c tm i n i m a ls i p h o n sa n dt h em i x e di n t e g e rp r o g r a m ( 1 y e ) ，a n df a c i l i t a t e so u rw o r ki nd e a d l o c ka v o i d a n c e t h i sp o l i c yc a n b eu s e dn o to n l y i no r d i n a r yn e t s ，b u ta l s oi nt h eg e n e r a lo n e s ，s oi th a sm o r ew i d e s p r e a r da p p l i c a t i o n v a l u e b u ts o m e t i m e st h i sm e t h o dn e e da d ds o m er e d u n d a n tc o n t r o lp l a c e s ，a n dm a k e s t h er e s u l tn e ts y s t e mm o r ec o m p l e x i nt h i st h e s i s ，as i m p l i f i c a t i o no ft h i sm e t h o di s i n t r o d u c e d , a n da n a l y t i c a lf o r m u l a t i o n sa n de f f i c i e n ts o l u t i o na l g o r i t h m sa r ed e v e l o p e d f o rt h ee a s et h a tt h ef m si ss t r u c t u r a l l yc o n t r o l l e db yac l a s so fs i m p l i f i e dc o n t r o l p l a c e s k e y w o r d ：p e t r in e t d e a d l o c ka v o i d a n c ep o l i c ye l e m e n t a r ys i p h o nf l e x i b l e m a n u f a c t u r i n gs y s t e m s r e s o u r c eu p s t r e a mn e i g h b o r h o o d 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 称为f 中弧上的权，n = 0 ，l ， 2 一) 。称n f f i ( p ，lf ，聊为普通网( o r d i n a r yn e t ) ，当且仅当v 斥f ，w q ) = l ，对 于普通网可以记做= ( 户，ld 。v p p ，vt o t , 如果p ，f ) 只且眠p ，沪l ， 则称为普通p 丁网( p to r d i n a r yn e t ) 。一个普通网肯定是一个普通p ，r 网。当| 厂 = 慨0 只阡仞 l 时，称气p ，乃只叨为一般网( g e n e r a l n e t ) 。 【定义x 2 l 令= ( p ，乃f ，聊是一个p e t r i 网，节点x e l ) u t 的前置集定义 为 x = y e p l ) t l 以力毋。其后置集定义为x = y e p w t i 隹，力毋。节点的集合 h e p u t 的前置集( 后置集) 定义为 h = u x 。巍f = u 。月妁。 【定义2 3 1 如果= c p ，lf ，功是普通网，且v t e t , i 4 = 1 t 1 = 1 ，则称是状 态机( s t a t em a c h i n e ) 。 【定义2 4 】如果= 妒，lf ，聊是普通网，并且有v c p ，i p l = k o 。h ，则称 是标识图( m a r k e d 伊a p ”。 【定义2 5 1 如果一个p e t r i 网系统c ，m o ) 的任意一个节点和其它节点中的任意 一个之间总存在一条连接路径，则称该网是强连通的。 【定义2 6 】如果一个p e t r i 网系统( ，m o ) 既是一个状态机又是强连通的，则称 其为强连通的状态机。 【定义2 7 1 网= ( p ，lf ，聊称为纯的，当且仅当，了 ，力( p x t ) w ( t x p ) ：0 ， 力e f a ( y , 功凡 非纯网可以在保持动态性质不变的情况下化为纯网。下面要讨论的网都是纯 网。 【定义2 8 】令= 妒，lf ，聊是一个网。 1 ) 的标识是映射膨p 刀讥 2 ) 一个变迁f 丁在膨下称为使能的，记为m f ) ，当且仅当v p 。f ：m 阡p ，f ) ； 3 ) 若m o 成立，则t 发射后，产生另一新标识m ，记为m f ) m ，有 6 一种资源分配系统广义相互抑制的简化控制器设计 m 7 ( p ) = m ( p ) 一形( p , t ) m ( p ) + 形( p , t ) 肘( p ) 一w ( p , t ) + ( t , p ) m ( p ) p 。m p t l t p e t n f 。 其它 4 ) 网从标识开始的所有可达标识的集合记为r ( ，m o ) 或g o d 。它是一个 最小集，即m o a 置( ，m o ) ， 拒r ( ，m o ) a m 【f m j m 五( ， 而) ； 5 ) 当t l ，t 2 ，“r 时，庐h t 2 如称为出现序列，当且仅当存在标识，蝎， 满足m o 【t o i t , 溉； 6 ) 对于网和标识m o ，o r , m o ) 称为一个网系统； 7 ) 网n = 妒，乃f ，叨的关联矩阵定义为以p 和r 为序标的矩阵口v 】：p x t - z , z 是整数的集合，且 ，= 盼叭力 p 加 p 。f p t i t 。 其它 【定义z 9 1 令气p ，lf ，聊是一个网，是的一个标识。 1 ) 一个变迁t 在标识硒下是活的，当且仅当v 时r ( ，m o ) ，j m r c 动： 矿【f ) 成立； 2 ) ( m o ) 是死锁的，当且仅当，j 旭乃? d o 【r ) 成立； 3 ) ( ，m o ) 是无死锁( 弱活) 的，当且仅当v 肘r ( n ，g o ) ，3 t e t ：m 【磅成立； 4 ) ( ，m o ) 是活的，当且仅当v t t , t 在标识m o 下是活的； 5 ) ( ，m o ) 是有界的，当且仅当3 k a n x 0 ，vm ar ( ，m o ) ，v p a p ：朋力敛； 6 ) ( ，m o ) 是结构有界的，当且仅当对于任意的有限的初始标识，它都是有界的； 值得说明的是，对于资源有限的实际系统而言，它的p e l r i 网模型一般都是结 构有界的。所有元素均为0 0 ) 的列向量记为o ( 1 ) 。 【定义2 1 0 1 令- ( p ，t ，f ，聊是一个网。 1 ) 以p 为序标的列向量v ：p - - z 称为的卫向量。 劲以r 为序标的列向量w ：n z 称为的n 向量。 3 ) 称p - 向量，是一个p 不变式( 库所不变式) 当且仅当i * 0 且i v 啪= o t 。 l 旧i - p p f ) 0 ) 称为，的支撑。 4 ) 称一个p - 不变式是极小的当且仅当它的支撑中不包含任何其它p 不变式的支 撑。本文中的p 一不变式，如果没有特别声明，则都是极小只不变式。 5 ) 称弘向量l ，是一个n 不变式( 变迁不变式) 当且仅当j 如且【? v 】j - - 0 。 第二章p e t r i 网的基本概念和基本信标理论 7 6 ) 1 1 3 1 = t e 7 v ( t ) - o 称为t ，的支撑。 7 ) 称是被p - 不变式( t - 不变式j ) 覆盖的当且仅当v p c p 坳) o ( v f 弘以f ) o ) 。 被p - 不变式覆盖的的网也称为是保守的。 【定义2 u l ( ，m o ) 是一个网系统，= 妒，lf ，叨。 1 ) 称一个非空集合s c p 是一个信标( s i p h o n ) ，当且仅当s s 9 成立； 2 ) 称一个非空集合s c p 是一个陷阱( t r a p ) ，当且仅当驾2 9 成立； 3 ) 称一个信标( 陷阱) 是极小的，当且仅当不存在其它信标( 陷阱) 是它的真子集； 4 ) 称p e p 是被标识m 标记的，当且仅当 甄p ) o 。称一个集合s 耋，是被标识m 标记的，当且仅当s 中至少有一个元素被m 标记。s 中的托肯数朋固= 马e m 筑力； 5 ) 不包含任何p - 不变式支撑的信标称为严格信标。一个严格信标有可能被清空； 回一个既是极小又是严格的信标，称为严格极小信标( s m s ) 。 2 1 2p e t r i 网的基本性质 【性质2 1 】网系统( ，m o ) ，j 是 h bt 只功的一个只不变式，v m r ( n , ) ： 1 1 b h r 。 【性质2 2 1 网系统( ，1 1 4 0 ) ，是_ 妒，lf ，叻的一个b 不变式，lj6 中所有 的变迁发射一次，可能会使网系统回到初始标识。 【性质2 3 1 网系统( ，m o ) ， ，- 俨，互只叨，风? 是一个信标，若3 m e r ( n , ) ： 心研= o ，则s 以后永远不会被标记，称为被清空。 【性质2 4 】网系统c ，1 1 4 0 ) ，= ( p ，l 只聊，s _ c p 是一个陷阱，若3 m r ( n , 1 1 4 0 ) ， 心s ) o ，则s 以后总是被标记。 【性质2 5 】网 ，_ ( p ，tf ，即的p 不变式川| 勺支撑u 川l 既是一个信标又是一个 陷阱。 【性质2 6 1 ( ，m o ) 是一个网系统，其中_ ( p ，正f ，功，j 是一个p - 不变式， s _ c p 是的一个信标，那么此信标s 是在m o 下被p - 不变式，控制的，当且仅当 r m o o 且对于所有的p a s ，j 郢成立，或等同地，r m o oj j p e pj ( p ) o c s 。 如果s 是一个在m o 下被p - 不变式，控制的信标，则s 不可能被清空。也就是说， v m r ( n , ) ：s 在标识蜥下是被标记的。 【性质2 7 】( ，m o ) 是一个普通网系统，_ ( p ，zd ，若在m 下是死锁的， 则所有未被标记的库所形成一个信标；如果网中没有信标可能被清空，则称( ， m o ) 是无死锁的( d e a d l o c k f r e e ) 。 【性质2 8 】对于普通网系统( ，m o ) ， 芦伊，ld ，死锁的必要条件是所有的 极小信标都被清空。 8 一种资源分配系统广义相互抑制的简化控制器设计 2 2 一个柔性制造系统的p e t r i 网模型 在这一小节中，我们通过介绍一个简单的例子对p e t r i 网的基本定义和概念做 一个系统的了解。 图2 1 是对一个f m s 的加工生产过程进行p e t r i 网建模。图中系统有4 个机床 m 1 一m 4 ，每个机床可以同时对两个工件进行处理；有3 个机器人r l r 3 ，它们 每次可以对一个工件进行操作；还包括三个输入缓存库1 1 - - 1 3 和三个输出缓存库 0 1 - - 0 3 ，该单元可生产三种零件类p 1 ，p 2 ，p 3 。 在这个系统中，机床处理原材料，机器人负责搬运工件，其中r 1 负责i l 到 m 3 ，l l 到m 1 和m 3 到0 3 ；r 2 负责m 1 到m 2 ，m 4 到m 3 ，m 3 到m 4 ，1 2 到 m 2 和m 2 到0 2 ：r 3 负责1 3 到m 4 ，m 2 到o l 和m 4 到0 1 。m 1 处理零件类p 3 ； m 2 处理零件类p 1 和p 3 ) m 3 处理零件类p 2 和p 3 ；m 4 处理零件类p 2 和p 3 。 其产品的生产进程如图2 1 ( b ) 所示，p e t r i 网仿真模型如图2 2 所示。 o u t p u t 3 田p 盼- t 崇：r 2 ：耄。 囫一一囫一 8 8 ； 岛萨一 第二章p e t r i 网的基本概念和基本信标理论 9 图2 2 图2 1 对应的p e t r i 网实例 我们分析一下此柔性制造系统的工作过程，不难发现，这个系统如果稍不注 意就会产生死锁。设想这样一种状态：m 4 机床完全由两个零件类p 3 占据，而r 3 正举起一个零件类p 2 准备往机床m 4 上装载，这样的话系统就产生死锁而不能继 续运行下去，必定大大降低了生产效率。 2 3 基本信标理论 2 3 1 基本信标与从属信标 根据【1 】，信标分为基本信标和从属信标两种。在下文中，兀用来表示严格极小 信标的集合，t e s ，t d s 则分别用以表示基本信标和从属信标的集合。 【定义2 a 2 1 设( ，m o ) 是一个网系统，s 是网的一个信标。如果v m e r ( n , m o ) ， 麒s ) o 成立，则称s 为可控信标。 其e p m ( s 3 代表信标s 中的托肯数总和，即 f 猡产，。s m ( p ) 。由定义我们可以明 显地看出：一个可控信标总是被标识的。由于线性规划法可以避免详细地列举所 有状态数，所以它是一个寻找网系统中可控信标的有效方法。通过解下列的线性 规划问题， m i n m ( s ) s 甜b j e 州o 慧翼 l o 一种资源分配系统广义相互抑制的简化控制器设计 我们可以认为：如果m i n m ( s ) o ，那么踺一个可控信标。称关系式m = m o + c y 为状态方程，根据p e t r i 网的基本概念知，任一可达标识脚满足状态方程，反之则 不成立。因此线性规划中的标识集合一般包含此p e t r i 网系统的所有可达标识，所以 这是信标刚# 空的充分条件。 【定义2 1 3 】 毙- 正刃为一个p e t r i 网，且s 昝是的一个信标，p 向量以 称为信标s 的特征p - 向量，当且仅当v p c s ：五s ( p 产1 ；否则，a 武力= o 。 【定义2 1 4 设 h p ，正d 是一个p e t r i 网，踺? 是的一个信标，乃是s 的特征 a 向量，称r s 是s 的特征弘向量，珊。= 矗o 【? 、7 】。 【定理2 1 】一个b 不变式的支撑的特征弘向量为0 。 【定理2 2 】浞 h p ，瓦刃的一个信标且秩该信标的特征乃向量。 ( 1 ) 发射 f 卸缄f ) o ) 中的变迁侩使s 中的标志数增自l r l s ( t ) 个。 ( 2 ) 发射 t t q v s ( t ) = o ) 中的变迁环会改变s 中的标志数。 ( 3 ) 发射 f z l r l s ( t ) o ，则称躔 一个强从属的严格极小信标，简称为强从属信标。 【定义2 1 8 】设 s 。鼢，s 彦为网系统c ， 知) 的一组基本信标，s 正 _ s 。， s 分是( ，m o ) 的一个严格极小信标。若r s = e 卢l r l s r e t q k 钧成立，其中 & 嘞 ，s 分= s l ，s 2 ，s 。) u s l ，s ，) ， s 1 ，s 2 ，s 。) n s n l ，s ，) = m ，且v i e 1 ， 2 ，“) ，a t 0 ：w u + l ，v ) ，矿o ，则称赃一个弱从属的严格极小信标，简 称为弱从属信标。 强从属信标和弱从属信标通称为从属信标，明显地，胆，砀s 。如果s 相 对于s l ，s 2 ，s 。来说是一个从属信标，则称s l ，s 2 ，s 。是s 的基本信标。 【定理2 3 】设_ 妒，l d 是一个p e 缸网，网中的基本信标个数等于【班枷的秩。 证明：设含有| j 个严格极小信标和p 个基本信标，因为基本信标集合是严格极 小信标集合的子集，所以t f 。若无从属信标时，七= p ，否则网肿有缸p 个从属信 标，根据定义2 1 7 和定义2 1 8 可知，从属信标可被基本信标线性表示，由矩阵定义 得r a n k ( 碉h 月) = f 。 第二章p e t r i 网的基本概念和基本信标理论 l l 【定义2 1 9 设( ，m o ) 是一个p “网系统，网中所有基本信标的集合为厨落， i 衄d 爿，岛，& ，两历西，睑，且( j 7 蜘，r s z ，r s d 是中所有基本信标对应的特征 d 向量阵【御7 l j 7 一1 i 衙、1 衲中的最大线性无关组，令【班s 】= 【獭7 i r s 2 t i l ，7 ：s r t ， 称【，z 翻是网的基本信标的特征正向量矩阵。 因为根据基本信标的定义，可能存在两个基本信标的特征t 向量相同的情况， 而根据【删的定义，这样的基本信标只对应 r e s 中的一行。 通过信标特征弘向量的含义，我们发现从属信标托肯数的变化与基本信标托 肯流向有着紧密的联系。例如，假定在网中s 相对于基本信标两，晶来说 是一个从属信标，盯，f 2 ，t 3 , t 4 是四个变迁，扩( - 1 ，- l ，l ，1 ) 1 ，r s l = ( - 1 ，0 ，0 ，1 ) t ，弛= ， 1 ，1 ，o ) o 。很明显，发射t l 会减少蜀和s 中的托肯数；发射f 2 会减少& 和s 中的 托肯数。假定在某一初始标志m o 下，m o ( s ) = m ，m o ( s o f f i m l ，且m o ( s e ) = m z 。进一 步，我们假定能够找到某种方法使f j 的发射次数与的发射次数的最大差值为 m l ，则我们能够保证信标s 1 的中的托肯数不被清空。同理，当我们使f 2 的发射 次数与打的发射次数的最大差值为m 2 1 ，则我们能够保证信标舵的中的托肯数 不被清空。如果m m 1 1 + 州2 1 成立，则从属信标肯定不会被清空。换句话说，如 果能够总是保证s 1 和舵被标记则从属信标s 永远被标记。 2 3 2 基于基本信标的死锁预防策略 在介绍此种控制策略前我们先引入一些概念和定理。 【定义2 2 0 1 设 辟妒，乃刃是一个p e a r l 网，假如挺，那么我们称t 为网 的源变迁。 【定理2 4 】设o 是一被标识的网，肛锄1 ，p a ，p 。) 是0 的一个信标，在 o 中加一控制库所珞，则新的网系统表示为( l ，尬) 那么：1 ) 1 1 气，l p a ，l p a ， l p l ，1 h ，) r 是n i 的p 不变式；2 ) 以( 哟= 怖圆- 岛，其中1 矗( s ) 一1 ；3 ) v p ? o ， 磊( 泸，其中凡是o 中库所的集合。那么s 是不变式可控的。 冬是信标s 的控制深度变量，( n o ，m o ) 表示原网系统，( l ，尬) 表示添加库所 后的网系统。 证明：见 1 。 【定理2 5 】设c 0 ，m o ) 是一网系统，s 是相对于基本信标岛，岛，晶的一个 强从属信标。设添加控制库所k l ，p k ，p 岛后蜀，s 是不变式可控的，且 蚴 ”川a m o ( s , ) - ”川鸲，那么岛是不变式可控的。 证明：见 1 。 【定理2 6 】设( n o ，m o ) 是一网系统，岛是相对于基本信标s l ，品，晶+ l ，s + 2 ， 岛+ 。的一个弱从属信标，其中r s o = e ，。l a ，r s ，z p + 0 。1 1 2 t 猾。设添加控制库所份l ， 玢2 ，p 岛+ 。后s i ，岛，岛，品+ l ，品+ 2 ，晶+ 。是不变式可控的，且 1 2 一种资源分配系统广义相互抑制的简化控制器设计 m o ( s o ) z n , = l a ，m o ( s i ) 一掣f l l a i 蠡，其中1 酶函；- l ，那么岛是可控的。 证明：见 1 。 【定理2 7 】设 r _ ( p ，乃刃是一p e t r i 网，磙示中基本信标的个数。则可 得。晦_ m i n ( i p i ，i t i ) 。 证明：见 1 。 对给定一个网，在参考文献 1 】中，我们可以得出基于信标的死锁预防算法的 步骤如下： 第一步：找出中所有的s m s 。 第二步；从s m s 中找出基本信标，其余的为从属信标( ) 。 第三步：对每一个基本信标s ，添加如下控制库所k 1 ) k 的输出狐连接到与s 相关的源变迁上。 2 ) 玎的输入弧与s 的补集相关联。 3 ) 1 簧矗 翻- 1 ，m o ( v , ) = m o ( a d e 。 第四步：重复第三步直到所有基本信标都被添加控制库所。 第五步：调整岛值直到每一个从属信标都得到控制。 其中，可以证明用此方法受控后得到的网模型是活的，见( 1 】。 下面我们参考图2 2 所示的p e t r i 网模型，不难求出该网一共存在1 8 个严格极小信 标，见表2 1 ： 表2 1 图2 2 中所有的严格极小信标 s m sp l a c e s m o ( s ) s 1 p l o , p l s p 觊，p 2 6 3 s 2 p 4 ，p l o , p 1 5 ，p 2 0 , p 2 1 ，p 2 2 , p 2 3 , p 2 4 , p 2 5 ，1 0 2 6 n s 3 p 4 , p l o , p 1 6 , i ) 2 1 p 2 2 , p 2 4 ，p 2 5 ，p 2 6 8 s d p 4 ，p 1 0 , p 1 7 ，p 2 a ，p 2 2 ，p 2 4 ，p 2 6 6 s 5 p 4 ，p 9 ，1 3 1 3 ，p 1 5 ，p 2 0 ，p 2 l ，p ：2 3 ，p 2 4 , p 2 5 ，p 2 6 1 0 s 6 p 4 ，p 9 ，p 1 3 ，p 1 6 p 2 1 ，p 2 4 ，p 2 5 ，p 2 6 7 s 7 p 4 ，p 9 ，1 ) 1 3 ，p i t , p 2 l ，p 2 4 ，p 2 6 5 s 8 p 4 ，p 9 ，p 1 2 ，p 1 5 p 2 0 ，p 2 1 ，p 2 3 ，p u , p 2 5 8 s o p 4 ，p 9 ，p 1 2 ，p 1 6 p 2 1 ，p 2 4 ，p 2 5 5 t s l o p 4 ，p 9 ，1 3 1 2 , p i t , p 2 1 ，p 2 4 3 s h p 2 ，p 4 , p s , p l o , p l s , p 2 0 p 2 1 ，p 2 2 ，1 7 2 3 1 3 2 5 ，p 2 6 9 s 1 2 p 2 ，p 4 ，p s , p t 3 ，p l s , p 2 0 ，p 2 l ，p 2 3 ，p 2 5 ，p 2 6 8 s 1 3 p 2 ，p 4 , p s , p 1 0 , p 1 6 p 2 1 ，p 2 2 ，p 2 s ，p 2 6 6 s t 4 p 2 ，p 4 , p s ，p 1 3 ，p 1 6 p 2 1 ，p 2 5 ，p 2 6 5 第二章p e m 网的基本概念和基本信标理论 s 1 5 p 2 ，p 4 ，p s ”p l o , p 1 7 , p 2 1 ，p 2 2 , p 2 6 4 * s 1 6 p 2 , p 4 ，p s , p 1 3 ，p 1 7 ，p 2 1 ，p 2 6 3 s 1 7 p 2 ，p 4 ，p s ，p 1 2 p 1 5 ，p 2 0 ，p 2 1 1 3 2 3 ，p 2 5 6 * s 1 s p 2 ，p 4 ，p 8 ，p 1 2 , p 1 6 , p 2 1 p 2 s 3 我们根据基本信标理论可以从表2 1 中可以得出，该网中一共有6 个基本信标， 表2 1 中带+ 号的属于基本信标，其余的为从属信标，也就是说，我们只需要控制6 个基本信标就可以使网变活。其中6 个基本信标和1 2 个从属信标之间的线形关系如 表2 2 所示： 表2 2 基本信标和从属信标的关系 s v信标从属关系初始标识之间关系 s 2 1 1 s 2 刁1 s 4 + t i s l 7 m o ( s 2 ) m o ( s 4 ) + m o ( s 1 7 ) - 2 s 3 t i s 3 。r t s 4 + r l s l 8m o ( s 3 ) m o ( s 4 ) + m o ( s 1 8 ) 2 s 5 q s 5 = q s l a + t 1 s 1 6 + t 1 s 1 7m o ( s s ) m o ( s l o ) + m o ( s 1 6 ) + m o ( s 1 7 ) 3 s 6 r l s 6 = r l s l o + t l s l m s l 8 m o ( s 6 ) m o ( s t o ) + m o ( s 1 6 ) + m o ( s i s ) - 3 s ， t 1 s 7 2 1 s 1 1 1 s 1 6m o ( s 7 ) m o ( s l o ) + m o ( s 1 6 ) - 2 s 8 t l s 8 。_ n s l o + ”s 1 7 m o ( s s ) m o ( s l o ) + m o ( s l t ) - 2 s 9 q s 9 t 1 s l o 斗1 1 s 1 8m o ( s g ) m o ( s ! o ) + m o ( s i s ) 一2 s n q s l l 。t 1 s l + 1 s 1 6 + 1 1 s 1 7m o ( s n ) = m o ( s 1 ) + m o ( s 1 6 ) + m o ( s i t ) 3 s t 21 s 1 2 = i 1 s 1 6 蜘s 1 7 m o ( s 1 2 ) m o ( s 1 6 ) + m o ( s 1 7 ) 一2 s t 3 1 1 s 1 3 = t i s i + ”s 1 6 + t 1 s 1 8 m o ( $ 1 3 产m o ( s 1 ) + m o ( s 1 6 ) + m o ( s 1 8 ) - 3 s ut 1 s 1 4 邗s 1 6 + 1 s 1 8m o ( 8 1 4 ) m o ( s 1 6 卜m o ( s 1 8 ) - 2 s i sr l s t s = q s l + n s l 6 m o ( s 1 s ) _ m o ( s 1 ) + m o ( s 1 6 ) - 2 根据以上基于基本信标的死锁预防算法，最终求得的6 个控制库所的前后置和 初始标识如下： v 1 ： v l = t 1 0 ，t 1 6 ；v i = 白t 1 5 ；m o ( v l 产m o ( s o 1 = 3 1 = 2 v 2 ：v 2 _ t 5 ，t lo ，t 1 3 ，t 1 7 ；v 2 = t 3 ，t s ，t l l ，h s ；m o ( v 2 ) = m o ( s 4 ) 一1 = 6 - 1 = 5 v 3 ：v 3 = “，t 1 3 ；v 3 。= t 3 。t n ； m o ( v 3 ) = m o ( s i o ) - 1 = 3 i - - 2 v 4 ：v 4 - 慨t 1 7 ) ； v 4 。 t s ，t 1 6 ；m o ( v 4 ) = m o ( s 1 6 ) 一1 = 3 1 = 2 v s ：v 5 = t 3 ，t 8 ，t 1 9 ；v 5 名 i l ，t i t ) ；m o ( v 5 ) = m o ( s 1 7 ) 一1 = 6 1 = 5 v 6 ：6 = t 8 ，h s ；v 6 = t 7 。t 1 7 ；m o ( v 6 ) = m o ( s i s ) 1 = 3 - 1 = 2 最终，用基于基本信标的控制算法受控后的网模型具有6 2 8 7 个状态，并且网是 活的。 1 4 一种资源分配系统广义相互抑制的简化控制器设计 2 4 小结 本章简要介绍了p e m 网的基本定义和性质，并结合例子对其进行了说明，另外， 作为一种解决死锁问题的重要思想，本章也重点介绍了基本信标理论，从而对后 面章节所用到的基本知识进行了说明。 第三章s 3 p g r 2 网模型及基本性质 本章中主要介绍一些s 3 p g r 2 的基本定义和性质【3 】【1 鲫，为后面的部分提供必要 的定理和依据。因此，本章引入一个特殊的p e u i 网的子类s 3 p g r 2 网，该子类可 以模拟更为复杂的系统。在这种类型的网中强连通的状态机模拟多个并行的顺序 加工进程，资源库所模拟不同的资源类型，如机床，机器人，夹具，运输小车等。 不同的工序可以申请不同类型的多个资源，因此有着更为重要的研究意义 3 1s 3 p g r 2 网的基本定义 一个r a s 模型是由一组不同类型的资源( 表示为r 予 ，i = 1 ，1 1 1 ) ) 和一组不 同类型的进程( 表示为j = j t j j = 1 ，山) 组成的。每一个资源r i 的容量表示为c i ， 也即是用一个有限的正整数表示资源类型中资源单元的个数。进程类型用一个 m - 维的向量( j t 业，k = 1 ，l ( ；) ) 来表示，该向量由巩k 组成，其中q - 1 ，m ，它表 示第j 个进程中的第k 步的顺利完成需要的r q 类型资源的个数。其中定义的这个 ，r i ，j = l ，l l 类型进程的向量的序列被称做它的路径，而这个序列中不同的元素将 被称做路径状态。通过上面对该类系统的描述，我们可以按如下来定义系统的状 态： 【定义3 1 】一个r a s 在时间t 的状态s ( t ) 是一个维数为d = i ：1 “i ( i ) ( 也即等于 系统中不同的路径状态的个数) 的向量，具有元素s 。( t ) ，i = 1 ，d ( 也即等于在时间 t 执行路径j t a 的第k 步的进程的个数，q 是最大的整数，s t i z p l q - i l o ) 并r k - - i 一一q - 1 l ( j ) ) 。 由于每个资源类型的容量是有限的，所以我们也可以说r a s 的状态个数也是 有限的，我们表示为：q 一 q i ，i = o ，z ) ，其中q o 表示系统的初始状态。如【4 】中所 述的那样，一个r a s 的状态空间可以用一个自动机口s a ) 来迸行描述，为了在最 小的限制条件下达到死锁避免的目的，系统的操作必须被限制在包括q o 的最大的 类范围之内，我们把这一范围表示为q s ，则任意的状态q q s 都是安全的，而不 属于q s 的状态则是不安全的，我们把这个范围表示为q u ，即是q s 的补集。我们 控制的最终目的也即是阻止r a s 进入q 。中的状态。 根据资源分配需求的结构不同和对资源的申请方式的不同，可以将r a s 分为 下面几类： 1 ) s u r a s ( s i n g l e u n i tr a s ) ：每个进程步骤的执行仅仅需要一个资源库所的一个 单一资源。 2 ) s t - r a s ( s i n g l e t y p er a s ) ：每个进程步骤的执行需要一个单一资源的任意个数 1 6 一种资源分配系统广义相互抑制的简化控制器设计 目的资源。 3 ) c r a s ( c o n j u n c t i v e ) r a s ) ：每个进程步骤的执行需要任意个资源( 集合) 的任 意个数目的资源。 4 ) c d - r a s ( c o n j u n c t i v e d i s j u n c t i v er a s ) ：每个进程步骤形成一个有限数目的任意 的连接类型资源需求。 【定义3 2 】一个简单加工进程( s i m p l es e q u e n t i a lp r o c e s s ) s 2 v 是一个p e t r i 网 舻= 口u 舶) ，瓦刀，m o 是的初始标识，助称为闲置库所( 加工进程的开始和结束工 序状态) ，p e p 称为工序状态库所。c m o ) 满足以下条件： ( 1 ) 辟西，邱芒p ，m o ( p o ) l ，v p p ，( p ) = o ； ( 2 ) 是一个强连通的状态机，i n v t 引d = j f | _ 1 ； ( 3 ) 的每一个回路包含珈。 图3 1 两个s 2 p p n 【定义3 3 1 一个拥有资源的简单加工进程( s 2 pw i mr e s o u r c e s ) s 2 p r 是一个网 - ( 尸u p o u j p _ 如e d ，是的初始标识。( m m o ) 满足以下条件：( 1 ) 令p o = p o ) ， 由j 每 p 0 u 丁生成的子网n x = ( p 为t x , 黝是一个s 2 p ，其中p x = i k | p o ) ，t x = t , f x = f n ( p 於7 劲；( 2 ) r e p r 称为资源，n 是资源的集合，舻，c p u 肌) ) n p 萨； ( 3 ) v p e p ，v t e ，y e l p ，了砀尸r ，t c 、p s = r c x p r = r p ：( 4 ) v r 尸k 而( 力l ；v re r r ， r r d = r c x p # o ；v ，尸k r r v - = o ：( 5 ) ”( p o ) f u p r = ( p o ) n p r = o ：( 6 ) 对于一个给定 的r e 尸屯坝r h ，) n l p 称为资源，的持有者集合。对于一个资源集合婀= ，r 2 ， ，用u h ( r ) l r e 孵 或l 3 r 。m 坝力表示嘶i ) u h ( r 2 ) w u 日) 。 第三章s h , g 9 2 网模型及基本性质 1 7 图3 2 两个s 2 p r 【定义3 4 1 一个拥有资源的简单加工进程系统( s y s t e mo fs 2 p r ) s 3 p r 是 t ( 七肌 o ) ) 个s 2 p r 通过共享资源复合而成的p e t r i 网n = - o # i k n t - ( p u p o u p r ，ld 。 记肌= 1 2 ，耐。s 3 p r 网系统( ，g o ) 满足以下条件： ( 1 ) 一个s 2 p r 也是一个特殊的s 3 p r ； ( 2 ) v i e n k , w 州岭) ，妒i u p 0 t ) n ( p o p o j ) = g i j ，且存在p r 介p 旷p c 护o ，研乎面； ( 3 ) ，爿j l ，f p o = k 7 产l p o f ，p s - 爿j 卢l ! p 彤；z 与j 产l 勺岛j b = u 扛1 日； ( 4 ) v i n k , 坳几j p o j ，( 炉力；v i e 耽v r 尸枷，c f ，m o ( r ) = m o i ( r ) ；v r p c g , m o ( r ) = m a x 9 0 1 ，如，) ； ( 5 ) 符号可表示组成第f 个s 2 p r 网m 的s 2 p 。 图3 3 一个s 3 p r 【定义3 s l 一个拥有一般资源需求的简单加工进程系统( s y s t e mo fs i m p l e s e q u e n t i a lp r o c e s s e sw i t hg e n e r a lr e s o u r c er e q u i r e m e n t s ) s 3 p g r 2 网是一个网n = ( p ，t ，f ：w ) ，n 一个以m o 为初始标识的网，其满足下列几个条件： l s 一种资源分配系统广义相互抑制的简化控制器设计 ( 1 ) 尸= bu 晶u 最，其中b = u 二l 。墨，且对于任给的，矗n 名= m ； 昂= u 二l 。 p o ， ，且昂n b = 中；最= ，卅) ，且( 马u p o ) n p r2 m ( 2 ) r = u 。乃。 ( 3