This Lecture
•	Modelling concurrency
•	Petri Nets - some examples
•	Formal definitions
•	Special classes of Petri Nets 
•	More examples
Basic Issues of Concurrency
•	Model of concurrency 
>	e.g interleaving semantics
>	how is combinatorial explosion handled
•	Non-determinism
>	e.g., to model concurrency
•	Deadlock
>	e.g, does it arise?
•	Synchronization and communication
>	how are concurrent processes sychnronized
•	Resource sharing
>	are there shared resources?
•	Fairness
>	is it part of the model?
Concurrency and FSAs
•	Concurrency with Finite State Machines leads to state explosion.
Possible Solution
•	Allow there to be multiple "state tokens" in a diagram.
Petri Nets: An Example
Simple Elevator
Producer/Consumer
Producer/Consumer (2)
Producer/Consumer (3)
Mutual Exclusion
Another Example
Petri Nets: Formal Definition
•	A Petri Net is a four-tuple (P, T, I, O), where
>	P is a set of places
>	T is a set of transitions
>	I is the input function, 	I : T Æ R P
»	 identifies the places leading into a transition
>	O is the output function, 	O: T Æ R P
»	 identifies the places leading out of a transition
•	Notes:
>	Determines a “bipartite directed graph,” where nodes are P » T and edges are defined by I & O
>	Definition implies at most one arc between a transition and any input or output place	
Markings & Execution Model
•	A marking  M of a Petri net is a mapping that is assignment of tokens  to places. 	
M : P Æ N
•	Petri nets are usually associated with an 		initial marking.
•	A transition is enabled  if each of its input places has at least one token.
•	A transition may fire  if it is enabled.
•	The firing of a transition
(a) Removes a token from each input place
(b) Produces a token on each output place
Reachable States
•	The state space  of a Petri net is the set of all markings (marking = state).
•	A marking M' is immediately reachable  from marking M if the firing of some enabled transition in M yields M'.
•	The reachable  states are all markings that can be obtained from some initial marking M.  
•	The reachability set  for a marking M is the set of reachable states. Sometimes indicated by R(M). 
Markings (continued)
•	It is often convenient to represent a marking as a vector
•	Example: 
Initial marking: (1,1,0,0)
After 1 step: (0,0,1,1)
After 2 steps: (1,1,0,0)
...
So reachability set is
{(1,1,0,0),(0,0,1,1)}
Comparing Markings
•	M ≥ M’ iff each place of M has at least as many tokens as each place of M’
•	Example:
>	M = (1,0,0,2)
>	M’ = (0,0,0,1)
•	Note not all markings are comparable
•	Example:
>	M = (1,0,0,2)
>	M’ = (0,1,0,1)
As we have seen ...
•	Petri nets can have nondeterministic transitions.
•	That is, two transitions are enabled and one of them will fire nondeterministically.
•	This makes it possible for Petri nets to model concurrent execution 
>	interleaved firing of transitions
•	Additionally Petri nets can model 
>	synchronization
>	resource sharing
Special Kinds of Petri Nets
Given an initial marking:
•	Safe net: 	No more than one token 				at any place.
•	K-bounded: 	No more than K tokens 				at any place.
•	Bounded: 	K-bounded for some 					value of K.
•	Conservative: 	Number of tokens in net 				remains constant.
Unbounded Nets
Is This Net Bounded?
Non-Conservative Nets
Is This Net Conservative?
Is This Net Conservative?
Other Questions
•	Liveness: 
>	Are all transitions potentially fireable?
•	Reachability:
>	Is  marking M'  reachable from marking M?
•	Coverability:
>	Given  markings M  and  M', does there exist a marking  M" reachable from  M, such that M" ≥  M' ?
Liveness 
Last Slide
Simple Example
Simple Elevator
Producer/Consumer
Is This Net Bounded?
Mutual Exclusion
Is This Net Conservative?
Liveness 
Another Example