A short introduction to Petri Nets

Covers the basics of Petri Nets

Transcript

1. A short introduction to Petri Nets Mourjo Sen sen.mourjo@etu.unice.fr
2. What a Petri Net is ▶ A directed bi-partite graph ▶ With two types of nodes: ▶ Places ▶ Transitions ▶ Arcs from places to transitions and vice versa ▶ Tokens placed inside places, or a marking ▶ Optional weights in arcs Cl 2 + H 2 → 2 HCl 2
3. What a Petri Net is 3 ▶ Mathematically, a petri net is a 5-tuple ▶ PN = (P, T, F, W, M 0 ) ▶ P = Finite set of places ▶ T = Finite set of transitions ▶ F = Finite set of arcs ▶ W: F → {1, 2, 3, …} is a weight function ▶ M 0 : P → {0, 1, 2, …} is the initial marking ▶ A petri net structure N =(P, T, F, W) is without any initial marking
4. Interpretations of Petri nets n Pre-conditions Event m Post-conditions 4
5. Interpretations of Petri nets n Input data Computation m Output data 5
6. Interpretations of Petri nets n Conditions Logic clause m Conclusions 6
7. Interpretations of Petri nets n Buffers Processor m Buffers 7
8. Interpretations of Petri nets n Resources needed Task/job n Resources released 8
9. Modeling Examples 9
10. Conflict (also called choice, decision) 10
11. Synchronization 11 e1
12. Parallel/Concurrent activities 12
13. Mutual Exclusion 13
14. Mutual Exclusion 14
15. Mutual Exclusion 15
16. Bounded buffers 16
17. Finite state machines 17 Finite State Machine Petri Net equivalent
18. Behavioral properties 18
19. Reachability set 19 ▶ Let M be a marking of a Petri net N = (P,T,F,W,M 0 ) ▶ The set of markings reachable from M is called the reachability set of M, written as reach(M) ▶ Reach(M) is the set of markings, such that: ▶ M ∈ reach(M), and ▶ If M’ → M’’ for some transition t ∈ T and M’ ∈ reach(M), then M’’ ∈ reach(M) ▶ The set of reachable markings of a petri net as a whole is defined to be reach(M 0 ) ▶ The “reachability problem” is to decide whether M ∈ reach(N), given a Petri net N and a marking M
20. Reachability graph 20
21. Boundedness 21 ▶ A place is called k-bounded or bounded if it does not contain more than k tokens in all reachable markings, including the initial marking ▶ It is said to be safe if it is one-bounded ▶ A (marked) Petri net is called (k-)bounded and/or safe if all of its places are (k-)bounded and/or safe.
22. Boundedness 22 If in the net N, both places are assigned capacity 2, we obtain a Petri net with place capacities, say N2 An unbounded petri net N A 2-bounded version N2
23. Liveness 23 A transition t in a Petri net N is said to be: ▶ L0-live or dead, if t can never be fired in any firing sequence ▶ L1-live or potentially fireable, if t can be fired at least once in some firing sequence of the Petri net ▶ L2-live, if for a given positive integer k, t can be fired at least k times in some firing sequence of the Petri net ▶ L3-live, if t can be fired infinite number of times in some firing sequence which can be obtained from M 0 of N ▶ L4-live, or live, if t is L1-live for every marking in reach(N)
24. Liveness 24 ▶ A Petri net is called Lk-live if every transition in the petri net is k-live, for k = 0, 1, 2, 3, 4 ▶ L4-liveness is the strongest ▶ L4-liveness ⇒ L3-liveness ⇒ L2-liveness ⇒ L1-liveness
25. Reversibility 25 A Petri net (N, M 0 ) is reversible if, in any marking M k reachable from initial marking M 0 , M 0 is reachable from Mk, that is, it is always possible to go back to the initial marking.
26. Persistence 26 ▶ A Petri net (N, M 0 ) is persistent if, for any two enabled transitions, the firing of one will not disable the other. ▶ An enabled transition, in such a petri net, stays enabled till it fires.
27. Synchronic Distance 27 ▶
28. Synchronic Distance 28
29. Conclusion: An example of a system computing (a+b)/(c+d) 29
30. A short introduction to Petri Nets Mourjo Sen sen.mourjo@etu.unice.fr Thank You!