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