王梅

摘要：定義了一類模糊時(shí)間Petri網(wǎng)（FTPN）演示在不確定的時(shí)間范圍內(nèi)的事實(shí)系統(tǒng)的變化，通過(guò)對(duì)模糊時(shí)間情況下的知識(shí)的推理和模糊時(shí)序情況下的邏輯分析，解決了在實(shí)時(shí)系統(tǒng)中的資源沖突的問(wèn)題，以及在實(shí)時(shí)系統(tǒng)中如何解決時(shí)間-空間的沖撞問(wèn)題，通過(guò)一個(gè)簡(jiǎn)單的生產(chǎn)加工系統(tǒng)來(lái)模擬演示如何解決系統(tǒng)資源沖突原因，更好的描述了基于FTPN的系統(tǒng)資源沖突的分析。

關(guān)鍵詞：模糊時(shí)間；實(shí)時(shí)系統(tǒng)；不確定性；資源沖突

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）21-5112-03

1 概述

Petri網(wǎng)自1962年由德國(guó)的C. A. Petri提出以來(lái)，經(jīng)歷四十多年的發(fā)展，已經(jīng)形成了較為堅(jiān)實(shí)的理論基礎(chǔ)，并形成多種類型的應(yīng)用體系。Petri網(wǎng)直觀的圖形表示和堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)使其特別適合描述系統(tǒng)的并發(fā)、競(jìng)爭(zhēng)、同步等特征。在實(shí)時(shí)系統(tǒng)進(jìn)行建模和分析時(shí)，時(shí)間是一個(gè)非常重要的因素[1]。傳統(tǒng)的Petri網(wǎng)模型沒(méi)有時(shí)間的概念，也就約束了Petri網(wǎng)在實(shí)時(shí)系統(tǒng)中的應(yīng)用，因?qū)?shí)時(shí)系統(tǒng)時(shí)間行為分析和性能評(píng)估的需求，各種與時(shí)間相關(guān)的Petri網(wǎng)模型也相繼提出。目前，常見(jiàn)的時(shí)間Petri網(wǎng)有Timed Petri Net[2]，Stochastic Petri Net[3]和Time Petri Net[4]，這些時(shí)間Petri網(wǎng)模型都是在基本網(wǎng)的變遷上添加時(shí)間因素形成的。但是時(shí)間知識(shí)具有一定的不確定性，所以在對(duì)實(shí)時(shí)系統(tǒng)進(jìn)行建模和分析時(shí)時(shí)間的合理表示和處理成為十分關(guān)鍵的問(wèn)題。隨著可能性理論和模糊集理論的引入，Murata提出了一種模糊時(shí)間高級(jí)Petri網(wǎng)[5]，這種網(wǎng)能夠合理分析系統(tǒng)中的時(shí)間不確定性，同時(shí)能夠進(jìn)行時(shí)間知識(shí)的推理。

2 模糊時(shí)間Petri網(wǎng)

3 沖突的檢測(cè)

4 沖突的消解

在模糊時(shí)間Petri網(wǎng)模型中，若檢測(cè)到?jīng)_突的存在，應(yīng)該采用相關(guān)的策略來(lái)消解沖突。通常情況下，采用先來(lái)先服務(wù)的原則解決沖突問(wèn)題。該文除了解決資源有限的沖突問(wèn)題，還分析了因庫(kù)所容量形成的沖撞問(wèn)題。沖撞為特殊的沖突，并且在結(jié)構(gòu)上沖撞問(wèn)題可以轉(zhuǎn)化為沖突問(wèn)題。

如果實(shí)時(shí)系統(tǒng)中存在沖撞的情況時(shí)，不能簡(jiǎn)單的將其轉(zhuǎn)化為沖突的結(jié)構(gòu)來(lái)解決問(wèn)題，因?yàn)橄到y(tǒng)存在了時(shí)間因素。如圖4所示，[T1]和[T2]不存在資源的沖突，但是[T1]和[T2]不能同時(shí)觸發(fā)，因?yàn)閹?kù)所[P4]的容量為4，而[T1]和[T2]同時(shí)觸發(fā)一共要產(chǎn)生5個(gè)托肯。這種特殊的沖突也可采用先來(lái)先服務(wù)的策略來(lái)消解。

