Deadlock: conditions and resource allocation graphs

Why it exists

Processes compete for resources: printers, files, locks, memory buffers, semaphores. A process requests a resource, uses it and releases it. If the resource is not free, the process waits. Waiting is normal; but waiting can become permanent. Two processes each hold something the other needs and each waits for the other: neither can ever continue. This is deadlock. It is not about slow processes; it is a state from which, without outside intervention, no process in the group can ever proceed. GATE asks you to identify the conditions that make it possible, to read deadlocks from resource allocation graphs, to tell which strategy breaks which condition, and to compute the minimum number of resource units for which deadlock cannot occur.

Prerequisites

You need the process and its waiting state from the process model; semaphores and locks are the usual resources, as in semaphores and the classic problems.

Precise definitions

Resource. Anything a process must hold exclusively for a while: a device, a file, a lock, a semaphore, a memory region. A resource type may have several identical instances (for example 3 printers). A process uses a resource in three steps: request (wait if no instance is free), use, release.

Deadlock. A set of processes is deadlocked if every process in the set is waiting for an event (here, the release of a resource) that only another process in the set can cause. None can proceed, so none will ever release anything.

The four necessary conditions (Coffman conditions). A deadlock can occur only if all four hold at the same time:

1. Mutual exclusion: at least one resource is held in a non-sharable mode (only one process at a time can use it).
2. Hold and wait: a process holds at least one resource while waiting to acquire additional resources held by others.
3. No preemption: a resource can be released only voluntarily by the process holding it; it cannot be taken away.
4. Circular wait: there is a set of waiting processes $P_0, P_1, \ldots, P_{k}$ such that $P_0$ waits for a resource held by $P_1$, $P_1$ for one held by $P_2$, ..., and $P_k$ for one held by $P_0$.

The four conditions are necessary. Together they are not always sufficient (see the graph with several instances below).

Resource allocation graph (RAG). A directed graph with a node for each process (drawn as a circle) and each resource type (a box with one dot per instance).

• A request edge $P_i \to R_j$: process $P_i$ has requested an instance of $R_j$ and is waiting.
• An assignment edge $R_j \to P_i$: an instance of $R_j$ is held by $P_i$.

Facts, for a graph in which no process requests more instances than exist:

• If the graph has no cycle, there is no deadlock.
• If every resource type has one instance, then a cycle means deadlock (and deadlock means a cycle).
• If some resource types have several instances, a cycle is necessary but not sufficient: there may be a cycle and no deadlock (when an instance in the cycle is held by a process that is not waiting and will release it). The deadlock test is then the reduction algorithm: repeatedly find a process whose outstanding requests can all be satisfied by the free instances, let it finish and release all it holds; the processes that can never finish are the deadlocked ones.

Four ways to handle deadlock.

