第二部分Petri網(wǎng)動(dòng)態(tài)質(zhì)

1、提綱n網(wǎng)系統(tǒng)網(wǎng)系統(tǒng)(以原型以原型Petri網(wǎng)為模型網(wǎng)為模型)運(yùn)行過程中的一些運(yùn)行過程中的一些性質(zhì)統(tǒng)稱為動(dòng)態(tài)性質(zhì)性質(zhì)統(tǒng)稱為動(dòng)態(tài)性質(zhì)(dynamic properties) 或行為性質(zhì)或行為性質(zhì)(behavioral properties)n這些性質(zhì)同這些性質(zhì)同Petri網(wǎng)所模擬的實(shí)際系統(tǒng)運(yùn)行過程中網(wǎng)所模擬的實(shí)際系統(tǒng)運(yùn)行過程中的某些方面的性質(zhì)有密切的聯(lián)系的某些方面的性質(zhì)有密切的聯(lián)系提綱n可達(dá)性可達(dá)性n有界性和安全性有界性和安全性n活性活性n公平性公平性n持續(xù)性持續(xù)性可達(dá)性n可達(dá)性是可達(dá)性是Petri網(wǎng)的最基本的動(dòng)態(tài)性質(zhì)，其余各種性質(zhì)都要通過可達(dá)網(wǎng)的最基本的動(dòng)態(tài)性質(zhì)，其余各種性質(zhì)都要通過可達(dá)性來定義

2、性來定義n定義定義2.1. 設(shè)設(shè)PN=(P,T;F,M)為一個(gè)為一個(gè)Petri網(wǎng)。網(wǎng)。如果存在如果存在t T，使，使MtM，則稱，則稱M為從為從M直接可達(dá)的直接可達(dá)的如果存在變遷序列如果存在變遷序列t1, t2, t3,tk和標(biāo)識(shí)序列和標(biāo)識(shí)序列M1,M2, M3,Mk使得使得 Mt1M1t2M2,Mk-1 tkMk (2.1) 則稱則稱Mk為從為從M可達(dá)的可達(dá)的從從M可達(dá)的一切標(biāo)識(shí)的集合記為可達(dá)的一切標(biāo)識(shí)的集合記為R(M)，約定，約定M R(M) 如果記變遷序列如果記變遷序列t1, t2, t3,tk為為 ，則，則(2.1)式也可記為式也可記為M Mk 可達(dá)性n設(shè)初始標(biāo)識(shí)設(shè)初始標(biāo)識(shí)M0表示系統(tǒng)

3、的初始狀態(tài)，表示系統(tǒng)的初始狀態(tài)，R(M0)給給出系統(tǒng)運(yùn)行過程中可能出現(xiàn)的全部狀態(tài)的集合。出系統(tǒng)運(yùn)行過程中可能出現(xiàn)的全部狀態(tài)的集合。n定義定義2.2. 設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)網(wǎng), M0為初始標(biāo)識(shí)。為初始標(biāo)識(shí)。PN的可達(dá)標(biāo)識(shí)集的可達(dá)標(biāo)識(shí)集R(M0)定義為定義為滿足下面兩條件的最小集合：滿足下面兩條件的最小集合： （1） M0 R(M0)； （2）若）若M R(M0)，且存在，且存在t T，使得，使得MtM，則則M R(M0) 可達(dá)性n定理定理2.1. 設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)，網(wǎng)， M0為初始標(biāo)識(shí)。則：為初始標(biāo)識(shí)。則： (1) 對任

4、意對任意M R(M0)，都有，都有R(M) R(M0) ； (2) 對任意對任意M1 , M2 R(M0)， R(M1)= R(M2)當(dāng)且當(dāng)且僅當(dāng)僅當(dāng)M1 R(M2)且且M2 R(M1) 。證：證：(1) 由于由于M R(M0)，所以，所以 M R(M): M R(M0) ，從而，從而R(M) R(M0) 。 同理可證同理可證(2)?？蛇_(dá)性n定義定義2.3. 設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)，網(wǎng)，M R(M0)。如果。如果 M R(M0)，都有，都有M R(M )，則，則稱稱M為為PN的一個(gè)可返回標(biāo)識(shí)或一個(gè)家態(tài)（的一個(gè)可返回標(biāo)識(shí)或一個(gè)家態(tài)（home state）。）。n

