基于進程代數(shù)的系統(tǒng)性能評價方法綜述

張小彬??嚴博??陳璐

摘要：現(xiàn)代通信網(wǎng)絡(luò)系統(tǒng)中大量存在的各種并發(fā)同步事件，使得系統(tǒng)的性能特征與其功能特征密切相關(guān)，該類系統(tǒng)進行性能評價時，需要綜合其性能模型與功能模型進行分析。由于進程代數(shù)具備功能推導和驗證能力，通過有效擴展，融合相應的性能參數(shù)，可以成為理想的針對并發(fā)系統(tǒng)的性能建模工具。綜述了進程代數(shù)的發(fā)展歷史，并總結(jié)了將進程代數(shù)應用于性能評價的有效擴展方法，通過實例論述了進程代數(shù)應用于性能評價的一般過程。最后，討論了基于進程代數(shù)的系統(tǒng)性能評價方法的發(fā)展趨勢。

關(guān)鍵詞關(guān)鍵詞：進程代數(shù)；并發(fā)系統(tǒng)；性能評價；標記轉(zhuǎn)移系統(tǒng)；隨機過程

DOIDOI：10.11907/rjdk.143787

中圖分類號：TP302

文獻標識碼：A文章編號文章編號：16727800（2015）002002503

基金項目基金項目：海軍工程大學自然科學基金（435517D50）；湖北省自然科學基金（2013CFB441）；信息保障技術(shù)重點實驗室開放基金（KJ13106）

作者簡介作者簡介：楊進（1983-），男，湖北宜昌人，海軍南海艦隊司令部工程師，研究方向為網(wǎng)絡(luò)安全管理；張小彬（1981-），男，云南陸良人，碩士，海軍南海艦隊司令部工程師，研究方向為網(wǎng)絡(luò)工程；嚴博（1984-），男，江西豐城人，海軍工程大學信息安全系講師，研究方向為信息與網(wǎng)絡(luò)安全；陳璐（1979-）女，廣東汕頭人，博士，海軍工程大學信息安全系講師，研究方向為信息安全、可信計算。

0引言

隨著現(xiàn)代通信網(wǎng)絡(luò)系統(tǒng)規(guī)模的擴大以及結(jié)構(gòu)復雜度的增加，尤其是系統(tǒng)中各種并發(fā)同步事件的大量存在，系統(tǒng)的功能特性與性能特性之間的界限已經(jīng)越來越模糊。系統(tǒng)性能特征往往與其功能特征密切相關(guān)，因此對此類系統(tǒng)進行性能評價時，單純的性能模型無法得出有效的結(jié)果，而需要結(jié)合系統(tǒng)功能模型進行綜合考慮[1]。作為一種高級建模工具，進程代數(shù)可以很好地描述網(wǎng)絡(luò)系統(tǒng)中常見的同步、并發(fā)、分布、沖突、資源調(diào)用，多被用于針對各種并發(fā)分布式系統(tǒng)的功能推導和驗證。如果通過融合相應的性能參數(shù)，使進程代數(shù)能夠同時刻畫系統(tǒng)的功能模型和性能模型，那么進程代數(shù)就可以成為一種理想的分析網(wǎng)絡(luò)、軟件等各類復雜并發(fā)系統(tǒng)性能的工具。近年來，各種改進的進程代數(shù)模型不斷推出，進程代數(shù)理論正在被越來越多地應用于網(wǎng)絡(luò)、軟件等各種復雜并發(fā)系統(tǒng)的性能評價中[24]，為這類系統(tǒng)的性能評價研究提供了一種新的思路和方法，并在一些工程領(lǐng)域中得到了應用。

1進程代數(shù)及其擴展形式

1.1進程代數(shù)概述