1. Ignore it (the "ostrich algorithm"): assume it is rare and let the operator reboot. Used by most general-purpose systems for most resources.
2. Prevention: make sure at least one of the four conditions can never hold.
3. Avoidance: let the system decide at each request whether granting it could lead to deadlock, using advance information about the maximum needs (Banker's algorithm).
4. Detection and recovery: allow deadlocks, detect them (cycle search or the reduction algorithm) and recover by terminating processes or preempting resources (detection and recovery).

Prevention, condition by condition.

Why ordering works: a cycle $P_0 \to R_a \to P_1 \to R_b \to \cdots$ would require, going round it, a resource number that is both greater than and less than itself, which is impossible.

Deadlock is not starvation. In starvation one process waits indefinitely but the system as a whole progresses (for example SJF). In deadlock every process in the set is blocked. In livelock the processes keep running and changing state but make no progress.

Resources needed so that deadlock cannot happen. Suppose $n$ processes share $R$ identical units of one resource type, process $i$ needs at most $m_i$ units in all, requests one unit at a time, and holds everything until it has all its units. Deadlock is impossible if and only if

$R \ge \sum_{i=1}^{n} (m_i - 1) + 1.$

(If $R$ is smaller, every process can be holding one unit fewer than its maximum, using up all units, and all wait.) When every process needs $k$ units: $R \ge n(k - 1) + 1$.

How it works

The animations are resource allocation graphs built event by event; the cycle and the deadlock are computed by script at each step. First the standard deadlock: two processes, two single-instance resources, requested in opposite orders. The last request closes the cycle and, since each resource has one instance, it is a deadlock.

Now a cycle that is not a deadlock. R1 has two instances. After the last request the graph has a cycle through P1, R1, P3 and R2, but R1's other instance is held by P2, which is not waiting for anything. When P2 finishes it releases R1, P1 gets it, and the cycle disappears.

And prevention by ordering: both processes request R1 before R2. Whoever gets R1 first can go on to take R2 and finish; the other simply waits. No cycle can ever form.

Worked examples

#include <stdio.h>
#include <string.h>
 
/* n processes, each needing up to k units of one resource type, asking for one unit at a time and releasing everything when it holds k.
   For R units in all, explore EVERY reachable state and report whether a deadlock (unfinished processes, none able to proceed) is reachable. */
static int n, k, R;
static unsigned char seen[8192];
 
static int encode(const int *held, int freeu) {
    int code = 0;
    for (int i = 0; i < n; i++) code = code * (k + 1) + held[i];
    return code * 64 + freeu;
}
 
static int deadlock_reachable(const int *held, int freeu) {
    int code = encode(held, freeu);
    if (seen[code]) return 0;
    seen[code] = 1;
    int moved = 0, unfinished = 0;
    for (int i = 0; i < n; i++) {
        if (held[i] == k) continue;                    /* finished: its units were returned when it reached k */
        unfinished = 1;
        if (freeu == 0) continue;
        moved = 1;
        int next[8], f = freeu - 1;
        memcpy(next, held, sizeof(int) * (size_t)n);
        next[i]++;
        if (next[i] == k) f += k;                      /* it now holds all it needs, finishes and releases */
        if (deadlock_reachable(next, f)) return 1;
    }
    return unfinished && !moved;
}
 
int main(void) {
    for (n = 1; n <= 4; n++) {
        for (k = 1; k <= 3; k++) {
            int found = -1;
            for (R = 1; R <= n * k + 1 && found < 0; R++) {
                int held[8] = {0};
                memset(seen, 0, sizeof seen);
                if (!deadlock_reachable(held, R)) found = R;
            }
            printf("%d processes, each needs up to %d units: deadlock is impossible from %2d units up; formula n(k-1)+1 = %2d\n", n, k, found, n * (k - 1) + 1);
        }
    }
    return 0;
}

1 processes, each needs up to 1 units: deadlock is impossible from  1 units up; formula n(k-1)+1 =  1
1 processes, each needs up to 2 units: deadlock is impossible from  2 units up; formula n(k-1)+1 =  2
1 processes, each needs up to 3 units: deadlock is impossible from  3 units up; formula n(k-1)+1 =  3
2 processes, each needs up to 1 units: deadlock is impossible from  1 units up; formula n(k-1)+1 =  1
2 processes, each needs up to 2 units: deadlock is impossible from  3 units up; formula n(k-1)+1 =  3
2 processes, each needs up to 3 units: deadlock is impossible from  5 units up; formula n(k-1)+1 =  5
3 processes, each needs up to 1 units: deadlock is impossible from  1 units up; formula n(k-1)+1 =  1
3 processes, each needs up to 2 units: deadlock is impossible from  4 units up; formula n(k-1)+1 =  4
3 processes, each needs up to 3 units: deadlock is impossible from  7 units up; formula n(k-1)+1 =  7
4 processes, each needs up to 1 units: deadlock is impossible from  1 units up; formula n(k-1)+1 =  1
4 processes, each needs up to 2 units: deadlock is impossible from  5 units up; formula n(k-1)+1 =  5
4 processes, each needs up to 3 units: deadlock is impossible from  9 units up; formula n(k-1)+1 =  9

Cheat box

Traps and GATE patterns

Connections

The resources are often semaphores: two processes waiting on two semaphores in opposite orders are exactly the cycle above, and the dining philosophers are a circular wait. Granting a request only when it keeps the system safe is deadlock avoidance; finding deadlocks after the fact and recovering is detection and recovery.

PYQs

Consider a computer system with multiple shared
resource types, with one instance per resource type.
Each instance can be owned by only one process at
a time. Owning and freeing of resources are done
by holding a global lock (L). The following scheme
is used to own a resource instance:

function OWNRESOURCE(Resource R)

Acquire lock L // a global lock

if R is available then

Acquire R

Release lock L

else

if R is owned by another process P then
           Terminate P, after releasing all resources
owned by P

Acquire R

Restart P

Release lock L

end if
         end if

end if

end function

Which of the following choice(s) about the above
scheme is/are correct?

With respect to deadlocks in an operating system,
which of the following statements is/are FALSE?

P = {P1, P2, P3, P4} consists of all active processes
in an operating system. R = {R1, R2, R3, R4} consists
of single instances of distinct types of resources in the
system.

The resource allocation graph has the following
assignment and claim edges.

Assignment edges: R1 → P1, R2 → P2, R3 → P3, R4
→ P4 (the assignment edge R1 → P1 means resource
R1 is assigned to process P1 , and so on for others)

Claim edges: P1 → R2, P2 → R3, P3 → R1, P2 →
R4, P4 → R2 (the claim edge P1 → R2 means process
P1 is waiting for resource R2 , and so on for others)

Which
of
the
following
statement(s)
is/are
CORRECT?

Which of the following statements is/are TRUE with
respect to deadlocks?

A multithreaded program P executes with x number
of threads and used y number of locks for ensuring
mutual exclusion while operating on shared memory
locations. All locks in the program are non-reentrant,
i.e., if a thread holds a lock l, then it cannot re-acquire
lock l without releasing it. If a thread is unable to
acquire a lock, it blocks until the lock becomes
available. The minimum value of x and the minimum
value of y together for which execution of P can result
in a deadlock are:

Consider the following policies for preventing
deadlock in a system with mutually exclusive
resources.

I. Processes should acquire all their resources at the
beginning of execution.  If any resource is not
available, all resources acquired so far are released.

II. The resources are numbered uniquely, and
processes are allowed to request for resources only
in increasing resource numbers.

III. The resources are numbered uniquely, and
processes are allowed to request for resources only in
decreasing resource numbers.

IV. The resources are numbered uniquely. A process
is allowed to request only for a resource with resource
number larger than its currently held resources.

Which of the above policies can be used for
preventing deadlock?

Three concurrent processes X, Y, and Z execute
three different code segments that access and
update certain shared variables. Process X executes
the P operation (i.e., wait) on semaphores a, b, and
c; process Y executes the P operation on
semaphores b, c, and d; process Z executes the P
operation on semaphores c, d, and a before entering
the respective code segments. After completing the
execution of its code segment, each process
invokes the V operation (i.e., signal) on its three
semaphores.
All
semaphores
are
binary
semaphores initialized to one. Which one of the
following represents a deadlock-free order of
invoking the P operations by the processes?

A system has n resources R0...,Rn-1, and k processes
P0....Pk-1. The implementation of the resource
request logic of each process Pi is as follows:

if (i % 2 == 0) {

if (i < n) request Ri

if (i+2 < n) request Ri+2

}

else {

if (i < n) request Rn-i

if (i+2 < n) request Rn-i-2

}
 In which one of the following situations is a deadlock
possible?

Which of the following is NOT true of deadlock
prevention and deadlock avoidance schemes?

Self-check

Revision card

References