5、定義定義2.4. 設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)。如果網(wǎng)。如果M0是一個(gè)家態(tài)，則稱是一個(gè)家態(tài)，則稱PN為可逆網(wǎng)系統(tǒng)（為可逆網(wǎng)系統(tǒng)（reversible net system），或稱可回復(fù)系統(tǒng)。），或稱可回復(fù)系統(tǒng)。網(wǎng)系統(tǒng)家態(tài)的存在是一個(gè)良好性質(zhì)，在評測系統(tǒng)性能或在系統(tǒng)模擬過程中網(wǎng)系統(tǒng)家態(tài)的存在是一個(gè)良好性質(zhì)，在評測系統(tǒng)性能或在系統(tǒng)模擬過程中具有非常關(guān)鍵的作用。具有非常關(guān)鍵的作用?？蛇_(dá)性n推論推論2.1. 設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)，網(wǎng)， M1 , M2是是PN的家態(tài)，則的家態(tài)，則 R(M1)= R(M2) 。證明：因?yàn)樽C明：因?yàn)镸1 , M

6、2是是PN的家態(tài)，的家態(tài)，所以首先有所以首先有M1 R(M0)，M2 R(M0)，進(jìn)而進(jìn)而M1 R(M2)， M2 R(M1)。根據(jù)定理根據(jù)定理2.1(2)，則有，則有R(M1)= R(M2)。有界性和安全性n定義定義2.4. 設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)網(wǎng), p P。若存在正整數(shù)。若存在正整數(shù)B, 使得使得 M R(M0): M(p) B, 則稱庫所則稱庫所p為有界的為有界的(bounded)。并稱滿足此條件的最小正整數(shù)并稱滿足此條件的最小正整數(shù)B為庫所為庫所p的界，記為的界，記為B(p)。即。即B(p)=minB| M R(M0): M(p) B 當(dāng)當(dāng)B(p)=

7、1時(shí)，稱庫所時(shí)，稱庫所p為安全的（為安全的（safe）。）。n定義定義2.5. 設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)網(wǎng)。如果每個(gè)。如果每個(gè)p P都是都是有界的，則稱有界的，則稱PN為有界為有界Petri網(wǎng)。稱網(wǎng)。稱 B(PN)=maxB(p)| p P為為PN的界。當(dāng)?shù)慕?。?dāng)B(PN)=1時(shí)，稱時(shí)，稱PN為安全的。為安全的。有界性和安全性p1p2t1t2p4p6p5t3t4p3p0t0t5p1p2t1t2p4t3t4p3PetriPetri網(wǎng)的有界性（網(wǎng)的有界性（boundednessboundedness）反映）反映被模擬系統(tǒng)運(yùn)行過程中對有關(guān)資源的容量要求被模擬系統(tǒng)運(yùn)行過

8、程中對有關(guān)資源的容量要求庫所庫所p p3 3無界無界其它庫所的界為其它庫所的界為1 1B(p1) =B(p2) =B(p3)=2 其它庫所界為其它庫所界為1 1有界性和安全性n定理定理2.2. 設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)網(wǎng)。R(M0)為有限集當(dāng)且僅當(dāng)為有限集當(dāng)且僅當(dāng)PN是有界的。是有界的。 證：證：活性nPetri網(wǎng)活性（網(wǎng)活性（Liveness）概念的提出源于對實(shí)際系統(tǒng)運(yùn)行中是否會(huì)出現(xiàn)死鎖的探索）概念的提出源于對實(shí)際系統(tǒng)運(yùn)行中是否會(huì)出現(xiàn)死鎖的探索的需要。的需要。n定義定義2.6. 設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)，網(wǎng)， M0為初始標(biāo)識(shí)，為

9、初始標(biāo)識(shí)，t T。如果對任意。如果對任意M R(M0)，都存在，都存在M R(M)，使得，使得Mt，則稱變遷，則稱變遷t為活的。為活的。 如果每個(gè)如果每個(gè)t T 都是活的，則稱都是活的，則稱PN為活的為活的Petri網(wǎng)。網(wǎng)。p1p2t1t2t3p1p2t1t2p4t3t4p32t1 1和和t t2 2是活的，是活的， t3是不活的是不活的不活的不活的活的活的活性n與實(shí)際系統(tǒng)中的無死鎖概念更為接近的定義。與實(shí)際系統(tǒng)中的無死鎖概念更為接近的定義。n定義定義2.7. 設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)，網(wǎng)， 如果對如果對M R(M0)， 使得使得 t T： Mt，則稱，則稱M為

