UoL CS Notes
Menu

High Level Petri Nets

COMP201 Lectures

Classical Petri nets can have some problems:

  • Petri nets can become too large and complex.
  • It takes too long to model a situation.
  • It is not possible to handle time or data.

High level Petri nets include the following to handle this:

  • Colour
  • Time
  • Hierarchy

Colour

Here is a standard example:

stateDiagram-v2
direction LR
state start <<fork>>
waiting(•••) --> start
note left of waiting(•••): Client waiting
state finish <<fork>>
start --> busy
busy --> finish
finish --> free(•)
free(•) --> start 
finish --> finished
note right of free(•): Hairdresser waiting

Adding colour involves adding attributes to each token:

stateDiagram-v2
direction LR
state start <<fork>>
waiting(•••) --> start
note left of waiting(•••)
	name: Sally
	age: 28
	hairtype: BL
end note
state finish <<fork>>
start --> busy
busy --> finish
finish --> free(•)
free(•) --> start 
finish --> finished
note right of free(•)
	name: Harry
	age: 28
	experience: 2
end note

Colour on Transitions

Transition can also have colour. This can involve:

  • The number of tokens to be produced.
  • The value of these tokens.
  • Optionally, a precondition.

You can see a mathematical example here:

stateDiagram-v2
direction LR
state + <<join>>
a(•) --> +
b(•) --> +
+ --> c
note right of +
	c: = a + b
end note

Here is a conditional example:

stateDiagram-v2
direction LR
state select <<fork>>
a(•) --> select
select --> b
select --> c
note left of select
	if a > 0
	then b: = a
	else c: = a
	fi
end note

Time

To analyse performance, we must model duration and delays.

A timed Petri net associates a pair $t_\min$ and $t_\max$ with each transition.

stateDiagram-v2
direction LR
state start <<fork>>
waiting(•••) --> start
state finish <<fork>>
start --> busy
busy --> finish
finish --> free(•)
free(•) --> start 

note left of start
	Tmin = 0
	Tmax = 3
end note
note left of finish
	Tmin = 5
	Tmax = 10
end note
finish --> finished

We could be answered the following questions:

  1. What is the minimum and maximum times for all three people to have their hair cut in this system?

    \[\begin{aligned} t_\min&=0 + 5 + 0 + 5=10\\ t_\max&=3 + 10 + 3 + 10 =26 \end{aligned}\]

  2. What is the general formula for min and max times with $n$ clients and $m$ haridressers?

    \[\lceil\frac n m\rceil(t_\text{start} +t_\text{end})\]

Hierarchy

This allows you to place a sub-nets in place of a transition:

stateDiagram-v2
direction LR
state h1 <<fork>>
state h3 {
direction LR
state start <<fork>>
state finish <<fork>>
[*] --> start
start --> busy
busy --> finish
finish --> [*]
finish --> free(•)
free(•) --> start

}
state h2 <<fork>>
waiting(••) --> h1
waiting(••) --> h2
waiting(••) --> h3
h1 --> ready
h2 --> ready
h3 --> ready

Example

Consider the following scenario that you have to model as a Petri net:

The message must be triplicated. The three copies must be forwarded through three different physical channels. The receiver accepts the message on the basis of a two-out-of-three voting policy.

stateDiagram-v2
[*] --> OriginalMessage
state f1 <<fork>>
state f2 <<fork>>
state f3 <<fork>>
state f4 <<fork>>
state j1 <<join>>
OriginalMessage --> f1
f1 --> Copy1
f1 --> Copy2
f1 --> Copy3
Copy1 --> f2
Copy2 --> f3
Copy3 --> f4
f2 --> P1
f3 --> P2
f4 --> P3
P1 --> j1
P2 --> j1
P3 --> j1
j1 --> [*]
note left of f1
	Time to Split:
	Tmin = c1
	Tmax = k1
end note
note left of f2
	Time to Send:
	Tmin = c2
	Tmax = k2
end note
note left of j1
	Time to Vote:
	Tmin = c3
	Tmax = k3
end note 
note right of j1
	Tvoting: (P1=P2) or (P2=P3)
		or (P1=P3) else "Error"
end note

From the above formal representation we can:

  • Analyse deadlock and live-lock states.

    Live-lock are a set of states that aren’t useful in a loop.

  • Represent timing and other constraints.