基于進(jìn)程網(wǎng)模型的仿真技術(shù)研究

郭 峰 楊顏公 閆 琦 喬 磊

（北方工業(yè)大學(xué)，北京 100144）

Petri網(wǎng)是一個(gè)分布式系統(tǒng)，目前已在制造系統(tǒng)、通信網(wǎng)絡(luò)、數(shù)字電路綜合與驗(yàn)證等領(lǐng)域得到了廣泛應(yīng)用。但Petri網(wǎng)也有很多缺點(diǎn)。把Petri網(wǎng)與進(jìn)程代數(shù)相結(jié)合的研究領(lǐng)域引起很多研究人員的興趣，文獻(xiàn)[6]提出了進(jìn)程表達(dá)式的一種概念，文獻(xiàn)[7]提出了用Petri網(wǎng)組件作為代數(shù)表達(dá)式的構(gòu)造模型，其組件對(duì)外只提供接口，分別為T(mén)opPlace與BottomPlace。復(fù)雜的Petri網(wǎng)可以通過(guò)各種操作符組合而成，并給出了其操作語(yǔ)義，此進(jìn)程網(wǎng)具有一般Petri網(wǎng)的運(yùn)行規(guī)則，將這種Petri網(wǎng)模型稱為進(jìn)程網(wǎng)（Process Net，簡(jiǎn)稱為PrN）文獻(xiàn)[7]給出了實(shí)現(xiàn)其建模工具PrnTools的具體方法，但此軟件目前僅局限于畫(huà)圖建模階段，沒(méi)有分析的功能。雖然目前有很多實(shí)現(xiàn)Petri網(wǎng)仿真的軟件，但缺乏針對(duì)PrN網(wǎng)的仿真理論與實(shí)現(xiàn)。本文在文獻(xiàn)[7]的基礎(chǔ)上對(duì)基于PrN的仿真技術(shù)進(jìn)行研究并實(shí)現(xiàn)。

1 進(jìn)程網(wǎng)的基本概念

本文假設(shè)讀者對(duì)Petri網(wǎng)理論有所了解，這里只對(duì)Pr給出定義：

定義1 PrN是一個(gè)七元組：（S，T，F(xiàn)，A，L，I，O），其中（S，T，F(xiàn)）是一個(gè)Petri網(wǎng)，有兩個(gè)特殊的庫(kù)所：i和o。庫(kù)所i是組件的起始庫(kù)所，即·i=?，在程序中用TopPlace表示；庫(kù)所o是組件的終止庫(kù)所，即o·=?；在程序中用BottomPlace表示。A是所有動(dòng)作的集合，由英文字母組成的字符串表示，I?T，是變遷的集合，但只表示接受的消息，O?T，同樣是變遷集合，但只表示輸出的消息，這兩個(gè)合起來(lái)就是PrN的接口變遷集合。PrN定義了最基本組合并稱其為基本PrN（BasicComponent），由兩個(gè)庫(kù)所一個(gè)變遷組合而成，復(fù)雜的網(wǎng)結(jié)構(gòu)由基本進(jìn)程網(wǎng)結(jié)構(gòu)組合而成。

2 進(jìn)程網(wǎng)仿真功能的設(shè)計(jì)與實(shí)現(xiàn)

文獻(xiàn)[7]介紹了進(jìn)程網(wǎng)建模工具PrnTools的實(shí)現(xiàn)。此建模工具基于Eclipse平臺(tái)開(kāi)發(fā)，包 括實(shí)現(xiàn)進(jìn)程網(wǎng)的建模。本文是在其基礎(chǔ)上做的仿真技術(shù)的研究。

圖1 PrnTools組件類圖

2.1 組合組件邏輯關(guān)系

接下來(lái)給出修改后的組件類圖（圖1）：

其中，BaseComplex是所有組合組件實(shí)現(xiàn)的接口，BaseComplexSupport是所有組合組件的父類。繪制的進(jìn)程網(wǎng)的過(guò)程本質(zhì)上就是產(chǎn)生新的組合組件，BasicComponent是最基本的進(jìn)程網(wǎng)模型，包含兩個(gè)庫(kù)所和一個(gè)變遷及對(duì)應(yīng)的流關(guān)系。

