第二部分Petri網(wǎng)的動(dòng)態(tài)性質(zhì),提綱,網(wǎng)系統(tǒng)(以原型Petri網(wǎng)為模型)運(yùn)行過(guò)程中的一些性質(zhì)統(tǒng)稱(chēng)為動(dòng)態(tài)性質(zhì)(dynamicproperties)或行為性質(zhì)(behavioralproperties)這些性質(zhì)同Petri網(wǎng)所模擬的實(shí)際系統(tǒng)運(yùn)行過(guò)程中的某些方面的性質(zhì)有密切的聯(lián)系,提綱,可達(dá)性有界性和安全性活性公平性持續(xù)性,可達(dá)性,可達(dá)性是Petri網(wǎng)的最基本的動(dòng)態(tài)性質(zhì)，其余各種性質(zhì)都要通過(guò)可達(dá)性來(lái)定義定義2.1.設(shè)PN=(P,T;F,M)為一個(gè)Petri網(wǎng)。如果存在tT，使MtM，則稱(chēng)M為從M直接可達(dá)的如果存在變遷序列t1,t2,t3,tk和標(biāo)識(shí)序列M1,M2,M3,Mk使得Mt1M1t2M2,Mk-1tkMk(2.1)則稱(chēng)Mk為從M可達(dá)的從M可達(dá)的一切標(biāo)識(shí)的集合記為R(M)，約定MR(M)如果記變遷序列t1,t2,t3,tk為，則(2.1)式也可記為MMk,可達(dá)性,設(shè)初始標(biāo)識(shí)M0表示系統(tǒng)的初始狀態(tài)，R(M0)給出系統(tǒng)運(yùn)行過(guò)程中可能出現(xiàn)的全部狀態(tài)的集合。定義2.2.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng),M0為初始標(biāo)識(shí)。PN的可達(dá)標(biāo)識(shí)集R(M0)定義為滿(mǎn)足下面兩條件的最小集合：（1）M0R(M0)；（2）若MR(M0)，且存在tT，使得MtM，則MR(M0),可達(dá)性,定理2.1.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng)，M0為初始標(biāo)識(shí)。則：(1)對(duì)任意MR(M0)，都有R(M)R(M0)；(2)對(duì)任意M1,M2R(M0)，R(M1)=R(M2)當(dāng)且僅當(dāng)M1R(M2)且M2R(M1)。證：(1)由于MR(M0)，所以MR(M):MR(M0)，從而R(M)R(M0)。同理可證(2)。,可達(dá)性,定義2.3.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng)，MR(M0)。如果MR(M0)，都有MR(M)，則稱(chēng)M為PN的一個(gè)可返回標(biāo)識(shí)或一個(gè)家態(tài)（homestate）。定義2.4.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng)。如果M0是一個(gè)家態(tài)，則稱(chēng)PN為可逆網(wǎng)系統(tǒng)（reversiblenetsystem），或稱(chēng)可回復(fù)系統(tǒng)。,網(wǎng)系統(tǒng)家態(tài)的存在是一個(gè)良好性質(zhì)，在評(píng)測(cè)系統(tǒng)性能或在系統(tǒng)模擬過(guò)程中具有非常關(guān)鍵的作用。,可達(dá)性,推論2.1.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng)，M1,M2是PN的家態(tài)，則R(M1)=R(M2)。證明：因?yàn)镸1,M2是PN的家態(tài)，所以首先有M1R(M0)，M2R(M0)，進(jìn)而M1R(M2)，M2R(M1)。根據(jù)定理2.1(2)，則有R(M1)=R(M2)。,有界性和安全性,定義2.4.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng),pP。若存在正整數(shù)B,使得MR(M0):M(p)B,則稱(chēng)庫(kù)所p為有界的(bounded)。并稱(chēng)滿(mǎn)足此條件的最小正整數(shù)B為庫(kù)所p的界，記為B(p)。即B(p)=minB|MR(M0):M(p)B當(dāng)B(p)=1時(shí)，稱(chēng)庫(kù)所p為安全的（safe）。定義2.5.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng)。如果每個(gè)pP都是有界的，則稱(chēng)PN為有界Petri網(wǎng)。稱(chēng)B(PN)=maxB(p)|pP為PN的界。當(dāng)B(PN)=1時(shí)，稱(chēng)PN為安全的。,有界性和安全性,Petri網(wǎng)的有界性（boundedness）反映被模擬系統(tǒng)運(yùn)行過(guò)程中對(duì)有關(guān)資源的容量要求,庫(kù)所p3無(wú)界其它庫(kù)所的界為1,B(p1)=B(p2)=B(p3)=2其它庫(kù)所界為1,有界性和安全性,定理2.2.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng)。R(M0)為有限集當(dāng)且僅當(dāng)PN是有界的。證：,活性,Petri網(wǎng)活性（Liveness）概念的提出源于對(duì)實(shí)際系統(tǒng)運(yùn)行中是否會(huì)出現(xiàn)死鎖的探索的需要。定義2.6.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng)，M0為初始標(biāo)識(shí)，tT。如果對(duì)任意MR(M0)，都存在MR(M)，使得Mt，則稱(chēng)變遷t為活的。如果每個(gè)tT都是活的，則稱(chēng)PN為活的Petri網(wǎng)。,2,t1和t2是活的，t3是不活的,不活的,活的,活性,與實(shí)際系統(tǒng)中的無(wú)死鎖概念更為接近的定義。定義2.7.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng)，如果對(duì)MR(M0)，使得tT：Mt，則稱(chēng)M為PN的一個(gè)死標(biāo)識(shí)（deadmarking）。如果PN中不存在死標(biāo)識(shí)，則稱(chēng)PN為弱活的（weaklive）或者不死的（non-dead）。定理2.3.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng)。若PN中有一個(gè)變遷是活的，則PN是弱活的。證：用反證法。假設(shè)PN不是弱活的，則必存在一個(gè)死標(biāo)識(shí)MR(M0)，即tT：Mt。從而不存在MR(M)，使得Mt。即任一個(gè)變遷都不是活的，這同假設(shè)矛盾。,活性,PN是弱活的，但不是活的,活性,定義2.8.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng)，tT。若MR(M0)：Mt，則稱(chēng)變遷t為死的。,如果一個(gè)Petri網(wǎng)中沒(méi)有死變遷，那么它是活的嗎？是弱活的嗎？,？,t3是死變遷,公平性,在Petri網(wǎng)中引入公平性（fairness）概念，旨在討論網(wǎng)系統(tǒng)中兩個(gè)變遷的發(fā)生之間的相互關(guān)系。這種關(guān)系反映被模擬系統(tǒng)的各個(gè)部分在資源競(jìng)爭(zhēng)中的無(wú)饑餓性問(wèn)題。定義2.9.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng)，M0為初始標(biāo)識(shí)，t1,t2T。如果存在正整數(shù)k，使得MR(M0)，T*：M都有#(,ti)=0#(,t3-i)k,i=1,2則稱(chēng)變遷t1和t2處于公平關(guān)系。如果PN中任意兩個(gè)變遷都處于公平關(guān)系，則稱(chēng)PN為公平Petri網(wǎng)。其中#(,ti)表示在序列中ti的出現(xiàn)次數(shù)。如果PN中不存在可發(fā)生的無(wú)限變遷序列，則網(wǎng)系統(tǒng)總是公平的。,公平性,定義2.10.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng)，M0為初始標(biāo)識(shí)，t1,t2T。如果MR(M0)，都存在正整數(shù)k，使得T*：M都有#(,ti)=0#(,t3-i)k,i=1,2則稱(chēng)變遷t1和t2處于弱公平關(guān)系。如果PN中任意兩個(gè)變遷都處于弱公平關(guān)系，則稱(chēng)PN為弱公平Petri網(wǎng)。,t2和t3是公平關(guān)系，也是弱公平關(guān)系,t2和t3是弱公平關(guān)系，但不是公平關(guān)系,公平性,定理2.4.Petri網(wǎng)中變遷之間的公平關(guān)系是一種等價(jià)關(guān)系證：公平關(guān)系的自反性和對(duì)稱(chēng)性是顯然的。下面證明其傳遞性。設(shè)t1和t2處于公平關(guān)系，即存在k1，使得MR(M0)，T*：M都有#(,t1)=0#(,t2)k1#(,t2)=0#(,t1)k1把寫(xiě)成=0t21t22t23j-1t2j,jk1.顯然#(i,t2)=0設(shè)t2和t3處于公平關(guān)系，即存在k2，使得MR(M0)，T*：M都有#(,t2)=0#(,t3)k2#(,t3)=0#(,t2)k2則由t2和t3的公平關(guān)系可知#(i,t3)k2，#(,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)系。,持續(xù)性,定義2.11.設(shè)PN=(P,T;F,M0)為一個(gè)Petri網(wǎng)。如果對(duì)任意MR(M0)和任意t1,t2T(t1t2)，有(Mt1Mt2M)Mt1則稱(chēng)PN為持續(xù)網(wǎng)系統(tǒng)。定理2.5.設(shè)PN=(P,T;F,M0)為一個(gè)持續(xù)網(wǎng)系統(tǒng)。對(duì)于任意MR(M0)，如果Mt1且M，#(,t1)=0，則有Mt1且Mt1。證明：對(duì)的長(zhǎng)度進(jìn)行數(shù)學(xué)歸納。,持續(xù)性,定理2.6.設(shè)N=(P,T;F)為一個(gè)純網(wǎng)，那么PN=(N,M0)是持續(xù)網(wǎng)系統(tǒng)的充要條件MR(M0)，t1,t2T(t1t2)，t1和t2在M不存在沖突。,持續(xù)性,定理2.7.若N=(P,T;F)為一個(gè)T-圖，則對(duì)N的任意初始標(biāo)識(shí)M0，PN=(N,M0)都是持續(xù)網(wǎng)系統(tǒng)。證明：已知MR(M0)和任意t1,t2T(t1t2)，有(Mt1Mt2M)。并且t1t2=,t1t2=證明Mt1。,公平性實(shí)例,變遷序列：(t1t2t3t4)*k=1弱公平非公平，因?yàn)槿暨x定某個(gè)k,則只要讓p1中存儲(chǔ)k+1個(gè)