Petri Net (PN)
-
VRML World
-
Author: Linda Dance
-
Image Gallery
-
Overview: The Dining Philosophers is a well known model used in
operating systems to illustrate resource sharing, fairness and synchronization.
There are five philosophers and five chopsticks. A philosopher must
obtain the use of his left and right chopstick concurrently to be able
to eat, which means two neighboring philosophers can not eat simultaneously
since they share the resource, the chopstick. If he is unable to
eat, he rests and thinks. Fairness is enforced by random selection
of the ordering in which a philosopher picks up his chopsticks if both
chopsticks are available to him at that time. This example serves
as a demonstration of creating a metaphor on top of a Petri Net. We use
the dining philosopher metaphor with places, transitions and traces.
The PN has fifteen places, ten transitions and forty traces. P0, P2, P4,
P6, P8 represent the five places for the five chopsticks when they are
not in use. P1, P3, P5, P7, P9 represent the five places for each
philosopher's napkin when it is not in use. P10, P11, P12, P13, P14
represent the five places for the unit token of 2 chopsticks and napkin
when in use by the philosopher for eating. T0, T1, T2, T3, T4 represent
the five transitions for eating. T5, T6, T7, T8, T9 represent the
five transitions for resting. The green ellipsoids are representing
the trace from place to transition. The red ellipsoids are representing
the trace from transition to place.
-
Model Templates: PN = Petri Net
-
Metaphors: Dining Philosophers resource sharing with fairness consideration
and synchronization as a Petri Net. The spheres are representing
the places in the petri net. When the sphere is gray, it is representing
that a token is not present. When the sphere is white, it is representing
that a token: chopstick, napkin, or unit of 2 chopsticks and napkin, is
present. The red cubes are representing the control for a philosopher
to pick up the chopstick or put it down. The chopstick resources
are representing the tokens in the petri net. The napkin resources
are representing the synchronization tokens in the petri net, which ensures
that a philosopher can not eat and rest at the same time. The ellipsoids
connecting the places to the transitions are representing the trace the
chopstick takes between eating and resting.
-
Simulation: Viewpoints: Top, Side, Observe, Close Up.
Execution:
press the yellow ball in the center of the table to start the simulation
which places tokens in the inner ring so there are five chopsticks and
five napkins on the table, which makes the petri net a live net.
When it is a transitions turn, if all places connected to the transition
with a green elliipsoid have a token - are white in color, then that transition
can fire, moving the token(s) into the place(s) connected by a red ellipsoid.
The logic is as follows: (P0,1)&&(P1,1)&&(P2,1)&&(T0,1)->(P10,1);
(P2,1)&&(P3,1)&&(P4,1)&&(T1,1)->(P11,1); (P4,1)&&(P5,1)&&(P6,1)&&(T2,1)->(P12,1);
(P6,1)&&(P7,1)&&(P8,1)&&(T3,1)->(P13,1); (P8,1)&&(P9,1)&&(P0,1)&&(T4,1)->(P14,1);
(P10,1)&&(T5,1)->(P0,1)&&(P1,1)&&(P2,1); (P11,1)&&(T6,1)->(P2,1)&&(P3,1)&&(P4,1);
(P12,1)&&(T7,1)->(P4,1)&&(P5,1)&&(P6,1); (P13,1)&&(T8,1)->(P6,1)&&(P7,1)&&(P8,1);
(P14,1)&&(T9,1)->(P8,1)&&(P9,1)&&(P0,1).
The simulation is continuous because the petri net is never in a condition
that a transition can no longer fire.
Animation: The places change color to white while a token
is present. The color changes to gray while a token is not present.
Click the yellow pace button to change the speed of the eating and resting
interval. Audio: Philosopher one eating: One,
Philosopher two eating: Two, Philosopher three eating:
Three, Philosopher four eating: Four, Philosopher five
eating: Five,
-
Modeling PROTOs used: PN (Petri Net), PN_PLACE (PN Place), PN_TRANSITION
(PN Transition), PN_TRACE_PLACE (PN Trace Place -> Transition), PN_TRACE_TRANSITION
(PN Trace Transition -> Place) and World Objects.
-
Object Hierarchy: Objects are defined with an uppercase first
letter with each object having its own PROTO; PROTOs are all uppercase
in parentheses; fields names are in italics; field values are to the right
of field names.
World (OBJECT)
contains Sky, Landscape, Table Cloth, Candle, Clock, Eating Status Board and Table
behavior Table
Table (PN)
places P0, P1, P2, P3, P4, P5, P6, P7, P8, P9, P10, P11, P12, P13, P14
transitions T0, T1, T2, T3, T4, T5, T6, T7, T8, T9
traces (place -> transition) T0p0t, T1p0t, T2p0t, T2p1t, T3p1t, T4p1t, T4p2t, T5p2t, T6p2t,
T6p3t, T7p3t, T8p3t, T8p4t, T9p4t, T0p4t, T10p5t, T11p6t, T12p7t, T13p8t, T14p9t
traces (transition -> place) T0t10p, T1t11p, T2t12p, T3t13p, T4t14p, T5t0p, T5t1p, T5t2p,
T6t2p, T6t3p, T6t4p, T7t4p, T7t5p, T7t6p, T8t6p, T8t7p, T8t8p, T9t8p, T9t9p, T9t0p
P0 (PN-PLACE)
behavior Board0
P1 (PN-PLACE)
behavior Board1
P2 (PN-PLACE)
behavior Board2
P3 (PN-PLACE)
behavior Board3
P4 (PN-PLACE)
behavior Board4
P5 (PN-PLACE)
behavior Board5
P6 (PN-PLACE)
behavior Board6
P7 (PN-PLACE)
behavior Board7
P8 (PN-PLACE)
behavior Board8
P9 (PN-PLACE)
behavior Board9
P10 (PN-PLACE)
behavior Board10
P11 (PN-PLACE)
behavior Board11
P12 (PN-PLACE)
behavior Board12
P13 (PN-PLACE)
behavior Board13
P14 (PN-PLACE)
behavior Board14
T0 (PN-TRANSITION)
script
T1 (PN-TRANSITION)
script
T2 (PN-TRANSITION)
script
T3 (PN-TRANSITION)
script
T4 (PN-TRANSITION)
script
T5 (PN-TRANSITION)
script
T6 (PN-TRANSITION)
script
T7 (PN-TRANSITION)
script
T8 (PN-TRANSITION)
script
T9 (PN-TRANSITION)
script
T10 (PN-TRANSITION)
script
T11 (PN-TRANSITION)
script
T12 (PN-TRANSITION)
script
T13 (PN-TRANSITION)
script
T14 (PN-TRANSITION)
script