没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
CPN建模语言是一种通用建模语言,即它不是着重于为特殊类型系统建模,而是旨在实现一个广泛类型的并发系统的建模。典型的CP-nets应用领域包括通信协议,数据网,分布式算法及嵌入式系统。然而,CP-nets也适用于更广泛地以并发性和交互性为主要特点的系统建模。 本文介绍了CPN建模语言和如何使用CPN Tools中支持的构建、模拟、状态空间分析、性能分析,和可视化的说明。
资源推荐
资源详情
资源评论
目录
1 引言..........................................................................................................................................2
2 CPN 建模语言.........................................................................................................................4
2.1 网结构、声明、标注...................................................................................................4
2.2 变迁的使能与发生.......................................................................................................7
2.3 步骤、并发和冲突.....................................................................................................10
2.4 模块.............................................................................................................................12
2.5 时间建模.....................................................................................................................16
3 CPN 模型的构建...................................................................................................................21
3.1 GUI 概述.....................................................................................................................21
3.2 模型元素的构建.........................................................................................................23
3.3 层次模型构建.............................................................................................................25
3.4 语法检查和代码生成.................................................................................................26
3.5 图形化反馈与帮助.....................................................................................................26
4 模拟........................................................................................................................................27
5. 状态空间分析.......................................................................................................................31
5.1 为状态空间分析改进模型.........................................................................................31
5.2 完全状态空间.............................................................................................................32
5.3 状态空间报告.............................................................................................................34
5.4 查询函数.....................................................................................................................39
6 性能分析................................................................................................................................40
6.1 性能分析的赋时模型.................................................................................................40
6.2 性能测量和数据收集.................................................................................................42
6.3 统计.............................................................................................................................44
6.4 性能输出.....................................................................................................................46
6.5 进行模拟实验.............................................................................................................48
6.6 模型参数及对比配置.................................................................................................49
7 可视化....................................................................................................................................50
7.1 消息序列图.................................................................................................................50
7.2 交互图形.....................................................................................................................51
8 结论........................................................................................................................................52
鸣谢...........................................................................................................................................53
参考文献...................................................................................................................................53
用于并发系统建模和验证的
着色 Petri 网及其工具软件 CPN Tools
Kurt Jensen, Lars Michael Kristensen, Lisa Wells
Department of Computer Science
University of Aarhus
IT-Parken, Aabogade 34, DK-8200 Aarhus N, DENMARK
1
e-mail: {kjensen,lmkristensen,wells}@daimi.au.dk
摘要:着色Petri网(CPNs)是一个用于建模和验证系统的语言,在这些系统中并发性、交互
性和同步性扮演着主要角色。着色Petri网是一种把Petri网与功能编程语言Standard ML结合
起来的离散事件建模语言。Petri网为建模提供图形注释以及并发性、交互性、和同步性的基本
的原语基础。Standard ML为数据类型定义、数据操作描述、创建紧凑的可参数化的模型提供
基本原语。一个系统的CPN模型是一个代表着系统状态和事件(变迁)的可执行模型,事件可
导致系统改变状态。CPN语言使一组模块来构件一个模型成为可能,这里面包括一种时间概念,
这种时间概念又使在被建模的系统中,表示处理事件所花费的时间成为可能。
CPN Tools,是一个为构建和分析CPN模型的工业价值的计算机工具。使用CPN Tools,
可以实现用模拟的方法调查被建模的系统的行为,借助状态空间方法和模型检查来验证性能,
进行基于模拟的性能分析。用户与CPN Tools交互,是基于对采用交互技术的图形表示的CPN
模型的直接操纵,如工具面板和(状态)标记菜单。工具的功能可以通过用户定义的
Standard ML功能来扩展。 CPN Tools的许可证可以免费得到,也用于商业用途。
关键词:着色Petri网,行为建模,确认,模拟,验证,状态空间方法,模型检查,性能分析,
可视化。
1 引言
系统工程是一门综合性学科,涉及各式各样的活动,例如需求工程、设计、规范化、实现、
测试与部署。开发分布式系统是特别具有挑战性的,主要原因是这些系统具备并发性和非确定
性,即此种系统的执行有许多不同的方式。这是极其容易使设计师在设计这种系统时错过一些
重要的交互模式,并导致在系统设计中出现功能偏差或错误。为了应对现代并行系统复杂性,
提供能在实现和部署之前,进行系统设计中中央部分的调试和测试的方法至关重要。
其中一个开发并行系统的富有挑战性的方法,就是要建立一个可执行的系统模型。构建模
型并模拟,通常可以使一些新见解被纳入系统设计和运行中,而且往往会导致一个更简单和更
精简的设计的产生。此外,构建一个可执行的模型通常会产生一个更完整的系统规范,便于场
景的系统化调查,这可显著降低设计中错误的数量。
着色Petri网(CP-nets或CPNs)[16,17,19,24] 是一种图形语言,用于为并发系统
构建模型,并分析其性能。CP-nets 是一个与Petri网[30]结合的离散事件建模语言,其功能性
编程语言CPN ML是基于Standard ML [33,34]的。CPN建模语言是一种通用建模语言,即
它不是着重于为特殊类型系统建模,而是旨在实现一个广泛类型的并发系统的建模。典型的
CP-nets应用领域包括通信协议[5],数据网[4],分布式算法[31],及嵌入式系统。然而,CP-
nets也适用于更广泛地以并发性和交互性为主要特点的系统建模。这类系统的例子有商业流程
与工作流建模〔36〕,制造系统[11]和代理系统。在不同工业领域的CPN应用的例子可以通过
[12] 得到。文献[19,25]给出了实际使用CP-nets的入门性介绍。
一个系统的CPN模型阐述了系统的状态和导致系统改变状态的事件(变迁)。通过CPN模
型的模拟,可以研究系统的不同场景,并探讨系统的行为特性。通常情况下,模拟的目的是调
试和研究系统的设计问题。CP-nets可以被交互的或自动的模拟。交互式模拟类似与单步调试。
它提供了一种方式,以“单步通过”(walk through)CPN模型,调查不同的场景并且检查模型
是否达到预期的效果。在一个交互的模拟过程中,建模人员通过在当前状态下使能的事件中做
出选择控制,并决定下一步该怎么做。可以在图形上直接观察CPN模型的单步运行效果。自动
2
模拟则类似于程序执行。目的是为了尽可能快地对模型进行模拟,其典型应用就是对模型进行
测试和性能分析。为了测试,建模人员通常设立适当的断点和停止运行的条件。为了进行性能
分析,模型需要有数据收集器,来搜集与系统的性能有关的信息。
在大量的并行系统中时间起着着重要作用。有些系统的正确运作关键取决于某些活动所占
用的时间,而且不同的设计决策都对系统的性能产生重大的影响。CP-nets包括一个时间概念,
使之能够捕捉在系统中执行活动所花费的时间。该时间概念也意味着CP-nets,可用于为基于
模拟技术的性能分析,研究影响系统性能的度量指标,如系统中的延迟、吞吐量、和队列长度,
也可以用于实时系统建模和验证。
CPN模型可以构造一系列模块来处理大规格的系统规范。这些模块通过一套定义完善的接
口相互交互,并用类似编程的方法来进行组织。CP-nets的模块概念是基于一个分层结构机制,
允许每一个模块有子模块,而且可以用一组模块来组成新的模块。
可视化是一项技术,该技术利用高层次的图形来生动的刻画CPN模型的行为,而且它与模
拟CPN模型密切相关。一个可视化的重要的应用是,它允许用应用领域的概念展示设计思路和
分析结果。这一点在与一般对CP-nets不熟悉的人和同事讨论时尤为重要。在CPN模型的顶层
增加特定领域图形的方法有许多,可用于在应用领域内从理论上展示CPN模型的执行。其中一
个例子是利用消息序列图(时间序列图)[7]在通信协议的执行中显示交换消息。
CPN模型是形式化的-本质上来说,CPN建模语言中有其语法和语义的数学定义。这意味着
他们可以用来验证系统特性,即证明某些需要的属性可以达到,或某些不需要的属性保证不会
出现。检查系统的特性是由一系列状态空间方法支持的。基础状态空间的基本思路是计算所有
可能达到的状态和有关CPN模型状态的变化,并以一个有向图表示这些变化,图中节点代表的
状态,弧代表发生的事件。状态空间可以完全自动构造。通过一个构造的状态空间回答一个系
列与系统行为有关的检查问题是有可能的,如有无死锁。即是否总是可以达到某种给定的状态,
并保证提供某项服务的可能性。CP-nets的状态空间方法也可应用于赋时的CP-nets。因此,
它也可以通过赋时CP-nets建模来验证系统功能的正确性。
应该强调指出的,为CP-nets以及他们支持的计算机工具的实际使用,需要对CPN建模语
言的语法和语义有一个直观的了解,这有点类似于普通的编程语言,如JAVA,可以被不熟悉这
种语言的形式化定义的编程人员所成功的应用。这里强调了一个重要的特性,那就是CP-nets
可以不用研究相关的正式定义就可以被教授和学习。
CPN建模和分析的实际应用,必须依赖于支持创建并操作模型的电脑辅助工具的存在。
CPN Tools[10]是一个关于CPN模型的编辑、模拟、状态空间分析和特性分析的工具套件。它
是现在在100多个不同的国家有4000多个经过许可的用户,并可用于MS Windows和Linux操
作系统。CPN Tools的用户直接工作于图形表示的CPN模型。CPN Tools的图形用户界面
(GUI)没有传统菜单栏和下拉式菜单,但是基于交互技术,如工具面板(tool palettes)和
状态菜单(marking menus)。CPN Tools的许可证可通过CPN Tools的网页免费获得
[10]。
本文简要介绍了CPN建模语言和如何使用CPN Tools中支持的构建、模拟、状态空间分析、
性能分析,和可视化的说明。第2节介绍CPN建模语言的概念。第3节说明如何建造CPN Tools
支持的CPN模型。第4节显示模拟是如何被支持的。第5节给出了状态空间方法的简要的介绍,
并说明了他们在CPN Tools中是如何被支持的。第6节介绍了基于模拟的性能分析的基本思想,
并说明它是如何被CPN Tools支持的。第7节说明CPN Tools是如何支持领域可视化的。最后,
第8节总结本文并提供参考文献,以进一步对CPN建模语言、实例分析、和CPN Tools的使用
进行学习。
读者指南
没有必要阅读完整篇文章或熟悉Standard ML后才开始使用CP-nets和CPN Tools。如果
3
只是了解基本内容,阅读以下的内容就足够了:CP-nets的非层次概念的介绍(Sects. 2.1-
2.3),CPN Tools和构造非等级模型的工具的介绍(Sects. 3.1-3.2 and 3.4-3.5),如何模拟
CP-nets模型(Sect. 4)。关于CPN ML的基本介绍和一些实例,以及如何使用CPN ML,都可
以在CPN Tools的帮助页面查找(也可以通过网上查找[10])。
对于熟悉基本的CP-nets和CPN Tools的读者,文章中其余的章节的是目前较高级的课题。
分层的CP-nets在2.4节中介绍。以及构建层次模型工具在3.3节介绍。如果读者对性能分析感
兴趣,就应该阅读关于赋时的CP-nets的介绍(第2.5节)。第6节是关于性能分析的。状态空
间分析和可视化分别在第5节和第7节中介绍。不需要为了使用性能、状态空间和可视化设备的
基本特征而对Standard ML有一个良好的认识。但是,要想对这些设施更先进的功能进行有效
的使用,就必须要了解Standard ML。又比如,帮助页面提供了相当多的例子,并且说明了
Standard ML是如何被用于支持高级分析技术。
2 CPN 建模语言
在本节中我们通过一个小例子介绍了CPN建模语言,模型是对通信协议的建模。我们使用
一个简单的协议,因为它容易解释和理解,而且因为它涉及到并发性、不确定性、通信和同步,
这是并发系统的关键特点。协议本身不复杂,但对于说明CPN模型语言的构建是足够的。读者
不需要对协议的相关知识有一定的基础。
简单的协议包括一个发送器(sender),传输若干的数据包(data packets)到一个接
收器(receiver)。通信发生在一个不可靠的网络,即数据包可能会丢失而且超越也是可能的。
协议利用序列号、确认和重传技术以确保数据包被准确传输,并且没有重复传输,而且在传输
结束后数据包的顺序是正确的。该协议使用“停止-并-等待”策略,即,相同的数据包的传输直到
收到相应确认。被传输的数据包中包括一个序列号及数据(有效载荷)。确认包括一个序列号,
用于指明接收器期望的下一个数据包的编号。
2.1 网结构、声明、标注
一个CPN模型通常是像绘制图形一样被创建出来,图1展示了协议的基本CPN模型。左面
的部分为发送器建模,中间部分为网络建模,右边的部分为接收器建模。该CPN模型包含了8
个库所(places)(形状和圆一样),5个变迁(transitions)(形状为矩形盒),还有一些
直接连接库所和变迁的弧(arcs),最后是一些靠近库所、变迁、弧的标注
(inscriptions)。这些标注在CPN ML编程语言中有记录,它是Standard ML语言的扩展。
库所和变迁被称为节点(nodes)。与直接弧一起,他们构成了网结构(net structure)。
一个弧总是把一个库所连接到一个变迁或把一个变迁连接到一个库所。在两个同类的节点间是
不允许有弧的,即在两个库所间或两个变迁间都不允许有弧。
建模系统的状态是由库所代表的。每个库所都可以被一个或一个以上令牌(tokens)标识,
而且每个令牌自身都附有一个数据值,这个数据值是所谓的令牌颜色(token colour)。在每
一个单独的库所里的令牌数量和令牌颜色合起来,构成了系统的状态(marking)。在一个特
定库所上的令牌数构成了那个库所的状态。按照惯例,我们在椭圆形内写库所的名字。这些名
字本身没有规范的意义-但他们对CPN模型的可读性具有重要实际意义(就像在传统的编程中使
4
用助记符一样)。发送器(Sender)的状态是由两个库所PacketsToSend和NextSend 建模
的。接收器(Receiver)的状态是由两个库所DataReceived和NextRec建模的,而网络的
状态是由库所A、B、C和D建模的。
在每一个库所附近,都有一个标注决定了在此库所的令牌允许使用的令牌颜色集(数据
值)。一个可能的令牌颜色集是由一个类型(如已知的编程语言的类型)指定的,它被称库所
的颜色集。按照惯例,颜色集是写在库所下面的。库所NextSend,NextRec,C和D有颜色
集NO。在CPN Tools中,颜色集是使用CPN ML关键字colset定义的,并且颜色集NO被定义
和整数类型等价:
int:
colset NO = int;
这意味着在四个库所NextSend、NextRec、C和D将有一个整数作为他们的令牌颜色。颜色
集NO被用来为建模协议中的序列号。在工具中,整数类型的大小,将取决于编写这种工具的
编程语言。例如,在CPN Tools中int 类型是31位整数。库所DataReceived 的颜色集 DATA
被定义为包含所有的文本内容的字符串。颜色集DATA是用来为数据包的有效载荷建模的。其
余的3个库所有颜色集NOxDATA,它定义为NO 的类型和DATA的积。该类型包含所有第一个
要素是一个整数而且第二个要素是一个文本串的两元组。元组用是逗号分割的列表加括号
(和)书写的。颜色集NOxDATA是用来为数据包建模的,这些数据包包括一些顺序号和一些
数据。颜色集的定义如下:
colset DATA = string;
colset NOxDATA = product NO * DATA;
每一个库所旁边,我们看到另一个标注,该标注决定这个库所的初始状态(initial
marking)。最初的原始库所的状态,按照惯例都是写在库所的上面的。举例来说,在库所
NextSend右上方的标注标明库所的原始状态是由一个有带颜色(值)的1个令牌构成的。这表
明,我们希望数据包1作为第一个被传送的数据包。类似地,库所NextRec也有一个初始的状
态,它包括一个带有颜色1的单一令牌。这表明接收器最开始期望接受标号为1 的数据包。库
所DataReceived 有一个初始的状态,这个状态包括一个带有颜色””牌(这是空的文本串)。
5
剩余54页未读,继续阅读
资源评论
- yx_yt2018-01-03很好哦,正需要使用,谢谢分享!
- qq_356945182017-10-04正在使用,谢谢分享
- qq_182838472017-12-06不错,谢谢啦
- 学不会的白羊梦2016-09-06正需要使用,谢谢分享!
HK-fly
- 粉丝: 5
- 资源: 6
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 图像处理中的White Patch算法来实现白平衡,MATLAB实现
- Python 爬虫:把廖雪峰的教程转换成 PDF 电子书
- 2024 年 Java 开发人员路线图.zip
- matplotlib-3.7.5-cp38-cp38-win-amd64.whl
- Android TV 开发框架: 包含 移动的边框,键盘,标题栏
- 图像处理中白平衡算法之一的灰度世界算法的MATLAB实现
- Cython-3.0.10-cp38-cp38-win-amd64.whl
- zotero安卓版"Zotero Beta"版本1.0.0-118
- Web应用项目开发的三层架构
- 基于QT和OpenCV的Mask编辑工具(python源码)
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功