郭峰

(北方工業(yè)大學(xué)信息學(xué)院,北京 100144)

0 引言

進(jìn)程網(wǎng)[1]是一種很好的描述并發(fā)系統(tǒng)、建模、進(jìn)行系統(tǒng)分析的工具。Petri網(wǎng)對(duì)于簡(jiǎn)單模型來(lái)說(shuō)很容易表示,而實(shí)際應(yīng)用中的系統(tǒng)模型往往是很復(fù)雜,詳細(xì)的規(guī)范說(shuō)明使建模者不太容易理解和分析,因此,一個(gè)抽象機(jī)制是必要的,它用來(lái)簡(jiǎn)化模型和方便進(jìn)行性質(zhì)分析,提供系統(tǒng)的更高層次的視圖。這時(shí),就需要提供細(xì)化機(jī)制以增強(qiáng)其描述能力,通過(guò)細(xì)化低層次子網(wǎng)來(lái)表示更高層次系統(tǒng)模型[2]。進(jìn)程網(wǎng)也可以采用這種機(jī)制。為了方便進(jìn)行系統(tǒng)仿真和性能分析,進(jìn)程網(wǎng)也需要進(jìn)行抽象和細(xì)化。

建模方法遵循三個(gè)步驟:第1步是建立系統(tǒng)的功能級(jí)模型;第2 步將功能級(jí)模型變換的成高層次可靠性模型,對(duì)于每個(gè)預(yù)先選擇的候選系統(tǒng)生成一個(gè)模型;第3步將選擇的系統(tǒng)中的高級(jí)模型細(xì)化成詳細(xì)可靠性模型[3]。

復(fù)雜系統(tǒng)的設(shè)計(jì)模型通常由簡(jiǎn)單的設(shè)計(jì)模型經(jīng)過(guò)逐步求精獲得[4]。在系統(tǒng)建模中,細(xì)化[5]操作是一個(gè)必要和基本的問(wèn)題,比如在工作流建模方面可以用細(xì)化規(guī)則保證工作流[6]的合理性。

在建模中使用細(xì)化和以一個(gè)更加抽象的模型開始建模有很多優(yōu)點(diǎn):細(xì)化給出了一個(gè)好的、結(jié)構(gòu)化的視圖。系統(tǒng)內(nèi)的部件可以清楚地識(shí)別,建模者不必理會(huì)內(nèi)部細(xì)節(jié)。細(xì)化節(jié)省了時(shí)間和空間的分析,解決了狀態(tài)空間爆炸問(wèn)題[7]。進(jìn)程網(wǎng)的細(xì)化可以用于模型的層次化設(shè)計(jì),它被用來(lái)表示系統(tǒng)在不同抽象層次的模型[8]。

采用基于層次細(xì)化這種設(shè)計(jì)方法,人們可以得到滿足最初的抽象模型指定的所有屬性的系統(tǒng)。此外,細(xì)化后模型的屬性也可以得到保護(hù),可以進(jìn)行更詳細(xì)的分析。

進(jìn)程網(wǎng)的細(xì)化就是對(duì)粗略進(jìn)程網(wǎng)系統(tǒng)中的基本組件具體化。細(xì)化技術(shù)根據(jù)他們保持得性質(zhì)的不同分為兩類:一類是保持行為性質(zhì),另一類是保持語(yǔ)義等價(jià)[9]。

進(jìn)程網(wǎng)的細(xì)化通過(guò)替換部分簡(jiǎn)單的成分形成較為具體的子網(wǎng)結(jié)構(gòu),使得進(jìn)程網(wǎng)能夠用于復(fù)雜系統(tǒng)的建模[10]。提出了使用網(wǎng)模型的細(xì)化設(shè)計(jì)一個(gè)在不同抽象層次上的上的復(fù)雜動(dòng)態(tài)系統(tǒng)的方法。某些變遷進(jìn)行細(xì)化,在細(xì)化過(guò)程中保持原系統(tǒng)的某些性質(zhì)不變。在一個(gè)給定的抽象層次上的變遷被一個(gè)復(fù)雜的進(jìn)程在較低層次上進(jìn)行替代。

