基于进程代数的系统性能评价方法综述

张小彬��严博��陈璐

摘要：现代通信网络系统中大量存在的各种并发同步事件，使得系统的性能特征与其功能特征密切相关，该类系统进行性能评价时，需要综合其性能模型与功能模型进行分析。由于进程代数具备功能推导和验证能力，通过有效扩展，融合相应的性能参数，可以成为理想的针对并发系统的性能建模工具。综述了进程代数的发展历史，并总结了将进程代数应用于性能评价的有效扩展方法，通过实例论述了进程代数应用于性能评价的一般过程。最后，讨论了基于进程代数的系统性能评价方法的发展趋势。

关键词关键词：进程代数；并发系统；性能评价；标记转移系统；随机过程

DOIDOI：10.11907/rjdk.143787

中图分类号：TP302

文献标识码：A文章编号文章编号：16727800（2015）002002503

基金项目基金项目：海军工程大学自然科学基金（435517D50）；湖北省自然科学基金（2013CFB441）；信息保障技术重点实验室开放基金（KJ13106）

作者简介作者简介：杨进（1983-），男，湖北宜昌人，海军南海舰队司令部工程师，研究方向为网络安全管理；张小彬（1981-），男，云南陆良人，硕士，海军南海舰队司令部工程师，研究方向为网络工程；严博（1984-），男，江西丰城人，海军工程大学信息安全系讲师，研究方向为信息与网络安全；陈璐（1979-）女，广东汕头人，博士，海军工程大学信息安全系讲师，研究方向为信息安全、可信计算。

0引言

随着现代通信网络系统规模的扩大以及结构复杂度的增加，尤其是系统中各种并发同步事件的大量存在，系统的功能特性与性能特性之间的界限已经越来越模糊。系统性能特征往往与其功能特征密切相关，因此对此类系统进行性能评价时，单纯的性能模型无法得出有效的结果，而需要结合系统功能模型进行综合考虑[1]。作为一种高级建模工具，进程代数可以很好地描述网络系统中常见的同步、并发、分布、冲突、资源调用，多被用于针对各种并发分布式系统的功能推导和验证。如果通过融合相应的性能参数，使进程代数能够同时刻画系统的功能模型和性能模型，那么进程代数就可以成为一种理想的分析网络、软件等各类复杂并发系统性能的工具。近年来，各种改进的进程代数模型不断推出，进程代数理论正在被越来越多地应用于网络、软件等各种复杂并发系统的性能评价中[24]，为这类系统的性能评价研究提供了一种新的思路和方法，并在一些工程领域中得到了应用。

1进程代数及其扩展形式

1.1进程代数概述

进程代数中的“进程”指系统的行为，系统是展示行为的系统，例如一个软件系统的执行、一个机器的动作等。“代数”指用代数或公理的方法进行讨论。因此，可以认为进程代数是用代数的方法研究系统行为的一门学科，是泛代数中的一种结构，满足特殊的公理集，其主要思想是将系统抽象成某种元素，用严格的语义描述系统及行为，并以确定的语法规则来演算系统的动态行为。

进程代数有很多种，其中主要的有Bergstra和Klop的ACP（Algebra of Communicating Processes）[5]，Hoara的CSP（Communication sequential Processes）[6]，Milner的CCS（Calculus of Communicating Systems）[7]和ISO的LOTOS（Language of Temporal Ordering Specifications）[8]等。这些进程代数的活动只有实施类型，没有联系时间，只能描述系统的功能特性，对系统功能进行定性分析。性能评价需要在详细描述系统结构的基础上，通过分析系统的动态行为，得到系统在时间或概率上的可量化性能指标。为了能利用进程代数对系统性能进行定量分析，通常采用的方法是在原有功能模型的基础上加入性能数量指标，使所得到的模型既能描述系统的行为，又能反映某些特定数量上的性能特征，这样就能得到统一的既可以进行功能分析，又可以进行性能分析的混合模型。

1.2进程代数的有效扩展

基于以上思想，产生了时间进程代数（Timed Process Algebra）和概率进程代数（Probabilistic Process Algebra）。例如，在时间进程代数TCCS（Temporal CCS）中，活动增加了取值为自然数的时间域，不仅可观察到一个进程执行的活动类型，也可观察到执行该活动的时间延迟；而在概率进程代数PCCS（Probabilistic CCS）中，则将不确定的选择用概率选择来代替，从而量化了不确定性。但无论是时间进程代数还是概率进程代数，都无法用来作为评价分析系统性能的工具，前者为活动附加的是一个确定的时间值，无法有效描述系统的各种随机性质；而后者则没有描述系统的时间特性，也无法用来对系统进行性能评价。为了将系统的随机性质、事件特性、功能特性有机结合，学者提出了随机进程代数。

