Petri Nets

Slides by Topic

1. Familiarity with an important modeling tool

* areas Petri nets can model well

* limitations of Petri nets

* variety of representations

* common properties

2. Capabilities with the tool

* understand complex models

* develop simple models

3. Further information:

World of Petri Nets

look for simulators under «Tools and Software» link

* complex processes

* concurrent activities

* flow of data or other things

may be transformed on the way

* multiple coordinated flows

hence abstraction of Data Flow Diagrams

focusing on synchronization

Some visual similarity between FSA and Petri Nets diagrams
both have circle and arrows

FSA are special cases of Petri nets

In general, Petri nets

* emphasize locality of condition
verses global state

* have multiple conditions active at once
hence non- determinacy more global

* express complex transitions succinctly

* allow multiple instances in one condition
without bound

+ explicit coordination / synchronization

- no identity of «packets»

expand this figure

Can imagine each Petri net as

* a unique gameboard

but

* using the same kind of pieces and

* following the same general rules

Each Petri net looks like a gameboard with

* circles called conditions or places

* bars called events or transitions

* arrows, called input arcs , from conditions to events

* condition is input to the event

* arrows, called output arcs , from events to conditions

* condition is output from the event

* multiple parallel edges possible

Notation:

expand this figure

* formally, a «bipartite directed multigraph»

A token on a condition

* means that condition currently is true

* is drawn by a black dot on that condition

* may share that condition with other tokens, indicating multiple objects sharing that condition

* during a given turn, may stay on a condition or move to an event

A marking of a Petri net

* is a function from the conditions to the non-negative integers

* indicates the number of tokens currently at that condition

An event is enabled when it is possible to place

on each input arc

a token from the corresponding input condition

An event fires

* only if it is enabled

* by consuming a token along each input arc

* and producing a token along each output arc

Indeterminate firing:

* If more than one event is enabled at a given time, any of the enabled events may fire

Concurrency:

* Formally, two events may not fire at the same time

* However, this is often not relevant, so it is common to think of event firings as being concurrent

expand this figure

expand this figure

     PARBEGIN
          S1, S2, ... Sk
     PAREND 

expand this figure

The simplest switch:

expand this figure

Use this to en/dis-able other transition(s)

expand this figure

What is wrong with the above?

Objective: prevent two programs from accessing the same data structure simultaneously

Code where a program accesses the shared structure is called the critical section

expand this figure

Issue is lock on buffer to prevent simultaneous access

expand this figure

expand this figure

A machine shop has resources:

* machines M₀, M₁, and M₂

* operators O₁ and O₂

Subject to the constraints:

* O₁ can operate M₀ and M₁

* O₂ can operate M₀ and M₂

* an order is processed first by M₀ and then either M₁ or M₂

Significant events:

* order arrives

* O_i [ begins | ends ] operating M_j

* product is shipped

Significant conditions:

* order waiting for M_j

* O_i or M_j is idle (5 cases)

* O_i is operating M_j (4 cases)

* order partially done

* product awaiting shipment

expand this figure

* PERT networks

* example: building a house

* Many complex processes in society

* example: civil legal action

A Petri net graph consists of

P a finite set of conditions (Places)

T a finite set of events (Transitions)

I a finite multiset of arcs from P to T (Inputs)

O a finite multiset of arcs from T to P (Outputs)

A marked Petri net consists of

G a Petri net graph <P,T,I,O>

m a function, m : P -> Z
Z = non-negative integers

          |
          |     conditions
       ---+---------------------
       e  |
       v  |
       e  |
       n  |
       t  |
       s  |

       

                            p1       p2       p3       p4

t1       <         1         ,         0         ,         0         ,         0         >
t2       <        -1         ,        -1         ,         2         ,         2         >
t3       <         0         ,         0         ,        -2         ,        -1         >
t4       <         0         ,         1         ,         0         ,        -1         >

 loop                loop
   acquire R1;         acquire R2;
   acquire R2;         acquire R1;
   critical            critical
       section;          section;
   release R1          release R1
       and R2;            and R2; end
end