進程代數(shù)中的“進程”指系統(tǒng)的行為，系統(tǒng)是展示行為的系統(tǒng)，例如一個軟件系統(tǒng)的執(zhí)行、一個機器的動作等?！按鷶?shù)”指用代數(shù)或公理的方法進行討論。因此，可以認為進程代數(shù)是用代數(shù)的方法研究系統(tǒng)行為的一門學科，是泛代數(shù)中的一種結(jié)構(gòu)，滿足特殊的公理集，其主要思想是將系統(tǒng)抽象成某種元素，用嚴格的語義描述系統(tǒng)及行為，并以確定的語法規(guī)則來演算系統(tǒng)的動態(tài)行為。

進程代數(shù)有很多種，其中主要的有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]等。這些進程代數(shù)的活動只有實施類型，沒有聯(lián)系時間，只能描述系統(tǒng)的功能特性，對系統(tǒng)功能進行定性分析。性能評價需要在詳細描述系統(tǒng)結(jié)構(gòu)的基礎(chǔ)上，通過分析系統(tǒng)的動態(tài)行為，得到系統(tǒng)在時間或概率上的可量化性能指標。為了能利用進程代數(shù)對系統(tǒng)性能進行定量分析，通常采用的方法是在原有功能模型的基礎(chǔ)上加入性能數(shù)量指標，使所得到的模型既能描述系統(tǒng)的行為，又能反映某些特定數(shù)量上的性能特征，這樣就能得到統(tǒng)一的既可以進行功能分析，又可以進行性能分析的混合模型。

1.2進程代數(shù)的有效擴展

基于以上思想，產(chǎn)生了時間進程代數(shù)（Timed Process Algebra）和概率進程代數(shù)（Probabilistic Process Algebra）。例如，在時間進程代數(shù)TCCS（Temporal CCS）中，活動增加了取值為自然數(shù)的時間域，不僅可觀察到一個進程執(zhí)行的活動類型，也可觀察到執(zhí)行該活動的時間延遲；而在概率進程代數(shù)PCCS（Probabilistic CCS）中，則將不確定的選擇用概率選擇來代替，從而量化了不確定性。但無論是時間進程代數(shù)還是概率進程代數(shù)，都無法用來作為評價分析系統(tǒng)性能的工具，前者為活動附加的是一個確定的時間值，無法有效描述系統(tǒng)的各種隨機性質(zhì)；而后者則沒有描述系統(tǒng)的時間特性，也無法用來對系統(tǒng)進行性能評價。為了將系統(tǒng)的隨機性質(zhì)、事件特性、功能特性有機結(jié)合，學者提出了隨機進程代數(shù)。

2隨機進程代數(shù)

隨機進程代數(shù)的主要思想是將進程代數(shù)模型的每個動作都聯(lián)系一個滿足某種隨機分布的延遲時間，進而通過各動作的隨機行為分析系統(tǒng)性能，得到系統(tǒng)性能的量化指標。因為絕大多數(shù)系統(tǒng)行為都具備隨機性，所以與時間擴展的進程代數(shù)和概率擴展的進程代數(shù)相比，隨機進程代數(shù)更能精確描述系統(tǒng)行為。

最早將動作的隨機性引入進程代數(shù)的是Nounou和Yemini兩位學者，它們提出用指數(shù)分布來表示動作的延遲時間，但他們沒有提出一套完整的進程代數(shù)形式化語義模型[9]。上世紀90年代，Herzog在進程代數(shù)CSP的基礎(chǔ)上，首次提出了一種隨機擴展的進程代數(shù)TIPP（TImed Process and Performance evaluation）[10]，之后經(jīng)過多位學者不斷地完善，最終形成了一種比較完整的隨機進程代數(shù)語言。1994年，英國愛丁堡大學的Hillston教授[11]在她的博士論文《A Compositional Approach to Performance Modeling》中提出了一種性能評價進程代數(shù)（Performance Evaluation Process Algebra，PEPA），PEPA也是一種動作延遲時間服從于負指數(shù)分布的隨機進程代數(shù)，PEPA在語法描述上與CCS類似，并具備完善的操作語義定義。目前，已有多種工具軟件支持PEPA模型的自動推導和求解。