2随机进程代数

随机进程代数的主要思想是将进程代数模型的每个动作都联系一个满足某种随机分布的延迟时间，进而通过各动作的随机行为分析系统性能，得到系统性能的量化指标。因为绝大多数系统行为都具备随机性，所以与时间扩展的进程代数和概率扩展的进程代数相比，随机进程代数更能精确描述系统行为。

最早将动作的随机性引入进程代数的是Nounou和Yemini两位学者，它们提出用指数分布来表示动作的延迟时间，但他们没有提出一套完整的进程代数形式化语义模型[9]。上世纪90年代，Herzog在进程代数CSP的基础上，首次提出了一种随机扩展的进程代数TIPP（TImed Process and Performance evaluation）[10]，之后经过多位学者不断地完善，最终形成了一种比较完整的随机进程代数语言。1994年，英国爱丁堡大学的Hillston教授[11]在她的博士论文《A Compositional Approach to Performance Modeling》中提出了一种性能评价进程代数（Performance Evaluation Process Algebra，PEPA），PEPA也是一种动作延迟时间服从于负指数分布的随机进程代数，PEPA在语法描述上与CCS类似，并具备完善的操作语义定义。目前，已有多种工具软件支持PEPA模型的自动推导和求解。

与经典的排队论模型和随机Petri模型不同，随机进程代数模型用一种组合的方法来描述和生成复杂的系统马尔可夫转移过程，随机进程代数独有的等价合并技术可有效压缩连续时间马尔可夫链（CTMC）一级的状态空间大小，从而可以在一定程度上解决系统在性能评价过程中的状态空间爆炸问题。

3基于进程代数的系统性能评价方法

3.1随机进程代数PEPA

PEPA是随机进程代数中非常有代表性的语言。在PEPA语法中，基本建模单位称为构件（component），整个系统由若干个构件组合而成，构件可以执行一系列活动（actions），并给每个活动指派一个负指数分布的随机变量，用于表现活动的持续时间（duration）或者称为时延（delay）。

假设系统可以观察到的所有动作集合为Obs，令A=Obs∪{τ}，表示所有动作的全集，a∈A，L∈Obs，γ∈R+，PEPA由以下语法定义产生：P∷=（a，γ）.P|P+Q|PQ|P/L|A上述定义可以看成是由系统所有构件的集合及定义在其上的5组操作算子构成的一个代数系统，这5组操作算子的含义如下：① （a，γ）.P代表前缀（Prefix）操作，构件（a，γ）.P执行活动a变成P，活动的执行时间呈参数γ的负指数分布；② P+Q代表选择（Choice）操作，表示系统要么执行进程P，要么执行进程Q；③ PQ代表合作（Cooperation）操作，表示两个进程P和Q的并发执行，其中活动集L是两个进程需要同步的动作；④ P/L代表隐藏（Hiding）操作，即P对集合L中的活动隐藏，这些活动被看成内部动作，不能被外部所观察到；⑤ A代表常量（Constant），定义方程A=P，表明A具有进程P一样的行为。PEPA模型需要借助操作语义来进行模型推导，以此产生与该模型对应的标记转移系统（labeled transition system，LTS），并利用其LTS隐含的马尔可夫转移关系，对模型进行证明与分析。PEPA操作语义的所有规则如下：

Prefix（a，r）.P（a，r）PChoiceP（a，r）P'P+Q（a，r）P'Q（a，r）Q'P+Q（a，r）Q'CooperationP（a，r）P'PQ（a，r）P'Q（aL）Q（a，r）Q'PQ（a，r）PQ'（aL）P（a，r1）P'Q（a，r2）Q'PQ（a，R）P'Q'（a∈L）whereR=r1ra（P）r2ra（Q）min（ra（P），ra（Q））HidingP（a，r）P'P/L（a，r）P'/L（aL）P（a，r）P'P/L（τ，r）P'/L（a∈L）ConstantQ（a，r）Q'P（a，r）Q'（P=Q）

3.2基于进程代数的系统性能评价

通过实例说明如何利用PEPA对系统进行性能评价。假设在一个只有1名医生的小诊所，每天都有很多病人来看病，病人（Patient）到达诊所后（come），医生（Doctor）为其诊断（diagnose），诊断完毕后医生将处方交给护士（prescribe），病人则到护士处领取药品后直接离开。这个系统可用如下随机进程代数语法描述：Patient = （come， λ1）.（diagnose， λ2）. PatientDoctor = （diagnose， λ3）. （prescribe， λ4）. DoctorSystem= PatientDoctor根据随机进程代数的操作语义，可推导该系统对应的带时间延迟的标记转移系统，如图1所示。

