第3章 Petri網.ppt

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