Understanding Petri Nets: A Versatile Tool for Modeling Systems
Petri nets are a powerful modeling tool characterized by their asynchronous state transitions, making them ideal for representing concurrent and distributed systems. Originating from Carl Adam Petri's work in the 1960s, Petri nets have found diverse applications in fields such as computer science and engineering. Their graphical and mathematical nature allows for efficient visualization and analysis of complex processes, enabling the modeling of systems with various levels of determinism and parallelism.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Petri Nets Lei Bu 1
Dining Philosphier 4 States 5 transitions
From automata to Petri Net automata are a theoretical and idealised model they reflect a Newtonian world-view: space & time as an absolute frame of reference clockwork view of processes within this frame Carl Adam Petri has made an attempt to combine automata from theoretical CS, and pragmatic expertise from engineers: Petri Net state is distributed, transitions are localised local causality replaces global time subsystems interact by explicit communication
Petri nets-Motivation In contrast to state machines, state transitions in Petri nets are asynchronous. The ordering of transitions is partly uncoordinated; it is specified by a partial order. Therefore, Petri nets can be used to model concurrent distributed systems. Many flavors of Petri nets are in use, e.g. Activity charts(UML) Data flow graphs and marked graphs 7
History 1962: C.A. Petri s dissertation (U. Darmstadt, W. Germany) 1970: Project MAC Conf. on Concurrent Systems and Parallel Computation (MIT, USA) 1975: Conf. on Petri Nets and related Methods (MIT, USA) 1979: Course on General Net Theory of Processes and Systems (Hamburg, W. Germany) 1980: First European Workshop on Applications and Theory of Petri Nets (Strasbourg, France) 1985: First International Workshop on Timed Petri Nets (Torino, Italy)
Introduction Petri Nets: Graphical and Mathematical modeling tools graphical tool visual communication aid mathematical tool state equations, algebraic equations, etc concurrent, asynchronous, distributed, parallel, nondeterministic and/or stochastic systems
Informal Definition The graphical presentation of a Petri net is a bipartite graph There are two kinds of nodes Places: usually model resources or partial state of the system Transitions: model state transition and synchronization Arcs are directed and always connect nodes of different types Tokens are resources in the places
Example p2 t2 t1 p1 p4 t3 p3
Definition of Petri Net C = ( P, T, I, O) Places P = { p1, p2, p3, , pn} Transitions T = { t1, t2, t3, , tn} Input I : T Pr(r = number of places) t Output O : T Pq(q = number of places) t 12
marking : assignment of tokens to the places of Petri net = 1, 2, 3, n p2 t2 t1 p1 p4 t3 p3 13
Applications performance evaluation communication protocols distributed-software systems distributed-database systems concurrent and parallel programs industrial control systems discrete-events systems multiprocessor memory systems dataflow-computing systems fault-tolerant systems etc, etc, etc
Basics of Petri Nets Petri net consist two types of nodes: places and transitions. And arc exists only from a place to a transition or from a transition to a place. A place may have zero or more tokens. Graphically, places, transitions, arcs, and tokens are represented respectively by: circles, bars, arrows, and dots. Below is an example Petri net with two places and one transaction. p1 t1 p2 15
State The state of the system is modeled by marking the places with tokens A place can be marked with a finite number (possibly zero) of tokens
Fire A transition t is called enabled in a certain marking, if: For every arc from a place p to t, there exists a distinct token in the marking An enabled transition can fire and result in a new marking Firing of a transition t in a marking is an atomic operation state transition of form (1, 0) (0, 1) p1 : input place p2: output place p1 t1 p2
Fire (cont.) Firing a transition results in two things: Subtracting one token from the marking of any place p for every arc connecting p to t Adding one token to the marking of any place p for every arc connecting t to p 1. 2.
Firing example 2H2 + O2 2H2O 2 t H2 2 H2O O2
Firing example 2H2 + O2 2H2O 2 t H2 2 H2O O2
Run-1 Safe PN A run of a Petri net is a finite or infinite sequence of markings and transitions ?0?1 the initial marking of the net, ???????(??) for any i (? 0) , and that ??= (?? 1 ?? 1) ?? 1 for any i (? 1) ?1 ?? 1?? ?? such that ?0 is ?0 ?? 21
Properties of Petri Nets Sequential Execution Transition t2 can fire only after the firing of t1. This impose the precedence of constraints "t2 after t1." Synchronization Transition t1 will be enabled only when there are at least one token at each of its input places. Merging Happens when tokens from several places arrive for service at the same transition. p1 t1 p2 t2 p3 t1 22
Properties of Petri Nets - continued Concurrency t1 and t2 are concurrent. - with this property, Petri net is able to model systems of distributed control with multiple processes executing concurrently in time. t1 t2 24
Non-Deterministic Evolution The evolution of Petri nets is not deterministic Any of the activated transactions might fire 25
Properties of Petri Nets -continued Conflict t1 and t2 are both ready to fire but the firing of any leads to the disabling of the other transitions. t1 t2 t1 t2 26
Properties of Petri Nets -continued Conflict - continued the resulting conflict may be resolved in a purely non-deterministic way or in a probabilistic way, by assigning appropriate probabilities to the conflicting transitions. there is a choice of either t1 and t2, or t3 and t4 t1 t2 27 t3 t4
Some definitions source transition: no inputs sink transition: no outputs self-loop: a pair (p,t) s.t. p is both an input and an output of t pure PN: no self-loops Weighted PN: arcs with weight ordinary PN: all arc weights are 1 s infinite capacity net: places can accommodate an unlimited number of tokens finite capacity net: each place p has a maximum capacity K(p) strict transition rule: after firing, each output place can t have more than K(p) tokens Theorem: every pure finite-capacity net can be transformed into an equivalent infinite-capacity net
Weighted Edges Associating weights to edges: Each edge fi has an associated weight W(fi) (defaults to 1) A transition t is active if each place pi connected through an edge fi to t contains at least W(f) tokens. 29
Finite Capacity Petri Net Each place pi can hold maximally K(pi) tokens A transition t is only active if all output places pi of t cannot exceed K(pi) after firing t. Pure finite capacity Petri Nets can be transformed into equivalent infinite capacity Petri Nets (without capacity restrictions). Equivalence: Both nets have the same set of all possible firing sequences 30
Removing Capacity Constraints For each place p with K(p) > 1, add a complementary place p with initial marking M0(p ) = K(p) M0(p). For each outgoing edge e = (p, t), add an edge e from t to p with weight W(e). For each incoming edge e = (t, p), add an edge e from p to t with weight W(e). 31
Resolving Self-Loops The algorithm to remove capacity constraints works if the Petri net has no self loops (is pure). No Problem! Rewrite the Petri net without self loops: 32
Example: Synchronization at single track rail segment Preconditions
Modeling communication protocols ready to send ready to receive buffer full send msg. receive msg. wait for ack. proc.2 proc.1 msg. received receive ack. send ack. buffer full ack. received ack. sent
Example: In a Restaurant Waiter free Customer 1 Customer 2 Take order Take order wait Order taken wait eating eating Tell kitchen Serve food Serve food 37
Example: In a Restaurant (Two Scenarios) Scenario 1: Waiter takes order from customer 1; serves customer 1; takes order from customer 2; serves customer 2. Scenario 2: Waiter takes order from customer 1; takes order from customer 2; serves customer 2; serves customer 1. 38
Example: In a Restaurant (Scenario 1) Waiter free Customer 1 Customer 2 Take order Take order wait Order taken wait eating eating Tell kitchen Serve food Serve food 39
Example: In a Restaurant (Scenario 2) Waiter free Customer 1 Customer 2 Take order Take order wait Order taken wait eating eating Tell kitchen Serve food Serve food 40
Example: Vending Machine Take 15c bar Deposit 10c 15c 5c Deposit 5c Deposit 5c Deposit 5c Deposit 5c 0c Deposit 10c 20c 10c Deposit 10c Take 20c bar 41
Example: Vending Machine (3 Scenarios) Scenario 1: Deposit 5c, deposit 5c, deposit 5c, deposit 5c, take 20c snack bar. Scenario 2: Deposit 10c, deposit 5c, take 15c snack bar. Scenario 3: Deposit 5c, deposit 10c, deposit 5c, take 20c snack bar. 42
Example: Vending Machine Take 15c bar Deposit 10c 15c 5c Deposit 5c Deposit 5c Deposit 5c Deposit 5c 0c Deposit 10c 20c 10c Deposit 10c Take 20c bar 43
Example: Four Philosophers First: Building a model for one philosopher 45
Behavioral properties (1) Properties that depend on the initial marking Reachability Mn is reachable from M0 if exists a sequence of firings that transform M0 into Mn reachability is decidable, but exponential Boundedness a PN is bounded if the number of tokens in each place doesn t exceed a finite number k for any marking reachable from M0 a PN is safe if it is 1-bounded
Behavioral properties (2) Liveness a PN is live if, no matter what marking has been reached, it is possible to fire any transition with an appropriate firing sequence equivalent to deadlock-free Reversibility a PN is reversible if, for each marking M reachable from M0, M0 is reachable from M relaxed condition: a marking M is a home state if, for each marking M reachable from M0, M is reachable from M
