第3章 Petri網(wǎng).ppt

1 Chapter3Petri網(wǎng) 一 基本定義 1 Petri網(wǎng)結(jié)構(gòu) 2 普通網(wǎng) 3 位置 遷移Petri網(wǎng) 二 Petri網(wǎng)的性質(zhì) 1 行為性質(zhì) 2 結(jié)構(gòu)性質(zhì) 三 Petri網(wǎng)分析技術(shù) 1 結(jié)構(gòu)化簡 2 可達樹 覆蓋樹 3 狀態(tài)方程 不變量 四 Petri網(wǎng)規(guī)格的例 1 哲學(xué)家就餐問題 2 生產(chǎn)者 消費者問題 Petri網(wǎng)的概念最早是由德國的CarlAdamPetri于1962年在其博士論文 自動機通信 中提出來的 它是一種適合于并發(fā) 異步 分布式軟件系統(tǒng)規(guī)格與分析的形式化方法 Petri網(wǎng)分為位置 遷移Petri網(wǎng)和高級Petri網(wǎng)兩類 高級Petri網(wǎng)包括 謂詞 遷移Petri網(wǎng) 有色Petri網(wǎng) 計時Petri網(wǎng)等 2 一 基本定義 任何系統(tǒng)都可抽象為狀態(tài) 或者條件 活動 或者事件 及其之間關(guān)系的三元結(jié)構(gòu) 在Petri網(wǎng)中 狀態(tài)用位置 place 表示 活動用遷移 transition 表示 遷移的作用是改變狀態(tài) 位置的作用是決定遷移能否發(fā)生 遷移和位置之間的這種依賴關(guān)系用流來表示 Petri網(wǎng)結(jié)構(gòu) Petri網(wǎng)結(jié)構(gòu)是一個三元組N P T F 其中 P p1 p2 pn 是有限位置集合 T t1 t2 tn 是有限遷移集合 P T P T F P T T P 為流關(guān)系 例 Petri網(wǎng)結(jié)構(gòu)N P T F P p1 p2 p3 p4 p5 p6 T t1 t2 t3 t4 t5 F p1 t1 t1 p2 t1 p3 p2 t2 p3 t3 t2 p4 t3 p5 p4 t4 p5 t4 t4 p6 p6 t5 t5 p1 3 一 基本定義 子網(wǎng)結(jié)構(gòu) 對于N1 P1 T1 F1 和N2 P2 T2 F2 如果P1 P2 T1 T2且F1 F2 P1 T1 T1 P1 則稱N1是N2的子網(wǎng)結(jié)構(gòu) 前集和后集 對于一個Petri網(wǎng)結(jié)構(gòu)N P T F 設(shè)x P T 令 x y y y x F x y y x y F 那么稱 x為x的前集或輸入集 x 稱為x的后集或輸出集 在N P T F 中 如果對所有的x P T 都有 x x 則稱N為單純網(wǎng) purenet 簡稱純網(wǎng) 如果對所有的x y X 都有 x y x y x y 則稱N為簡單網(wǎng) simplenet Petri網(wǎng)允許位置中包含令牌 token 令牌可以依據(jù)遷移的引發(fā)而重新分布 具有動態(tài)特征的Petri網(wǎng)定義如下 普通Petri網(wǎng) 普通Petri網(wǎng)形式上定義為一個四元組PN P T F M0 N M0 其中 N P T F 是一個Petri網(wǎng)結(jié)構(gòu) M P Z 非負(fù)整數(shù)集合 是位置集合上的標(biāo)識 marking 向量 對于任一位置p P 以M p 表示標(biāo)識向量M中位置p所對應(yīng)的分量 稱為位置p上的標(biāo)識或者令牌數(shù)目 M0是初始標(biāo)識向量 在Petri網(wǎng)的圖形表示中 標(biāo)記或令牌用位置中的黑點或數(shù)字表示 同一位置中的多個標(biāo)記代表同一類完全等價的個體 標(biāo)識向量表示了令牌在位置中的分布 5 一 基本定義 在Petri網(wǎng)中 依據(jù)遷移的使能 enable 條件 可以使得使能的遷移引發(fā) fire 遷移的引發(fā)會依據(jù)引發(fā)規(guī)則實現(xiàn)令牌的移動 不斷變化著的令牌重新分布就描述了系統(tǒng)的動態(tài)行為演化 遷移的使能條件I 對于Petri網(wǎng)PN P T F M 如果 p1 p1 t M p1 1 則稱t在M下使能 記為M t 遷移的引發(fā)規(guī)則I 對于Petri網(wǎng)PN P T F M 任何在M下使能的遷移t將會引發(fā) 遷移t的引發(fā)使得位置中令牌重新分布 從而將標(biāo)識M變成新標(biāo)識M 并稱M 為M的后繼標(biāo)識 并記為M t M 對于 p P M p 可通過下式計算 M p 1p t t M p M p 1p t tM p 其它 在圖 a 所示Petri網(wǎng)中 變遷t1和t2是使能的 在這種情況下 該Petri網(wǎng)的演化 即令牌的變化就可能存在如下3種不同方式 引發(fā)t1 引發(fā)t2 或者引發(fā)t1和t2 也就是說 在給定Petri網(wǎng)的初始標(biāo)識后 其演化過程可能是不同的 具有不確定性 引發(fā)t1所得到的圖 b 所示狀態(tài) 引發(fā)t2所得到的圖 c 所示狀態(tài) 引發(fā)t1和t2得到圖 d 所示狀態(tài) 在圖 b 的情況下 變遷t2和t3使能 在引發(fā)變遷t2后 將得到圖 d 所示狀態(tài) 在圖 c 的情況下 變遷t1和t4使能 在引發(fā)變遷t1后 將同樣得到圖 d 所示狀態(tài) 圖 d 所示Petri網(wǎng)中 變遷t3和t4是使能的 令牌的變化就可能存在如下2種不同方式 引發(fā)t3 或者引發(fā)t4 引發(fā)t3得到圖 e 所示的下一個狀態(tài) 引發(fā)t4得到圖 f 所示狀態(tài) 在圖 e 的情況下 變遷t5使能 引發(fā)變遷t5后 將得到圖 c 所示狀態(tài) 在圖 f 的情況下 變遷t6使能 引發(fā)變遷t6后 將得到圖 b 所示狀態(tài) 一 基本定義 一個沒有任何輸入位置的遷移叫源遷移 一個源遷移的使能是無條件的 一個源遷移的引發(fā)只會產(chǎn)生令牌 而不消耗任何令牌 一個沒有任何輸出位置的遷移叫阱遷移 一個阱遷移的引發(fā)只會消耗令牌 而不產(chǎn)生任何新的令牌 位置 遷移Petri網(wǎng) 位置 遷移Petri網(wǎng) 簡稱為Petri網(wǎng) 形式上定義為一個六元組PN P T F K W M0 N K W M0 其中 N P T F 是一個Petri網(wǎng)結(jié)構(gòu) K P Z 是位置上的容量函數(shù) Z 是正整數(shù)集合 規(guī)定了位置上可以包含的令牌的最大數(shù)目 對于任一位置p P 以K p 表示向量K中位置p所對應(yīng)的分量 若K p 表示位置p的容量為無窮 9 W F Z 是流關(guān)系上的權(quán)函數(shù) 規(guī)定了令牌傳遞中的加權(quán)系數(shù) 對于任一弧f F 以W f 表示向量W中弧f所對應(yīng)的分量 M P Z 非負(fù)整數(shù)集合 是位置集合上的標(biāo)識向量 對于任一位置p P 以M p 表示標(biāo)識向量M中位置p所對應(yīng)的分量 并且必須滿足M p K p M0是初始標(biāo)識向量 10 在Petri網(wǎng)的圖形表示中 對于弧f F 當(dāng)W f 1時 將W f 標(biāo)注在弧上 當(dāng)W f 1時 省略W f 的標(biāo)注 當(dāng)一個位置的容量有限時 通常將K p 寫在位置p的圓圈旁 當(dāng)K p 時 通常省略K p 的標(biāo)注 容量函數(shù)和權(quán)函數(shù)均為常量1的Petri網(wǎng)稱為基本Petri網(wǎng) 簡稱基本網(wǎng) 或條件 事件網(wǎng) 容量函數(shù)恒為無窮和權(quán)函數(shù)恒為1的Petri網(wǎng)稱為普通Petri網(wǎng) 簡稱為普通網(wǎng) 顯然 基本網(wǎng)和普通網(wǎng)都是Petri網(wǎng)的特殊情形 基本網(wǎng)和普通網(wǎng)可以用四元組PN P T F M 來表示 遷移的使能條件II 對于Petri網(wǎng)PN P T F K W M 如果 p1 p1 t M p1 W p1 t 且 p2 p2 t K p2 M p2 W t p2 則稱t在M下使能 記為M t 遷移的引發(fā)規(guī)則II 對于Petri網(wǎng)PN P T F K W M 任何在M下使能的遷移t將會引發(fā) 遷移t的引發(fā)使得位置中令牌重新分布 從而將標(biāo)識M變成新標(biāo)識M 并記為M t M 對于 p P M p 可通過下式計算 M p W p t p t t M p M p W t p p t tM p W p t W t p p t t M p p t t W t1 p2 2 W t3 p5 3 W p6 t5 3 W p1 t1 W t1 p3 W p2 t2 W p3 t3 W t2 p4 W p4 t4 W p5 t4 W t4 p6 W t5 p1 1 K p2 3 K p4 K p5 4 K p6 6 K p1 K p3 K p5 M 1 0 0 1 0 0 的Petri網(wǎng) 順序 并發(fā) 沖突 混惑結(jié)構(gòu)的Petri網(wǎng)模型 順序關(guān)系 設(shè)M為Petri網(wǎng)PN的一個標(biāo)識 若存在t1和t2使得M t1 M 且 M t2 M t2 亦即 在M標(biāo)識下 t1使能 而t2不使能 且t1的引發(fā)會使t2使能 即t2的使能以t1的引發(fā)為條件 則稱t1和t2在M下有順序關(guān)系 并發(fā)關(guān)系 設(shè)M為Petri網(wǎng)PN的一個標(biāo)識 若存在t1和t2使得M t1 和M t2 并滿足M t1 M1 M1 t2 且M t2 M2 M2 t1 則稱t1和t2在M下并發(fā) 就是說在M標(biāo)識下 t1和t2都使能 且它們當(dāng)中任一個遷移的引發(fā)都不會使另一個遷移不使能 沖突關(guān)系 設(shè)M為Petri網(wǎng)PN的一個標(biāo)識 若存在t1和t2使得M t1 和M t2 并滿足M t1 M1 M1 t2 且M t2 M2 M2 t1 則稱t1和t2在M下沖突 就是說M標(biāo)識下 t1和t2都使能 但它們當(dāng)中任一個遷移引發(fā)都會使另一個遷移不使能 混惑關(guān)系 某些情形下 一個Petri網(wǎng)中可能同時存在著并發(fā)和沖突 而且并發(fā)遷移的引發(fā)會引起沖突的消失或出現(xiàn) 下圖所示的Petri網(wǎng)中 t1和t3是兩個并發(fā)遷移 若t3先于t1引發(fā) 則t2獲得發(fā)生權(quán) 而且t2和t1處于競爭資源的沖突狀態(tài) 若進一步在解決沖突時讓t2引發(fā) 則t1就失去了曾經(jīng)擁有的發(fā)生權(quán) 如果在t1和t2的沖突中讓t1引發(fā) 則p5獲得令牌 系統(tǒng)到達最終狀態(tài) 0 0 1 0 1 0 從初始狀態(tài) 1 1 0 1 0 0 到達 0 0 1 0 1 0 的另一種可能是t1先引發(fā) 然后t3引發(fā) t1和t3并發(fā)也到達這一狀態(tài) 這后兩種情況不會出現(xiàn)沖突 換句話說 從所觀察到的狀態(tài)變化 1 1 0 1 0 0 0 0 1 0 1 0 無法判斷其間是否出現(xiàn)過沖突 象這樣并發(fā)和沖突混合在一起產(chǎn)生的困惑 使人無法從終態(tài)判斷是否有沖突發(fā)生過 所以將這種情況稱為 混惑 16 二 Petri網(wǎng)的性質(zhì) Petri網(wǎng)具有兩類性質(zhì) 與初始標(biāo)識有關(guān)的和與初始標(biāo)識無關(guān)的 前者稱為標(biāo)識有關(guān)性質(zhì)或者行為性質(zhì) 后者稱為標(biāo)識無關(guān)性質(zhì)或者結(jié)構(gòu)性質(zhì) 1 行為性質(zhì)可達性 可達性是研究任何系統(tǒng)動態(tài)行為的基礎(chǔ) 按照遷移引發(fā)規(guī)則 使能遷移的引發(fā)將改變令牌的分布 產(chǎn)生新的標(biāo)識 對于初始標(biāo)識M0 如果存在一系列遷移t1 t2 tn的引發(fā)使得M0轉(zhuǎn)換為Mn 則稱標(biāo)識Mn是從M0可達的 記為M0 Mn 其中 M0t1M1t2M2 tnMn 或簡記為 t1t2 tn 稱為遷移的引發(fā)序列 對于Petri網(wǎng)PN N M0 所有可達的標(biāo)識組成一可達標(biāo)識集 記為R N M0 或R M0 從M0出發(fā)的所有可能引發(fā)序列組成一引發(fā)序列集 記為L N M0 或L M0 17 行為性質(zhì) 有界性和安全性 在PN N M0 中 若存在一個非負(fù)整數(shù)k 使得M0的任一可達標(biāo)識的每個位置中的標(biāo)記數(shù)都不超過k 即 k Z 對 M R M0 都有k M p 則稱位置p為k有界 如果PN中每一位置都是k有界 則稱PN為k有界 位置p為1有界稱為位置p是安全的 如果PN中每一位置都是安全的 則稱PN是安全的 這里的k與Petri網(wǎng)定義中的位置容量K完全不同 是在無限容量網(wǎng)的運行過程中 自動地滿足k M p 而Petri網(wǎng)定義中是對某個位置的容量加以限制 從而也強制地使系統(tǒng)運行過程中每個位置中的令牌數(shù)不超過一定的上限 18 行為性質(zhì) t4 右圖中Petri網(wǎng) 在初始標(biāo)識 1 0 1 0 下的可達標(biāo)識為 0 1 1 0 0 0 0 1 0 0 1 0 對應(yīng)的遷移引發(fā)序列為t2t3t4 所以R M0 0 1 1 0 0 0 0 1 0 0 1 0 L M0 t2t3t4 故該Petri網(wǎng)在M0下是有界的和安全的 標(biāo)識 0 1 1 1 1 0 0 1 1 0 0 0 都是不可達標(biāo)識 左圖中Petri網(wǎng) 在初始標(biāo)識下可能的引發(fā)序列有t2t1t2t1 t2t3t4t1t2t3t4t1 t2t3t1t4t2t3t1t4 t2t3t4t1t2t1t2 等 由于引發(fā)序列t2t1t2t1 將使p3中的令牌無限制增多 故該Petri網(wǎng)不是有界的 19 行為性質(zhì) 活性 在PN N M0 中 若存在M R M0 使得遷移t使能 則t是潛在可引發(fā)的 如果對任何M R M0 遷移t都是潛在可引發(fā)的 即從M0可達的任一標(biāo)識出發(fā) 都可以通過執(zhí)行某一遷移序列而最終引發(fā)t 則稱t在標(biāo)識M0下是活的 如果所有遷移t都是活的 則稱PN是活的 或者稱M0是N的活標(biāo)識 對于M R M0 若不存在遷移引發(fā)序列使得遷移t最終引發(fā) 則稱遷移t是死遷移或死的 對于M R M0 若不存在任何遷移t使能 則稱PN包含一個死鎖 而標(biāo)識M稱為死標(biāo)識 活的PN中無死鎖 20 行為性質(zhì) 活性 活性是許多系統(tǒng)的理想特性 但這是不現(xiàn)實的 要驗證這一特性并不那么簡單 因此 可放寬對活性的限制 并定義不同的活性等級 Petri網(wǎng)中遷移t的活性分成如下5級 L0 活的 死的 在任何遷移序列 L M0 中 遷移t都不能引發(fā) L1 活的 可能引發(fā) 在某些 L M0 中 遷移t至少引發(fā)一次 L2 活的 給定一個正整數(shù)k 在某些 L M0 中 遷移t至少引發(fā)k次 L3 活的 在某些 L M0 中 遷移t可以無限次地引發(fā) L4 活的 對于每個M R M0 遷移t是L1 活的 如果一個Petri網(wǎng)的每一個遷移都是Lk 活的 則稱該Petri網(wǎng)為Lk 活的 k 0 1 2 3 4 如果一個遷移是Lk 活的 而不是Lk 1 活的 k 1 2 3 則稱該遷移是嚴(yán)格Lk 活的 顯然L0 活的實際上是永不引發(fā)的 其它4種活性之間存在如下關(guān)系 L4 活的 L3 活的 L2 活的 L1 活的 事實上 活性定義中 PN是活的 對應(yīng)于活性登記中的 L4 活的 圖中Petri網(wǎng) t1 t2 t3和t4分別是L0 L1 L2和L3 活的 因為t1總是不能引發(fā)的 一旦p1因t2引發(fā)而失去令牌 就無法再獲得令牌 即t2最多只能引發(fā)1次 t2引發(fā)后 t4不能再引發(fā) t3的最大引發(fā)次數(shù)為p2中的令牌數(shù) 即t4的引發(fā)次數(shù) 而t4的最大引發(fā)次數(shù)存在可以任意指定引發(fā)序列 在p1有令牌的情況下 t4可以反復(fù)連續(xù)發(fā)生 而不使p1失去令牌 因為無限次地引發(fā)t4可使p2中的令牌無限地增加 所以該Petri網(wǎng)不是有界的 圖中Petri網(wǎng)L M0 t2t4t5t1t3 t1 引發(fā)序列t2t4t5t1t3 使各遷移都引發(fā)一次 該Petri網(wǎng)是有界的和安全的 且嚴(yán)格L1 活的 p2 p4 嚴(yán)格L1 活的 活的 可逆性 在PN N M0 中 如果 M R M0 M0 R M 則稱該Petri網(wǎng)是可逆的 對于可逆的Petri網(wǎng) 存在引發(fā)序列 t1t2 tn 從 M R M0 返回到M0 在很多應(yīng)用中 僅要求系統(tǒng)回到某個特定狀態(tài) 而無需返回到初始狀態(tài) 稱這個特定狀態(tài)為主 home 狀態(tài) 即對于R M0 的每個標(biāo)識M 主狀態(tài)M 都是可達的 有界 非活 可逆R 1 0 0 R 0 1 0 R 0 0 1 0 1 0 1 0 0 0 0 1 L M0 t2t4t2t4 t3t5t3t5 t2t4t3t5t2t4t3t5 t3t5t2t4t3t5t2t4 無界 非活 不可逆 23 行為性質(zhì) 可覆蓋性 在PN N M0 中 如果對于M M R M0 使得 p P 有M p M p 則稱標(biāo)識M是可覆蓋的 持續(xù)性 在PN N M0 中 如果對于任何兩個使能的遷移 其中一個引發(fā)以后 另一個仍是使能的 則稱PN是持續(xù)的 也就是說 具有持續(xù)性的PN中 一個遷移一旦使能 將保持這種使能性直至它引發(fā)為止 24 行為性質(zhì) 同步距離 對于PN N M0 任意t1 t2 T的同步距離定義為d12 max t1 t2 其中 是從任意一個標(biāo)識M R M0 開始的引發(fā)序列 t1 和 t2 分別是引發(fā)序列 中t1和t2的引發(fā)次數(shù) 同步距離是用來刻劃不同形式的同步關(guān)系的 是兩個遷移之間這種相對關(guān)系的一種定量描述 公平性 在PN N M0 中 對于t1和t2 若不引發(fā)其中一個 另一個可以引發(fā)的最大次數(shù)為有界的 則稱這兩個遷移具有有界公平關(guān)系 若PN中任意一對遷移都存在有界公平關(guān)系 則稱PN為有界公平網(wǎng) 對于一個引發(fā)序列 若 引發(fā)序列中遷移的數(shù)目 為有限數(shù) 或PN中的任何遷移t都在 中無限次出現(xiàn) 則稱 為無條件 全局 公平的 如果 L M0 都是無條件公平的 則稱PN為無條件公平網(wǎng) 25 2 結(jié)構(gòu)性質(zhì) Petri網(wǎng)的結(jié)構(gòu)性質(zhì)取決于其拓?fù)浣Y(jié)構(gòu)N 而與初始標(biāo)識無關(guān) 這里 與初始標(biāo)識無關(guān) 有兩層含義 任何初始標(biāo)識M0下均成立 或者存在某一個初始標(biāo)識M0使其成立 結(jié)構(gòu)活性 對于N 若存在活的初始標(biāo)識M0 則稱N為結(jié)構(gòu)活的 結(jié)構(gòu)有界性 如果N對于任何初始標(biāo)識M0都有界 則稱N具有結(jié)構(gòu)有界性 守恒性 對于 M R M0 如果對應(yīng)于所有 某些 位置p存在正整數(shù)Y p 使得標(biāo)識的加權(quán)和MTY M0TY 常數(shù) 則稱N為 部分 守恒的 26 2 結(jié)構(gòu)性質(zhì) 可重復(fù)性 如果N存在一個初始標(biāo)識M0和一個引發(fā)序列 L M0 使得所有 某些 遷移引發(fā)無限次 則稱N為 部分 可重復(fù)的 相容性 如果N存在一個初始標(biāo)識M0和一個從M0返回到M0的引發(fā)序列 L M0 使得所有 某些 遷移至少引發(fā)一次 則稱N為 部分 相容的 結(jié)構(gòu)有界公平性 對于任何初始標(biāo)識 如果兩個遷移之間總存在有界公平關(guān)系 則稱這兩個遷移具有結(jié)構(gòu)有界公平關(guān)系 如果N中任何遷移都是有界公平的 則稱N為結(jié)構(gòu)有界公平的 三 Petri網(wǎng)的分析技術(shù) 1 結(jié)構(gòu)化簡結(jié)構(gòu)化簡是處理復(fù)雜問題的一種方法 其基本原則是在保持化簡前后Petri網(wǎng)所具有的某些性質(zhì)不變的前提下 將多個不同的位置或遷移抽象為單個位置或遷移 消除自循環(huán)位置 消除自循環(huán)遷移 合并串行位置 合并并行位置 合并串行遷移 合并并行遷移 2 可達樹 覆蓋樹 對于一個Petri網(wǎng)PN N M0 以M0作為樹根 樹中的結(jié)點表示M0經(jīng)過使能遷移的引發(fā)所產(chǎn)生的標(biāo)識 結(jié)點之間的連線表示了標(biāo)識和遷移之間的關(guān)系M t M 可達標(biāo)識的這種樹結(jié)構(gòu)表示 稱之為Petri網(wǎng)的可達樹 對于有界Petri網(wǎng) 可達樹中包含了其所有可達標(biāo)識 在這種情況下 前面討論的Petri網(wǎng)的所有性質(zhì)問題都能由可達樹來分析 2 可達樹 覆蓋樹 2 可達樹 覆蓋樹 31 2 可達樹 覆蓋樹 對于無界Petri網(wǎng) 由于可達標(biāo)識將無限制地增長 故可達樹結(jié)構(gòu)的結(jié)點也將無限制地增長 為了使所得到的樹保持有限 可引入一個被認(rèn)為是 無限 的特殊符號 該 具有如下特性 k Z 整數(shù)集 k k 且 對于結(jié)點M 如果從M0到M的路徑上存在結(jié)點M 滿足 p P M p M p 且M M 即 M 是可覆蓋的 此時 可對M中滿足M p M p 的p用 重置M p 這樣得到的樹就稱為Petri網(wǎng)的覆蓋樹 2 可達樹 覆蓋樹 覆蓋樹的構(gòu)造算法如下 step1 將初始標(biāo)識M0作為樹根 并標(biāo)記為new step2 若不存在標(biāo)記為new的標(biāo)識 停機 step3 選擇一個標(biāo)記為new的標(biāo)識M 重復(fù)以下各步 若從根節(jié)點M0到M的路徑上有與M相同的標(biāo)識 將M標(biāo)記為old 并轉(zhuǎn)step2 若標(biāo)識M下沒有遷移可以引發(fā) 則將M記為dead end 并轉(zhuǎn)step2 若標(biāo)識M下存在可以引發(fā)的遷移 則對每個使能遷移t進行如下各步 a 計算在t引發(fā)后M的后繼標(biāo)識M 注 若M p 則M p b 若從根節(jié)點M0到M 的路徑中存在結(jié)點M 滿足 p P M p M p 且M M 則對M 中的每個滿足M p M p 的p 用 重置M p c 將M 作為樹的一個標(biāo)志為new節(jié)點 并從M到M 畫用t標(biāo)注的弧 step4 將M標(biāo)記為old 并轉(zhuǎn)step2 33 2 可達樹 覆蓋樹 利用覆蓋樹 可以分析Petri網(wǎng)PN N M0 的如下性質(zhì) 當(dāng)且僅當(dāng)覆蓋樹中不出現(xiàn)含有 的標(biāo)識時 PN有界 且因此R M0 是有限的 當(dāng)且僅當(dāng)覆蓋樹中每個標(biāo)識的元素都為0或1時 PN是安全的 當(dāng)且僅當(dāng)遷移t T不出現(xiàn)在覆蓋樹中時 t為死的 即存在死鎖 由于 的存在 于覆蓋樹一般不能用來分析可達性和活性 34 3 狀態(tài)方程 不變量 Petri網(wǎng)的網(wǎng)結(jié)構(gòu)可以用一個矩陣來表示 對于PN N M0 令P p1 p2 p3 pm T t1 t2 t3 tn 關(guān)聯(lián)矩陣 Petri網(wǎng)PN N M0 的關(guān)聯(lián)矩陣為一個以P T作序標(biāo)的矩陣C P T Z 整數(shù)集合 其矩陣元素C pi tj W tj pi W pi tj 也可以寫作 Cij m n Cij m n Cij m n或者C C C 其中 Cij W tj pi 是從遷移tj到它的輸出位置pi的弧的權(quán) Cij W pi tj 是從遷移tj的輸入位置pi到遷移tj的弧的權(quán) 并稱C 為Petri網(wǎng)的輸入關(guān)聯(lián)矩陣 C 為Petri網(wǎng)的輸出關(guān)聯(lián)矩陣 35 如果Petri網(wǎng)PN N M0 是一個純網(wǎng) 即滿足 x P T x x 則對任何pi tj Cij 和Cij 中必至少有一個為0 所以關(guān)聯(lián)矩陣是對Petri網(wǎng)結(jié)構(gòu)的準(zhǔn)確描述 如果PN不是純網(wǎng) 那么Cij 和Cij 就可能全不為0 于是Cij Cij 就是t引發(fā)時輸入輸出的最終效果 而不是對輸入和輸出的準(zhǔn)確描述 36 3 狀態(tài)方程 不變量 S 向量 T 向量 以位置集P為序標(biāo)集的列向量V P Z叫做PN的S 向量 以遷移集T為序標(biāo)集的列向量U T Z叫做Petri網(wǎng)的T 向量 對于關(guān)聯(lián)矩陣為C C C 的Petri網(wǎng) 如果M1 tj M2 則標(biāo)識向量M2和M1之間的關(guān)系 可用下述等式描述 M2 M1 C j C j表示矩陣C的第j列向量 狀態(tài)方程 若M0 M 則標(biāo)識向量M0和M之間的關(guān)系為 M M0 C U Petri網(wǎng)的狀態(tài)方程其中 U是PN的T 向量 對于ti T U ti 對應(yīng)于ti在 中出現(xiàn)的次數(shù) 稱為遷移的引發(fā)向量 37 3 狀態(tài)方程 不變量 38 3 狀態(tài)方程 不變量 從關(guān)聯(lián)矩陣和狀態(tài)方程角度 Petri網(wǎng)的遷移使能條件和引發(fā)規(guī)則有如下形式 遷移的使能條件III 對于容量無限Petri網(wǎng)PN N M0 M tj iff pi P Cij M pi 或者C j M 其中 C j表示矩陣C 的第j列 遷移的引發(fā)規(guī)則III 對于Petri網(wǎng)PN N M0 在M下使能遷移tj的引發(fā) 產(chǎn)生新的標(biāo)識M M M C E其中 E是第j個元素為1的單位列向量 39 3 狀態(tài)方程 不變量 狀態(tài)方程為部分解決可達性分析問題提供了一個依據(jù) 對于Petri網(wǎng)PN N M0 若Md從M0可達 即Md R M0 則Md 0 且必存在遷移引發(fā)序列 t1t2 tl 依次引發(fā)這些遷移后 標(biāo)識從M0變成Md 令uk是第k個元素為1 其余元素為0的引發(fā)向量 代入 M Md M0 C X 跌代l次可得 X 0X中各元素即為所對應(yīng)遷移的引發(fā)次數(shù) 亦即 方程 M Md M0 C X必然存在一個非負(fù)整數(shù)解 該解即為遷移引發(fā)次數(shù)向量 40 3 狀態(tài)方程 不變量 S 不變量 S invariant 設(shè)I為PN的S 向量 C是PN的關(guān)聯(lián)矩陣 若CT I 0 就稱I為PN的S 不變量 PI p P I p 0 稱為I的支撐集 若I 0 就稱I為非負(fù)S 不變量 PN中有某幾個位置中包含的令牌個數(shù)之總和在任何可達標(biāo)識下都不變 T 不變量 T invariant 設(shè)J為PN的T 向量 C是PN的關(guān)聯(lián)矩陣 若C J 0 就稱J為PN的T 不變量 PJ t T J t 0 稱為J的支撐集 若J 0 就稱J為非負(fù)T 不變量 PN中有某幾個遷移的引發(fā) 會使得Petri網(wǎng)的標(biāo)識向量恢復(fù)到先前的狀態(tài) 41 3 狀態(tài)方程 不變量 圖中的Petri網(wǎng) 在任何情況下 所有位置中包含的令牌總數(shù)始終為1 從而得到該Petri網(wǎng)的S 不變量 111 T 同時 遷移t1 t2各引發(fā)一次 Petri網(wǎng)的狀態(tài)從M返回到M 則t1 t2是該Petri網(wǎng)的一個T 不變量 類似地 遷移t3 t4各引發(fā)一次 Petri網(wǎng)的狀態(tài)從M返回到M 遷移t1 t2 t3 t4各引發(fā)一次 Petri網(wǎng)的狀態(tài)也從M返回到M 因此 該Petri網(wǎng)有如下三個T 不變量 1100 T 0011 T 1111 T 基于狀態(tài)方程以及T 不變量和S 不變量 可以對Petri網(wǎng)的一些結(jié)構(gòu)性質(zhì)進行分析 四 Petri網(wǎng)規(guī)格的例 1 哲學(xué)家就餐問題五位哲學(xué)家pi i 0 1 2 3 4 圍圓桌而坐 pi和pi 1 p5 p0 共享餐叉fi 已知pi用餐時需同時占有fi和fi 1兩把叉子 f4 f0 1 該問題中 每一位哲學(xué)家pi共有三種可能的狀態(tài) 饑餓狀態(tài)hi 等待資源 用餐狀態(tài)ei 使用資源 思考問題ki 無需資源 狀態(tài)之間通過事件獲得資源ti1 事件釋放資源ti2和事件請求資源ti3聯(lián)系在一起 用位置 遷移分別表示相應(yīng)的狀態(tài)和事件 可以得到哲學(xué)家pi的Petri網(wǎng)模型規(guī)約 圖中位置pi標(biāo)記有1個令牌表示 哲學(xué)家pi的正在思考問題 fi和fi 1兩把叉子均未被占用 將五位哲學(xué)家的行為均用Petri網(wǎng)模型規(guī)格 并通過它們之間的資源 叉子 共享關(guān)系聯(lián)系起來 便可以得到整個問題的Petri網(wǎng)規(guī)格 四 Petri網(wǎng)規(guī)格的例 2 生產(chǎn)者 消費者問題生產(chǎn)者 消費者系統(tǒng)包含一個生產(chǎn)者和一個消費者 生產(chǎn)者進程產(chǎn)生消息 并把產(chǎn)生的消息寫入一個能容納兩個消息的緩存區(qū)中 生產(chǎn)者在進行 生產(chǎn) 動作后 狀態(tài)由P1轉(zhuǎn)變?yōu)镻2 而在 寫 動作后 狀態(tài)由P2恢復(fù)為P1 消費者進程能讀取消息 并把消息從