由模糊時(shí)間知識(shí)推理可以計(jì)算得到變遷[T1]產(chǎn)生的托肯到達(dá)[P4]的模糊時(shí)間為[πP4（τ）=[4，6，9，11]]，變遷[T2]產(chǎn)生的托肯到達(dá)[P4]的模糊時(shí)間為[πP4（τ）=[6，8，11，13]]，[T1]和[T2]產(chǎn)生的托肯在模糊時(shí)間[6，8，9，11]內(nèi)在庫(kù)所[P4]可能發(fā)生沖撞。同理，采用模糊時(shí)序邏輯求的[T1]產(chǎn)生托肯先于[T2]產(chǎn)生的托肯到達(dá)[P4]的可能性為1，[T2]產(chǎn)生托肯先于[T1]產(chǎn)生的托肯到達(dá)[P4]的可能性為0.6，計(jì)算得到，[T1]先于[T2]觸發(fā)的概率應(yīng)為0.625， [T2]先于[T1]觸發(fā)的概率應(yīng)為0.375。

5 實(shí)例分析

一個(gè)簡(jiǎn)單的生產(chǎn)加工系統(tǒng)如圖5所示。系統(tǒng)的模糊時(shí)間Petri網(wǎng)模型如圖6所示，[P1][P2][P3]和[P4]的模糊時(shí)間分別表示預(yù)備原料1-原料4所需的時(shí)間，弧上的模糊時(shí)間表示設(shè)備加工所需要的時(shí)間。依據(jù)對(duì)FTPN模型的分析，通過(guò)模糊時(shí)間知識(shí)推理可以計(jì)算得到原料2使得設(shè)備1和設(shè)備2在模糊時(shí)間[3，4，4，5]內(nèi)發(fā)生沖突，通過(guò)模糊時(shí)序邏輯的分析，可以計(jì)算得到設(shè)備1占用原料2進(jìn)行加工的概率為2/3，設(shè)備2占用原料2進(jìn)行加工的概率為1/3。另外，從模型中可以看到設(shè)備1產(chǎn)生的中間產(chǎn)品1和設(shè)備3產(chǎn)生的中間產(chǎn)品1在儲(chǔ)罐1中可能因容量限制產(chǎn)生沖撞，通過(guò)模糊時(shí)間知識(shí)推理可得到設(shè)備1產(chǎn)生的中間產(chǎn)品1和設(shè)備3產(chǎn)生的中間產(chǎn)品1可能在模糊時(shí)間[4，6，7，9]內(nèi)產(chǎn)生沖撞，使得儲(chǔ)罐1內(nèi)的中間產(chǎn)品1溢出。通過(guò)模糊時(shí)序邏輯分析，選擇設(shè)備1的概率為5/9，選擇設(shè)備2的概率為4/9。

6 結(jié)論

本文主要分析了基于時(shí)間不確定性的實(shí)時(shí)系統(tǒng)資源沖突問(wèn)題，采用模糊時(shí)間Petri網(wǎng)進(jìn)行建模，通過(guò)模糊時(shí)間知識(shí)推理，研究了實(shí)時(shí)系統(tǒng)沖突的檢測(cè)方法，通過(guò)模糊時(shí)序邏輯分析，研究了實(shí)時(shí)系統(tǒng)沖突的消解方法。最后，通過(guò)一個(gè)簡(jiǎn)單的生產(chǎn)加工系統(tǒng)的分析，驗(yàn)證了方法的有效性。

參考文獻(xiàn)：

[1] Tasi JJP， Yang SJ. Timing Constraint Petri Nets and Their Application to Schedulability Analysis of Real-time System Specifications [J]. IEEE Trans. Software Engineering， 1995， 21（1）：32-49

[2] 洪國(guó)彬.基于隨機(jī)Petri網(wǎng)的企業(yè)業(yè)務(wù)流程重組的理論與優(yōu)化方法研究[D].天津：天津大學(xué)， 2003.

[3] Ciardo G，German R，Lindemann C.A characterization of the stochastic process underlying a stochastic Petri net [J]. IEEE Trans on Software Engineering， 1994， 20 （7）：506-515

[4] Merlin P M，F(xiàn)arber D J.Recoverability of communication protocols： Implications of a theoretical study [J]. IEEE Trans on Communications， 1976， 24（9）：1036-1043

[5] 袁崇義.Petri網(wǎng)原理與應(yīng)用[M].北京：電子工業(yè)出版社，2005：35-36.