（计算机软件与理论专业论文）petri网混惑结构研究及应用.pdf

t 1 1 ，。l 西华大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，：也不包含其他已申请 学位或其他用途使用过的成果与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：陪赢 指导教师签名： 日期：7 , o o 石男日期 启叉 西华大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，在校 攻读学位期间论文工作的知识产权属于西华大学，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，西 华大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复印手段保存和汇编本学位论文。( 保密的论文在解 密后遵守此规定) 学位论文作者签名猎，芍， 日期：珈，口g 指导教师签名：害叉 日期如矿6 ，1 0 ， 西华大学硕士学位论文 摘要 p e r t i 网采用可视化图形描述但被形式化的数学方法所支持，表达离散事件动态系统 的静态结构和动态变化。它是一种结构化的离散事件动态系统描述工具，对于具有异步 并发、分布、不确定性和随机性的系统，都可以利用这种工具构建模型，然后对其进行 分析，即可得到系统静态结构和动态行为方面的信息。它既有直观的图形表示，又有深 刻的数学内涵和基础。 p e t r i 网的结构是指具有某种特征的图结构的子图包括如；s i p h o n 、t r a p 、混惑等。 网的结构性质就包括了s 不变量( s i n v a r i a n t ) 和t 不变量( t - i n v a f i a n t ) 、死锁( d e a d l o c k ) 结构活性、结构有界、结构混惑等，由于这类性质由网的结构确定，它们中大多都可以 通过网的关联矩阵给出确定的判定准则，得到比较完整的分析结果，这些结果又是用代 数方法分析p e t r i 网的基础f n 。 本文的主要工作如下： ( 1 ) p e t r i 网中，混惑会给系统分析和系统控制带来麻烦，有混惑的系统不是好系 统，有混惑的模型不是好模型。文中针对混惑的特质进行了研究；在已知的3 种结构混 惑( 增混惑、减混惑、不增不减混惑) 的基础上，给出了基于增广p e t r i 网的增混惑、减混 惑的消除方法。 ( 2 ) 在p e t r i 网结构性质下用p t 网构建了网上商城订单前台处理和后台处理的基 本流程模型，此模型保证了订单在后台处理时订单不丢失、订单处理员与发送订单两大 主体之间同时核对订单。最后，利用s 一不变量给出订单后台处理模型的验证。 ( 3 ) 本文通过c e 系统比高级网系统更容易在硬件上实现的特点，通过进一步完善。 利用( 狂网下的两个精细化操作，最终给出了一个具有动态优先级调度策略的哲学家就 餐问题伽网持卡模型。 关键词：p e n i 网；混惑；消除；s 不变量；验证 p e t r i 网混惑结构研究及应用 a b s t r a c t p e r i ln e t s u s i n g v i s u a la n d g r a p h i cr e p r e s e n t a t i o n , b u t i s s u p p o r t e db y f o r m a l m a t h e m a t i c a lm e t h o d s ，e x p r e s s i o no fd i s c r e t ee v e n td y n a m i cs y s t e mo fs t a t i cs t r u c t u r ea n d d y n a m i c s i ti s as t r u c t u r e dt o o lt od e s c r i b ed i s c r e t ee v e n td y n a m i cs y s t e m s ，f o rw i t h a s y n c h r o n o u sc o n c u r r e n c y ，d i s t r i b u t i o n , u n c e r t a i n t ya n dr a n d o m n e s so ft h es y s t e m , c a nu t h i st o o lt ob u i l dm o d e l sa n dt h e na n a l y z ei t ，t h e ny o uc a ng e tt h es y s t e ms t a t i cs t r u c t u r ea n d d y n a m i cb e h a v i o ro ft h ei n f o r m a t i o n i ti sb o t hh a v ei n t u i t i v eg r a p h i c a lr e p r e s e n t a t i o na n d d e e pm a t h e m a t i c a lm e a n i n ga n df o u n d a t i o n p e t r i n e ts t r u c t u r ei sc h a r a c t e r i s t i co ft h eg r a p hs t r u c t u r ew i t has u b - p l a ni n c l u d e s ：s i p h o n ， t r a p ，c o n f u s i o na n ds oo n p e r t in e t ss t r u c t u r en a t u r ei n c l u d i n gt h es i n v a r i a n ta n dt - i n v a r i a n t , d e a d l o c k ，c o n s t r u c t i o na c t i v i t y ，s t r u c t u r ei n d u s t r y ，s t r u c t u r ec o n f u s i o n ，b e c a u s et h en a t u r eo f t h en e t si ss t r u c t u r ed e t e r m i n e ，s om o s to ft h e mc a nb eg i v e nt h r o u g ht h en e t si n c i d e n c em a t r i x d e f i n e dc r i t e r i a , t h e no b t a i nm o r ec o m p l e t ea n a l y s i so ft h e s er e s u l t s ，i ti sa l g e b r a i cm e t h o d so f a n a l y s i sb a s e do np e t r in e t s t h em a i nw o r ko ft h i sp a p e ri sa sf o l l o w s ： ( 1 ) i np e t r in o t s ，c o n f u s i o nw i l lc a u s et r o u b l ew h e na n a l y s i sa n dc o n t r o lt h em i x e d s y s t e m ，t h e r ei sc o n f u s i o ni nt h es y s t e mi sn o tw e l lm i x e ds y s t e m ，t h e r ei sn o tag o o dm o d e l o fm i x e dc o n f u s i o nm o d e l i nt h i sp a p e r t h ec h a r a c t e r i s t i c so fc o n f u s i o nw a ss t u d i e d ，t h r e e k i n d so fs t r u c t u r ei nt h ek n o w nm i x t u r ea n dc o n f u s i o n ( c ic o n f u s i o n , c dc o n f u s i o n , n e i t h e ra c ic o n f u s i o nn o r ac dc o n f u s i o n ) , t h ep a p e rg i v ee l i m i n a t i o nm e t h o d so fc ic o n f u s i o na n de d c o n f u s i o nb a s e do ng i v e np e t r in e t sa u g m e n t e d 、 ( 2 ) u n d e rt h es t r u c t u r a lp r o p e r t i e so fp e t r in e t su s ep tn e tt ob u i l da l lo n l i n es h o pf r o n t o r d e rp r o c e s s i n ga n d ”b a c k g r o u n dp r o c e s s i n go ft h eb a s i cp r o c e s sm o d e l , t h i sm o d e le n s u r e d n o tl o s eo r d e r st h eo r d e ri nt h eb a c k g r o u n da n do r d e rp r o c e s s i n ga n ds e n d i n gm e m b e r so ft h e t w oo r d e r s tb e t w e e ns u b j e c t sa tt h es a m et i m ec h e c ko r d e r s f i n a l l y ，u s es - i n v a r i a n t s v e r i f i c a t et h em o d e lo fb a c k g r o u n do r d e r sp r o c e s s i n g ( 3 ) 1 1 1 i sp a p e ru s ec es y s t e mm o r ee a s i l yt h a nt h es e n i o rn e t w o r ks y s t e mi m p l e m e n t e d i nt h eh a r d w a r ef e a t u r e s ，b yf u r t h e ri m p r o v i n gt h eu o fc en e tr e f i n e m e n to p e r a t i o nu n d e r t h et w of i n a l l yg i v e sa d y n a m i cp r i o r i t ys c h e d u l i n gs t r a t e g yd i n i n gp h i l o s o p h e r sp r o b l e mc | en e t w o r kc a r dm o d e l 。i ，0：二j i 。：5 ： k e yw o r d s ：爹询。前南彩鳓专商x 锺7 南瓶玉q 矗；e l i m i n 7a t i o n ；s - i n v a r i a n t ；v e r i f i c a t i o n i i 西华大学硕士学位论文 目录 摘要j 。i a b s t r a c t i 】 i 1 绪论1 1 1 课题的研究背景和意义，。1 1 2p e t r i 网的发展历史。2 1 3p e 砸网的研究现状。3 1 4p e t r i 网的结构性质6 1 5p e t r i 网的分析技术。6 1 6p e t r i 网的应用。7 1 6 1 应用于柔性制造系统的建模、分析、控制和优化设计8 1 6 2p e t r i 网应用于工作流、物流等建模8 1 6 3 应用于人工智能9 1 6 4 用于离散系统的建模和仿真9 1 6 5p e t r i 网应用于网络通讯中协议的描述、验证和设计1 0 1 6 6 p e t r i 网应用于计算机系统和软件系统建模1 l 1 6 7p e t r i 网应用于数据库系统。1 1 1 7 本文的主要内容及结构1 2 2p c t r i 网的基础知识。1 3 2 1p e t r i 网的基本概念。1 3 2 2 网系统分类：1 9 2 3 网的结构和行为特征：2 1 3 基于p e t r i 网结构性质下的混惑研究2 3 3 1 本章相关概念。2 3 3 2 混惑的检测与消除。2 4 3 3 本章的贡献与需进一步研究的工作2 7 4 基于p e t r i 网结构性质下的应用2 9 4 1 模型的建立：2 9 4 1 1 订单前台处理基本架构2 9 4 1 2 订单前台处理的p e t r i 网模型3 0 4 1 3 网上商城后台处理的p e t r i 网模型的建立。3 2 p e t r i 网混惑结构研究及应用 4 2 基于p e t r i 网结构下的订单处理模型的正确性分析与验证3 3 4 3 本章的贡献与需进一步研究的工作3 5 5 带优先级控制的哲学家进餐问题无饥饿解的p e t r i 网模型3 7 5 1 基本概念3 7 5 2 模型的改进与验证。3 9 5 3 本章的贡献与需进一步研究的工作4 3 结论z 1 5 参考文献4 6 攻读硕士学位期间发表学术论文情况5 0 致谢! ；】【 西华大学硕士学位论文 1 绪论 i 1 课题的研究背景和意义 随着科学技术的进步，人类社会进入2 l 世纪，计算机科学技术得到迅猛发展。从 单c p u 的串行计算机系统到多c p u 的并行计算机系统；从单纯的文本处理到集文本、图 形、图像和语言等于一体的多媒体处理；从基于单机环境下的操作到基于网络并行环境 下的机群操作；如此种种，其基本理论模型可以归结为从串行处理的串演系统到并行 处理的并发系统。由此可见，并发系统是当今计算机科学技术中一项重要的基础研究课 题之一。 并发模型的出现，可以追溯到2 0 世纪3 0 年代。神经元网络可谓是早期的并发模型， 它以多结点的网络机制模拟人的神经网络系统，各种经元结点除了自身的信息处理活动 之外，还要进行神经元结点之间的信息传输和协调，由此呈现整个网络系统的并行处理 活动。神经网络系统从本质上来说，属于数值信息处理，主要集中在计算这一特征上， 其网络中的通信处理不甚明显。随着对多处理机系统通信要求的提高，出现了一系列反 映通信机制的并发模型。p e t r i 网便是其中颇具代表性的模型之一，也是当今研究并发 系统的主要工具之一1 2 1 。 在应用系统中出现混惑，则系统环境无法确定是否有冲突出现，或未加控制而冲突 消失，混惑会给系统分析和系统控制带来麻烦，有混惑的系统模型不是好模型，产生混 惑的原因是系统和系统环境的分割不正确( 系统中某些变迁的外延不完整，应该从环境 中补充他们的外延，以获得这些变迁更准确的描述) ，顺序系统和确定性系统都是无混 惑系统，系统中出现冲突之处正是系统对环境对系统进行控制的地方。有混惑的系统模 型不是一个好的模型，在实际应用中必须保证混惑现象不会发生。 网上商城利用现代网络技术等手段，尽可能的减少了买卖的中间环节，消除了运营 成本和代理中间的差价。面向顾客，能够最大限度的保证消费者的利益；面向商家，能 够获得更大的发展空间。订单是联系顾客与商家的纽带，由此，网上商城系统的核心功 能可以归结为对订单流程的科学管理，目的是更加合理、快速的处理订单，更好地为物 流服务。已有的订单管理对于订单及客户的行为描述过于依赖u m l 、数据流图和状态图 等传统建模方法。对于u m l ，由于其顺序特性，该方法不便于描述并发的动态行为，不 符合面向多人购物的特性；数据流图，能够很好体现数据的流向，和系统运行的宏观过 程，是一个静态的模型，但是系统的动态行为分析难以实现；状态迁移图，可以分析系 p e t r i 网混惑结构研究及应用 统的动态行为，却很难从其模型结构分析出系统的宏观行为。p e t r i 网同时具备静态结 构和动态行为的分析方法。s 一不变量、t 一不变量是p e t r i 网的重要结构特性，对网的动 态分析和验证起着关键作用。 哲学家就餐问题可以看作当应用程序中包含并发线程的执行时，处理共享资源合作 的一个有代表性的问题，该问题是评价同步方法的一个测试标准。 1 2 p e t r i 网的发展历史 p e t r i 网( p n ) 最早由c a r la d a mp e t r i 博士于1 9 6 2 年在他的博士论文用自动机 通信中提出。文中采用一网络( 用其名命名为p n ) 描述计算机系统事件之间的因果关 系。他的研究工作引起了美国应用科学研究所( a p p l i e dr e s e a r c hi n c ) 信息系统理 论项目研究组的h o l t 及其他人的注意。他们的研究工作说明了p e t r i 网能够描述与分 析并行系统。这些有关p e t r i 网的研究工作也引起d e n n i s 教授领导的美国麻省理工学 院( m i t ) 计算结构研究室的注意。后来，7 0 年代初发表了若干有关p e t r i 网的博士论 文及研究报告。1 9 8 1 年p e t e r s o n 出版了第一部关于p e t r i 网的书，书中罗列了1 9 8 0 年前发表的大部分有关p e t r i 网的论文。1 9 8 5 年第二部有关p e t r i 网的书由r e s i g 出版， 书中总结了欧洲有关p e t r i 网的研究工作并罗列了所发表的文章【3 l 。 从2 0 世纪7 0 年代末期开始，p e t r i 网尤其在欧洲成为十分活跃的研究领域。从1 9 7 9 年开始p e t r i 网理论及其应用年会一直在召开，会议论文集一直以计算机科学序列讲义 ( l e c t u r en o t e s ) 的方式由s p r i n g e rv e r l a g 出版社出版发行。这些早期的有关p e t r i 网理论及应用的论文主要面向消息处理系统。 8 0 年代初，具有工程背景的研究人员也开始了p e t r i 网在工程尤其是自动制造系统 的研究。他们发现p e t r i 网是事件驱动系统建模的十分有用的工具。这些系统可以是异 步的( a s y n c h r o n o u s ) ，可能包括顺序的和并行的操作，并可能涉及冲突( c o n f l i c t s ) 、 互斥及非确定，这正是离散事件系统( d e s ) 。第一本关于将p e t r i 网作为离散事件系 统建模工具的专著由d a v i s 与a l l a 于1 9 9 2 年出版。1 9 9 3 年z h o u 与d i c e s a r e 出版的专 著集中于制造系统的d e s 建模与模型合成方法的研究。1 9 9 5 年d e s r o c h e r s 与a 卜j a a r 出版另一本关于p e t r i 网在自动制造系统建模及其在制造系统分析、性能评价及控制中 的应用的专著。1 9 9 8 年z h o u 与v e n k a t e s h 出版了关于p e t r i 网在柔性制造系统中应用 的专著。 4 0 多年来，p e t r i 网的理论不断地充实与完善。一大批学者与工程技术人员致力于 p e t r i 网的理论及其应用研究。概括起来，这些研究从以下几方面展开： 西华大学硕士学位论文 ( 1 ) 系统的p e t r i 网模型行为特性( b e h a v i o rp r o p e r t i e s ) 及其分析方法的研究。 系统的p e t r i 网模型特性包括状态的可达性( r e a c h a b i l i t y ) 、库所的有界性 ( b o u n d e d n e s s ) 、变迁的活性( l i n e n e s s ) 与死锁性( d e a d l o c k ) 、初始状态的可逆 性( r e y e r s i b 订i t y ) 、事件之间的同步性( s y n c h r o f i i cd i s t a n c e ) 等。分析方法主要 依赖于：可达树、关联矩阵与状态方程、不变量分析( i n v a r i a n t s ) 和分析简化规则。 ( 2 ) p e t r i 网的扩展。为了增强p e t r i 网描述系统的能力，基本p e t r i 网被扩展为 谓词变迁网( p r e d i c a t e t r a n s i t i o nn e t s ) 、着色p e t r i 网( c o l o r e dn e t s ) 、等高 级网。 ( 3 ) p e t r i 网的应用从计算机科学向其他领域渗透，成为历史事件系统一种有用工 具。这些领域包括自动制造系统、交通系统、医疗诊断与管理系统、办公自动化系统、 容错与故障诊断系统和决策系统等。 ( 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 网外，主要有层次与模块抽象合成 两种方法。 ( 5 ) 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 网软 件包和工具，如丹麦a a l h u s 大学计算机科学系j e n s e n 等人开发的c p n 模型设计与分析 软件包。 1 3p c t r i 网的研究现状 自p e t r i 先生开创性的工作之后，网论得到了长足发展，至今已形成了具备相当规 模的研究领域。在理论方面，p e t r i 网模型和分析技术的研究取得了许多有价值的成果， p e t r i 网作为一种全新的自动机被开发出来，研究者对此充满了希望，认为p e t r i 网比 下推自动机( p d a ) 有用，原因是它不存在图灵机所具有的那些可判定问题。在此期间， m i t 出现的许多博士论文都是以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 网来适 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 网所做的工作影响着其在建模能力、 模型的表达能力以及从模型中可获得的计量单位l 引。具有代表性的p e t r i 网模型介绍如 下： ( 1 ) 带抑制弧p e t r i 网模型( i n h i b it o ra r c sp e t r in e tm o d e l ) 对p e t r i 网模型的重要扩充就是附加一些新型的弧线。早期模型的引发规则是当输 入库所被标识时，相应的变迁就可以引发，从而改变模型的状态。更进一步，一个变迁 的发生除了需满足它的引发规则，还需要保证其通过抑制弧相连接的前置库所不被标 识。抑制弧的引进使p e t r i 网具备了零检验能力h 1 。 ( 2 ) 高级p e t r i 网( h i g h l e v e lp e t r in e t ) p e t r i 网面临的另一个问题是，为了某一个特别的操作建立模型从而必须建立复杂的 编码。一些学者认为，如果以某种方式来区别标记( t o k e n ) ，可使复杂编码容易实现。 成熟的高级网系统包括谓词变迁系统( p r t 一系统) 和有色网系统( c o l o r e dn e ts y s t e m ) ， 统称为个性托肯系统( s y s t e m sw i t hi n d i v i d u a lt o k e n s ) i s , 6 o 对个性托肯的描述方式， 前者为每个个体命名，后者为不同个性的托肯染上不同的颜色。托肯的个性其实代表着 除名字以外或颜色以外更复杂的内容。由于高级网系统是由p t 一系统折叠而来，因而较 p t 一系统少了许多结构信息，这是为减少节点付出的代价。 ( 3 ) 对象p e t r i 网( o b j e c tp e t r in e t ) 对象p e t r i 网是由内部结构和外部结构，以及对象与对象之间的消息传递形成的实 际系统模型的控制结构组成的口】。对象内部包含了该对象自身的属性以及处理这些数据 的方法。在对象p e t r i 网模型中，对象的属性( 即数据结构或数据类型) 是由库所表示 的。对象的外部结构是消息接口，库所是对象中唯一与外界( 其他对象实体) 进行消息 传输的接口，其中包括消息接收接口和消息发送接口。对象的消息接收接口和消息发送 接口是成对出现的，分别与对象内的某个方法的输入弧和输出弧相连。消息隐藏在消息 传递接口库所中的t o k e n 中，如果不同的对象同时向一个对象发送同一个消息，则在此 对象的该消息接收接口中形成一个消息队列。同理，在该对象的消息发送接口中也有可 能会产生一个消息队列。对象p e t r i 网系统通过对象间的控制结构协调各对象间的消息 传递，对象控制结构有一类具有特殊含义的变迁和库所实现。 4 西华大学硕士学位论文 ( 4 ) 时序p e t r i 网( t e m p o r a lp e t r in e t ) 1 9 8 5 年，s u z u k i 提出一种网子类：时序p e t r i 网，、引入了时序逻辑操作，如o ( n e x t ) 、口( h e n c e f o r t h ) 、( e v e n t u a l l y ) 和u n t i l 等，通过时序逻辑公式控制或限 定p e t r i 网的变迁引发序列，描述系统事件之间的时序关系，并且反映出系统的基本性 质忉一。时序p e t r i 网特别适合用于并发系统的建摸、分析和验证。 ( 5 ) 被控p e t r i 网( c o n t r o l l e dp e t r in e t ) 被控p e t r i 网是在p e t r i 网中引入一组外部输入的库所，这些外部输入库所中的 t o k e n 数决定变迁的发生或限制变迁的发生次数，控制的状态为输入库所中的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 网模型。 ( 6 ) 混合p e t r i 网( h y b r i dp e t r in e t ) 混合控制系统是由实时决策子系统与实时数值( 开环或闭环) 子系统组成的复杂的 控制系统口。实时决策子系统确定分布系统( 全局的或局部的) 控制模态的转移；每一 个控制模态下，实现特定活动功能的实时数值控制子系统与被控对象、传感器和执行器 组成传统的数值控制回路。但由于混合系统的复杂性，使得每一个控制模态下的状态特 征量不仅仅是被控对象向数值控制器的连续量或数值量反馈，还有来自被控对象的符号 量或离散事件特征量，这些量组成模态下的混合状态。 混合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 网的全部结点是离散的结点，则混合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 网的离 散发生规则和连续p e t r i 网的实值发生规则。 ( 7 ) p e t r i 网语言( t h el a n g u eo fp e t r in e t ) 语言是对模型的动态行为的一种刻画。它是用代数方法研究模型的行为理论的一 种有效的工具。自动机与形式语言相辅相成，其相互渗透启发了网人对p e t r i 网语言研 究的兴趣，既然p e t r i 网是图论的高级阶段，那么自动机与形式语言的研究方法也可以 运用于p e t r i 网的研究中。 5 p e t r i 网混惑结构研究及应用 p e t r i 网语言是研究p e t r i 网的一个手段，目前已形成一个重要的研究方向。h a c k 嘲 和p e t e r s o n m 最早从事这方面的研究。将一个p e t r i 网所有可能引发序列的集合视为由 该网产生的语言，文献 1 0 ，1 1 研究了语言的封闭性，以及与经典形式语言的关系。h a c k 在文献 4 中还讨论了网模型的计算能力，指出带抑制弧的增广p e t r i 网与图灵机在计 算能力上是等价的，从而充分显示出p e t r i 网模型的表达能力。另外，r o z e n b e r g 等人 n 2 1 在事件多重集上讨论了子集语言的类似问题，文献 1 3 给出了p e t r i 网语言的一个很 好综述，文献 1 4 给出了p e t r i 网语言与形式语言关系的一个清楚刻画。文献 1 5 分别 从各个角度研究了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 网语言研究的不成 熟，同时也暗示了一个极具吸引力的研究方向n 制。 1 4p e t r i 网的结构性质 网的结构性质主要有：结构有界性( s t r u c t u r a lb o u n d e d n e s s ) 、守恒性 ( c o n s e r v a t i v e n e s s ) 、可重复性( r e p e t i t i v e n e s s ) 、协调性( c o n s i s t e n c y ) 、结 构公平性( s t r u c t u r a l f a i r n e s s ) 、结构活性( s t r u c t u r a lli v e n e s s ) 、s 一不变量 ( s - i n v a r i a n t ) 和t 一不变量( t - i n v a r i a n t ) 、死锁( d e a d l o c k ) 与陷阱( t r a p ) 等。 结构理论的思想是以某种特定结构比如t r a p 、不变量和子网覆盖，通过这些结构上t o k e n 的分布特征研究网的动态行为。t r a p 是这样一些库所的集合：关联的流入变迁，一定也 是关联的流出变迁，所以一旦t r a p 不被标识，将永远不被标识，这一特征对于网的活 性，弱活性的描述极其深刻。当某个t r a p 不被标识后，它的输出变迁将永远不会发生， 因此不能满足网的活性：当所有极小t r a p 不被标识，那么整个网完全死锁：当t r a p 中至 少有一个极小陷阱能够被标识，比如一个极小死锁中至少包含着一个m 。标识的陷阱， 由于陷阱具有特征：一个陷阱一旦被标识将永远被标识，于是它的输出变迁是活的，网 就不会死锁，具有弱活性。s 一不变量( s - i n v a r i a n t ) 和t 一不变量( t - i n v a r i a n t ) 是 p e t r i 网的重要结构性质，对网的结构分析起着关键作用。合成操作是解决复杂系统设 计与分析的一条重要途径，p e t r i 网合成过程中，其动态行为特性的保持问题是重要的。 1 5p e t r i 网的分析技术 现有的p e t r i 网分析技术包括： 6 西华大学硕士学位论文 ( 1 ) 基于状态方程和代数分析技术【1 6 1 7 ，1 s l 。代数分析技术主要以关联矩阵的形式对 一个网系统的结构给予刻画，然后建立状态可达的线性系统关系，这种分析途径首先是 由p c t e r s o n 1 6 l 提出，之后m u r a t a 1 8 l 的工作最为出色。它的优点是基于线性代数的方法刻 画网的静态结构，用不变量( i n v a r i 强妫研究的网的一些性质，尤其是结构性质。当然， 其作用是有限的，难于很好地刻画动态特征。一般来说，它对可达性的刻画只是一个必 要条件，而非充分，只有针对无冲突的子类才是充要的。最近，文献【1 8 】试图做出努力， 取得了一些进展，但仍未很好的解决。 ( 2 ) 基于可覆盖树( 图) 的分析技术1 1 9 , m 。图分析技术是以一个有限的有向( 树) ， 直接展现一个网系统的运行机制，类似于一个状态机。k a 印和m i l l e r 2 1 l 首先提出这一思 想，它的优点是能反映一个网系统的动态行为和一些特征。特别地，对一个有界p e t r i 网，它能准确刻画，而且对应一个有限状态机。然而，对无界p e t r i 网，它只能部分反 映。虽说可达树是p e t r i 网分析的一个较好工具，但无法回避状态空间爆炸。 ( 3 ) 基于化简分解的归纳分析技术【翻。针对状态空间爆炸，人们提出极小可达树、 可达树化简等办法来克服这一困难，各种化简方案的提出和应用，可以使对复杂的网( 或 网系统) 的一些性质分析的工作量大幅度地减少。因此p e t r i 网的化简不失为p e t r i 网分 析的一种有力的辅助手段。m u r a t a 2 3 4 l 针对t 图提出若干化简规则，并讨论了这些规则 对活性、安全性的保持关系；蒋昌俊推广了m u r a t a 的工作i 矧，进一步提出了对加权t 图的化简规则，并给出了化简运算对结构性质的保持条件：a a l s t l 2 6 1 在工作流过程验证中 使用了这些技术。m u g a r z a i 2 r l f f lf e r s c h a | 2 8 l 给出了并行程序的化简规则，并给出了相应的 p e t r i 化简规则；林闯【2 冽运用自底向上逐步综合替代的分层分析方法，给出了基本随机 p e t r i 网性能等价公式，并利用变迁可实施谓词和随机开关对模型进行了精化设计及化 简。这些化简方法都是在权为1 的p e t r i 网上考虑或者是在加权的特殊p e t r i 网子类上考 虑的；文【3 1 】将化简方法推广到加权的阴网，并给出了其对结构性质及公平性、s m 不变量的保持条件。较新的研究成果有基于实时系统的化简规则及其在工作流方面的应 用。就总体而言大多数工作都局限在保性研究上，而且条件过强，很难普适。减弱条件， 提高适应性将是进一步努力的目标。 1 6p 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 网 系统模型的框架上完成各项任务。在这一点上，其它图形或数学工具都不具备如此完整 的功能1 3 2 l 。 1 6 1 应用于柔性制造系统的建模、分析、控制和优化设计1 3 3 1 p n ( p e t dn e t s ) 在计划调度领域的研究最早是在2 0 世纪8 0 年代提出来的 3 , t j ，一般仅 是分析计划调度问题的可行性与可达性1 3 5 _ 3 7 】。在现代企业生产中，获取最大利润是每个 生产经营者的最大目标，合理优化的计划调度策略是保证企业取得上述目标的关键。当 一个企业确立了其发展规划和长期计划后，就按照预先设定计划方案发展。然而，在实 际生产环境中，制造系统经常受外部随机事件的干扰1 3 引，如设备故障、缺货、更换交货 日程等。如何及时调整计划，制定合理优化调度策略，使企业尽快按照预先的计划调度 策略完成任务，是当前企业界迫切需要解决的课题。文献 3 9 1 介绍了一种实时调度策略 应用于制造系统的例子。还有一些文献着重介绍了p n 用于柔性制造系统的方法，路由 器动态调度的优化问题，工作流设计及其优化等【4 0 , 4 1 】。文献【4 2 1 提出了一种用p e t r i 网 模型的变迁计数器来对连续故障进行分析的方法。 p e t r i 网在柔性制造系统( f l e x i b l em a n u f a c t u r es y s t e m ，简称f m s ) q 丁的应用比较典型。 一般采用随机p e t r i 网为柔性制造系统建模。p e t r i 网有一个重要的优点，它可以从设计 的第一步到系统的实现提供统一的模型工具。p e t r i 网模型提供图形的、准确的形式描述， 这可以使设计者、拥有者和用户之间进行关于系统行为的深入对话；良好定义的理论， 它可进行模型性质( 活性、公平、有界等) 的验证；性能评价的理论和方法( 指随机网) ； 系统实现技术，包括实时控制软件的代码产生技术。由于f m s 是复杂、大型的系统， 在使用随机p e t r i 网对这样的系统进行模拟时，可以采用细分和抽象的方法。这种方法 可以建立起层次结构化的网模型；子模型模块的合并可以是简单的子系统及成为复杂的 整个系统。文献【6 4 】提出了一种改进的p e t r