系統(tǒng)模型細(xì)節(jié)的描述在底層中,中間層反映了抽象的變遷的細(xì)節(jié)?；拘再|(zhì)分析都在較高的層次上考慮,建模開始時(shí)省略分支或細(xì)節(jié),這些細(xì)節(jié)會(huì)在較低層次一步一步的考慮,直到完成一個(gè)完全描述模型[11]。

我們?cè)敿?xì)的說(shuō)明細(xì)化技術(shù)主要是為了規(guī)范結(jié)構(gòu)化建模,也是為了便于進(jìn)行技術(shù)驗(yàn)證,它可以保持系統(tǒng)的行為屬性。

使用給定的細(xì)化規(guī)則來(lái)進(jìn)一步的細(xì)化。細(xì)化規(guī)則可以保證進(jìn)程網(wǎng)的工作流可以有期望的穩(wěn)定性。

進(jìn)程網(wǎng)建模工具可以進(jìn)行建模、存儲(chǔ),但仍有一些缺陷。進(jìn)程網(wǎng)的層次建模過(guò)程是自頂向下的,先建立的模型還比較粗糙,最開始從一個(gè)單一的進(jìn)程網(wǎng)的基本組件出發(fā),建立抽象模型。細(xì)化技術(shù)可以用于一個(gè)自上而下的方法合成并發(fā)系統(tǒng)的進(jìn)程網(wǎng)模型。目前進(jìn)程網(wǎng)的建模及細(xì)化工具很少,在本論文中我們給出了一個(gè)進(jìn)程網(wǎng)細(xì)化的方法和工具。

本文提出了進(jìn)程網(wǎng)細(xì)化的規(guī)則和實(shí)現(xiàn)方法?？梢苑从尺M(jìn)程網(wǎng)的詳細(xì)構(gòu)建的過(guò)程,表現(xiàn)了系統(tǒng)在不同抽象層次上的視圖。論文的結(jié)構(gòu)如下:在第1 節(jié)描述基本概念。第2節(jié)介紹進(jìn)程網(wǎng)的細(xì)化規(guī)則和細(xì)化模型分析,第3節(jié)介紹進(jìn)程網(wǎng)的細(xì)化的實(shí)現(xiàn)以及存儲(chǔ),第4節(jié)結(jié)論。

1 進(jìn)程網(wǎng)及其細(xì)化規(guī)則

進(jìn)程網(wǎng):(Process Net)是一個(gè)七元組(P,T,F,A,β,I,O),其中(P,T,F)是一個(gè)Petri網(wǎng);A是動(dòng)作集合,I∈T,表示接受消息的變遷集合,O∈T表示輸出消息的變遷集合[1]。

細(xì)化指從較為抽象的高層模型到更具體的底層模型的轉(zhuǎn)換過(guò)程[12]。在Petri網(wǎng)的研究中,細(xì)化通常是指用一個(gè)子網(wǎng)結(jié)構(gòu)替換一個(gè)變遷或者庫(kù)所[13]。進(jìn)程網(wǎng)的細(xì)化是用一個(gè)子網(wǎng)結(jié)構(gòu)替換一些基本組件形成較為具體的子網(wǎng)模型。

進(jìn)程網(wǎng)的基本組件是進(jìn)程網(wǎng)用來(lái)建模的最小單位,也是進(jìn)程網(wǎng)進(jìn)行細(xì)化的基本單位,進(jìn)程網(wǎng)的基本組件有3種,分別表示三種不同的基本動(dòng)作:內(nèi)部動(dòng)作,發(fā)送消息動(dòng)作,接收消息動(dòng)作。進(jìn)程網(wǎng)細(xì)化模型允許設(shè)計(jì)者通過(guò)預(yù)定義的模型進(jìn)行細(xì)化(主要是變遷的細(xì)化)使模型的設(shè)計(jì)更加合理[14],進(jìn)程網(wǎng)的細(xì)化規(guī)則如下:

規(guī)則1:一個(gè)變遷擴(kuò)展為一個(gè)子網(wǎng)的細(xì)化規(guī)則,如圖4、圖5所示。