其他組合組件由繼承BaseSingle Support的類添加元素修改而來(lái)，而其中每一個(gè)包含的基本元素?cái)?shù)量和邏輯又各不相同。為了實(shí)現(xiàn)仿真，就必須添加每個(gè)組件的內(nèi)部邏輯，包括前、后集合的實(shí)現(xiàn)，Token的添加以及組件元素的添加與命名。

2.1.1 前后集合的實(shí)現(xiàn)

前集用來(lái)判斷是否滿足點(diǎn)火條件，以便為點(diǎn)火做鋪墊，實(shí)現(xiàn)仿真。在每一個(gè)變遷（TransitionComponent）中加入兩個(gè)List，分別記錄此組件的前集和后集：

在繪制每一個(gè)基本組件的時(shí)候，實(shí)現(xiàn)庫(kù)所（Place）和變遷（Transition Component）的內(nèi)部邏輯關(guān)系；在組件實(shí)現(xiàn)組合方式的時(shí)候.記錄每一個(gè)Place和Transition新產(chǎn)生的邏輯關(guān)系。另外點(diǎn)火的時(shí)候面向變遷，所以每一個(gè)組 件都需要一個(gè)自己的List記錄變遷。

publicList transInComponent

2.1.2 組件中元素的添加與命名

庫(kù)所和變遷的標(biāo)記用來(lái)區(qū)分彼此，是在可達(dá)圖生成時(shí)的必須條件。此工具Prntools 以構(gòu)造內(nèi)部邏輯來(lái)實(shí)現(xiàn)一個(gè)完整的Petri網(wǎng)。 在內(nèi)部邏輯構(gòu)造過(guò)程中，需要修改自身組件或者鏈接兩個(gè)基本組件，不同的邏輯需要不同的構(gòu)造方法。

為了記錄組件中所有元素，在組件父類（BaseSingleSupport）中添加兩個(gè)List，分別記錄產(chǎn)出的所有的庫(kù)所和變遷。這樣才能在畫(huà)圖結(jié)束后知道此組件中存在多少個(gè)庫(kù)所和變遷，也能將其在命名上分開(kāi)。命名規(guī)則如下：

基本組件：由兩個(gè)庫(kù)所和一個(gè)變遷組合而成，上面的庫(kù)所（Topplace）標(biāo)記為p1，下面的庫(kù)所（Bottomplace）標(biāo)記為p2。變遷標(biāo)記為t1。

組件組合：兩個(gè)組件進(jìn)行算子組合，組件內(nèi)部標(biāo)記變化：組件1的庫(kù)所和變遷序號(hào)不變，組件2的庫(kù)所序和變遷依次增加組件1的元素個(gè)數(shù)。

2.2 仿真技術(shù)實(shí)現(xiàn)

2.2.1 進(jìn)程網(wǎng)仿真技術(shù)

進(jìn)程網(wǎng)的仿真步驟是先建立系統(tǒng)模型，然后通過(guò)多次點(diǎn)火模擬系統(tǒng)運(yùn)行，得到仿真運(yùn)行方式和結(jié)果。使用仿真方法，用戶可以觀察此組件中出現(xiàn)的Token的變化過(guò)程。分析出系統(tǒng)所具有的特性，如：可達(dá)性、有界性、可覆蓋性等，以便使我們得到系統(tǒng)的一些重要信息。

2.2.2 點(diǎn)火技術(shù)

為組件父類（BaseComplexSupport）增加點(diǎn)火函數(shù)Firing。增加點(diǎn)火按鈕，在選擇組件并點(diǎn)擊按鈕時(shí)調(diào)用點(diǎn)火函數(shù)。一次的點(diǎn)火規(guī)則如下：當(dāng)一個(gè)變遷的所有前集中含有一個(gè)以上的Token，則此變遷可以發(fā)生點(diǎn)火：此變遷前集Token數(shù)量減一，此變遷后集Token數(shù)量加一。

具體方法如下：

（1）變遷選擇與Token移動(dòng)

選中要點(diǎn)火的組件，在點(diǎn)火按鈕被點(diǎn)擊時(shí)，判斷組件是否可以點(diǎn)火。如果組件可以實(shí)行點(diǎn)火，遍歷所有變遷，判斷可以點(diǎn)火的變遷數(shù)量。如果此時(shí)只有一個(gè)變遷可以點(diǎn)火，則根據(jù)規(guī)則進(jìn)行：

