Petri Nets

Definition and basic ideas

Definition

The MARKED PETRI NET (P-net) is a 5-tuple (P,T,I,O,M) where P and T are non empty finite sets of PLACES and TRANSITIONS respectively. (The sets P and T have no common elements.)
I is the so called Input function: I: PxT-> N, where N is the set of non negative integer numbers. The value I(p,t) is the number of (directed) ARCs from the place p to the transition t.
O is the so called Output function: O: TxP-> N, where the value O(t,p) is the number of arcs from the transition t to the place p.
So the 4-tuple (P,T,I,O) is a bipartite (directed) multigraph whose arcs connect nodes from two distinct sets (P and T).
M is the Initial marking of places: M: P -> N, where the value M(p) is the number of the so called TOKENS that are located in the place p.

Interpretation

A transition is ENABLED if all places contain at least so many tokens as is the number of arcs from the place to the transition. A transition which is not enabled is DISABLED. An enabled transition may be FIRED. During firing every arc whose endpoint is the transition REMOVES one token from its starting (input) place and every arc starting at the transition ADDS one token to its ending (output) place.
From modeling point of view places represent certain conditions that must be true for some activities (transition firings) to start. Firing changes the markings of both input and output places. This may enable or disable other transitions, etc. All enabled transitions that are not mutually exclusive may be fired in parallel.
There are many extensions to the basic P-net theory improving modeling power of network models. Petri nets have both analytical and descriptive (modeling) capabilities. For more details and for classification of various types of Petri and related nets, visit the World of Petri Nets - see Reference.

Drawing

Places are drawn as circles that are either empty or that contain some number of tokens. Because of practical reasons PetriSim does not draw tokens as small filled circles but every place contains an integer (non-negative) number of tokens. Name of the place is displayed at the bottom right side of the place.
Transitions are drawn as short thick lines. PetriSim also displays the name at the bottom right side of the transition. PetriSim allows either horizontal (default) or vertical direction of a transition. Enabled transitions are displayed with a mark.
Arcs are lines finished by an arrow. Points where the arcs start/end are defined by the user. PetriSim allows any length and shape of arcs.

Example

The following picture (created by PetriSim) is an example that models a cooperation between two processes called Producer and Consumer:

The Producer prepares data and writes them to buffers. If there is no empty buffer, the Producer must wait. The Consumer reads the data supplied by the Producer. The initial marking of the place Empty_buffers is the total number of buffers available (initially all the buffers are empty). The place Semaphore ensures that only one process can work with the data at a time. After reading the data the Consumer returns the empty buffer.
The above picture shows the P-net in the initial state, when the Producer is ready to start writing data, all buffers are empty, the Consumer is ready to accept data. Note that the transition Producer_works is enabled because of the token in the place Producer_starts.

Next picture shows the P-net after firing the transition Producer_works. This picture has been taken in PetriSim Simulation mode.

Note how firing moved the token from the place Producer_starts to the place Data_ready. This has enabled the transition Writing_data. Its firing in the next step moves the token back to place Producer_starts, so Producer will be again in its initial state. Firing of Writing_data moves also one token from Empty_buffers to Data_in_buffer. A token from the place Semaphore is taken only for this firing (see next picture).

The following picture shows a refinement of the above model. Here both writing and reading data may take some time, which is represented by another two places. There are now two transitions per operation representing start and finish of the operation:

In this model the use of Semaphore is obvious. Either reading or writing takes the token from Semaphore, the other operation must wait until the successful one is completed. Note that there are two enabled transition. The one to be fired in the next step is either selected by user or PetriSim selects it randomly. This is a way how P-nets cope with parallelism. In the real situation both operations (preparing data by Producer and reading data by Consumer) are independent and may be carried on in parallel.

PetriSim manual contains some more Examples.

Reference

This page contains an extract from the PetriSim manual. For more information visit the World of Petri Nets page that contains many useful links and references. There you can subscribe for The Petri Net Newsletter, you can get a comprehensive updated bibliography, information on many existing Tools on the Web, Petri Nets Standard, Petri Nets People, Events, etc.

This article is translated to Ukrainian by Irma Alekseeva.

Go back to Heading
Go back to Home page