petri net

petri net

Petri Net(PN) 是對離散並行系統的數學表示。Petri網是1962年由卡爾·A·佩特里發明的,適合於描述異步的、並發的計算機系統模型。Petri網既有嚴格的數學表述方式,也有直觀的圖形表達方式,既有豐富的系統描述手段和系統行為分析技術,又為計算機科學提供堅實的概念基礎。 由於Petri網能夠表達並發的事件,被認為是自動化理論的一種。研究領域趨向認為Petri網是所有流程定義語言之母。

基本介紹

經典的Petri網是簡單的過程模型,由兩種節點:庫所和變遷,有向弧,以及令牌等元素組成的。

結構元素

petri net petri net

(1) Petri網的元素:

庫所(Place)圓形節點

變遷(Transition)方形節點

有向弧(Connection)是庫所和變遷之間的有向弧

令牌(Token)是庫所中的動態對象,可以從一個庫所移動到另一個庫所。

Token,又有一部分學者翻譯為托肯,表示庫所中的資源對象。

(2) Petri網的規則是:

有向弧是有方向的

兩個庫所或變遷之間不允許有弧

庫所可以擁有任意數量的令牌

行為

如果一個變遷的每個輸入庫所(input place)都擁有令牌,該變遷即為被允許(enable)。一個變遷被允許時,變遷將發生(fire),輸入庫所(input place)的令牌被消耗,同時為輸出庫所(output place)產生令牌。

變遷的發生是原子的

有兩個變遷都被允許的可能,但是一次只能發生一個變遷

如果出現一個變遷,其輸入庫所的個數與輸出庫所的個數不相等,令牌的個數將發生變化

Petri網路是靜態的

Petri網的狀態由令牌在庫所的分布決定

Petri網的形式化定義

一個經典的Petri網由四元組(庫所,變遷,輸入函式,輸出函式)組成。任何圖都可以映射到這樣一個四元組上,反之亦然。

流程建模

一個流程的狀態是由在場所中的令牌建模的,狀態的變遷是由變遷建模的。令牌表示事物(人,貨物,機器),信息,條件,或對象的狀態; 庫所代表庫所,通道或地理位置;變遷代表事件,轉化或傳輸。

一個流程有當前狀態,可達狀態,不可達狀態。

經典Petri網的局限性

沒有測試庫所中零令牌的能力

模型容易變得很龐大

模型不能反映時間方面的內容

不支持構造大規模模型,如自頂向下或自底向上

高級Petri網

為了解決經典Petri網中的問題,研究出了高級Petri網,在以下方面進行了擴展:

令牌著色

一個令牌通常代表具有各種屬性的對象,因此令牌擁有值(顏色)代表由令牌建模的對象的具體特徵,如一個令牌代表一個工人(張三,28歲,經驗3級)。

時間

為了進行分析,我們需要建模期間,延遲等,因此每一個令牌擁有一個時間戳,變遷決定生產出的令牌的延遲。

層次化

構造一個複雜性與數據流圖相當的Petri網的機制。子網是由庫所,變遷和子網構成的網路。

時序

增加時序邏輯的定義,更好的描述行為過程。

Petri網的套用

Petri網的套用非常廣泛,以下是Petri網比較常用的幾種套用:

軟體設計

工作流管理

工作流模式

數據分析

並行程式設計

協定驗證

相關詞條

相關搜尋

熱門詞條

聯絡我們