與經(jīng)典的排隊論模型和隨機Petri模型不同，隨機進程代數(shù)模型用一種組合的方法來描述和生成復雜的系統(tǒng)馬爾可夫轉(zhuǎn)移過程，隨機進程代數(shù)獨有的等價合并技術(shù)可有效壓縮連續(xù)時間馬爾可夫鏈（CTMC）一級的狀態(tài)空間大小，從而可以在一定程度上解決系統(tǒng)在性能評價過程中的狀態(tài)空間爆炸問題。

3基于進程代數(shù)的系統(tǒng)性能評價方法

3.1隨機進程代數(shù)PEPA

PEPA是隨機進程代數(shù)中非常有代表性的語言。在PEPA語法中，基本建模單位稱為構(gòu)件（component），整個系統(tǒng)由若干個構(gòu)件組合而成，構(gòu)件可以執(zhí)行一系列活動（actions），并給每個活動指派一個負指數(shù)分布的隨機變量，用于表現(xiàn)活動的持續(xù)時間（duration）或者稱為時延（delay）。

假設(shè)系統(tǒng)可以觀察到的所有動作集合為Obs，令A=Obs∪{τ}，表示所有動作的全集，a∈A，L∈Obs，γ∈R+，PEPA由以下語法定義產(chǎn)生：P∷=（a，γ）.P|P+Q|PQ|P/L|A上述定義可以看成是由系統(tǒng)所有構(gòu)件的集合及定義在其上的5組操作算子構(gòu)成的一個代數(shù)系統(tǒng)，這5組操作算子的含義如下：① （a，γ）.P代表前綴（Prefix）操作，構(gòu)件（a，γ）.P執(zhí)行活動a變成P，活動的執(zhí)行時間呈參數(shù)γ的負指數(shù)分布；② P+Q代表選擇（Choice）操作，表示系統(tǒng)要么執(zhí)行進程P，要么執(zhí)行進程Q；③ PQ代表合作（Cooperation）操作，表示兩個進程P和Q的并發(fā)執(zhí)行，其中活動集L是兩個進程需要同步的動作；④ P/L代表隱藏（Hiding）操作，即P對集合L中的活動隱藏，這些活動被看成內(nèi)部動作，不能被外部所觀察到；⑤ A代表常量（Constant），定義方程A=P，表明A具有進程P一樣的行為。PEPA模型需要借助操作語義來進行模型推導，以此產(chǎn)生與該模型對應的標記轉(zhuǎn)移系統(tǒng)（labeled transition system，LTS），并利用其LTS隱含的馬爾可夫轉(zhuǎn)移關(guān)系，對模型進行證明與分析。PEPA操作語義的所有規(guī)則如下：

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基于進程代數(shù)的系統(tǒng)性能評價

通過實例說明如何利用PEPA對系統(tǒng)進行性能評價。假設(shè)在一個只有1名醫(yī)生的小診所，每天都有很多病人來看病，病人（Patient）到達診所后（come），醫(yī)生（Doctor）為其診斷（diagnose），診斷完畢后醫(yī)生將處方交給護士（prescribe），病人則到護士處領(lǐng)取藥品后直接離開。這個系統(tǒng)可用如下隨機進程代數(shù)語法描述：Patient = （come， λ1）.（diagnose， λ2）. PatientDoctor = （diagnose， λ3）. （prescribe， λ4）. DoctorSystem= PatientDoctor根據(jù)隨機進程代數(shù)的操作語義，可推導該系統(tǒng)對應的帶時間延遲的標記轉(zhuǎn)移系統(tǒng)，如圖1所示。

圖1系統(tǒng)對應的帶時間延遲的LTS

根據(jù)以上LTS的轉(zhuǎn)移關(guān)系，可得到該系統(tǒng)共有4種狀態(tài)，各狀態(tài)對應的CTMC轉(zhuǎn)移速率矩陣Q：

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

