（计算机软件与理论专业论文）基于petri网下的离散事件的模拟与动态系统的验证.pdf

西华大学硕士学位论文 基于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 网作为一种图形工具。除了w 戳用作类似于流程图、 框图和网图等可视交互工具外，黧要的在于它用静态的直观图形蕴涵着系 统的动态行为，这是经典豳论不能具备盼特点；同对它又色容经典闰论， 几乎所有图论的结论、方法都可以直接、间接地使用和借黢；而经典图论 在描述网络环境时是困难的。 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 网的主要理论研究 方面、具体应用做了较为深入细致的工作，得到了一些新的结果。主要贡 献包括： ( 1 1 令牌环介质访问控制技术。这一技术最有影响的是i b m 公司的 t o k e nr i n g 。令牌环介质访问控制技术多用于环形拓扑结构的网络，属于 有序的竞争协议。本人的研究给出了令牌环网在p e t r i 网中最一般的p ，r _ 系统下的模型，并对其加以验证； ( 2 ) 系统的模拟与验证。股票交易系统是典型的异步并发的 d e s ( d i s c r e t ee v e n ts y s t e m s ) 用p e t r i 网来描述非常合适，更能满足数据的 海量性、有效性、公平性、撮合成交时的正确性等要求；p e 们网本身可以 实现对变迁引发序列的控制，如采用抑制弧或对s 元添加补的方法，把模 型建立在了p 厂r 系统上。本人的研究是以上海证交所为例，对网上证券 交易系统进行了模拟与验证。 ( 3 ) 工作流的理论研究。工作流的提出源于办公自动化的发展，是对 在计算机环境下具有异步并发特征的业务流程的形式化描述，其目标是在 需要的时刻把需要的信息传递给需要它的人，使该项业务能高效地完成。 工作流技术为企业的经营过程、自动化管理控制过程、最高决策系统等提 供了一个从模型分析、建立、管理、仿真到运行的完整框架，是实现业务 过程管理与控制的一项关键性技术。 工作流逻辑网w ln e t ( w o r k f l o wl o g i ch e 0 只关心任务间的依赖关系， 包括因果依赖和规章依赖，不关心任务的具体操作内容。从p e t r i 网的角 度看，i f 壬务集构成变迁集，变迁由库所和流关系连接，通过托肯的流动体 现顺序、并发和冲突( 选择) 等关系。 一个正确的工作流逻辑系统w f _ l o g i c = ( p t f ，k ，w m o ) 应具有畅通 性，即入口库所中的托肯经传递、复制及合并能流动到一个终点库所。为 了判断是否畅通，需要对其进行化简，本人的研究借助矩阵及矩阵运算 i i 西华大学硕士学位论文 或矩阵上的初等变换以及删除全零行( 列) 来实现这些已有的化简规则。 关键词：p e t r i 网：离散事件；模拟；验证；s 不变 l l i 西华大学硕士学位论文 s i m u l a t i o na n dv e r i f i c a t i o no fd y n a m i cb e h a v i o r o f d i s c r e t ee v e n tb a s e do np e t r in e t s m e n g y o n g g a n g ( c o m p u t e rs o f t w a r et h e o r e t i c s ) d i r e c t e db yp r o f s o n gw e n a b s t r a c t p e t r in e t sa r ef i tf o rd e s c r i p t i o na n dm o d e l i n go fi n f o r m a t i o nm a n a g e m e n t s y s t e m i nn e t w o r kc i r c u m f e r e n c e i t sm a i np r o p e r t yi n c l u d e sc o n c u r r e n t ， u n c e r t a i n t y , a s y n c h r o n i s m ，s t e p p i n gd e s c r i p t i o na n da n a l y s i sa b i l i t y w i t ht h e a d v a n t a g e s d i s c u s s e da b o v e ，p e t r in e t sh a v e v a r i e t y o fa p p l i c a t i o n si n d e s c r i p t i o na n dm o d e l i n go fd i s c r e t ee v e n ts y s t e m s f o re x a m p l e ，p e t r in e t s a r eu s e f u lt o d e s c r i p t i o n o fm u l t i p r o c e s s o rc o m p u t e rs y s t e m ，c o m p u t e r n e t w o r k ，t r a f f i cc o n t r o ls y s t e ma n ds oo n p e t r in e t s ，a sag r a p h i ct o o l ，n o to n l y b eav i s u a l i z e di n t e r a c t i v et o o l ，s u c ha sf l o wc h a r e ，f r a m ec h a r e ，n e tg r a p h ，b u t a l s od e s c r i b ed y n a m i ca c t i v i t yo fs y s t e mb yu s i n gs t a t i ci n t u i t i o n a lg r a p h ， w h i c hi sw h a tc l a s s i c a lg r a p ht h e o r yc o u l d n td o i nt h em e a n t i m e ，p e t r in e t i n c l u d e sc l a s s i c a lg r a p ht h e o r y , b e c a u s ea l m o s te v e r yc o n c l u s i o no ft h el a t t e r c a nb eu s e dd i r e c t l ya n di n d i r e c t l y h o w e v e r ，c l a s s i c a lg r a p ht h e o r i e sh a v e t r o u b l ei nd e s c r i b i n gn e t w o r kc i r c u m f e r e n c e p e t r in e ti sas u b j e c tb r a n c ho fc o m p u t e rt h e o r ya n da p p l i c a t i o n ，w h i c h h a v ep r o f o u n da c a d e m i cc o n n o t a t i o na n de x t e n s i v ea p p l i c a t i o nb a c k g r o u n d a sam a t h st o o l ，w ec a nb u i l ds t a t ee q u a t i o n ，a l g e b r ae q u a t i o na b o u tp e t r in e t a n dc o n n e c ti tw i t hl o g i c o nb a s i so fd i f f e r e n tn e e d ，w ec a n ，u s i n gd i f f e r e n t c o n v e n i e n ta n a l y s i st 0 0 1 a n a l y s e ss t a t i cc h a r a c t e r so fs y s t e mi no r d e rt o 西华大鬻颈学位论文 u n d e r s t a n di t sd y n a m i ca c t i v i t y , w h i c hi st h er e s e a r c hw a yt h e o r yo fp e t r in e t s i na d d i t i o n ，p e t r in e th a ss e l f - e x p l a i n i n ga b i l i t y f o re x a m p l e ，p r o c e s si sa l l i m p o r t a n tc o n c e p ti nc o m p u t e rs c i e n c e i nr e s e a r c h i n gp r o p e r t yo fp e t r in e t s ， w ec a l ld e f i n ep r o c e s sb yu s i n gas p e c i a ls u b c l a s so fp e t r in e t s ，o c c u r r e n c en e t s ， w h i c hi sw h a tc l a s s i c a lg r a p ht h e o r yc o u l d n td o o u rw o r ki sr e s e a r c ho ns o m ep r o p e r t yo fg e n e r a lp e t f in e t s ，w h i c hb e g i n s w i t hm o d e l i n ga n dv e r i f i c a t i o n ，d os o m ep r e c i s ea n dt h o r o u g hw o r ko nt h e o r y r e s e a r c ha n da p p l i c a t i o no fp e t r in e t s b yu s i n gr e d u c i n ga n di n v a r i a n t s t e c h n o l o g y , a n dd r a ws o m en e wc o n c l u s i o na sf o l l o w s ( 1 ) a b o u tt o k e nr i n gm e d i aa c c e s sc o n t r o lt e c h n o l o g y t h em o s te f f e c t i v et e c h n o l o g yo ni ti st o k e nr i n go fi b m t o k e nr i n g m e d i aa c c e s sc o n t r o lt e c h n o l o g yi so f t e nu s e di nr i n gt o p o l o g yn e t w o r k ， b e l o n g st oo r d i n a lc o m p e t ep r o t o c 0 1 o u rr e s e a r c hg i v e st h em o d e lo ft o k e n r i n gn e tb a s e do np tn e t ，w h i c hi st h em o s tn o r m a lp e t r in e t s ，a n dv e r i f yi t ( 2 ) a b o u tm o d e l i n ga n dv e r i f i c a t i o n o f s y s t e m s t o c kt r a d i n gs y s t e mi sat y p i c a la s y n c h r o n i s mc o n c u r r e n td e s ( d i s c r e t e e v e n ts y s t e m s ) i ti sf i tf o rb e i n gd e s c r i b e db yp e t r in e t ，w h i c hc a nf u l f i l li t s d e m a n d ss u c ha sp l e n t yo fd a t a ，v a l i d i t y , j u s t i c e ，c o r r e c t n e s s p e t r in e tc a n r e a l i z ec o n t r o lo ft r a n s i t i o nf i r es e q u e n c eb yi t s e l ls ow eg i v eam o d e lb a s e d o np tn e tb yu s i n gi n h i b i t o ra r co ra d d i n gt h ec o m p l e m e n to fs - e l e m e n t s w e p r o p o s ean e wm o d e lo fo n l i n es t o c kt r a d i n gs y s t e mo fs h a r l g h a i s t o c k e x c h a n g e ，a n dt h ev e r i f i c a t i o no ft h em o d e li ss h o w n ( 3 ) a b o u tt h e o r yr e s e a r c ho fw o r k f l o w w o r k f l o wd e r i v e sf r o mh a n d l e0 f ：f i c i a lb u s i n e s sa u t o m a t i o n i ti s f o r m u l a t i o nd e s c r i p t i o no fa s y n c h r o n i s mc o n c u r r e n tb u s i n e s sp r o c e s s i t sg o a l i st ot r a n s m i tf i ti n f o r m a t i o nt ot h o s ew h on e e di tw h e ni ti sn e e d e d ，t of i n i s h t h eb u s i n e s se f f e c t i v e l y w o r k f l o wt e c h n o l o g yp r o v i d eac o m p l e t ef l a m eo f a n a l y s i s ，m o d e l i n g ，m a n a g e m e n t ，s i m u l a t i o n ，r u n n i n gi no r d e rt om a n a g e m e n t v 西华大学硕士学位论文 p r o c e s so fc o r p o r a t i o n ，a u t o m a t i o nm a n a g e m e n tc o n t r o lp r o c e s sa n ds u p r e m e d e c i s i o n m a k i n gs y s t e m i t i s k e yt e c h n o l o g yt or e a l i z eb u s i n e s sp r o c e s s m a n a g e m e n ta n dc o n t r 0 1 w l n e t ( w o r k f l o wl o g i cn e t ) o n l yc o n c e r nd e p e n d e n c er e l a t i o no ft a s k i n c l u d i n gc o n s e q u e n c ed e p e n d e n c ea n dr e g u l a t i o nd e p e n d e n c e ，b u td o n t c o n c e r nc o n t e n to ft a s ki nd e t a i l i np e t r in e t ，t a s ks e ti st r a n s i t i o ns e t ， t r a n s i t i o n sc o n n e c tw i t h e a c ho t h e rb yp l a c ea n df l o wr e l a t i o n f l o w i n go f t o k e ne x p l a i n ss e q u e n c e ，c o n c u r r e n ta n dc o n f l i c t ac o r r e c tw o r k f l o w1 0 9 i cs y s t e m = ( p t f k w ，m 0 ) s h o u l db ee x p e d i t e ， t h a ti s ，t h et o k e n so fe n t r a n c ep l a c ec a nf l o wi n t oae x i tp l a c eb yd e l i v e r y , c o p y u n i o n t ok n o wi f i se x p e d i t e ，w ec a nr e d u c ei t w er e a l i z et h e s ek n o w n r e d u c i n gr u l e sb yu s i n gm a t r i x ，m a t r i xa r i t h m e t i ca n dp r i m a r yc h a n g e so f m a t r i x k e y w o r d s ：p e t r in e t ；d i s c r e t ee v e n t ；m o d e l i n g ；v e r i f i c a t i o n ；s _ i n v a r i a n t v i 西华大学硕士学位论文 第一章综述 1 1p 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 n m i t a u t o m a t e n ”( 自动机通讯) i lj 中提出。c a r l a d a m p e t r i 的开创性工作立即引起了欧美学术界和工业界的注意】，后来逐步为科 技界所接受，现在已是人们常用的一种数学工具【4 l o1 9 7 0 年至1 9 7 5 年， m i t ( m a s s a c h u s e t t si n s t i t u t eo ft e c h n o l o g y ) 的计算结构研究小组积极参与 p e t r i 网相关的研究，1 9 7 5 年7 月在m i t 举行了第一次p e t r i 网和相关方法 的研讨会。1 9 8 1 年p e t e r s o n 出版了第一本p e t r i 网方面的专著【5 】。1 9 8 5 年 出版了第二本p e t r i 网专著【6 】。从八十年代起，由于p e t r i 网的理论的成熟， 人们把这一学科称为网论( n e tt h e o r y ) ，以区别于图论。目前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 先生在其博士论文中将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 网所提供的系统信息要丰富的多，其分析在 理论上也更为深刻。因此，它被广泛地应用于人造系统模型，是跨越通信 科学、计算机科学、控制科学和系统科学的交叉研究领域，有着广泛的应 用背景。例如，信息高速通信网、交通控制系统陟1 5 】、计算机集成制造系 统、分布式并行处理系统等【1 6 1 。 1 1 1 p e t r i 网的理论背景 随着科学技术的进步，人类社会进入2 l 世纪，计算机科学技术得到 迅猛发展。从单c p u 的串行计算机系统发展到多c p u 的并行计算机系统： 从单纯的文本处理到集文本、图形、一图象和语音等于一体的多媒体处理； 从基于单机环境下的操作到基于网络并行环境下的机群操作；如此种种， 其基本理论模型可以归结为从串行处理的串演系统( 如经典自动机模型 等) 到并行处理的并发系统f 包括：通信顺序进程( c o m m u n i c a t i o ns e q u e n c e p r o c e s s e s ，记为c s p ) 、通信演算系统( c o m m u n i c a t i o nc a l c u l u ss y s t e m s ， 记为c c s ) 、迹语言( t r a c e sl a n g u a g e s ) 、偏序语言、p e t r i 网等) 。由此可见， 并发系统是当今计算机科学技术中一项重要的基础研究课题之一【1 “。 计算机的描述工具有： 1 、形式语言自动机 形式语言与自动机理论 1 7 , 1 8 】是2 0 世纪5 0 年代发展起来的，起初作为 计算机的一个重要分支，它在编译系统、模式识别等方面得到广泛应用。 自8 0 年代以来，它在控制科学、系统科学中也得到广泛应用【1 9 】。 但自动机表达的行为是串语义下的，从而不能很好地刻画并发等重要 现象。 2 、c s p 【2 州与c c s 【2 1 】 c s p 和c c s 都是为处理分布式系统而设计的演算工具，其目标是给 出在不同描述程度上构造和比较不同模型的框架，它们都是以表达式的基 本语法为起点。 西华大学硕士学位论文 c s p 是由英国科学家c a r h o a r e 于1 9 7 8 年提出的一个命令式语 言。一个c s p 程序就是一个进程，每个进程可以平行地分解为许多子进 程，子进程问以进程运算符相连。子进程又可以分解为更深一层的子进程。 这种进程嵌套可达到任一深度i l 。 c c s 是由美国科学家r m i l n e r 于1 9 8 0 年提出的一个函数式语言，它 的基本成分是项，或称动程表达式。动程的组合仍是动程，其组合深度也 是任意的【1 9 】。 发( c o n c u r r e n t ) 、并行( p a r a l l e l ) 是一组重要的概念，二者的关系是前 者大大地包含后者，可以用一段流传甚广的源自名人的话( 大意) ：t w o e v e n t ，s a yaa n db ，a r ec o n c u r r e n t ( o rp a r a l l e l ) i ft h e i ro c c u r r i n go r d e rd o e sn o t c h a n g et h ec o n s e q u e n c e 1 7 1 c s p 、c c s 描述并发现象存在着一些不足，如：其表达式过于复杂， 不便于控制操作：对并发虽有一定刻画【2 0 , 2 1 】，但仍不能很好地反映真并发 行为。 3 、迹语言0 2 1 和偏序语言i 迹语言是由波兰人a m a z u r k i e w i c z l 2 2 】于1 9 7 7 年提出的，它是试图通 过并发系统的序列观察来刻画系统的非序列行为的一种i 具t 1 9 1 。 偏序语言是由j g r a b o w s k i 2 3 】于1 9 7 9 年首先提出的，它对并发行为能 清晰地刻画，被认为是研究并发系统在串语义和进程语义下行为的一个统 一的框架【1 9 】。 然而，这些语言在系统性质( 如活性、公平性等) 方面的刻画与分析 手段仍不令人满意【1 9 j 。 1 1 2 国内外的p e t r i 网的理论研究成果 自p e t r i 开创性的工作之后，p e t r i 网理论得到了长足的进展。p e t r i 网 研究的系统模型行为特性包括：状态的可达性、库所的有界性、变迁的活 性；状态的再生性( 家态，h o m es t a t e ) 、事件之间的同步性和公平性等。 p e t r i 网模型的主要分析方法依赖于：基于图论的方法：可达图；基于线性 西华大学硕士学位论文 代数下的方法：关联矩阵和状态方程、s ( t ) 不变量：基于代数下的方 法：序关系；基于机器模型下的方法：p e t r i 网语言：基于逻辑与代数下的 p e t r i 代数；分析化简规则；结构理论等。p e t r i 网的抽象描述能力也在不 断向纵向和横向扩展。它的横向扩展表现为：原先是没有参数的普通的网， 现在有了时间p e t r i 网【2 4 j 和随机p e t f i 网【2 5 】：原先是一般有向弧，现在有了 约束弧和可变弧；原先资源( t o k e n ) 的个数都是自然数，现在有了概率 标记个数；原先只有普通的原子变迁，现在有了谓词变迁和子网变迁。它 的纵向扩展表现为：原先只有基本的条件事件网【2 6 1 ( c o n d i t i o n e v e n tn e t s ， 记为c e 网) ，后来有了库所变迁( p l a c e t r a n s i t i o nn e t s ，记为p 门n 网1 2 7 】， 现在更有了高级网：包括谓词变迁网fp r e d i c a t e t r a n s i t i o n p e t r i n e t ，记 为p r 厂r 网) 和有色网【2 9 挪 ( c o l o r e dn e t s ) 。 一、带抑制弧p e t r i 网模型( i n h i b i t o r a r c sp e t r in e tm o d e l ) 1 3 1 首先对p e t r i 网模型的重要扩充就是附加一些新型的弧线。早期模型 的引发规则是当有一个以上的标记( t o k e n ) 驻留在每一个输入库所时， 相应的变迁就可以引发，从而改变模型的状态( 这里的输入库所是由从库 所到变迁的弧来定义的) 。抑制弧的定义则相反，当输入库所无标记时变 迁可以引发。抑制弧的引进使p e t r i 网具备了零检验能力i l “。 二、高级p e t r i 网( h i g h 1 e v e lp e t r in e t ) 3 2 , 3 3 p e t r i 网面临的另一个问题是，为了某一个特别的操作建立模型从而必 须建立复杂的编码。一些学者认为，如果以某种方式来区别标记( t o k e n ) ， 可使复杂编码容易实现。目前的有色网和谓词变迁网就是这种思想的体现 1 1 6 1 。 三、时间时延p e t r i 网( t i m e t i m e dp e t r in e t ) 口4 , 3 5 1 随着系统逻辑层分析的进一步深入，必然进行物理层的处理，时间是 系统物理层上的一个重要参数。建立含时间因素的系统分析模型对实际系 统来说是非常必要的。在过去十年中，出现了两类含时间因素的基本p e t r i 网模型。一类是时延p e t r i 网模型，它是由r a m c h a n d a n i 3 4 】提出的。这类 p e t r i 网模型规定每个变迁都具有有限的引发时延，其引发规则被修改为： 4 西华大学硕士学位论文 ( 1 ) 每一个引发变迁都有一个时延过程： ( 2 ) 一个变迁一旦使能就必须立即引发。 时延p e t r i 网主要用于系统的评估方面。另一类是时间p e t r i 网模型， 它是由m e r l i n l 3 5 i 提出的。这类p e t r l 网模型规定每个变迁都对应着一个时 间区间【a b 】，任何一个变迁，当它使能之后，它在时间区间【a ，b 】内便具有 连续使能权。使用这种网m e r l i n 讨论了一些计算机系统和通信进程中的 可达性问题。应该说时间p e t r i 网比时延p e a r l 网更为一般，一个时延p e t r i 网可以表达成一个时间p e t r i 网，反之不行。关于时间( 延) p e t r i 网的一 些分析方法可从参考文献f 3 4 ，3 5 】得到1 1 6 】。 四、随机p e t r l 网( s t o c h a s t i cp e t r in e t ) 口卅 时延p e t r i 网中的时延值如果是一个随机变量，便得到随机p e t r i 网模 型。它是由m o l l o y | 3 6 】首先提出的，参考文献【3 6 】中考察的是有界随机p e t r i 阋，其随机变量服从负指数分布，从而证明了p e t r i 网状态可达图同构于 一个马尔科夫链。m a r s a n 等人【3 7 】推广了m o l l o y 的工作，提出一种广义随 机p e t d 网( g e n e r a ls t o c h a s t i cp e t r in e t ，记为g s p n ) 模型，此模型包括 _ ，某些变迁为立即变迁( 无时延) 的情形。d u g a n 等人f 3s 】从另一角度推广 7m o | l o y 的工作，提出一种增广随机p e t r i 网( e x t e n s i v es t o c h a s t i cp e t r in e t ， 记为e s p n ) 模型，该模型包含了抑制弧的情况。然而，这些工作均未突 破颂指数分布的限制。参考文献【3 9 】等分别从不同角度试图取消负指数分 布伪限制，但仍有待进一步的努力。无论时间( 延) p e t r i 网还是随机p e t r i 网，目前的分析手段基本上是在可达图上操作的，由此产生的状态复杂性 娃难以克服的。为此，寻求新的分析途径，拓宽应用领域是这一方向的进 一步研究目标1 1 6 j 。 五、对象p e l d 网( 0 b j e c tp e t r in e t ) h 町 对象p e t r i 网是由内部结构和外部结构，以及对象与对象之间的消息 传递形成的实际系统模型的控制结构组成的。对象内部包含了该对象自身 的属性以及处理这些数据的方法。在对象p e t r i 网模型中，对象的属性( 即 数据结构或数据类型) 是由库所表示的。对象的外部结构是消息接口，库 5 西华大学硕士学位论文 所是对象中唯一与外界( 其他对象实体) 进行消息传输的接口，其中包括 消息接收接口和消息发送接口。对象的消息接收接口和消息发送接口是成 对出现的，分别与对象内的某个方法的输入弧和输出弧相连。消息隐藏在 消息传递接口库所中的t o k e n 中，如果不同的对象同时向一个对象发送同 一个消息，则在此对象的该消息接收接口中形成一个消息队列。同理，在 浚对象的消息发送接口中电有可能会产生一个消息队列。对象p e t r i 网系 统通过对象间的控制结构协调各对象间的消息传递，对象控制结构有一类 具有特殊含义的变迁和库所实现【1 6 j 。 六、时序p e t r i 网( t e m p o r a lp e t r in e t ) 【4 1 , - 4 3 1 1 9 8 5 年，s u z u k i 提出一种新网子类：时序p e t r i 网，引入了时序逻辑 操作，通过时序逻辑公式控制或限定p e t r i 网的变迁引发序列，描述系统 事件之间的时序关系，并且反映出系统的基本性质。因此，时序p e t r i 网 特别适合作为并发系统的建摸、分析和验证工具i l 。 七、被控p e t r i 网( c o n t r o l l e dp e t r in e t ) 4 4 1 被控p e t f i 网是在p e t r i 网中引入一组外部输入的库所，这些外部输入 库所中的t o k e n 数决定变迁的发生或限制变迁的发生次数控制的状态为输 入库所中的t o k e n 数，由反馈策略决定。反馈控制是基于外部输入库所的 离散事件动态系统协调反馈控制综合，根据需求规范和原系统的p e t r i 网 模型，综合出附加的控制器p e t f i 网模型，同原p e t r i 网合成便形成了满足 需求的受控p e t r i 网模型l l 。 八、混合p e t r i 网( h y b r i dp e t r in e t ) t 4 5 1 混合控制系统是由实时决策子系统与实时数值( 开环或闭环) 子系统 组成的复杂的控制系统。实时决策子系统确定分布系统( 全局的或局部的) 控制模态的转移；每一个控制模态下，实现特定活动功能的实时数值控制 子系统与被控对象、传感器和执行器组成传统的数值控制回路。但由于混 合系统的复杂性，使得每个控制模态下的状态特征量不仅仅是被控对象 向数值控制器的连续量或数值量反馈，还有来自被控对象的符号量或离散 事件特征量，这些量组成模态下的混合状态1 1 6 1 。 6 西华大学硕士学位论文 混合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 网的实值发生规则【l 。 九、p e t r i 网语言i 圳 在自动机与形式语言中语言、自动机是同一的。既然p e t r i 网是图论 的高级阶段，那么自动机与形式语言的研究方法也可以运用于p e t r i 网的 研究中。 p e t r i 网语言是研究p e t r i 网的一个手段，目前形成一个重要的研究方 向。h a c k 4 6 】和p e t e r s o n 4 1 7 1 最早从事这方面的研究。将一个p e t r i 网所有可 能引发序列的集合视为该网产生的语言，文4 8 ，4 9 研究了语言的封闭 性，以及与经典形式语言的关系。h a c k 在参考文献【3 1 】中还讨论了网模型 的计算能力，指出带抑制弧的增广p e t r i 网与著名的图灵机在计算能力上 是等价的，从而充分显示出p e t r i 网模型的表达能力。另外，r o z e n b e r g 等 人【5 0 】在事件多重集上讨论了子集语言的类似问题，参考文献1 5 1 】给出了 p e t r i 网语言的一个很好综述，这以后的工作还有参考文献【5 2 】给出了p e t r i 网语言与形式语言关系的一个清楚刻画。参考文献【5 3 】分别从各个角度研 究了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 网语言研究的不成熟性，同 时也为人们展现出新的极具吸引力的研究方向。 国内以山东科技大学吴哲辉教授、同济大学蒋昌俊教授为代表，一直 西华大学硕士学位论文 从事于这方面的研究，做了系列的工作，其研究成果体现在文 1 6 ，1 9 】 1 2p e t r i 网的应用 p e t r i 网有着广泛的应用背景。随着信息处理系统的日益庞大和复杂 化，人们越来越需要采用系统工程的方法来设计和维护信息处理系统。在 信息处理系统的整个生命期内，采用图形化的数学工具来完成：系统的形 式描述、系统的正确性验证、系统性能的评价、系统的目标实现和测试是 非常必要的。p e t r i 网是适应上述各项任务的有效工具，可以在一个p e t r i 网系统模型的框架上完成各项任务。在这一点上，其它图形或数学工具都 不具备如此完整的功能1 4 1 。 1 2 1 应用于柔性制造系统、计算机机械制造系统和智能制造系统的建模、 分析、控制和优化设计5 4 1 p n ( p e t r i n e t s ) 在计划调度领域的研究最早是在2 0 世纪8 0 年代提出来 的【5 5 j ，一般仅是分析计划调度问题的可行性与可达性【5 6 。射。在现代企业 生产中，获取最大利润是每个生产经营者的最大目标，合理优化的计划调 度策略是保证企业取得上述目标的关键。当一个企业确立了其发展规划和 长期计划后，就按照预先设定计划方案发展。然而，在实际生产环境中， 制造系统经常受外部随机事件的干扰【5 ，如设备故障、缺货、更换交货日 程等。如何及时调整计划，制定合理优化调度策略，使企业尽快按照预先 的计划调度策略完成任务，是当前企业界迫切需要解决的课题。文献 6 0 1 介绍了一种实时调度策略应用于制造系统的例子。还有一些文献着重介绍 了p n 用于柔性制造系统的方法，路由器动态调度的优化问题，工作流设 计及其优化等1 6 l 6 2 1 。文献f 6 3 1 提出了一种用p e t r i 网模型的变迁计数器来 西华大学硕士学位论文 对连续故障进行分析的方法。 一、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 ) o o 的 j 虹用比较典型。一般采用随机p e t r i 网为柔性制造系统建模。p e t r i 网有一 个重要的优点，它可以从设计的第一步到系统的实现提供统一的模型工 具。p e t r i 网模型提供： 1 ) 图形的、准确的形式描述，这可以使设计者、拥有者和用户之间进 行关于系统行为的深入对话； 2 ) 良好定义的理论，它可进行模型性质( 活性，公平，有界等) 的验证； 3 ) 性能评价的理论和方法( 指随机网) ； 4 ) 系统实现技术，包括实时控制软件的代码产生技术。 由于f m s 是复杂、大型的系统，在使用随机p e t r i 网对这样的系统进 行模拟时，可以采用细分和抽象的方法。这种方法可以建立起层次结构化 的网模型；子模型模块的合并可以是简单的子系统及成为复杂的整个系 统。文献【6 4 】提出了一种改进的p e t r i 网模型，可充分发挥f m s 的柔性制 造能力。 二、p e t r i 网应用于工作流、物流等建模 工作流是一类能够完全或者部分自动执行的业务过程，根据一系列过 程规则，文档、信息或任务能够在不同的执行者之间传递、执行。 一般来说，对工作流的分析主要有以下3 个方面： 1 1 有效性，也就是说，测试工作流是否按照设计的要求来运转； 2 ) t 确性，即工作流模型应该是没有错误的； 3 ) 性能分析，