下载文档原格式
![[分享]Petri网论文：基于Petri网的几个并发问题的建模与分析](https://img.taocdn.com/s1/m/17f1111903020740be1e650e52ea551810a6c9ba.png)
Petri网论文：基于Petri网的几个并发问题的建模与分析【中文摘要】Petri网不仅可以采用可视化图形描述而且可被形式化的数学方法所支持,是一种形式化、图形化的分布式系统建模和分析工具。
它不但能够精确地分析系统的静态特性,而且能够很好地分析系统的动态行为性质,从而很好地刻画系统的动态行为、分析系统的性能。
它既可采用形式化直观的图形表示,又可以引入许多数学方法对其性质进行分析与验证。
目前,大多数的软件系统都是并发系统,并发是衡量系统运行效率高低的一个参数标准。
为了达到“事半功倍”的效果,现在的系统环境越来越需要并发,只有这样才能更好地利用系统资源环境,才能使一个系统具有更强的竞争力。
Petri网作为一个优秀的形式化描述和分析工具,能很好地描述和分析这类系统。
采用软件形式化技术,不仅有利于开发人员之间的沟通,提高软件的可靠性,而且可以尽可能地缩短开发的总体时间,减少软件设计早期阶段的错误。
本文的主要工作如下:(1)在Petri网下对哲学家就餐问题模型进行了分析。
哲学家就餐问题是描述在共享资源下同步与并发的经典案例,活性与无饥饿性是求解此问题的前提,效率是基本要求。
由于对资源的竞争使几个哲学家不可能同时处于就餐状态,在考虑公平性的情况下定义了延迟Petri网...【英文摘要】Petri nets can not only use visual graphic description, but also can be supported by formal mathematical methods, it is a kind of formalized, graphical distributedsystem modeling and analysis tools. It can analyze system static characteristics accurately and analyze system dynamic behavior well, thereby good depicting system dynamic behavior and analyzing system performance. It may adopt formalized visual graphics and introduce many mathematical methods to analyze and verify its properties.At present, ...【关键词】Petri网异步并发形式化方法 S-不变量建模系统分析【英文关键词】Petri net Asynchronous concurrent Formal methods S-invariant Modeling System analysis。
基于Petri网的GSM/GPRS性能分析摘要：首先介绍了数字蜂窝移动通信中的语音通信业务，分析了语音通信各种行为所满足的分布函数。
接下来建立基于Petri 网的语音通信业务的模型，研究在3种通道共享机制控制下语音通信的性能。
最后利用TimeNET工具对模型加以分析和讨论。
关键词：GSM;GPRS;SCPN;通信模型0 引言在全球所有的第二代移动通信中，GSM通信网络的使用人数最多，由于最初的GSM标准主要是考虑支持语音业务和少量电路交换方式的数据业务，因此GSM网络的语音通信是电路交换方式。
20世纪90年代以后，随着互联网技术的迅猛发展，人们开始想到了移动互联网，希望能通过手机享受各种高速数据业务(包括收发Email、进行Internet浏览等)。
正是在这样的社会需求下，欧洲电信标准化组织(ETSI)及时在GSM系统的基础上制定了一套移动数据通信技术标准，使GSM与Internet相结合，重组的新网络称为通用分组无线业务(General Packet Radio Service，GPRS)。
该网络既有电路交换又有分组交换，后称2.5G 系统。
第三代数字蜂窝移动通信（3G）业务能同时提供电路切换服务和报文分组交换服务，这样自然会增加无线资源调制和系统模拟的复杂性。
本文将移动无线通信的性能评价和Petri网的建模与分析能力结合在一起，用直观的Petri网模型描述了系统的行为，根据不同的通道共享机制，利用TimeNET对模型加以分析和验证。
本文的核心是一个基站（BS）与多个移动站点（MS）之间的通信，所研究的通信类型是语音服务。
1 GSM/GPRS无线网GSM（Global System for Mobile Communications）是全球移动通讯系统，俗称"全球通"，是由欧洲开发的数字移动电话网络标准，它的开发目的是让全球各地共同使用一个移动电话网络标准，让用户使用一部手机就能行遍全球。
Microcomputer Applications V ol.27,No.8,2011开发应用微型电脑应用2011年第27卷第8期文章编号：1007-757X(2011)08-0047-03基于Petri 网的工作流模型时间性能分析潘海兰摘要：利用高效的建模技术来构建复杂的业务流程，一方面可以提高模型形式化表示的可读性，另一方面便于进行模型性能分析，确保模型在投入使用后的正确性。
阐述了利用Petri 网技术的严格语义，来构建流程模型并进行性能分析的过程。
首先指出时间性能对工作流性能分析的重要性，然后介绍了Petri 网和工作流网的定义、工作流基本路由结构的Petri 网表示，及其对应的性能等价公式，最后在这些基本定理的基础上，通过一个购车流程的实例来构建模型，并对其时间性能进行分析，证明了利用Petri 网技术建模的合理性和优越性。
关键词：工作流网；Petri 网；路由结构；建模；时间性能分析中图分类号：TP302文献标志码：A0引言目前，工作流管理技术已经应用于许多领域，它给企业的流程管理带来巨大的变革。
但是目前在工作流技术中还存在着许多需要解决和改进的问题，如异常处理、流程监控、流程重构等，而这些都与工作流模型的建立相关。
工作流建模是将企业业务流程进行抽象表示，并实现使用计算机进行处理，那么一个优秀的模型定义方式十分重要。
Petri 网是严格定义的数学模型，它具有规范的模型语义，同时Petri网还拥有许多成熟的分析技术和手段，有利于模型性能的分析和评价。
工作流的响应时间是衡量工作流过程优劣的重要指标，也是工作流系统中最重要的性能参数之一。
传统的时间性能分析大多是基于马尔可夫链的，其时间复杂度是指数级别的，很不实用，分析过程过于复杂[1]。
而利用Petri 网建立工作流网模型可以充分利用Petri 网技术进行形式化定义，结合概率论知识实现时间性能分析，降低时间复杂度。
1工作流的建模、分析和执行基于Petri 网的工作流网模型的性能分析大大提高了时间性能分析的复杂度，因此下面首先介绍它们的相关概念。
自动制造系统的Petri网结构分析和控制器设计自动制造系统的Petri网结构分析和控制器设计摘要：自动制造系统是现代工业中一种高度智能化和自动化的生产方式。
Petri网作为一种形式化描述和分析系统行为的工具，被广泛应用于自动制造系统中的建模和控制。
本文介绍了自动制造系统中的Petri网结构分析方法和控制器设计技术，并通过一个实例说明了其在实际应用中的有效性。
关键词：自动制造系统；Petri网；结构分析；控制器设计1.引言自动制造系统是现代工业中应用广泛的一种高度智能化和自动化的生产方式。
其核心目标是提高生产效率、降低成本，并保障产品质量。
为了实现这一目标，自动制造系统通常需要一个有效的控制系统来监测和调度各个生产环节，以实现流程的自动化控制。
Petri网作为一种形式化描述和分析系统行为的工具，被广泛应用于自动制造系统中的建模和控制。
2.Petri网的基本概念Petri网是Petri于1962年提出的一种描述系统并发行为的图形工具。
它由一组标记、过渡和弧线组成。
标记表示系统在某一时刻的状态，过渡表示系统的活动，弧线则表示标记和过渡之间的关联关系。
Petri网描述了系统状态在不同活动之间的转换关系，并且能够对系统的行为进行形式化的分析。
3.Petri网在自动制造系统中的应用在自动制造系统中，Petri网广泛应用于系统的建模和控制。
通过将自动制造系统抽象为Petri网，可以清晰地描述系统的各个组成部分以及它们之间的关系。
特别是在多任务的情况下，Petri网能够有效地处理不同任务之间的并发和冲突关系，提高系统的并行处理能力。
同时，Petri网的结构分析方法也可以帮助我们深入理解自动制造系统的行为，发现系统中的潜在问题，并进行系统性能的评估和优化。
4.Petri网结构分析方法Petri网的结构分析方法主要包括有向图分析、路径分析和状态空间分析。
有向图分析是最简单直观的分析方法，可以帮助我们了解Petri网的结构特征和系统行为。
基于Petri网的分析方法简述
摘要：对数学和图形进行描述和分析的工具很多，但能用良好的数学性质把一些复杂的现象（例如，同步、并发、分布、冲突、资源共享等）描述的直观、生动形象的工具很少，而Petri网就具有这些优点。
在分布式系统、信息系统、离散事件系统等领域，都可以利用Petri网对离散事件动态系统建模、规范分析和设计，而且非常好。
Petri网有很多分析方法，文章就作简要概述。
关键词：Petri网；Petri网语言；可达性；不变量；死锁
Petri网是一种计算模型，也是一种数学模型，最先是由德国的C.A.Petri教授提出来的，之后，得到了深入的研究，对于异步并发系统的描述和模拟，能用非常友好的图形表示出来。
友好的图形表示只是Petri网得到广泛应用的一个原因，更主要的原因是它的分析方法非常完备，而且这些方法对于分析和模拟系统的行为非常有效。
下面就简述一下其丰富的分析方法。
1Petri网语言
Petri网语言，是用来解决一个网系统中由于变迁而引发的序列问题。
这种通过变迁引发的序列，可以控制事件发生的顺序，从而对资源进行合理的配置和有效地调度。
最初Petri网语言的目的是利用这种变迁引发的序列来分析系统的行为，并通过其语言来进行计算和模拟，对于系统的设计能有效地进行控制和改进。
随着Petri网语言的发展，它在理论和应用方面都得到很好的应用，成为了Petri网的重要组成部分。
2可达树
Petri网是否可达如何判定，可以在一个网系统中设置一个标识，根据这个标识是否能够从初始标识可达来判定Petri网的可达性。
Petri网的很多问题都是通过可达性问题来进行分析的。
判定Petri网的可达性很难，但其可达性问题是可以判定的。
如何去判定？有很多方法，基其中之一是基于可达树或可覆盖树。
如果Petri网有界，那么可达树的节点就有限，其网系统的可达性就能够分析的非常准确。
如果Petri网无界，可达树的节点就无限，所以这样的可达树就没办法构造出来。
如果节点有限就可以判定，那么可构造一个可覆盖树，这个可覆盖树的节点是有限的，如何构造，可以在可达树中引入一个无界符号来解决。
但是这样的话一些不可达的标识也有可能出现在可覆盖树中，所以这时候可达性也解决不了。
所以，一般都用有界的Petri网来模拟现实系统。
所以，系统的行为可以根据可达树来分析。
3状态方程
用一个矩阵来表示Petri网结构，用一个向量来表示Petri网的标识，当然这个向量必须是非负整数。
这样的话，就可以用线性代数的方法即状态方程的方法来分析Petri网的性质。
如果Petri网的标识是可达的，那么它肯定满足状态方程。
反过来，如果Petri网中的标识满足状态方程，但它不一定可达。
造成这种情况出现的原因是“先借后还”，对于一些特殊的Petri网，其可达性与状态方程的可满足性等价，这样的话，其可达性就可以通过解方程来判定。
4基于Petri网结构性质的分析方法
不管是状态方程还是可达树，都关系到Petri网的初始标识，但也有可能遇到与初始标识无关的，但与网的结构有关的性质，所以网系统的一些性质可以通过T-不变量、可重复向量、死锁等方法来解决。
①T-不变量。
T-不变量反映的是网的这样一种性质：与这个T-不变量所对应的变迁序列引发之后，并不会改变每个库所中的托肯的数目。
也就是说这组变迁引发前后的标识一样。
这样，这组变迁序列按照原来的次序可重复、无限次地引发，因此，T-不变量与系统的活性有着紧密的联系。
T-不变量在通信系统的活性判定及通信协议的验证上有着很好的应用。
利用T-不变量可得出一个很漂亮的结论：根据规则与已知条件可推出某个结论，则Petri网中就存在一个相应的T-不变量，反之亦然。
现在大家关注的一个问题是关于T-不变量的求解。
其实。
一个T-不变量就是一个平凡的整数系数线性方程组的解。
然而，这个解要求是非负整数解（全零向量除外），这就给解方程组增加了很大的麻烦。
求解算法已经存在一些。
但比较经典的当属FM算法。
此算法简短，容易实现，是基于矩阵的初等变换，可以求出一组T-不变量。
而一个网的任一T-不变量都可由这组T-不变量非负有理数系数线性表出。
另外一些方法，也主要是基于FM 算法。
②可重复向量。
可重复向量是Petri网中的一个重要的结构性质之一，利用它可以表示这样的一组变迁，即当这组变迁引发后每个库所中的托肯数不减少的情况。
所以这种方法可以用来判定网是有界还是无界的。
活性的判定也可利用可重复向量作为一个必要条件。
前面介绍的T-不变量也是一种可重复向量，只不过具有特殊性。
可重复向量是一个不等式方程组的解，这个不等式方程要求是整数系数且具有线性，所以这个解也必须是非负整数解。
③死锁(siphon)。
死锁指的是某组库所的所有输入变迁都是它的输出变迁。
这种结构与网的活性联系比较紧密。
由此可见，在检测系统的活性及预防时死锁起着非常重要的作用。
利用死锁来分析Petri网，首先要找出此网的死锁。
目前已经存在一些求解算法。
最直接的就是枚举判断，然而这种方法的时间与空间复杂度都是指数级的。
因此，许多学者就去研究其他一些方法：基于不等式、逻辑方程、代数方法、结构特性、标号关联矩阵等。
还有其他一些方法，这些方法为死锁在Petri网分析中的应用提供了保障。
P-不变量与T-不变量是一对对偶的概念。
陷阱(trap)与死锁也是一对对偶的概念。
它们在Petri网的分析中也有着一定的应用，特别是经常利用死锁与陷阱相结合来分析Petri网的活性。
利用求解T-不变量与死锁的方法，可相应地去求解P-不变量与陷阱。
5其他分析方法
另外的一些分析方法。
像：网进程、网的分解与合成等，也经常被用到，也得到了一定的研究，在此不再叙述。
6结语
综上所述，Petri网的分析方法非常丰富，并且各有所长，这为Petri网的广泛应用提供了有力的支持。
参考文献：
[1] J.Peterson著.吴哲辉译.Petri网理论与系统模拟[M].徐州:
中国矿业大学出版社,1989.
[2] 蒋昌俊.离散事件动态系统的PN机理论[M].北京:科学出
版社,2O00.
[3] 蒋昌俊.Petri网的行为理论及其应用[M].北京:高等教育出
版社,2003.
[4] 吴哲辉.Petri网导论[M].北京:机械工业出版社,2006.
[5] 表崇义.Petri网原理及应用[M].北京:电子工业出版社,
2005.
[6] 昊哲辉.有界Petri网的活性与公平行的分析与实现[J].计
算机学报,1989,(7).。
