9.3 Classical Petri nets

---

9.3 Classical Petri nets

Given the basic definitions and notation from the prior section, we can now begin to examine how these fundamental elements can be used in modeling aspects of computer systems and ultimately entire systems. The first new notation required is that of Petri net state transitions. To move from one state to another state, a Petri net will fire all transitions that are enabled. The exact moment of firing can be pictured as occurring as a clock signal in a computer system. When the clock begins a cycle (e.g., a rising edge) all gates that have signals enabling their execution do so during the cycle. Similarly, in a Petri net all transitions that are enabled will fire once during this cycle.

Before we look at firing, we need to address the conditions required. Having tokens available in places is fundamental to the concept of enabling transitions. Therefore, it is important to know the state of the entire Petri net before preparing to fire enabled transitions. The enabling of a transition is caused by tokens being available in places that are members of a transition's input function. Only if all of the places named in a transition's input functions have tokens available is a transition enabled (Figure 9.9).

Figure 9.9: Enabled transition.

The Petri net shown in Figure 9.9 has the marking μ₀ = (1,2,0), input function I(t₁) = {p₁,p₂,p₃} and output function O(t₁) = {p₃,p₃,p₃}. Given this initial marking and the defined input and output functions, transition t₁ is enabled, since it requires one token contributed by P₁ and two tokens contributed by P₂ to have all of its input functions satisfied with tokens available in the named places and in the required quantities. The tokens in these places are referred to as the transition's enabling tokens. Given that a transition is enabled at the beginning of a Petri net's firing cycle, it will fire the transition, causing the movement of the number of tokens from its input places to its output places, as modeled by the output function's arity. The result of this firing will be a new Petri net state, μ₁. For example, in Figure 9.9, given the initial state μ₀, transition t₁ will fire at the beginning of the firing cycle, removing one token from place p₁ and two tokens from place p₂ and placing these three tokens into place p₃. The resulting new Petri net state is represented by the marking μ₁ = (0,0,3), and is depicted in Figure 9.10. The firing action is considered an atomic action, in that it appears as if all of the tokens are removed from the input places and deposited into the output places instantaneously.

Figure 9.10: New Petri net state.

The firing of the Petri net provides the movement from one state to a new state. The new state is the only state reachable in a single total transition firing of all the enabled transitions. The collection of all possible states that can be represented by this Petri net and its initial markings is called state-space. The collection of all states in the state-space of this Petri net can only be reached in sequence from the initial state to the final state by single step, state-space changes. This implies that a Petri net can only fire enabled transitions, and, after they fire, they cannot fire any newly enabled transitions until the next cycle. This single state Petri net state-change can be described using a next-state function, δ. This function, δ, when applied to a Petri net state, μ_i, will cause the Petri net to transition from state μ_i to a new state: μ_i+1. The function δ is then defined as:

(9.5) 

The set {t} represents the set of all enabled transitions within this Petri net. If a transition is not enabled, then this function is undefined.

Beyond the basics defined here, Petri nets have been developed for the modeling of conditions not typically available through queuing theory. For example, synchronization, conflict, and concurrency are concepts not easily defined and modeled by queuing theory.

To clarify some of the concepts covered we will take a look at a simple example: that of resource sharing. In this example, shown in Figure 9.11, we model two user processes requesting a specific resource (p_{res_idle}). If the resource is idle, there is a token present in the p_{res_idle} place. If a process wanting this resource has a token in its place (e.g., P_{1_req}), and the resource is idle (a token in p_{res_idle}), then the transition (e.g., t_{1_start}) is enabled and can fire on the next cycle. When the transition fires, the resource now becomes unavailable (it is busy), and the second process must wait until the resource is released (Figure 9.12).

Figure 9.11: Resource sharing example.

Figure 9.12: Allocated resource.

