（机械电子工程专业论文）基于一类petri+net模型的初始状态配置与死锁检测.pdf

摘要 模型的建立是使用p e 硒n e t 对柔性制造系统( f m s ) 进行控制，确认，性能 分析和仿真的第一步。本文将一个子类i 广s 3 p r 网中的活性性质进行了推广，并 提出了一种用于检测一类更大范围网模型s 3 p r 中是否存在死锁的线性算法。本 文介绍了资源回路的概念和如何从网结构中获得资源回路，进而从资源回路导出 信标的方法。证明了从资源回路导出的一个极小信标如果不含有任何p 不变式的 支撑，则它不是一个潜在的死锁。只有在系统运行中可被清空的极小信标才是系 统不活的真正原因。 除了结构，网模型不恰当的初始标识也会导致死锁。在设计和调整网模型时， 根据约束条件来重新配置初始标识，使网模型无死锁的方法也结合实例在本文中 做了详细介绍。对于s 3 p r ( l 广s 3 p r ) 网模型，给出了闲置库所与资源库所中托肯数 之间的合适关系。所以，在不改变网结构的前提下，系统可以被快速重新配置， 以适应需求的变化。这使得柔性制造系统的敏捷性得以保证。 此外，本文还提出了一种用于死锁预防策略的正确算法。在这类系统的p e t r i 网模型中，死锁是由未被标识的信标产生的。这个算法被用来从由m i p 方法获得 的极大信标中求取极小信标。本文还从信标定义的角度对算法的正确性进行了证 明，而且这种算法同样是一种线性算法。 关键词：资源回路活性判定约束条件族无死锁线性算法 a b s t r a c t t 1 l ed e s i g no fm o d e l si st l l ef i 璐ts t c pf o fc o n t m l ，v a l i d a t i o n ，p e r f o m a n c ea n a l y s i s ， a n ds i m u l a t j o nf o rn e x i b i em a n u f 缸t i l r i n gs y s t e m s ( f m s ) 1 1 l i st l i e s i se x t e n d st h e l i v e n e s sc h a f a c t e f i z a t j o nf c s u l t so nas u b c l a s so fp e mn e t s ，l s p r ap 0 1 y n o m i a l a l g o r i t h mi sd “e l 叩e dt od e c i d ew h e t h e ram o f eg e n c r a lc l a s so fp e t r in e t s ，s p r ，h 鹬 p o t e n t i a ld e a d l o c k ，w h i c hc a nm o d c law i d ed a s so ff m s t 1 l ec o n c e p to fr e s o u r c e c i r c i i i ta i l dt h ew a yt o6 n dt h 哪f 如man e ts t n l c t u t ea f ep m p o s e ds u c c e s s i v e ly t h e t h e s i ss h o w st h ea p p r o a c ht oo b t a i nam a ls i p h o nf f o mar e s o u r c ec i r c u i t ni sa l p r o v e dt h a ti fam i n i m a ls i p h o i id e r i v e df 如mar e u r c ec i r c u i td o e sn o tc o n t a i nt h e s u p p o no fa n yp - s e m 讯o w i ti sn o tap o t e n t i a ld c a d l o c k am i n i i i l a ls i p h o nt h a tc 缸b e e m p t i e di st h er e a lc a u s e0 ft h en o t - l i v e n c s si i l 拙s 3 p r i na d d i t i 咖t ot h en e ts t m 咖f c ，t h ei n 印p m p r i a t ei n i t i a lm a r k j n gc a nc a u s e d e a d l o c kt o o s e t t i n gt h en e tt ob ed c a d l o c k f f c eb yc o n f i g i l r i n gt h ei n i t i a lm a r k i n g a c c o r d i n gt ot h ec o n s t r a j n t s 芦o u pi si 1 1 u s t r a t c df o rd e s i 印i n ga n dm o d i f y i n g t h cs y s t c m m o d e l i tp r o v i d e sa p p r o p r i a t er d a t i o n sb c t w e c nt h cn u m b e ro ft o k e n si n i d l ep l a c c s 卸dt h a “nt h er e s 0 u r c ep l a c e sw h c nd c a l i n gw i t hs p r ( l s 。p r ) a sar e s u l t ，w j t h o u t c h a n g i n gm es t m c t u r eo ft h es y s t e m ，w ec a nq u i c k l yr c n 6 9 i l r et h es y s t e mt or e s p o n d t ot h ec h a n g eo fd e m a n d t h ea 西l i t yo ff m s 啪b eg u a r a n t e e d n i st h e s i sa l s op m p o s c sac o r r c c ta 1 9 0 r i t h r i lt h a ti su s e di nt h ed e v e l o p m e n to fa d e a d l o c kp r e v e n t i o np o l i c yf o rac l a s so ff m sw h e r ed e a d l o c k sa r ec a u s e db y u n m a r k e ds i p h o n si nt h e i rp e mn c tm o d e l s 皿ea l g o r i t h mi sd e s i 9 1 1 e dt od e r i v ea m i n i m a ls i d h o nf m mam a x i m a lu 砌a r k e do n et l l a tc a nb eo b t a i n e dd u et ot h em j x e d i n t e g e rp r o g r a n l m j n gb a s e dd e a d l o c kd e t e c t i o n i ti sa l s op r o v e dt h es i p h o n st h a tc a l l b ed e r i v e du s i n gt h ea l g o r i t h ma r em i n i m a lo nt h e 芦o u n do fs i p h o ns d e f i n i t i o n k e y w o r d ：r e s o u r c ec i 砌n d e a d i o c k f h e l i v e m s sc h e c kc o n s t 豫i n t sf a m i i y p o l y 舯m j a la l g o r i t h m 创新性声明 y85 8 7 8 二 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名嫂日期型：兰：塑 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证 毕业离校后，发表论文或使用论文工作成果时署名单位仍然为谣安电子科技大 学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文 的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 日期筮型：兰：丝 日期型：望丞辛 第一章绪论 第一章绪论 1 1 研究背景与意义 随着社会的进步与人类需求的不断增长，进行大批量生产的刚性自动化生产 方式，由于缺少快速适应市场变化的灵活性，已开始不能满足人们对于产品多样 性的需求，不能适应时代发展的潮流。因此，伴随着科学技术的发展，先进制造 技术逐渐进入人们的视野。 先进制造技术( a d v 飘c e dm 柚u f a d u 由gt e c l l n o l o g y 州t ) 是一个国i 啄上形 成广泛共识的概念和已被公认的技术术语。 先进制造技术可定义为：在制造系统的一系列生产环节中，传统的制造技术 有机的融合并有效的利用计算机，信息，新材料，能源，系统管理等现代化科学 技术，实现优质，高效，低耗，灵活和清洁地制造满足市场需求的产品，并取得 理想经济效益的工程技术的总和。 多品种，小批量生产方式日渐成为现代制造业的主流和发展趋势，因此企业 将面向用户，面向订单组织生产，这要求制造系统既要有高度的生产率，又要具 有充分的灵活性( 柔性) 和可重构性。作为a m t 重要组成部分之。的柔性制造 系统( f l e x i b l em a n u f a c t u r i n e s y s t e m ，f m s ) 应运而生。 1 9 6 7 年，英国莫林斯公司首次根据威廉森提出的f m s 基本概念，研制了 “m o i i n s 2 4 ”。其主要设备是六台模块化结构的多 二序数控机床，目标是在无人 看管条件下，实现昼夜2 4 小时连续加工，但最终由于经济和技术上的困难而未全 部建成。 同年，美国的怀特森斯特兰公司建成“o m n i l i n ei ”系统，它由八台加工 中心和两台多轴钻床组成，工件被装在托盘上的央具中，按固定顺序以一定节拍 在各机床间传送和进行加工。这种柔性自动化设备适于少品种、大批量生产中使 用，在形式上与传统的自动生产线相似，所以也叫柔性自动线。日本、前苏联、 德固等也都在上世纪6 0 年代末至7 0 年代初，先后开展了f m s 的研制工作。 1 9 7 6 年，日本发那科公司展出了由加工中心和1 ：业机器人组成的柔性制造单 元( 简称f m c ) ，为发展f m s 提供了重要的设备形式。柔性制造单元( f m c ) 一般由 1 2 台数控机床与物料传送装置组成，有独立的工件存储站和单元控制系统，能 在机床上自动装卸工件，甚至自动检测工件，可实现有限工序的连续生产，适于 基于一类p e t r in e t 模型的初始状态配置1 i 死锁检测 多品种小批量生产应用。 上世纪7 0 年代末期，f m s 在技术上和数量上都有较大发展，8 0 年代初期已 进入实用阶段，其中以由3 5 台设备组成的f m s 为最多，但也有规模更庞大的 系统投入使用。 1 9 8 2 年，日本发那科公司建成自动化电机加工车间，由6 0 个柔性制造单元 ( 包括5 0 个工业机器人) 和一个立体仓库组成，另有两台自动引导台车传送毛坯 和工件，此外还有一个无人化电机装配车间，它们都能连续2 4 小时运转。这种自 动化和无人化车间，是向实现计算机集成的自动化工厂迈出的重要一步。与此同 时，还出现了若干仅具有f m s 基本特征，但自动化程度不很完善的经济型f m s 。 这都使得f m s 的设计思想和技术成就得到普及应用。 一套完整的柔性制造系统( f m s ) ，如图1 1 所示，包括自动化的加工系统， 自动化的物流系统，信息和控制系统。其中，信息和控制系统负责f m s 的实时控 制和在线监督，信息由多级分布式计算机进行处理和控制。f m s 的工艺基础是成 组技术，它按照成组的加工对象确定工艺过程，选择相适应的数控加工设备和工 件、工具等物料的储运系统，并由计算机进行控制，故能自动调整并实现一定范 围内多种工件的成批高效生产( 即具有“柔性”) ，并能及时地改变产品以满足市 场需求。 图1 1 柔性制造系统( f m s ) 柔性制造系统具有自动化程度高，运行效率高的优点，但也存在着系统复杂 第一章绪论 性大，投资风险大，物流系统的复杂性使整个f m s 可靠性下降的缺点。所以，如 何设计和构建良好的信息与控制系统，对f m s 中的物质流和信息流实施有效的自 动化控制和管理，避免死锁，使它们在最佳的状态下运行并获得高效率，就成为 一个迫切需要解决的问题。 p e t r i n e t ，也称为p e t r i 网，是由德国人c a p e t r j 于1 9 6 2 年在他的博士论文 中首次提出的。它【1 】【2 】是一种适用于多种系统的图形化、数学化建模工具，为描 述和研究具有并行、异步、分布式和随机性等特征的信息加工系统提供了强有力 的手段。目前已经广泛应用于对离散时间动态系统的建模与分析。 在f m s 中【5 】【6 】【7 】【1 3 】【1 5 】【1 7 】，各种工件按照一定的节拍，在离散时间点上 进入系统，系统对它们进行并行加工处理，各加工进程共享一定数量的资源，如 数控机床、工业机器人、夹具、小车等。各种工件有自己的特殊加工路径，即资 源需求序列在加工过程中，各种工件的并行处理竞争有限的资源，从而可能导致 系统的运行陷入死锁之中。构建良好的p e m 网模型，是对f m s 进行建模设计， 控制，确认，仿真及性能分析的第一步。在这种情况下，如何快速判断系统的活 性，如何从网模型结构和配置的角度，在设计和调整阶段避免死锁，以及如何对 存在问题的网模型进行控制，都是需要深入研究的问题。 本文的研究工作就是针对用于f m s 建模的一类p e 网模型的活性判断，通 过配景初始标识来避免死锁的方法及一种应用于迭代控制的有效算法所展开的。 1 2 本文所完成的主要工作 针对柔性制造系统( f m s ) 的p e t r i 网模型，本文主要完成了如下工作： 1 介绍并对比了s 3 p r 及其子类l s 3 p r 网模型的定义，结构及性质。 2 提出了一种判定一类网模型活性的多项式( 线性) 算法。 将子类l s 3 p r 中的性质推广到s 3 p r 网中，即严格极小信标的存在是s 3 p r 网不活的充分必要条件： 对由资源回路导m 的信标若不含任何p 不变式的支撑则是严格极小信标的 性质的证明进行了介绍，并结合实例解释了从资源回路导出信标的过程； 提出了资源有向图的概念，并根据通用图论说明了这种判定网活性的算法是 一种线性时间复杂度的算法。 3 洋细介绍了通过配置初始标识使网模型无死锁的方法。 介绍了求取约束条件族的直接方法； 结合实例解释了如何应用这种通过配置初始信标使网模型无死锁的方法： 从物理意义的角度，对这种配置方法进行了解释。 4基于一类p e t r in e i 模型的初始状态配置与死锁检测 4 提出了从极大信标中求取极小信标的算法。 分析了【1 5 】中的错误算法； 提出了新的正确的算法，并以更清晰的方式表达 结合实例详细解释了算法运行的过程和结果； 从信标定义的角度，对算法进行了理论证明。 指出这种算法也是一种线性时间复杂度的算法。 l 下。 限于时问、条件和个人的认识，本文不可避免地存在一些不足之处，恳请指 第二章基于p c 访网的建模与分析 第二章基于p e t f i 网的建模与分析 近年来，p e t r j 网在各个领域中得到了广泛的应用：利用p e 砸网成功地实现 通信协议的验证；在软件工程中，p e 仃i 网可以应用于软件开发生命周期的各个阶 段：一般p e t f i 网和时问p e t r i 网在计算机网络性能评价和多媒体技术领域内得到 越来越多的应用：模糊p e t i i 网在知识推理和神经元网络中的得到了很好的应用： p e t f i 网在现代制造业中的柔性制造系统( f m s ) 也有着比较广泛的应用：此外，p e t r i 网在编译和操作系统，并发和并行编程，决策模型，可编程逻辑和超大规模集成 电路阵列，异步电路和结构等领域也有着不同程度的应用。 随着信息处理系统的日益庞大和复杂化，人们越来越需要采用系统工程的方 法来设计和维护信息处理系统。在信息处理系统的整个生命周期内，采用图形化 的数学工具来完成系统的形式描述、系统的正确性验证、系统的目标实现和测试 是非常必要的。p e t r i 网是适应上述各项任务的有效工具，可以在一个p e t r i 网系 统模型的框架上完成各项任务。在这一点上，其他图形或数学工具是不具备这样 的功能的。 2 1 基于p e t r i 网的建模 用p e t “网描述、建模的系统有一个共同的特征：系统的动态行为表现为资源 ( 物质资源和信息资源) 的流动。 图2 1 ，2 2 用一个常见的化学反应式2 h 2 + 0 2 = 2 h 2 0 演示了p e t r i 网的基本运行 规则，图2 1 表示在该时刻有两个h 2 和两个0 2 ，图2 2 表示f 发射后的系统状态。 对比2 1 ，2 2 可知f 】5 l i 个h 2 和两个0 2 合成两个水分子h 2 0 。 h 2 图2 1 发射前 基于一类p e t r in e t 模型的初始状态配置与死锁检测 h 2 图2 2 发射厉 f 面以几个例子简单演示了p e t r i 网模型在其他几个领域中的应用。 1 哲学家就餐问题 哲学家就餐问题是一个进程通信中的典型问题。有五个哲学家围坐在一圆桌 旁，每人面前有一只空盘子，每两人之间放一支筷子。每个哲学家的行为是冥想， 感到饥饿，吃通心粉。无论如何，为了能吃到通心粉，任何一个哲学家都必须使 用两支筷子，因此，任何一个哲学家就必须拿起他左边和右边的筷子。当然，问 题在于如果每个哲学家都拾起他左边的筷子，并等待去拾取右边的筷子，他们就 会永远等待下去，一直吃不到通心粉( 产生了死锁) 。 图2 3 哲学家就餐问题的p e 伍网建模 第二章基于p e t r i 网的建模与分析 7 图2 3 表示了对于这个问题的p e t r i 网解决办法。库所c l c 5 分别代表五支 筷子。初始标识中这五个库所分别都含有一个托肯，这表示开始时筷子都是放好 的，没有被使用。每个哲学家则分别用m 和最来表示冥想和进食状态。对于一 个哲学家而言，要想从冥想状态变为进食状态，他左边和右边的筷子就都必须是 可以获得的。这样一个状态和过程可以通过p e t r i 网很容易的建模得到。 2 对运动小车的建模 图2 4 中( b ) 是对一个运动小车系统( a ) 的p c t r i 网建模。小车处于导轨之中，开 始向左运动，抵达a 端后，改变运动方向，向右运动直至b 端，到达后再改变方 向向左运动，如此在导轨内来回往复运动。 a a b - b 图2 4 ( a ) 一个小车运动系统( b ) 相应的p e l f i 网模型 向左运动 到达a 端 向右运动 到达b 端 3 一个简单的计算机数据处理系统 以下是一个从计算机数据处理系统中抽象出来的简单例子系统从输入设备中 接收数据，进行处理，并将处理完成的数据送入输出设备。 待处理数据首先出现在输入设备上，当处理器空闲并且在输入设备卜有数据 时，处理器丌始工作，处理数据。当数据处理完成后，数据被送入输出设备。此 时处理器则要么继续处理输入设备送来的数据，要么处于等待状态直到输入设备 送入设备。这个系统呵以使用p e l r i 网进行如图2 5 所示的建模。 基于一类p e t r in e i 模犁的初始状态配置与死锁检测 薮据被送入输出设备 图2 5 一个简单计算机数据处理系统的p e 砸网模型 4 柔性制造系统 图2 6 用p e t r i 网描述了一个简单的柔性制造系统，该系统包含两个进程，分 别为p l 节2 节3 曲，p l l - p l o - p 9 伽，三个加工工具p 5 ，p 6 ，p 7 ，每次可以加工一个工件。 以p e t “网作为模型来描述柔性制造系统，可以直观的分析系统的结构与行为，是 对f m s 进行设计，建模，仿真及性能分析的有力工具。本文中的工作就是以f m s 的p e t r i 网模型为对象展开研究的。 图2 6 一个柔性制造系统的p e tr i 网模型 第二章基于p e t r i 网的建模与分析 2 2p e t r i 网的分析技术 在p e t r i 网模型的基础上，其分析技术的研究也取得了长足进展，有代表性的 技术包括： 1 代数分析技术 代数分析技术主要以关联矩阵的形式对一个网系统的结构给予刻画，然后建 立状态可达的线性系统关系。这种分析途径的优点在于可以借助线性代数的有关 结果，简洁地展现p e t r i 网的一些性质，尤其是结构性质。当然，其作用是有限的， 难以很好地刻画系统动态特性。一般来说，它对可达性的刻画只是一个必要条件 而非充分条件，只有针对无冲突的子类才是充要的。 2 图分析技术 图分析技术是以一个有限的有向图( 树) ，直接展现个网系统的运行机制， 类似于一个状态机。它的优点在于能反映出一个网系统的动态行为和一些特征。 特别的，对一个有界p c t r i 网，它是一个准确刻画，而且对应一个有限状态机。然 而，对无界p c 埘网，它只能部分反映。 3 归纳分析技术 归纳分析技术是针对p e t r i 网的状态复杂性而提出的。一般来说，一个规模不 大的系统，可能会出现状态组合爆炸的危险，从而给系统分析带来困难，对此人 们提出了化简和分解的思想。化简是将一个较复杂的p e t “网简化成一个比较简单 的p e t r i 网而又要保留一些性质不变的同态变换过程，这个过程减少了可达状态空 间，通过对简单网的分析，能为理解原网的性质提供充分的信息。 分解的思想即是“分而治之”，是将一个复杂的网系统分解成若干较为简单的 网系统，分解过程也要保持一些性质不变。这样，通过分析简单的子网系统便可 了解复杂网系统。 此外，p e t r i 网理论研究的另一主流方向是建立在通用图论基础之上的并发行 为的特性研究。通用图论是从更为基础、更为抽象的网模型上探索系统的特性， 其中最为重要的就是并发性。 2 3 本章总结 本章简要介绍了利用p e t r i 网对系统建模以及常用的分析方法。 p e t r i 网对于系统设计与分析的实际应用，可以有几种方式来完成。一种方式 是将p e t r i 网视为一种辅助性的分析工具。在这种方式中，传统的设计技术被用于 1 0 基于一类p e t r in e t 模型的初始状态配置与死锁检测 建立系统。然后系统由p c t r i 网进行建模并分析。分析中出现的任何问题就都指出 了系统设计的缺陷。这时，系统设计就可以被修正以弥补缺陷。这个修正过的系 统可以再被建模和分析。这个循环可以一直进行下去直到分析不再发现问题。这 种方法如图2 7 所示。要指出的是，这种方式同样可被应用于对已有系统的分析。 圈2 7 系统，系统性质，p e 晡网模型关系 以上这种在系统设计过程中使用p e 埘网的传统方式要求在实际系统和p e 伍 网模型之间不断转换。在另一种更直接的方式中，系统的整个设计与规格说明的 过程都使用p e t r i 网来完成。分析技术只被恰当地应用于创造出一个无错误的p c 倒 网设计，然后问题就成为如何将这个p e t r i 网表示转换成一个实际的工作系统。 这两种在设计阶段使用p e t r i 网的方式为研究者提供了不同类型的许多问题。 一方面，建模技术必须能够将一个实际系统转换成一个p e t r i 网模型来表示。另一 方面，实际实现的技术也必须被研发使得p e t r i 网模型丁以被转换成实际的系统。 在这两个方面中，我们都需要各种分析技术来确定系统的各种性质。并在此基础 上对系统进行控制，运行和仿真。 本文中的工作主要是针对柔性制造系统( f m s ) 的一类p e t r i 网模型，使用直 接的方式展开研究的。 第三章p e t r i 网的基本定义与性质 第三章p e t ri 网的基本定义与性质 本章详细介绍了p e t r i 网的基本定义与基本性质【1 】【2 】【3 】【1 2 1 ，作为本文后面 章节内容中概念，性质和定理的基础理论准备。 3 1 基本定义 【定义2 1 】库所变迁网( 简称跗网) 是一个四元组，= ( p ，r ，f ，聊， 其中p 代表库所的集合，r 代表变迁的集合，并且p 和r 是有限非空和不相交的 集合；眶( p 乃u ( a p ) 称为有向弧集：渺n 蹦 0 ，称为，中弧上的权，胙 0 ，1 ， 2 ) 。称= ( p ，n ，叼为普通网( 0 i d i y e t ) ，当且仅当v 庠三f ，= 1 ，对 于普通网可以记做j v = ( p ，r ，d 。v p p ，v 框兀如果p ，f ) f ，且阡协，f ) = l ， 则称为普通p 丁网( 州r o r d i n 盯yn e t ) 。一个普通网肯定是一个普通p r 网。当可 = 0 ，0 f 研 1 时，称= ( p ，r ，聊为一般网( g c n e r a l n e t ) 。 【定义2 2 】令= ( p ，l ，聊是一个p e 嫡网，节点z p u r 的前置集定义 为k = ) p u r p ，z ) f 。其后置集定义为工= y p u 丁| 0 ，y ) n 。节点的集合 h p u r 的前置集( 后置集) 定义为= u d k 旧= l k 耐) 。 【定义2 3 】如果j v = ( 尸，t ，聊是普通网，且v f 丁，r 卅= | f i = 1 ，则称是 状态机r s t a t em a c h i n e ) 。 【定义2 4 】如果= ( p ，t ，f ，聊是普通网，并且有坳p ，i _ l = | p l - 1 ，则 称是标识图( m a r k e d 簪a p h ) 。 【定义2 5 】如果。个p e t r i 网系统( 肘o ) 的任意一个节点和其它节点中的任 意一个之间总存在一条连接路径则称该网是强连通的。 【定义2 6 】如果一个p e 晡网系统( 肘o ) 既是一个状态机又是强连通的，则 称其为强连通的状态机。 【定义2 7 】网= ( 尸，丁，f ，聊称为纯的，当月仅当，了0 ，y ) ( 尸7 ) u ( 取p ) ： 0 ，y ) n ( y ，) f 非纯网可以在保持动态性质不变的情况下化为纯网。下面要讨论的刚都是纯 网。 【定义2 8 】令j v = ( p ，n ，聊是一个网。 1 1 | v 的标识是映射肘：尸一； 基于一类p e 晡n e t 模型的初始状态配置与死锁检测 2 ) 一个变迁f 丁在m 下被称为使能的，记为m 阶当且仅当v p r ：肼p b 砰幼 f ) ； 3 ) 若m 【f ) 成立，则f 发射后，产生另一新标识m ，记为j ! l f 【f m ，有 im ( p ) 一矽( 另f ) 川小 嚣；：嚣嚣) + 肜。卯， lm ( p ) p 。小。 p “ p t n t 其它 4 ) 网从标识肘i 开始的所有可达标识的集合记为尺( ，肘o ) 或胁【) 。它是一个 最小集，即 忙只吖，蚴，旌r ( ， 锄 m 【f m 一m r ( ，蛳) ； 5 ) 当1 ，f 2 ，“丁时，s = f l f 2 “称为出现序列，当且仅当存在标识胁，m ， 慨满足坻【f 1 ) 溉： 6 ) 对于网j v 和标识 而，( ，肘i ) 称为一个网系统； 7 ) 网= ( p ，r ，f ，聊的关联矩阵定义为以p 和丁为序标的矩阵【m ：p 丁_ z ，z 是整数的集合，且 _ 形( b f )p 咖 c 川= 仁销k 吣p ，蓦? _ 10其它 【定义2 9 】令= ( p ，r ，聊是一个网， 如是的一个标识 1 ) 一个变迁f 在标识胁下是活的，当且仅当v m 目? ( j 】l 如) ，j 膨甘 ( 肘曲：肘协 成立： 2 ) ( ， 如) 具备死锁性，当且仅当，j f 丁：a 如【d 成立； 3 ) ( ，肘j ) 具备无死锁( 弱活) 性，当且仅当柜嘏( ， 南) ，了眶硎成立； 4 ) 系统在 ，0 下具备准活性，当且仅当在 如状态下v f l 埘 如 f 。 5 ) ( ， 知) 具备活性，当且仅当v f 7 1 ：f 在标识肘。下是活的，也即是v f 孔 v m 【 如 ：埘【 f ，m i f 。 6 ) ( ，m o ) 具备有界性，当且仅当孤d m 0 ) ，v f 尺( 朋o ) ，v p p ：m p ) 娃； 7 ) ( 如) 具备结构有界性，( ， ) 是有界的； 8 ) ( ， ，0 ) 具备结构活性，当且仅当j 如，( ， f 0 ) 是活的。 值得说明的是，对于资源有限的实际系统而言，它的p e t r i 网模型一般都是结 构有界的。所有元素均为o ( 1 ) 的列向量记为o ( 1 ) 。 【定义2 i o 】令= ( p ，r ，f ，阶是一个网。 1 ) 以p 为序标的列向量y ：j p z 称为j v 的尸向量。 第三章p e t r i 网的基本定义与性质 2 ) 以r 为序标的列向量，：z 兮z 称为的耳向量。 3 ) 称p - 向量j 足一个p - 不变式( 库所不变式) 当且仅当h o 且，1 m = 0 1 。 j j _ p p i f o 称为j 的支撑。 4 ) 称一个p - 不变式是极小的当且仅当它的支撑中不包含任何其它p - 不变式的支 撑。本文中的尸不变式，如果没有特别声明，则都是极小p 不变式。 5 ) 称n 向量，是一个l 不变式( 变迁不变式) 当且仅当 o 且m 啦o 。 i l ，l | _ f 姐0 0 称为，的支撑。 6 ) 称是被b 彳i 变式，( d 不变式 ，) 覆盖的当且仅当v p p ：眄，卜o ( v t r ，( f ) - o ) 。 被p 一不变式覆盖的的网也称为是保守的。 【定义2 1 l 】( ， 如) 是一个网系统，= ( p ，nf ，叻。 1 ) 称一个非空集合s p 是一个信标( s i p h o n ) ，当且仅当各s 成立： 2 ) 称一个非空集合s p 是一个陷阱( t r a p ) ，当且仅当0 r 成立； 3 ) 称一个信标( 陷阱) 是极小的，当且仅当不存在其它信标( 陷阱) 是它的真子集； 4 ) 称p p 是被标识m 标记的，当且仅当朋p ) o 。称一个集合s p 是被标识肘 标记的，当且仅当s 中至少有一个元素被m 标记。s 中的托肯数( 令牌数) m = e 洲p ) ； 5 ) 不包含任何p 不变式支撑的信标称为严格信标。一个严格信标有可能被清空； 一个既是极小的，又是严格的信标，称为严格极小信标( s m s ) 。 3 2 基本性质 【性质2 1 】刚系统( ，胁) ，j 是= ( p ，l ，聊的一个p 不变式，v 心( ， m 由：1 1 m = 1 1 m o 。 【性质2 2 】网系统( 眠) ，是= ( p ，lf ，聊的一个l 不变式，0 ，0 中 所有的变迁发射一次，可能会使网系统回到初始标识。 【性质2 3 】网系统( 炳) = ( p ，r ，f ，聊，题p 是一个信标，若勤托琥( ， 朋r o ) ：肘= o ，则s 以后永远不会被标记，称为被清窄。 【性质2 4 】网系统( j | i f o ) ，= c 尸，l ，聊，5 p 是一个陷阱，若孙挺琥( 如) ，肘 o ，则s 以后总是被标记。 【性质2 s 】网= ( p ，f ，f ，聊的p - 不变式j 的支撑i i 圳既是一个信标又是 一个陷阱。 【性质2 6 】( m 肘o ) 是一个网系统，其中= ( p ，l 只聊，j 是一个p 一不变 式，s 凹是j v 的一个信标，那么此信标s 是在梳下被p 不变式j 控制的，当且仅当 j _ 。 o 且对于所有的p 尸岱，j p ) = 0 成立，或等同地，。 如 o 且 1 4基于一类p e t r in e t 模型的初始状态配置与死锁检测 p p 【，p ) o 。如果s 是一个在 如下被p 不变式j r 控制的信标，则s 不可能被 清空，也就是沈啪r ( ，m o ) ：s 在标识 如下是被标记的。 【性质2 7 】( ， 而) 是一个普通网系统，j v = ( p ，ld ，若在j 】l f 下是死( 锁) 的， 则所有未被标记的库所形成一个信标；如果网中没有信标可能被清空，则称， 而) 是无死锁的( d e a d l o c k 行c c ) 。 【性质2 8 】对于普通网系统( ， 幻，= ( p ，l 毋，死锁的必要条件是所有的 极小信标都被清空； 该性质是一般死锁分析方法的基础。需要说明的是，本中主要讨论普通有界 网。除非特别说明，下文提到的网模型是普通有界网。 3 3 本章总结 本章主要对p e t r i 网的基本定义和基本概念进行了叙述，为本文后面章节中的 活性判定，通过系统初始标识配置来避免系统死锁和从未被标识的极大信标中求 取极小信标的算法做了理论上的准备。 第四章s 3 p r 网及其子类l 5 3 p r 网 第四章s 3 p r 网及其子类l s 3 p r 网 s 3 p r 网及其子类l 厂s 3 p r 网模型是被广泛应用于柔性制造系统( f 1 e x i b l e m 如u f a c t u r i n gs y s t e m ，f m s ) 建模分析的一类p e 仃i 网模型。在本章中，主要从 网模型结构的定义和性质的方面，对l s 3 p r 网和其父类s 3 p r 网模型进行介绍。 在后面的章节中，l 厂s 3 p r 网中的性质被推广应用到其父类s 3 p r 网模型中。 4 1 结构与性质 带有资源的简单加工进程系统( n es y s t c mo fs i m p l ep r o c e s sw i l hr c s o u r c e s ， s 3 p r ) 是一类广泛应用于对柔性制造系统建模的p c 硒网模型。 【定义4 1 】一个简单加工进程( s i l p l cs c q u e m i a lp m c c s s ) s 2 p 是一个p e 埘网 = ( p up o ，l 叼， 如是j v 的初始标识，p o 称为闲置库所( 加工进程的开始和结束 工序状态) ，p p 称为工序状态库所。以肘j ) 满足以下条件： ( 1 ) 中，幽以胁p 协1 ，坳p 劬= o ； ( 2 ) 是一个强连通的状态机，即v f 霉| f l = = 1 ； ( 3 ) n 的每一个回路包含矿。 i l凸 图4 1 两个s 2 p 1 6基于一类p e 埘n e t 模型的初始状态配置与死锁检测 【定义4 2 】一个拥有资源的简单加工进程2 pw i t hr e s o u r c e s ) s 2 p r 是一个 网j v = ( p u 妇o u 靠，l d ，肘j 是的初始标识。( ， 幻) 满足以下条件：( 1 ) 令 p = p o ) ，由：r _ p u 伽o ) u f 生成的子网扛( 圾，脚是一个s 2 p ，其中即p u 矿 ， 7 扣t 脚n ( 蹦z 曲；( 2 ) r 艮称为资源，靠是资源的集合，靠_ f ，( p u 仞o ) ) n 如= f ；( 3 ) v p 只v f ，v f ，了_ 、。f n 如= f ”广b f r p ；( 4 ) v r 靠，胁( r ) 芑1 ；v ，“r n 尸- ，”n p 印；v r 艮，。r n r 廿；( 5 ) 一p o ) n 砾= p o ) 一n p r = ，；( 6 ) 对于 一个给定的，艮，嘶) = ( ”，) n p 称为资源，的持有者集合。对于一个资源集合m = r ， r 2 ，r 。) ，用u h ( r ) i r 毗) 或u e g 口珩) 表示h ( r 1 ) u 爿( r 2 ) u u 日( ) 。 图4 2 两个s 2 p r 【定义4 - 3 】一个拥有资源的简单加工进程系统( s y s t e mo fs 2 p r ) s 3 p r 是 t ( d m o ) 个s 2 p r 通过共享资源复合而成的p e t r i 网= q ：1 = 妒u u 件，td 。 记帆= 1 ，2 ， 。s 3 p r 网系统( ， 而) 满足以下条件： ( 1 ) 一个s 2 p r 也是一个特殊的s 3 p r ； ( 2 ) v f m ，m f ) ，( p i u 以) v l 畔) = 蛾月存在f k 峨= 尸c 泸f ，玎1 乃= 霞 ( 3 ) p _ u f ：1 只，尸o = u 扛l 以，段= u ；k u 正? f - u 。l r ； ( 4 ) v f 坼，v p u 尸l ，m 妇) = 如0 ) ；v i 土，v r 岛。p 叫，( r ) = ( r ) ；v ，日? 叫 蛳( ，) = 麟 肘0 1 ( ，) ，肘脏( ，) ) ； ( 5 ) 符号瓯表示组成第f 个s 2 p r 网j 的s 2 p 。 第四章s 3 p r 网及其子类l s 3 p r 网 图4 3 一个s 3 p r p l l 【定义4 4 】设一个s 3 p r 网系统( 肘o ) ，其中 k ( p l 一旧r ，l 司，s 是网 的个信标。靠表示信标s 中的资源，岛舒n 段；昂表示信标s 中的工序状态 库所，s n p 。明显地，s = 靠u 昂。 对于一组资源y _ r 1 ，r 2 ，h ) ，使用它的这组操作库所记做上廿1 ) u 矾r 2 ) u l 胤) 或被简记作u 一讲( r ) 。在【6 】中证明了如果s 3 p r 的信标s 不含有p 不变 式的支撑，则有峪厂烁i 1 为真。此外还有： ( 1 )v f 1 ，2 ，七 ，v r 昂，只u 以) 和嘶) u ，) 是s 3 p r 网一个p 不变 式的支撑。 ( 2 )设5 劫u 品是一个严格极小信标，其中岛= ，1 ，r 2 ，h ) 。则有： v ，p 【叫，j f 1 ，2 ，以) ，p 研f ) 并且w 1 ，2 ，n 0 ) ，p 凹( 0 ) 。 ( 3 )假设存在一个严格极小信标s ，吲u s 是一个p 不变式的支撑。 在s 3 p r 网模型中，每个严格极小信标都有可能在系统运行的过程中被清空。 l s 3 p r 是s 3 p r 网模型的一个子类。l s 3 p r 由一组持有并释放一组共享资源 的状态机所组成。每个状态机不包含任何的分支选择。 【定义4 5 】一个线性s 3 p r 网( l s 3 p r ) = 僻l 毋是一类满足如下条件的 普通网。 1 ) p = p u 尸0 u 尸_ r ，其中 1 8基r 一类p e t r in e i 模型的初始状态配置与，e 锁检测 n ) p = 伽1 0 ，p ，) b o 彬p = u 气：p j ，w h e r ep l n 毋= f ，f o ra nf 身 c j 尸r = ，1 ，m ) ，m 0 2 ) 7 - u i ：1 正，其中露n 乃= f ，f 身。 3 ) v j 1 ，埘，由 p ， u 靠u 噩产生的子网是一个强连通的状态机，且每 个回路包含扫f 0 ，且v p p f ，i p l - 1 a 4 ) 1 ，) ，v p 只，乍n 靠印”n 斥并且l 甲n 靠i - l 。 5 ) 该网是强连通的。 在下面一个小节中结合一个简单的实际系统建立了一个l 广s 3 p r 模型。 图4 4 一个带分支的s 3 p r 网模型 7 正是因为旌加在l s 3 p r 网模型上的约束i p i - 1 ，以及其持有和使用资源的方 式的原因，我们称其为“线性( “n e a r ) ”s 3 p r 网模型。在r 面的图4 5 中我们从 结构的角度对几个不同的网模型进行了比较。 第四章s 3 p r 网及其子类l s 3 p r 网 a )b )c )d ) 图4 5 几个不同结构的处理进程 为了简洁