（计算机软件与理论专业论文）自控网系统的理论及应用研究.pdf

西华大学硕士学位论文 自控网系统的理论及应用研究 计算机软件与理论专业 研究生杨松指导教师宋文 摘要 p e t r i 网适合于网络环境下的信息处理系统的描述和建模。它的主要特性包 括：并行、不确定性、1 异步及分步描述能力和分析能力。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 r i l 网的研究的方法论； 另外，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 ) 由于自控系统的非线性关系，无法直接套用其他网系统的分析技术，目 前对自控系统的研究成果并不多；而且正是由于自控系统的非线性关系，它有 第l 页 西华大学硕士学位论文 更强的描述能力，因此，对自控系统的研究具有重要的意义；但人们在建模的 过程中，往往需要通过模型的发生，然后去观察模型发生结果是否正确，随着 模型规模的增长，人为的分析模型运行结果( 变迁序列发生后的后继标识) 就 越来越困难。基于这点提出了自控系统下计算后继标识的程序设计方法，实现 了只需输入初始标识、关联矩阵和变迁发生序列就能得到后继标识的算法。最 后利用该程序对f i b o n a c i i 数列的自控网模型进行分析，验证了该算法的正确性 和实用性，同时也为自控网及其它的子类的应用研究的分析与验证提供了一种 耨的途径。 一 f 2 ) 由于自控网有较好的模拟能力，所以对自控网的应用研究显得尤为重 要。本文运用自控网系统定义了加、减、乘、除四种基本运算以及2 个算予的 自控网模型，并巧妙地运用p e t f i 网抽象与细化的概念，通过逐级抽象方法建立 了递归关系的自控网模型，并用( 1 ) 所得到的结果( 程序) 验证了所建立的递归模 型的正确性和实用性。同时也为利用p e t r i 网建立递归关系模型形成了一种方 法，这种分级分析方法也是利用p c t r i 网进行形式化软件开发的一种新途径。 关键词：p c t r i 网；自控网：程序设计；递归关系；模拟 第页 西华大学硕士学位论文 t h er e s e a r c ho f t h e o r ya n da p p l i c a t i o nb a s e do n c y b e r n e ts y s t e m 。 y a n g s o n g ( c o m p u t e rs o f t w a r et h e o r e t i e s ) d i r e c t e db yp r o ls 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 mi 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 n a n d a n a l y s i sa b i l i t y w i t h t 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 ev a r i e t yo fa p p l i c a t i o n si nd e s c r i p t i o na n dm o d e l i n g o 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 sa r eu s e f u lt o d e s c r i p t i o no f m u l t i - p r o c e s s o rc o m p u t e rs y s t c m ，c o m p u t e rn 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 o o n p e t r in e t s ，a sa g r a p h i c1 0 0 l ，n o to n l yb ea v i s u a l i z e t li n t e r a c t i v et o o l ，s u c ha sf l o w c h a f e ，f z a m ec h a r e ，n e tg r a p h , b u ta 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 g s t a t i ci n t u i t i o n a lg r a p h w h i c hj 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 e m e a n t i m e ，p e t r in e ti 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 n o ft h el a t t e rc 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 s h a v et 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 hh a v e p 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 sa m a t h s t 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 ta n dc o n n e c ti tw i t h l 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 mc o n v e n i e n ta n a l y s i st o o l ， 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 ou 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 h w a yt h e o r y o fp e t r in e t s i n a d d i t i o n , p e t r i n e th a s s 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 ni m p o a a n tc o n c e p ti nc o m p u t e r s 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 e 锄d e f i n ep r o c e s sb yu s i n ga 第m 页 堕兰盔堂堡主兰垡丝奎 s 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 h i sw h a tc l a s s i c a lg r a p ht h e o r y c o u l d n td o i nt h i sp a p e r , t h em a i nw o r ki so p e r a t e do n , as u b n e to fp e t r in o t t h r o u g h p e t r i - n e tl a n g u a g ea n dp r o g r a m m i n gm e t h o d ，w ed e v e l o pad e e pr e s e a r c ht ot h e t h e o r ya n da p p l i c a t i o n so fc y b e r - n o ts y s t e m ，a n do b t a i nag o o de f f e c t i n c l u d i n gt h e f o l l o w i n gm a i nc o n t r i b u t i o n s ： ( 1 ) b e c a u s ec y b e r - n e ts y s t e mi st h e1 1 0 1 1 - l i n e a rr e l a t i o n ，a n di t c a nn o ta p p l y m e c h a n i c a l l yt h ea n a l y s i st e c h n o l o g yo fo t h e rn e ts y s t e m s c u r r e n t l y , t h er e s e a r c h p r o d u c t i o na b o u tc y b e rn e ts y s t e mi sl i t t l e ；b u tj u s ta b o u tt h en o n - l i n e a rr e l a t i o no f c y b e rn e ts y s t e m ，i th a st h ep o w e r f u ld e s c r i p t i o nf u n c t i o n , s oi ti si m p o r t a n t t os t u d y c y b e rn e ts y s t e m ；b u ti nt h ep r o c e s so fm o d e l i n g , j u d g i n gt h er e s u l tc o r r e c to r h o ti s t h r o u 【g ht h eo c a ：o r r e i l c eo fm o d e l h o w e v e rw i t ht h eg r o w i n g 默7 , a l eo fm o d e l , i ti s m o r ea n dm o r ed i f f i c u l tt oa n a l y z et h ee x e c u t i n gr e s u l t s b e c a u s e o ft h e s ed i f f i c u l t i e s ， w ep r e s e n tt h ep r o g r a m m i n ga p p r o a c ho fc o m p u t i n gs u c c e s s o rm a r k i n g , w ec a ng a i n t h es u c c e s s o rm a r k i n gt h r o u g ho n l yi n p u t t i n gi n i t i a lm a r k i n g 、i n c i d e n c em a t r i xa n d t r a n s i t i o no c c u r r e n c es e q u e n c e f i n a l l yw eu t i l i z e dt h ep r o g r a mt oa n a l y z et h em o d e l o fc y b o r - n o ta b o u tf i b o n a c i is e q u e n c e ，a n dt e s t i f i e dt h ea c c u r a c ya n dp r a c t i c a b i l i t y o ft h i sa l g o r i t h m ，m e a n w h i l ep r o v i d i n gan e wa p p r o a c h f o rt h ea p p l i c a t i o no fc y b e r n e ts y s t e ma n do t h e rs u b c l a s s ( 2 ) b e c a f l s eo fag o o dm o d e l i n ga b i l i t y a b o u tc y b e rn e ts y s t e m ，s oi tw a s n o t i c e a b l ei m p o r t a n c et ot h er c s e a r c ha b o u tc y b e rn e ts y s t e m t h i st h e s i se m p l o y e d t h ec y b e rn e ts y s t e mt od e f i n ea d d i t i o n , s u b t r a c t i o n , m u i t i p l i c a t i o n , d i v i s i o n ，f o u r b a s i co p e r a t i o n sa n dt w oo p e r a t o r sc y b e rn e tm o d e l i na d d i t i o nt h r 0 1 l g hs u b t l y e m p l o y i n gt h ea b s t r a c ta n d t h i nc o n c e p to fp e t r in e ta n du s i n gs t e pb ys t e pa b s t r a c t m e t h o d s ，w ee s t a b l i s hr e e u r s i v ec y b c rn e tm o d e i b yu 此i n gt h er e s u l t f r o m p r o c e d u r e1 , w ep t o v e dt h a t t h er e c u r s i v em o d e le s t a b l i s h e dw a sa c c u r a t ea n d p r a c t i c a l 礅a l s op r o v i d e san e wm e t h o df o ru t i l i z i n gp e t r in e tt oe s t a b l i s h i n g r e c u r s i v em o d e l ，m e a n w h i l es t e pb ys t e pa n a l y z i n gm e t h o dw a sa l s oan e wa p p r o a c h t od e v e l o pf o r m a ls o f t w a r eb yu s i n gp e t r in e l k e yw o r d s ：p e t r in e t s ；c y b e rn e ts y s t e m ；p r o g r a md e s i g n ；r e e u r s i o n ； s i m u l a t i o n 第页 西华大学硕士学位论文 申明 本人申明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了丈中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期闻在导师指导下取得缒，论文成 果归西华大学所有，特此申明。 第5 3 页 垆节 唔l 又耜& 匆孽例摩 签 签 西华大学硕士学位论文 第一章绪论 1 1p e t f 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 ”( 用自动机通讯) f 1 】中提出。p e t r i 阐述了一台计 算机中的两个异步分支间的通讯理论基础，并特别注意到事件之间因果关系的 描述。c a r l a d a m p e t r i 的开创性工作立即引起了欧美学术界和工业界的注意i ”】， 后来逐步为科技界所接受，现在已是人们常用的一种数学工具 4 l ，他的论文也 成为p e t r i 网理论研究发展的奠基石。 1 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 f t e c h n o l o g y ) 的计算结构研 究小组积极参与p c t d 网相关的研究，1 9 7 5 年7 月在m r r 举行了第一次p e 仃i 网 和相关方法的研讨会。1 9 8 1 年p c t c r s o n 出版了第一本p e t r i 网方面的专著 5 1 。1 9 8 5 年出版了第二本p e t d 网专著闱。从八十年代起，由于p e t r i 网的理论的成熟，人 们把这一学科称为网论( n e tt h e o r y ) ，以区别于图论。目前p c t r i 网理论与应用研 究的状况是：几乎所有与信息科学有关的学术期刊及会议论文集中都能见到涉 及p e t d 网的论文；每年都有以p c t d 网理论和应用为主题的国际会议和专题会 议；许多高校都在教授p c t d 网课程：每年都有p c t r i 网的学术著作问世。到1 9 8 7 年已有2 0 7 4 篇重要的相关论文发表【”。四十余年的发展足以证明p e t r i 网的生 命力i s 。 p e t r i 先生在其博士论文中创立了一种用于并发通信机理描述的新型“自动 机”模型。众所周知，传统的自动机模型适用于描述顺序处理的计算机系统， 而p e t r i 网则适合于描述异步并发行为的系统问题。如果说自动机是对顺序系统 行为机理的直接描述，那么p e t r i 网在两个层面上对并发系统的行为机理给予充 分的描述。首先，p e t r i 网直接展现并发系统的物理结构层次及资源状态的初始 分布情况：其次，在p e 啊网引发规则的作用下将间接展现出该并发系统的动态 第1 页 西华大学硕士学位论文 行为机理。这两个方面相互关联，形成了一个集物理结构和行为机理于一体的 集成模型。同顺序处理系统的自动机模型相比，p e t r i 网以其静态的结构展示动 态的行为，而以图灵机为代表的模型仅有静态结构不能刻画系统动态行为。p e t r i 网所提供的系统信息要丰富的多，其分析在理论上也更为深刻。因此，它被广 泛地应用于人造系统模型，是跨越通信科学、计算机科学、控制科学和系统科 学的交叉研究领域，有着广泛的应用背景。例如，信息高速通信网、交通控制 系统1 9 - 1 6 1 、计算机集成制造系统、分布式并行处理系统等1 1 7 1 。 1 1 1p e t r i 网的理论背景 随着科学技术的进步，人类社会进入2 1 世纪，计算机科学技术得到迅猛发 展。从单c p u 的串行计算机系统发展到多c p u 的并行计算机系统；从单纯的 文本处理到集文本、图形、图和语音等于一体的多媒体处理；从基于单机环境 下的操作到基于网络并行环境下的机群操作；如此种种，其基本理论模型可以 归结为从串行处理的串演系统( 如经典自动机模型、a 演算模型、p o s t 系统模 型等) 到并行处理的并发系统俾e 仃i 网、通信顺序进程( 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 o s ) 、迹语言( t r a c 七sl a n g u a g e s ) 、偏序语言等) 。由此可见，并发系统是当今计 算机科学技术中一项重要的基础研究课题之一【堋。 ， 计算机的描述工具有： 1 、形式语言自动机 形式语言与自动机理论1 1 8 , 1 9 】是2 0 世纪3 0 年代发展起来的。在这同一时期， 丘奇、波斯特和图灵等人围绕着怎样判断一类数学问题是否是机械可解的这样 一个问题，从不同的角度考察了计算这一概念，并探索了计算这一概念所包容 的内涵。其中，以图灵的研究与实际计算机更为接近，他提出的形式化的理想 计算模型深刻地揭示了计算这一本质概念，为能行计算理论奠定了基础。正是 因为机器模型的建立，2 0 年后才诞生了第一台计算机。以图灵机为基础的形式 语言分析起初作为计算机的一个重要分支，它在编译系统、模式识别等方面得 第2 页 西华大学硕士学位论文 到广泛应用。自8 0 年代以来，它在控制科学、系统科学中也得到广泛应用 2 0 1 。 但自动机表达的行为是串语义下的，从而不能很好地刻画并发等重要现象1 2 0 l 。 2 、c s f 2 1 】与c c s l 2 2 】 。 c s p 和c c s 都是为处理分布式系统而设计的演算工具，其目标是给出在不 同描述程度上构造和比较不同模型的框架，它们都是以表达式的基本语法为起 点【刎。 c s p 是由英国科学家c a r h o a r c 于1 9 7 8 年提出的一个命令式语言。一 个c s p 程序就是一个进程，每个进程可以平行地分解为许多子进程，子进程间 以进程运算符相连。子进程又可以分解为更深一层的子进程。这种进程嵌套可 达到任意深度【冽。 、 c c s 是由美国科学家m i l n e r 于1 9 8 0 年提出的一个函数式语言，它的基 本成分是项，或称动程表达式。动程的组合仍是动程，其组合深度也是任意的 1 2 0 玎演算是基于c c s 上发展起来的一类进程演算模型，石演算的语法和语义 的研究目前较为活跃。 、并发( c o n c u r r e n t ) 、并行( p a r a l l e l ) 是一组重要的概念，二者的关系是前者大大 地包含后者，可以用一段流传甚广的源自名人的话( 大意) ：t w oe v e n t , s a ya a n d b 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 r o c c u r r i n g o r d e rd o e sn o tc h a n g et h e c o n s e q u e n c e 【8 1 尽管c s p 、c c s 、万演算和p e t r i 网具有很好的模拟能力和分析演算能力， 但它们仍存在着以下不足。c s p 、c c s 、石演算如同形式语言自动机一样，其处 理是针对系统运行机制的，没有反映系统物理结构信息，不便于系统结构设计 和处理；由于其表达形式较自动机的语言更为繁杂，不便于控制操作；c s p 、 c c s 、石演算所刻画的并发是交叠式语义，而非真并发式语义1 2 1 , 2 2 1 。 3 、迹语言1 2 3 1 和偏序语言【2 4 】 迹语言是由波兰人am a z u r k i 倒v i c z 2 a l 于1 9 7 7 年提出的，它是试图通过并发 系统的序列观察采刻画系统的非序列行为的一种工具【捌。 偏序语言是由j c n - a b o w s k i l 2 4 1 于1 9 7 9 年首先提出的，它对并发行为能清晰 第3 页 西华大学硕士学位论文 地刻画，被认为是研究并发系统在串语义和进程语义下行为的一个统一的框架 【捌。 在描述并发环境的模型家族中，各成员各有自己的优劣。p e t f i 网理论的诞 生并不仅是在这个家族中添加了一个新的成员，而是显示出它在描述对象的时 候的深刻性。的确，迹语言或并发控制语言对并发系统的行为，尤其是并发行 为都能给出很好的刻画，而且起到了各种语义之间关系的桥梁作用。然而，这 些语言在系统性质( 如活性、公平性等) 方面的刻画与分析手段仍不令人满意 例。 1 1 2国内外的p e 仃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 i r i 网语言；基于逻辑与代数下的p e 砸代数：分析化简规则；结构理论等。p e t r i 网的抽象描述能力也在不断向纵向和横向扩展。它的纵向扩展表现为：从基本 网到基本的条件事件网瞄l ( c o n d i t i o n e v e n tn e t s , 记为c e 网) ，c e 系统是基本 网系统的扩展，它允许动态行为的描述时除了向前的运动，还允许向后的回顾； 接着从基于逻辑描述的基本网系统和c 疆系统扩展到包括多t o k e n 的库所变迁 ( p l a c e t r s a m i t i o nn e t s ，记为p ，n 网，再发展到可以描述谓词逻辑的谓词变迁 网1 2 1 ( p r e d i c a t et r a n s i t i o np e l r ln 鸭记为p r t 网) 和对t o k e n 分类的有色网 i 嚣2 9 l ( c o l o r e dn e a ) 。它的横向扩展表现为：原先是没有参数的普通的网，现在 有了时间p e t r i 网闭j 和随机p e t r ii i l l 7 1 ：原先是一般有向弧，现在有了约束弧和 可变弧；原先资源( t o k e n ) 的个数都是自然数，现在有了概率标记个数【3 1 捌： 原先只有普通的原子变迁，现在有了谓词变迁和子网变迁。p e t r i 网的发展是便 第4 页 西华大学硕士学位论文 于用恰当的模型定义方便于问题的规范、建模j 模型检测等。 一、带抑制弧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 ) 3 3 1 首先对p e t r i 网模型的重要扩充就是附加一些新型的弧线。早期模型的引发 规则是当输入库所被标识时，相应的变迁就可以引发，从而改变模型的状态( 这 里的输入库所是由从库所到变迁的弧来定义的) 。抑制弧的定义则相反，当抑制 的输入库所不被标识且其他输入库所被标识时变迁可以引发。抑制弧的引进使 p e t r i 网具备了零检验能力旧。 二、高级p e t r i 网( h i g h l e v e lp e t a ln e t ) 1 3 4 , 3 5 1 p e t r i 网面临的另一个问题是，为了某一个特别的操作建立模型从而必须建 立复杂的编码。一些学者认为，如果以某种方式来区别标记o o k e n ) 。可使复杂 编码容易实现。目前的有色网和谓词变迁网就是这种思想的体现旧。 三、时间时延p e t r i 网( t u n e t i m e dp e t r in e t ) 1 3 6 , 3 7 随着系统逻辑层分析的进一步深入，必然进行物理层的处理，时间是系统 物理层上的一个重要参数。建立含时间因素的系统分析模型对实际系统来说是 非常必要的。在过去十年中，出现了两类含时间因素的基本p e t r i 网模型。一类 是时延p e t r i 网模型，它是由r a m c h a n d a n i 3 6 1 提出的。这类p e t r i 网模型规定每 个变迁都具有有限的引发时延，其引发规则被修改为： ( 1 ) 每一个引发变迁都有一个时延过程： ( 2 ) 一个变迁一旦使能就必须立即引发。 时延p e t r i 网主要用于系统的评估方面。另一类是时间p e t r i 网模型，它是由 m e r l i n 3 7 j 提出的。这类p e t r i 网模型规定每个变迁都对应着一个时间区间【曲】， 任何一个变迁，当它使能之后，它在时间区间【a ，b 】内便具有连续使能权。使用 这种网，m e r l i n 讨论了一些计算机系统和通信进程中的可达性问题。应该说时 间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 网的一些分析方法可从参考文献 3 6 ，3 7 得 到【切。 四、随机p e t r i 网( s t o c h a s t i cp e t r in e t ) l 叫 时延p e t r i 网中的时延值如果是一个随机变量，便得到随机p e t r i 网模型，它 第5 页 西华大学硕士学位论文 是由m o l l o y 3 8 嗜先提出的，参考文献 3 8 1 q ，考察的是有界随机p e t r i 网，其随机 变量服从负指数分布，从而证明了p e t d 网状态可达图同构于一个马尔科夫链。 m a r s a n 等人1 3 9 推广了m o l l o y 的工作，提出一种广义随机p e t r i 网( g e n e r a l s t o c h a s t i cp e t r in e t , 记为g s p n ) 模型，此模型包括了某些变迁为立即变迁( 无 时延) 的情形。d u g a n 等人i 加】从另一角度推广了m o l 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 s p n ) 模型，该模型包含了 抑制弧的情况。然而，这些工作均未突破负指数分布的限制。参考文献【4 l 】等 分别从不同角度试图取消负指数分布的限制，但仍有待进一步的努力。无论时 间( 延) p e t r i 网还是随机p e t r i 网，目前的分析手段基本上是在可达图上操作的， 由此产生的状态复杂性是难以克服的。为此，寻求新的分析途径，拓宽应用领 域是这一方向的进一步研究目标【1 7 1 。 五、对象p e t r i 网( o b j e c tp e t r in e t ) 1 4 2 1 对象p e t r i 网是由内部结构和外部结构，以及对象与对象之间的消息传递形 成的实际系统模型的控制结构组成的。对象内部包含了该对象自身的属性以及 处理这些数据的方法。在对象p e t r i 网模型中，对象的属性( 即数据结构或数据 类型) 是由库所表示的。对象的外部结构是消息接口，库所是对象中唯一与外 界( 其他对象实体) 进行消息传输的接口，其中包括消息接收接口和消息发送 接口。对象的消息接收接口和消息发送接口是成对出现的，分别与对象内的某 个方法的输入弧和输出弧相连。消息隐藏在消息传递接口库所中的t o k e n 中， 如果不同的对象同时向一个对象发送同一个消息，则在此对象的该消息接收接 口中形成一个消息队列。同理，在该对象的消息发送接口中也有可能会产生一 个消息队列。对象p e t r i 网系统通过对象间的控制结构协调各对象间的消息传 递，对象控制结构有一类具有特殊含义的变迁和库所实现【切。 六、时序p e 打i 网( t e m p o r a lp e t r in e t ) 1 4 ”引 1 9 8 5 年，s u z u k i 提出一种新网子类：时序p e t r i 网，引入了时序逻辑操作， 如o ( n e x 0 、口( 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 网特别适合作为并发系统的建摸、分析和验证工 第6 页 西华大学硕士学位论文 具1 1 7 1 。 七、被控p e t i i 网( c o n t r o l l e dp e t r in e t ) 4 6 1 被控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 网模型1 1 7 1 。， 八、混合p e t r i 网( h y b r i dp c t r in e t ) 1 4 7 混合控制系统是由实时决策子系统与实时数值( 开环或闭环) 子系统组成 的复杂的控制系统。实时决策子系统确定分布系统( 全局的或局部的) 控制模 态的转移；每一个控制模态下，实现特定活动功能的实时数值控制子系统与被 控对象、传感器和执行器组成传统的数值控制回路。但由于混合系统的复杂性， 使得每一个控制模态下的状态特征量不仅仅是被控对象向数值控制器的连续量 或数值量反馈，还有来自被控对象的符号量或离散事件特征量，这些量组成模 态下的混合状态【r 丌。 混合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 网的实值发生规则 1 1 7 1 。 九、p c t l i 网语言【1 7 】 在自动机与形式语言中语言、自动机是同一的。既然p e t r i 网是图论的高级 阶段，那么自动机与形式语言的研究方法也可以运用于p e t r i 网的研究中。 p e r i l 网语言是研究p e t r i 网的一个手段，目前形成一个重要的研究方向。 h a c k 4 8 1 和p e t e r s o n l 5 最早从事这方面的研究。将一个p e t r i 网所有可能引发序列 第7 页 西华大学硕士学位论文 的集合视为该网产生的语言，3 乏 4 9 ，5 0 】研究了语言的封闭性，以及与经典形式 语言的关系。h a c k 在参考文献【3 3 】中还讨论了网模型的计算能力，指出带抑制弧 的增广p e t r i 网与著名的图灵机在计算能力上是等价的，从而充分显示出p e t r i 网模型的表达能力。另外，r o z e n b e r g 等人【5 1 】在事件多重集上讨论了子集语言 的类似问题，参考文献【5 2 】给出了p e t r i 网语言的一个很好综述，这以后的工作 还有参考文献【5 3 】给出了p e t r i 网语言与形式语言关系的一个清楚刻画。参考文 献 5 4 1 分别从各个角度研究了p e t r i 网语言的性质。然而，同经典形式的语言相 比，p e t f i 网语言还显得不那么成熟。首先，没有建立p e t r i 网语言的表达层次及 相应的文法关系，只将p e t r i 网看成语言的产生器，而没有考察作为识别器的可 能。还有，就p e t r i 网讨论的一些重要性质( 如活性) 则缺少以语言的形式加以 刻画和分析。这方面的问题既反映出p e t r i 网语言研究的不成熟性，同时也为人 们展现出新的极具吸引力的研究方向j 。 语言是对模型的动态行为的一种刻画。它是用代数方法研究模型的行为理 论的一种有效的工具。自动机与形式语言相辅相成，其相互渗透启发了网人对 p e t r i 网语言研究的兴趣，但是历史只是一种借鉴，不能做为一种复制。目前国 内外的研究都受制于复制，缺乏扩展和新的手段的实现。 。 国内以山东科技大学吴哲辉教授、同济大学蒋昌俊教授为代表，一直从事 于这方面的研究，做了系列的工作，其研究成果体现在文献 1 7 ，2 0 ，5 3 1 。 1 2 p e t r i 网的应用 软件开发的形式化方法是建立在严格数学基础上，它是软件开发过程中分 析、设计及实现的系统工程方法，形式化方法可以帮助软件工程师创建更为简 洁、准确、无歧义的规格说明，进而通过严格的验证分析发现软件设计及开发 过程中的不一致性、模糊性和不完备性，以达到对软件质量、开发成本及开发 进度的有效控制。形式化方法分为形式化规格说明和形式化验证。前者是通过 具有明确数学定义的文法和语义方法或语言对软件的期望特性或行为进行精 确、简洁的描述；后者是基于已建立的形式化规格说明对软件的相关特性进行 第8 页 西华大学硕士学位论文 评价的数学分析和证明p e t r i 网是满足上述两个要求的很好的描述工具。可以 在一个p e 仃i 网系统模型的框架上完成各项任务。在这一点上，其它图形或数学 工具都不具备如此完整的功能【4 】。 1 2 1应用于柔性制造系统、计算机初械制造系统和智能制造系统的建模、分 析、控制和优化设计【5 5 1 p e t r i 网在计划调度领域的研究最早是在2 0 世纪8 0 年代提出来的【5 6 】，一般 仅是分析计划调度问题的可行性与可达性 s v - 5 9 1 。在现代企业生产中，获取最大 利润是每个生产经营者的最大目标，合理优化的计划调度篆略是保证企业取得 上述目标的关键。当一个企业确立了其发展规划和长期计划后，就按照预先设 定计划方案发展。然而，在实际生产环境中，制造系统经常受外部随机事件的 干扰i 卯】，如设备故障、缺货、更换交货日程等。如何及时调整计划，制定合理 优化调度策略，使企业尽快按照预先的计划调度策略完成任务，是当前企业界 迫切需要解决的课题。文献【6 1 】介绍了一种实时调度策略应用于制造系统的例 子。还有一些文献着重介绍了p e t r i 网用于柔性制造系统的方法，路由器动态调 度的优化问题，工作流设计及其优化等1 6 2 一。文献【“】提出了一种用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 ) 中的应用 比较典型。一般采用随机p e t r i 网为柔性制造系统建模。p e t r i 网有一个重要的