（计算机应用技术专业论文）基于cpn的软件开发过程建模.pdf

摘要 随着计算机软件项目规模和复杂度的日益增大，软件产品的质量问题逐渐突出。在 软件开发的需求分析、概要设计和详细设计等阶段，建立一个能够准确描述和分析开发 活动的软件开发模型，已成为成功实现软件开发的重要手段。有效的软件开发模型可以 尽早地发现设计早期阶段的错误，降低软件开发的成本和风险，提高软件的开发质量和 效率。 本文提出利用c p n 建立和分析软件开发过程模型，使用c p nt o o ls 对软件开发各 个阶段进行建模，针对仿真中的问题提出改进办法，用仿真结果说明改进后的模型能够 提高软件性能。在软件开发的需求分析阶段，以方案设计系统为例建立基于c p n 的需 求模型，利用状态空间验证需求模型的正确性，找出需求模型缺陷，提出需求的优化模 型，保证开发人员和客户理解的一致性。软件开发的概要设计阶段提出对软件重要的模 块或数据库建模，对分布式数据库中两阶段提交协议建立模型，利用数学分析和数据监 视法分析模型性能。实例证明c p n 是概要设计阶段提高软件性能的有效手段。软件开 发的详细设计阶段采用c p n 描述算法，通过仿真分析评价算法性能，同时给出算法模 型向代码转化的规则。 通过c p n 在软件开发各个阶段上的应用，说明软件开发中采用着色p e t r i 网技术可 以有效的避免软件开发周期的反复，优化软件性能，提高软件开发的可靠性，从而保障 整个软件开发过程的顺利进行。 关键词：着色p e t r i 网、软件开发模型、正确性验证、性能分析 m o d e l i n go fs o f t w a r ed e v e l o p m e n tp r o c e s sb a s e d o nc p n l iq i n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f e s s o rz h ul i a n z h a n g a b s t r a c t a l o n g 谢t hi n c r e a s i n g l ye x p a n s i o no ft h es c a l ea n dc o m p l e x i t yo ft h es o f t w a r ep r o j e c t ， t h eq u a l i t yp r o b l e mo ft h ep r o d u c th a sg r a d u a l l yb e e nh i g h l i g h t e d a ts o m es t a g e so fs o f t w a r e d e v e l o p m e n t ，s u c ha st h er e q u i r e m e n ta n a l y s i s ，s u m m a r yd e s i g na n dd e t a i l e dd e s i g n , e t c ， s o f t w a r ed e v e l o p i n gm o d e lt h a td e s c r i b e se x a c t l ya n da n a l y z e sd e v e l o p i n ga c t i v i t ys h o u l db e e s t a b l i s h e d ，w h i c hi sa ni m p o r t a n tm e a s u r et oa c h i e v et h es o f t w a r ed e v e l o p m e n t t h ee r r o r c a l lb ef o u n d 、) i ，i t ha ne f f e c t i v em o d e lo fs o f t w a r ed e v e l o p m e n ta se a r l ya sp o s s i b l ei nt h e d e s i g ns t a g e ，w h i c hn o to n l yr e d u c et h ec o s ta n dr i s ko fs o f t w a r e ，b u ta l s oi m p r o v et h eq u a l i t y a n de f f i c i e n c yo fs o f t w a r ed e v e l o p m e n t i nt h i sp a p e r , i tp u t sf o r w a r dt oe s t a b l i s h m e n ta n da n a l y s i so ft h ep r o c e s sm o d e lo ft h e s o f t w a r ed e v e l o p m e n t 、i t l lc p n ，m a k e sm o d e l i n g 谢t hc p nt o o l sf o re a c hs t a g eo fs o f t w a r e ， a n ds u g g e s t sw a yt oi m p r o v et h ep r o b l e m sa tt h es i m u l a t i o n ，a n de x p l a i n st h a tt h ei m p r o v e d m o d e lc a ni m p r o v et h ep e r f o r m a n c eo ft h es o f t w a r e a tt h er e q u i r e m e n ta n a l y s i ss t a g eo f s o t h v a r ed e v e l o p m e n t ，t a k i n gt h es y s t e mo fp r o je c td e s i g na sa ne x a m p l e ，w ee s t a b l i s ht h e r e q u i r e m e n tm o d e lb a s e do nc p n ，v a l i d a t ei t sa c c u r a c ya c c o r d i n gt ot h es t a t es p a c e ，f i n do u t t h ed e f e c t s ，i n t r o d u c et h eo p t i m i z a t i o nm o d e la n dk e e pt h ec o n s i s t e n c yo ft h eu n d e r s t a n d i n g b e t w e e nd e v e l o p e r sa n dc u s t o m e r s t h es t a g eo fs u m m a r yd e s i g ns u g g e s t st oe s t a b l i s hm o d e l s f o rt h ei m p o r t a n tm o d u l ea n dd a t a b a s eo fs o f t w a r e ，t oc o m m i t p r o t o c o lf o rt w os t a g e si nt h e d i s t r i b u t e dd a t a b a s e ，i ta n a l y z e st h ep e r f o r m a n c eo ft h em o d e lb ym a t h e m a t i c a la n a l y s i sa n d d a t ec o n t r o lm e t h o d ，i ti s p r o v e dt h a t ，c p ni s t h ee f f e c t i v em e a s u r et oi m p r o v et h e p e r f o r m a n c eo fs o a r ed e v e l o p m e n ta tt h i ss t a g e t h es t a g eo fd e t a i l e dd e s i g nf o rs o f t w a r e d e v e l o p m e n tu s e sd e s c r i p t i o na l g o r i t h m ，a n de v a l u a t e si t sp e i f o r m a n c ef r o mt h es i m u l a t i o n a n a l y s i s ，i na d d i t i o n , ar e g u l a t i o nf o rt h et r a n s f o r m a t i o nf r o mt h em o d e lo fa l g o r i t h mt oc o d e i sp r o v i d e d t h r o u g ht h ea p p l i c a t i o no fc p na tv a r i o u so fs t a g e so fs o f t w a r ed e v e l o p m e n t , i t i l l u s t r a t e st h a t , a d o p t i n gt h ec o l o r e dp e t r in e t st e c h n o l o g yc a l la v o i dt h er e p e a t a b i l i t yo ft h e d e v e l o p m e n tc y c l e ，o p t i m i z et h ep e r f o r m a n c eo ft h es o f t w a r e ，a n di m p r o v et h er e l i a b i l i t yo f t h es o f t w a r ed e v e l o p m e n t ，t h u st h es m o o t h l yr u n n i n go ft h ew h o l es o f t w a r ed e v e l o p m e n t p r o c e s sc a l lb ee n s u r e d k e yw o r d s ：c o l o r e dp e t r in e t ，s o f t w a r ed e v e l o p i n gm o d e l ，v e r i f i c a t i o n ，p e r f o r m a n c e a n a l y s i s 1 1 1 独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，馀文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志对 研究所做的任何贡献均已在论文中做出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名： 鸯矗日期：彻c 年5 月门日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版和 电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学 位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和复印， 将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他复制手 段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名： 杰孟 指导教师签名：生j 红章_ 日期：御年f 月j9 日 日期：卯口年厂月j7 日 中国石油丈学( 华东) 硕士学位论文 1 1 研究背景及意义 第一章绪论弟一早珀下匕 早期计算机软件应用需求范围较小，需求简单，质量问题不突出，只要求程序能够 正常运行【1 1 。随着计算机软件的飞速发展，用户对软件和软件系统的功能要求日益增长， 产品的复杂程度逐渐提高，软件的质量问题开始凸现。如何减少软件设计早期阶段的失 误，缩短开发周期，提高软件的可靠性，成为各大软件公司亟需解决的问题。 软件产品的开发是由具体的软件开发过程来完成【2 j ，定义详细精确的软件过程不仅 能够约束软件人员，保证软件的质量，而且有利于开发人员之间的交流和项目进度的控 制。软件开发过程的质量很大程度上决定了所产生的软件产品的质量和软件生产率【3 】。 因此，为了提高软件开发的质量和效率，在软件开发的需求、设计、编码、测试和维护 阶段，建立一个能够准确描述和分析软件开发活动的软件开发模型( s o f t w a r e d e v e l o p m e n tm o d e l ) 已成为成功实现软件开发的重要手段。软件开发模型采用分层理论 可以将复杂问题细分为多个问题逐一解决。这就是为什么要对开发过程进行建模的原 因。有效的软件开发模型有利于分工与专业化生产，从而降低软件开发风险。 使用软件开发模型便于从整体上、宏观上把握问题，在需求分析阶段，可以加强人 员之间的交流，使开发人员准确地捕获用户的需求，更好地理解问题，建立一个双方都 能达成一致的模型，为建立正确的软件系统打下良好的基础。在概要设计阶段，可以帮 助开发人员方便地研究软件的多种构架和设计方案，从中找出效率最高、速度最快最适 合的解决方案，并验证设计的正确性，这种早期决策对软件系统的后续开发、部署和维 护具有相当重要的意义。在详细设计阶段，编码前对数据结构和算法设计建模，评价算 法在整个软件中对软件性能的影响，优化软件性能。 目前在软件开发建模中，很少有模型语言既能够验证软件功能流程的正确性，又能 评价软件性能，而着色p e t r i 网( 简称c p n ) 可同时满足这两方面的要求。c p n 是在基本 p e t r i 网基础上提出的一种高级p e t r i 网和层次p e t r i 网，是一种可以对系统进行检验和仿真 的有色建模语言。它通过将相似组件或行为进行折叠的方式来表征一个具有若干相似部 件的大系统，从而解决了系统模型规模不可控制的问题1 4 。c p n 除具有普通p e t r i 网所具 有的可描述系统动态特性、表示系统竞争和冲突现象等优点外，还具有模型结构简单、 可重用性强等优点。c p n 中颜色集的概念能够表示更为丰富的数据类型，从而降低模型 第一章绪论 的复杂度。此外，c p n 弥补了普通p e t r i 网没有数据和分层分解的缺陷，对数据结构和层 次分解进行了很好的结合，应用c p n 层次分解可以方便的表述复杂系统的层次和内部关 系。 因此，应该把c p n 这个有形式化描述方法、图形表达能力和动态仿真特性的工具引 入到软件开发过程中，利用c p n 模型对软件开发过程中各个阶段的问题和细节进行描 述，保证开发软件数据结构的有效性和模块的完善性。在开发过程中，运用c p n 建立模 块或子系统的可执行模型，描述模块、子系统之间的输入输出关系，通过有效的控制模 型中托肯的移动和传播，反映软件运行时的静态和动态特性。运用c p n 的层次性可以清 晰的表达复杂软件的结构和内部关系，将复杂软件进行分页，逐步细化，解决软件的复 杂性问题。此外，利用c p nt o o l s 的状态空间和m o m t o r i 具，分析软件开发过程模型中 模块或数据之间存在的冲突、竞争和并发等各种关系，对开发过程的行为和模块性能进 行正确性验证和评价，为模块和子系统的优化提供依据，减少软件开发后期才发现设计 的错误而带来的损失。 将c p n 引入到软件开发的过程中，可以保证每个开发阶段成果的正确性，开发人员 能够在软件测试前及时发现软件存在的问题，从而可以避免软件开发周期的反复，降低 软件开发成本，提高软件开发的质量和效率。 1 2 相关技术及现状 着色p e t r i 网是一种在p e t r i 网基础上发展起来的适用于描述并行和异构网络的系 统分析和设计工具，已被广泛应用于各个领域进行系统的建模、分析和控制，包括柔性 制造系统、决策模型、逻辑推理、人工智能、并行编译、分布式数据库系统、工作流程 分析等。 1 2 1 软件开发模型的发展 1 9 7 0 年由w r o y c e 提出了第一个软件开发模型瀑布模型。当时，软件开发模 型也称为软件生命周期模型。随着人们研究的不断深入、经验不断积累以及软件工程其 他领域的发展，人们对软件过程本质的认识不断提高，软件开发模型也在不断发展之中， 上世纪8 0 年代以来，又陆续出现了快速原型模型( r a p i dp r o t o t y p em o d e l ) 、渐增模型演 化迭代( i n c r e m e n t a lm o d e l ) 、螺旋模型( s p i r a lm o d e l ) 、喷泉模型( f o u n t a i nm o d e l ) 以及智能 模型( i n t e l l i g e n tm o d e l ) 掣5 , 6 1 。 2 中国石油大学( 华东) 硕士学位论文 瀑布模型给出了固定的顺序，将生存期活动从上一个阶段向下一个阶段逐级过渡， 最终得到所开发的软件产品。但计算拓广到统计分析、商业事务等领域时，大多数程序 采用高级语言( 如f o r t r a n 、c o b o l 等) 编写。瀑布模式模型存在着缺乏灵活性、无法 通过并发活动表示本来不够确切的需求等缺点。 快速原型模型克服了瀑布模型的缺点，减少由于软件需求不明确带来的开发风险。 它尽可能快速的建造出了软件原型，一旦确定了客户的真正需求，所建造的原型将被丢 弃，因此，原型系统重要的是必须迅速建立原型，然后迅速修改原型，以反映客户的需 求。由于原型模型没有考虑软件的整体质量和长期的可维护性，达不到质量要求的产品 可能被抛弃，而采用新的模型重新设计，所以原型模型不适合实时控制等大型软件系统 的开发。 演化模型主要是针对事先不能完整定义需求的软件开发。软件开发人员根据用户的 需求，首先开发核心系统。当核心系统投入运行后，用户试用，完成他们的工作，并提 出精化系统、增强系统能力的需求。由于软件需求一开始并不明确，给总体设计带来困 难，会削弱产品设计的完整性，并影响产品性能的优化及产品的可维护性。 螺旋模型在1 9 8 8 年由b a r r yb o e h m 正式发表，它将瀑布模型和快速原型模型结合 起来，强调了其他模型所忽视的风险分析，特别适合于大型复杂的系统。但是，采用螺 旋模型需要相当丰富的评估经验，如果在大型软件的开发中不能及时发现风险，会造成 重大的损失，而且过多的迭代次数增加开发成本，延迟提交时间。 喷泉模型即面向对对象的生存期模型，它比传统的结构化模型具有更多的增量和迭 代性质，在生存期的各个阶段可以相互重叠和多次反复，而且在项目的整个生存期中还 可以嵌入子生存期。由于喷泉模型在各个开发阶段是重叠的，开发过程中需要大量的开 发人员，不利于软件开发的管理。 智能模型拥有一组如数据查询和处理、报表和代码生成、屏幕定义及电子表格等工 具，每个工具都能使开发人员在高层次上定义软件的某些特性，并把开发人员定义的这 些软件自动地生成为源代码。但智能模型目前主要限于事务信息系统的中、小型应用程 序的开发。 其中，瀑布模型、快速原型模型、渐增式模型、螺旋模型等传统模型，都较注重对 软件过程进行一个抽象化的描述，它们都起到了提供一个客户与开发人员之间交流平台 的作用。但是，软件开发作为一个生命周期，后一个周期的正确必须建立在前一周期正 确的基础之上。由于传统模型都是静态模型，模型的正确与否无法在模型建立后进行验 3 第一章绪论 证，从而对开发人员的建模经验提出了很高的要求。利用传统模型开发软件，模型的反 复修改必然造成开发周期和风险的增加。c p n 建模的方法可以解决这一难题，它不但能 起到交流平台的作用，而且能够验证模型的正确性，更主要的是能够帮助项目经理对项 目过程进行分析和管理，以及为软件开发者提供了构建支持软件过程提升工具的基础。 着色p e t r i 网模型是一种用来描述和分析在异步并发系统中的数据流与控制流的模 型。与其他建模方法相比，它具有形式化的语义、状态和动作的显示表示以及丰富的分 析技术等特点，对于从理论上验证软件开发过程十分有效。将着色p e t r i 网运用到软件开 发中，主要有以下优点【7 】： ( 1 ) 图形显示，易于理解，清晰简捷。着色p e t r i 网模型可以对实际软件开发过程中的 开发活动、产品、资源、人员等各类信息进行抽象，有效地描述和模拟软件中的行为。 通过查看c p n 模型很容易观察软件系统描述的细节，减少软件的纰漏。 ( 2 ) 互动仿真。软件开发人员可以通过对c p n 模型仿真预测软件性能，获得自信，同时 软件开发系统的模型可以展示给用户，明确用户的需求，方便沟通。 ( 3 ) c p nt o o l s 提供了包括画图、仿真和分析方面的可视化界面，很容易进行建模和语 法检测。 ( 4 ) 丰富的分析手段。状态空间和m o n i t o r 等工具对检验模型提供了技术支持，一些潜 在的错误可以在模型仿真中被发现。如果在最后的测试中发现和纠正错误，费用是非常 昂贵的。 ( 5 ) 着色p e t r i 网与程序设计语言的结合，使模型易于向程序代码转换。 因此，着色p e t r i 网己逐渐被认定为一种具有较好的理论基础、适合于描述软件开发 过程的建模方法，尤其适用于大型复杂软件的开发过程。 1 2 2 着色p e t r i 网在软件开发中研究的现状 目前，在使用c p n 对软件的开发过程进行设计建模的理论方面，国内外都进行了一 些研究。h a r u m iw a t a n a b e 和h i r o k it o k u o k a 8 】提出基于着色p e t r i 网的面向对象软件测 试技术。此技术利用对象和着色p e t r i 网的着色标记共同描述面向对象软件，以避免状 态爆炸问题。d b u c h s 、l l u c i o 和l p e d r 0 1 9 又将u m l 和p e t r i 网技术结合，将u m l 描述的 面向对象的软件系统转换为并行面向对象的着色p e t r i 网模型，最后利用谓语逻辑语言 p r o l o g 自动产生基于规约的测试用例。r o b e r tg p e t t i ti v 和h a s s a ng o m a a t l o l 采用将c p n 和u m l 相结合来提高面向对象软件设计可靠性的方法，尤其适用于并发式系统。该方法 4 中国石油大学( 华东) 硕士学位论文 利用u m l 描述实际状态，c p n 来模拟体系结构的功能流程，分析并发行为。通过c p n 对原 始u m l 模型的分析结果，来提高设计的质量和最终系统的可靠性。v e k o z u r a 、 v a n e p o m n i a s c h y 和r m n o v i k o v 】提出一种用来分析、模拟和验证c p n 模型的工具 p n v ( p e t r in e tv e r i f i e r ) ，该工具由两部分组成，一部分产生c p n 内部结构和模型输入 c p n 的c + + 程序，另一部分是检测模型的组件。该文还描述了用c p n 模拟令牌通信协议的 模型检测试验。 国内也有不少文章提到将c p n 应用到软件工程中去，例如刘密霞、余冬梅和冯涛【5 】 提出引入c p n 的软件开发框架，用自然语言描述软件功能，c p n 描述软件需求分析和系统 建模。但是文中仅仅对安全告警系统设备的软件开发过程进行了建模，并没有对模型进 行分析和验证。颜志军和甘仞初【1 2 】也指出一种基于c p n 的规范化建模方法，并对租车管 理系统的整个建模过程进行了描述，提出系统层次模型结构和执行图的概念，并对执行 图和p e t r i 网间的转换过程进行了分析和定义，然而该文也只是建模，没有模拟系统的 运行状况和评价系统性能。所以，国内大部分对c p n 模型的研究都处于建模阶段，对建 模后模型的分析验证比较少，而且他们的研究大部分都是从总体上考虑建模或只针对软 件开发过程的某一阶段。 从国内外研究的总体现状来看，许多学者强调将模型从u m l 转化成c p n 实现开发模 型的验证分析，但是由于u m l 和c p n 之间存在差异，并且涉及c p n 编程控制的问题，完 成从u m l 到c p n 的自动转化一时难有突破性进展。有的学者提出c p n 的软件开发框架的 构想，由于软件开发的多样性与非工厂化生产的特点，其构想没有很大的实用价值。有 的学者则针对的是c p n 在一个具体系统中的应用，解决的问题缺乏普遍性。本文强调的 是在软件各个开发阶段，为了保证阶段性成果的正确性，c p n 起到的作用，并通过实例 说明c p n 是如何发挥的作用。 1 3 主要研究内容 本文在研究软件开发过程的基础上，结合着色p e t r i 网理论在工作流、排队网等方面 的应用，提出将着色p e t r i 网运用在软件开发过程中，通过在开发过程中分阶段的建模仿 真来提升软件性能，提高软件开发的质量，最终保障整个软件开发的顺利进行。 软件开发包括需求、设计、编码和测试等阶段，有时也包括维护阶段。为了在测试 以前尽早发现和纠正错误，针对开发过程的各个阶段，提出相应的参照模型，其阶段框 架如图1 - 1 所示。 5 第一章绪论 建模阶段 模型分析 需求分析l- i 功能需求 卜 弋夕 概要设计 结构设计 状态芏1 日j 工具。l 八 亡“4 h 数据库设计 一 7 l 川训旺目匕 m o n i t o r 工具 v ；茔朝血_ 二 l- l 数据结构 洋l i 芦卅l r 1 算法 u 编码 图1 - 1 软件开发过程建模框架 f i 9 1 1t h em o d e l i n gf r a m eo fs o f t w a r ed e v e l o p m e n tp r o c e s s 第一步是开发人员向客户确定需求分析之前，开发人员根据客户提出的要求，建立 需求功能模型，对基于c p n 的需求模型进行正确性验证。找出需求模型的缺陷，根据需 求模型再次向客户确定软件的功能，消除客户与开发人员理解的二义性。 第二步是为软件概要设计阶段，将c p n 与u m l 相结合定义和分析软件模块或子系统 的接口、层次结构和调用关系，利用c p n 模型设计和分析软件结构和数据库，提高软件 性能。 第三步在开发人员进行详细设计时，用c p n 描述数据结构与算法设计，对模型进行 仿真数据模拟和状态空间分析，找出算法中死循环、缓冲区溢出等错误，通过性能分析 挑选出高效的算法。 第四步将详细阶段中数据结构和算法的c p n 模型的函数和颜色集转化为程序语言的 函数和类型，将模型的结构作为程序的模板，生成程序语言代码。 本文通过研究需求分析、概要设计、详细设计等阶段在软件开发过程中的作用，针 对不同阶段不同的开发目标，对软件性能有重大影响的功能结构、数据库和算法等建立 c p n 模型，利用c p nt o o l s 的状态空间和数据监视( m o n i t o r ) 等工具，通过数学分析方法对 软件进行性能分析和验证，确保开发过程的正确性，或指出软件开发过程的缺陷。c p n 在每一阶段的应用都通过实例建模说明。 6 中国石油大学( 华东) 硕士学位论文 1 4 论文组织结构 本文共分为五章： 第一章为绪论，介绍了软件开发模型在开发过程中的重要意义及其发展演变过程， 从中引出着色p e t r i 网，阐述着色p e t r i 网应用在软件开发过程中的优点，并对本文的研 究内容和组织结构进行了说明。 第二章主要介绍着色p e t d 网的发展和基本理论包括定义、图形表示、触发规则、 性质和分析方法，这些都是进行软件开发过程建模和仿真的基础，最后还简单介绍了 c p nt o o l s 。 第三章描述着色p e t r i 网在软件开发需求阶段的应用，介绍了良好的需求分析对软 件开发的重要作用，以方案设计系统的需求分析为例，建立基于c p n 的需求模型，对 模型进行验证和分析，提出优化的需求模型。 第四章简要介绍着色p e t r i 网在概要设计阶段的应用，给出采用着色p e t r i 网建模分 析分布式数据库的两阶段提交协议的过程。 第五章对详细设计阶段的数据结构和算法设计进行着色p e t r i 网建模，通过模型的 动态仿真和状态空间分析，验证算法的正确性，通过c p nt o o l s 监视工具分析算法对软 件性能的影响，并给出模型向代码转化的规则。 最后是论文的总结部分，对论文工作进行了全面的、概括性的总结，并对c p n 在 软件开发过程中的应用做出了设想和展望。 7 第二章着色p e t r i 网概述 第二章着色p e t ri 网概述 着色p e t r i 网( 简称c p n ) 是k u r tj e n s e n 在基本p e t r i 网基础上提出的一种图形化 的高级p e t r i 网模型。它有机地结合了p e t r i 网的图形表示和计算机程序语言，是少有 的能同时用于验证系统功能、逻辑地正确性和评估系统性能的有色建模语言，通过将相 似状态或动作进行折叠，c p n 可提供一种以紧凑、简明的方式来表示一个具有若干相似 状态或动作的大系统的能力，从而解决系统模型规模不可控制的问题1 4 】。c p n 中还引入 了层次概念，从整体到局部、由粗到精的把系统分页，逐步细化，突出重点，使建模和 仿真起来更方便和清楚。 2 1 着色p e 砸网的发展 19 6 2 年，德国的c a r la d a mp e t r i 博士在( c o m m u n i c a t i o nw i t ha u t o m a t o n ) ) 一文中 首次提出了网状结构的信息流模型，该系统模型后来就被称为p e t r i 网。现在的p e t r i 网 一词既指这种模型，又指以这种模型为基础发展起来的理论。 最早的p e t r i 网被称为条件事件网( c e n e t s ) ，库所的容量为1 ，弧的权值也为1 。其 后随着人们对新的网模型、网的基本概念及分析方法等的不断探索，产生了库所容量和 弧都任意的库所变迁网( p t - n e t s ) ，也就是常说的p t 网【1 3 】。这些早期的网模型都属于基 本l 双j ( e n - n e t s ) 1 1 4 3 5 】。 然而，在实际使用中，p e t r i 网又因为“太 直观而使其难以描述复杂系统。于是不 同的研究人员从不同角度对p e t r i 网进行了不同的扩展【1 6 】，例如在网中增加变迁的优先 级、时间延迟、全程变量等一些概念，并在此基础上形成了比条件事件网和库所变迁 网更加通用化的高级网( h i g h 1 e v e ln e t s ) 理论。最早的高级网是谓词变迁网 ( p r e d i c a t e t r a n s i t i o nn e t s ) 1 7 , 1 8 】，它综合了p e t r i 网和条件事件网的优点，利用了命题逻 辑和谓词逻辑的相同的推理机制。 不过人们在分析谓词变迁网的库所不变量和变迁不变量时也碰到了一些问题。对 于谓词变迁网，计算它的不变量并不难，难的是解释所得到的结果【1 9 】。这是因为在谓 词变迁网的弧表达式中出现了变量，而与此同时这些变量也出现在不变量中。因此在 解释不变量时必须现通过一系列复杂的替代规则来绑定这些变量。为了克服这些缺点， 丹麦的j e n s e nk u r t 于1 9 8 1 年首次提出着色p e t r i 网( c o l o r e dp e t r in e t s ，c p n ) 2 0 , 2 1 1 的概念。该模型的思想直接从谓词变迁网引申而来，用函数来表示变迁的激发和着色 8 中国石油大学( 华东) 硕士学位论文 标识之间的关系，这样就去掉了变量，使得不变量的解释问题得到解决。 2 2 着色p e t r i 网的基本理论 在这一节里，对着色p e t r i 网的基本概念包括它的定义、图形表示和有关规则等，进 行系统的介绍。这些概念都是着色p e t r i 网的基础。 2 2 1 着色p e t r i 网的基本定义 c p n 的定义是一个九元组【2 2 , 2 3 ： c p n = ( ，p ；t ，a ，n ，c ，g e ，i ) ( 1 ) 是一个有限非空类型集，也称作颜色集，它决定用于网标注中的类型、运算和 函数，例如弧表达式、守卫函数、初始化表达式和颜色集等。 ( 2 ) p 是有限库所集。 ( 3 ) t 是有限变迁集。 ( 4 ) a 是有限弧集。p n t = p n a = t n a = o ，与普通p e t r i 网不同的是c p n 结构可以 为空，即put ua = a ，这样在构造一个复杂的c p n 模型之前，可以先定义颜色集，并 对其做语法检查。c p n 还允许一对有序节点之间存在几条弧，所以把弧a 定义为一个 独立的集合，而不是p t u t p 的子集。 ( 5 ) n 是节点函数，定义：n a 专p t u t p ，返回与弧相连的节点的函数， 节点是库所和变迁的统称，h i j ( 变迁，库所) 或( 库所，变迁) 。 ( 6 ) c 是颜色函数，定义：c e p 专c ) ，每个库所p 都能映射到一个颜色集c ( p ) ， 也就是说库所中的每个标识都必须属于某个颜色集。 ( 7 ) g 是守卫函数，由变迁到表达式的函数。定义：g ：t - - e x p r s ，且满足 v f t ： 巧邵( g ( f ) ) = b o o ， t y p p ( 哳( g ( f ) ) ) ，g 把每个变迁t 都映射到一个布尔 表达式，并且g ( t ) 中所有的变量的类型必须包含于颜色集中。 ( 8 ) e 是弧表达式函数，由弧到表达式的函数。定义：e ：a _ e x p r s ，且满足 v a e a ： 聊p ( e ( 口) ) = c ( p o ) k 人t y p p ( 哳( e ( 口) ) ) 冬 ，其中p ( a ) 表示节点函数n ( a ) 中的库所，c m s 表示集合c 上的多种集合的集合。e 把每条弧a 都映射到一个具有类 型c q ( a ) ) m s 的表达式，这表示e ( a ) 的每次求值都生成一个依赖于相邻库所颜色集的多 重集合。弧表达式可以缺省为空。 9 第二章着色p e t r i 网概述 ( 9 ) i 为初始函数。定义hp - - e x p r s ，p 是一个封闭表达式，且满足 砌p ：t y p e ( ，( p ) ) = c ( p ) 艘人哳( ，( p ) ) = a ，i 把每个库所p 映射为不包含变量的表 达式，其类型为c ( p ) m s 。初始化表达式的类型可以为c q ) 或取空。 2 2 2 着色p e t r i 网的图形表示 着色p e t r i 网是一种面向图形的建模语言，它主要由声明、库所、变迁和弧组成。 ( 1 ) 声明( d e c l a r a t i o n ) 用c p nm l 矧语言描述，可以定义颜色集、函数、多重集、运算和变量。颜色集( c o l o r s e t ) 就是对建模中要用到的数据类型进行定义，它限定了库所中托肯所能取得的颜色范 围。 从图2 1 的着色p e t r i 网的声明中可知，n 是声明常数，p 为变量，m 为函数，x 和y 都是 索引颜色集，索引值是由标识符和特定的索引值组成的序列，所以x 的颜色范围是 a ( 1 ) ， “2 ) ，a ( 3 ) ，a ( 4 ) ，a ( 5 ) ，y 的取值范围为 c ( 1 ) ，c ( 2 ) ，c ( 3 ) ，c ( 4 ) ，c ( 5 ) ) 。 d e c l a r a t i o n s ，v a in = 5 ： t c o l s e t x = i n d e xaw i t h1 。n ； v c o l s e ty j n d e xcw ；t h1 。n ； v v a rp ：x ； v f u nm ( a ( i ) ) = l c ( i ) + + l 。c ( i f i s n t h e nle l s ei + 1 ) ； 图2 - 1c p n 声明示例 f i 9 2 - ic p ns t a t e m e n te x a m p l e ( 2 ) 库所( p l a c e ) x a l l o r e ( o ) 孓一瓿。一。一i 纛 图2 - 2c p n 基本模型 f i 9 2 - 2c p nb a s i cm o d e l 着色p e t r i 网中，库所表示系统状态，用椭圆表示，主要元素有库所名、颜色集、初 始托肯。图2 2 中，库所a 、b 的颜色集是x ，库所c 的颜色集是y 。库所旁边的标记是着 色p e t r i 网的当前标识。为了表示当前标识，在标识的前面画一小圆圈，圆圈内注明库所 中托肯( t o k e n ) 的数目，圆圈附近的文本字符串则表示具体的标识。库所a 有五个初始标 识，分别为 a ( 1 ) ，a ( 2 ) ，a ( 3 ) ，a ( 4 ) ，a ( 5 ) ，c 也有 c ( 1 ) ，c ( 2 ) ，c ( 3 ) ，c ( 4 ) ，c ( 5 ) ) 五个初 始标识。因为图2 2 表示的是初始状态，所以当前标识和初始标识相同。当变迁被激发 后，当前标识则会发生变化。 1 0 中国石油大学( 华东) 硕士学位论文 ( 3 ) 变迁( t r a n s i t i o n ) 着色p e t r i 网上的变迁用来描述系统的活动或状态改变，以长方形来表示，主要元素 由变迁名、守卫函数和代码段组成。在图2 2 中有变迁t 1 ，t 2 。 ( 4 ) 弧( a r c ) 库所和变迁之间用有向弧连接，有向弧必须从库所到变迁或从变迁到库所，所有的 弧只有一种注入式( 即弧表达式) 。指向变迁的弧，反映了变迁发生的前提条件，表明变 迁要从相应的库所中迁移出托肯。指向库所的弧，则说明变迁发生的效果，即向指向的 库所添加托肯。托肯的数量和数据值的变化是由弧表达式决定的。图2 2 中，变迁t 1 周 围有三条弧和两个不同的弧表达式：p 和m ( p ) 。弧表达式p 是x 类型的值。当变迁t 1 发生 时，将有一个x 类型的托肯从库所a 迁移到库所b 上。 2 2 3 变迁的触发规则 由于系统的状态是变化的，因此只要给出系统的初始标识m o ，然后根据着色p e t r i 网的触发规则，变迁就可以二个接一个地发生，标识也会不断变化，从而描述系统的运 行。 着色p e t r i 网的变迁触发规则： 定义2 1 ：对着色p e t r i 网中的任意变迁t ，如果 跏尸：e ( p ，) m ( p ) ( 2 - 1 ) 则称变迁，在标识m 下的激发步y 是使能( 有发生权) 的，记为u t 。 若激发步y 在m 下是使能的，存在( f ，b ) y ，称变迁r 在标记m 下对绑定b 是使能 的。激发步y 使能说明标识m 从输入库所中移去加入到了输出库所中，标识的数目和 颜色由弧表达式决定。 定义2 2 ：若m 【， ，则变迁f 的发生引起标识的变化。设在标识m 下发生变迁f 产 生新的标识m ( 记为u t m ) ，那么 印p ：m ( p ) = lm ( p ) - e ( p ，) ( 6 l + ( r ，p ) ( 6 ( 2 - 2 ) ( 。6 ) e 】， ( f ，6 ) e r 式中的第一个累加是移出标识，第二个累加则是移入标识。 简单的说就是，一个变迁的前集是库所集合，当这个集合中的每个库所都有托肯， 并且库所中托肯的个数要大于等于输入弧上的数值，那么这个变迁是使能的。但是使能 第二章着色p e t r i 网概述 的变迁不一定能触发，只有当这个变迁的后集( 也是一个库所集) 中的任何一个库所中的 托肯数量加上对应的输出弧上的数值小于等于这个库所的容量限制，并且变迁的警卫函 数为真的时候，这个变迁才能触发。因为c p n 中一般假设库所的容量为无限大，故一 般变迁使能就能触发。 2 2 4 着色p e t r i 网的基本性质 建立系统模型的目的是通过运行系统模型来仿真实际系统的运行，通过分析系统模 型的性质和性能来研究实际系统的性质和性能。从而根据性质的分析提出对实际系统的 改进设计，甚至对一个实际系统进行设计时，可以根据性质和性能要求先设计出系统的 模型，然后通过模型来实现一个系统的设计。因此，对任何一种系统模型，都不能只研 究如何描述系统中的各种行为，还要研究模型的性质。接下来，开始讨论着色p e t r i 网的 基本性质。 对着色p e t r i 网已提出的各种性质可以分为动态性质和结构性质两种。动态性质是着 色p e t r i 网运行过程中的性质，这些性质同网的结构有关，也同初始标识有关。而结构性 质与网的初始状态无关，仅仅取决于网的拓扑或结构1 2 5 1 。着色p e t r i 网的主要性质有： 可达性i 描述从初始标识开始，一些标识是否可达。可达标识集是从初始标识m o 出发按照触发规则在有限步之内可到达的所有状态标识的集合。可达标识是状态方程的 解。 有界性( 安全性) ：反映系统运行过程中对资源变量的需求。在理论分析时常可假定 库所容量为无穷，但在实际系统设计中，必须使网络中的每个库所在任何状态下的标识 数小于库所的容量，这样才能保证