10、為PN的一個(gè)死標(biāo)識(shí)的一個(gè)死標(biāo)識(shí)（dead marking）。如果）。如果PN中不存在死標(biāo)識(shí)，則稱中不存在死標(biāo)識(shí)，則稱PN為弱為弱活的（活的（weak live）或者不死的（）或者不死的（non-dead）。）。n定理定理2.3.設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)。若網(wǎng)。若PN中有一個(gè)中有一個(gè)變遷是活的，則變遷是活的，則PN是弱活的。是弱活的。 證：證：用反證法。假設(shè)用反證法。假設(shè)PN不是弱活的，則必存在一個(gè)死標(biāo)識(shí)不是弱活的，則必存在一個(gè)死標(biāo)識(shí)M R(M0)， 即即 t T： Mt。從而不存在。從而不存在M R(M)，使得，使得Mt。即任一個(gè)變遷都不是活的，這同假設(shè)矛盾。即

11、任一個(gè)變遷都不是活的，這同假設(shè)矛盾。活性p1p5t1t2p4t5t4p3t3p2t6PN是弱活的是弱活的，但不是活的，但不是活的(1, 0, 0, 0, 0)(0, 0, 0, 1, 0)(0, 0, 1, 0, 0)(0, 0, 0, 0, 1)(0, 1, 0, 0, 0)t4t5t3t2t1t6活性n定義定義2.8.設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)，網(wǎng)， t T。若若 M R(M0)： Mt，則稱變遷，則稱變遷t為死的。為死的。如果一個(gè)如果一個(gè)PetriPetri網(wǎng)中沒有死變遷，網(wǎng)中沒有死變遷，那么它是活的嗎？是弱活的嗎？那么它是活的嗎？是弱活的嗎？p1p2t1t

12、2t3t3是死變遷是死變遷公平性n在在Petri網(wǎng)中引入公平性（網(wǎng)中引入公平性（fairness）概念，旨在討論網(wǎng)系統(tǒng)中兩個(gè)變遷的）概念，旨在討論網(wǎng)系統(tǒng)中兩個(gè)變遷的發(fā)生之間的相互關(guān)系。這種關(guān)系反映被模擬系統(tǒng)的各個(gè)部分在資源競爭中的發(fā)生之間的相互關(guān)系。這種關(guān)系反映被模擬系統(tǒng)的各個(gè)部分在資源競爭中的無饑餓性問題。無饑餓性問題。n定義定義2.9. 設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)，網(wǎng)， M0為初始標(biāo)識(shí)，為初始標(biāo)識(shí)，t1,t2 T。如果存在正整數(shù)如果存在正整數(shù)k，使得，使得 M R(M0) ， T*：M都有都有 #(, ti) =0#(, t3-i)k, i=1,2 則稱變遷則

13、稱變遷t1和和t2處于公平關(guān)系。處于公平關(guān)系。 如果如果PN中任意兩個(gè)變遷都處于公平關(guān)中任意兩個(gè)變遷都處于公平關(guān)系，則稱系，則稱PN為公平為公平Petri網(wǎng)。其中網(wǎng)。其中 #(, ti)表示在序列表示在序列中中ti的出現(xiàn)次數(shù)。的出現(xiàn)次數(shù)。n如果如果PN中不存在可發(fā)生的無限變遷序列，則網(wǎng)系統(tǒng)總是公平的。中不存在可發(fā)生的無限變遷序列，則網(wǎng)系統(tǒng)總是公平的。公平性n定義定義2.10. 設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)，網(wǎng)， M0為初始標(biāo)識(shí)，為初始標(biāo)識(shí)，t1,t2 T。如果。如果 M R(M0)，都，都存在正整數(shù)存在正整數(shù)k，使得，使得 T*：M都有都有 #(, ti) =0#(

