Lecture 8: Petri-NetsKenneth M. AndersonFoundations of Software EngineeringCSCI 5828 - Spring Semester, 2000February 10, 2000 © Kenneth M. Anderson, 2000 2Today’s Lecture• Introduce the Petri Net Formalism– Present several examplesFebruary 10, 2000 © Kenneth M. Anderson, 2000 3Petri NetsN = {P,T,A,M0 }, where P is a finite set of places T is a finite set of transitions A is a finite set of arcs (arrows) M0 is the initial marking of N• Formal DefinitionFebruary 10, 2000 © Kenneth M. Anderson, 2000 4Graphical RepresentationIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 5Graphical RepresentationplaceIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 6Graphical RepresentationplacetransitionIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 7Graphical RepresentationarcplacetransitionIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 8Graphical RepresentationarctokenplacetransitionIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 9Graphical RepresentationarctokenplacetransitionIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 10Petri Nets• Intuitive Meaning– A place holds tokens– A transition represents activity– An arc connects a place and a transition– A marking is an arrangement of tokens inplaces, representing state– An initial marking represents an initial stateFebruary 10, 2000 © Kenneth M. Anderson, 2000 11Execution Model• Input and Output Places– Place P is an input place for transition T if thereis an arc from P to T– Place P is an output place for transition T ifthere is an arc from T to P• Enabled Transition– A transition is enabled if there is at least onetoken at each of its input placesFebruary 10, 2000 © Kenneth M. Anderson, 2000 12Petri Net SemaphoreIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 13Enabled TransitionsIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 14Execution Model• Firing a Transition– An enabled transition is nondeterministicallyselected and fired by removing one token fromeach of its input places and depositing onetoken at each of its output places• Firing Sequence–A firing sequence is a sequence <t0,t1,…,tn>such that t0 is enabled and fired in M0, t1 isenabled and fired in M1, etc.February 10, 2000 © Kenneth M. Anderson, 2000 15Enabled TransitionsIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 16After FiringIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 17Enabled TransitionIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 18After FiringIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 19Enabled TransitionIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 20Breaking the Semaphore• Lets look at the semaphore example againand see how a change to the initial markingwill change the semantics of the Petri Net– In particular, we will break the semantics of thesemaphore by adding one tokenFebruary 10, 2000 © Kenneth M. Anderson, 2000 21Petri Net SemaphoreIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 22Enabled TransitionsIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 23After FiringIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 24Enabled TransitionsIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 25After FiringIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 26Enable TransitionsIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 27After FiringIn1In2Out1Out2CR1CR2SemFebruary 10, 2000 © Kenneth M. Anderson, 2000 28Filling Station Example• Lets model the following situation– Fuel Pumps– Spaces next to Pumps– A cashier that takes payment• Questions– What is the concurrency that we want modeled?– How do we handle the parameterization of thePetri net? (e.g. lets say I want to add a
View Full Document
Unlocking...