Deadlock detection and recovery

Why it exists

Prevention and avoidance cost something: prevention restricts how processes may ask for resources, and the Banker's algorithm needs every process to declare its maximum need in advance and is slow. Many systems choose a third way: let deadlocks happen, notice them, and recover. That needs two things: an algorithm that detects a deadlock (and says which processes are in it) and a policy that recovers (which processes to abort, or which resources to take away). GATE asks for the cycle in a wait-for graph, for the result of the detection algorithm on matrices, for which processes are deadlocked, and for the difference from the Banker's safety test.

Prerequisites

You need the four conditions of a deadlock, the resource allocation graph, and the safety algorithm of the Banker's page, which the detection algorithm closely resembles.

Precise definitions

The four ways to treat deadlocks. Prevention (make one of the four conditions impossible), avoidance (grant only requests that keep the state safe), detection and recovery (allow deadlock, find it, break it), and ignoring it (leave it to the user; this is what UNIX and Windows do for most resources, because deadlocks are rare and the other methods are expensive).

Single instance of each resource: the wait-for graph. Take the resource allocation graph and remove the resource nodes: draw an edge $P_i \to P_j$ if $P_i$ is waiting for a resource that $P_j$ holds. With one instance per resource,

$\text{deadlock} \iff \text{the wait-for graph has a cycle}.$

Finding a cycle by a depth-first search takes time proportional to the number of edges, at most $n^2$ for $n$ processes; the system must also keep the graph up to date as processes ask and release.

Several instances: the detection algorithm. The data structures have the same shape as the Banker's, but Max is replaced by what the processes are asking for now:

• Available (a vector of $m$ numbers), Allocation ($n \times m$), and Request ($n \times m$): Request[i][j] is the number of instances of resource $j$ that process $i$ is currently waiting for.

The algorithm:

1. Work = Available. For every process, Finish[i] = false if it holds anything (Allocation[i] is not all zero), and true if it holds nothing (such a process cannot be holding anybody up).
2. Find an i with Finish[i] = false and Request[i] <= Work (componentwise). If there is none, go to step 4.
3. Assume process $i$ gets what it asks for, runs to the end and returns what it holds: Work = Work + Allocation[i], Finish[i] = true. Go to step 2.
4. If every Finish[i] is true, there is no deadlock. Otherwise every process with Finish[i] = false is deadlocked.

It takes of the order of $m \cdot n^2$ operations (at most $n$ passes, each testing at most $n$ processes against $m$ numbers). The algorithm is optimistic: it assumes that a process that is not waiting will not ask for more. If it does, the next run of the algorithm will see it. The set of deadlocked processes does not depend on which eligible process is picked first, but the order in which processes can finish usually does.

Detection against the Banker's safety test. They are the same loop, with a different matrix compared with Work:

A deadlocked state is always unsafe; an unsafe state need not be deadlocked.

Processes that wait behind a deadlock. A process that is not on a cycle but waits for a resource held by a deadlocked process can never finish either. The algorithm leaves it unfinished and lists it with the deadlocked processes.

When to run detection. After every request that cannot be granted at once (finds the deadlock at the moment it forms and names the process whose request closed the cycle, but costs a lot); at fixed intervals; or when something suggests trouble, for example when CPU utilisation falls below a threshold. The more rarely it runs, the more processes are stuck by the time it finds them, and with many cycles in the graph it is hard to tell which process "caused" the deadlock.

Recovery 1: terminate processes.

• Abort all deadlocked processes. Certain to break the deadlock, expensive: all their computation is lost.
• Abort one at a time until the deadlock is gone, running the detection algorithm after each abort: less is lost, but more detection work.

Choosing the victim: the priority of the process; how long it has run and how long it still needs; the resources it holds and how many more it needs; how many processes would have to be terminated; whether it is interactive or batch; whether it is in the middle of an update that leaves a file inconsistent.

