（计算机软件与理论专业论文）基于增广petri网的协作系统及混惑消除.pdf

两华人学硕f ：学位论文 基于增广p e t r i 网的协作系统及混惑消除 计算机软件与理论专业 研究生姚建指导教师宋文 摘要 p e t r i 网是一种形式化、图形化的系统建模、描述和分析工具。对于具有 异步并发、分布、不确定性和随机性的系统，都可以利用这种工具构建模型， 然后对其进行分析，即可得到系统静态结构和动态行为方面的信息。p e t r i 网 既有直观的图形表示，又有深刻的数学内涵和基础。 p e t r i 网的并发不确定性在描述具体问题时常会有一些不便，究其原因在 于它不能准确地检测出库所中特定的标识。为此，网人在原型p e t f i 网中引入 禁止弧( i n h i b i t o ra r c ) 和容许弧( p e r m i s s i v ea r c ) ，得到一类增广p e t r i 网一禁止弧 容许弧网。 现实中的系统往往具有并发和不确定性，任务的复杂程度在时间或空间上 超越了单个主体的能力，仅靠单个主体的实现是不可能的，所以多主体协作成 为必不可少的行为。传统的协作系统模型往往在任务分配时十分复杂，没有考 虑任务的分级与处理的公平性，一旦出现局部故障，缺少相应的恢复机制。 本文不考虑中心控制的情况，使用带禁止容许弧的增广p e t r i 网构建了一 类具有中断处理功能、可实现任务转移和故障恢复的协同控制系统，并利用结 构分析、分块建模等技术，对系统的主要行为特征进行了较深入细致的研究。 随后对模型进行了验证，表明该模型具有主体协作能力，能够兼顾系统的任务 分级和处理的高效、公平性，在局部处理异常时能实现任务的转移和故障恢复。 在p e t r i 网中，并发和冲突是普遍存在的。并发和冲突混合在一起的现象 称作混惑。系统中出现冲突之处j 下是系统环境对系统进行控制的地方，但若应 两华人学硕1 ：学位论文 用系统中出现混惑，则系统环境或无法确定是否有冲突出现。产生混惑的原因 是系统中某些变迁的外延不完整，混惑会给系统分析和系统控制带来麻烦，有 混惑的系统模型不是一个好的模型，在实际应用中必须保证混惑现象不会发 生。本文对三种基本结构混惑做了进一步研究，并给出了增广p e t r i 网的三种 基本混惑的消除方法。对结论的f 确性做了证明。混惑的消除使得p e t r i 网的 描述能力更强、使用范围更宽。所得结论可广泛用于工作流模型的验证。 关键字：增广p e t r i 网，协作，模拟，混惑，消除 i i c o l l a b o r a t i o ns y s t e ma n de l i m i n a t ec o n f u s i o n b a s e do nt h ee x t e n d e dp e t r in e t c o m p u t e rs o f t w a r et h e o r e t i e s m a s t e rd e g r e ec a n d i d a t ey a o j i a n s u p e r v i s o rs o n g w e n a b s t r a c t a st ok n o w nt h a tp e t r in e t si sat o o lo fs y s t e mf o rm o d e l i n g ，d e s c r i b i n ga n d a n a l y z i n g i t i s a l w a y su s e d t oc o n s t r u c tt h es y s t e mc o n c e r n i n gc o n c u r r e n t ， a s y n c h r o n o u s ，p a r a l l e l ，u n c e r t a i n a n dr a n d o m f u r t h e r m o r e ，t h es t r u c t u r ea n d d y n a m i cb e h a v i o r so ft h ep r o p e r t i e sc a nb eo b t a i n e da n da n a l y z e d i th a sn o to n l y b e h a l fo nt h eg r a p h i c a l l yd e s c r i p t i o n ，b u ta l s oh a st h e s t r i c tm a t h e m a t i c a l f o u n d a t i o n 、 i ti sn o tc o n v e n i e n tt od e s c r i b et h er e a l - l i f eu s i n gp e t r in e t sb e c a u s es o m e t i m e s i tc a nn o tc o r r e c t l yc h e c kt h et o k e n si np l a c e a ne x t e n d e dp e t r in e t sw i t hi n h i b i t o r a r ca n dp e r m i s s i v ea r cb a s e do nt h eg e n e r a lp e t r in e t si sb u i l tt oo v e r c o m et h e d e f i c i e n c y t h es y s t e mi np r a c t i c ei su s u a l l yc o n c u r r e n ta n du n c e r t a i n s i n g l es y s t e mc a n n o tt a c k l e t h ec o m p l e xp r o b l e ma n dw a s t et i m e t h ec o l l a b o r a t i o ns y s t e m i s n e c e s s a r y i ti sd i f f i c u l tt oa s s i g nt h et a s k sa n dt h ef a i r n e s si sn e g l e c t e di nt r a d i t i o n a l c o l l a b o r a t i o ns y s t e m t h e r ei sn ow a yt or e c o v e rt h ef a u l t i nt h i sd i s s e r t a t i o n ，an e wc o l l a b o r a t i o ns y s t e mw i t h o u tc e n t e rc o n t r o l i s p r o p o s e db ye x t e n d e dp e t r in e t s i ti sc o n c e r n i n g t h ei n t e r r u p tt e c h n o l o g ya n df a u l t r e c o v e r y t a k i n ga d v a n t a g eo fs t r u c t u r ea n a l y z i n ga n dm o d e l i n gt e c h n o l o g y , i t s p r o p e r t i e sa f e d i s c u s s e di nt h ef o l l o w i n g w ea l s os h o wt h a tt h em o d e lc a nd e a l i i i 两华人学硕i ：学位论文 w i t hm u l t i t a s ka n df a i r n e s s ，h a v em o r ee f f e c t i v et h a no t h e r s s o m er e s u l t sa r e p r o v e ni nt h i sd i s s e r t a t i o n w i t h i np e t r it h e o r yc o n c u r r e n c ya n dc o n f l i c th a v eac o m m o nc o n d i t i o n c o n f u s i o nc a na r i s ew h e nt h e r ei sam i x t u r eo fc o n c u r r e n c ya n dc o n f l i c t t h e c o n f l i c tc a nb ec a p t u r e da n dc o n t r o l l e db yt h ee x t e r n a le n v i r o n m e n t h o w e v e ht h e c o n f l i c to fs y s t e m sc a n n o tb ee x p l o r e dw i t h i nc o n f u s i o n t h ec a u s e so f c o n f u s i o ni s t h a ti nt e r m so fn o n d e t e r m i n i s mw h e r e a si nt h e f i n e rt r u l yc o n c u r r e n t f o rs u c h s y s t e m s ，t e s t i n ga l o n e i si n a d e q u a t ea si tc a no n l yd e t e c te r r o r sn o tv e r i f yt h e i r a b s e n c e r a t h e r , w em u s tp r o v et h a tt h es y s t e mc o n t a i n i n gn oc o n f u s i o n i ti sv e r y n e c e s s a r yt oe l i m i n a t ec o n f u s i o no f t h eg e n e r a lp e t r in e tm o d e l f u r t h e r m o r e ，t h r e e b a s i cs t r u c t u r eo ft h ec o n f u s i o ni ne x t e n d e dp e t r in e t sa r ed i s c u s s e da n ds o m e p r o p e r t i e s a l e p r e s e n t e d t h e c o r r e c t n e s so ft h o s er e s u l t sa l ep r o v e n b y e l i m i n a t i n gc o n f u s i o no ft h eg e n e r a lp e t r in e t ，t h e m o d e lc a nb eu s e di nm o r e f i e l d a n dt h ew f - n e tm o d e lc a nb ev e r i f i e db yt h ec o n c l u s i o n k e y w o r d s ：e x t e n d e dp e t r in e t s ，c o l l a b o r a t i o n ，s i m u l a t i o n ，c o n f u s i o n ，e l i m i n a t e i v 两。芦人学顾i ：学位论文 声明 文成果归西牛人学昕仃特此童嚣囊曩：潞乞胃，夕昌 作厅签名：。r k 、，m 年月同 导师签铭：名lj 爿年l 月1只 两芦人学坝i ：学位论文 授权书 西华大学 学位论文版权使用授权书 小。位沦文作抒完伞。j ，解学校有关保留、使用学位论文的规 定，同意学校保留并向凼家有关部fj 或机构送交论文的复印件和i 包 子版，允许论文被查阅和借阅，西华大学可以将本论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 印手段保存和汇编本学位论文。 本学位论文属于 1 、保密 2 、不保 年解密后适用本授权书； 本授权书。 ( 请在以上口内划4 ) 学位论文作者签名：妒良 日期： 。j 、1 1 9 指导教师签名：铲沪 瞧o 1 两。芦人学顾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 j t i o nm i t a u t o m a t e n ”( 用自动机通i t t ) i l l 中提出了p e t r i 网的概念。p e t r i 阐述了。f r 计算 机中的两个异步分支间的通讯理论基础，并特别注意到事件之间因果关系的 描述。他的论文是p e t r i 网理论研究发展的奠基石。p e t r i 的论述引起了a d r ( 应 用数据研究) 和麻省理工学院( m 1 t ) 的m a c 理论研究小组的注意，随后做了 相关的研究，这些研究主要展示了如何用p e t r i 网来模拟和分析具有并行分支 的系统。p e t r i 的开创性工作同时还引起了欧美学术界和工业界的注意1 2 , 3 1 ，后 来逐步为科技晃所接受，现在已是人们常用的一种数学工具1 4 1 。1 9 7 0 年至1 9 7 5 年，m 1 1 r 的计算结构研究小组积极参与p e t r i 网相关的研究，并在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 网著作问世 i s 】。1 9 8 5 年出版了第二本p e t r i 网专著1 6 1 。 几十年来，p e t r i 网理论得到了长足的进展。p e t r i 网研究的系统模型行为 特性包括：状态的可达性、变迁的活性、库所的有界性、初始状态的再生、事 件之间的同步性和公平性等。p e t r i 网模型的分析方法有很多，如： ( 1 ) 基于图论的方法：可达图、基于线性代数下的方法、关联矩阵和状态 方程、s ( t ) 不变量； ( 2 ) 基于代数下的方法：序关系；基于机器模型下的方法：p e t r i 网语言； ( 3 ) 基于逻辑与代数下的p e t r i 代数； ( 4 ) 分析化简规则； ( 5 ) 结构理论等。 两。每人学颂i j 学位论文 p e t r i 网的抽象描述能力也在不断向纵向和横向扩展。 它的横向扩展表现为： 原先是没有参数的普通的网，现在有了时i 日jp e t r i 网1 7 l 和随机p e t r i 网【8 l ；原 先是一般有向弧，如今有了约束弧和可变弧：原先标i 7 ( t o k e n ) 的个数都是自然 数，现在有了概率标记个数；原先只有普通的原子变迁，现在有了谓词变迁和 子网变迁。 它的纵向扩展表现为： 原先只有基本的条件事件( c e ) 网1 9 1 ，后来有了库所变迁( p t ) 网1 1 0 1 ，现 在更有了高级网( 包括谓词变迁网1 1 1 l 和有色网1 1 2 ，1 引，对象p e t r i 网15 、时序 p e t r i 网、被控p e t r i 网和混合p e t r i 网，p e t r i 网语- 言( t h el a n g u eo fp c t r in e t ) 1 1 6 1 ) 1 2p e t r i 网的扩展 自p e t r i 丌创性的工作之后，网论得到了长足的进展，至今已形成了具备 相当规模的研究领域。具有代表性的p e t r i 网模型介绍如下： 1 2 1 时间时延p e t r i 网( t i m e t i r e e dp e t r in e t ) p e t r i 最初提出的p e t r i 网并没有把时间因素放到p e t r i 网中。时间网( t i m e d p e t r in e t s ) 是后来人们根据实际需要把时白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 网模型，它是由r a m c h a n d a n i l l 7 1 提出的，主要用于系统的评估方面。这类 p e t r i 网模型规定每个变迁都具有有限的引发时延，其引发规则被修改为： ( 1 ) 每一个引发变迁都有一个时延过程； 2 两f # 人学顾i ：学位论文 ( 2 ) 一个变迁一旦使能就必须立即引发。 另一类是时间p e t r i 网模型，它由m e r l i n1 1 8 j 提出的。这类p e t r i 网模型规 定每个变迁都对应着一个时问区间【a ，b 】，任何一个变迁，当它使能之后，它在 时间区间【a ，b 1 内便具有连续使能权。使用这种网，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 网，反之则不行。 1 2 2 随机p e t r i 网( 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 在文献 1 9 1 首先提出，随机p e t f i 网考察的j _ l ! = “界的网，其随机 变量服从负指数分布，从而证明了网的状念可达图同构于个马尔科夫链。 m a r s a n 等人例】推广了m o l i o y 的工作，提出一种广义随np e t d 网( 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 等人1 2 l j 从另一角度推广了m o l l o y 的工作，提出一种增广随机p e t r i 网( e x t e n s i v e s t o c h a s t i cp e t r in e t ，记为e s p n ) 模型，该模型包含了抑制弧的情况。然而，这 些工作均未突破负指数分布的限制。文献1 2 2 1 等分别从不同角度试图取消负指 数分布的限制，但仍有待进一步的努力。无论时间( 延) p e t r i 网还是随机p e t r i 网，目前的分析手段基本上是在可达图上操作的，由此产生的状态复杂性是难 以克服的。为此，寻求新的分析途径，拓宽应用领域是这一方向的进一步研究 目标。 1 2 3 带抑制弧p e t r i 网模型( i n h i b i t o ra r c sp e t f in e tm o d e l ) 对p e t r i 网模型的重要扩充就是附加一些新型的弧线。早期模型的引发规 则是当输入库所被标识时，相应的变迁就可以引发，从而改变模型的状态。更 进一步，一个变迁的发生除了需满足它的引发规则，还需要保证其通过抑制弧 相连接的前置库所不被标识。抑制弧的引进使p e t r i 网具备了零检验能力【2 3 1 。 1 2 4 高级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 网面临的另一个问题是，为了某一个特别的操作建立模型从而必须 建立复杂的编码。一些学者认为，如果以某种方式来区别标h 己( t o k e n ) ，可使复 3 两o # 人学硕i j 学位论文 杂编码容易实现。成熟的高级网系统包括谓词变迁系统( 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 l t o k e n s ) 1 2 4 ，矧。对个性托肯的描述方式，前者为每个个体命名，后者为不同个性 的托肯染上不同的颜色。托肯的个性其实代表着除名字以外或颜色以外更复杂 的内容。由于高级网系统是由p t - 系统折叠而来，因而较p t - 系统少了许多结 构信息，这是为减少节点付出的代价。 1 2 5 对象p e t r i 网( o b j e c tp e t r in e t ) 对象p e t r i 网是由内部结构和外部结构，以及对象与对象之间的消息传递 形成的实际系统模型的控制结构组成的陋l 。对象内帮竺含了该对象自身的幅 性以及处理这些数据的方法。在对象p e t r i 网模型中，i t 象的属性( 即数据结 构或数据类型) 是由库所表示的。对象的外部结构足i f j 基接口，库所足对象1 1 唯一与外界( 其他对象实体) 进行消息传输的接口，其中包括消息接收接口和 消息发送接口。对象的消息接收接口和消息发送接口是成对出现的，分别与对 象内的某个方法的输入弧和输出弧相连。消息隐藏在消息传递接口库所中的 t o k e n 中，如果不同的对象同时向一个对象发送同一个消息，则在此对象的陔 消息接收接口中形成一个消息队列。同理，在该对象的消息发送接口中也有可 能会产生一个消息队列。对象p e t r i 网系统通过对象间的控制结构协调各对象 间的消息传递，对象控制结构有一类具有特殊含义的变迁和库所实现。 1 2 6 时序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 ) 、o ( e v e n t u a l l y ) 和u n t i l 等，通过时序逻辑公式控制 或限定p e t r i 网的变迁引发序列，描述系统事件之间的时序关系，并且反映出 系统的基本性质1 2 - 捌。时序p e t r i 网特别适合用于并发系统的建摸、分析和验 证。 1 2 7 被控p e t f 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 数决定变迁的发生或限制变迁的发生次数，控制的状态为输入库所 4 两f 每人学硕i j 学位论文 中的t o k e n 数，由反馈策略决定i 矧。反馈控制是基于外部输入库所的离散事件 动态系统协调反馈控制综合，根据需求规范和原系统的p e t r i 网模型，综合出 附加的控制器p e t r i 网模型，同原p e t r i 网合成便形成了满足需求的受控p e t r i 网模型。 1 2 8 混合p e t r i 网( h y b r i dp e t r in e t ) 混合控制系统是由实时决策子系统与实时数值( 开环或闭环) 子系统组成 的复杂的控制系统1 3 1 j 。实时决策子系统确定分布系统( 全局的或局部的) 控 制模念的转移；每一个控制模念下，实现特定活动功能的实时数值控制子系统 与被控对象、传感器和执行器组成传统的数值控掣! i j 路。但由于混合系统的复 杂性，使得每一个控制模念下的状态特征量不仅f ，之乞破控对象向数值控：l 器的 连续量或数值量反馈，还有来自被控对象的符号茧二f 砭离故事件特征量，这 鼍量 组成模念下的混合状态。 混合p e t r i 网基于离散p e t r i 网模型( 即传统p e t r i 网模型) 和连续p c t r i 网 模型。在一个混合p e t r i 网模型中，其库所集和变迁集分为离散与连续两部分， 这就构成一个混合p 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 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 2 9p e t r i 网语言( t h el a n g u eo fp c 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 网的一个手段，目前已形成一个重要的研究方向。 h a c k 3 2 l 和p e t e r s o n l 3 3 j 最早从事这方面的研究。将一个p e t r i 网所有可能引发序 列的集合视为由该网产生的语g ：l ，文献 3 4 ，3 5 1 研究了语言的封闭性，以及与经 5 两 ；人学颂i ：学位论文 典形式语言的关系。h a c k 在文献f 2 3 】中还讨论了网模型的计算能力，指出带抑 制弧的增广p e t r i 网与图灵机在计算能力上是等价的，从而充分显示出p e t r i 网 模型的表达能力。另外，r o z e n b e r g 等人p 6 j 在事件多重集上讨论了子集语言的 类似问题，文献【3 7 】给出了p e t r i 网语言的一个很好综述，文献 3 8 1 给出了p e t r i 网语言与形式语言关系的一个清楚刻画。文献【3 9 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 t r i 网语苦研 究的不成熟，同时也暗示了一个极具吸引力门：洱究方向i 捌。 1 3p e t r i 网的动态性质及分析方法 p e t r i 网理论研究的另一主流方向是建立在通用网论基础之上的并发行为 的特性研究。通用网论是从更为基础、更为抽象的网模型( 如c e 系统，p 厂r 系统) 上探讨系统的特性。 p e t r i 网不仅具有可视化的描述特点，同时还提供完善的分析工具i m 书l 。 高级p e t r i 网能够进一步提供简洁的系统描述，能够对数据控制流，触发条件 动作，多样化的系统资源进行建模，其模拟能力已经广泛用于形如工作流的 模拟1 4 6 1 、模糊p e t r i 网( f u z z yp e t dn e t s ) 4 7 1 、o b j e c tp e t r in e t 4 s , 4 9 j 等。但是随着 p e t r i 网模型的描述能力越强，性质分析就越困难。动态系统行为的复杂性导 致p e t r i 网分析的高度复杂，这也影响了p e t r i 网在实际中的应用。为此，国内 外的网人一方面不断充实和发展p e t r i 网的抽象能力和描述能力，从c e 网， 经过p 厂r 网直到p r t 网及有色网。另一方面，对于复杂的系统，从基于p e t r i 网的结构分析理论入手，研究网的合成与分解理论。 从p e t r i 网问世以来，有关p e t r i 网的性质的研究就一直非常的活跃。现已 被广泛研究的p e t r i 网的性质包括活性、活性单调性、有界性、s i p h o n 、陷阱 ( t r a p ) 、s - i n v a r i a n t 、t - i n v a r i a n t 等 s o - j 。其中活性和活性有界性是p e t r i 网分析 中的重要行为特征，活性反映了被描述系统的无死锁性，有界性保证了系统的 6 两# 人学顾l ：学位论文 无溢出。对于一般的p e t r i 网系统，有关这些性质的判定非常困难，此类算法 的复杂度往往是指数级的，对于大一点的系统往往不实用。并且人们已经证明 在一般网上讨论网的活性、有界性、公平性和可逆性等性质是n p 的，其中有 些性质还是n p c 的。在n p 问题中设法找到涉及描述问题本质的性质，从而 获得p 类算法，这是做算法研究得理论工作者所追求的。现已得到的对一些 有限定的某些网类已经证实其相应系统的活性和有界性的多项式判定算法确 实存在。这些算法涉及到p e t r i 网系统的活性与该网的不变特性密切相连，有 几个概念在基于结构分析技术的研究过程中一直扮演着重要的角色，s i p h o n 、 陷阱( t r a p ) 和不变( i n v a r i a n t s ) 。s i p h o n 是这样一些库所集合，它们一旦不被标 识就一直不被标识；而陷阱一旦被标泌j 等水远标识，当一蝗f 车所集合既楚 s i p h o n 也是陷阱即是s 不变。探索的腔，首先从标识i 隆 l ( m a r k e dg r a p h ，简秘： m g ) 和状态机( s t a t em a c h i n e ，简称s m p h j 丌始，并得到了比较理恕的结粜： s m 是活的当且仅当它是强联通且被标识的1 5 5 , 5 6 1 ：m g 是活的当且仅当其每个 有向回路中至少有一个被初始标识标识1 5 7 l 。但m g 与s m 所代表的系统是很 简单的子类，描述的问题一般比较简单，所以它的应用范围及其有限。1 9 7 2 年，h a c k 在他的硕士论文中定义了自由选择网( f r e ec h o i c en e t s ，简称f c 网) ， f c 是包含m g 和s m 的子类。并给出了f c 网活的充分必要条件：一个f c 网 是活的当且仅当它的每个( 极小) 非空s i p h含有一个被标识的陷阱(在_on p e t r i 网的结构分析技术中，称作为s t 0 条件) 。一个f c 网是有界的当且仅当网被 强连通的s 分支覆盖且每个s 分支的标识有限。一个活的且有界的f c 网满足 活性单调性。b e s t 证明了：一个活的且安全的f c 网具有家态。当网人把f c 网的性质扩展到更大的子类：非对称选择i 网( a s y m m e t r i cc h o i c en e t s ，简称a c 网) ，在f c 网上成立的很多充分必要性质在a c 网上不存在了。于是，至上世 纪9 0 年代初期到目前，以a c 网为轴心的的研究是结构分析技术的主要内容， 其最新的研究成果参见文 5 8 ，5 9 1 。 一般情况下jp e t r i 网中变迁发生条件满足局部化公理，不用表示系统中 数据值或属性的具体变化或运算。在大型和复杂的系统模型应用中，p e t r i 网 的模型状态空间的规模将随着实际系统规模的扩大而呈指数增长。因此，在实 际应用中，常常不仅需要根据特定的应用环境对网模型加以限制、修改或扩充， 7 两o ；人学坝l ：学位论文 而且需要对p e t r i 网模型进行化简处理或结构分析等。现有的p e t r i 网分析技术 包括： ( 1 ) 基于状念方程和代数分析技术【6 0 , 6 1 , 6 2 l ；代数分析技术主要以关联矩 阵的形式对一个网系统的结构给予刻画，然后建立状态可达的线性系统关系， 这种分析途径首先是由p e t e r s o n l 6 0 】提出，之后m u r a t a l 6 2 l 的工作最为出色。它 的优点是基于线性代数的方法刻画网的静态结构，用不变量( i n v a r i a n t s ) 研究的 网的一些性质，尤其是结构性质。当然，其作用是有限的，难于很好地刻画动 念特征。一般来说，它对可达性的刻画只是一个必要条件，而非充分，只有针 对无冲突的子类l 。是充要的。最近文献【6 2 】试图做出努力，取得了一些进眨， 但仍未很好的解决。 ( 2 ) 基于可覆盖树( 图) 的乡，听技术1 6 3 , 6 4 j ；图分析投术是以一个仃限的 有向( 树) ，直接展现一个网系统的运行机制，类似于一个状念机。k a r l ) 手i j m i l l e r i 叫首先提出这一思想，它的优点是能反映一个网系统的动态行为和一些 特征。特别地，对一个有界p e t r i 网，它能准确刻画，而且对应一个有限状念 机。然而，对无界p e t r i 网，它只能部分反映。虽说可达树是p e t d 网分析的 个较好工具，但无法回避状念空问爆炸。 ( 3 ) 基于化简分解的归纳分析技术1 6 5 1 。针对状态空问爆炸，人们提出极 小可达树、可达树化简等办法来克服这一困难，各种化简方案的提出和应用， 可以使对复杂的网( 或网系统) 的一些性质分析的工作量大幅度地减少。因此 p e t r i 网的化简不失为p e t r i 网分析的一种有力的辅助手段。m u r a t a l 6 6 _ 7 】针对 图提出若干化简规则，并讨论了这些规则对活性、安全性的保持关系；蒋昌俊 推广了m u r a t a 的工作唧j ，进一步提出了对加权t - 图的化简规则，并给出了化 简运算对结构性质的保持条件；a a l s t 6 9 j 在工作流过程验证中使用了这些技术。 m u g a r z a 7 0 l 和f e r s c h a l 7 1 1 给出了并行程序的化简规则，并给出了相应的p e t r i 化 简规则；林剐仫7 3 l 运用自底向上逐步综合替代的分层分析方法，给出了基本 随机p e t r i 网性能等价公式，并利用变迁可实施谓词和随机开关对模型进行了 精化设计及化简。这些化简方法都是在权为1 的p e t r i 网上考虑或者是在加权 的特殊p e t r i 网子类上考虑的；文【7 4 】将化简方法推广到加权的p 厂r 网，并给出 了其对结构性质及公平性、s f f ) 不变量的保持条件。较新的研究成果有基于 8 两# 人学硕l ：学位论文 实时系统的化简规则及其在工作流方面的应用。就总体而言大多数工作都局限 在保性研究上，而且条件过强，很难普适。减弱条件，提高适应性将是进一步 努力的目标。 1 4p e t r i 网理论的应用 p e t r i 网是并发系统和其他很多应用领域的数学工具，它的存在并不仪仅 是为描述并发系统增加一种新的方法，同传统的基于图论所建立起来的自动机 理论相比较，它具有图的静念结构，因此可以充分的利用图论中已有的结论加 以分析研究；同时它还具有捕! 苎系统动态行为的能力这足图论不县备的。另 外，p e t r i 网有着深厚的、孥实j 数学理论作为基础，以p c t r i 网这种模，鹌建立 起来的推理系统能够提供丰富多彩的分析技术。自从p e t r i 刚i u j 雌以米它已 广泛地应用于实践之中。 p e t r i 网以其简洁，直观，潜在模拟能力强等特点被广泛用于离散事件系 统的模拟和分析中，例如多处理器计算机系统、计算机网络、自动控制系统、 交通控制系统和柔性制造等1 7 5 埘j 。p c t f i 网的主要功能是为各种与并行系统有 关的特性和问题提供分析方法。利用p c t f i 网模型可以研究两类特性：依赖于 初始状态和独立于初始状态的特性。前者是指状态行为特性，后者是指状态结 构特性。在大型和复杂的系统模型应用中，p e t f i 网的模型状态空问的规模将 随着实际系统规模的扩大而呈指数增长，网人称为“空问爆炸”。因此，在实 际应用中，常常需要根据特定的应用环境对网模型加以限制、修改或扩充处理 箜 8 2 - 9 4 1 可o 最近数十年来，由于p e t r i 网不仅具有可视化的描述特点，同时还提供完 善的分析工具。所以，它的应用已逐步应用到建模和分析各种过程，其领域从 协议、硬件、嵌入式系统到柔性制造系统、用户交互和业务流程。p e t r i 网模 拟以及数学分析方式已广泛应用于人工智能、形式语义、并行编译、数据管理 等计算机学科的各个领域，其在柔性制造系统及工作流中的应用尤为成功。 2 0 世纪7 0 年代开始，柔性制造系统( f m s ) 已成为p c t r i 网应用的一个重要 领域。西安电子科技大学李志武教授结合结构分析技术，从极小s i p h o n 、陷 9 两仁人学顾i ：学位论文 阱、不变量出发建立了基本s i p h o n 理论，构建控制策略来防止系统死锁，得 到了一些很好的结果1 9 5 l o o l 。 数据库及其管理系统把数据和数据管理从应用程序中分离出来，从而化简 了应用程序的复杂性，也是提高了它的可靠性。每个企业或组织都有自己的业 务。例如，保险公司的投保、索赔；工商企业的订货、发货；领事馆的签证申 领等。传统上，每项业务的处理都是全序的，因为每张保单、每张订货单及每 张签证申领表等都均需顺序经过一道道环节，表格成为串联各任务的纽带，无 需其他管理。计算机使无纸办公成为可能，e 表格代替纸质表格传递和记录业 务信息。e 表格可以复制，合成，使业务环节的并行成为可能。工作流指的就 是在计算机环境下，既l f ：j 行又有顺序的业务流程，j h 。j ：业务的f c l 动化管理。 所谓b u s i n e s sr e e n g i n e e r i n g 是对全序流程或工作流流程的、i k ；争重组。应用问 题是工作流的管理。我们要为描述工作流的流程设计种模型，确定设计口标 并提出分析方法，为工作流管理的形式化打下基础。当使j jp e t f ih 描述业务 流程时，能够采用很多p e t r i 网的分析技术，其良好的图形表示，使之成为流 程定义的优秀工具。这些方面的研究已成为近年来p e t r i 网研究的热点问题 il o l 一1 0 4 1 o 对于复杂系统，可以采用p e t r i 网图形的化简或分层等方法，使得复杂系 统简单化。这给开发设计人员带来了极大的方便。根据p e t r i 网严谨的数学方 法来对模型进行分析验证，即可得到有关系统静态结构和动态行为方面的信 息，这些信息可以对要开发的系统进行评价和改进。p e t r i 网对这些系统特性 有通用的控制策略，对其描述有一定的规则可循，能够做到有效合理地模拟。 协作控制系统是一类典型的并发、同步系统，传统基于p e t r i 网的协作模 型【i 0 5 , 1 0 6 1 ，最常见的是具有协作中心控制的多成员协作模式在该模式下，协 作中心动态地组织协作过程、管理共享的协作对象及分配协作成员对协作对象 的操作控制权等，即在n 个结点中有一个结点为协作控制中心，其余1 1 1 个 结点为一般协作成员，多个协作成员对协作对象进行协同操作，而各协作成员 之间无直接的联系，只与协作控制中心进行直接交互，当协作成员请求对一个 协作对象进行操作时，首先向协作控制中心提出申请，经协作控制中心授权 后才可以对协作对象进行许可操作。操作完成后由协作控制中心向所有协作成 l o 两华人学硕i ：学位论文 员广播协作处理的最新结果信息。本文将利用带禁止和容许弧的增广p e t r i 网 构建一类具有中断处理功能且能够实现任务转移和故障恢复的协作控制系统。 1 5 本文的结构 本文的结构如下： 第二章介绍了p e t r i 网基本概念、术语及相关性质；第三章给出了基于增 广p e t r i 网的协作系统解决方案；第四章基于增广p e t r i 网的混惑消除；第血章 进行总结。 两f ；人学顺i ：学位论文 第二章p e t r i 网的基础知识 本章，我们将对以后各章节所需要用到的p e t r i 网的一些基本概念和术语 作简单的介绍。详见文【6 ，4 6 ，1 0 7 ，1 0 8 ，1 0 9 ，1 1 0 。 2 1p e t r i 网的基本概念 定义2 1 1 二i 元组n = ( j p ，丁；，) 是一个p e t f i 网( 简称网) ，当且仅当： ( 1 ) p n t - 口p u t 妒； p = p i ，