（计算机软件与理论专业论文）基于petri网的几个并发问题的建模与分析.pdf

西华大学学位论文 作者郑重声明：所呈交的学位论文， 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均己在论文中做了明确的说明并表示了谢意。 + 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：棚 日期： 如l 石i o 西华大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，在校 攻读学位期间论文工作的知识产权属于西华大学，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，西 华大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复印手段保存和汇编本学位论文。( 保密的论文在解 密后遵守此规定) 学位论文作者签名：研跌p f l 日期： 多口f ，9 舯挪签名：壤 日期 劢6 ， 西华大学硕士学位论文 摘要 p e t r i 网不仅可以采用可视化图形描述而且可被形式化的数学方法所支持，是一种形 式化、图形化的分布式系统建模和分析工具。它不但能够精确地分析系统的静态特性， 而且能够很好地分析系统的动态行为性质，从而很好地刻画系统的动态行为、分析系统 的性能。它既可采用形式化直观的图形表示，又可以引入许多数学方法对其性质进行分 析与验证。 目前，大多数的软件系统都是并发系统，并发是衡量系统运行效率高低的一个参数 标准。为了达到“事半功倍”的效果，现在的系统环境越来越需要并发，只有这样才能 更好地利用系统资源环境，才能使一个系统具有更强的竞争力。p e t r i 网作为一个优秀的 形式化描述和分析工具，能很好地描述和分析这类系统。采用软件形式化技术，不仅有 利于开发人员之间的沟通，提高软件的可靠性，而且可以尽可能地缩短开发的总体时间， 减少软件设讨早期阶段的错误。 本文的主要工作如下： ( 1 ) 在p e t r i 网下对哲学家就餐问题模型进行了分析。哲学家就餐问题是描述在共 享资源下同步与并发的经典案例，活性与无饥饿性是求解此问题的前提，效率是基本要 求。由于对资源的竞争使几个哲学家不可能同时处于就餐状态，在考虑公平性的情况下 定义了延迟p e t r i 网( d e l a y e dp e t r i n e t ) 的概念。解决了竞争资源引起的冲突，并提高了 就餐的效率。 ( 2 ) p e t r i 网下对信道复用的建模与改进。解决了用户要求通信且被要求的用户也 空闲，但信道被占用；几个用户同时向另外几个用户请求通信时，而另几个用户正在通 信中。考虑到信道的利用率及对共享资源带来的冲突，本章采用栈技术对这一问题进行 了分析与验证，提出了一个应用性更强，应用范围更广的p e t r i 网模型。 关键词：p e t r i 网；异步并发；形式化方法；s 一不变量；建模；系统分析 基于p e t r i 网的几个并发模型的建模与分析 a b s t r a c t p e t r in e t sc a l ln o to n l yu s ev i s u a lg r a p h i cd e s c r i p t i o n ，b u ta l s oc a nb es u p p o r t e db y f o r m a lm a t h e m a t i c a lm e t h o d s ，i ti sak i n do ff o r m a l i z e d , g r a p h i c a ld i s t r i b u t e ds y s t e m m o d e l i n ga n da n a l y s i st o o l s i tc a l la n a l y z es y s t e ms t a t i cc h a r a c t e r i s t i c sa c c u r a t e l ya n d a n a l y z es y s t e md y n a m i cb e h a v i o rw e l l ，t h e r e b yg o o dd e p i c t i n gs y s t e md y n a m i cb e h a v i o ra n d a n a l y z i n gs y s t e mp e r f o r m a n c e i tm a ya d o p tf o r m a l i z e dv i s u a lg r a p h i c sa n di n t r o d u c em a n y m a t h e m a t i c a lm e t h o d st oa n a l y z ea n dv e r i f yi t sp r o p e r t i e s a tp r e s e n t ，m o s ts o f t w a r es y s t e m sa r ec o n c u r r e n c es y s t e m s ，i ti sap a r a m e t e rs t a n d a r d w h i c hc a nb eu s e dt om e a s u r eo p e r a t i o ne f f i c i e n c yo fs y s t e m i no r d e rt oa c h i e v et h ee f f e c t w i t h “l i t t l ee f f o r td om u c hw o r k ”，t h es y s t e me n v i r o n m e n t sa v a i l a b l ea r er e q u i r i n gc o n c u r r e n t i n c r e a s i n g l y , o n l yi nt h i sw a yc a nw eu s es y s t e mr e s o u r c e se n v i r o n m e n ta n dc a nw em a k ea s y s t e m h a ss t r o n g e rc o m p e t i t i v e n e s s a sa ne x c e l l e n tf o r m a l i s md e s c r i p t i o na n da n a l y s i st o o l s ， p e t r in e t s 龆nd e s c r i b e sa n da n a l y z e st h i sk i n ds y s t e me a s i l y 乃ea d o p t i o no ff o r m a ls o f t w a r e t e c h n o l o g y , n o to n l yb e n e f i t st ot h ei n t e r c o m m u n i o no fd e v e l o p e r sa n dp r o m o t e st h es o f t w a r e r o b u s t n e s s ，b u ta l s or e d u c et h et o t a ld e v e l o p m e n tt i m ea n dd e c r e a s eg r e a tn u m b e ro fe r r o r si n t h ee a r l y d e s i g np h a s e t h em a i nw o r ko f t h i sp a p e ri sa sf o l l o w s ： ( 1 ) a n a l y s i so ft h ed i n i n gp h i l o s o p h e r sp r o b l e m sb a s e do np e t r in e t s 1 1 1 ed i n i n g p h i l o s o p h e r sp r o b l e mi sac l a s s i c a le x a m p l eo fs y n c h r o n i z a t i o na n dc o n c u r r e n c yo fd e s c r i b i n g t h es h a r e dr e s o u r c e s t h el i v ea n ds t a r v a t i o n f r e ea r et h ep r e r e q u i s i t e st os o l v et h i sp r o b l e m ， a n de f 矗c i e n c yi sb a s i cr e q u i r e m e n t s s i n c et h ec o m p e t i t i o no fr e s o u r c e st h a tp h i l o s o p h e r s c a n n o ts i m u l t a n e o u s l yi ne a t i n gs t a t e c o n s i d e r i n gf a i m e s so f p h i l o s o p h e r s ，w ed e f i n ec o n c e p t o fd e l a y e dp e t r in e t s s o l v e dt h ec o n f l i c tc a u s e db yc o m p e t i t i o no fr e s o u r c e sa n di m p r o v i n g t h ee f f i c i e n c y ( 2 ) m o d e l i n ga n di m p r o v i n gp e t r in e tm o d e lo ft h es e n d e r - r e c e i v e rp r o b l e m s o l v i n g t h eu s e rr e q u i r et oc o m m u n i c a t ea n dr e q u i r e du s e ri sf r e e , w h i l et h ec h a n n e l sa r eb u s y , s e v e r a lu s e r sr e q u e s tt oc o m m u n i c a t e 、析t ho t h e rs e v e r a lu s e r ss i m u l t a n e o u s l y w h i l et h eo t h e r s e v e r a lu s e r sa r ec o m m u n i c a t i n g ，c o n s i d e r i n gt h ec h a n n e lu t i l i z a t i o na n dt h ec o n f l i c to f s h a r e dr e s o u r c e s ，w eu s et h es t a c kt e c h n o l o g yt oa n a l y z ea n dv e r i f y ，b r i n gf o r w a r dam o d e l w h i c hi ss t r o n g e ra n dw i d e ra p p l i c a t i o no fp e t r in e t s k e yw o r d s ：p e l r in e t ；a s y n c h r o n o u sc o n c u r r e n t ； f o r m a lm e t h o d s ； s - i n v a r i a n t ； m o d e l i n g ；s y s t e ma n a l y s i s i i 摘要 a b s t r a c t 引言 1 1 研究背景及意义 1 2 p e t r i 网的发展历史 1 3p e t r i 网的研究现状 1 3 1模型的扩展4 1 3 2p e t r i 网的分析技术7 1 4 本文的主要内容及结构9 2p e t r i 网的基础知识l o 2 1 p e t f i 网及网系统的基本概念1 0 2 2网系统中事件的几个关系1 3 2 3p e t r i 网系统的不变量l4 2 4 网系统分类。1 7 2 5网的结构和行为特征1 7 3基于p e t r i 网下对哲学家就餐问题的分析2 0 3 1基本概念21 3 2 模型的改进与推广2 5 4 基于p e t r i 网下对通信信道复用的建模应用2 8 4 1基本概念2 9 4 2问题描述及建模2 9 4 3 模型的分析3 2 结论。3 5 参考文献。3 6 攻读硕士学位期间发表的论文及科研成果3 9 致谢4 0 r 7 两华人学 1 1研究背景及意义 引 在科学技术高速发展的背景下，计算机 社会进入了科学技术高度发展的2 l 世纪。自 计算机的发展趋势就向着高速化、小型化、智能化和并行处理能力方向发展。分布式客 户服务器逐渐取代了传统的集中式主机模式，如今已发展为基于i n t e r n e t 和w e b 技术 的三层模式，在这个模式下，人们所关注的焦点是服务器网络通信和应用平台的发展趋 势。 。因此，并行计算技术就自然而然的伴随着产生和发展了，并行计算技术指的是同时 使用多种计算资源解决问题的方法及过程。主要分为时间上的并行和空间的并行两种： 时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计 算。并行与并发的关系：并发包含并行，a 、b 并发指的是：a 、b 并行，a 在前b 在后， b 在前a 在后，即a 、b 并发指的是a 、b 无序。 在竞争共享资源的情况下，如何更好地提高资源利用率，将是一个系统目前最迫切 需要解决的难题。并发可以看作是衡量系统资源利用效率的一个参数标准。在系统许可 下，允许尽可能多的并发操作才能更好提高资源的利用率( 这里是在需要的情况下) 。 在p e t r i 网中并发可以理解为非序，即一个变迁发生和另一个变迁的发生之间没有顺序 关系，值得注意的是：客观存在的并发不具有传递性，例如你可以边唱边跳，也可以边 说边跳，却不能边唱边说。因为说和唱共同用同一张嘴，只能交替发生。c a ra d a mp e t r i 给出的并发公理准确地刻画了并发的性质。 对系统进行建模与分析往往离不开形式化的描述方法，形式化方法是系统建模与分 析的重要工具之一。形式其实是对事物内在存在的内容的一种外在方式、形状或结构总 和的表达：形式化是指将事物的外在形式与内在内容相分离，用事物的某种外在特定形 式来表示事物：形式化方法是在对事物形式化描述的基础上，通过形容事物的外在形式 变化规律来研究事物的内在变化规律的全体方法的总称。 哲学家就餐问题是描述在共享资源下异步并发的经典案例。它是操作系统中描述并 发操作，处理资源共享的经典案例之一，由e w d i j k s t r a e i 】提出。问题描述如下：有1 1 位哲学家围坐在一个圆桌前，每两位哲学家之间放有一根筷子。每位哲学家有三种状态： 思考、准备就餐和就餐；但只有同时拥有了芹右两根筷子才能就餐，就餐完毕将两根筷 子放【口1 原处，哲学家回到思考状态。在此问题中既有由于资源的共享引起的冲突，相邻 基fp e t r i 网的几个并发问题的建模与分析 两位哲学家都准备就餐时竞争俩人之间的筷子：又有并发操作，允许两位( 不相邻的) 学家同时就餐。该问题也是评价同步方法的一个测试标准。 由于现实中的应用系统庞大，具有并发性和不确定性，执行过程中的时间和空间复 度远远超过了单个主体所拥有的能力，所以多宅体协作成为不可缺少的技术。在系统 境中难免会有冲突发生，冲突是指资源的一种争夺，在某些模型中，带有冲突并不是 型的罪过，比如p e t r i 网。冲突之处表达了不确定性，给外部控制给予了可能：但是， 基于p e t r i 网的工作流模型中是不允许有冲突的。冲突有时是无法预知的，即不清楚 种冲突何时发生何时结束，可能系统运行某一种执行顺序时就有冲突，但当运行另一 执行顺序时就没有，冲突还可能会转移。由于变迁的使能规则满足局部化公理，即变 的使能规则只涉及变迁的前、后条件( 状态) ，产生混惑的根本原因在于外延( 前、 置) 分割不清。 通讯系统与网络正向着无线网络状态发展，就如身边发生的事情一样，车载卫星定 系统与无线上网等。将来的用户越来越离不开网络，网络已经成为人们不可缺少的事 ，而且伴随着3 g 时代的到来，将来的网络通信必将向无线网络发展。因此对无线网 中的资源利用问题变得相当重要，本文给出了在p e t r i 网下对通信系统中的信道复用 术的建模与分析，考虑到信道的利用率及对共享资源带来的冲突，采用栈技术对这一 问题进行了分析与验证，提出了一个应用性更强，应用范围更广的p e t r i 网模型。 1 2p e t r i 网的发展历史 c a r la d a mp e t r i ( 德国) 先牛在其1 9 6 2 年的博士论文“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 网的概念。该论文提出了一种用于描述物理进程 和物理系统的组合的网状模型，即并发这一概念。作为一种系统模型，p e t r i 网通过直观 的图形表示或采用许多数学方法对其性质分析，来刻画系统的结构和描述系统的动态行 为( 如系统的状态变化等) 。同样地，对于复杂的系统，p e t r i 网对其进行分层描述，逐 步求精，便于同面向对象的思想方法相沟通【2 】。 2 0 世纪6 0 年代，p e t r i 网研究对象为孤立的网系统，且研究的目标局限在寻求分析 技术和应用方法上。通常把这些内容称为特殊网论( s p e c i a ln e t t h e o r y ) ，就足孤立的网 系统个体。这里的特殊是与一般相比较而言的。 2 0 世纪7 0 年代，p e t r i 网得到了进一步发展，c a r la d a mp e t r i 等一批科学家提出了 新的理论体系，其内容以研究全体网系统为辛要对象，研究其分类及各类网之间的关系， 包括并发论( c o n c u r r e n c y ) 、同步论( s y n c h r o n y ) 、网逻辑( e n l o g y ) 和网拓扑( n e tt o p o l o g y ) 。 1 9 6 2 年以来的研究成果在1 9 7 9 年的旨届夏季培训班得到了总结，并由s p r i n g v e r l a g 出 两华人学硕- f ：学位论文 版社以l n c s 8 4 ( l e c t u r en o t e si nc o m p u t e rs c i e n c e ) 的形式出版发行，对以后p e t r i 网理 论研究产生了极其深远的影响。 2 0 世纪8 0 年代是p e t r i 网的综合发展阶段，其主要内容为理论与应用的结合及计算 机辅助工具的开发。随后，在1 9 8 6 年的第二届夏季培训班，对这些研究成果又做了一 次阶段性总结，讲稿集结为l n c s 2 5 4 2 5 5 两卷。同时，以工程背景( 尤其是自动制造 系统) 的研究人员开始在工程领域对p e t r i 网进行研究，从研究中得出的结论是：p e t r i 网能很好的对事件驱动系统进行建模与分析。称一个系统为离散事件系统( d e s ) ，是 因为该系统不仅可能包含异步的、顺序的和并行的操作，并且可能涉及系统中的互斥、 非确定性及冲突。 2 0 世纪9 0 年代，d a v i s 与a l i a 于1 9 9 2 年出版了将p e t r i 网作为离散事件系统建模 工具的专著。第二年，z h o u 和d i c e s a r e 在其专著中详细的介绍了制造系统的e e s 建模 与模型合成方法。随后在1 9 9 5 年，d e s r o c h e r s 与a 1 j a a r 又给出了关于p e t r i 网在自动制 造系统中的建模与应用，并分析了p e t r i 网在制造系统的性能评价、分析及控制中的应 用。z h o u 与v e n k a t e s h 于1 9 9 8 年出版了在柔性制造系统中p e t r i 网的应用。 4 0 多年的发展，使p e t r i 网形成- - 1 3 系统的独立的学科分支，而且p e t r i 网的研究方 法与理论成果为p e t r i 网在自动化科学技术( 如混杂系统、离散事件动态系统等) 、机 械设计与制造( 如柔性制造系统) 、计算机科学技术( 如人工智能、形式语义、软件工 程、网络协议、操作系统等) 以及其它科学技术领域的研究提供了很好的基础。w b r a u e r 教授在庆祝c a r la d a mp e t r i 教授6 0 岁生日的演讲中指出：p e t r i 网理论的发展必将为信 息论奠定坚实的理论基础。 概括起来，可以从以下几个方面展开： ( 1 ) p e t r i 网的动态性质( d y n a m i cp r o p e r t y ) 用p e t r i 网对实际系统进行建模与分析时，主要目的之一就是借助系统模璎来分析 实际系统的性质和功能。p e t r i 网的系统模型与其它的模型相比，不仪有直观的图形表示 而且可以给出形式化的表述。这样若一个p e t r i 网模型能够准确地描述个系统的结构 和运行，那么这个系统所具有的一些性质必会在其p e t r i 网模型上得到体现。动态性质 有：可达性( r e a c h a b i l i t y ) 、可逆性( r e v e r s i b i l i t y ) 、可覆盖性( c o v e r a b i l i t y ) 、有界 性( b o u n d e d n e s s ) 、安全性( s e c u r i t y ) 、活性( 1 i v e n e s s ) 、公平性( f a i r n e s s ) 、持续 性( p e r s i s t e n c y ) 等。 ( 2 ) p e t r i 网的分析方法( a n a l y s a b l e m e t h o d ) 对于某些简单的网系统，通过观察该系统的运行( 或者仿真) 结果叮以得到它的一 些基本性质。但对于复杂的系统，用这种方法来确定其性质难免会漏掉一部分( 或者说 插入计数器、插入基本元素的补元素等) 、删除( d e l e t i o n ) 、替换( s u b s t i t u t i o n ，分为 两种：库所的替换与变迁的替换) 、化简( s i m p l i f i c a t i o n ) 、合成( c o m p o s i t i o n ，包括： 共享合成( s h a r i n gc o m p o s i t i o n ) 、同步合成( s y n c h r o n o u sc o m p o s i t i o n ) 等) 、分解 ( d e c o m p o s i t i o n ，包括：公平分解与非公平分解等) 等。 1 3p e t r i 网的研究现状 1 3 1 模型的扩展 自c a r la d a mp e t r i 先生开创性的工作之后，网论得到了快速的发展，至今己形成了 在许多研究领域具备相当规模的研究，如：软件工程、数据库、人工智能、网络协议、 操作系统等。理论上，对p e t r i 网模型和分析技术的研究已取得相当多的有价值的成果， 如作为一种全新的自动机p e t r i 网被开发出来：对此方面的研究，网人充满了前所未有 的兴趣和希望，认为p e t r i 网的应用要比下推自动机( p d a ) 有用的多，比下推自动机 的功能更强大，并且不存在图灵机所具有的那些可判定问题。于是在对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 ) 带抑制弧的p e t r i 网 带抑制弧的p e t r i 网是在原型p e t r i 网的基础上增加一种连接库所与变迁的新型的弧 线而成的，这种弧线只对具备发牛条件的变迁起控制作用( 即是否允许其发生) ，且变 迁的发牛不会引起该弧线前置库所中的托肯，使得引进这种改进的模型具备零检测的能 力，这也是一种模型与图灵机具备同等的模拟能力的一个标志。 ( 2 ) 混合p e t r i 网( h y b r i dp e t r in c t ) 由于复杂性是混合系统的特性，因此每一个控制模态下的每一个状态特征量不仪是 被控对象的符号量或离散事件特征量，而且是被控对象向数值控制器的数值量反馈或连 续量，这些量组成模态下的混合状态。分布系统( 局部的或全局的) 控制模态的转移由 实时决策子系统完全确定，在每一个控制模态下，传统的数值控制回路由实现特定活动 功能的实时数值控制子系统与被控对象、执行器和传感器组成，这样由实时数值子系统 与实时决策子系统组成的控制系统称为混合控制系统【3 j 。 基于连续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 c t r i 网 的离散变迁发牛规则。 ( 3 ) 时序p e t r i 网( t e m p o r a lp 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 网加入一组时 5 为了用p e t r i 网方法描述和分析具有连续变量的系统，d a v i d 等人提出了连续p e t r i 网的概念【7 8 】。连续网系统中的标识在各库所的取值是非负实数值，而原型p e t r i 网系统 在各库所的取值只能是非负整数值。因此，变迁发牛的条件和变迁发生的结果也相应的 改变，最明显的变化在于变迁可以以任意发牛量发乍，从而一个变迁的发牛可以得到多 种不同的结果。 ( 7 ) p e t r i 网语言( p e t r in e tl a n g u a g e ) p e t r i 网语言是研究p e t r i 网的一个重要研究方向，p e t e r s o n 9 1 和h a c k 【1 0 】最早的研究是： 将网中所有可能发牛变迁序列所组成的集合作为该p e t r i 网产牛的语言，j a n i c k i 在文献 1 1 ，1 2 】中给出了p e t r i 语言的封闭性，并指出它的封闭性与经典形式语言的关系。另外， r o z e n b e r g 等人【l3 】于1 9 8 3 年讨论了子集语言的类似问题，不同的是他们是在事件多重集 上进行的。t o s z e w a vk t l 4 】给出了p e t r i 网语言的详细定义，吴哲辉1 1 5 于1 9 8 9 年研究了 p e t r i 网语言与形式语言之间的关系。1 9 9 4 年，w o l f s t h a l 和y o e l i 【1 6 】分别从多个方面研 究与分析了p e t r i 网语言的性质。明显地是，同经典的形式语言相比，p e t r i 网语言理论 6 两华大学硕上学位论文 研究只是处于起步阶段，还很不完善，因为p e t r i 网语言还没有形成与其语言相对应的 文法关系，仅简单的将p e t r i 网语言看成一种生成器，并没有考虑其作为语言识别器的 可能。这些问题说明了在p e t r i 网语言研究领域的还不成熟，同时也反映出p e t r i 网语言 是一个值得网人去研究的方向1 1 7 j 。 图灵机模型是机器的至高点，人们总想建立起功能强大的完全超越图灵机的模型， 从m o o r 机到多头、多带、限界、带栈的机器模型，无例外的都等价于图灵机。历史又 在重复：原型p e t r i 网到各式各样的p e t r i 网，形态各异模型只是针对于应用领域方便而 已，而不是真正意义下的对p e t r i 网的表达能力的完备化。p e t r i 网并不是在众多的并发 模型中增加一个成员，它既直观又有深刻的数学内涵和基础，由此而导出以下分析技术。 1 3 2 p e t ri 网的分析技术 要想对实际的网系统中进行很好的分析，只有对p e t r i 网模型的动态性质进行很好 的分析，才能得到人们想要的系统分析结果。现介绍部分p e t r i 网的分析技术： ( 1 ) 基于代数分析和状态方程技术【1 7 1 8 , 1 9 】 代数分析技术方法最先由p e t e r s o n 【1 8 1 和m u r a 0 1 9 1 提出，用关联矩阵的形式去刻画 一个网系统的行为结构是其辛要内容，并在这一过程中给出了一个状态可达的线性系统 关系。网系统的静态结构刻画方法辛要是用基于线性代数的分析技术，用不变量 ( i n v a r i a n t s ) 技术研究网的一些基本性质，尤其是网的动态行为方面的结构性质。但这 并不能很好的刻画网系统的动态特征。如：s 不变量、t 不变量等。 ( 2 ) 基于可覆盖树的分析技术【2 0 , 2 1 】 与状态机的分析技术类似，图分析技术展现了一个网系统的运行机制，与状态机不 同的是它基于一个有限的有向树形式。可覆盖树( 图) 的分析技术能准确地反映一个网 系统的一些基本特征和动态行为性质。对于有界p e t r i 网，由于状态的有限性它能准确 刻画网系统的行为性质，并且在这过程中形成一个与该网系统相对应有限状态机；但 是对于无界p e t r i 网，它只能反映一部分系统的行为且对应的状态机有可能是无限。可 达树是p e t r i 网分析的一个较好工具，但是对于状态较多的网系统不能很好的解决空间 状态过多的情况，即状态空间爆炸。 ( 3 ) 基于化简分解的归纳分析技术田j p e t r i 网化简作为p e t r i 网分析的一种霞要的辅助手段。为了克服状态空间爆炸这一 闲难，可以采用可达树化简、极小可达树等办法来解决，化简分解归纳分析技术的提出 和应用使得以前对一些复杂网系统不可能完成的分析工作成为町能，并且分析的工作量 也有大幅度地减少。m u r a t a d 在文献 2 3 ，2 4 】中提出了针对t 一图的若干化简规则，并讨论 了这些规则对一些性质的保持关系，如安全性、活性等；随后蒋昌俊推广了m u r a t a 在 最早由h a c k 提出，首先用于研究自由选择网，循着这条路径，网人研究了一个更大的 子类，非对称选择网。上世纪8 0 年代末到9 0 年代，有关自由选择网，活性、有界性的 判定性结论硕果累累，它们都是基于s i p h o n 的。与此同时，一篇有关s i p h o n 求解是n p 的论文使得这些理论结果在应用层面上大打折扣。在此之前，人们普遍认为，求解s i p h o n 的方法是多项式的，但是求解s i p h o n 是n p 的，它如同在烈焰上浇了一盆冷水，此后， 结构技术几乎是步履蹒跚、举步维艰。 ( 6 ) 基于进程的分析方法 p e t r i 网是一个具有并发特征的计算模氆，有可能出现系统的变迁发牛序列不同佃结 果相同的情况，一般的分析方法很难通过初始条件和系统的运行结果来刻画系统的实际 运行过程，也不能反映事件间的顺序或者并发关系。因此引入进程这一分析工具来记录 系统运行过程中发生的变化和引起的状态改变，所有进程的集合可以作为系统动态行为 的完整描述。 9 基于p e t r i 网的几个并发问题的建模与分析 p e t ri 网的基础知识 p e t r i 网有许多定义和性质，本章我们仅简单的介绍后面各章节需要的p e t r i 网的一 概念和术语。其它概念详见文献 2 ，9 ，1 7 ，2 2 ，3 2 ，3 3 ，3 4 。 1p e t r i 网及网系统的基本概念 定义2 1 1n = ( s ，t ；f ) 是一个p e t r i 网( 简称网) 的充要条件是，满足如下规则： ( 1 ) s u t 矽； s = 如l ，s 2 ，s r n ) 是一个有限库所集( p l a c es e t ) ； ( 2 ) s nt = 西； t = t 1t 2 ，乙) 是一个有限变迁集( t r a n s i t i o ns e t ) ； ( 3 ) f ( s r ) u ( 丁s ) ： f 是上的流关系( f l o wr e l a t i o n ) ，其元素叫弧。 ( 4 ) d o m ( f ) u c o d ( f ) = s u t ： 其中：d o m ( f ) = zf3 y ：( x ，y ) f ) ，c o d ( f ) = z3 y ：( j ，x ) f ) ； ( 1 ) 式说明s ( p l a c e ) 和t ( t r a n s i t i o n ) 的并集为非空集合； ( 2 ) 说明s 和r 的 交集为空集；( 3 ) 式指出，有向边只存在圆和方块之间，f 是网的流关系( f l o w r e l a t i o n ) ；( 4 ) 式说明d o m ( f ) 为f 的定义域，c o d ( f ) 为f 值域。 用图形表示p e t r i 网时，库所用小圆圈来表示，而变迁则用小方块来表示，小圆圈 和小方块之间是通过有向弧连接起来的，任意两个小圆圈或小矩形之间都不能育有向弧 连接。 定义2 1 2 令是网，x = su t ，对于v x x ，称： 。x = yl ( y ，工) f 为x 的前置集( p r e s e 0 ； 石。= yi ( x ，y ) f ) 为x 的后置集( p o s t - s e t ) 。 图2 1 ( 五y ) f n ( s t ) 图形表示 f i g 2 1 a ne x a m p l ef o r e x p l a i n i n g ( x ，y ) f n ( s x t ) 1 0 两华大学硕t 学何论文 图2 2 ( x , y ) f n ( t x s ) 图形表示 f i g 2 2 a ne x a m p l ef o re x p l a i n i n g ( x ，y ) ，n ( txs ) 图2 3 f i g 2 3 网m l n e t 如图2 3 是一个网 = ( s ，丁；f ) 的图，其中s = s 15 2 ，岛，s 4 ，t = t it 2 ，岛，) ， f = ( s l ，f 2 ) ，( s 2 ，t 1 ) ，( s 2t 4 ) ，( s 3 毛) ，( s 3 ，t 4 ) ，( s 4 ，t 3 ) ，( t l ，s 1 ) ，( f 2 ，s 2 ) ，( t 2s 3 ) ，( 乙，s 1 ) ， ( f 4 ，s 4 ) ； 对于库所s 。，它的前集和后集分别为。s = t l , 岛) ，s 。= t 2 ) ；而变迁f 2 的前集和后集 分别为t 2 = s 1 ) ，乞= s 2 , s 3 ) ，易得，在一个网中n = ( s ，丁；，) ，对任意s s ，t 。s 当 且仅当s t 。；同样地可得到对任意t t ，t s 。当且仪当s t 。 定义2 1 3 设n = ( s ，r ；，) 是一个网。 ( 1 ) 若v x sut ，x n x 。= 矽，则称为一个纯网( p u r en e t ) ； ( 2 ) 若比，y sut ，( 。x = y ) ( x 。= y ) ox = y ，则称为一个简单网( s i m p l e n e t ) 。 定义2 1 4 称六元组= ( s ，t ；f ，k ，形，m ) 为一个库所变迁系统( p l a c e t r a n s i t i o n s y s t e m ) ，满足以下条件： ( 1 ) ( s ，丁；f ) 是一个网， 分析 k ( s ) t n t 。 从该定义可以看出，由于容量函数和权函数的作用，p 丁系统的运行与原型p e t r i 网有区别。在叫丁系统中一个变迁f 在标识m 能否发生，不仪取决于它的前集库所( 集) ， 而且还同它后集的各库所有关，因为每个库所都有容量限制，要查看是否超过了它的容 量。实际例子如图2 4 所示。 s 3 t 4 图2 4 库所变迁系统样式 f i g 2 4s y s t e mm a n n e ro fp l a c e t r a n s i t i o n k ( s ) = 5 定义2 1 5 标识( m a r k i n g ) 是函数m ：s - - - z ，z = o ，1 ，2 ，) ；称= ( ，m 。) 为一 个p e t r i 网系统，称m o 为网系统的初始标识。 两华大学硕十学位论文 定义2 1 6 令是一个p e t r i 网，【m o 为( ，肘o ) 的可达标识集，并满足以下两个 条件的最小集： ( 1 ) m o 【m o 。t ( 2 ) v m “m o ，如果3 t t ，s z a l t m7 ，则m m o 。 定义2 1 7 设= ( s ，t ；f ，m ) 为一个p e t r i 网。称m 为从m 直接可达的，如果存 在t t 使得m t m 。如果存在标识序列m 。，m 2 ，m i 和变迁序列f l ，f 2 ，使得 m 【 m 1 t 2 以一，【气 心则称坂为从m 可达的。p , m 可达的一切标识的集合记 为r ( m ) 。约定m r ( m ) 。 2 2 网系统中事件的几个关系 设c 为e n 系统n = ( 召，e ；f ，气) 的情态集，c c 为任一情态，q ，q e 为的仟意 两个事件。 定义2 2 1 顺序关系( s e q u e n t i a lr e l a t i o n ) 如果“q ，但 c 乞 而e 2 ，其中c ，是c 的后继：c 7e 2 ，就说q 和乞在c 有 顺序关系。 定义2 2 2 冲突( i nc o n f l i c t ) 若c 【q a c e 2 ，但- 1 c q ，e 2 ，则q 和乞在c 互相冲突。通俗的说，冲突指的是 这两者都有发生权，却只能有一个能发生的关系，且谁有优先权不确定，所以冲突也称 为不确定和选择，也可以说它是决策之处。