基于UML顺序图的Petri网建模

基于UML顺序图的Petri网建模 基于 UML 顺序图的 Petri 网建模 1 ,2 1杨玉梅,刁永锋 ( 1 . 西华师范大学 计算机学院 , 四川 南充 637000 ; ) 2 . 绵阳师范学院 计算机科学与工程系 ,四川 绵阳 621000 ) ( 摘 要 : U ML 统一建模语言是一种功能较强的面向对象图形建模工具 ,但其过程描述中缺乏严格的语义 ,而 Pet ri 网不 仅有形象直观的图形描述还有严格的 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 定义 。针对一个简单运输系统的建模将二者结合起来 ,阐述了 U ML 类图 、顺序 图的 Pet ri 网建模转换方法 ,避免直接进行 Pet ri 网建模过程的烦琐 ,使建模过程清晰可见 。 关键词 : U ML ; Pet ri 网 ;建模 ( ) 文章编号 :1673 - 629 X200710 - 0130 - 04 中图分类号 : TP311 文献标识码 :A Petri Net Model ing Ba sed on UML Sequence Diagra m 1 ,2 1YAN G Yu2mei,D IAO Yo ng2feng (1 . Co mp uter College of China West Normal U niversity , Nancho ng 637000 ,China ; )2 . Co mp uter Science and Project Depart ment of Mianyang Normal U niversity ,Mianyang 621000 ,China Abstract :U ML is a st ro ng f unctio n of t he o bject - o riented grap hical mo deling tool , but it’s lack of st rict semantic descriptio n of t he p ro2 cess , and Pet ri net s not o nly have t he visual image of t he grap hic descriptio n ,but also have st rict mat hematical definitio ns. In t his paper , a simple mo deling of t he t ranspo rt system will allow t he t wo to wo r k toget her , expo unded t he U ML class diagram , sequence diagram mo deling ways to avoid t he cumberso me p rocess of direct Pet ri net mo deling , t he mo deling p rocess is clearly discernible . Key words :U ML ; Pet ri net ; mo deling 0 引言1 UML ( ) , 比如开发传统的系统分析和设计存在许多不足 统一建模语言 U ML统一了 Booch , Rumbaugh 和 出来的软件与实际需求不符 、维护困难 、软件复用率低 J acobso n 的表示方法 ,并对其作了进一步的改进 , 最终 等 。为了解决这一系列的问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 提高软件设计质量 , 人 成为能为大众所接受的标准建模语言 。U ML 是一种 们提出了面向对象的方法 ,而面向对象的分析与设计 图形化建模语言 ,因为结合了软件工程领域面向对象 应该从建立模型开始 。模型的建立是对现实系统的一 的设计思想 ,因此具有定义良好 、易于表示 、表现直观 种抽象 ,它的建立反映现实系统的特点 ,同时又区别于 等特点 ,可谓是建模的好帮手 。目前 , U ML 已经成为 1 现实系统 。能否高效率高质量地建立系统模型 , 建模 建模语言的工业标准, 应用领域包括软件系统和非 工具的选择是关键 。文中实例中涉及 U ML 建模的类 软件系统领域 。但是 U ML 作为一种图形建模语言语 图和顺序图 ,其中类图体现各对象之间的静态关系 ,顺 义不严格只能半形式化地对系统进行描述 。U ML 的 序图描述各对象之间在时间顺序上的交互关系 , 这些 建模提供了 9 种图 ,它们分别是用案图 、类图 、对象图 特点恰好是 Pet ri 网建模所关心的要素 ,结合 U ML 建 状态图 、活动图 、顺序图 、协作图 、构件图 、部署图 。这 模和 Pet ri 网的建模方法 ,实现了从 U ML 到 Pet ri 网的 些图反映了不同的系统元素 , 元素之间的联系构成了 建模 。 系统 ,其中元素之间的联系是通过关系来实现的 ,这些 1 关系也是模型元素,常见的关系有关联 、聚合 、组合 泛化 、依赖 、实现 。 收稿日期 :2006 - 12 - 04 ( ) 基金项目 :四川省科技厅重点科研项目 05J Y029 - 0932 Petri 网 ( ) 作者简介 :杨玉梅 1978 - ,女 ,四川仁寿人 ,硕士研究生 ,主要研究 Pet ri 网是 1962 年由德国科学家 C. A . Pet ri 先生 方向为 Pet ri 网 、计算机应用 ;刁永锋 ,教授 ,硕士研究生导师 ,研究方 在其博士论文《用自动机通信》中首次提出的 , 是对离向为计算机辅助教育应用 。 散并行系统的数学表示 ,适合于描述异步的 、并发的系对 Π p ?P , M ’= 〃〃 t p ?t - 若 ( ) ( ) M p- W p , t 统模型 。Pet ri 网有严格的数学定义和直观的图形表 〃〃2 ( ) ( )M p+ W t , p 若 p ?t - t 达方式 ,具有相对成熟的语义和可执行性,系统结构 〃〃( ) ( ) ( )M p- W p , t + W t , p 分析技术比较完善 , 可以对系统的活性 、可达性 、有界若 p ?t ?t 〃〃( )性等进行有效验证 。所以在进行系统模型的分析和设 M p t 若 p | 计过程中可以将直观易懂的 U ML 图和具有严格数学 M ’为 M 的后继记作 M [ t > M ’。 3 定义的 Pet ri 网二者有机结合起来使用 。2 . 2 Petri 网相关性质 4 Pet ri 网是一个二元关系有向图 ,其中包括库所和 ( 以下提到的 Pet ri 网都是四元组, 其中略去了 ( ) 变迁两类节点 。库所 图中用小圆圈表示代表系统中 )权函数和容量函数 。 ( ) ( 表示状态的节点 , 其中状态信息用托肯 to ken小圆 定义 6 冲突关系 。 ) ( ) 圈里的小黑点表示 ;变迁 图中的小矩形块是系统中 ( ) 设 ?= P , T ; F , M 为一个 Pet ri 网 , M 为网的 0 活动的部分 。 任一标识 , t , t ?T 为 ?任意两个变迁 , 若 M [ t > ? 1 2 1 3 2 . 1 Petri 网基本定义M [ t > , 但是M { t , t } > , 则 t , t在 M 冲突 。「 2 1 2 1 2 ( ) 定义 1 三元组 N = P , T ; F称作有向网的充 定义 7 并发关系 。 分必要条件是 : ( ) 设 ?= P , T ; F , M 为一个 Pet ri 网 , M 为网的 0 ( ) 1P ?T = Ø; 任一标识 , t 和 t 在 M 并发的充分必要条件是 : 1 2 ( ) 2P ?T ? Ø; 〃〃〃〃 t?t = Ø ?t ?t Α M 1 2 1 2 ( ) ) (3F Α P ×T ?T ×P “x ”为笛卡尔积; 定义 8 可达性 。 ( ) ( ) ( ) 4do m F?cod F= P ?T , 其中 ?网系统的可达集[ M > 是满足下列条件的最小 0 ( ) ) ( do m F= { x | ϖ y : x , y?F}集合 : ( ) ( ) cod F= { y| ϖ x : x , y?F}( ) 1M ?[ M > ;0 0 ( ) 定义 2 令 N = P , T ; F为网 , X = P ? T 为其 ( ) 2若有 M ’?[ M > , t ?T , 使 M ’[ t > M , 则 M0 元素集 , 设 x ?X 为 N 的任一元素 , ?[ M > 。0 〃( ) ( ) () 1x = { x | y , x ?F} 称为 x 的前集 p re - set 定义 9 Pet ri 网的有界性 、安全性和活性 。 或输入集 。( ) 1若对于所有 M ?[ M > , 存在正整数 k , 使得 0 〃( () ( ) 2x = { z | x , z ? F} 称 为 x 的 后 集 post - ( ) 对所有 p ?P , M p?k , 就说 ?是有界的 , 当 k = 1 ) set或输入集 。 时称 ?是安全系统 。 ( ) 定义 3 六元组 ?= P , T ; F , K , W , M 为网系 0( ) 2对 t ?T , 若对任一可达标识 M ?[ M > , 均 0 统的条件是 : 有从 M 可达的标识 M ?[ M > , 使得 M [ t > , 就说变 ( ) ( ) 1N = P , T ; F构成有向网 , 称为 ?的基网 。 迁 t 是活的 。() 2K , W , M 依次为 N 上的容量函数 、权函数 0 ( ) 3若所有 t ?T 都是活的 , 就说 ?是活的 。 在实和标识 。 M 称 作 ?的 初 始 标 识 。 M : P ?{ 1 , 2 , 3 0 0 际的 Pet ri 网建模的过程中 ,要充分利用 Pet ri } 。 网的这些严格的定义为依据建立和验证系统模型 。定义 4 变迁发生条件 。 变迁的触动必须在标识 满足条件的情况下才能进 3 UML 和 Petri 网的建模应用 行 。设 M 为网系统 ?的基本网上的任一标识 , t ? T 这里以一个简单的运货机工 作 过 程 为 例 来 进 行 为任一变迁 〃〃〃〃U ML 和 Pet ri 的建模 。运货系统主要包括控制台 、左 ( ) 1t = t ?t 称为 t 的外延 。 右活动杆 、传送器 、机车 。前提假定所有设备能正常运 ( ) 2t 在 M 有发生权的条件是 : 〃〃 行 ,整个流程描述如下 :( ) ( ) ( ) Π p ?t : M p?W p , t ?Π p ?t : M p+ ( )1 控制台初始化 ;( ) ( ) W p , t ?K p ( ) 2控制台同时启动两个活动杆 ;t 在 M 有发生权记作 M [ t > 。 ()3 两个活动杆将货物抬起放入传送器 , 传送器定义 5 变迁发生结果 。 再将货物运入机车 ,一次传送完毕控制台从第一步开如果 M [ t > , 则 t 在 M 可以发生 , 将标识 M 改变 始继续传送 ,系统如图 1 所示 。为 M 的后继 M ’, M ’的定义如下 : () ) ”部分,其中还用到了消息的嵌套 ,即对象自身引用 自身的消息 ,在图中体现为系统的“初始化”。 图 3 消息的表示法 3 . 2 从 UML 顺序图到 Petri 网的转换 正如前面所提到的 U ML 是一种半形式化的建模 工具 ,通过建立顺序图很清晰地看到整个系统运行过 图 1 运货机工作流程图,但是还不能充分地验证系统的有效性 。Pet ri 网具程 3 . 1 类图和顺序图的建立有严格的数学定义和有效的 验 证 方 法 , 因 此 将 U ML ( 转换成 Pet ri 网以便验证运货系统模型的有效性 ,在此类图是对一组具有相同属性 、动作等对象类的具 针对图 4 进行转换 。) 体实例的总体描述 。类图能够比较直观地描述各对 象之间的关系 ,便于分析和设计系统 ,也为 动态模型的建立奠定了基础 。类图用矩形 表示 ,包括类名 、属性和动作 , 根据情况类 图中属性和动作可以省略 。对图 1 的货物 传送系统的 U ML 类图建模如图 2 所示 。 类图是一种静态图 , 因此系统具体的 运行情况在类图中并不能得到充分体现 , 要体现 系 统 的 运 行 情 况 应 该 采 用 动 态 建 模 ,动态建模在 U ML 中有多种 , 在这里采 用顺序图进行动态建模 。顺序图采用的二 维图关系主要体现对象之间基于时间的交 图 4 货物传送系统的 U ML 顺序图 互关系 ,在这个二维图中横向代表系统中所涉及的各在针对文中实例进行转化的过程中应遵循以下几 对象 ,纵向代表时间 ,对象的生命周期由其下方的生命 个规则 : 线表示 ,对象之间通过传递消息来进行交互 ,生命线之 () ( ) ( ) 1将顺序图中的消息“启动 ”、“带送货物 1 间的箭头表示消息的 传 递 , 表 示 方 法 如 图 3 所 示。( ) 和“入库 ”转换成一个基本的顺序 Pet ri 网 ,如图 5 中 通过顺序图可以很清晰地看到各对象之间执行的先后 虚框内的结构所示 。p2 到 p6 和 p3 到 p7 分别是启动 关系及交互关系 。图 4 为系统的顺序图建模 , 在该图 活动杆 1 和活动功杆 2 的过程 , 其中 p17 和 p18 是作 ( 中只用到了同步箭头和表示并行的箭头图中的“启动为条件存在 。p8 到 p12 和 p9 到 p13 是带动货物的过 程 。p14 到 p16 是入库的过程 。每个动作 都 有 开 始 5 处理和结束三个状态 ,状态之间由变迁过渡。 ( ) 2如果是嵌套调用动作 ,即对象自身调用自身的 ( ) 动作 ,处理方法跟 1一样 ,不过这里简化成一个库所 表示 ,即就是一个开始状态 。如图中 p1 。 () ( ) 3消息之间的转变 或者是传递由一个变迁表 示 ,如图中 t1 ,t4 ,t6 ,t14 ,t17 。 ( ) 4循环系统的起止状态用同一个库所表示 。 有时候所建立的 Pet ri 网模型外观上看上去非常 复杂 ,这样可读性差 , 分析的时候也容易出错 , 为了能 够看上去更简洁且保持系统的原本性质 ,根据 Pet ri 化 6 简方法,将图 5 最终化简为如图 6 所示 ,按理还可以 图 2 货物传送系统的 U ML 类图将图 6 进一步简化 ,但是为了能更清楚地了解系统的 运行过程就化简到此 。根据前面的定义 8 和定义 9 验,充分利用了 U ML 的的直观 、易懂的性质 , 分与设计 证该 Pet ri 网是可达的 、活的并且是有界的 , 所以这是 别用类图和顺序图描述了系统对象的结构组成以及它 一个有效的 Pet ri 网模型 。 们之间的动态行为关系 , 并且在此基础上结合了 Pet ri 网的具 有 严 格 数 学 定 义 和 有 效 的 验 证方法的特点 , 将 U ML 和 Pet ri 网有 机结合起 来 , 实 现 了 U ML 顺 序 图 到 Pet ri 网 的 转 化 。通 过 实 践 证 明 这 种 转化是有效的和可利用的 。 参考文献 : 1 徐宝文 ,周毓敏 ,卢红敏. U ML 与软件 建模 M .北 京 : 清 华 大 学 出 版 社 , 2006 :55 - 63 ;85 - 92 . 汪文元 ,沙基昌 ,谭东风. 基于 Pet ri 网的 U ML 活动图工作 图 5 货物运送系统的 Pet ri 网模型 2 ( ) 流程建模比较J . 系统仿真学报 ,2006 2:504 - 510 . 袁崇 义. Pet ri 网原理与应用 M . 北京 : 电子工业出版社 , 3 2005 :18 - 23 ;35 - 37 . 柯飞帆 ,宁宣熙. 基于 Pet ri 网和 U ML 的工作流模型设计 4 ( ) J . 南京航空航天大学学报 ,2006 2:121 - 1251 周长红. U ML 的 Pet ri 网 建 模 D . 青 岛 : 山 东 科 技 大 学 , 5 图 6 货物运送系统的 Pet ri 网简化模型 2004 :52 - 60 . 吴 哲 辉. Pet ri 网 导 论 M . 北 京 : 机 械 工 业 出 版 社 , 2006 : 6 167 - 169 . 结束语4 文中通过对一个简单的货物运输系统模型的分析 ()上接第 129 页 ( )( ) 3 如果 v > n 或 flag = 0 , 则转 9;,实现对 n 个元素依次入栈 , 求其全部的给出三种算法 ( )如果栈 stack 是空栈 , 则将第 w 个入栈序列符出栈序列 , 并对这三种算法进行了分析和研究 。由于当 4 , w + + ;n 很大时 , 求出所有出栈序列是一个不现实的问题 , 所 号入栈 ( ) 5如果 stack 栈顶元素值等于序列的第 v 个元 以如何判断一个序列是否为出栈序列显得更为重要 , ( ) ( ) 素 , 或者 w ? n 则转 7; 文中结合栈的性质给出一种时间复杂度为 O n的判 ( )转+ + , 断某一序列是否为出栈序列的算法 , 提高了程序的执 6 第 w 个入栈元素压入 stack 栈中 , w ( ) 5; 行效率 。下一步 ,将继续对栈的性质进行研究 ,探讨栈 ( )7 如果 stack 栈顶元素值等于序列的第 v 个元在其他领域中的应用 。 素 , 则匹配 , stack 栈顶元素出栈 , v + + ; 否则 ,说明所 参考文献 : 判断的序列不是出栈序列 ,赋 flag 为零 ; 1 卢开澄. 组合数学 M . 第 2 版. 北京 : 清华大学出版社 , ( ) ( ) 8转 3; 1991 :119 - 130 . () 9结束 ,若此时 flag 为 1 ,则序列为出栈序列 ,否 2 徐凤生. 出栈序列的性质及其求解新算法J . 计算机工程 则不是 。 ( ) 与应用 ,2006 ,42 5:66 - 68 . 将该算法替代算法 1 中的相应部分 , 称为改进后( ) 严蔚敏 ,吴伟民. 数据结构 C 语言版M . 北京 : 清华大 3 的算法 1 。从表 1 可以看出改进后的算法 1 ,在运行时 学出版社 ,1997 :152 - 155 . 间上比原算法大大缩短 ,甚至比算法 2 还要好 。 唐保祥. 栈序列及其生成算法J . 郑州大学学报 : 自然科 4 ( ) 学版 ,2001 ,33 4:33 - 35 . 5 范年柏 ,张大方 , 颜学义 , 等. 基于栈操作的用例规模的一 结束语4 ( ) 个计算公式J . 湖南大学学报 : 自然科学版 ,2004 ,31 6: 由前置 O 栈序列可构造出其对应的二叉树 , 用该 80 - 82 . 二叉树表示入栈和出栈操作比较直观 ,易于理解 ;文中