隨機Petri網

Petri網的概念源於1962年C. A. Petri 的博士論文《用自動機通信》,適合於描述異步的、並發的計算機系統模型。 Petri網既有嚴格的數學表述方式,也有直觀的圖形表達方式,既有豐富的系統描述手段和系統行為分析技術,又為計算機科學提供堅實的概念基礎。


Petri網是對離散並行系統的數學表示。
經過三十多年的發展,Petri網理論已經成為具有嚴密數學模型,多抽象層次、多用途的通用網論,並逐漸成為各相關學科的“通用語言”。Petri網作為一種圖形化、數學化建模工具,能夠提供一個集成的建模、分析和控制環境,為系統的設計提供便利。針對Petri網模型,除了利用可達樹、可達圖和狀態方程等方法進行性能分析外,仿真分析也是一種有效工具。
由於Petri網能夠表達並發的事件,被認為是自動化理論的一種。研究領域趨向認為Petri網是所有流程定義語言之母。
* 經典Petri網Petri網的結構

一個已標識的Petri網是一個六元組:
PN={P,T,F,K,W,M0},
其中
P={P1,P2,…Pm,},庫所集,
T={T1,T2,…Tm,},變遷集,
F(P×T)∪(T×P),弧集, ⊆
K:P→N+∪{ω},庫所容量函式,
K(P)=ω表示P的容量為無窮,N+={1,2,…},
W:F→N+,弧上權,
M0:P→N,初始標誌,要求:P∩T=,P∪T≠ф,
M:P→N,N={0,1,2,…},網的標識,且
∀Pi⊆P,M(Pi)≤K(Pi),i=1,…m。
(P,T,F)被稱為PN的基網,記為N。
Petri網的圖形表示就是一種有向圖,它包括兩類節點:庫所(用圓表示)和變遷(用短線表示)。弧用來表示流關係。Petri網的狀態由標識M來表示,在某一時刻的標識決定該PN的狀態。圖1表示一個已標識的PN,各庫所包含整數(正或零)個標記(稱為token或marking),用圓點表示,初始標識M0=(1,0,0,0,0),下文稱為令牌。
標識在Petri網中的變化遵循一定的規則——變遷規則:(1)一個變遷,如果它的每一個輸入庫所(庫所到變遷存在有向弧)都包含至少一個標記,則這個變遷是使能的;(2)一個使能變遷的激發,將引起其每個輸入庫所中標記減少,而每個輸出庫所(變遷到庫所存在有向弧)中增加標記。

Petri網的基本特性如下:

可達性:指系統運行過程中能達到指定的狀態。狀態M1從狀態M可達,是指存在使能的變遷序列σ,使得M[σ>M1。
有界性(安全性):反映系統運行過程中對資源變數的需求。在理論分析時常可假定庫所容量為無窮,但在實際系統設計中,必須使網路中的每個庫所在任何狀態下的標誌數小於庫所的容量,這樣才能保證系統的正常運行,不至於產生溢出現象。
活性:表明系統能正常運行,即無死鎖。此特性在系統設計中很重要,要保證系統避免死鎖。
回復性:表明系統運行的周期性或循環性。
公平性:反映系統的無飢餓性,即系統的各個子部分在競爭共享資源時不出現飢餓現象。
可逆性:表明系統運行的可回復性,即系統可以由當前狀態返回到初始狀態;
保守性:表明在實際系統中的資源是受限的,即保守的。
一致性:對並行系統和並行算法比較重要,表明系統的兩個行為之間不存在衝突。

Petri網的規則是:

+ 有向弧是有方向的
+ 兩個庫所或變遷之間不允許有弧
+ 庫所可以擁有任意數量的令牌
o 行為
如果一個變遷的每個輸入庫所(input place)都擁有令牌,該變遷即為被允許(enable)。一個變遷被允許時,變遷將發生(fire),輸入庫所(input place)的令牌被消耗,同時為輸出庫所(output place)產生令牌。
+ 變遷的發生是原子的
+ 有兩個變遷都被允許的可能,但是一次只能發生一個變遷
+ 如果出現一個變遷,其輸入庫所的個數與輸出庫所的個數不相等,令牌的個數將發生變化
+ Petri網路是靜態的
+ Petri網的狀態由令牌在庫所的分布決定
o Petri網流程建模
一個流程的狀態是由在場所中的令牌建模的,狀態的變遷是由變遷建模的。令牌表示事物(人,貨物,機器),信息,條件,或對象的狀態; 庫所代表庫所,通道或地理位置;變遷代表事件,轉化或傳輸。
一個流程有當前狀態,可達狀態,不可達狀態。
o 經典Petri網的局限性
+ 沒有測試庫所中零令牌的能力
+ 模型容易變得很龐大
+ 模型不能反映時間方面的內容
+ 不支持構造大規模模型,如自頂向下或自底向上

* 高級Petri網

為了解決經典Petri網中的問題,增強對系統的建模能力,研究出了高級Petri網,在以下方面進行了擴展:
o 令牌著色
一個令牌通常代表具有各種屬性的對象,因此令牌擁有值(顏色)代表由令牌建模的對象的具體特徵,如一個令牌代表一個工人(張三,28歲,經驗3級)。
o 時間
為了進行分析,我們需要建模期間,延遲等,因此每一個令牌擁有一個時間戳,變遷決定生產出的令牌的延遲。
o 層次化
構造一個複雜性與數據流圖相當的Petri網的機制。子網是由庫所,變遷和子網構成的網路。
o 時序
增加時序邏輯的定義,更好的描述行為過程。
* Petri網的套用
Petri網的套用非常廣泛,以下是Petri網比較常用的幾種套用:
o 軟體設計
o 工作流管理
o 工作流模式
o 數據分析
o 並行程式設計
o 協定驗證

相關詞條

相關搜尋

熱門詞條

聯絡我們