（机械电子工程专业论文）结构简化的petri网活性控制器设计.pdf

摘要 信标的重要性在p e t r i 网的死锁预防分析和控制中已经被充分地认识。本论文 就是致力于研究一般p e t d 网系统，并以其一种特殊子类s 4 p r 在柔性制造系统中 的死锁问题为例，提出了一种基于信标的结构简化的活性控制器设计方法。同时， 该方法具有一定的普遍性可以将其应用到一般p c t r i 网的其它特殊子类中。 在本论文中我们依据以前的工作，首先将一个原始的网模型中的信标区分为 基本信标和从属信标，然后通过只给每一个基本信标添加控制库所使其满足最大 可控信标的性质从而使网模型具有活性，以达到结构简化的设计目的。同时发展 了基本信标最大可控则从属信标也最大可控的条件，即通过线性整数规划使原网 模型中的基本信标有适合的控制深度变量从而确保从属信标的最大可控性。与现 有的死锁预防方法相比，本论文的方法只需加入少量的控制库所，且可避免不必 要的迭代过程。 关键词：p e t r i 网死锁预防基本信标柔性制造系统线性整数规划 a b s t r a c t t h ei m p o r t a n c eo fs i p h o n si sw e l lr e c o g n i z e di nt h ea n a l y s i sa n dc o n t r o lo f d e a d l o c kp r e v e n t i o ni np e t r in e t s t h i st h e s i si n v e s t i g a t e sg e n e r a l i z e dp e t r in e t sa n d g i v es 4 p r , ac l a s so fg e n e r a l i z e dp e t r in e t s ，w h i c hc a nw e l lm o d e lal a r g ec l a s so f f l e x i b l em a n u f a c t u r i n gs y s t e m s m s ) a sa ne x a m p l e ，a n dp r o p o s e sam e t h o do f d e s i g n i n g as t r u c t u r a l l ys i m p l el i v e n e s s - e n f o r c i n gp e t r in e ts u p e r v i s o r o t h e r w i s e ，t h i sm e t h o dc a n b ee x t e n d e dt oo t h e rc l a s so f g e n e r a l i z e dp e t r in e t s a o c o r d l n gt oo u rp r e v i o u sw o r k s ，w ed i v i d es i p h o n si nap l a n tn e tm o d e li n t o e l e m e n t a r ya n dd e p e n d e n to n e s d e a d l o c kp r e v e n t i o ni sa c h i e v e db ya d d i n gm o n i t o r s ( c o n t r o lp h c e s ) t om a k ee v e r ye l e m e n t a r ys i p h o ns a t i s f yt h em a x i m a lc o n t r o l l e d - s i p h o n p r o p e r t y c o n d i t i o n sa r ed e v e l o p e du n d e rw h i c had e p e n d e n ts i p h o ni sm a x i m a l l y c o n t r o l l e dw h e ni t se l e m e n t a r ys i p h o n sa l es o t h em a x - c o n t r o l l a b i l i t yo fad e p e n d e n t s i p h o ni se n s u r e db yp r o p e r l ys u p e r v i s i n gt h ec o n t r o ld e p t hv a r i a b l e so fi t se l e m e n t a r y s i p h o n sv i al i n e a ri n t e g e rp r o g r a m m i n gt e c h n i q u e s c o m p a r e dw i t h t h ee x i s t i n g m e t h o d s ，t h ea d v a n t a g eo fo u r si st h a tam u c hs m a l l e rn u m b e ro fs u p e r v i s o r ym o n i t o r s i sa d d e da n du n n e c e s s a r yi t e r a t i v ep r o c e s s e sa r ea v o i d e d k e y w o r d s ：p e t r i n e td e a d l o c kp r e v e n t i o n e l e m e n t a r ys i p h o n f 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 l i n e a ri n t e g e rp r o g r a m m i n g 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：土兰挺显 日期 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证 毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本人签孤趣量一 导师签名 第一章绪论 1 1 研究背景与意义 随着社会的进步和生活水平的提高，社会对产品多样化，低制造成本及短制造 周期等需求日趋迫切，传统的制造技术已不能满足市场对多品种小批量，更具特色 符合顾客个人要求样式和功能的产品的需求。9 0 年代后，由于微电子技术、计算机 技术、通信技术、机械与控制设备的发展，制造业自动化进入一个崭新的时代，技 术日臻成熟。市场环境决定着企业的生产方式，制造企业需要以最快的上市速度， 最好的质量、最低的成本、最优的服务及最清洁的环境来满足不同客户对产品的 需求和社会可持续发展的要求。在这一目标的驱动下，多种先进制造技术( a d v a n c e d m a n u f a c t u r i n g t e c h n o l o g y ，a m t ) 被提出，并受到重点研究和发展。柔性制造系统 ( f l e x i b l em a n u f a c t u r i n gs y s t e m ，f m s ) 是a m t 发展的产物，受到了普遍的研究， 并在制造企业得到大量应用。f m s 通常包括若干数控设备、中央刀库、物料运输 装置和计算机控制系统等子设备或予系统，由控制网络将多个设备有机联合，使 各设备统一调度、相互协调共同完成生产加工任务，并可以根据制造任务或生产 环境的变化进行灵活调整。这种灵活性即指系统的柔性，柔性是f m s 的最大特点， 其具有应变性好、生产率高，适应中、小批量生产等特点。 图1 1 为一个柔性制造系统( f m s ) ，其加工系统由三台机床、一台检查装置 和集中切屑处理装置构成，物流系统由有轨小车、工件存储、工件识别、工件准 备站等装置构成。毛坯根据生产计划在准备站从几个到几十个为一批装在一个料 箱内，通过有轨小车送往各加工设备。 图1 1 一个柔性制造系统样例 2 柔性制造系统是一个具有同时处理多种零件能力的计算机控制的生产系统。 它的特点是：可以同时完成不同零件、不同工序的制造任务；各制造设备之间是通 过物料的自动输送、自动加工，大大缩短了占9 5 的无机器加工时间；整个物流 系统由计算机集成控制和集中监视，能在不停机调整的情况下以最短时间向另一 种零件转换。这些特点表明f m s 具有更大的柔性，进一步提高了设备利用率，缩 短了生产周期，降低了制造成本。f m s 的出现改变了传统生产方式。生产设备在 时间上和空间上是兼容的，即加工对象不断改变时，只改变生产信息，而原生产 设备不变( 时间柔性) ；且同一种制造系统可同时制造不同的加工对象( 空间柔性) 。 这些正是多品种、中小批量生产所要求的生产方式。然而，集计算机辅助设计( c a d ) 技术、机电一体化技术、模糊控制技术、模糊数学、人工智能、专家系统技术和 人工神经网络( a n n ) 技术于一体的f m s 为了适应市场的需要变得日益复杂，从单 一进程的串行系统到多个进程的并行系统，从基于单机环境下的操作到网络并行 环境下的机群操作等等。而具备并发、异步、离散、并行、时变和随机特征的复 杂f m s 给设计者带来了更为严峻的挑战。死锁是f m s 设计者们不可回避的问题。 如何采用科学的数学、图形模型来动态地描述实际的f m s ，实现优化无死锁的高 生产效率的f m s 是工程设计者们所面临的主要课题。 通常，f m s 由一系列的工作站和柔性的传输系统所组成，工件通过运输系统 得到加载、传输和卸载并且在工作站加工。不同类型的毛坯离散地进入系统，利用 有限的资源( 如机床、机器人、夹具、运载小车、传送带等) 按照既定的加工进程( 由 一系列工序组成) 进行加工。工件也可以根据当前系统实时状态灵活地选择加工进 程，这样就造成众多的不同加工进程并行共存于f m s 中，从而来竞争有限的共享 资源。如果有限的共享资源不能得到合理的分配，必然会产生各个进程忙于抢占 系统资源，同时每一个进程都不能满足自身的资源申请，从而造成部分进程不能 进行或者使所有进程都停止不前，即系统陷入了局部死锁或者是全局死锁状态， 严重地影响了系统的动态性能，降低了系统的生产效率。因此设计人员需要建立 系统的抽象模型，研究死锁发生的机理，进而防止系统死锁的发生，也即提出有 效的控制死锁发生的策略。国内外的专家学者在这一方面进行了广泛深入的研究， 如串行处理的串演系统( 如经典自动机模型，卜演算模型，p o g t - 系统模型等) 、并行 处理系统的系统( p e t r i 网、c s p 、c c s 等) 。本文以p e 砸网模型来动态地模拟f m s ， 提出了结构简化的活性控制器设计方法。 1 2p e t r i 网的研究和应用现状 1 9 6 7 年柔性系统( f m p - f l e x i b l em a n u f a c t u r i n gs y s t e m ) 在英国的诞生标志 着现代制造科技进入了一个全新的时代。随着计算机技术和机电一体化技术的飞 第一章绪论 3 速发展，出现计算机集成制造系统( c i m s - - c o m p u t e ri n t e g r a t e dm a n u f a c t u r i n g s y s t e m ) 并迅速向纵深发展，f m s 己跳出传统概念局限，被定义为广义上的可编程 控制系统，具有自动物流和高层次分布数据的能力。但f m s 是一个由物流和信息 流组成的技术密集，耗资较大的复杂的自动系统。充分发挥其潜在优势，要求数 据技术尽可能完整地渗透到系统中去，以适应提高柔性和增强功能两方面的要求。 而p e t r i 网的特点正适合于像f m s 这种复杂系统的建模、仿真与控制。 p e t r i 网是分布式系统的建模和分析工具。它特别便于描述系统中进程或部件 的顺序、并发、冲突以及同步等关系。同其他系统网模型相比较，对真并发的确 切描述是p e t r i 网的独特优势。 p e t r i 网的概念是1 9 6 2 年由德国科学家c a r la d a mp e t r i 在他的博士论文 “k o m m u n i k a t i o nm i ta u t o m a t e n ”( 用自动机通信) 中首次提出的。为了使并发这 一概念直观化，论文中提出了一种用于描述物理进程和物理系统的组合的网状模 型。由此发展起来的一类系统模型，后来被人们称之为p e t r i 网。2 0 世纪7 0 年代 初，p e t r i 网的概念和思想方法受到欧美学者的广泛关注。对p e t r i 网的各种性质的 研究，以及把p e t r i 网应用于各种实际系统的建模和性质分析的论文和研究报告开 始大量涌现。经过4 0 多年的发展，不仅p e t r i 网理论本身已形成一门系统的、独立 的学科分支，而且p e t r i 网在计算机科学技术( 如操作系统、并行编译、网络协议、 软件工程、形式语义、人工智能等) ，自动化科学技术( 如离散事件动态系统、混 杂系统等) ，机械设计与制造( 如柔性制造系统) ，以及其他许多科学技术领域， 都得到广泛的应用。p e 砸网是一种系统的数学和图形的描述与分析工具。对于具 有并发、异步、分布、并行、不确定性和随机性的信息处理系统，都可以利用这 种工具构造出要开发的p e t r i 网模型，然后对其进行分析，即可得到有关系统结构 和动态行为方面的信息，根据这些信息就可以对要开发的系统进行评价和改进， 因此具有很好的工程应用前景。目前，p e t r i 网最为成功的应用领域当属系统性能 的评估与通信网络协议的分析。p e t r i 网作为一种图形工具，像软件设计中的结构 图、流程图一样，直观、形象，而且在这些网中，可以使用标记( t o k e n ) 来模拟系统 的动态行为和并发活动。作为一种数学工具，p e t r i 网可以建立状态方程、代数方 程以及系统行为的其他数学模型。数学方法的好处就是系统的数学方程一旦建立， 就便于计算和验证，所以对于p e t r i 网，实际工作者和理论工作者都可以根据需要 加以利用。同时，p e t r i 网为他们之间的沟通和交流提供了一个强有力的终结，即 实际工作者可以从理论工作者那里学到如何使他们的建模更加条理化，而理论工 作者可以从实际工作者那里学到如何使他们的建模更加实用化。随着实际系统提 出更高的模拟要求，从事p e t r i 网理论研究的专家们不断的扩充其模型，具有代表 性的p e r t i 网模型有：高级p e t r i 网( 1 1 i g l l 1 e v e lp e t r in e t ) t 1 】【2 】1 3 1 ；增广p e r t in e t ( e x t e n d e d p e t r in e t ) t 4 1 ；时间时延p e t r in e t ( t i m e t i m e dp e t r in e t ) t 1 ；受控p e t r in e t ( c o n t r o l l e dp e t r i 4 n e d f 6 】等。在p e t r i 网模型的基础上，其分析技术也取得了长足的发展，有代表性的 技术包括：代数分析技术川，图形分析技术8 j 和归纳分析技术嘲。 1 3 f m s 系统的死锁研究现状 系统的死锁一直是困扰f m s 系统设计者的一个棘手的问题。这个问题对于复 杂的并行f m s 而言，尤其突出。许多专家学者在这一方面做了大量的研究工作。 通常死锁可以分为全局死锁和局部死锁两种，前者影响系统所有的状态，后 者仅影响系统部分的状态。死锁和相关的阻塞情况经常造成不必要的成本浪费， 诸如长期的待料停工和一些昂贵资源的低使用率，甚至在一些商精度自动化制造 系统中造成灾难性的后果，如半导体制造系统。并行f m s 系统共享有限的资源， 资源的不合理分配就可能造成上述死锁的出现，降低系统的生产效率。 假设死锁是由于进程竞争资源而引起的，我们下面给出死锁发生的四个必要 条件，这四个条件是c o f f m a n 首先提出的，所以也称为c o f f m a n 条件【1 0 l ： ( 1 ) 资源独占( m u t u a le x c l u s i o n ) ：一个资源在同一时刻只能分配给一个进程 如果某一进程申请某一资源，而该资源正被另外某一进程所占有，则申请者需等 待，直到占有者释放该资源； ( 2 ) 不可剥夺( n o p r e e m p t i o n ) ：资源申请者不能强行地从资源占有者手中夺取 资源，即资源只能由其占有者在使用完后自愿地释放； ( 3 ) 保持申请( h o l da n dw a i t ) ：进程在占有部分资源后还可申请新的资源，而且 在申请新资源的时候并不释放它已经占有的资源； ( 4 ) 循环等待( c i r c u l a r w a i t ) ：存在一个进程等待序列 p l ，p 2 ，p n ) ，其中p l 等 待p 2 所占有的某一资源，p 2 等待p 3 所占有的某一资源，p n 等待p l 所占有 的某一资源。 当且仅当上述四个条件同时满足时，死锁才会发生。换言之，只要破坏上述 四个条件中的任意一个，死锁就不会发生。 通常专家学者通过控制系统资源的分配来破坏不同进程问循环等待的条件， 从而解决系统中的死锁，相关的死锁解决策略也是基于这种思想。这些策略大致可 分为以下几类：死锁检测和恢复策略、死锁避免策略、死锁预防策略。 1 死锁检测和恢复1 1 1 1 1 1 2 这种方法允许死锁的发生，一旦检测到系统发生了死锁，检测系统测定所涉 及到的资源并且重新分配这些资源来恢复系统的状态。这种方法往往会达到较高 的生产率和资源利用率，但控制工程师必须对可能发生死锁的生产环节有充分的 认识，在设计单机( 如机器人，机床) 控制器时，需要设计相应的控制程序以便解锁 时应用。此外，可能还需要一些附加的设备供解锁时使用，其结果又是要加大投 第一章绪论 入。 2 死锁避免1 1 3 1 - 1 1 _ 7 】 死锁避免通过不断地搜索系统的可达状态来取得死锁控制的目的。根据该算 法，系统每运行一步，即由控制系统判断系统选择可达图的何种分支不会导致死 锁，并沿该分支继续运行下去，反之，则不选择该分支，从而达到远离死锁状态 的效果，即采用了该算法。死锁避免算法的优点在于系统可以具有最大许可的控 制效果，也就是说除了危险节点及死锁节点外，受控系统保留了全部的好的状态， 在实际的并发系统中，这意味着系统运行效率得到了最大程度的保留。但是，死 锁避免算法也具有必须事先计算系统的可达状态图的缺点。而在p e t r i 网系统中， 系统的可达状态具有爆炸性的特点，也就是说，其可达状态数随着网规模的增大 呈现指数级的增长趋势。这使得即使在一些中等规模的网系统中，该算法的实现 都是极其不现实的。 3 死锁预防1 1 8 1 【3 l 】 死锁预防策略是基于信标理论的一种死锁控制思想。这种方法从逻辑上保证 了系统中不会出现死锁，因而不必再去控制系统运行过程中对资源的申请。该策 略要向f m s 系统添加控制策略或者通过离线的机构控制资源的分配从而保证系统 的所有进程得以顺利进行。我们希望系统的离线静态控制策略一旦建立就可以保 证系统不会出现死锁状态。根据该思想，死锁是由于系统中的信标被清空而引起 的，只要控制该系统中的所有的严格极小信标使之不被清空则该网系统就不会出 现死锁。 基于p e t r i 网系统的死锁问题研究取得了不少成果，但是仍然有许多问题需要 进一步研究和解决。此外许多控制方法和策略对系统的行为施加了过多的限制， 降低了系统的性能。近年来出现的死锁预防方法大都采用在目标p e t r i 网模型增加 控制库所限制网系统的行为，来保证网系统是无死锁的。【1 8 l 中e z p e l e t a 提出了针 对普通网的子类一s 3 p r 的死锁预防策略，把死锁和严格极小信标( 简记为s m s ) 一一 对应起来，通过对每一个s m s 添加监控器来保证网系统的活性。该算法具有不需 要计算系统的可达状态的优点，但是其缺点也是十分明显的，首先，通过添加控 制库所，危险的尤其是死锁节点去除的同时，一部分好的节点也会被去除，从而 使得目标网系统的运行效率受到影响。其次，由于在网系统中，s m s 的个数也是 与网规模的大小成指数关系增加的，所以对于大型网系统而言我们需要添加大量 的监督器和连接弧，从而使得控制器的设计变得复杂，甚至难以实现。论文致力 于死锁预防方法的研究，通过分析p e t r i 网的结构特性，完成了结构简化的死锁预 防策略的基础性理论研究，运用代数的方法保证系统的p e t r i 网模型的活性。 6 1 4 本文完成的主要工作 本文主要致力于p e t r i 网的一般网系统死锁预防策略的研究。其中主要引入了 两大理论：基本信标理论和信标最大可控性理论，在这两种基本理论的基础上开 发的结构简化的活性控制器可以有效的预防死锁发生，提高f m s 系统的动态性能。 我们的研究对象主要是p e t r i 网一个特殊的子类s 4 p r ( s y s t e m s o f s e q u e n t i a ls y s t e m s w i t hs h a r e dr e s o u r c e s ) 。s 4 p r t 2 3 1 没有任何的特定含义。这一特殊子类是s 3 p r | 1 8 】网 ( s y s t e m so f s i m p l es e q u e n t i a lp r o c e s s e sw i t hr e s o u r c e s ) 的一般化。国外相关学者已经 对该特殊p e t r i 网子类做了比较详细的定义和描述。s 4 p r 网系统可以有效地模拟工 序对多个多类型的资源申请的完全顺序加工系统，这意味着该网系统是比普通网 系统更复杂的一般网系统。 本文基于基本信标理论和信标最大可控性理论提出了结构简化的活性控制器 设计方法。以前采用的死锁预防策略多是对每一个严格极小信标添加控制器来保 证系统的无死锁性的，它仅适用于规模较小的网系统，对于大型网系统而吉，由 于严格极小信标的数量是随网的规模呈现指数递增，这意味着所要添加的控制器 数量也将随之呈现指数递增，这样会使得受控网系统更加复杂化，难以控制。我 们依据信标的特征向量的线性相关性将严格极小信标分为基本信标和从属信 标，从而引入了基本信标理论。该理论能大大减少控制器的设计数量，简化受控 系统的复杂度。该理论的核心就是只需要为基本信标添加控制器，并且通过调节 控制器的初始标识来控制从属信标的可控性，不需要对每一个严格极小信标添加 控制器就可以保证系统无死锁性。该方法将添加控制库所的初始标识用含有控制 深度参数( 1 ) 的变量表达式来设定，通过保证基本信标最大可控性而获得该变量的 约束条件；随后检验从属信标的最大可控性，获得满足从属信标最大可控的控制 深度变量的约束条件；因为控制深度变量越小就意味着对系统的约束就越小，所 以对该变量建立优化函数来保证系统获得最优控制。利用线性整数规划对变量进 行优化，优化过程可以直接避免从属信标最大可控性的重复性验证，可以一次性 获得满足系统最大可控性的控制器中的初始标识，从而优化了算法。最后，结合 s 4 p r 网系统的结构特性，就可以得到结构简化的且活的网系统。该方法可以推广 到一般p e t r i 网中使用，例如e s 3 p r l 3 2 】1 3 3 1 ，g s y s t e m l 3 4 】等。 总之，本文主要致力于p e l r i 网的一般网系统死锁预防策略的研究，提出了基 于基本信标和信标最大可控的结构简化的活性控制器设计方法，通过实例验证可 以看出取得了较好的控制效果，具有一定的工程应用前景。相信我的工作会对一 般p e 埘网死锁预防控制策略的研究起到进一步的丰富和促进作用。限于时间、条 件和个人的认识，文中难免有一定的欠缺，恳请批评指正。 第二章p e t r i 网理论初步和系统建模分析 本章主要介绍了p e t r i 网的基本概念、性质以及系统的建模分析，为本文后面 几章的命题、定理做了必要的准备。详细的例子以及证明可以参考【3 5 1 1 3 6 】 2 1p e t r i 网理论初步 2 1 1p e t r i 网的基本定义 【定义2 1 】库所变迁网( 简称p 厂r 网) 是一个四元组，表为n = f p ，t ，f ，w ) ， 其中p 代表库所的集合，用圆圈表示；t 代表变迁的集合，用长方框表示；p 和t 是有限集合，并且p 翊，辟o ，p n r r - a ；f x t ) u ( l x p ) 称为有向弧集：w ：f j 肌 o 称为f 中弧上的权，i n = 0 ，1 ，2 ，n 。 当且仅当v f e f ，w ( f r l ，称n = 口，t ，f ，w ) 为普通网( o r d i n a r yn e t ) ，可以记作 n = ( p ，t ，f ) 。v p e p ，v t t ，如果0 ，d f ，且w ( p ，t ) = l ，则称n 为普通p 厂r 网口厂r o r d i n a r y n e t s ) 。一个普通网肯定是一个普通p 厂r 网。3 f = ( p ，0 e f , w ( 0 i 时，称n = 口， t ，f ，聊为一般网( g e l l e r a l i z e dn e t s ) 。 【定义2 2 】令n = 吧t ，f ，w ) 是一个网，n 的标识是映射m ：p - - * i n ，m 表示库所p 中的托肯数，托肯用实心圆点或数字表示：给定s c p u t ，则m ( s 声 p s m 0 ) ) ；称( n ，m o ) 为网系统或标识网，其中m o 为网n 的初始标识。 【定义2 3 】设n = ( p ，t ，f ，w ) 是一个p e t r i 网，节点x e p u t 的前置集定义为 x = y p u ti ( y ，x ) f ) 。其后置集定义为x = y e p w ti ( x ，y ) e f ) 。将该定义进一步 推广为节点的集合，即h e p u t 的前置集( 后置集) 定义为气 。h x ( h 气j x 。h x ) 。 【定义2 4 】设n = t ，f ，w ) 是一个p e t r i 网，v p e p , 令m a x p = m a x t 。p w ，t ) ) ， m i n p = m i n t 。p w t ) ) ，m a x p = m a x t 。p w ( t ，p ) ) ，m i n p = m i m 。p w 化p ) 。如果网是 无阻塞当且仅当v p p ，p o 并且m i n 芦v l i 蚰。如果网是强无阻塞当且仅当v p e p , p o 并且m i n 岔_ m a x , 。 【定义2 5 】如果n 气p ，t ，f ，w ) 是普通网，i 寻v t e t ，i 。t l = l t l = l ，则称n 是状 态机( s t a t em a c h i n e ) 。 【定义2 6 】如果n = ( p ，t ，f ，w ) 是普通网，并且有v p e p ，i p 卜l p 户l ，则称n 是标识图( m a r k e dg r a p h ) 。 【定义2 7 】如果一个p e t r i 网( n ，m o ) 的任意一个节点和其它节点中的任意一 个之间总存在一条连接路径，则称该网是强连通的。 【定义2 8 】如果一个p e t r i 网( n ，m o ) 既是一个状态机又是强连通的，则称其 为强连通的状态机。 【定义2 9 】称网n = ( 只t ，f ，w ) 为纯的，当且仅当_ 1 j ( x ，y ) ( p t ) u ( t x p ) ：( x ， y ) e f a ( y , x ) f 。 非纯网可以在保持动态性质不变的情况下转化为纯网，下面讨论的网都是纯 网。 【定义2 1 0 1 设n = ( p ，t ，f ，w ) 是一个网。 1 ) n 的标识是映射m ：p - - m n ； 2 ) 一个变迁t t 在m 下是使能的，记为m 【t ) ，当且仅当v p 、：m w ( p ，t ) ； 3 ) 若m t ) 成立，则t 发射后，产生另一新标识m ，记为m t ) m ，有 朋( p ) = m ( p ) 一w ( p ，t ) m ( p ) + w ( p ，t ) m ( p ) 一w ( p ，t ) + w ( t , p ) m ( p ) p t 、t + p t 、。t p 。t n t 。 其它 4 ) 网n 从标识m o 开始的所有可达标识的集合记为r ( n ，m o ) 或m o d 。它是一个最小 集，即m o r ( n ，m o ) ，m e r ( n ，m o ) a m t ) m 。j m r ( n ，m 0 ) ； 5 ) 当t l ，t 2 ，t a t 时，o = t l t 2 k 称为出现序列，当且仅当存在标识m o ，m l ，h 蕾n 满足m o l t 0 ) m 。； 6 ) 对于网n 和标识m o ，( n ，m o ) 称为一个网系统； 7 ) 网n 邓，t ，f ，叼的关联矩阵定义为以p 和t 为序标的矩阵 n ：p x t - z ，z 是整数 的集合，且 m 胪融毗 p e 。t 、t p t 。、t p e t 、t 其它 8 ) 输入关联矩阵 n 】一_ 知 ，输出关联矩阵 n 】+ = a l j + ) ，关联矩阵【n 】= 口盯口叼j n 】j ( d 吧。，【n 】l 十) 是矩阵【n 】( n 】j 。，【n 1 j + ) 的第j 列，其中嘞- = w p j ，b ，+ _ 化p l 2 ，1 2p e t r i 网的活性及不变式 【定义2 1 1 】设n = ( p t f 聊是一个网，m o 是n 的一个标识 1 广个变迁t 在标识m o 下是活的，当且仅当v m 。r 删，m o ) ，3 m 。r ( n ，m o ) ：m i i t ) 成 立： 2 ) ( n ，m o ) 具备死锁性，当且仅当，3 t e t ：m o t ) 成立； 3 ) ( n ，m o ) 具备无死锁( 弱活) 性，当且仅当v m e r ( n ，m o ) ，3 t t ：m 【t ) 成立； 第二章p e t r i 网理论初步与系统建模分析 9 4 ) 系统在m o 下具备准活性，当且仅当在m o 状态下v t t ，3 m m o t 。 5 ) ( n ，m o ) 具备活性，当且仅当v t e t ：t 在标识m o 下是活的，也即是v t e t ：v m e m o ： q m 【m ，m 1 i t 。 6 ) ( n ，m o ) 具备有界性，当且仅当j k i n 0 ) ，v m r ( n ，m o ) ，v p p ：m 盘； 7 ) ( n ，m o ) 具备结构有界性，v m o ，0 也m o ) 是有界的； 8 ) ( n ，m o ) 具备结构活性，当且仅当3 m o ，州，m o ) 是活的。 9 ) 设m 。是“h o m e ”的，当且仅当v m m 0 ，m 。吣i 。 1 0 1 ) ( n ，s o ) 具备可逆性，当且仅当m o 是 h o m e ”的。 值得说明的是，对于资源有限的实际系统而言，它的p e t r i 网模型一般都具备 结构有界性。 【定义2 1 2 设n = ( p ，t ，f ，w ) 是一个网。 1 ) 以p 为序标的列向量v ：p - - ) z 称为n 的p 向量，z 是整数的集合。 2 ) 以t 为序标的列向量w ：t - - z 称为n 的b 向量。 3 ) 称p 向量i 是一个p 不变式( 库所不变式) 当且仅当i ；l - o 且i t 【n 】甜。 i | i l | = p p 1 1 0 瑚) 称为i 的支撑。令i i i i i + = p p i i ( p ) 0 ，i i i i l = p p l i ( p ) o ，则s 以后总是被标记。 【性质2 6 】网n = ( p ，t ，f ，w ) 的p 不变式i 的支撑既是一个信标又是一个 陷阱。 【性质2 7 】( n ，m o ) 是一个网系统，其中n = ( p ，t ，f ，w ) 。如果该网系统是无 死锁的并且状态m o 是h o m e 的，那么该网系统就是活的。 【性质2 8 lf n ，m o ) 是一个普通网系统，n = 口，t ，f ) ，若n 在m 下是死锁的t 则所有未被标记的库所形成一个信标；如果网n 中没有信标可能被清空，则称o 也 m o 是无死锁的( d e a d l o c k 舶e ) 。 下面的一般p e t r i 网的定义和性质 3 7 1 。给定一个库所p ，我们用m a x r j 晰 m 嗵。， w 0 ，t ) ) 。 【定义2 1 4 1 令( n ，m o ) 是一个被标识的网系统并且s 是n 的一个信标。在标 识m r ( i q , m o ) 下，当且仅当3 p e s 使得m q ) - m r x p 时，我们称s 是被最大标识的。 【定义2 1 5 1 令( n ，m o ) 是一个被标识的网系统并且s 是n 的一个信标。当且 仅当s 在任何可达标识下都是被最大标识的信标，我们称s 是被最大可控的。 p 7 图2 i 一个小的一般p e t r i 网f n o ，m 曲) 模型 p l i 第二章p e t r i 网理论初步与系统建模分析 l l 【定义2 1 6 1 当且仅当网n 的每一个极小信标是最大可控的，那么网系统( n ， m o ) 被认为是满足最大可控信标的性质。 【性质2 9 】如果网系统( n ，m o ) 满足最大信标可控定理那么该网系统就是活 的。 图2 1 中所示的网是纯的并且有界的存在死的可达状态，该网的结果是不活 的。网中有六个p 一不变式i l = 2 p l + p l o + p 1 2 ，h = l 阮+ p s + p 9 印1 3 ，1 3 硇+ 似 p s + p t 4 ，1 4 碘+ p 1 5 ， i s = p l m + p 3 + p 4 + p 5 + p n p 7 和1 6 = p s + p g + p l o + p n 。包含t - - 个严格极小信标s 1 = p 3 ，p 6 ， p 9 ，p 1 3 ，p 1 4 ，s ： p 2 ，p 5 ，p l o ，p 1 2 ，p 1 3 ，s 3 = p 3 ，p 6 ，p 1 0 ，p 1 2 ，p 1 3 ，p 1 4 在以前的方法中，为 了使网满足最大信标可控定理三个严格极小信标都应该被最大可控。 2 2p e t r i 网的系统建模思想 本节通过几个简单的例子说明怎样用p e t r i 网表示离散事件系统1 3 8 1 【3 9 1 。 1 四季系统 如果把地球上的气候变化看成一个系统，那么它包含四个变化：温暖花开一炎 热一秋风叶落一寒冷一温暖花开。我们把四个箭头代表的变化依次叫做变迁( 或事 件) r 1 ，f 2 ，f 3 和t 4 , 用朋，见，朋和内来表示对应的四个库所，或更准确地说四个条件( 事 实上就是春、夏、秋、冬四季) 于是每个条件都有真和非真两种状态。得到初步模 型如图2 2 ( a ) 所示，得到的四季系统的p e t r i 网模型如图2 2 所示。如图所示，t 2 发生的结果是托肯从融流到功，及炎热把我们从夏季带到了秋季。不过托肯的流 动不同于只有位置变化的水流，它的流动不仅有量变，而且有质变。 潞雎杜矸炎媳 砍h i | i ，*絮； 件斗型- _ i 卜欲- _ l 卜冬呻异 2 化学反应过程 ( a ) t j p 4 h m ( b ) 图2 2 四季系统 图2 3 用一个常见的化学反应式2 1 - 1 2 + 0 2 = 2 h 2 0 演示了p e t r i 网的基本运行规 则，图2 3 ( a ) 表示在该时刻有两个h 2 和两个0 2 ，图2 3 ( b ) 表示t 发射后的系统状 态。对比图2 3 ，可知两个h 2 和两个0 2 合成了两个水分子h 2 0 。如果库所8 卜s 2 和s 3 中的标志分别表示为氢分子、氧分子和水分子的个数，变迁t 表示化合作用， 那么变迁t 的发生和这个网中表示的变化反映了2 1 - 1 2 + 2 0 2 _ 2 h 2 0 + 0 2 的化学反应 过程。 ( a )( b ) 图2 3 表示化学反应的p e t r i 网模型 3 进程间的通信协议 图2 4 是两个进程之间的通信协议的简化模型。进程a 准备好的信息通过变：i z 壬_ t 2 的发生向进程b 发送，发送到缓冲寄存器以。如果进程b 作好接受信息的准备， 便通过变迁f 的发生从矗中接收进程a 发送的信息，并通过变迁的发生向进程a 发送应答，应答信息通过缓冲寄存器& 回送到进程a 。变迁 是进程a 接收应答 的描述。当进程a 发送信息( 即 发生) 后，库所如中有一个标志，表示进程a 随时准备接收应答。以上过程可重复多次。 进 程 a 发送信息 缓冲寄存器接收信息 接收应答缓冲寄存器 发送应答 图2 4 进程间的通信协议的p e t r i 网模型 进 程 b 4 生产者消费者问题 生产者消费者系统属于另一类资源共享系统。生产者进程和消费者进程的共 享资源是缓冲寄存器( b u f f e r ) ，不过缓冲寄存器对它们有不同的作用。生产者进程 把生产出来的数据项存入缓冲寄存器，而消费者进程从缓冲寄存器中取走数据项， 第二章p e 仃i 网理论初步与系统建模分析 1 3 并消费它们。消费者进程能够运行的条件是缓冲寄存器中含有未被消费的数据项。 而生产者进程能够运行的条件是缓冲寄存器不溢出，因为缓冲寄存器的容量一般 是有限制的。生产者和消费者系统的p e t r i 网模型如图2 5 所示： 生 孝 者 进 程 图2 5 生产者消费者系统的p e t r i 网模型( 其中b 表示缓冲寄存器) 5 哲学家用餐问题 d i j k s t r a 提出的哲学家用餐问题是资源共享系统的一个通俗的典型例子。5 个哲学家坐在一个圆桌旁，圆桌上摆满了中餐食品，每2 个哲学家之间摆了一 根筷子。一个哲学家要吃食品时，必须同时拿起他左边和右边的筷子。这时坐 在他旁边的两位哲学家就不可能有足够的筷子来吃食品，只能坐在那里思考问 题。 图2 6 是这个问题的一个p e t r i 网模型。这个模型己对问题进行了一定的处 理：规定只有当一个哲学家身边的左右两根筷子都未被占用时，它才能拿起筷 子( 而且同时拿两根筷子) 。这样才能避免这样一种情况：每位哲学家都拿起 一根( 譬如说右边的一根) 筷子不放下，等待别人让步，而结果谁也吃不上。 图2 6 哲学家问题的p e t r i 网模型 ( 图中c f ，弓( i - l ，2 ，3 ，4 ，5 ) 分别表示第i 个哲学家处于“思考”或“吃”的状 态，e ( i - l ，2 ，3 ，4 ，5 ) 中有一个标志表示第i 根筷子未被占用) 2 3p e t r i 网系统模型分析 下面以一个例子演示p e t r i 网模型在柔性制造系统中的应用。 图2 7 用p e l r i 网描述了一个简单的柔性制造系统。 p 1 t 1 图2 7 一个f m s 的例子 t 8 图2 8 具有两个生产进程的柔性制造系统的p e t r i 网模型 图2 8 是对图2 7 中的f m s 所建立的p e t r i 网模型，网系统包含两个加工进程， 分别为p l - p 2 一p s - p s ，p n - p 1 0 - p 7 - p 4 ，三个加工工具p 3 ，p 6 ，p 9 ，每次可以加工一个工件。 它可以模拟两个独立的f m s 共享资源后的系统，这个独立的f m s 系统由两个机 床( m a c h i n e l ，m a c h i n e 2 ) 、一个机器人( r o b 0 0 、输入缓存库i n p u t 和输出缓存库 o u t p u t 组成，且机床m a c h i n e 每次只加工一个工件，机器人r o b o t 每次只能夹持 一个工件。机器人r o b o t 可以将输入缓存库i n p u t 中的零件装载到机床m a c h i n e 上， 第二章p e t r i 网理论初步与系统建模分析 也可以将机床m a c h i n e 上的零