（计算机应用技术专业论文）petri网仿真平台的研究与实现.pdf

摘要 p e t r i 网是对具有并发、同步、异步、冲突、资源共享以及不确定性等特点的离散事件 系统进行建模分析的有效工具。随着现实中系统规模的不断增大，作为支持p e t r i 网可视化 建模与仿真分析的计算机辅助软件就显得十分重要，它不仅可以大大简化建模过程，而且还 能显著提高模型分析的可靠性和有效性。 本文详细讨论了p e t r i 网的基本概念、基本性质、主要的分析方法以及主要的扩展形式， 并在此基础上，研究和开发了一个较为通用的p e t r i 网仿真平台( p n s p ) ，为常用的p e t r i 网 模型提供可视化建模和辅助分析。本文的主要工作包括以下几方面： ( 1 ) 将时间、子网变迁引入p e t r i 网仿真，增强模型的描述能力，简化模型规模，使 得工具更适合于对复杂系统进行建模仿真。 ( 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 网) 提供可视化建模和仿真分析功能，大大拓展了工具的适用性。 ( 3 ) 提供常用的辅助分析：基于不变量的辅助分析和基于可达树的辅助分析，实现了 不变量的求解和可达树的构造。 ( 4 ) 支持p n m l 的语法规范，便于与不同的p e t r i 网工具进行数据交流。 本文在第三章和第四章详细论述了p e t r i 网仿真平台的设计方案、关键技术和具体实 现，并分别就辅助分析功能和模型仿真功能给出了具体的应用实例，有效说明了工具的应用 价值。 关键字：p e t r i 网，建模，仿真，子网变迁。不变量，可达树 a b s t r a c t p e t r in e ti sa ne f f e c t i v em o d e la n da n a l y s i st o o lf o rd i s c r e t ee v e n ts y s t e mw i t ht h e c h a r a c t e r i s t i c s ，s u c ha sc o n c u r r e n c y , a s y n c h r o n i s m ，c o l l i s i o n ，r e s o u r c es h a r i n ga n ds oo n s i n c e t h es c a l eo fs y s t e mb e c o m el 甜g e ra n dl a r g e rn o w a d a y s ，i ti s v e r yn e c e s s a r yt od e v e l o pa v i s u a l i z e dm o d e l i n ga n ds i m u l a t i o nc o m p u t e r - a i d e ds o f t w a r e ，w h i c hc a ng r e a t l ys i m p l i f yt h e p r o c e s so f m o d e l i n ga n di m p r o v et h er e l i a b i l i t ya n dv a l i d i t yo f m o d e l i n ga n da n a l y s i s t h i sp a p e rd i s s e r t a t e st h et h e o r i e s ，p r o p e r t i e s ，c h i e fa n a l y z i n gm e t h o d sa n dc h i e fe x p a n s i o n m o d e so fp e t r in e t s b a s e do nt h e s ec o n t e n t sr e f e r r e dt o ，ag e n e r a lp e t r in e ts i m u l a t i o n p l a t f o r m ( p n s p ) i se s t a b l i s h e d t h ef o l l o w i n g sa r et h em a i nr e s u l t sa c h i e v e di nt h i sd i s s e r t a t i o n ( 1 ) t i m ea n ds u b n e tt r a n s i t i o na r ei n t r o d u c e dt ot h es i m u l a t i o no fp e t r in e t s ，w h i c hc a n e n h a n c et h ed e s c r i p t i o nc a p a c i t ya n ds i m p l i f ys c a l eo fm o d e l sw h i c ha r es u i l a b l ef o rt h ec o m p l e x s y s t e mm o d e l i n ga n ds i m u l a t i o n ( 2 ) t h ef u n c t i o n so fv i s u a l i z e dm o d e l i n ga n ds i m u l a t i o nf o rc o m m o np e t r in e t s ( i n c l u d i n g b a s i cp e t r in e t ，t i m ep e t r in e t ，s t o c h a s t i cp e t r in e t ，a n dh i e r a r c h i c a lp e t r in e t ) a l ep r o v i d e d ，w h i c h g r e a t l ye x p a n dt h ea p p l i c a b i l i t yo ft h i st 0 0 1 ( 3 ) t h et w of u n c t i o n so fa s s i s t e da n a l y s i sa r ep r o v i d e d ：t h ea n a l y s i sb a s e do np - i n v a r i a n ta n d t - i n v a r i a n ta n dt h ea n a l y s i sb a s e do nr e a c h a b i l i t yt r e eo fp e t r in e t i n v a r i a n t sa n dr e a c h a b i l i t yt r e e w o u l db eg e n e r a t e da sar e s u l t ( 4 ) t h ep e t r in e tm a r k u pl a n g u a g ei ss u p p o r t e df o rs a v i n ga n dl o a d i n gm o d e l s 1 1 1 ed e s i g n k e yt e c h n o l o g i e sa n dr e a l i z a t i o no fp n s pa r ed i s s a t a t e di nc h a p t e ri i ia n d c h a p t e ri v 。f i n a l l y , t w oe x a m p l e sa r ei l l u m i n a t e dt os h o wt h ef u n c t i o n so fa s s i s t e da n l y s i sa n d m o d e ls i m u l a t i o n k e y w o r d s ：p e t r in e t ，m o d e l ，s i m u l a t i o n ，s u b n e tt r a n s i t i o n ，i n v a r i a n t ，r e a c h a b i l i t yt r e e h 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：午继l 日期：趔 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：瓣 导师签名：鱼兰厶一日 期：加留，j = 么 第一章绪论 1 1 选题背景 第一章绪论 随着社会的进步和科学技术的发展，人们面临的系统问题越来越复杂，系统分析的难度 越来越大。其典型的例子有大规模的计算机系统、各种生产特点的生产调度系统、交通管理 系统、军事指挥系统等。这类系统的共同特点就是存在大量的离散事件和对离散信息的处理， 由于系统的复杂性和离散事件之间各个因素错综复杂的相互作用，这类系统具有并发、同步、 异步、冲突、资源共享以及不确定性等特点。由于这些特点使得分析研究变得十分复杂，人 们尚难找到统一的数学方法进行系统建模和分析。目前已有的分析手段中，p e t d 网分析方 法能够较好的模拟过程的同步、异步、并发、冲突和资源共享等特征。因此，p e t r i 网逐步 成为研究大规模离散系统的有力工具。 p e t r i 网是德国学者c a r la d a mp e t r i 于1 9 6 2 年提出的一种网络图理论，具有图形化的直 观表达方式和一套严密的数学理论，适合于描述含并发性、异步性、分布式、非确定性系统 的结构【l 】。四十多年来，经过许多学者的共同努力，p e t r i 网理论得到不断地充实和完善，其 抽象和描述能力也不断的朝着横向纵向发展。它的纵向扩展表现为：从基本的条件摩件( c e ) 网，位置废迁( p r ) 网发展到谓词变迁网和着色网等高级网。它的横向扩展表现为：从无参 数的网，发展到时间p e t r i 网和随机p e t r i 网【2 1 。目前，p e t r i 网理论已发展成为一个比较完整 的体系，是分析具有并发、并行、异步、同步、资源共享、随机等特征系统的有力工具。作 为一种图形化的工具，p e t r i 网除了具有类似流程图、块图和网络图的直观描述功能之外， 还可以使用托肯( t o k e n ) 来模拟系统的动态行为和并发活动；作为一种数学化的工具，可以 用它建立系统的状态方程、关联矩阵、代数方程，或其它描述系统行为的数据模型p j 。与传 统的系统建模、分析和控制方法相比，p e t r i 网作为一种图形化和数学化的建模工具，能够 提供一个集成的建模、分析和控制环境，为系统的设计提供便利。 p e t r i 网是通过利用直观图形来描述和分析离散事件动态特性的建模工具，同时也可作 为对事件的发生过程进行模拟的工具。它是建立在严格的数学基础上的，可对模型进行分析、 验证和形式化，具有良好的离散事件处理模型构造能力，通过采用严格的数学方法，能够导 出系统的各种性质。 p e t r i 网的性质【4 】主要包括结构特性和行为特性，前者与网的初始标识无关，后者却依赖 于初始标识。我们可以通过关联矩阵的方法求得p 不变量和t - 不变量来研究网的结构特性； 而对于网的行为特性，则可以通过可达树和可达图来进行研究。 p e t r i 网在应用方面主要的缺点是它的复杂性问题，对于一些小型系统来说，基于p e t r i 网的建模分析有可能以手工方式完成，但是当被描述系统的状态变量数目增大时，就很难以 手工来完成。因此，作为支持p e t r i 网可视化建模与仿真分析的计算机辅助软件就显得十分重 要。计算机仿真分析工具是p e t r i 网系统研究必备的工作环境和应用基础，可以大大提高建模 分析的可靠性和工作效率。 1 2 国内外研究现状 对于应用基本p e t r i 网及其某些扩展形式( 随机p e t r i 网、着色p e t r i 网【5 1 等) 建立的系统 模型，当前国内外己经有一些专业的p e t r i 网软件对其进行了分析，比较著名的有有色p e t r i 东南大学硕士学位论文 网软件d e s i g n c p n 、随机p e t r i 网软件包s p n p 、确定与随机p e t r i 网软件包d s p n e x p r e s s ， 等等。 ( 1 ) d e s i g n c p n 。d e s i g n c p n 最早是在1 9 8 9 年由美国的m e t a 软件公司与丹麦 a a r h u s 大学的有色p e t r i 网研究组合作开发的。该软件专门针对有色p e t r i 网而 设计，提供了一个集成的环境，支持有色p e t r i 网从建模到模拟运行以及性能分 析的全过程【6 j 。 ( 2 ) s p n p 。s p n p 是由美国杜克大学的t r i v e d i 教授所领导的研究小组研究和开发的 7 j ，s p n p 的使用界面是c 语言形式的s p n 描述语言，它是c 语言的一个扩充， 附加了s p i n 模型的描述和性能参数测试函数，它所测试的性能参数包括两类： 稳态期望值和瞬态分析值。s p n p 的运行平台为u n i x 操作系统。一些重要的 s p n 模型特性，如标识相关的实施速率和概率、变迁实施条件函数、变迁有限 级、可变弧、禁止弧和弧权等都可在s p n p 中规定和应用，这些特性的应用可 为复杂系统的模型带来方便。 ( 3 ) d s p n e x p r e s s 。d s p n e x p r e s s 是由德国多特蒙德大学的l i n d e m a n n 教授研究和开 发的【引，运行的平台也是u n i x 操作系统。它是确定与随机p e t r i 网的数值求解 软件，可以计算d s p n 所对应嵌入马尔可夫链的状态转换概率和换算因子。实 现了确定时间变迁与标识相关的实施延时。 但这些现成的仿真工具和软件包多数是收费的而且是基于u n i x 或l i n u x 平台的，不能 有效满足国内的实际需要。另外，它们大多是针对某类具体的p e t r i 网描述形式，很难满足 针对具体应用环境而经进一步扩展的模型仿真，而对于这些经进一步扩展的模型仿真需编程 实现。 在国内，一些大学和科研单位基于研究的需要也开发了一些运行在w i n d o w s 平台的基 本p e t r i 网的分析工具，如中国科学院自动化所f 9 】、清华大学1 0 】、华中科技大学、北京化 工大学【1 2 】和南京理工大学【1 3 】等都分别开发了各自的基于p e t r i 网方法的辅助分析工具。比较 有代表性的有华中科技大学开发的g p n t 1 1 】。g p n t 系统是在w i n d o w s 环境下使用v i s u a l c + + 开发的一款图形化的p e t r i 网建模工具，作为一个计算机辅助设计和分析工具。它允许 用户在交互式的计算机图形方式下进行p e t r i 网的建立、删除、修改和存储，并通过对关联 矩阵的初等线性变换求解p e t r i 网的p 不变量和t - 不变量。g p n 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 网仿真平台， 为常用的p e t r i 网模型提供可视化建模和辅助分析，希望对国内p e t r i 网软件工具的发展有一 定的帮助。 1 3 本文的研究工作 本文的主要研究内容有： 1 将时间、子网变迁引入p e t r i 网仿真。 基本p e t r i 网有很强的描述能力，但对于描述实际系统来说能力还不够。为了更好地评 价动态系统的实际性能，人们在p e t r i 网中引入时间参数【1 4 】。在p e t r i 网中引入时间的方式有 很多。p e t r i 网是由库所、变迁和有向弧组成的，所以，时间可以附加在变迁、库所、托肯 和有向弧上。具体采用何种方式，取决于被描述系统的应用背景和建模要求。一般来说，常 用的将时间引入p e t r i 网有两种方式：一种是库所( p l a c e ) 与时间结合，称为p t i m e dp n ，它 2 第一章绪论 的主要优势在于可以使得传统意义上的变迁的实施规则不变，即变迁的可实施和实施都是瞬 间完成的。另一种是变迁( t r a n s i t i o n ) 与时间有关，称为t - t i m e dp i n ，因为在大多数情况下， 用变迁表示一个任务，那么将时间延迟与变迁联系起来就是一件很自然的事情：变迁表示任 务，任务的执行需要花费时间。 随着系统功能的增强和规模的扩大，对系统的扁平建模将会带来网模型规模过大的问 题，这将使得网模型难以理解和分析。因此，本文在p e t r i 网仿真平台的实现中引入子网变 迁，使得用户可以实现分层建模，大大简化了模型规模，从而使得该仿真工具更适合于对复 杂系统进行建模仿真。 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 网应用的，具有 一定的局限性。本文在综合分析了国内的各种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 网) 提供可视化建模和辅助分析，大大扩展了工具的适用范围。 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 ) 易用的、友好的图形界面。使得用户可以很方便的对模型进行编辑、修改和保存。 ( 2 ) 动态仿真：支持对p e t r i 网模型状态变化的动态仿真，使用户可以更直观的分析网 状态的变化过程。 ( 3 ) 基于不变量的辅助分析：实现对p 不变量和t - 不变量的求解。不变量是网系统的 结构特征，它与初始标识无关。p e t r i 网的不变量对于分析系统的性能如有界性、活性和周 期性等具有重要意义。 ( 4 ) 基于可达树的辅助分析：通过构造p e t r i 网模型的可达树对p e t r i 网模型的许多重 要性质，如有界性、活性和死锁等做出分析。 4 支持p n m 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 网类型的多样性以及各种p e t r i 网工具产生的文件格式之 间的差异使得这个看似简单的问题一直得不到一个很好的解决。2 0 0 0 年在p e t r i 网应用和理 论国际会议上开始了p e t r i 网标准化的努力，提出了几种基于x m l 交换格式的建议，p n m l 就是其中的方案之一【”】。p n m l 支持任何类型的p e t r i 网，主要用来解决由于不同的p e t r i 网类型而导致的数据交流问题【l6 1 。本文所开发的p e t r i 网软件工具将p e t r i 网模型以符合 p n m l 语法规范的x m l 文件格式保存到物理磁盘上，便于与不同的p e t r i 网工具进行数据 交流。对p n m l 语法规范的支持，使得任何支持p n m l 语法规范的p e t r i 网模型文件都可以 使用本软件工具进行分析，同理，本软件工具所产生的p e t r i 网模型文件也能被其它支持 p n m l 语法规范的p e t r i 网软件工具所分析。 1 4 本文的组织结构 本文由以下章节组成。本章主要介绍了论文的研究背景、研究现状、研究内容等。第二 3 东南大学硕士学位论文 章介绍p e t r i 网的基本概念，基本性质以及主要的p e t r i 网分析技术和扩展形式。第三章主要 介绍了p e t r i 网仿真平台和仿真策略的设计过程，以及在此过程中遇到的技术难题和相应的 解决方案。第四章讲述p e l r i 网仿真平台的具体实现，并分别就辅助分析功能和模型仿真功 能给出了具体的应用实例，有效说明了工具的应用价值。第五章是工作总结以及对后续工作 的展望。 4 第二章p e t r i 网概述 第二章p e t r i 网概述 p e t r i 网是一张有向图，图中包含两类节点：库所( p l a c e ) 和变迁( t r a n s i t i o n ) 【l 丌。库 所通常是用圆圈或者椭圆来表示，可以代表现实中的条件，缓存，服务，资源，队列等等。 变迁则用方框或者粗杠来表示，代表现实中的处理过程，算法或事件等。有向弧只能从库所 到变迁或者反方向。在本文中，从库所到变迁的有向弧称为该变迁的输入弧，而从变迁到库 所的有向弧称为该变迁的输出弧。 t o k e n ( 一般译作托肯) ，是p e t r i 网最重要的元素，我们通常用黑点来表示t o k e n ，它 只能出现在库所中，它的个数代表资源的个数。t o k e n 在库所间的移动是受到变迁的控制的。 在建立的模型中，各t o k e n 所处的位置被定义为系统的状态，这种状态代表实际系统的某一 种确定的状态，比如缓存中的数据，可用的服务数目，可用的资源数目，队列中的实体等等。 而从p e t r i 网的角度来看，这种t o k e n 在网中的布局被定义为p e t r i 网的标识，它代表的就是 实际系统的当前状态。下面，给出p e t r i 网的相关概念。 2 1 p e t r i 网的基本概念 定义2 1 满足下列条件的三元组n = ( p 丁，) 称为有向 网( d i r e c t e dn e t ) ，简称网( n c t ) 【l8 】【l9 l 。 ( 1 ) p u t ( 2 ) p n t = 西 ( 3 ) ，( p 丁) u ( 丁p ) ( 4 ) d o m ( f ) u c o d ( f ) = 尸u ? 其中 d o m ( f ) = xlj y ：( x ，j ，) f ) ， c o d ( f ) = 抄l3 x ：( x ，y ) f ) 分别为，的定义域和值域。 在p e t r i 网中，尸的元素称为库所( p l a c e ) ，用来表示系统的状态，库所可以容纳资源， 资源可以是原料、部件、产品、人员、工具、数据以及信息等一切与状态有关的元素( 用托 肯表示) ；t 的元素称为变迁( t r a n s i t i o n ) ，变迁的实施使系统的状态发生变化：f 的元素称 为弧( a r c ) ，用来表示库所与变迁之间的流关系，弧只能存在于库所与变迁之间而不能存在于 库所与库所或者变迁与变迁之间。 定义2 2 前集与后梨1 8 】 设n = ( 只t ，) 为一个网，对x p ur ，记 工= yl ( y ，x ) ，) x = p i ( 毛z ) ，) 称。x 为x 的前集，x 。为x 的后集。 下面来介绍基本p e t r i 网( 也称p l a c e t r a n s i t i o n 网，简称p t 网) 的定义： 带有m 个库所和n 个变迁的基本p e t r i 网可以用一个六元组来表示1 8 】【2 们。 定义2 3 六元组= ( p ，t ，f ，k w ，m ) 被称为一个p 厂r 网系统，当且仅当： 5 东南大学硕士学位论文 ( 1 ) ( 尸，t ，) 是一个网： k ：p j 0 称为容量函数； w ：f 一n 一 o ) 称为权函数； m ：p 专o 是的一个标识，满足条件v p p ：m ( p ) k ( p ) 。 ( 2 ) 满足下面变迁发生规则： 对t t ，t 在m 有发生权( f i r a b l e ) 的条件为 砌t ：m ( p ) w ( p ，) v p t ：m ( p ) + w ( t ，p ) k ( p ) t 在m 有发生权记作g t ，也说m 授权( e n a b l e s ) t 发生或者t 在m 受权( e i l a b l e d ) 发生。 若g t ，则t 在必可以发生，将标识时改为m 的后继( s u c c e s s o r ) m ，记为 g t m 7 。m 定义为：v p p ： 2 2p e t r i 网的基本性质 酆。t t 部t t 邬t a t 酆芒+ t u 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 网的基本性质墙】 2 1 3 1 2 2 。 ( 1 )可达性 可达性是研究任何系统动态特性的基础。 定义2 4 设= ( p ，t ，k w ，m ) 是一个p e t r i 网，如果存在t t ，使得g t m ，则 称m 为从m 直接可达的。如果存在变迁序列t 1 ，t ：，t t 和标识序列 膨l ，m 2 ，膨i ，使m t l m l 乞 m e 帆一l 厶 m k ，则称肘女是从膨可达的。 从m 可达的一切标识的集合记为足( 必) 。约定m r ( m ) 。 定义2 5 设= ( p ，t ，k w ，m o ) 为一个p e t r i 网，其中m o 是的初始标识。的可达 标识集r ( m 。) 定义为满足下面两个条件的最小集合： m o r ( m o ) 。 若m o 尺( m o ) ，且存在t t 使得m o i t m ，则m r ( m o ) 。 对于有界p e t r i 网，由于其可达标识集r ( m 。) 是一个有限集，因此可以以r ( m 。) 作为 顶点集，以标识之间的直接可达关系为弧集构成一个有向图。这种有向图称为p e t r i 网的可 达表示图睇引。 ( 2 )有界性和安全性 定义2 6 设= ( p ，t ，k w ，m o ) 为一个p e t r i 网，p p ，若存在正整数曰，使得 m r ( m 。) ：m ( p ) b ，则称库所p 为有界的，并称满足此条件的最小正整数曰为库所p 的界，记为曰( p ) 。即 6 。矿 以 ) ) 吖 力们矿p 以+ 肌肌力计 一 + p “ )i- 扩卅帅似 m m 矿 m = pv 膨 第二章p c t r i 网概述 b ( p ) = m i n 徊im r ( m o ) ：m ( p ) 曰) 当曰( p ) = 1 时，称库所p 为安全的。 定义2 7 设= ( p ，t ，k w ，m o ) 为一个p e t r i 网，如果每个p p 都是有界的，则称 为有界p e t r i 网。称 b ( ) = m a x b ( p ) ip p ) 为的界。当曰( ) = 1 时，称为安全的。 有界性( 安全性) 反映系统运行过程中对资源容量的需求。在实际系统的设计中，必须 使得网中的每个库所在任何状态下的托肯数小于库所的容量，这样才能保证系统的正常运 行。 ( 3 ) p 不变量和t - 不变量 不变量是( i n v a r i a n t ) 是网系统的结构特性，与初始标识无关。网系统中有p 不变量和t - 不变量。如果网系统中有一些库所，其中包含的托肯的总和在任何可达标识情况下均为常数， 也即系统不论发生什么事情，这些库所中的托肯总数不变，则这些库所就是系统的p 不变 量。如果网系统中有一些变迁，它们的发生会使它们的标识恢复到它们的开始状态，则这些 变迁就是系统的一个t 不变量【2 4 1 。 2 3p e t r i 网的分析技术 我们常常希望通过对模型进行适当的分析来掌握并控制实际系统。p e t r i 网的分析方法 主要有三种：基于可达树的分析方法、基于矩阵方程的分析方法和结构分析法【4 】【1 8 】【2 5 1 。 ( 1 ) 可达树法。可达树是最直观的一种方法，它是将p e t r i 网运行的所有可达状态用树 状形式表示出来。这样，死锁、有界性等性质很容易得到验证，一些不希望运行的状态也可 以在可达树上找到，并对其父节点的使能变迁加以控制，所以可以进行死锁分析与控制。这 种方法的不足之处是需要列举所有可达到的状态，存在状态空间爆炸的问题，所以它适合中 小型系统。 ( 2 ) 矩阵方程法。这个方法是用代数计算对网系统进行分析。通过关联矩阵和状态方 程可以计算网系统的p 不变量和t 不变量。t 不变量说明它对应的几个变迁发生后会使标 识恢复成它们开始发生时的状态，它反映了使状态回归的可能变迁序列，可用于研究周期性 等性能；p 不变量则反映了部分库所中托肯总量的一种加权守恒性，可用来研究互斥行为、 死锁分析和进行错误检测等【4 】。 定义2 8 关联矩阵 设= ( n ，m o ) ，其中，n = ( p ，t ，f ) 是一个纯网，即v x p u t ：x n x = 。 其中： p = p 1 ，p 2 ，p 。) t = 瓴，乞，乙) 以库所集尸为序标集的列向量阼p 寸z 叫做的p 向量，其中z 是整数集。 以变迁集z 为序标集的列向量阢丁jz 叫做的丁向量。 以p t 作序标的矩阵c ：p t z 叫做的关联矩阵，其矩阵元素 c ( p f ，t ，) = w ( t j , p f ) 一w ( p f ，t ，) ， ( 1 f m ，1 刀) 。 的p 向量x 被称做的一个p 不变量埘c r x = 0 ，其中c r 为c 的转置矩 阵。 7 东南大学硕士学位论文 的r 向量y 叫做的一个f 不变量i 行c xy = 0 。 定义2 9 状态方程 设= ( ，m o ) ，其中，n = ( p 丁，f ) 是一个纯网，a pv x p u 丁：。xn x = 。 其中，p = p l ，p 2 ，p 。) ，t = ，f 2 ，乙 ，c 为的关联矩阵。若m m o 且 m 。 口 m ，则存在n 维以t 为序标的非负整数向量u 使得 m = m o + c e u 其中口是把m 。变为m 的变迁序列，对于t ，t ，u ( ) 等于在a 中出现的次数， 上式称为p c t r i 网的状态方程，满足状态方程是一个标识可达的必要条件。 ( 3 ) 结构分析法。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 e t r i 网确定其化简或细 化规则。 2 4p e 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 网理论进行 充实和扩展，使其抽象和描述能力得到进一步的完善。它的扩展主要表现为：纵向上从基本 的条件事件( c e ) 网、库所变迁( p t ) 网发展到谓词变迁网、着色网和层次网等高级网；横 向上从无参数的网发展到时间p e t r i 网和随机p e t r i 网【2 】。本文主要研究了时间p e t r i 网、随机 p e t r i 网和层次p e t r i 网。 ( 1 )时间p e l r i 网 时间p e t r i 网一般指对p e t r i 网中每一个变迁引入一个延迟量，根据延迟量是一个固定值 和区间值又分为固定延迟时间网和不固定延迟时间网【2 6 1 1 2 7 1 。 定义2 1 0 = ( p ，t ，k ，w ，m o ，f ) 称为固定延迟时间网，当且仅当： ( 尸丁，k ，m 。) 为一个基本p e t r i 网。 t - ：t - - - ) r + 是变迁到确定时间延迟的映射，r + 为非负实数集合。 定义2 1 1 = ( 尸，t ，k ，w ，m o ，f ) 称为不固定延迟时间网，当且仅当： ( 尸，丁，k ，形，m 。) 为一个基本p e t r i 网。 f ：t - - ) 彳p 是变迁到不确定时间延迟的映射，其中么尸的元素为递增非负实数对 a p2 【口m j n ，口瑚xj ， us 口m 缸s 口眦。 在这种时间网中，对每个t t ，均有一个a p a p 与之对应，这意味着t 的启动要考 虑时间。假设f 在时钟为u 时有效，则它可在区间【u + 口岫，u + 口一】内执行。 ( 2 )随机p e t r i 网【2 8 t 2 9 1 【3 0 】 在随机p e t r i 网( s t o c h a s t i cp e t r i n e t s ，简称s p n ) 中，引入时间参数的方法是在每个变 8 第二章p e t r i 网概述 迁的有效和实施之间联系一个随机延迟时间。对随机p e t r i 网的性能分析大多建立在其状态 空间与马尔可夫链( m a r k o vc h a i n ，简称m c ) 同构的基础上的。 s p n 是p 厂rp e t r i 网的扩充，每个变迁关联一个实施速率，它表示在有效条件下，单位 时间内平均实施的次数，即次数单位时间。实施速率是托肯( t o k e n ) 的函数，如一个变迁表 示多个任务或进程并发执行时，变迁的平均实施速率与任务个数( 或进程个数) 成正比。平 均实施速率的倒数称为变迁的实施延时或平均服务时间。p tp e t r i 网可以看成是s p n 的特 例，即当其所有变迁的实施延时为零时。 ( 3 )层次p e t r i 网【副【j u 为了解决复杂大型系统扁平模型描述所带来的网规模过大而难以理解和分析的问题，层 次p e t r i 网定义了子网变迁，通过子网变迁可以实现分层建模。 定义2 1 2 = ( 只丁，足，形，坂，f ) 为层次p e t f i 网，其中： p = ( 只，e ) 为一组库所，只为普通库所，e 为引用库所，引用库所只在子网变迁中 使用，是对父网某一普通库所的引用。t = ( l ，正) 为一组变迁，z 为普通变迁，t 为子网 变迁，在子网变迁中，必须以引用库所作为子网的输入库所和输出库所，通过引用结点实现 从子网变迁的输入偷出库所( 父网中) 到子网的输a 输出库所( 子网中) 的映射。k 、矿、 m o 同普通p e t r i 网，r 为普通变迁到时间延迟的映射。 9 东南大学硕士学位论文 第三章p e t ri 网仿真平台的设计 p e t 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 网辅助工具之后，研 究和开发了p e t r i 网仿真平台，为常用的p e t r i 网模型提供可视化建模和辅助分析，希望对国 内p e t r i 网软件工具的发展有一定的帮助。 3 1 设计思路 系统模型的建立和分析是一项非常复杂的工作，它既要求建模人员的创造能力和分析能 力，同时也要求有一个良好的辅助支持工具。开发p e t r i 网仿真平台的主要目的就是提供一 个计算机辅助工具，使用户能够以简单直观的方式，建立分析常用的p e t r i 网模型。 理想情况下，一个良好的图形化建模仿真工具应该达到以下标准： ( 1 ) 具备良好的易用性； ( 2 ) 能够提高建模效率； ( 3 )减少模型错误； ( 4 )建模工具本身应该很直观； ( 5 ) 提供多种分析功能； ( 6 )提供多种类型的建模： ( 7 )易于和其它的p e t r i 网模型工具交流。 基于以上标准，本文基于实际的研究和应用需要，在综合分析了国内的各种p e t r i 网辅 助工具之后，研究和开发了p e t r i 网仿真平台( p n s p ) 。与现有的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 网应用面临着“状态空间爆炸”的问 题，因此，对p e l 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 n s p ) ，为常用的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 网) 提供可视化建模和辅助分析，大大扩展了工具的适用范围。 ( 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 网有两种方式【1 4 】【2 6 1 ：一种是库所( p l a c e ) 与时问结合，称为p - t i m e dp n ， 它的主要优势在于可以使得传统意义上的变迁的实施规则不变，即变迁的可实施和实施都是 1 0 第三章p e t r i 网仿真平台的设计 瞬间完成的；另一种是变迁( t r a n s i t i o n ) 与时间有关，称为t - t i m e dp n ，因为在大多数情况下， 用变迁表示一个任务，那么将时间延迟与变迁联系起来就是一件很自然的事情：变迁表示任 务，任务的执行需要花费时间。 随着系统功能的增强和规模的扩大，对系统的扁平建模将会带来网模型规模过大的问 题，这将使得网模型难以理解和分析。因此，本文在p e t r i 网仿真平台的实现中引入子网变 迁，使得用户可以实现分层建模，大大简化了模型规模，从而使得该仿真工具更适合于对复 杂系统进行建模仿真。 ( 3 ) 提供多种分析功能。 当前的一些p e t r