With these basic concepts we can now move on to more advanced ones. Very often in a computer system, when one process is accessing or even attempting to access some resource, others are blocked from trying to enter. This is the concept of a gate, lock, or semaphore. In the case of such items, when one job has control over the resource, others are blocked from attempting to access the resource, even if they have all the other resources they need to move forward with their execution. To model this concept of a lock or semaphore, Petri net modelers developed the concept of the inhibitor. An inhibitor is a function that relates a place (as a blocker) to a transition. If a place, p, has an inhibitor relationship with a transition, t, then, when place p has a token present, transition t cannot fire, even if all input functions are satisfied and the transition would be otherwise enabled. For example, Figure 9.13 depicts the reader and writer problem. The problem states that when a writer is in the mode of writing, all readers must be blocked from accessing the held resource. In the example, the inhibitor is shown as an undirected arc with a small circle at the transition being inhibited by the place at the other end of the arc. The example shows that place, p₆ is acting as the inhibitor to transition t₅. The Petri net is now described using the six-tuple, M = (P, T, I, O, N, H). In the set notation the inhibitor is described as H{t₅} = {p₆}.

Figure 9.13: Petri net with an inhibitor.

A Petri net's state, μ, is said to be reachable from some other state, μ', if there exists some finite number of firings of the Petri net beginning at state μ, which will result in the final marking μ'. A reachability set [RS(μ)] from each valid marking of our Petri net, M starting in state N, is defined as the set of all possible markings reachable through any set of firings. There is no reachability set possible for a Petri net with an initial null marking.

The reachability set for a Petri net with an initial marking, μ₀, is denoted RS(μ₀) and is defined as the smallest set of markings, so that:

(9.6) 

To determine the reachability set, we must begin from the initial state, μ₀ and incrementally define each step possible emanating from this initial state and all states derivable from this state. Once a marking has been considered, during any iteration, it cannot be considered again. The reachability set for the reader and writer graph shown in Figure 9.13 is as follows for k = 2.

μ₀ = 2p₁ + p₅

μ₁ = p₁ + p₂ + p₅

μ₂ = 2p₂ + p₅

μ₃ = p₁ + p₃ + p₅

μ₄ = p₁ + p₄ + p₅

μ₅ = p₂ + p₃ + p₅

μ₆ = p₂ + p₄ + p₅

μ₇ = p₁ + p₅ + p₆

μ₈ = p₁ + p₇

μ₉ = 2p₃ + p₅

μ₁₀ = p₃ + p₄ + p₅

μ₁₁ = p₂ + p₅ + p₆

μ₁₂ = 2p₄ + p₅

μ₁₃ = p₂ + p₇

μ₁₄ = p₃ + p₅ + p₆

μ₁₅ = p₄ + p₅ + p₆

μ₁₆ = p₃ + p₇

μ₁₇ = p₄ + p₇

μ₁₈ = p₅ + 2p₆

The reachability set contains no information about which transitions fired to reach the state markings. Such information can be found in a reachability graph, shown in Figure 9.14. In this graph each node represents a state of the Petri net and each arc represents a direct transition, which is possible from one end of the directed arc to the other end due to a single transition's firing. For example, you can see that if we fire transition t₁ from μ₀ we can get to a new state, μ₁, where a token has moved from place 1 to place 2.

Figure 9.14: Reachability graph for the reader and writer problem.

It is often desirable to model logical conditions. For example, to only fire a transition when there are more than n tokens in a place, we simply need to include an arc with arity n + 1. Since the basic condition on a transition firing is that its connected input places meet the conditions of the transition's input function, by including n + 1 redundant set items for the input place we can accomplish what we need (Figure 9.15).

Figure 9.15: Petri net component to test condition greater than M.

If we wish instead to test for the condition of equal to some value but not greater than the value, we can use an inhibitor of arity n + 1 to block a transition if there are more than n tokens in place 0. To meet the equal condition we use the arc weighted at n to remove n items if there are n and only n items (Figure 9.16). If we wish to test for less than n items and remove the items, we could use the Petri net shown in Figure 9.17. Again, this Petri net uses an inhibitor function to block movement of the desired number of tokens.

