（计算机软件与理论专业论文）petri网运算及其性质研究.pdf

山东科技大学硕士学位论文摘要 摘要 p e t r i 网作为系统模拟与分析的工具已在众多领域得到应用。同其他分析方 法一样，p e t r i 网对于大系统的分析是非常复杂的。因此，通过一些较为简单的 小网利用某种运算或组合而得到较为复杂的大网，且在组合过程中保持网的某 些性质不变，或者对于一个大系统，利用p e 砸网的分解技术把大系统分成若干 小的子网来进行分析，这些无疑为大系统的分析提供了很好的途径。已有文献 提出了p e 越网的加法、笛加、笛积、广义笛加等运算并研究了一系列重要性质。 另有文献定义了p e t r i 网的并运算、分解运算，讨论了这些运算保持网的结构性 质和公平性的条件。结合近年来p e t r i 网理论的发展，本文进一步研究了网运算， 分析了并运算的代数性质；针对网的分解运算，给出实例显示了网的分解运算 的背景及意义：同时讨论了网的并分解及和分解，研究了这些运算保持网的结 构性质和动态性质的条件。 关键 司：p e 研网，并运算，并分解，和分解，结构性质，动态性质 山东科技犬学硕士学位论文摘要 a b s t r a c t a sak i n do ft 0 0 lf b rs y s t e m m o d e l i n ga i l d 趾a l y z i n g ，p c t r i n c t sa r ew i d e l yu s e d h o w e v e r i tc o s t st o om u c h ( t i m ea n ds p a c e ) t oa i l a l y z eal a r g ea i i dc o m p l i c a t e d s y s t e m i f w c u s e 血c 嘶g i n a l p e t r in e t m o d c lo f s y s t e m a s 也e a i i a l y s i so b j c c ts o “i s 0 f t e nn e c e s s a r yt oc o m p o s eal a 唱e ，c o m p l i c a t e ds y s t e mf 如ms o i r 圯s m a l l ，s i m p l e o n e sw i m 山ee s s e n t i a lp r o p e m e s p r e s e r v e d ，o r t od c c o m p o s ea c o m p l i c a t e d p e t r in e t i n t os o m es i i n p ko n e su n d c rt h ec o n m t i o na t 0 u tp r e s e r v i i l gs o m ep m p e n i e so fp e t r i e t u n d o u b t e d l y a l lt h e s em c t h o d sa r eu s e f u lf b ra r i a l y z i n gl a r ：g es y s t e m s s o m en e t o p e r a t i o n s ，s u c h 淞a d m t i o n ，c a n e s i a i ia d d i t i o n ，c a n e s i a i lp f o d u c t i o na i l dg e n e r a l c a 毗s i a np r o d u c t i o n0 fw e i g h t e dn e ts y s t e l s ，w e r ep r e s e n t e di ns o m ep a p e r s ，a n d u i l i o no p e m t i o n ，d e c o m p o s i 怕n0 p e 叫o n sw e 他g i v e ni no ( h e r s t h ec o n d i t i o n sf o r p f e s e f v i n gs t m c t u r a l 嬲dd y n 戚cp r o p e r i i e so f 也e n e ta f t e r 也e s eo p e r a t i o n sw e r e d i s c u s s e d s o r 雎北to p e r a t i o n sa mf u r 0 1 e rs t l l d i e di nt h i sn l e s i s u i l i o no p e r a t i o ni s 卸a l y z e d 舳d o n ee x a m p l c i s 百v e n t om a k et h eb a c k g r o u n d 姐d m e a i l i n gc l e a d y f o r n e td e c o m p o s i t i o n 哪屺r a t i o n s a tt h es a m et i m eu i l i o n 卸da d m n o nd e c o m p o s i t i o n a f em a i l l l yd i s c u s s e d k e y w o r d s ： p e 血n e t ，u n i o nd c c o i r 啦o s i t i o n ，a d 蛳o n d e c o m p o s i 廿o n ， 蚰n l c m r a lp p e r t y d y n a m i c p r o p e r t y 声明 本人呈交给山东科技大学的这篇硕士论文，除了所列参考文献和世所公认的 文献外，全部是本人在导师指导下的研究成果。该论文尚没有呈交于其它任何学 术机关作鉴定。 研究生签名：海于分 日 期：1 一i 石6 a f f i r m 啥t i o n id e c l a 弛t h a tt l i i sd i 雠r t a 蚰，s u l 瑚i 仕e di nf u m m n 恤t o ft h er e q l l i n m 咖曲f o rt l i e a w a r do fm a s t e r0 fp h i i 惦o p h y ms h a n d o 嘴u n i v e 倦时o fs c i 咖e 蚰dt 灿l o 鼢 i sw h 0 u ym yo w nw o r ku n l e 璐州衙e n c e do f 舵k 舯w l e d g e t h ed o c 哪嘶th a sn o t b 咖s u b n i i t t e df o rq u a 断6 0 na t 柚yo m e ra d e m i ci 蛐把 s 咖恤：弘牙叼s i 霉衄t e ：扣扩1 扩 d a t e ：；一j - 山东科技大学硕士学位论文绪论 1绪论 1 1p e t r i 网的产生和应用 p e t r i 网是由德国的c a r la d a mp e t r i 于1 9 6 2 年在他的博士论文“自 动机通信”中首次提出的，它是一种适用于多种系统的图形化、数学化 建模工具，为描述和研究具有并行、异步、分布式和随机性等特征的信 息加工系统提供了强有力的手段。与传统的系统建模、分析和控制方法 相比，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 网在现代制造业中的柔性制造系统 ( f m s ) 有着比较广泛的应用；此外，在p c t r i 网在编译和操作系统，并 发和并行编程，决策模型，可编程逻辑和超大规模集成电路阵列，异步 电路和结构等领域也有不同程度的应用； 1 2 问题的提出 p e t r i 网应用的主要途径之一是对于我们要研究的实际系统，先构造 得到其相应的p e t r i 网模型，然后通过对p e t r i 网模型的分析来了解实际 系统的各种性能。但对一个规模大的系统，可能会出现状态组合爆炸的 危险，从而给分析带来很大困难。针对这个问题，国内外学者作了许多 工作，他们提出了网化简、网运算，定义了化简子网、等级化简，以及 针对特殊子网、特殊结构的化简方法【6 s l 。自国内的吴哲辉教授、蒋昌俊 教授和王培良教授提出p e t r i 网的合成运算或分解运算以来，在p e t r i 网 运算方面取得了一些新的进展。文【9 1 1 】提出了网的加法、笛积和广义笛 积运算的定义并分析了合成后所保持的网的结构有界性、守恒性、可重 复性、协调性，以及s 一不变量和r 一不变量等；文【1 2 1 3 ，1 4 提出了网 山东科技大学硕士学位论文绪论 的并运算、并分解和和分解的定义并分析了运算后所保持的网的结构有 界性、守恒性、可重复性、协调性、公平性和弱公平性等；文【1 5 1 8 】提 出了若干p e t r i 网运算的定义，有组合加网、笛加网、组合并网、笛并网、 组合积网、并积网等，这些是分别对应库所、变迁和流关系的不同组合 而得到的，并讨论了这些运算的部分代数性质。到目前为止，各文献已 给出若干种网运算，但相对于p e t r i 网理论而言，合成或分解的网运算是 否有一些其他重要特性，是否还有未提出的网运算，以及如何降低条件 使网运算能很好的保持网的性质等问题都是需进一步研究的内容。 基于以上的分析，本文主要针对p e t r i 网的合成或分解运算进行了研 究，扩充了运算的定义并讨论了运算后所保持的网的结构性质：s 一不变 量和r 一不变量、死锁与陷井；两种p e t r i 网子类的动态性质以及网的( 亚) 公平性等。 1 3 本文的内容安排 本文从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 网运算的概况及其相关的研究历程， 其中包括了各种文献所提出的p e t r i 网的合成或分解运算的若干方法；本 文继续分析了p e t r i 网加法运算和并运算的代数性质；第四章扩充了p e t r i 网的并分解及和分解运算的概念，并对运算进行了性质分析；第五章是 本文的结语，总结本文所作的工作并讨论了今后所要继续研究的工作。 一2 一 山东科技大学硕士学位论文p e t r i 网的基本概念与基本性质 2 p e t r i 网的基本概念与基本性质 2 1 p e t r i 网的基本概念1 5 l 定义2 1 满足下列条件的三元组= ( p ，r ；，) 称为一个网 1 ) p u r 西 2 ) 尸n r = 西 3 ) f e ( ( p 丁) u ( r 尸) ) 4 ) d d m ( f ) u c d d ( f ) = p u r 其中 锄( f ) = 扛p u r c 珍p u r ：o ，) ，) ，) c 谢( f ) = x p u r ( 匆尸u r ：( y ，曲e ，) 口 p 和r 是两个不相交的集合，称为网的基本元素集，p 的元素称为p 元或位置( 库所) ，丁的元素称为t 元或变迁。，是网的流关系。一个网可 以用一个有向二分图来表示：把一个p 元画成一个小圆圈，一个r 元画成一 个小矩形，对y p u r ，若( 工，y ) f ，则从工到) ，画一条有向弧。 定义2 2 设= ( p ，瓦f ) 为一个网，对工p u r ，记 工= y ( ) ，尸u r ( y ，曲f ) z = ( y p u r ( 而y ) f ) 称z 为工的前集或输入集，工为x 的后集或输出集、u 工称为元素毒的外延。 定义2 3 设| = ( p ，死，) 为一个网 1 ) 若工p u 扎j n j = 咖，则称为一个纯网( p “坤n 鲥) ； 2 ) 若而y p u 丁：( 。工= y ) o = y ) _ = ) ，) ，则称为一个简单网 ( s f ，印k n 盯) 。 3 ) 若s s ：l 4 = h = 1 ，则称为一个7 - 图( 丁一g 唧； - 3 - 山东科技大学硕士学住论文p e t r i 网的基本概念与基本性质 4 ) 若r 扎h = 川= 1 ，则称| 为一个s - 图( s g 唧 ) 定义2 4 设= ( p r ；，) 为一个网。o 为非负整数集。映射m ：p - o 称为网的一个标识，( ，m ) 称为标识网。 用图形来表示标识网时，对p p ，若肘( p ) = t ，则在位置p 的小圆圈内加 上个小黑点( 数值较大时，也可直接写上数字女) ，并称p 中有女个标志。 定义2 5 一个网系统是一个标识网= ( m ) ：( 尸乃f ，m ) ，并且有 下面的变迁发生规则： 1 ) 对f 丁，若v p 。 m ( p ) l ，称肘授权f 发生，记为m 【f ( 当t = 妒时，f 在任意标识下都有发生权) 。 2 ) 若标识m 授权f 发生，则变迁r 在m 下可以发生( 力坤) ，从j l f 发生f 得到 新的标识肼( 记作州f m ) ，对v 口p ： 帅，懈；： p t r p e r 一f o t i l e r s 一个网系统有一个初始标识，记为 毛。可能有若干个变迁在有发生权， 随意选择其中一个( 一组) 变迁发生，得到一个新的标识，如m 。( 不同的变迁发 生，产生新的标识也不相同) 。在帆又可能有若干变迁有发生权，其中一个( 一 组) 发生，又得到一个新的标识这样继续下去，就是网系统的运行。通 常把这种网系统称为p e t r i 网。 中 定义2 6 六元组z = ( p ，死r 墨，肘) 称为一个位置，变迁系统，其 1 ) 乃f ) 是一个网； 置：p _ o ( o 是自然数集合) 称为容量函数； w ：f - 0 一f o j 称为权函数； m ：p _ n 是的一个标识，满足条件 v p p f ( p ) 置( p ) 2 ) 满足下面变迁发生规则： a ) 对f e r ，m n 的条件为 山东科技大学硕士学位论文p c t r i 网的基本概念与基本性质 v 肘( ，) ( 力，) 、咖f 一r ： f ( p ) + w ( f ，p ) 芷( p ) 、咖rn f f ( p ) + w ( f ，p ) 一w ( p ，f ) 置( p ) b ) 若m p 肘，则对v p p ： m ( p ) = m ( p ) 一h 7 ( p ，f ) 当占f r m ( p ) + w ( p )当p r 一。f m ( p ) 一w ( p f ) + w ( “p ) 当p f n 广 m ( p )当p 芒u r p 厂r 系统是在p e t r i 网的基础上，对各位置加上容量限制并对各条弧赋于 权值得到的。由于容量函数和权函数的作用，在p ，r 系统中一个标识m 授权 某些变迁f 发生，不仅要求变迁f 的每个输入位置p 的标志数m ( p ) 不小于p 的f 的弧上的权w ( p f ) ，而且要求变迁发生后f 的每个输出位置的容量不被 突破。同样，一个变迁的发生使其前集和后集中各位置的标志数的变化也要 根据各位置同该变迁之间的连接弧的权的大小而定。 p 厂r 系统的提出，是为了便于对某些实际系统构造网模型。对于一个p ，r 系统，如果v p p 置( p ) = * ，v r ，：w ( ，) = l ，那么这个p ，r 系统就是定义 过的p e t r i 网，但是p ，r 系统并不比p e t r i 网有更强的模拟能力。理论上已证明， 任一个p ，r 系统都可以转化为一个行为等效的p e 啪网。鉴于p 腰系统便于对某 些实际系统构造网模型，文【9 一1 1 ，1 4 4 0 ，4 3 _ 4 5 。4 7 】提出了p ，r 网的若干运算方法 以达到对实际系统模型的更好的分析。 如果规定p ，r 系统中各库所的容量为无限大。即取消库所集上的容量函数 限制而只保留弧集上的权函数，便得到一个五元组z = ( p 死丹w ，m ) ，我 们把这种介于p e t r i 网和p ，r 系统之间的网模型称为加p e t r i 权网，而四元组 ( p 死，w ) 为一个加权网。 2 2 p e t r i 网的动态性质1 5 】 以p e t r i 网( 不含权函数和容量函数的网系统) 为模型，定义和讨论网系统 运行过程中的一些性质，并把这些性质统称为动态性质( 由删l c p r 口p p m 曲或 行为性质( 6 9 枷 阳fp 唧8 ，f f 酣) 。这些性质同p e t r i 网所模拟的实际系统某些 方面的性能有密切的联系。在其它的网系统中，这些性质的定义可以很容易 得到延伸。 山东科技大学硕士学位论文p e t r i 网的基本概念与基本性质 下面给出p e t r i 网的各种性质所代表的系统特性。 1 可达性：( m 口幽曲劝 可达性是p e m 网的最基本的动态性质，其余各种性质都要通过可达性来 定义。 定义2 7 设= ( p ，乃em ) 为一个p e t r i 网，如果存在f r ，使得 州f m ，则称肘。为从m 直接可达的。如果存在变迁序列，f ：，f 。和标识序 列m ，m ：，m 。使得 肘【f l m l 【| 2 m 2 f i l 【f l 以 则称肘。为从m 可达的。从肘可达的一切标识的集合记为r ( m ) 。约定 m r ( m ) 。 用p e t r i 网模拟一个实际系统时，网( p ，瓦f ) 描述予系统的结构，初始标 识 如表示系统的初始状态，而r ( 如) 给出了系统运行过程中可能出现的全部 状态的集合。 定义2 8 设= ( 只死rm 。) 为一个f i e t r i 网，其中娥是的初始标识。 的可达标识集r ( 蝇，) 定义为满足下面两条件的最小集合： 1 ) 氓r ( ) ； 2 ) 若肼r ( m o ) ，且存在f t 使得m 【f m ，则膨r ( m i ) 。 对于有界p e t r i 网，由于其可达标识集r ( 厶) 是一个有限集，因此可以以 r ( 肘。) 作为顶点集，以标识之间的直接可达关系为弧集构成一个有向图。这 种有向图称为p e 伍网的可达标识图( ，8 恸km 口崩岵g 嗍蝴。 2 有界性和安全性曲d “埘砌l 跚甜d 删锄跚) 定义2 9 设z = ( p ，死 m 。) 为一个p e t r i 网，p p ，若存在正整数b ，使 得协f r ( j l f 。) 肘( p ) b ，则称位置p 为有界的，并称满足此条件的最小正 整数丑为位置p 的界，记为b ( p ) 。即 b ( p ) = i i l i n 8 ( v j l f r ( 肘i ) m ( p ) b ) 当b ( p ) = l 时，称位置p 为安全的。 山东科技天学硕士学位论文p e t r i 网的基本概念与基本性质 定义2 1 0 设= ( 只死，肘。) 为一个p c t r i 网，如果每个p p 都是有界 的，则称z 为有界p e t r i 网。称 曰( z ) = m a x 忙( p ) ( p p ) 为的界。当b ( ) = l 时，称为安全的。 有界性( 安全性) 反映系统运行过程中对资源容量的需求。在实际系统的 设计中，必须使得网中的每个位置在任何状态下的标识数小于位置的容量， 这样才能保证系统的正常运行，不至于产生溢出现象。 3 活性( z 扣e h e 船) 定义2 1 1 设z = ( p 丁；f ，肘o ) 为一个p e m 网，峨为初始标识，f r 。 如果对任意m r ( m 。) ，都存在m e r ( j l f ) ，使得j l f p ，则称变迁f 为活的。 如果任f r 都是活的，则称为活的p e 廿i 网。 4 公平性( 血棚伽) p e t r i 网的公平性旨在讨论网系统中两个变迁( 变迁组) 的发生之间的关系。 这种关系反映被模拟系统的不同部份在资源竞争中的无饥饿性问题。 定义2 1 2 设z = ( p ，t ；，m 。) 为一个p e 廿i 网， 。e 丁。如果存在正整 数t ，使得对任意肘r ( m o ) 和任意仃r ：肘【盯 都有 样( ，o = 0 _ 井( j ，o ，k f ，j 1 ，2 】，f j ( 2 1 1 ) 则称f 。和f 2 处于公平关系。如果z 中任意两个变迁都处于公平关系，则称为 公平p e t r i 网。 文【1 9 】研究了有界网的活性和公平性；【2 0 ，2 1 】提出了用于公平性判断的若 干方法；【2 2 】对公平性的概念进行了拓展，提出了弱公平性的概念；【2 3 】对公 平性的概念进行了进一步的拓展，提出了广义公平性的概念；而文【2 4 2 5 】则 提出了亚公平性的概念。我们会在本章2 6 节中更加详细的介绍和p e m 网的公 平性相关的概念和分析方法。 5 持续性( 即玷妇加c ) | ) p e t r i 网的持续性是这样的一种性质：如果在可达标识m 下变迁r 有发生权， 那么从m 发生了其它任意变迁或任意不包含f 的变迁序列后，f 仍有发生权。 山东科技大学硕士学位论文p e t r i 网的基本概念与基本性质 如果一个p e t r i 网中对任意可达标识和任意变迁t ，上面所述性质都成立，就称 这个网为持续网。 定义2 1 3 设z = 丁：rm o ) 为一个p e t r i 网，如果对任意肘r ( 肘o ) 和 任意f l ，f 2 l ( f l f 2 ) ： ( 肘【f l 膨【f 2 m ) _ m 【f l 则称为一个持续网。 6 可逆性( ，删e 坩曲f f f o ，) 定义2 1 4 设= 乃f ，m 。) 为一个p e t r i 网，m r ( 毛) ，如果对 v m 尺( 肘) ，都有肘暑r ( 肘。) ，则称m 为的一个可返回标识或一个家态。 定义2 1 5 设z = ( 只r ；bm 。) 为一个p e m 网，如果z 的初始标识是 一个家态，则称z 为可逆网系统。 p e t r i 网的可逆性反映了系统的可恢复性。 对于p e t r i 网的动态性质，在关于p e t r i 网运算的文献中，文【3 0 ，3 2 】针对t 图提出了若干化简运算方法，讨论了这些方法对活性、安全性的保持关系； 文【3 6 】提出了基于可达图化简的动态分析方法；文【1 2 1 4 ，4 0 _ 4 l 】等运算方法均 对保持网的公平性进行了讨论；文【5 2 】则讨论了网的活性和可逆性的保持条 件。 2 - 3 p e 懈网的分析方法1 - 5 】 网论对p e 砸网已提出了多种分析方法，主要有可达标识图与可覆盖性树、 关联矩阵与状态方程、p e t r i 网语言与p c t r i 网进程等。这些方法都建立在坚实的 数学基础之上，各自有其优点和不足之处。 2 3 1 可迭标识图与可覆盖性树 定义2 1 6 设= ( p ，r ；f ，m 。) 为一个有界p e t r i 网。z 的可达标识图定 义为一个三元组尺g g p = ( r ( j l f o ) ，e ，) ，其中 e = ( m i ，肘川哆，m je r ( ) ，j | i p m 【气 肼) ，：e _ 7 ，( m i ， f j ) = & 当且仅当m f m m 8 山东科技大学硕士学住论文p e t r i 网的基本概念与基本挂质 称r ( 如) 为r g ( ) 的顶点集，e 为尺g ( ) 的弧集，若，( m 。m ，) = f i ，则称f 。为 弧( m 。，m ，) 的旁标。 当不是有界p e 啊网时，由于r ( 厶) 是一个无限集，不可能画出z 的可达 标识图。为了用有限形式表达一个有无限个状态的系统的运行情况，需要引 入一个表示无界量的符号。具有这样的性质 1 ) 对任意正整数n ： n 。n = 2 ) 当位置s ；中的标识数在p e t r i 网的运行中趋向于无限增长时，就把标识向量 中的第j 个分量改为，以此覆盖所有这类标识。这样，就可以通过一个有限 树来反映这个p e t r i 网的运行情况。称这种有限树为p e m 网的可覆盖性树， 记为c r ( ) 。 对于有界p e t r i 网，采用可达标识图可分析可达状态、可逆性、活性、公平 性和位置的有界性等。对于无界p e 仃i 网，则可采用可覆盖树或可覆盖图分析 p e t r i 网的有界性。由予无界量的引入，不易分析网的活性和可达性等特征。 文 1 9 利用可达标识图很好地分析了有界p 砌网的活性和公平性。 2 3 2 关联矩阵和状态方程 正如p c t r i 网的一个标识可以表示成一个m 维非负整数向量一样，p e 廿i 网 的结构也可以用一个矩阵来表示。这样，就可以引入线性代数的方法对p c t r i 网的性质进行分析。 定义2 1 7 设= 仍孔b 肘) 为一个p c t r i 网，p = a ，助，儿) ， 丁= ，f ：，f ) ，则p c t r i 网的结构( s ，已，) 可以用一个m 行 列矩阵 c = 【】。 来表示。其中 q = 菇一丐 f l ，2 ，m ) ， 1 ，2 ，n +f 1( f f ，只) f f l ，2 ，m l ， 1 ，2 ，n 。f 一1 0o t h e r s f 1( a ，f ，) f f ( 1 ，2 ，m ，j 1 ，2 ，n ) q 2 1 0o t 二 称c 为( 或网= ( p tr ；，) ) 的关联矩阵。 山东科技大学项士学位论文p e t r i 网的基本概念与基本性质 定理2 1 设= ( p ，死 m o ) 为一个p e t r i 网，其中m o 为初始标识，c 为z 的关联矩阵。若肼r ( 矗) ，则存在非负整数，l 维向量x 使彳导 m =m n + c x 上式称为p e t r i 网的状态方程。它给出了p e t r i 网中，m 从m ，可达的一个必 要条件。 文 2 2 2 4 都是从关联矩阵出发，研究网结构公平性的。 对于弧权不恒等于l 的网系统( 如p ，r 系统，加权p e t r i 网等) ，也可以引入关 联矩阵的概念。下面以加权p e t f i 网为例作一简述。 设z = ( s 死f ，w ，肼o ) 为一个加权p c 仃i 网，其中p = 协，p 2 ，) ， r = r 。，f ：，f 。的关联矩阵定义为 c = 【气】。 其中 勺= g 一百 f 1 ，2 。，m ，j l ，2 ，j l 芍= m 轰舶f 旭2 m k 批n 2 川 巧= ：，b 。耄则 b 。f 1 2 一 m h 7 1 2 ， “ 此外，对p e t r i 网系统进行分析的另一种方法是考察网系统中一切可能发生 的变迁序列以及这些序列构成的集合的性质。众所周知，某字母表上满足某 些特定条件的字符串的集合，称为该字母表上的一个语言。如果我们定义了 从一个p e t r i 网的变迁集r 到某个字母表a 上的一个映射，那么该p e t r i 网上所有 可能发生的变迁序列( 或各序列映射到a 上的字符串) 的集合就是丁( 或a ) 上的一个语言，即：p c t r i 网语言；还有一种分析方法是建立在出现网和网映 射等概念的基础上的p e t r i 网进程。 在p c t r i 网的各种运算方法中，大部分都利用了关联矩阵；文【3 6 】是利用可 达图来进行分析的：而文【4 7 _ 4 9 】则是利用了p e 仃i 网语言来分析p e t r i 网的合成运 算的。 2 4 p e t r i 网的结构性质f 1 5 】 p e t r i 网的结构性质是这样一类性质：这些性质由网的结构( 基网) 确定， 而同网的初始标识无关因此，把这类性质称为网的结构性质 ( s f 九l c m r ，p r 叩p 脚曲主要有结构有界性、守恒性、可重复性、协调性、s 一不 山东科技大学硕士学位论文p e t r i 网的基本概念与基本性质 变量和t 一不变量、可重复向量、死锁与陷井等。由于这类性质由网的结构 确定，它们都可以通过网的关联矩阵给出确定的判定准则，得到比较完整的 分析结果。这些结果又是用代数方法分析p e t r i 网的基础。 定义2 1 8 设= ( p ，丁；，) 为一个网，如果对赋予任意初始标识 网系统( ， f 0 ) 都是有界的，则称为结构有界网。 定理2 2 设a 为网= ( p ，nf ) 的关联矩阵，则为结构有界网的充 分必要条件是：存在m ( m = h ) 维正整数向量y ，使得c 7 y s o 。 定义2 1 9 设= r ；f ) 为一个网，如果存在一个m ( m = | p i ) 维正整 数权向量y = b ，( 1 ) ，) ，( 2 ) ，y ( m ) r ，使得对的任一个初始标识和任意 f r ( 帆) 都有： 暑m ( p ，) y ( j ) 2 盖m 。( p ，) y ( j ) 则称为守恒的。特别地当y = 【l ，1 ，。1 】r 时，我们得到 m ( p ，) = m o ( p ，) j 叭j o j 这时称为严格守恒的。 从定义2 1 9 知，一个严格守恒网对任意给定的初始标识峨和任意从可 达的标识肼，网中标志数的总和是一个常数。对于( 一般) 守恒网来说，则 是标志数的加权和不变。 定理2 3 设= ( p 死f ) 为一个网，c 是的关联矩阵，为守恒网 的充分必要条件是：存在m ( m = ) 维正整数向量y ：c y = o 。 定义2 2 0 设= ( p ，死f ) 为一个网，若存在的一个初始标识和 一个无限的变迁序列盯丁，使得 f 0 【仃 ，且v f r 都在仃中无限多次地出现， 则称为一个可重复网。 定理2 4 设= ( p ，乃，) 为一个网， 为的关联矩阵。则为可重复 网的充分必要条件是：存在n 伽= 例) 维正整数向量x ，使得c ；j f o 。 - 1 1 - 生查型型生蔓兰堕主主堡垒圭p e t r i 网的基本概念与基本性质 定义2 2 1 设= ( 尸，死，) 为一个网，若存在的一个初始标识和 一个变迁序列盯r 使得【仃 ，而且v f 扎# ( f ，仃) 1 ，则称为一个 协调网。 定理2 5 设c 为网= ( p ，r ；f ) 的关联矩阵，则为协调网的充分必 要条件是：存在正整数n ( n = j 卅) 维向量x ，使得c x ：o 。 阵。 定义2 2 2 设= ( p ，丁；f ) 为一个网，| p l = m ，川= n ， 为的关联矩 1 ) 如果非平凡的m 维非负整数向量y 满足c r y ：o ，则称y 为网的一个 s 一不变 2 ) 如果非平凡的肛维非负整数向量x 满足c x ：0 ，则称x 为的一个r 一 不变量。 定义2 2 3 设x ，x ，x ：，以都是非平凡的非负整数厅维向量，如果存 在一组非平凡的非负整数c 1 ，c ：，g 使得： x = c l x l + c ：x 2 + + c i x i 则称x 能被x 。，x ：，x 。非负整数系数线性表出。简称x 能被置，x ：，x 。 线性表出。 类似可定义线性相关、线性无关和线性组合等术语。 定义2 2 4 设= ( 尸瓦f ) 为一个网，c 为的关联矩阵，若n 维非平 凡的非负整数向量x 满足c y 0 ，则称x 为的一个可重复向量。 定义2 2 5 设= ( p r ；f ) 为一个网，日p 。如果。墨c 墨，则称只为 网 r 的一个死锁，如果最e 墨，则称毋为的一个陷井。 各文献提出的p e t r i 网的合成或分解运算对保持p e t r i 网的结构性质进行了 讨论。只有很好的保持了网的结构性质，所提出的运算方法才能很好的用于 分析实际系统模型，进而解决“状态爆炸”的问题。 山东科技大学硕士学位论文p e t r i 网的基本概念与基本性质 2 5 一些p e t r i 网子类的活性分析和判定【1 5 】 p e m 网各种动态性质中，活性是比较难以判定的一种。对一些p e 砸网子类 讨论其活性的分析和判定问题。所讨论的子类包括：标识s 一图，标识r 一图 等。这些子类由于结构上的特殊性，对其活性可以得到比较完整的分析结果， 可以给出比较简明的判定依据。本文在讨论p c t r i 网的并分解及和分解运算保 持网的性质时，用到了以下定义和定理： 定义2 2 6 网= ( p 丁；f ) 称为一个s 一图当且仅当 v f 死h = 川= l 如果是一个s 一图，m 为的一个标识，则称( ，肘) 为标识s 一图。 一个s 一图= ( p r ；f ) 可以简化表示成一个有向图阳= ( p ，e ) 其中的结点集p 就是网的位置集，昱为图站的有向边集。这样得 到：气= ( 只p j ) e 当且仅当存在气使得 = 只= f ， 。 ( 2 1 ) 由于s 一图中每个变迁只有一个前置库所和一个后置库所，为方便起见。( 2 1 ) 也可简记为 气= p f= p ， 当把一个s 一图= ( p ，t ；f ) 简化表示成踮= d 时，显然有： 1 ) 旧= 1 7 1 ，而且e 中的元素( 有向边) 同t 中的元素( 变迁) 存在着一一对应 关系。具体地说，s g 中的一条有向边对应着中的一个变迁连同该变迁的输 入弧和输出弧。 2 ) ( 作为一个网) 的关联矩阵c ( 见定义2 1 7 ) 是跖! ( 作为有向图) 的关联 矩阵( 依据图论中的定义) 。 以后当我们说网是一个s 一图时，就用= ( p e ) 来表示。 定理2 5 设= ( p ，e ) 为一个s 一图，为的初始标识，则( ， “) 为 活的充分必要条件是是一个强连通图且m 。( p ) 1 。其中 肘o ( j p ) = m o ( p ) 山东科技大学硕士学位论文 p e tr i 网的基本概念与基本性质 定义2 2 7 网= ( p 乃，) 称为r 一图当且仅当 却a h = l p i = l 如果是一个丁一图，m 为的一个标识，则称( ，j i 彳) 为标识丁一图 和用= ( p e ) 来表示网是一个s 一图类似，我们用= e ) 来表 示网是一个r 一图。 定理2 6 设= ( le ) 为一个r 一图，为的一个初始标识，则 ( ， “) 为活的充分必要条件是：对的任意有向回路c ： ( o 1 。 2 6 p e 珊网的公平性分析【1 _ 5 】 p c m 网的公平性质旨在讨论网系统中各变迁( 或变迁组) 发生之间的相 互依赖关系。这种关系反映了被模拟系统运行过程中各个部件( 各个进程) 之问 的相互依赖，即是否满足无饥饿性的问题。由于无饥饿性是系统运行中的一 个重要性质，因此p e l r i 网的公平性质分析也是p e 矾网理论的一个重要组成部 分。本文讨论了p e t f i 网的并分解及和分解运算保持网的公平性、亚公平性的 条件。 定义2 2 8 设= ( p ，孔r 肘o ) 为一个p e m 网，f l ，f 2 r ，如果存在 正整数t ，使得对任意材r ( 眠) ，和v 叮r ：m 妙 都有 襻( f l ，仃) = o - 并( 乞，仃) t 则说在中，变迁f 2 公平依赖于f 。 定义2 2 9 在= ( 只已，肘。) 中， ，f 2 r 。如果 公平依赖于屯， 且f 2 公平依赖于f 。，则说t 和r 2 在中处于公平关系。 定义2 3 0 设= ( 尸，孔r 肘o ) 为一个p e 埘网，如果对于任意，f ，e r ， 和0 在中都处于公平关系，则称为一个公平p e m 网。 山东科技大学硕士学位论文p e t r i 网的基本概念与基本性质 定义2 3 l 设 ，= ( p ，丁：f ) 为一个网，如果对于的任意初始标识m 。 = ( ，m 。) 都是公平p e m 网，则称| 为一个公平网。 【例2 1 】在图2 1 的p e t r i 网中，任意两个变迁都处于公平关系。因而这是 一个公平p e t r i 网。 图2 1 一个公平p e m 网 定义2 3 2设= ( p ，乃，) 为一个网，l 刀= n ，c 为网的关联矩阵。 如果对于任意n 维非负整数向量x a | ：0 j v ， 1 ，2 ，n ：x ( j ) o 即x 必为正整数向量，那么我们说的每一个可重复向量都不含零分量， 或说满足可重复的整体性条件。 定理2 7 若网= ( p ，r ；f ) 为一个公平网，那么必须满足可重复的 整体性条件，即的每一个可重复向量都不含零分量。 定义2 3 3 设= ( p 丁；rm o ) 为一个p e l r i 网，f l ，f 2 r ，如果对任 意肘r ( 如) ，都存在正整数女，使得v 盯t ：m p 都有 # ( f 1 ，盯) = o # ( f 2 ，d ) 七( 7 1 ) 则说在中，变迁f 2 弱公平依赖于f l 。 山东科技大学硕士学位论文 p e t r i 网的基本概念与基本性质 定义2 3 4 设= ( p 死rm 。) 中，f ，f 2 丁。如果f l 弱公平依赖于岛， 且f ：弱公平依赖于f 。，则说f ，和f2 在中处于弱公平关系。 定义2 3 5 设= ( p ，丁； m o ) 为一个p e 戚网，如果v f f ，f j 丁，和 自在中都处于弱公平关系，则称为一个弱公平p e f r i 网。 定义2 3 6 设= ( 尸，死，) 为一个网，如果对于的任意初始标识肘。， = ( ，m 。) 都是弱公平p e m 网，则称为一个弱公平网。 定理2 。8 = ( p t ：f ) 为一个弱公平网当且仅当满足可重复的整体 性条件。即对任意满足c x o 的n ( h = l r i ) 维非平凡非负整数向量x ，x 的每一 个分量都必为正数，其中c 是网的关联矩阵。 定理2 9 设= ( p ，死f ) 为一个网，为网的关联矩阵，那么网 为公平网的充分必要条件是： 1 ) 的每一个可重复向量都不含零分量； 2 ) 的任意两个可重复向量都线性相关。 定义2 3 5设三= ( p 孔rm o ) 为一个p e 晡网，l l ，f 2 芒t ，如果 1 ) 对啪r c m o ) 都存在正整数七任意d r ：枷仃 都有 井( f l ，叮) = o _ 峁( f 2 ，叮) 七 2 ) 对任意正整数露，都存在m r ( m o ) ，v 仃t ：肘俺 满足 群( f l 仃) = o 群( f 2 ，仃) 七 则称f 2 亚公平依赖于f ，。 定义2 3 6 设= ( p ，死，m 。) 中p e f r i 网，f l ，r 2 r 如果f 1 亚公平依赖 于乞，且f 2 弱公平依赖于f 。，则称f ，和如在中处于亚公平关系。 山东科技大学硕士学位论文p e t r i 网的基本概念与基本性质 定义2 3 7 设= ( p 丁；，) 为一个网。如果对于任意初始标识肘。， = ( ，m 。) 都是弱公平p e m 网；而且存在初始标识m l ，使得z = ( ，m 。) 不 是公平p e m 网，则称为一个亚公平网。 由这个定义知，亚公平网必须是一个弱公平网，但不可能是公平网，这样， 就可以给出如下等价定义。 定义2 3 7 设= ( 只丁；，) 为一个网，如果是弱公平网但不是公平 网，则称为一个亚公平网。 是 定理2 1 0 设= ( 尸r ；，) 为一个网。则为亚公平网的充分必要条件 1 ) 的每个可重复向量都不含零分量 2 ) 存在的两个可重复向量x 1 和憋，使得x l 和x 2 线性无关。 山东科技大学硕士学位论文关于p e t r i 网运算的研究 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 网的合成和分解 运算。 3 1p e t r i 网运算的概述 3 1 1 p e t r i 网运算的提出 p e t r i 网可以精确的描述系统