Petri Nets ------------------------------------------------ slide number 1 Petri Nets ______________________________ Outline These slides will be covered during TWO lectures. Introduction Basic Definition Modeling Program Graphs Modeling Control Modeling Non-computer Systems Formalism Properties of Petri Nets Modeling Databases & Operating Systems Variations in Modeling Petri Nets ------------------------------------------------ slide number 2 Goals for Studying Petri Nets 1. Familiarity with an important modeling tool * areas Petri nets can model well * limitations of Petri nets * variety of representations * common properties 2. Capabilities with the tool * understand complex models * develop simple models 3. Further information: World of Petri Nets web page: http://www.informatik.uni-hamburg.de/TGI/PetriNets/ look for simulators under "Tools and Software" link Petri Nets ------------------------------------------------ slide number 3 Characteristics of the Model * complex processes * concurrent activities * flow of data or other things may be transformed on the way * multiple coordinated flows hence abstraction of Data Flow Diagrams focusing on synchronization Petri Nets ------------------------------------------------ slide number 4 Petri Nets & Finite State Automata Some visual similarity between FSA and Petri Nets diagrams both have circle and arrows FSA are special cases of Petri nets In general, Petri nets * emphasize locality of condition verses global state * have multiple conditions active at once hence non-determinacy more global * express complex transitions succinctly * allow multiple instances in one condition without bound Petri Nets ------------------------------------------------ slide number 5 Beyond DFDs + explicit coordination / synchronization - no identity of "packets" How do invoice and build order from the same purchase order get matched up? OMITTED figure Petri Nets ------------------------------------------------ slide number 6 Game Metaphor for Petri Nets Can imagine each Petri net as * a unique -g-a-m-e-b-o-a-r-d- but * using the same kind of -p-i-e-c-e-s-and * following the same general -r-u-l-e-s- Petri Nets ------------------------------------------------ slide number 7 The Gameboard Each Petri net looks like a gameboard with * circles called -c-o-n-d-i-t-i-o-n-s-or -p-l-a-c-e-s- * bars called -e-v-e-n-t-s-or -t-r-a-n-s-i-t-i-o-n-s- * arrows, called -i-n-p-u-t--a-r-c-s-, from conditions to events * condition is -i-n-p-u-t-to the event * arrows, called -o-u-t-p-u-t--a-r-c-s-, from events to conditions * condition is -o-u-t-p-u-t-from the event * multiple parallel edges possible Notation: OMITTED figure * formally, a "bipartite directed multigraph" Petri Nets ------------------------------------------------ slide number 8 The Pieces A -t-o-k-e-n-on a condition * means that condition currently is true * is drawn by a black dot on that condition * may share that condition with other tokens, indicating multiple objects sharing that condition * during a given turn, may stay on a condition or move to an event A -m-a-r-k-i-n-g-of a Petri net * is a function from the conditions to the non-negative integers * indicates the number of tokens currently at that condition Petri Nets ------------------------------------------------ slide number 9 The Rules of Play An event is -e-n-a-b-l-e-d-when it is possible to place on each input arc a token from the corresponding input condition An event -f-i-r-e-s- * only if it is enabled * by consuming a token along each input arc * and producing a token along each output arc Indeterminate firing: * If more than one event is enabled at a given time, any of the enabled events may fire Concurrency: * Formally, two events may not fire at the same time * However, this is often not relevant, so it is common to think of event firings as being concurrent Petri Nets ----------------------------------------------- slide number 10 Example OMITTED figure Petri Nets ----------------------------------------------- slide number 11 Basic Control Constructs OMITTED figure Petri Nets ----------------------------------------------- slide number 12 Parallel Programming PARBEGIN S1, S2, ... Sk PAREND OMITTED figure Petri Nets ----------------------------------------------- slide number 13 Switches The simplest switch: OMITTED figure Use this to en/dis-able other transition(s) OMITTED figure What is wrong with the above? Petri Nets ----------------------------------------------- slide number 14 Mutual Exclusion Objective: prevent two programs from accessing the same data structure simultaneously Code where a program accesses the shared structure is called the -c-r-i-t-i-c-a-l- -s-e-c-t-i-o-n- OMITTED figure Petri Nets ----------------------------------------------- slide number 15 Producer/Consumer Model Issue is lock on buffer to prevent simultaneous access OMITTED figure Petri Nets ----------------------------------------------- slide number 16 Process Pipeline OMITTED figure Petri Nets ----------------------------------------------- slide number 17 Machine Shop Specification A machine shop has resources: * machines M0, M1, and M2 * operators O1 and O2 Subject to the constraints: * O1 can operate M0 and M1 * O2 can operate M0 and M2 * an order is processed first by M0 and then either M1 or M2 Significant events: * order arrives * Oi [ begins | ends ] operating Mj * product is shipped Significant conditions: * order waiting for Mj * Oi or Mj is idle (5 cases) * Oi is operating Mj (4 cases) * order partially done * product awaiting shipment Petri Nets ----------------------------------------------- slide number 18 Petri Net Model of Machine Shop OMITTED figure Petri Nets ----------------------------------------------- slide number 19 Petri Net Can Model Any Flow * PERT networks * example: building a house * Many complex processes in society * example: civil legal action Petri Nets ----------------------------------------------- slide number 20 Formal Definitions A -P-e-t-r-i--n-e-t--g-r-a-p-h-consists of P a finite set of conditions (Places) T a finite set of events (Transitions) I a finite multiset of arcs from P to T (Inputs) O a finite multiset of arcs from T to P (Outputs) A -m-a-r-k-e-d--P-e-t-r-i--n-e-t-consists of G a Petri net graph  m a function, m : P -> Z Z = non-negative integers Petri Nets ----------------------------------------------- slide number 21 Firings Formally define: * event enabled * firing * firing sequence Petri Nets ----------------------------------------------- slide number 22 Vector Addition Systems An (almost) equivalent formalism: * an n place Petri net written as a vector of conditions < p1, p2, . . ., pn > * a marking of that net is written as a vector of non-negative integers < m1, m2, . . ., mn > * an event is written as a vector of integers < d1, d2, . . ., dn > * di < 0 for input arcs from condition pi * di > 0 for output arcs to condition pi * one event cannot have same condition as both input and output | | conditions ---+--------------------- e | v | e | n | t | s | Petri Nets ----------------------------------------------- slide number 23 Example VAS A Petri net in VAS notation p1 p2 p3 p4 t1 < 1 , 0 , 0 , 0 > t2 < -1 , -1 , 2 , 2 > t3 < 0 , 0 , -2 , -1 > t4 < 0 , 1 , 0 , -1 > The same Petri net in graphical notation OMITTED figure Petri Nets ----------------------------------------------- slide number 24 Analysis of Behavior Given * a Petri net with * an initial marking determine * behavior patterns * over all possible firing sequences Petri Nets ----------------------------------------------- slide number 25 Conflict Two events are said to be -i-n--c-o-n-f-l-i-c-t-if there is a marking in which both events are enabled, but the firing of one event disables the other A conflict: OMITTED figure Petri Nets ----------------------------------------------- slide number 26 Boundedness A condition t is -b-o-u-n-d-e-d-by b if there is no firing sequence that marks t with a value greater than b A condition bounded by 1 is called -s-a-f-e-. Petri Nets ----------------------------------------------- slide number 27 Liveness An event t is dead if it is never enabled live-1 if there is some firing sequence after which t is enabled live-2 if, for every integer n, there is a firing sequence in which t fires n times live-3 if there is an infinite firing sequence in which t fires n times, for any integer n live-4 if every finite firing sequence can be extended to one that enables t Petri Nets ----------------------------------------------- slide number 28 Liveness Examples * dead OMITTED figure * live-1 but not live-2 OMITTED figure * live-2 but not live-3, for t3 OMITTED figure * live-3 but not live-4, for t1 in same net * live-4, non-trivially OMITTED figure * live-4, but trivial OMITTED figure [ slides 28 thru 29 combined in above ] Petri Nets ----------------------------------------------- slide number 30 Reachability & Coverability Reachability question: Given * a Petri net with an initial marking and * a target marking M does there exist * a firing sequence that produces M ? A marking < m1, m2, . . ., mn > -c-o-v-e-r-s-a marking < k1, k2, . . ., kn > if ki <= mi for all i, 1 <= i <= n Coverability question: Given * a Petri net with an initial marking and * a target marking M does there exist * a firing sequence that produces a marking covering M ? Coverability tree formed by 1. initial marking is root 2. successive markings form branches -e-x-c-e-p-t- 3. if identical marking on path to root, stop branch 4. if covers a marking on path to root, mark increased conditions with o Petri Nets ----------------------------------------------- slide number 31 Coverability Tree Example OMITTED figure Petri Nets ----------------------------------------------- slide number 32 Two-Phase Commit OMITTED figure Petri Nets ----------------------------------------------- slide number 33 OS Model Correspondences A condition typically is * a -q-u-e-u-e-of processes * where many tokens may be in one condition * an active process * where one token may occupy a condition Tokens model * processes * controls (semaphores, etc.) Petri Nets ----------------------------------------------- slide number 34 Deadlocked Programs loop loop acquire R1; acquire R2; acquire R2; acquire R1; critical critical section; section; release R1 release R1 and R2; and R2; end end Petri Nets ----------------------------------------------- slide number 35 Petri Model with Possible Deadlock OMITTED figure Petri Nets ----------------------------------------------- slide number 36 Petri Model without Deadlock OMITTED figure Petri Nets ----------------------------------------------- slide number 37 Colored Petri Nets * allow tokens of various colors * events specify colors of tokens input and output Example: OMITTED figure * t1 takes a Yellow token and outputs a Green one * t2 consumes a Green token as long as a Red is present, outputing a Red token * t3 takes either a Green or Red token as input Petri Nets ----------------------------------------------- slide number 38 Coloring Doesn't Matter OMITTED figure Petri Nets ----------------------------------------------- slide number 39 Numeric Petri Nets OMITTED figure Copyright 2109-3-26, Edward L. Robertson