在圖1中,可以看到將一個(gè)變遷替換成進(jìn)程網(wǎng)的基本組件后,可以完成進(jìn)程網(wǎng)的細(xì)化。在圖2中,將一個(gè)變遷分解成有兩個(gè)分支的進(jìn)程網(wǎng)模型,實(shí)現(xiàn)細(xì)化。

規(guī)則2:并發(fā)細(xì)化的細(xì)化規(guī)則:如圖3所示。

圖3 細(xì)化規(guī)則2:進(jìn)程網(wǎng)的并發(fā)細(xì)化規(guī)則Fig.3 Refinement rule 2: concurrent refinement rule of process network

在圖3中,將一個(gè)新的進(jìn)程網(wǎng)附加在原來(lái)存在的進(jìn)程網(wǎng)的一側(cè),完成進(jìn)程網(wǎng)的細(xì)化。雖然圖3和圖2進(jìn)行細(xì)化后的效果看著一樣,但本質(zhì)不同。它們分別是在遵循兩種不同的細(xì)化規(guī)則后所實(shí)現(xiàn)的。圖2 是一種分解操作,是一個(gè)變遷擴(kuò)展為子網(wǎng)的細(xì)化規(guī)則。圖3 是一種附加操作,是并發(fā)細(xì)化規(guī)則。

規(guī)則3:選擇細(xì)化的細(xì)化規(guī)則:如圖4所示。

圖4 細(xì)化規(guī)則3:進(jìn)程網(wǎng)的選擇細(xì)化規(guī)則Fig.4 Refinement rule 3: selection refinement rule of process network

圖5 細(xì)化規(guī)則4:進(jìn)程網(wǎng)的循環(huán)細(xì)化規(guī)則Fig.5 Refinement Rule 4:cycle refinement rule of process network

在圖4中一個(gè)進(jìn)程網(wǎng)組件或進(jìn)程網(wǎng)基本組件中的變遷經(jīng)過(guò)細(xì)化后變成具有兩個(gè)分支的進(jìn)程網(wǎng),它屬于選擇細(xì)化規(guī)則。

規(guī)則4：循環(huán)細(xì)化的細(xì)化規(guī)則:如圖5所示。

圖5中一個(gè)進(jìn)程網(wǎng)中的變遷或基本組件經(jīng)過(guò)細(xì)化后變成具有循環(huán)結(jié)構(gòu)的進(jìn)程網(wǎng),它屬于循環(huán)細(xì)化。

規(guī)則5：通信細(xì)化的細(xì)化規(guī)則:如圖6所示。

圖6 細(xì)化規(guī)則5:進(jìn)程網(wǎng)的通信細(xì)化規(guī)則Fig.6 Refinement Rule 5: Communication refinement rule of process network

圖6中兩個(gè)進(jìn)程網(wǎng)經(jīng)過(guò)細(xì)化后變成具有通信功能的進(jìn)程網(wǎng),它屬于通信細(xì)化。細(xì)化后的進(jìn)程網(wǎng)不僅保持了進(jìn)程網(wǎng)的一些特性,使模型更加準(zhǔn)確,而且細(xì)化規(guī)則可以幫助設(shè)計(jì)者進(jìn)行系統(tǒng)的分析。細(xì)化后模型可以提供多層次視圖來(lái)反映進(jìn)程網(wǎng)的層次關(guān)系。這種模型可以支持模塊化驗(yàn)證和設(shè)計(jì)分析。

2 進(jìn)程網(wǎng)細(xì)化的實(shí)現(xiàn)

目前在進(jìn)程網(wǎng)建模工具中實(shí)現(xiàn)了上述的細(xì)化規(guī)則[15],建模工具的類圖如圖7 所示。

進(jìn)程網(wǎng)建模工具的基本組件由最基本的圖形,如圓、直線、矩形等進(jìn)行組合表示的。定義了基本組件和復(fù)雜組合組件,分別用BaseSingle、BaseComplex這兩個(gè)接口來(lái)實(shí)現(xiàn)進(jìn)程網(wǎng)基本組件的繪制。

進(jìn)程網(wǎng)細(xì)化規(guī)則類之間的關(guān)系如圖8 所示。