图1系统对应的带时间延迟的LTS

根据以上LTS的转移关系，可得到该系统共有4种状态，各状态对应的CTMC转移速率矩阵Q：

Q=-λ1λ1000-min（λ2，λ3）min（λ2，λ3）0λ40-λ1-λ4λ10λ40-λ4

假设系统的4种状态S1、S2、S3、S4的稳态概率分布为：p = （p1， p2， p3， p4），显然有：

p1+ p2+ p3+ p4=1 （1）

p·Q=0（2）

设λ1=2，λ2=6，λ3=5.5，λ4=8，将各参数的值带入到矩阵Q中，求解式（1）和式（2），可得系统的4种状态S1、S2、S3、S4的稳态概率分布为：p = （p1， p2， p3， p4） = （0.5659， 0.2572， 0.1415， 0.0354）。如要求出医生在工作时忙碌时间占总时间的比率，即构件Doctor的利用率，则需首先为系统的4种状态各自联系一个回报值，分别为：r1=0，r2=1，r3=1，r4=1，联合计算得到稳态概率分布，则可得出Doctor的利用率R为：

R = r1· p1+ r2· p2+ r3· p3+ r4· p4 = 0.4341如果要求医生在单位时间内完成诊断操作总数的期望值大小，即动作diagnose的吞吐量，则需为活动（diagnose，min（λ2， λ3））联系一个回报值，回报值的大小等于活动的执行速率，即min（λ2， λ3），反映到系统的4种状态上，则联系回报值分别为：r1=0，r2=5.5，r3=0，r4=0，联合计算得到的稳态概率分布，则可得动作diagnose的吞吐量T为：

T = r1· p1+ r2· p2+ r3· p3+ r4· p4 = 0.1446

4结语

目前，基于进程代数的系统性能评价方法主要有以下发展趋势：①大部分进程代数都是采用指数分布的形式来表示动作延迟时间的随机分布，在实际建模过程中具有一定局限性。因此，支持活动执行速率服从一般分布的进程代数有效扩展是面向性能评价的进程代数的一个重要研究方向；②部分研究人员尝试将进程代数理论与系统综合评价理论相结合。这种结合目前还比较简单，还有很大探索空间。这种结合方式，扩展了模型变迁形式，可有效优化组合系统状态，丰富进程代数在系统性能评价研究领域；③进程代数模型中存在各种逻辑和推导，对于结构简单的模型来说，通过人工进行分析工作量虽然不大，但对于结构复杂的模型，则需借助机器进行自动推导，因此需要开发对应的进程代数建模与分析工具；④进程代数理论性和逻辑性很强，只有在实际应用中才能体现其价值。目前，将进程代数理论应用于系统性能评价的研究虽进展较快，但真正在工程实践中成功应用的实例还不多见。因此，如何将先进的理论成果与方法应用到实际的工程领域中去还有待深入研究。

参考文献参考文献：

＼[1＼]吴尽昭，王永祥，覃广平.交互式马尔可夫链—并发系统的设计、验证与评价[M].北京：科学出版社，2007.

[2]严博，吴晓平，付钰.应用随机进程代数的网络系统可靠性预计方法研究[J]. 西安交通大学学报，2011，45（6）：4045.

[3]肖芳雄，李燕，黄志球，等.基于时间概率代价进程代数的Web服务组合建模和分析[J].计算机学报，2012，35（5）：918936.

[4]祝义，肖芳雄，周航，等. 一种嵌入式实时系统软件能耗建模与分析的方法[J].计算机研究与发展，2014，51（4）：846855.

[5]BAETEN J C M，WEIJLAN W P.Process algebra[M].New York：Cambridge University Press，1990.

[6]HOARE C. Communicating sequential processes[M].UK： Prentice Hall International Ltd， 1985.

[7]MILNER R.A calculus of communicating systems[M].New York：Springer，1980.

[8]BOLOGNESI T，BRINKSMA E.Introduction to the ISO specification language LOTOS[J].Computer Networks and ISDN systems，1987，14（1）：2529.

[9]HERMANNS H，HERZOG U， KATOEN J P.Process algebra for performance evaluation[J].Theoretical Computer Science，2002，274（12）：4387.

[10]HERZOG U.Formal description，time and performance analysis—a framework[J].Entwurfund Betrieb verteilter systeme，Informatik—Fachberichte，1990，264：172190.

[11]HILLSTON J. A compositional approach to performance modeling[D].Edinburgh：University of Edinburgh， 1994.

责任编辑（责任编辑：陈福时）