張小彬??嚴(yán)博??陳璐

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

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

DOIDOI：10.11907/rjdk.143787

中圖分類號：TP302

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2015）002002503

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

作者簡介作者簡介：楊進(jìn)（1983-），男，湖北宜昌人，海軍南海艦隊(duì)司令部工程師，研究方向?yàn)榫W(wǎng)絡(luò)安全管理；張小彬（1981-），男，云南陸良人，碩士，海軍南海艦隊(duì)司令部工程師，研究方向?yàn)榫W(wǎng)絡(luò)工程；嚴(yán)博（1984-），男，江西豐城人，海軍工程大學(xué)信息安全系講師，研究方向?yàn)樾畔⑴c網(wǎng)絡(luò)安全；陳璐（1979-）女，廣東汕頭人，博士，海軍工程大學(xué)信息安全系講師，研究方向?yàn)樾畔踩⒖尚庞?jì)算。

0引言

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

1進(jìn)程代數(shù)及其擴(kuò)展形式

1.1進(jìn)程代數(shù)概述

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

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

1.2進(jìn)程代數(shù)的有效擴(kuò)展

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

2隨機(jī)進(jìn)程代數(shù)

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

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

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

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

3.1隨機(jī)進(jìn)程代數(shù)PEPA

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

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

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

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

根據(jù)以上LTS的轉(zhuǎn)移關(guān)系，可得到該系統(tǒng)共有4種狀態(tài)，各狀態(tài)對應(yīng)的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ī)生在工作時(shí)忙碌時(shí)間占總時(shí)間的比率，即構(gòu)件Doctor的利用率，則需首先為系統(tǒng)的4種狀態(tài)各自聯(lián)系一個(gè)回報(bào)值，分別為：r1=0，r2=1，r3=1，r4=1，聯(lián)合計(jì)算得到穩(wěn)態(tài)概率分布，則可得出Doctor的利用率R為：

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

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

4結(jié)語

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

參考文獻(xiàn)參考文獻(xiàn)：

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

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

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

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

責(zé)任編輯（責(zé)任編輯：陳福時(shí)）