Deadlock Characterization
In the previous section we illustrated how deadlock could occur in multi- threaded programming using mutex locks. We now look more closely at con- ditions that characterize deadlock.
Necessary Conditions
Adeadlock situation can arise if the following four conditions hold simultane- ously in a system:
1. Mutual exclusion. At least one resource must be held in a nonsharable mode; that is, only one thread at a time can use the resource. If another thread requests that resource, the requesting threadmust be delayeduntil the resource has been released.
2. Hold and wait. A thread must be holding at least one resource and waiting to acquire additional resources that are currently being held by other threads.
3. No preemption. Resources cannot be preempted; that is, a resource can be released only voluntarily by the thread holding it, after that thread has completed its task.
4. Circular wait. A set {T 0, T 1, …, Tn} of waiting threadsmust exist such that T 0 is waiting for a resource held by T 1, T 1 is waiting for a resource held by T 2, …, _Tn_−1 is waiting for a resource held by Tn, and Tn is waiting for a resource held by T 0.
We emphasize that all four conditions must hold for a deadlock to occur. The circular-wait condition implies the hold-and-wait condition, so the four
/* thread one runs in this function */ void *do work one(void *param) {
int done = 0;
while (!done) { pthread mutex lock(&first mutex); if (**pthread mutex trylock**(&second mutex)) {
/** * Do some work */
pthread mutex unlock(&second mutex); pthread mutex unlock(&first mutex); done = 1;
} else
pthread mutex unlock(&first mutex); }
pthread exit(0); }
/* thread two runs in this function */ void *do work two(void *param) {
int done = 0;
while (!done) { pthread mutex lock(&second mutex); if (**pthread mutex trylock**(&first mutex)) {
/** * Do some work */
pthread mutex unlock(&first mutex); pthread mutex unlock(&second mutex); done = 1;
} else
pthread mutex unlock(&second mutex); }
pthread exit(0); }
Figure 8.2 Livelock example.
conditions are not completely independent. We shall see in Section 8.5, how- ever, that it is useful to consider each condition separately.
Resource-Allocation Graph
Deadlocks can be described more precisely in terms of a directed graph called a system resource-allocation graph. This graph consists of a set of vertices V and a set of edges E. The set of vertices_V_ is partitioned into two different types of nodes: T = {T 1, T 2, …, Tn}, the set consisting of all the active threads in the system, and R = {R 1, R 2, …, Rm}, the set consisting of all resource types in the system.
A directed edge from thread Ti to resource type Rj is denoted by Ti → Rj; it signifies that thread Ti has requested an instance of resource type Rj and is currently waiting for that resource. A directed edge from resource type Rj to thread Ti is denoted by Rj → Ti; it signifies that an instance of resource type Rj has been allocated to thread Ti. A directed edge Ti → Rj is called a request edge; a directed edge Rj → Ti is called an assignment edge.
Pictorially, we represent each thread Ti as a circle and each resource type Rj as a rectangle. As a simple example, the resource allocation graph shown in Figure 8.3 illustrates the deadlock situation from the program in Figure 8.1. Since resource type Rj may have more than one instance, we represent each such instance as a dot within the rectangle. Note that a request edge points only to the rectangle Rj, whereas an assignment edge must also designate one of the dots in the rectangle.
When thread Ti requests an instance of resource type Rj, a request edge is inserted in the resource-allocation graph. When this request can be fulfilled, the request edge is instantaneously transformed to an assignment edge.When the thread no longer needs access to the resource, it releases the resource. As a result, the assignment edge is deleted.
The resource-allocation graph shown in Figure 8.4 depicts the following situation.
• The sets T, R, and E:
◦ T = {T 1, T 2, T 3} ◦ R = {R 1, R 2, R 3, R 4}
◦ E = {T 1 → R 1, T 2 → R 3, R 1 → T 2, R 2 → T 2, R 2 → T 1, R 3 → T 3} • Resource instances:
◦ One instance of resource type R 1
◦ Two instances of resource type R 2
◦ One instance of resource type R 3
◦ Three instances of resource type R 4
• Thread states:
◦ Thread T 1 is holding an instance of resource type R 2 and is waiting for an instance of resource type R 1.
◦ Thread T 2 is holding an instance of R 1 and an instance of R 2 and is waiting for an instance of R 3.
◦ Thread T 3 is holding an instance of R 3.
Given the definition of a resource-allocation graph, it can be shown that, if the graph contains no cycles, then no thread in the system is deadlocked. If the graph does contain a cycle, then a deadlock may exist.
If each resource type has exactly one instance, then a cycle implies that a deadlock has occurred. If the cycle involves only a set of resource types, each of which has only a single instance, then a deadlock has occurred. Each thread involved in the cycle is deadlocked. In this case, a cycle in the graph is both a necessary and a sufficient condition for the existence of deadlock.
If each resource type has several instances, then a cycle does not necessarily imply that a deadlock has occurred. In this case, a cycle in the graph is a necessary but not a sufficient condition for the existence of deadlock.
To illustrate this concept, we return to the resource-allocation graph depicted in Figure 8.4. Suppose that thread T 3 requests an instance of resource type R 2. Since no resource instance is currently available, we add a request
edge T 3 → R 2 to the graph (Figure 8.5). At this point, two minimal cycles exist in the system:
T 1 → R 1 → T 2 → R 3 → T 3 → R 2 → T 1 T 2 → R 3 → T 3 → R 2 → T 2
Threads T 1, T 2, and T 3 are deadlocked. Thread T 2 is waiting for the resource R 3, which is held by thread T 3. Thread T 3 is waiting for either thread T 1 or thread T 2 to release resource R 2. In addition, thread T 1 is waiting for thread T 2 to release resource R 1.
Now consider the resource-allocation graph in Figure 8.6. In this example, we also have a cycle:
However, there is no deadlock. Observe that thread T 4 may release its instance of resource type R 2. That resource can then be allocated to T 3, breaking the cycle.
In summary, if a resource-allocation graph does not have a cycle, then the system is not in a deadlocked state. If there is a cycle, then the system may or may not be in a deadlocked state. This observation is important when we deal with the deadlock problem.