all about petri netis model and simulation

Petri
Nets
Lecturer. Roohollah Abdipour

Agenda
• Introduction
• Petri Net
• Modelling wïth Petri
Net
• Analysïs of Petri net

Introduction
• Techniques for Evaluating SW / HW:
—Simulation
—Testing
Deductive Verification
—Model Checking

Introduction
• Simulation & Testing:
—Needs experiments before system deployment
—Simulation is performed on an abstraction of a
model of the system
—Testing is performed on the real system.
— It is very diffucult to evaluate all
possible interactions / faults /
behaviors / states

Introduction (3)
• Deductive Verification:
— Validate a system's performance
based on deductive rules
—Applicable to infinite-state systems
—A time-consuming process
—Needs expert people with good
experiments
— Usually is used for critical systems (e.g.,
security protocols)

Introduction
• Model Checking:
—An automated technique to evaluate finite-state
systems
— Perform a thorough search in the state
space of the system in order to determine some
properties of the system.

Introduction
• The process of Model Checking:
• Modeling: Transform a design to formalism
(e.g., a state-transition graph of the system)
• Verification: Perform a thorough search in the state
space of the system in order to determine whether some
properties of the system are true or not.
• Is performed automatically

Petri Net
• A ‘Petri Net’ was introduced by a
German mathematician and used to model a
system
— Condition: a Boolean description of the state
of the system
— Event: an action that depends on the state
of the system
• Petri net is a graphical and mathematical tools
for
the analysis of discrete event dynamic systems.
— The system model is represented by a
set of conditions and a set of events
—A condition is represented by a place and an event by
transition.

Petri Net: Building Blocks
Basic
Elements
• PN consists of three types of components: places (circles),
transitions
(rectangles) and arcs (arrows):
— Places represent possible states of the system;
— Transitions are events or actions which cause the change of
state; And
— Avery arc simply connects a place with a transition or a
transition
with a place.

• Building Blocks:
• An
example:
tJ
Petri Net
input place
token
P
Input arc
transition
'
1
P2
output place
output arc

Petri Net: Marks
(Tokens)
• A marking M is an assignment
of (dots) to places of a petri net.
token
s
• Dots are placed in the circle to
represent place in which its condition is
satisfied
— e.g. a resource is available or
operation in a process
• The marking can be represented as M
= (1,1,0)

Petri Net: Marks (Tokens)
• A place can have more than one token
and
therefore can represent a queue
— (e.g. a @ffer holding several prgcesses).

Petri Net : Firing a transition
• Executing a marked Petri net causes the number
and positions of the token to change. The rules for
the execution are:
—A transition is enabled if all its input places contain at least
one token.
—Any enabled transition may fire
—Firing of a transition results in one token being removed
from each of its input places and being deposited
of its output places
—Execution halts when there are no enabled transitions.
Each time a transitions fires, the marking of the petri net
will change.

Petri Net : Exam
Ie
q 1 1 0
t2
001
010

Petri Net: Formal Definition
A Petri net (PN) is a 5 tuple
PN (P,T,IN,OUT,M)
where:
P = {p1,p2,....,p } is a finite set of
places, T = {t1 , t2, ...,tn} is a finite set of
transitions IN: (PxT)—+S
OUT: (TxP)—>S
M: Marking vector