Recovery 2: preempt resources. Take resources away from one process and give them to another until the cycle is broken. Three issues: selecting a victim (minimise cost, as above); rollback (the victim cannot continue as if nothing happened: roll it back to a safe state or to its start and restart it); and starvation (the same process may be picked every time: include the number of rollbacks in the cost so that it is not).

How it works

A resource allocation graph with five processes and five resources of one instance each. Step through the requests: two cycles form, one through P1, P2 and P3 and one between P4 and P5, and P2 is also waiting for a resource held by P4. Then two victims are aborted, one from each cycle.

The wait-for graph of the final state: for each waited-for resource, the process that holds it.

Which processes to abort? Every process alone fails (each cycle needs a victim); every smallest sufficient set has one process from each cycle; with the costs shown, aborting P3 and P5 is the cheapest. The table was filled by aborting the processes in the graph and running the deadlock test again.

The detection algorithm on matrices: five processes, three resource types with totals $(9, 4, 6)$. First a state without a deadlock. The scan starts at P0, which asks for more than is free, so P1 goes first.

Then a state in which P0 and P4 each hold one B and each wait for three more:

The same allocation seen by the Banker's safety test and by detection:

Worked examples

#include <stdio.h>
 
#define N 5
#define M 3
 
static const int alloc[N][M] = {{1, 1, 0}, {3, 0, 2}, {2, 1, 1}, {1, 0, 2}, {1, 1, 0}};
static const int avail[M] = {1, 1, 1};
 
static void detect(const char *title, const int req[N][M]) {
    int work[M], finish[N], order[N], k = 0;
    for (int j = 0; j < M; j++) work[j] = avail[j];
    for (int i = 0; i < N; i++) finish[i] = (alloc[i][0] == 0 && alloc[i][1] == 0 && alloc[i][2] == 0);
    int moved = 1;
    while (moved) {
        moved = 0;
        for (int i = 0; i < N && !moved; i++) {
            if (finish[i]) continue;
            int fits = 1;
            for (int j = 0; j < M; j++)
                if (req[i][j] > work[j]) fits = 0;
            if (fits) {
                for (int j = 0; j < M; j++) work[j] += alloc[i][j];
                finish[i] = 1;
                order[k++] = i;
                moved = 1;
            }
        }
    }
    printf("%s\n  finish order:", title);
    for (int i = 0; i < k; i++) printf(" P%d", order[i]);
    printf("\n  deadlocked:");
    int any = 0;
    for (int i = 0; i < N; i++)
        if (!finish[i]) { printf(" P%d", i); any = 1; }
    printf("%s\n  final Work = (%d, %d, %d)\n", any ? "" : " none", work[0], work[1], work[2]);
}
 
int main(void) {
    const int ok[N][M] = {{2, 1, 1}, {0, 1, 0}, {0, 0, 0}, {1, 0, 1}, {2, 0, 1}};
    const int dl[N][M] = {{0, 3, 0}, {0, 1, 0}, {0, 0, 0}, {1, 0, 1}, {0, 3, 0}};
    detect("first example", ok);
    detect("second example", dl);
    return 0;
}

first example
  finish order: P1 P0 P2 P3 P4
  deadlocked: none
  final Work = (9, 4, 6)
second example
  finish order: P1 P2 P3
  deadlocked: P0 P4
  final Work = (7, 2, 6)

#include <stdio.h>
 
#define N 5
 
/* wait-for edges: P1 -> P2, P2 -> P3, P2 -> P4, P3 -> P1, P4 -> P5, P5 -> P4  (bit i is process P(i+1)) */
static const int edge[N][N] = {{0, 1, 0, 0, 0}, {0, 0, 1, 1, 0}, {1, 0, 0, 0, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 1, 0}};
static const int cost[N] = {3, 5, 2, 4, 1};
 
