工作流系统模型的性能等价分析

《工作流系统模型的性能等价分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1000-9825/2002/13(08)1472-09©2002JournalofSoftware软件学报Vol.13,No.8工作流系统模型的性能等价分析á林闯,田立勤,魏丫丫(清华大学计算机科学与技术系,北京100084)E-mail:chlin@tsinghua.edu.cn;{lqtian,yywei}@csnet1.cs.tsinghua.edu.cnhttp://www.tsinghua.edu.cn摘要:讨论了基于随机Petri网的工作流系统的顺序、并行、选择、循环4种基本模型,并详细推导了这4种基本模型的性能等价公式.最后通过现实中

2、的一个工作流实例来说明如何建立相应的随机Petri网模型,以及如何利用这些性能等价公式来计算工作流的性能参数.给出了定量分析工作流系统性能的通用方法,通过用这些等价公式不仅可以对复杂的系统进行性能等价化简,而且还可以得到性能参数的乘积解.关键词:工作流;随机Petri网模型;性能等价;性能分析中图法分类号:TP302,TP391文献标识码:A[1,2]最近几年,工作流技术的研究和应用已引起了研究人员、开发人员和用户的普遍关注,诸如计算机支持的协同工作、无纸办公、表单传递、协作系统和办公自动化等.业务流程建模是工作流描述的重要内容,模型的性能评价是工作

3、流系统研究和应用的主要理论基础和支撑技术,因此对模型的性能分析是工作流的一个重[3~7]要研究内容.有很多文献讨论了工作流系统模型的性能,但都是针对工作流某一方面的特性来分析或改进工作流的性能,如文献[6]根据客户服务器这种工作流模型来对工作流的性能进行分析;文献[7]根据具有时间限制的这种工作流模型来对工作流的性能进行分析.本文则根据基于随机Petri网的工作流模型的顺序、并行、选择、循环4种基本结构,推导出由任意多个变迁组成的串联、并联、选择和循环结构的性能等价公式,给出了定量分析工作流系统性能的通用方法.这一技术除了可以应用在工作流系统中以外,

4、还可以广泛应用在诸如多媒体系统、计算机网络等模型的性能分析中.1工作流的4种基本随机Petri网模型及其性能等价公式的证明1.1模型及前提假定本文工作流模型的描述是基于随机Petri网的,且通常都假设工作流模型的变迁延时是服从指数分布函数的,因为这种假定本身是与现实多数系统实际相符合的.关于随机Petri网的更详细的内容,读者可参阅文献[8].[9]工作流主要由4种基本模型组成,即串联模型、并联模型、选择模型、循环模型.1.2工作流的串联随机Petri网模型及其性能等价公式的证明串联随机Petri网模型用来定义工作流中一系列按固定顺序执行的活动,如图

5、1左端所示,其中t1,t2,…,tn是n个串行执行的时间变迁.为了简化模型的复杂性,可将n个变迁进行性能等价化简,化简后的模型如图1右端á收稿日期:2001-11-26;修改日期:2002-03-13基金项目:国家自然科学基金资助项目(60173012,90104002);国家重点基础研究发展规划973资助项目(G1999032707);国家高科技研究发展计划资助项目(2001AA112080)作者简介:林闯(1948－),男,辽宁沈阳人,博士,教授,博士生导师,主要研究领域为系统性能评价,计算机网络,随机Petri网,逻辑推理模型;田立勤(1970

6、－),男,陕西定边人,讲师,主要研究领域为计算机网络,工作流模型,系统性能评价;魏丫丫(1979－),女,湖北荆州人,博士,主要研究领域为系统性能评价,计算机网络,随机Petri网.林闯等:工作流系统模型的性能等价分析1473所示.ttAftersimplification1t2nt●...●Fig.1ThesequentmodelbasedonstochasticPetrinetsanditsperformanceequivalentmodel图1基于随机Petri网的工作流的串联模型及其性能等价模型下面推导由n个变迁串联组成的系统的性能等价公式.

7、定理1.由n个变迁串联组成一个系统B,设这n个串联变迁的延时时间为n个相互独立的随机变量,且分111别服从参数为l1,l2,...,ln的指数分布函数,即n个变迁的平均延时时间分别为,,...,,则这n个变迁总的l1l2ln等价延时时间为n11=å.(1)li=1li证明:首先推导由两个变迁t1,t2组成的串联子系统B2的性能等价公式.为了求两个变迁串联的性能等价公式,将这两个变迁组成一个活的、标记守恒的分析系统,如图2所示,位置S1中设置了一个初始标记.ttS1S212●Fig.2Twotransitionsconsistofaactiveandt

8、okenconservationanalyticalsystem图2两个变迁串联组成一个活的、标记守恒的分析