假設(shè)系統(tǒng)的4種狀態(tài)S1、S2、S3、S4的穩(wěn)態(tài)概率分布為：p = （p1， p2， p3， p4），顯然有：

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

p·Q=0（2）

設(shè)λ1=2，λ2=6，λ3=5.5，λ4=8，將各參數(shù)的值帶入到矩陣Q中，求解式（1）和式（2），可得系統(tǒng)的4種狀態(tài)S1、S2、S3、S4的穩(wěn)態(tài)概率分布為：p = （p1， p2， p3， p4） = （0.5659， 0.2572， 0.1415， 0.0354）。如要求出醫(yī)生在工作時忙碌時間占總時間的比率，即構(gòu)件Doctor的利用率，則需首先為系統(tǒng)的4種狀態(tài)各自聯(lián)系一個回報值，分別為：r1=0，r2=1，r3=1，r4=1，聯(lián)合計算得到穩(wěn)態(tài)概率分布，則可得出Doctor的利用率R為：

R = r1· p1+ r2· p2+ r3· p3+ r4· p4 = 0.4341如果要求醫(yī)生在單位時間內(nèi)完成診斷操作總數(shù)的期望值大小，即動作diagnose的吞吐量，則需為活動（diagnose，min（λ2， λ3））聯(lián)系一個回報值，回報值的大小等于活動的執(zhí)行速率，即min（λ2， λ3），反映到系統(tǒng)的4種狀態(tài)上，則聯(lián)系回報值分別為：r1=0，r2=5.5，r3=0，r4=0，聯(lián)合計算得到的穩(wěn)態(tài)概率分布，則可得動作diagnose的吞吐量T為：

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

4結(jié)語

目前，基于進程代數(shù)的系統(tǒng)性能評價方法主要有以下發(fā)展趨勢：①大部分進程代數(shù)都是采用指數(shù)分布的形式來表示動作延遲時間的隨機分布，在實際建模過程中具有一定局限性。因此，支持活動執(zhí)行速率服從一般分布的進程代數(shù)有效擴展是面向性能評價的進程代數(shù)的一個重要研究方向；②部分研究人員嘗試將進程代數(shù)理論與系統(tǒng)綜合評價理論相結(jié)合。這種結(jié)合目前還比較簡單，還有很大探索空間。這種結(jié)合方式，擴展了模型變遷形式，可有效優(yōu)化組合系統(tǒng)狀態(tài)，豐富進程代數(shù)在系統(tǒng)性能評價研究領(lǐng)域；③進程代數(shù)模型中存在各種邏輯和推導，對于結(jié)構(gòu)簡單的模型來說，通過人工進行分析工作量雖然不大，但對于結(jié)構(gòu)復雜的模型，則需借助機器進行自動推導，因此需要開發(fā)對應的進程代數(shù)建模與分析工具；④進程代數(shù)理論性和邏輯性很強，只有在實際應用中才能體現(xiàn)其價值。目前，將進程代數(shù)理論應用于系統(tǒng)性能評價的研究雖進展較快，但真正在工程實踐中成功應用的實例還不多見。因此，如何將先進的理論成果與方法應用到實際的工程領(lǐng)域中去還有待深入研究。

參考文獻參考文獻：

＼[1＼]吳盡昭，王永祥，覃廣平.交互式馬爾可夫鏈—并發(fā)系統(tǒng)的設(shè)計、驗證與評價[M].北京：科學出版社，2007.

[2]嚴博，吳曉平，付鈺.應用隨機進程代數(shù)的網(wǎng)絡(luò)系統(tǒng)可靠性預計方法研究[J]. 西安交通大學學報，2011，45（6）：4045.

[3]肖芳雄，李燕，黃志球，等.基于時間概率代價進程代數(shù)的Web服務(wù)組合建模和分析[J].計算機學報，2012，35（5）：918936.

[4]祝義，肖芳雄，周航，等. 一種嵌入式實時系統(tǒng)軟件能耗建模與分析的方法[J].計算機研究與發(fā)展，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.

責任編輯（責任編輯：陳福時）