第11讲petri之基本网系统

1、DONG HUA UNIVERSITY Copyright DHU 2010工作流基本技术管理学院 Copyright DHU 20102Main ContentslPetri NetlNetlElementary Net System 管理学院 Copyright DHU 20103History of Petri net Carl Adam Petri (1962, PhD thesis) In sixties and seventies focus mainly on theory Since eighties also focus on tools and applications (

2、cf. CPN work by Kurt Jensen)管理学院 Copyright DHU 20104Why Petri Net? The chief attraction of the area of Petri Net is the way in which the basic aspects of distributed systems are identified both conceptually and mathematically- G. ROZENBURGLeiden University, The Netherlands管理学院 Copyright DHU 20105Mai

3、n ContentslPetri NetlNetlElementary Net System 管理学院 Copyright DHU 20106管理学院 Copyright DHU 20107管理学院 Copyright DHU 20108Definition of NetA Net is a triple N=(S, T, F)lS T and S T= lF (S T) (T S)ldom(F) ran(F) = S T ldom(F) = x|y:(x,y)F(1)ran(F) = x|y:(y,x)FlSN S BS-elements of NlTN T ET-elements of N

4、lXN elements of NlFN F Fflow relation of N管理学院 Copyright DHU 20109Notations in Petri NetlCalled conditions in Elementary Net SystemlCalled placesplaces in Place/Transition SystemlCalled events in Elementary Net SystemlCalled transitionstransitions inPlace/Transition System管理学院 Copyright DHU 201010A

5、Net Examplet8t1t2t4t7t3t6t5s0s1s2s4s3s9s5s8s6s7lN=(B,E,F)lB=s0,s9lE=t1,t8lF=(s1,t1),(s0,t1),(s0,t2),(s2,t2), (t5,s1),(t8,s0),(t7,s2)管理学院 Copyright DHU 201011Case and Step Case(情态）- Distributed (global) state- Set of conditions holding concurrently- Constellation(条件丛)- E.g. s0,s1,s9 Step(步)- Distribu

6、ted (global) transition- Set of events occurring concurrently- E.g. t1,t8t8t1t2t4t7t3t7t5s0s1s2s4s3s9s5s8s6s7管理学院 Copyright DHU 201012pre-Set & post-Setpre-Set(前集) /pre-conditionspost-Set (后集) /pre-conditionsN=(B,E,F), xXN, Y XNx=y XN: (y,x) F x= y XN: (x,y) F Y= x Y = x x Y x Yt8t1t2t4t7t3t6t5s

7、0s1s2s4s3s9s5s8s6s7管理学院 Copyright DHU 201013Pure Net & Simple NetPure net(纯网/单纯网)-对于网N(S,T;F), x X; x x = ，其中X=STSimple net(简单网）-对于网N(S,T;F), 若x,y X, x= y x =y 则x=y，其中X=ST 管理学院 Copyright DHU 201014Key QuestionsWhen can a step occur(concurrently) at a case?What is the resulting case when a step o

8、ccurs at a caseStructural transition relation relating potential cases to potential cases via potential steps管理学院 Copyright DHU 201015Question 1Q: When can an event e occur at a case C?A: e can occur at C all pre-conditions hold at C (e C) andno post-conditions hold at C (e C= ) 记作， CeNEnabled可实施的/有

9、发生权的/受权的管理学院 Copyright DHU 201016Question 1(c1)Note that if CeNthen e e = Hence we often consider only pure netst8t1t2t4t7t3t7t5s0s1s2s4s3s9s5s8s6s7管理学院 Copyright DHU 201017Question2Q: What is the result of an event e occurring at a case C?A: When e occurs at C the pre-conditions of e cease to hold

10、and the post-conditions of e begin to hold; the remaining part of the case remains unaffected.(Hence the resulting case C is(C e) e)记作，CeN C Firing实施/发生管理学院 Copyright DHU 201018Question2(c1)N=(B, E, F), C,CB, e ECeN C iff C-C= e & C-C= ee = e e is the extension of e管理学院 Copyright DHU 201019Quest

11、ion3N=(B,E,F), CB, u EQ: When can the events in u occur concurrently at C?(when can the step u occur at C)A: u can occur at C iff the events in u can individually occur at C without interfering with each other记作，CuN 管理学院 Copyright DHU 201020Question4N=(B,E,F), CB, u E, u is enabled to occur at CQ: W

12、hat is the result of u occurring at C?A: The result is the sum of the results of the events in u occurring individually at C(C=(C- u) u)记作，CuN C管理学院 Copyright DHU 201021Question4(c1)N=(B,E,F), CB, u Eu is independent, indN(u), iff(e1,e2) u if e1e2 then( e1 e1 ) ( e2 e2 ) =U is a step enabled at C, C

13、uN , iff indN(u), u C and uC= 管理学院 Copyright DHU 201022Question4(c2)Theorem(diamond property)N=(B,E,F), C,DB, uELet u1,u2 be a partition of u(u1,u2, u1 u2= ,u1 u2=u)If C u ND, then Q B such that C u1 NQ and Q u2 ND管理学院 Copyright DHU 201023Question5N=(B,E,F), CB, =e1 e2 enE+Q: When can occur at C?A:

14、can occur at C iff the events in can individually occur in the order determined by 记作，C N管理学院 Copyright DHU 201024Question5(c1)THEOREMN=(B,E,F), CB, e1, e2EIf Ce1,e2 N and C e2 N,thenCe1,e2 N管理学院 Copyright DHU 201025Question5(c2)THEOREM( sequentialization property) N=(B,E,F), C,DB, uE(1) If Cu N iff

15、 ordering e1,en u, Ce1,en N (2) If Cu N D iff ordering e1,en u, Ce1,en N D管理学院 Copyright DHU 201026Main ContentslPetri NetlNetlElementary Net System 管理学院 Copyright DHU 201027Definition of EN SystemAn Elementary Net System(EN system) is a 4-tuple N = N = (B, E, F, Cin) where (B,E,F) is a net called t

16、he underlying net of N N ,und(N N), Cin B is the initial case of N N, inc(N N)Notations of EN systemBN N E N N F N NC CN N = Cin the set of cases of NUN = u E:(C1,C2) C CN N C1uN C2 the set of steps of N管理学院 Copyright DHU 201028EN SystemEN system as an abstract model of a distributed system: N = N =

17、 (B, E, F, Cin)Graphical notation for an EN system consists of the marking of C in by tokensUnderlyingStaticStructureDynamicBehaviourt8t1t2t4t7t3t7t5s0s1s2s4s3s9s5s8s6s7管理学院 Copyright DHU 201029管理学院 Copyright DHU 201030Relation of 2 EventsLet N N be an EN system, let C C CN N , and let e1, e2 E N. N

18、.e1,e2 can be related to each other at C in (at least) three wayssequence,conflict,concurrency管理学院 Copyright DHU 201031Relation of 2 Events:SequenceLet N N be an EN system, let C C CN N , and let e1, e2 E N. N.e1 can occur at C but not e2. However, after e1 has occurred e2 can occur.e1,e2 are in seq

19、uence at C iffCe1, Ce2, and Ce2 , where Ce1Ct8t1t2t4t7t3t7t5s0s1s2s4s3s9s5s8s6s7管理学院 Copyright DHU 201032Relation of 2 Events:ChoiceLet N N be an EN system, let C C CN N , and let e1, e2 E N. N.e1 and e2 can occur individually at C, but they cannot occur together at C. e1, e2 is not a step at C.wheth