第10讲petri之基本网系统.ppt

Header text,Level One Text,Level Two Text,Level Three Text,Level Four Text,Level Five Text,*,管理学院,Copyright DHU 2010,*,第10讲petri之基本网系统,Main Contents,Petri Net,Net,Elementary Net System,2,History 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(cf.CPN work by Kurt Jensen),3,Why 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.ROZENBURG,Leiden University,The Netherlands,4,Main Contents,Petri Net,Net,Elementary Net System,5,6,7,Definition of Net,A Net is a triple N=(S,T,F),S,T,and S T=,F (S T)(T S),dom,(F,),cod,(F,)=,S,T,dom,(F,)=,x|,y:(x,y),F,cod,(F,)=,x|,y:(y,x),F,S,N,S,B,S-elements of N,T,N,T,E,T-elements of N,X,N,elements of N,F,N,F,F,flow relation of N,8,Notations in Petri Net,Called,conditions,in,Elementary Net System,Called,places,in,Place/Transition System,Called,events,in,Elementary Net System,Called,transitions,in,Place/Transition System,9,A Net Example,t8,t1,t2,t4,t7,t3,t6,t5,s0,s1,s2,s4,s3,s9,s5,s8,s6,s7,N=(B,E,F),B=s0,s9,E=t1,t8,F=(s1,t1),(s0,t1),(s0,t2),(s2,t2),(t5,s1),(t8,s0),(t7,s2),10,Case and Step,Case(情态）,Distributed(global)state,Set of conditions holding concurrently,Constellation,(条件丛),E.g.s0,s1,s9,Step(步),Distributed(global)transition,Set of events occurring concurrently,E.g.t1,t8,t8,t1,t2,t4,t7,t3,t7,t5,s0,s1,s2,s4,s3,s9,s5,s8,s6,s7,11,pre-Set&post-Set,pre-Set(前集)/pre-conditions,post-Set(后集)/pre-conditions,N=(B,E,F),x,X,N,Y X,N,x=y,X,N,:(y,x),F,x=y,X,N,:(x,y),F,Y=,xY=,x,x,Y,x,Y,t8,t1,t2,t4,t7,t3,t6,t5,s0,s1,s2,s4,s3,s9,s5,s8,s6,s7,12,Pure Net&Simple Net,Pure net(纯网/单纯网),对于网N(S,T;F),x X;x x=，其中X=ST,Simple net(简单网）,对于网N(S,T;F),若x,y X,x=y x=y 则x=y，其中X=ST,13,Key Questions,When can a step,occur(concurrently)at a case?,What is the resulting case when a step occurs at a case,Structural transition relation relating potential cases to potential cases via potential steps,14,Question 1,Q:When can an event,e,occur at a case,C,?,A:,e,can occur at,C,all pre-conditions hold at,C,(,e,C,)and,no post-conditions hold at,C,(,e,C,=,),记作，,C,e,N,Enabled,可实施的/有发生权的/受权的,15,Question 1(c1),Note that if,C,e,N,then,e,e,=,Hence we often consider only pure nets,t8,t1,t2,t4,t7,t3,t7,t5,s0,s1,s2,s4,s3,s9,s5,s8,s6,s7,16,Question2,Q: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 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,),记作，,C,e,N,C,Firing,实施/发生,17,Question2(c1),N=(B,E,F),C,CB,e E,C,e,N,C,iff,C-C=,e,&C-C=,e,e=e e is the extension of e,18,Question3,N=(B,E,F),CB,u,E,Q: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,记作，,C,u,N,19,Question4,N=(B,E,F),CB,u,E,u,is enabled to occur at C,Q:What 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,),记作，,C,u,N,C,20,Question4(c1),N=(B,E,F),CB,u,E,u,is,independent,ind,N,(,u,),iff,(e1,e2),u,if,e1e2 then,(e1 e1 )(e2 e2 )=,U is a step,enabled,at C,C,u,N,iff,ind,N,(,u,),u,C and,u,C,=,21,Question4(c2),Theorem(diamond property),N=(B,E,F),C,DB,u,E,Let u1,u2 be a partition of,u,(u1,u2,u1 u2=,u1 u2=,u,),If C,u,N,D,then Q B such that,C u1,N,Q and Q u2,N,D,22,Question5,N=(B,E,F),CB,=e1 e2 en,E,+,Q:When can,occur at,C,?,A:,can occur at C iff,the events in,can individually occur in the order determined by,记作，,C,N,23,Question5(c1),THEOREM,N=(B,E,F),CB,e1,e2,E,If C,e1,e2,N,and C,e2,N,then,C,e1,e2,N,24,Question5(c2),THEOREM(sequentialization property),N=(B,E,F),C,DB,u,E,(1)If C,u,N,iff ordering e1,en,u,Ce1,en,N,(2)If C,u,N,D iff ordering e1,en,u,Ce1,en,N,D,25,Main Contents,Petri Net,Net,Elementary Net System,26,Definition of EN System,An Elementary Net System(EN system)is a 4-tuple,N=,(B,E,F,C,in,)where(B,E,F)is a net called the underlying net of,N,und,(,N,),C,in,B is the initial case of,N,inc,(,N,),Notations of EN system,B,N,E,N,F,N,C,N,=C,in,the set of cases of,N,U,N,=u,E:(,C1,C2),C,N,C,1,u,N,C,2,the set of steps of N,27,EN System,EN system as an abstract model of a distributed system:,N=,(B,E,F,C,in,),Graphical notation for an EN system consists of the marking of C,in,by tokens,Underlying,Static,Structure,Dynamic,Behaviour,t8,t1,t2,t4,t7,t3,t7,t5,s0,s1,s2,s4,s3,s9,s5,s8,s6,s7,28,29,Relation of 2 Events,Let,N,be an EN system,let C,C,N,and let e1,e2,E,N.,e1,e2 can be related to each other at C in(at least)three ways,sequence,conflict,concurrency,30,Relation of 2 Events:Sequence,Let,N,be an EN system,let C,C,N,and let e1,e2,E,N.,e1 can occur at C but not e2.However,after e1 has occurred e2 can occur.,e1,e2 are in sequence at C iff,Ce1,Ce2,and Ce2,where Ce1C,t8,t1,t2,t4,t7,t3,t7,t5,s0,s1,s2,s4,s3,s9,s5,s8,s6,s7,31,Relation of 2 Events:Choice,Let,N,be an EN system,let C,C,N,and let e1,e2,E,N.,e1 and e2 can occur individually at C,but they cannot occur together at C.,e1,e2 is not a step at C.,whether e1 or e2 will occur at C is left unspecified,thus,N,exhibits non-determinism.,e1,e2 are in,conflict,at C iff,Ce1,Ce2,and,Ce1,e2,t8,t1,t2,t4,t7,t3,t7,t5,s0,s1,s2,s4,s3,s9,s5,s8,s6,s7,32,Relation of 2 Events:Concurrency,Let,N,be an EN system,let C,C,N,and let e1,e2,E,N.,e1 and e2 can occur at C without interfering with each other.Moreover no order is specified over their occurrences.,e1,e2 is a step at C.,N,exhibits non-sequential behaviour.,e1,e2 can occur concurrently at C iff,Ce1,e2,t8,t1,t2,t4,t7,t3,t7,t5,s0,s1,s2,s4,s3,s9,s5,s8,s6,s7,33,Dutch Traffic Lights,34,Modeling Your Lifecycle,35,