Figure 9.16: Petri net component to test condition equal but not greater than M.

Figure 9.17: Petri net modeling conflict.

An important property required when modeling computer systems is that of conflict (Figure 9.18). In this example, when there is a token in place p₀, both transitions t₁ and t₂ are enabled. However, only one of them may fire, since there is only one token available. As soon as one fires, say t₁, it removes the token from place p₀ and transfers it to place p₁. As soon as transition t₁ removes the token, transition t₂ is no longer enabled. If there were two tokens in place p₀, then both of the transitions would be enabled and could fire during this firing cycle. Very often we wish to indicate which of these transitions is to fire when only one can, and in which order if they both are able to fire. We will discuss some of these extended controls when we look at colored Petri nets and generalized Petri nets later in this chapter.

Figure 9.18: Petri net component to test condition less than.

Another important property required when modeling computer systems and software processes is concurrency. Concurrency is characterized by the concurrent or parallel execution of activities. For a Petri net to have concurrent activities, it is required that we have concurrently enabled transitions. For example, in Figure 9.19, transitions t₁ and t₂ are considered concurrent, since they are both enabled at the same time in the Petri net marking. In our example, μ = (1,2,0,0) has transitions t₁ and t₂ enabled, and, therefore, they can fire concurrently.

Figure 9.19: Petri net modeling concurrency.

Very often a computer system can have both conflict and concurrency occur at the same time. In Figure 9.20 we have an initial marking, μ = (1,1,0,0,0), which results in transitions t₁ and t₂ being enabled, the condition of concurrent transitions. If t₁ fires first, then we now have two transitions enabled, t₂ and t_3. This then depicts conflict, since the token from p₂ can only satisfy one of the necessary conditions for the two transitions it is enabling at this point in time.

Figure 9.20: Petri net modeling confusion.

A Petri net can have a variety of other qualities. For example, a Petri net state, μ, is reachable from another state, μ', of the same Petri net if there is an integer number of intermediate steps from μ' that lead us to state μ. For example, in Figure 9.21 we have an initial state μ₀ = (3, 0, 0, 0), and a target state μ' = (1, 1, 0, 1). We can see from our computations of state transitions that our net can reach this target state in three firings of our net. A related property is that of reversibility. Reversibility is the property where, given some initial Petri net state, μ, we can return back to this state, μ, in finite time. In Figure 9.21 the initial state, μ₀, is not reversible, since we cannot get back to this state in a finite number of steps. On the other hand, if the initial state is μ' = (0, 1, 0, 2), we find that we can return to this state every four state transitions. Therefore, this state is reversible.

Figure 9.21: Petri net indicating reachability and reversibility.

A Petri net is deadlocked if there are no transitions in the net that are enabled. In the example shown in Figure 9.22, the net has an initial marking, μ₀ = (0, 0, 2, 0). This marking results in no transitions being enabled and no hope after an infinite amount of time of becoming enabled. Conversely, a Petri net is considered live if there are any transitions enabled.

Figure 9.22: Deadlocked Petri net.

A Petri net is defined to be k-place bounded if for all places in the network there are k or less tokens in each place for all possible states of the network. For example, in the Petri net shown in Figure 9.21, we have a three-bounded net, since all places in the network have at most three or less tokens in their places for all reachable states within the Petri net.

Mutual exclusion is the final property we will define for traditional Petri nets. Mutual exclusion is defined for places and for transitions. The property holds for pairs of places or transitions within a Petri net. Two places, p_a and p_b, are mutually exclusive in a Petri net system if for all states in the system places p_a and p_b are never both loaded with tokens concurrently. This implies that if one has tokens the other cannot. Similarly, for transitions, a Petri net possesses transition mutual exclusion if for all pairs of transitions in the Petri net, t_a and t_b, only one can be enabled during any state reachable by this network. The properties presented in this section are generic and can be applied to most Petri nets.

---