①根據(jù)初始數(shù)據(jù)對(duì)模型進(jìn)行初始標(biāo)記。②發(fā)生點(diǎn)火變遷前的所有庫(kù)所令牌數(shù)-1，點(diǎn)火變遷后的所有庫(kù)所令牌數(shù)+1。③仿真結(jié)束后，將仿真結(jié)果顯示和存儲(chǔ)。若遍歷后有兩個(gè)以上的變遷可以進(jìn)行點(diǎn)火的情況下，會(huì)給出一個(gè)提示面版，讓用戶自己選擇

（2）記錄狀態(tài)圖組件

對(duì)于Petri網(wǎng)的仿真，其點(diǎn)火過(guò)程中的可達(dá)標(biāo)識(shí)集是一個(gè)有限集，可以以此集合作為頂點(diǎn)，以庫(kù)所狀態(tài)與經(jīng)歷的變遷的關(guān)系構(gòu)成一個(gè)有向圖，這個(gè)圖稱為進(jìn)程網(wǎng)的狀態(tài)圖。通過(guò)這個(gè)Petri網(wǎng)的狀態(tài)圖可以得到這個(gè)網(wǎng)系統(tǒng)狀態(tài)的變化與狀態(tài)變化時(shí)經(jīng)歷的變遷，從而得知網(wǎng)系統(tǒng)的有關(guān)性質(zhì)。

在每次點(diǎn)火的過(guò)程中，記錄下組件點(diǎn)火前后的狀態(tài)，即Mi與Mj，發(fā)生點(diǎn)火的變遷Tx，以便生成狀態(tài)圖。

（3）重復(fù)點(diǎn)火

回到步驟1，直到用戶停止操作或發(fā)生死鎖

（4）點(diǎn)火結(jié)束

在數(shù)次點(diǎn)火仿真后，如果組件達(dá)到死鎖狀態(tài)，及不能再繼續(xù)點(diǎn)火，工具會(huì)對(duì)用戶進(jìn)行提示。

2.3 點(diǎn)火技術(shù)的描述

圖2 一次點(diǎn)火的流程圖

可以發(fā)現(xiàn)，整個(gè)大仿真過(guò)程由一次次的點(diǎn)火完成，用戶可以在任何地方停止操作，以下給出點(diǎn)火的程序流程圖，如圖2所示。

結(jié)語(yǔ)

本文所提出的技術(shù)有效地實(shí)現(xiàn)了進(jìn)程網(wǎng)流模型的分析與仿真，實(shí)現(xiàn)了對(duì)于順序、選擇、循環(huán)及并發(fā)等所有組合模式的標(biāo)識(shí)及仿真技術(shù)，并且清晰地反映出進(jìn)程網(wǎng)仿真過(guò)程中經(jīng)歷的狀態(tài)改變及行為特征。進(jìn)一步的工作可以考慮利用進(jìn)程網(wǎng)點(diǎn)火和狀態(tài)圖的思想，實(shí)現(xiàn)可達(dá)圖的構(gòu)造。

[1]Murata T.Petri nets: Properties,analysis and applications[J].Proceedings of IEEE,1989,77（04）: 541-574.

[2]Gu Tianlong,Bahri P A.A survey of Petri-net applications in batch processes[J].Computers in Industry,2002,47（01）: 99-111.

[3]Luo Jun-Zhou,Shen Jun,Gu Guan-Qun.From Petri nets toformal description techniques and protocol engineering[J].Journal of Software,2000,11（05）: 606-615.

[4]Wolfgang Reisig.Petri Nets-An Introduction[J].New York: Springer-Verlag,1985.

[5]Wu Zhe-Hui.Process expression of bounded Petri net[J].Sciencein China（Series E）,1996,39（01）: 37-49.

[6]Guo Feng,Deng Mengmeng,Shi Wanlin,Process Net: A petri net model with the characteristics of process algebras,Journal of Chemical and Pharmaceutical Research,2013-9.

[7]郭峰，鄧蒙蒙，楊顏公.進(jìn)程網(wǎng)建模工具的設(shè)計(jì)與實(shí)現(xiàn)[J].北方工業(yè)大學(xué)學(xué)報(bào)，2014，3（01）：22-26.

[8]袁崇義.Petri網(wǎng)原理[M].北京：電子工業(yè)出版社，2005.