（计算机应用技术专业论文）petri网的仿真软件的研究.pdf

r e s e a r c ha n dd e v e l o p m e n to fp e t r in e ts i m u l a t i o ns o f t w a r e a nf e n g m e i at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g m c o m p u t e rs c i e n c e t e c h n o l o g y m c h a n g s h au n i v e r s i t yo fs c i e n c e t e c h n o l o g y s u p e r v i s o r p r o f e s s o ry u ex i a o b o m a r c h 2 0 11 长沙理工大学 学位论文原创性声明 本人郑重声明 所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果 除了文中特别加以标注引用的内容外 本论文不包含任 何其他个人或集体已经发表或撰写的成果作品 对本文的研究做出重要贡 献的个人和集体 均已在文中以明确方式标明 本人完全意识到本声明的 法律后果由本人承担 作者签名 噎良梅日期 知f 年岁月z o 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版 允许论文 被查阅和借阅 本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索 可以采用影印 缩印或扫描等复制手段保存 和汇编本学位论文 本学位论文属于 1 保密口 在年解密后适用本授权书 2 不保密团 请在以上相应方框内打 切叶日期 砷i f 年 月矶日 e l 期 矽 年j 一月矿日 叭 梅 圳 风 扩 蝻凶 名 名 凳 登 者 师 作 导 摘要 c a r la d a mp e t r i 于1 9 6 2 年在他的博士论文 k o m m u np c a t i o nm i t a u t o m a t i o n 中 正式提出了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 l a b2 0 的基础 上实现了一个功能更加完善的p e t r i 网仿真工具 p e t r i l a b3 o 本文以众多分析技术及p e t r i 网的基本理论为依据 采用m a t l a b 和v c 混合编程 利用面向对象的技术 通过软件再工程模式对谭丹等开发的p e t r i 网 仿真软件p e t r i l a b2 0 进行了软件再造 本文所实现的p e t r i 网仿真软件p e t r i l a b3 0 通过添加带抑制弧的p e t r i 网系统的仿真 增强了工具的模拟仿真能力 该仿真 软件目前适用于e n 系统 p 厂r 系统 自控网系统 包括带约束弧和不带约束弧 的两种自控网 以及带抑制弧的p e t r i 系统 同时 为了实现对复杂系统的模拟 分析功能 本文对p e t r i 网的化简规则进行了深入研究 并在软件中实现了比较 完善的化简功能 最后 经过对原型系统进行全面的测试及运行调试 证明了系 统运行稳定可靠 分析结果准确无误且仿真方便快捷 与同类仿真软件相比 该 文所实现的p e t r i 网仿真软忡e t r i l a b3 0 功能更为完善 关键词 p e t r i 网 抑制弧 化简规则 仿真 一 a b s t r a c t t h i st h e o r yi sr a i s e db yc a r la d a mp e t r ii nh i sd o c t o r a lt h e s i s k o m m u np c a f i o n m i ta u t o m a t i o n i n19 6 2 t h ep e t r in e ti sam a t h e m a t i c a lm o d e l i n gt o o lt od e s c r i b e d i s c r e t e d i s t r i b u t e ds y s t e m s c u r r e n t l y t h e r ea r em a n yr e s e a r c h e r sa r o u n dt h ew o r l d f o c u so nt h ep e t r in e tr e s e a r c h a n dm a n yf o c u so ni nt h ep e t r in e tm o d e l i n gt o o lf o r s o f t w a r er e s e a r c h t h et h e s i sc o m m e n c eo np r a c t i c a lo fp e t r in e t s t u d i e dt h ea n a l y s i s a n ds i m p l i f i c a t i o nt e c h n i q u e si nd e t a i l a n a l y z e dt h ee q u i v a l e n c eb e t w e e no r i g i n a l d i a g r a m sa n ds i m p l i f i e dd i a g r a m s f i n a l l y a c h i e v e dp e t r i l a b3 0w h i c hi saf u n c t i o n a l p e t r in e ts i m u l a t i o nt 0 0 1b a s e do np e t r i l a b2 0 t h i st h e s i sr e b u i l dp e t r i l a b2 0w h i c hi sap e t r in e ts i m u l a t i o ns o t t w a r e d e p v e l o p e db yt a nd a n p r o g r a m e di nm a t l a ba n dv c w i t ho b j e c t o r i e n t e d p r o g r a m m i n g p e t r i l a b3 0e n h a n c e ds i m u l a t i o nf u n c t i o nb ya d d i n gs i m u l a t i o no f t h e p e t r in e t 嘶t hi n h i b i t o ra r c t h es o f t w a r ei sc u r r e n t l ya v a i l a b l ef o re ns y s t e m s p 厂r s y s t e m t i m ep e t dn e t s a u t o m a t i cc o n t r o ln e t w o r ks y s t e m s i n c l u d i n g 谢t 1 1c o n s t r a i n t s a n dw i t h o u tc o n s t r a i n t sa r c a l ec o n t r o l l e dn e t w o r k s i no r d e rt os i m u l a t et h ep e t r in e t w i t ha r cs u p p r e s s i o na n da n l y z ec o m p l e xs i m u l a t i o ns y s t e m t h et h e s i sr e s e a r c h e d d e e p l yo ns i m p l i f i c a t i o nr u l e s 衍ma r c t h i st h e s i sd e f i n e da n dp r o o f e ds i m p l i c a t i o n r u l e sw i t ha r cs u p p r e s s i o n a f t e rac o m p r e h e n s i v et e s t i n ga n dd e b u g g i n g t h es y s t e m i sp r o v e dt ob es t a b l e r e l i a b l e c o n v i n i e n t e f f i c i e n ta n da c c u r a t e t h i sp e t r in e t s i m u l a t i o ns o f t w a r ep e t r i l a b3 0i sm o r ec o m p l e t ec o m p a r e dw i t hs i m i l a rp r o d u c t s k e yw o r d s p e t r in e t s i n h i b i t o ra r c s i m p l i f i c a t i o nr u l e s s i m u l a t i o n 目录 摘要 i a b s t r a c t i i 第一章绪论 1 1 1问题的提出 1 1 2国内外的研究现状 2 1 3 研究的目的及意义 一3 1 4研究方法 4 1 5创新点 5 1 6本论文的结构安排 6 第二章p e t d 网的基本理论及相关技术的研究 7 2 1 p e t r i 网基本定义及相关定理 7 2 1 1 p e t r i 网的定义 7 2 1 2 变迁的发生条件和后果 9 2 1 3p e t r i 网的性质 9 2 1 4p e t r i 网的分类 1 0 2 1 5p e t d 网的分析技术 1 2 2 2 p e t r i 网的化简技术及迸一步研究 13 2 2 1不带抑制弧的p e t r i 网的化简技术 1 3 2 2 2带抑制弧的p e t r i 网的化简技术 2 0 2 3 面向对象的软件再工程 3 3 2 3 1软件再工程 3 4 2 3 2 反向工程 3 4 2 3 3软件再工程模式 3 5 2 4 本章小结 3 6 第三章需求分析与系统功能设计及模型分析 3 7 3 1需求分析 3 7 3 2p e t r i l a b3 0 系统的功能设计 4 1 3 2 1对p e t d l a b2 0 原有功能的修改 4 1 3 2 2 对带抑制弧的p e t r i 网系统建模 4 1 3 2 3系统模型的构成 4 8 3 2 4 系统模型的运行 4 9 3 2 5 p 厂r 网的化简模块设计 5 4 3 2 6带抑制弧的p e t r i 网化简模块设计 5 7 3 3 本章小结 5 8 第四章系统模型及分析算法的设计 5 9 4 1系统模型设计 5 9 4 1 1 m f c 简介 5 9 4 1 2系统模型构建 6 0 4 2重点特性的算法设计 6 2 4 3本章小结 6 6 第五章建模软件的仿真与测试 6 7 5 1建模软件的实验 6 7 5 2与其它p e t r i 网仿真软件的对比 7 2 5 3测试与维护 7 3 5 4本章小结 7 4 第六章结论与展望 7 5 6 1 总结 7 5 6 2进一步的工作及展望 7 5 参考文献 7 6 附录 攻读学位期间发表论文目录 81 长沙理耿学硕撇 第一章绪论 第一章绪论 c a r la d a mp e t r i 于1 9 6 2 年在他的博士论文 k o m m u np c a t i o nm i t a u t o m a t i o n 中 正式提出了p c t r i 网论 p e t r i 网经过几十年的充实和发展 已推广到多个领域并得到广泛应用 1 1 近些年 随着p e t r i 技术的广泛应用 p c t r i 网仿真软件也应运而生 本章从发展的角度出发 首先简要介绍论文所提出的问 题 再介绍p c t r i 网仿真软件的研究现状 进一步又介绍研究p c t r i 网仿真软件的 目的和意义以及研究方法 最后 通过与以往的p c t r i 网仿真软件做对比 较详 细的阐述本课题的创新点所在之处 1 1 问题的提出 所谓的系统是具有特定功能的一个有机整体 它是由一些相互联系且 相互制约的若干部分组成 任何一个系统都取决于三要素即实体 活动 属性 该三要素在某一时刻所呈现的形式称为系统的一个状态 由于系统总是处于不断 演变的过程中 所以在不同的时刻 系统所处状态也可能有所不同 但是通常存 在许多要素导致直接在真实系统上做实验是行不通的 所以 系统仿真成为研究 系统的必要手段 其基本方法是建立真实系统所对应的结构模型与量化模 型 并将其转化为适合在计算机上编程实现的仿真模型 然后 再针对仿 真模型进行实验分析 系统仿真可较准确且真实地描述系统的运行 演变 发展的过程 系统仿真按照系统模型特性来分可分成连续型系统仿真 离散型系统仿真和 混合型系统仿真三大类 1 1 连续型系统是指随着时间变化系统状态连续发生变化 的系统 而离散事件系统只能在离散的时间点上随机发生变化 且离散时间点是 不确定的 即离散型系统状态变化由随机事件驱动 混合型系统兼备离散型系统 和连续型系统的特征 任何一个离散动态系统都具有静态部分和动态部分冈 所 谓的基于u m l 和p c t r i 网的层次建模分析方法也就是将一个系统的静态部分采用 u m l 来描述而动态部分借助p e t r i 网来描述 通过两者有效结合来描述系统的整 个组织结构以及其子系统之间的连接关系包括消息传递 同步 资源共享等 2 虽然u m l 是功能强大的图形化建模语言 但它有自身的缺陷即缺乏精确的语义 第1 页 共8 l 页 长沙理工大学硕上论文第一章绪论 描述 因此 u m l 形式化研究一直是关注的焦点 3 另外 p e t r i 网不仅具有坚实 的数学基础 而且具有直观的图形表示的特性 目前 p e t f i 网已存在许多较成熟 的分析方法可以用来直接分析模型的某些特性 3 1 p e t r i 网是适合d e s 即离散事件系统建模和仿真的有效工具之一 4 离散事 件系统仿真主要包括实体 事件 活动 进程等基本概念 实体又细分为永久实 体和临时实体 永久实体是在系统中永久存在的实体 而临时实体在系统中只在 一个时间段内存在 事件用于表示引起离散事件系统状态变化的行为 活动用来 表示不同事件之间转换的过程 进程是由若干个有序活动及事件组成 在基于 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 f i 网模型 模型的仿真运行 得出仿真结果等都需要借助p e t r i 网仿真软件来实现 随着p e t r i 网技术的广泛应用 p e t r i 网仿真软件也应运而生 1 e e e 把p e t r i 网仿真软件的研究和实现纳入了自身的知识体系 5 但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 在复杂系统中的应用中经常 会遇到 空间爆炸 问题 通过分析等价化简图的某些特性从而达到分析原网的 某些特性 是解决复杂系统模型性能分析的一种有效途径 虽然p e t r i 具有大量 的较成熟的分析技术 但是对于大而复杂的系统 根据p e t r i 网基本理论的定理 及公式仅仅依靠手工计算是很不现实的 因此 一个兼顾模型编辑 仿真 模型 分析的p e t r i 网仿真软件是非常必要的 1 2 国内外的研究现状 p e t r i 网仿真软件的开发一直是国内外研究者所关注的焦点 6 1 目前 国外已 有一些相对成熟的p e t r i 网仿真软件 且大部分用于商业用途 但国内的p e t r i 网 仿真软件功能比较简单 一般仅适用于计算机教学和实验用 暂无做商业用途的 第2 页 共8 l 页 长沙理工 撇 第一章绪论 国外对p e t r i 网仿真研究的较多且比较深入 目前 国外已经研究出了一些 较实用的软件原型 例如 德国的r a i n e rd r a t h 博士为商业目的而开发了v i s u a l o b j e c tn e t 7 德国的h e n r y ka n s c h u e t z 为科研目的而开发了i i p s i m s l 美国的 r i c h a r ds c o t tb r i n k 在其硕士论文 ap e t r in e t d e s i g ns i m u l a t i o na n dv e r i f i c a t i o n t 0 0 1 中实现了一种p e t r i 网建模软件p e t r i t 0 0 1 1 9 其它的p e t r i 网仿真软件还有 s e d i t 1 0 1 p n s 1 1 1 p e t r in e ts i m u l a t o r 1 2 1 等等 国外相对比较成熟的p e t r i 网仿真 软件有p i p e 2 5 v i s u a lo b j e c tn e t h 着色p e t r i 网软件d e s i g n c p n 等 它们大 都有可视化界面 可移植性较好的特点 p i p e 2 5 是基于j a v a 平台的p e t r i 网模 拟软件 p i p e 2 5 所建模型的库所属性框里有 c a p a c i t y 一栏 是稀有的设置 库所容量的成熟软件 v i s u a lo b j e c tn e t 是德国伊尔默瑙工业大学研制开发的 可视化通用交互集成仿真环境 1 3 d e s i g r g c p n 最早于1 9 8 9 年由m e t a 软件公司 与a a l h u s 大学j e n s e n 等人组成的c p n 研究小组合作开发的 1 2 1 该软件是特意针 对着色p e t r i 网而开发设计 支持着色p e t r i 网的建模 仿真 特性分析等 国内也有一些学者对p h i 仿真软件进行了研究 例如 中山大学的宋咏军和 朱思铭等人研究开发的p n s s 仿真系统 长沙理工大学的蔡志林等开发的p e t r i l a b 1 0 仿真工具 长沙理工大学的谭丹等开发的p e t f i l a b2 0 仿真工具等 其中 国 内中山大学的宋咏军和朱思铭等人设计开发的p n s s 仿真系统是国内p e t r i 网计 算机软件包功能比较全面的 具有对时间p e t r i 网的编辑 分析 仿真运行等功 能 还有长沙理工大学的蔡志林等开发的p e t r i l a b1 0 工具也提供了模型编辑 仿真 模型存储等功能 另外 长沙理工大学的谭丹等开发的p e t r i l a b2 0 工具 提供了静态分析 动态分析 生成 化简等功能 本课题在谭丹的p e t r i l a b2 0 研究开发的基础上 对其进行软件再工程 1 3 研究的目的及意义 本课题借鉴了蔡志林的p e t r i l a b1 0 面向对象的多层系统模型以及各个分析 模块的功能 并参照了谭丹的p e t r i l a b2 0 静态分析功能 动态分析功能 化简 功能等 目的在于 1 扩展p e t r i l a b2 0 的应用范围 比如 实现了带抑制弧的p e t r i 网系统的仿 真功能 同时 希望对p e t r i 网的理论研究将起到一定的作用 第3 页 共8 l 页 长沙理工大学硕撇第一章绪论 2 完善p e t r i l a b2 0 的功能 可实现性是p e t r i 网这个系统建模工具的价值所 在 所以本课题从p e t r i 网的实用性着手 为了解决现实问题 便于分析复杂系 统 提供了等价化简功能 通过分析该化简模型 解决了 空间爆炸 问题 这 样才具有更大的实用价值 希望本课题提供的p e t r i l a b3 0 对p e t r i 网仿真软件的 研究起到一定的推动作用 本课题对p e t r i 网仿真软件的研究与开发 在理论上和应用上有如下价值 1 本课题以p e t d 网基本理论为基础 除了p e t r i l a b2 0 中原有的基本网 库所 变迁网 自控网系统 包括带约束弧的和不带约束弧的两种自控网系统 以 外 还提供了带抑制弧的p e t r i 网 这是p e t r i 网仿真软件p e t f i l a b2 0 中没有实现 的 所以本课题的研究有比较重要的实用价值 2 运用面向对象的思想 采用众多的p e t r i 网分析技术 另外 本课题又重 点对等价化简的分析方法进行了较深入的研究 对这几种不同类型的网提供通用 的分析技术和较完善的化简功能 同时还可针对复杂系统进行等价化简 通过分 析等价化简图的某些特性从而达到分析原网的某些特性 希望通过化简模型所得 到的分析结果对用户会有一定的参考价值 3 本课题着重对带抑制弧度的p e t r i 的等价化简规则进行了较深入的研究 在文中定义了八种不同的带抑制弧的p e t d 网化简规则 又证明了等价化简图的 活性与原图的活性是一致的 迄今为止对带抑制弧的p e t r i 网的结构性质进行判 定的文献很少见 所以本课题的研究有比较重要的理论价值 4 本文在开发仿真软件的整个过程中应用了软件再工程技术 该技术是基 于面向对象的 因此 该仿真软件也可进一步软件再造 1 4 研究方法 本课题主要的研究方法 以p e t r i 网的基本理论为基础 利用面向对象的软 件再工程技术 对p e t r i 网模型进行全面分析 确保分析结果与p e t r i 网的特性的 一致性及正确性 各个研究阶段采用的研究方法如下所示 1 引入了u m l 建模技术和面向对象技术 对带抑制弧的p e t r i 根据面向对 象的继承关系来建立其基本元素的对象模型 2 在对s 不变量 t 不变量 关联矩阵进行分析时 引入了m a t l a b 工 第4 页 共8 l 页 0 长沙理工大学硕上论文 第一章绪论 具中矩阵类以及对矩阵的操作 3 对可达标识树进行操作时 定义了一个可达标识树结构体 另外 在进 行系统的活性分析时需要构造可达标识树 需要采用递归技术对树结构进行遍历 等操作 4 对p e t r i 化简 针对带抑制弧的p e t r i 网和不带抑制弧的p e t r i 分别提出了 化简规则 尤其对带抑制弧的p e t d 网的化简规则进行了详细研究 为了确保化 简规则的正确性 在本文中针对有界性和活性的不变性分别采用了反证法进行了 证明 5 在系统的测试阶段 设计了大量测试用例来确保系统的准确性和安全性 1 5 创新点 本课题与以往的p e t r i 网仿真软件相对比 有以下创新点 1 本课题对带抑制弧的p e t r i 网系统进行了建模 分析和仿真 这是p e t r i l a b 2 0 工具中没有的功能 2 本课题对带抑制弧的p e t r i 网的化简技术进行了较深入的研究 总结并定 义了八种不同的带抑制弧的p e t r i 网化简规则 这八种化简规则确保了化简图的 活性和有界性依次与原图的活性和有界性是一致的 并在文中分别给予了证明 3 本课题提供了化简功能 p e t r i l a b3 0 与p e t r i l a b2 0 相比 虽然p e t r i l a b2 0 也提供了化简功能 但只采用了一种化简方法 且化简的同时没有保证化简模型 中的托肯数及流动方向与原图的托肯数及流动的 致性 本课题中采用了多种化 简规则 化简效果更好 且保证了化简模型中的托肯数目及流动方向和原图的托 肯数及流动分别是一致的 这是国内外所有p e t r i 仿真软件中没有实现的功能 4 本课题通过分析等价化简图的某些特性从而达到分析原网的某些特性 在p e t r i l a b2 0 中 为了安全起见 对化简图的特性没有设计分析功能 因此其 化简功能就失去了化简的根本意义 本课题就化简网与原网的等价性进行了深入 的研究 通过分析等价化简图的某些特性从而达到分析原网的某些特性 从根本 上真正解决了 空间爆炸 问题 这也是国内外所有p e t r i 网仿真软件中没有实 现的功能 5 本课题对p e t r i l a b2 0 存在的如下问题做了进一步的完善工作 第5 页 共8 l 页 硕 第一章绪论 在p e t r i l a b2 0 中 默认情况下 库所中均含有一个托肯 而实际建模时 往往只有少数库所中存在托肯 针对这一缺陷 在p e t r i l a b3 0 中进行了修改完 善 即默认情况下 库所中均无托肯 这样只需根据实际需要 添加托肯即可 在p e t r i l a b2 0 中 新建模型时 当选择一个模型是系统可以显示模型类 型 但若同时选择多个模型时 则模型类型消失 系统仅显示模型l 模型2 等 针对这一缺陷 在p e t r i l a b3 0 进行了修改完善 即选择多个模型时 仍能 显示模型类型 1 6 本论文的结构安排 第一章首先提出问题 然后从课题的研究现状 目的和意义及研究方法进 行简单的分析 最后较详细的阐述本课题的研究任务和创新点所在 第二章首先介绍了p e t r i 网的定义 性质 化简技术 然后针对不带抑制弧 的p e t f i 网的化简规则和带抑制弧的p e l r i 网的化简规则分别进行了深入的研究 最后引入了面向对象的软件再工程技术 本章节为以后的章节提供了坚实的理论 基础及依据 第三章首先明确p e t f i l a b3 0 的需求分析 然后使用面向对象的再工程技术 接着又实现了带抑制弧的p e t r i 网的建模及分析 最后针对化简模块进行详细的 分析并设计化简算法来实现化简功能 第四章首先介绍了关键技术 郴c 然后介绍了构建系统模型的关键 类 最后有针对性地描述了本系统的几个具体算法 第五章简单地介绍了建模软件的仿真与测试 并和其它p e t r i 网仿真软件进 行了对比 第六章总结与展望章节 回顾全文所做工作并基于相关问题进一步展望 第6 页 共8 1 页 长沙理工大学硕士论文 第二章p e t r i 网的基本理论及相关技术的研究 第二章p e t ri 网的基本理论及相关技术的研究 p e k i n 不仅具有直观 易用 易懂的优点 而且易于描述和分析并发现象 阐 但p e t r i 网有其自身的缺陷即容易遇到 状态空间爆炸 问题 针对这一问题 本 章也着重对化简技术进行较深入的分析研究 并在其前人的研究基础上 进一步 总结并提出了带抑制弧的化简规则 最后 针对面向对象的软件再工程技术作了 简单介绍 2 1p e t rj 网基本定义及相关定理 p e t r i 网适合于描述分布式系统的一种有力工具 它不仅能很好地描述系统 的结构特性 又能模拟系统运行的动态过程 这一节简单地介绍了p e t r i 网定义 变迁发生的条件和后果 p e t r i 的性质与分类以及p e t r i 网的分析技术 2 1 1p e t ri 网的定义 为了便于大家理解p e t r i 网定义 先了解下有向网的定义 定义2 1 有向网用三元组n 只t f 来表示 且满足有向网的充分必要条件如 下所示 pr t 尸ut f p t u t x p d o m f u c o d f p u t 其中 p 的元素称为库所 t 的元素称为变迁 f 是网n 的流关系 d o m f xl 砂 x y f 被定义为有向弧f 的定义域 c o d f yik x y f 被定义为有向弧f 的值域 第7 页 共8 1 页 长沙理工大学硕士论文 第二章p e t r i 网的基本理论及相关技术的研究 i 肘 s 1 s 曰 一 f m s 膨 5 1 s 一广 im s o t h e r s 第8 页 共8 l 页 长沙理工大学硕士论文第二章p e t r i 网的摹本理论及相关技术的研究 2 1 2变迁的发生条件和后果 上一节已经给出了网系统的静态特征如系统结构 资源等 这小节定义下变 迁发生的条件和后果 网系统的动态规律称为变迁规则 1 5 其实 变迁和现代 操作系统概念中的 线程 具有类似的性质 1 6 也 定义2 6 变迁具有触发权的条件 假设m 为网系统 p 丁 f k 职眠 的任一标识 vf t t 在m 有触发权则要满足以下条件 v p f m p w p t v p e t m p w t p k p t 在m 具有触发权记作m 伊 换句话说 t 在m 受权发生或m 授权t 发生 定义2 7 触发变迁的后果 若m 胗 则t 在m 可以被触发 将标识m 转换为m 的后继m m 的定义 是 对任何p p m p m p w p 力都 t t m p 形o p 都 f r m p w p r 形 f p 都 t f t m p 都舞 t m 为m 的后继可记作m p m 2 1 3 p e t ri 网的性质 本节介绍了与本系统有关的p e t r i 网的性质 1 5 1 分别包括纯网 简单网 逆 网 对偶网 活系统 循环系统的定义 定义2 8 在网n p t f 中 若存在库所p p 和变迁f t 使得p tn t 那么当 f 触发时p 中既会得到拖肯同时又会失去拖肯 这种结构上的特征表明p 中的资 源对t 的触发所起的作用和化学反应中催化剂的作用相类似 如果不含有这种结 构的网则称为单纯网即纯网 另一方面 x p u 丁为有向网n 的元素集 若不 第9 页 共8 1 页 长沙理工大学硕士论文 第二章p t r i 网的基本理论及相关技术的研究 存在z y ex 当x y 时满足 x y 人弦 y 的结构的网称为简单网 定义2 9 n 尸 t f 1 称作n p t f 的逆网 n 叮 尸 尸 称作n p 丁 的对偶网 定义2 1 0 设n p t f 为有向网 n 为s 一网的充要条件为 v t t 1 tl l l l n 为s 图的充要条件为 v t t i 彳 it i 1 n 为t 网的充要条件为 跏 p i p i 1 i p l c 另外 r 的 传递闭包为一 ou 1u r 2u u 1 0 若v c c v e e l c c c r c r a c p 则n 是活的 若n 不仅是活的 而且满足v c c c c r 堆c 则n 是循环系统 2 1 4p e t ri 网的分类 p e t r i 网主要分为e n 系统 p t 系统和自控网 谓词 变迁网 时间p e t r i 网 着色网 随机p e t r i 网等各具特点的高级网系统 本文主要针对e n 系统 p t 系 统 两种不同的自控网系统 带抑制弧的p e t r i 网进行了研究 下面介绍本系统涉及的几种网系统的概念 定义2 1 2 基本网系统定义为一个四元组n b e f c 简称e n 系统 其中 b e f 是一个网 b 为条件集 e 为事件集 c 互b 为 的一个情 态 第1 0 页 共8 1 页 长沙理工大学硕士论文第二章p e t r i 网的基本理论及相关技术的研究 事件e e 在情态c 具有触发权的充分条件是 p c e nc 若事件e 在情态f 触发 产生一个新的情态f 记作f e c 则 cr c e u e 这里的变迁规则同p 厂r 系统中容量函数k 1 和权值函数w l 的 情况是完全相同的 定义2 1 3 在网系统 尸 乃bk 职m 中若k o o w 1 则这种系 统称为p e t r i 网的系统简称为胛网 定义2 1 4 在网系统 尸 乃b 豇职m 中若k 和w 为任意函数则这 种系统称为库所 变迁系统简称为p t 系统 定义2 1 5自控网系统 1 5 p t f w m o 为自控网系统的充要条件是 p t f 称为 的基网 w p xtu t x 尸一 o 1 2 一 u p r w x y 0 当且仅当 x y f 称作 的权函数 m o p o 1 2 称为 的初始标识 上述定义中每个p 元的容量均默认为无穷 自控网系统有两种表示方法 一种表示方法是以库所名为有向弧上的权值即 有向弧的权值为库所中的托肯数 另一种表示方法是使用约束弧 若w x y p 则从库所p 画一条以小圆圈为箭头的有向弧指向弧 x y 定义2 1 6 带抑制弧的p e t r i 网田1 用一个五元组 p 乃 m o 来定义 其中 p t f 是一个基网 i cp t 称作抑制弧集 m 是一个网的标识 i nf 对t t 如果 a vp p 0 t f m p 1 b v p p q t i m p 0 多 则t 在标识m 具有触发权 记作 m 胗 第1 1 页 共8 1 页 长沙理工大学硕士论文第二章p t r i 网的基本理论及相关技术的研究 若m e t 则变迁t 在m 可以发生 t 在标识m 下发生产生新的标识m i m p 一l 若 p r f a t p 聋f m q m p 1 若 p f 薯f a t p f l m 0 其他 从定义2 1 6 中的式 可知 如果在 中 从库所p 到变迁t 之间存在一条抑 制弧 则变迁t 在标识m 下可以被点燃的条件不仅要满足原型p e t r i 网的有关要 求 而且必须满足m 0 同时 式 说明抑制弧集i 在因变迁引起的标识变 化中 没有起到任何作用 2 1 5p e t ri 网的分析技术 目前 比较常用的p e t r i 网分析方法 1 1 有 不变量方法 可达树方法 可达 图方法 基于关联矩阵的动态分析等 针对上面所述的分析方法 下面再一一进 行介绍 不变量方法 该方法完全采用代数计算来处理系统 该方法具体又分为 不变量和弘不变量 s 不变量反映了若干资源的流动范围 弘不变量用来描 述一个循环子系统中变迁的循环触发的规律 可用于研究周期性 死锁分析 可达树方法和可达图 可达树是用树状结构把p e t r i 网运行的所有可达 标识表示出来 借助可达树可以查找到某些不希望运行的状态 然后 针对父节 点的使能变迁加以控制 则可避免死锁的出现 但该方法也有明显的缺陷 一是 对计算时间与存储空间的要求比较苛刻 二是活标识和死标识不能一目了然 而 可达图将所有的活结点与其对应的中间节点重叠 这样 可达图中的活标识和死 标识之间的区别可一目了然 基于关联矩阵的动态分析 基本p e t r i 网由库所p 变迁t 和有向弧f 三 类基本元素组成 其中 系统的状态用标记m 表示 m 是一列向量 其第i 个 元素是库所p i 所含有的托肯数 系统状态的动态过程等价于p e t r i 网的标识m 的 动态变化过程 除了以上常用的三种分析方法外 还存在一些重要概念 比如 变迁序列借 助系统中触发的变迁来考察系统韵行为 可达标识集可以表示系统可能的状态 定义2 1 7 出现序列与变迁序列 1 5 第1 2 页 共8 1 页 长沙理工大学硕士论文第二章p e t r i 网的基本理论及相关技术的研究 设 p t f w m o 为无冲撞的p t 一系统 盯 m o r l m l r 2 m 2 t m 为 的一个有限出现序列的充要条件是对所 有f f 1 2 万 m j l 阮 m 其中 m o 为 的初始标识 1 1 为盯的长度 仃 m o t i m 2 心 为 的一个无限出现序列的充要条件是对所有的 f f 1 2 以 m 州i t m 若盯 眠 鸩f m 厶心为系统的一个出现序列 则f t 2 厶称 为 的变迁序列 出现序列与变迁序列的长度均为n 定义2 1 8 可达标识集 1 5 p t f w m 的可达标识集是满足以下两个条件的最小集合 m o m o 若存在m m o t et 使m i t m 则m m o 2 2p e t ri 网的化简技术及进一步研究 p e t r i 网的应用过程中还存在一个尚未解决的重大问题即 状态空间爆炸 问题 2 3 为了解决这一问题 国内外很多学者进行了广泛而深入的研究并提出 了p e t r i 网的化简技术 化简规可以急剧地减小了状态空间 2 睨习 2 2 1 不带抑制弧的p e t ri 网的化简技术 网的化简技术最初是h a c k 提出 2 6 1 l i p t o n 提出了d 化简 并将它应用于并 行程序的化简 k w o n g 等人推广了l i p t o n 的化简思想 k o w a l k 和v a l k 又进一 步扩展了k w o n g 的思想 建立了化简定理 b e r t h e l o t 扩展了k w o n g 和k o w a l k 的工作 并建立了一种新的p e t r i 网化简及分解方法 m u r a t a 2 6 1 针对t 图又提出 了若干条化简规则 讨论了这些化简规则保持活性 安全性的不变性 i a c u nw a n g 阐述了p e t r i 网化简方法在时间p e t r i 网上的应用口 近十年来 国内对p e t r i 网的化简研究也越来越多 如蒋昌俊 许安国 林 第1 3 页 共8 l 页 长沙理工大学硕士论文第二章p e t r i 网的基本理论及相关技术的研究 闯 王培良等一批学者的研究成果 为研究p e t r i 网化简技术的学者开拓了思路 在文献 2 8 中 蒋昌俊教授推广了m u r a t a 的工作 提出了加权t 图的几种化简 运算 许安国教授和蒋昌俊教授在文献 2 9 还针对这几种化简规则的性质进行了 研究 林闯教授深入的研究了随机p e t r i 网的化简技术 如文献 3 0 提出的随机 p e t r i 网的时间数量级分解 压缩技术等 王培良教授在文献 3 1 中定义了网的并 分解的概念及其一系列重要特性 下面借助图2 1 一图2 8 分别定义了串联变迁 合并 串联库所合并 并联变迁化简 并联库所化简 消除自环路变迁 消除自 环路库所 抽象化简i 抽象化简i i 等八种化简规则 定义2 1 9 串联变迁合并 简称i l lc s t 设原p e t r i 网n i p l t i f i m i 化简后为n 2 p 2 1 2 f 2 m 2 若 n l n 2 中c s t 则原n 1 n 2 的结构分别如下 1 n 1 的结构 暑p p 1 存在两个变迁t v t l 并满足 p t t 是p 的唯一前集 p v v 是p 的唯一后集 v p p 是v 的唯一前集 t nv 西 t 和v 没有公共的后集 2 n 2 的结构 存在一个变迁u e t 2 t l 并满足 p 2 p l 一 p 1 2 t 1 t v u f f t n p 2x t 2 u 1 2x p 2 uct x u u u t uv p v x e p 2 l g 毗 等 为了便于理解串联变迁合并的定义 下面引入一个串联变迁合并的简单 例子 如图2 1 所示 第1 4 页 共8 1 页 图2 1 串联耍迁合开 定义2 2 0 串联库所合并 简称巾c s p 设原p e t r i 网n l p l t l f l m 1 化简后为n 2 p 2 t 2 f 2 m 2 若 n 1 n 2 巾c s p 则n l n 2 的结构分别如下 1 原网n l 结构 存在两个库所r v e p l j t t l 并满足 t r r 是t 的唯一前集 tt v v 是t 的唯一后集 r t t 是r 的唯一后集 tr n v r 的前集和v 的前集交集为空 2 网1 1 2 结构 p 2 p l r v u u t 2 t l t f 2 口l n p 2 t 2 u t 2x p 2 u r u v t u u u v v x 钮 2 嚣m 为了便于理解串联库所合并的定义 f i 面弓 i a 一个串联库所合并的简单 例子 如图2 2 所示 图2 2 串联库所合并 第1 5 页 共8 l 页 长沙理工大学硕士论文第二章p e t r i 网的基本理论及相关技术的研究 定义2 2 l 并联变迁合并 简称巾c p t 设原p c t r i 网n l p l t l f l m 1 化简后为n 2 p 2 t 2 f 2 m 2 若 n l n 2 中 c p t 则n l n 2 的结构分别如下 1 网n l 结构 存在变迁集合s e t l 任意取一个变迁t s 并且lsl 2 且满 足 v x s v y es x y 集合s 中的所有变迁的前集都相同 v x s r y e s x y 集合s 中的所有变迁的后集都相同 2 网n 2 的结构 v et 2 t l p 2 p l t 2 t t s u v v t es f 2 f l n p 2 t 2 t 2x p 2 u t x v u v t m 2 m 1 为了便于理解并联变迁合并的定义 下面引入一个并联变迁合并的简单 例子 如图2 3 所示 图2 3 并联变迁合并 定义2 2 2 并联库所合并 简称由c p p 设原p e t r i 网n l p 1 t 1 f 1 m 1 化简后为n 2 p 2 t 2 f 2 m 2 若 n l n 2 l l l c p p 则n l n 2 的结构分别如下 1 网n l 结构 存在库所集p e p t 任意取一库所p e p