14、, t3-i)k, i=1,2 則稱變遷則稱變遷t1和和t2處于弱公平關(guān)系。處于弱公平關(guān)系。 如果如果PN中任意兩個(gè)變遷都處于弱公平關(guān)系，則中任意兩個(gè)變遷都處于弱公平關(guān)系，則稱稱PN為弱公平為弱公平Petri網(wǎng)。網(wǎng)。p1t1t2p4t4p3p2t3t2和和 t3是公平關(guān)是公平關(guān)系，也是弱公平系，也是弱公平關(guān)系關(guān)系t2和和 t3是弱公平是弱公平關(guān)系，但不是公關(guān)系，但不是公平關(guān)系平關(guān)系公平性n定理定理2.4. Petri網(wǎng)中變遷之間的公平關(guān)系是一種等價(jià)關(guān)系網(wǎng)中變遷之間的公平關(guān)系是一種等價(jià)關(guān)系 證：公平關(guān)系的自反性和對稱性是顯然的。下面證明其傳遞性。證：公平關(guān)系的自反性和對稱性是顯然的。下面證明其傳

15、遞性。 設(shè)設(shè)t1和和t2處于公平關(guān)系，即存在處于公平關(guān)系，即存在k1，使得，使得 M R(M0) ， T*：M都有都有 #(, t1) =0#(, t2) k1 #(, t2) =0#(, t1) k1 把把寫成寫成 = 0 t2 1 t2 2 t2 3 j-1 t2 j, j k1. 顯然顯然#(i , t2) =0 設(shè)設(shè)t2和和t3處于公平關(guān)系，即存在處于公平關(guān)系，即存在k2，使得，使得 M R(M0) ， T*：M都有都有 #(, t2) =0#(, t3) k2 #(, t3) =0#(, t2) k2 則由則由t2和和t3的公平關(guān)系可知的公平關(guān)系可知#(i, t3) k2 ， #(,

16、 t3) k2(j+1) k2 (k1+1) k. 其中其中k=maxk2 (k1+1) , k1 (k2+1) 即即#(, t1) =0#(, t3) k 同理可證同理可證#(, t3) =0#(, t1) k 所以，所以，t1和和t3處于公平關(guān)系。處于公平關(guān)系。持續(xù)性n定義定義2.11.設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)為一個(gè)Petri網(wǎng)。如果對網(wǎng)。如果對任意任意 M R(M0) 和任意和任意t1,t2 T (t1 t2)，有，有 ( Mt1 Mt2M) Mt1 則稱則稱PN為持續(xù)網(wǎng)系統(tǒng)。為持續(xù)網(wǎng)系統(tǒng)。n定理定理2.5.設(shè)設(shè)PN=(P,T;F, M0)為一個(gè)持續(xù)網(wǎng)系統(tǒng)。對于為一個(gè)持續(xù)網(wǎng)

17、系統(tǒng)。對于任意任意 M R(M0)，如果，如果 Mt1 且且M， #(, t1) =0，則，則有有Mt1 且且Mt1。證明：對證明：對的長度進(jìn)行數(shù)學(xué)歸納。的長度進(jìn)行數(shù)學(xué)歸納。持續(xù)性n定理定理2.6. 設(shè)設(shè)N=(P,T;F)為一個(gè)純網(wǎng)，那為一個(gè)純網(wǎng)，那么么PN =(N, M0)是持續(xù)網(wǎng)系統(tǒng)的充要條件是持續(xù)網(wǎng)系統(tǒng)的充要條件 M R(M0) ， t1,t2 T (t1 t2)， t1和和t2 在在M不存在沖突。不存在沖突。持續(xù)性n定理定理2.7. 若若N=(P,T;F)為一個(gè)為一個(gè)T-圖，則對圖，則對N的的任意初始標(biāo)識(shí)任意初始標(biāo)識(shí)M0，PN =(N, M0)都是持續(xù)網(wǎng)系都是持續(xù)網(wǎng)系統(tǒng)。統(tǒng)。證明：已知證明：已知 M R(M0) 和任意和任意t1,t2 T (t1 t2)，有，有( Mt1 Mt2M)。并且并且 t1t2 = , t1t2 = 證明證明Mt1 。公平性實(shí)例n變遷序列：變遷序列：n (t1t2t3t4)* k=1n 弱公平弱公平非公平，因?yàn)槿暨x