南京大学：复杂系统学习（PPT课件讲稿）佩特里网 Petri Nets

大房 NANJING UNIVERSITY Petri Nets Lei bu

Lei Bu Petri Nets 1

Dining Philosphier 4 States, 5 transitions put_ |F1 1 get F1 11F2 F2 1F1 1F1 1 1_get_ F2 1_ get_F1 IF2 1F1 1F2

Dining Philosphier ◼ 4 States， 5 transitions

9 States 14 transitions N put back 2_9tF 1. get F1 2g°tF2 1 get F2 F2 get Ft

◼ 9 States 14 Transitions

27 States, 56 transitions +2 3 2F2 2.F3

◼ 27 States， 56 Transitions

81 States, 252 Transitions 的到面

◼ 81 States， 252 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

• 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 From automata to 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 o Activity chartS(UML) o Data flow graphs and marked graphs

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. Petris dissertation (U. Darmstadt, W. Germany) 1970: Project MAC Conf on Concurrent Systems and Parall 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)

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 o graphical tool visual communication aid o mathematical tool state equations, al gebraic equations, etc concurrent, asynchronous, distributed, parallel nondeterministic and/or stochastic systems

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 h grap There are two kinds of nodes o Places: usually model resources or partial state of the stem o Transitions: model state transition and synchronization Arcs are directed and always connect nodes of different type es Tokens are resources in the places

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