基于FTPN的實時系統(tǒng)資源沖突分析

王梅

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

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

中圖分類號：TP181 文獻標識碼：A 文章編號：1009-3044（2014）21-5112-03

1 概述

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

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

3 沖突的檢測

4 沖突的消解

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

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

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

5 實例分析

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

6 結論

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

參考文獻：

[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] 洪國彬.基于隨機Petri網(wǎng)的企業(yè)業(yè)務流程重組的理論與優(yōu)化方法研究[D].天津：天津大學， 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)原理與應用[M].北京：電子工業(yè)出版社，2005：35-36.