進(jìn)程網(wǎng)的細(xì)化研究中定義了5個(gè)細(xì)化規(guī)則,在工程中定義了5個(gè)細(xì)化類:TransitionExtendsToSubNetRule,SimulationRefinementeRule,SelectionRefinementRule,LoopRefinement,CommunicationRefinementRule。這5個(gè)類分別來(lái)實(shí)現(xiàn)子網(wǎng),同步,選擇,循環(huán),通信這5種不同的細(xì)化。

建模時(shí)首先建立進(jìn)程網(wǎng)的粗略抽象模型。當(dāng)需要進(jìn)行細(xì)化時(shí),首先按層次選中想要細(xì)化的最基本組件。在構(gòu)建模型的過(guò)程中,已經(jīng)保存了模型的層次關(guān)系,選擇進(jìn)程網(wǎng)的頂層模型,一層一層自頂向下選中,直到選中需要細(xì)化的那一層。進(jìn)行細(xì)化時(shí),會(huì)顯示一個(gè)細(xì)化選擇的選項(xiàng)框,用來(lái)供建模者進(jìn)行細(xì)化規(guī)則的選擇,細(xì)化結(jié)果將會(huì)在新的層次上進(jìn)行顯示。

選擇5種不同的細(xì)化規(guī)則之后,將彈出一個(gè)新的面板,在新的面板上顯示進(jìn)程網(wǎng)基本組件被細(xì)化后的效果。進(jìn)程網(wǎng)每一個(gè)組件的屬性及標(biāo)記與細(xì)化前的保持一致。

在文獻(xiàn)[16]中,建立了petri網(wǎng)的細(xì)化樹。在進(jìn)程網(wǎng)細(xì)化中也可以構(gòu)建進(jìn)程網(wǎng)的細(xì)化樹。由于進(jìn)程網(wǎng)的細(xì)化是自頂向下的,逐步求精的,進(jìn)程網(wǎng)建模工具在建模時(shí)使用二叉樹的結(jié)構(gòu),如圖9所示。

圖7 進(jìn)程網(wǎng)建模工具整體類圖Fig.7 Overall class diagram of process network modeling tool

圖8 進(jìn)程網(wǎng)細(xì)化規(guī)則類圖Fig.8 Process network refinement rule class diagram

圖9 層次進(jìn)程網(wǎng)細(xì)化樹Fig.9 Hierarchical process network refinement tree

進(jìn)程網(wǎng)按照細(xì)化規(guī)則轉(zhuǎn)換后,我們得到一個(gè)細(xì)化樹。進(jìn)程網(wǎng)的基本組件我們用樹的葉子表示,樹根表示最初的進(jìn)程網(wǎng)模型。

在建模工具中支持分層視圖。在工具中我們可以分層瀏覽系統(tǒng)模型,可以使用細(xì)化樹瀏覽分層結(jié)構(gòu),或者雙擊細(xì)化的基本組建,就可以進(jìn)入到下一層次中。

進(jìn)程網(wǎng)的邏輯結(jié)構(gòu)和細(xì)化后的結(jié)果保存在x m l 文件里。進(jìn)程網(wǎng)的建模過(guò)程中的邏輯關(guān)系用二叉樹的結(jié)構(gòu)進(jìn)行存儲(chǔ)。他們之間的層次關(guān)系,每個(gè)組件的屬性和標(biāo)記用xml文件進(jìn)行存儲(chǔ)。當(dāng)進(jìn)行建模和性能分析時(shí),將xml文件導(dǎo)入到進(jìn)程網(wǎng)建模工具中,即可還原出建模時(shí)的系統(tǒng)模型。

3 結(jié)語(yǔ)

本文提出了一種進(jìn)程網(wǎng)分層模型的細(xì)化規(guī)則和細(xì)化方法,并實(shí)現(xiàn)了進(jìn)程網(wǎng)的細(xì)化,給出了進(jìn)程網(wǎng)的細(xì)化樹,提供了一個(gè)進(jìn)程網(wǎng)細(xì)化的工具。到目前為止,實(shí)驗(yàn)室已經(jīng)完成了進(jìn)程網(wǎng)建模工具的畫圖,仿真,可完成圖的生成,分層選中,進(jìn)程網(wǎng)的細(xì)化。進(jìn)程網(wǎng)的語(yǔ)義等價(jià)性等方面的研究還有待完善。