| Home | Up | Questions? |
Petri nets are a popular and useful model for the representation of systems with concurrency or parallelism. They are named for, and have been developed from, the work of Carl Adam Petri, at the Gesellschaft fur Mathematik und Datenverarbeitung in Bonn, West Germany. A Petri net (see Figure 1) is a graph with two types of nodes -- places and transitions. Places are drawn as circles while transitions are drawn as bars. Directed arcs (arrows) connect places to transitions and transitions to places. For each transition, the directed arcs define its input places (an arc from a place to the transition) and its output places (an arc from the transition to a place).
Figure 1. An example Petri net.
A Petri net is executed by defining a marking and then firing transitions. A marking is a distribution of tokens to the places of the Petri net. A token is represented on a Petri net graph by a small solid dot in a place. A transition is enabled whenever all of its input places have tokens. A transition fires by removing one token from each of its input places and adding one token to each of its output places.
For example, in the marked Petri net of Figure 1, two transitions are enabled. Transition b has one input (p2) and that place has a token, so transition b is enabled. Similarly, transition e has tokens in both of its input places (p4 and p7), so it is also enabled. Transition d is not enabled since there is no token in place p5, one of its inputs. To fire transition b, we remove the token from p2 and put a token in p5 and a token in p8 (its two outputs). This would enable transition d. Firing transition e will remove a token from both p4 and p7 and put a token in p10.
If more than one transition is enabled, the firing of these transitions is generally asynchronous -- they may fire simultaneously or at different times before or after each other. For example, in Figure 1, transitions b and e are enabled and may fire completely independently. If two transitions share input places, then they are in conflict and only one can fire. In Figure 1, transitions f and g are in conflict when a token is in place p8.
Petri nets are a simple, elegant model of information flow. The simplicity of the Petri net model makes them useful for describing and explaining systems, especially systems with concurrency and synchronization. Petri nets have been used mainly to model computer hardware (e.g. asynchronous circuits, pipelined computers, and computers with multiple functional units such as the CDC 6600 and IBM 360/91) and computer software (e.g. sets of cooperating processes, communication protocols, and operating systems). Transitions represent events in the modeled system while places represent resources or conditions. For example, Figure 2 is a Petri net model of a disk scheduling algorithm with 2 disk drives, a disk controller and a channel. The two available disk drives are represented by two tokens in the ``disk drive available'' place. Only one disk controller is available.
Figure 2. A Petri net model of an algorithm for allocating a disk controller and disk drives.
A Petri net can be analyzed to determine properties of the modeled system. Analysis techniques have been developed to decide if the number of tokens in a Petri net is bounded, if tokens are conserved, if deadlocks can occur or if mutual exclusion is violated. These correspond to important problems for concurrent systems, but more general analysis techniques would be useful. Current techniques are based on either of two approaches: (1) a matrix representation of the Petri net, or (2) a tree representation of its state space.
One typical analysis technique is the reachability problem: Given a Petri net with an initial marking and a desired final marking, is it possible to fire transitions and change the initial marking to the desired final marking? Researchers have shown that the reachability problem is decidable, although expensive. The time and memory (computational complexity) needed to analyze a Petri net grows exponentially with the size of the Petri net (in the worst case).
Petri net execution does not include a concept of time, only the relative order of events. When performance metrics of systems are desired, the execution time of an transition must be defined. (A few models which associate time with places have been suggested, but they can be shown to be equivalent to times associated with transitions.) Two extended Petri net models are used for performance analysis: Timed Petri nets and Stochastic Petri nets. Both models have the concept of time (or a clock) associated with transition firings. For Timed Petri nets the time value is constant; for Stochastic Petri nets the time is a random variable (typically exponentially distributed).
Since transition firings are no longer instantaneous the semantics of transition enabling can be changed. Two cases are possible. First, the tokens in the enabling marking may be removed when the particular transition that will fire has been determined. The appearance of the tokens in the output places is then delayed by the transition firing time. This is an example of transition firing with preselection semantics. Second, the tokens in the enabling marking may be left in the input places so that conflicting transitions are still enabled (and their firing clocks are also running). This is considered non-preselection of transition firings and is the enabling method assumed in Stochastic Petri nets.
The addition of a time for the firing of transitions adds significant complexity to the model. In the case of Timed Petri nets, the reachability set may be a subset of the reachability set of the underlying Petri net. When the time is a constant time value, it has been shown that even the boundedness question becomes undecidable. In the case of Stochastic Petri nets the reachability set does not change with the introduction of time (assuming that the proability density of the random variables are non-zero on the interval of [0,$inf$]).
Continued work on Petri nets and their use is resulting in the development of a new research area called general net theory. Within this general theory, special net theory corresponds to the Petri net model described here.
| Home | Comments? |