/* the graph induced by the processes that are NOT victims has no cycle iff repeatedly deleting a node without outgoing edges deletes them all */
static int acyclic_without(int victims) {
    int alive = ((1 << N) - 1) & ~victims, changed = 1;
    while (changed) {
        changed = 0;
        for (int i = 0; i < N; i++) {
            if (!(alive & (1 << i))) continue;
            int out = 0;
            for (int j = 0; j < N; j++)
                if ((alive & (1 << j)) && edge[i][j]) out = 1;
            if (!out) { alive &= ~(1 << i); changed = 1; }
        }
    }
    return alive == 0;
}
 
static int popcount(int x) { int c = 0; while (x) { c += x & 1; x >>= 1; } return c; }
 
int main(void) {
    int minimal[64], nmin = 0;
    for (int size = 1; size <= N; size++)
        for (int m = 1; m < (1 << N); m++) {
            if (popcount(m) != size || !acyclic_without(m)) continue;
            int proper = 0;
            for (int k = 0; k < nmin; k++)
                if ((minimal[k] & m) == minimal[k]) proper = 1;
            if (!proper) minimal[nmin++] = m;
        }
    int best = -1, bestcost = 1000;
    for (int k = 0; k < nmin; k++) {
        int c = 0;
        printf("abort");
        for (int i = 0; i < N; i++)
            if (minimal[k] & (1 << i)) { printf(" P%d", i + 1); c += cost[i]; }
        printf(": cost %d\n", c);
        if (c < bestcost) { bestcost = c; best = k; }
    }
    printf("single victims that work:");
    int any = 0;
    for (int i = 0; i < N; i++)
        if (acyclic_without(1 << i)) { printf(" P%d", i + 1); any = 1; }
    printf("%s\ncheapest: mask %d, cost %d\n", any ? "" : " none", minimal[best], bestcost);
    return 0;
}

abort P1 P4: cost 7
abort P2 P4: cost 9
abort P3 P4: cost 6
abort P1 P5: cost 4
abort P2 P5: cost 6
abort P3 P5: cost 3
single victims that work: none
cheapest: mask 20, cost 3

Cheat box

Traps and GATE patterns

Connections

Detection resembles the safety algorithm of the Banker's page and works on the same kind of graph as resource allocation graphs. Terminating a victim is the process termination of the process lifecycle. The same idea appears in databases: a lock manager keeps a wait-for graph of transactions, finds the cycle and aborts a victim, as in two-phase locking.

PYQs

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?

Consider a system with 4 types of resources R1 (3
units), R2 (2 units), R3 (3 units), R4 (2 units). A non-
preemptive resource allocation policy is used. At any
given instance, a request is not entertained if it cannot
be completely satisfied. Three processes P1, P2, P3
request the resources as follows if executed
independently.
Process P1:
t= 0 : requests
2 units of
R2
t= 1 : requests
1 unit of
R3
t= 3 : requests
2 units of
R1
t= 5 : releases
1 unit of
R2 and 1
unit
of
R1
t= 7 : releases
1 unit of
R3
t= 8 : requests
2 units of
R4
t= 10
:
Finishes
Process P2:
t= 0 : requests
2 units of
R3
t= 2 : requests
1 unit of
R4
t= 4 : requests
1 unit of
R1
t= 6 : releases
1 unit of
R3
t= 8 : Finishes
Process P3:
t= 0 : requests
1 unit of
R4
t= 2 : requests
2 units of
R1
t= 5 : releases
2 units of
R1
t= 7 : requests
1 unit of
R2
t= 8 : requests
1 unit of
R3
t= 9
:
Finishes

Which one of the following statements is TRUE if all
three processes run concurrently starting at time t = 0
?

OPERATING SYSTEMS

A single processor system has three resource types
X, Y, and Z, which are shared by three processes.
There are 5 units of each resource type.

The column alloc denotes the number of units of
each resource type allocated to each process, and
the column request denotes the number of units of
each resource type requested by a process in order
to complete execution.

Which of these processes will finish LAST?

alloc (X Y Z)
request (X Y Z)
P0
1 2 1
1 0 3
P1
2 0 1
0 1 2
P2
2 2 1
1 2 0

Self-check

Revision card

References