Petri Net: Formal Definition (cont'd)
• IN are
input
functions defining directed
arcs
fro
m
• places to transitions
• OUT are output functions defining directed
arcs
• from transitions to places
• S is a set of all nonnegative integers k such
that:
• If k = 1 a directed arc is drawn without a
label
• If k > 1 a directed arc is drawn with label k.
• If k = 0 no arc is drawn.

Petri Net: Formal Definition (cont'd)
• An example:
Its I = Opgl Ott I = I sql
If q = t l , O,O, 0, OJ
1
7

Petri Net: Firing Rules for
Transitions
• A specific transition I, is said to be firable or
enabled if each input place pt is marked with at least
w(p„t ) tokens where w(p„t,) is the weight of the arc
from p, to t,.
• An enabled transition may or may not fire depending
on whether or not the event actually takes place .
• The firing of an enabled transition th removes vv(p ,t )
tokens from each input place p, of I;, and
adds w(pj§ ) tokens to each
output place p, of t
h where w(p„t) is the weight of
the arc from input place p, to t„ and
w(p„t;) is the weight of the arc from I, to
output place p,

Petri Net: Firing Rules for Transitions
P1
P2
T1
TI is not etabled
T1
T'i i”s
enabled

Petri Net: Firing Rules for Transitions
• Firing Examples
p
1
p
2
Ti
p3
p
1
p2
p3

PN: Firing Rules for Transitions
• Firing Examples
(b
)

PN: Firing Rules for Transitions
• Fïring of a sequence of
transitions:
), -- (1, 2, 0, 2,1)

Firing Rules for Transitions
• Firing of a sequence of
transitïons:
r.

• Firing of a sequence of transitïons:

• Firing of a sequence of transitïons:
3' (0,3,1,1,2)

PN: Change of States
(1)
• is denoted by a movement of token(s)
(black dots) from place(s) to place(s);
and is caused by the firing of a
transition.
• The firing represents an occurrence of
the event or an action taken.
• The firing is subject to the input
conditions, denoted by token
availability.

PN: Change of States (2)
• A transition is lira///e or enabled when
there are sufficient tokens in its input
places.
• After firing, tokens will be transferred
from
the input places (old state) to the
output
places, denoting the new state.
• Note that the examples are Petri nets
representation of a finite state machine
(FSM). PNs are much more powerful to
model systems beyond F5Ms.

Modelling with petri net
• Petri net is mainly used for modelling.
—Many systems can be modelled by petri net.
• The system may be of many different
kinds like computer hardware, computer
software, physical system and so on.
— Petri net is used to model the
occurrence of various events and activities in the
system.

• Sequential Execution:
ti
Sequencetial execution

— Concurrency: two events
could take place in
parallel, without
interfering with one
another.

Synchronisation:
By having two
places as input
conditions to the
same transition,
these two
conditions
become
synchronised.
Sjmchronation

• Example : Concurrency and Synchronisation

• Confilincts:
• Two transitions t1 and t2 are
said to be conflict if
either th
or t can occur but not
both of
2
them,
—i.e., when there is one
place acting as
input
to a number
of
that is
condition
transition
s.
— Therefore, only one
transition can be fire.
ti 2
Co
d

• Merging:
4
Mergin g

• Example: Font
Selection
T1
Bold on
T2
Bold off
User presses
Old
User presses
italic
T3
Italic on
T4
User presses
italic

• Another Example: a finite-state machine
— Consider a vending machine
• It accepts either nickels or dimes
• Sells 15c or 20c candy bars
• The vending machine can hold up to 20c
• Coin return transitions are omitted
the next slides are the state diagram of this
vending machine which represented by the
Petri net Any finite-state machine (or its state
diagram) can be modeled with a state
machine.

• Another Example: a finite-state machine
Deposit 5c
Deposit 5
Deposit 10c
Get 20c
candy

• Mutual exclusion
Recall: Mutual exclusion is a technique of defining
entry and exit code so that at most one process is
allowed to access the critical region at the same
time.
• The idea is that no process is allowed to enter the
critical region, unless it checks that no other process is
executing its own critical region.
Mutual exclusion can be represented in Petri net
using conflict.

Mutual exclusion
permission to enter
• The place s
represents
the
the
critical region
and
there must be token in p 1
and p .
2
— If both processes want
to
simultaneously,
enter the critical region
then
transition t1 and t2 are in
conflict
— i.e., only one of them can
fire.
' ' I ''
I( ''!
t2 “
Critical
section
Process 2
2 1
Process
1
{1
section

Producer consumer problem
• bounded
buffer
Produc
e
Put in
buffe
Re ove
buffe
r
Consum
e
Consume
r

Analysis of Petri net
• Petri nets are capable of modelling a
large variety of systems and properly
representing the interactions between the
various actions which can occur.
— The strength of Petri net is its capability to
model the system.
• However, modelling by itself is of little use and its
necessary to analyse the modelled system.
This could lead to important insights into the
behaviour of the modelled system.

Reachibility
• Given a Petri net, one would like to know
which marking Mr can be reached from an
initial marking MO
• Example:
For the Petri net of the bounded
buffer
consumer producer problem, M0 = (1,
0, 1, 0,
0, n) and M1 = (0, 1, 1, 0, 0, n)
— is immediately reachable from the marking
of M .

Analysis of Petri net : Safeness
• A place in a Petri
net is safe if the
number of tokens in
that place never
exceeds one.
A petri net is same if
all
its places are safe.
what does this Petri
net do?

Analysis of Petri net : Boundedness
• A place is k-safe or k-bounded if the number
of tokens in that place cannot exceed an
integer k.
—Therefore a place is 1-bounded is simply a safe place.
• Example:
—The Petri net for the producer/consumer
problem with a bounded buffer, is it safe? Bounded?
The Petri net for the producer/
consumer problem with a unbounded buffer, is
it bounded? Why?

Analysis of Petri net : Conservation
• A Petri net with an initial marking M0, is
strictly
conservative,
if for all the reachable marking, the total number of
tokens in each marking is exactly the same as the
initial marking.
• A Petri net can be used to model
resource allocation systems. In this systems
some tokens may represents the resources.
— Therefore, in such Petri nets conservation is
an important property such that resources can neither
be created nor destroyed.

Analysis of Petri net : Liveness
• Another problem that could occur in
resource allocation is deadlock.
—A deadlock in a Petri net is a transition (or a
set of transition) which cannot fire.
—A transition is alive if it is not deadlock.
—A transition is live in a marking M if it is potentially
fireable in every marking in the Petri net.
I-- i | --. | › , |
t , ,-I
.' - ' ! '',' 'i .' .
”
. .- . ”

Exercises
• For the above
Petri bounded,
live, and why?
net, indicate whether
each is conservative or
not and show

Summary
• Petri net
concepts
Petri net representation
Firing a transition
— Marks (Tokens)
• Modeling with Petri
net
Events and condition

all about petri netis model and simulation

Recommended

More Related Content

Similar to all about petri netis model and simulation (20)

More from AssadLeo1 (20)

Recently uploaded (20)

all about petri netis model and simulation