Deadlock

A deadlock is a set of processes in which each one waits for a resource that another one in the set holds. Nobody can go on, so they all wait forever.

Thread A holds the printer and waits for the scanner; thread B holds the scanner and waits for the printer. Neither will ever let go.

The four conditions

A deadlock can happen only if all four hold at once (Coffman's conditions):

1. Mutual exclusion: a resource can be used by only one process at a time.
2. Hold and wait: a process holds some resources while it waits for more.
3. No preemption: a resource cannot be taken away; only its holder can release it.
4. Circular wait: there is a cycle P0 waits for P1, P1 waits for P2, ..., Pn waits for P0.

Resource-allocation graphs

Draw processes as circles and resources as squares. An arrow P → R means P requests R; an arrow R → P means R is assigned to P.

   P1 ──→ [Printer] ──→ P2
    ↑                    │
    └──── [Scanner] ←────┘

With one copy of each resource, a cycle means deadlock. With several copies, a cycle means deadlock is possible, not certain.

Four ways to handle deadlock

The banker's algorithm

A state is safe if there is some order (a safe sequence) in which every process can get its maximum and finish. The algorithm needs, for n processes and m resource types:

• Available: free copies of each resource.
• Max: the most each process may ever ask for.
• Allocation: what each process holds now.
• Need = Max − Allocation: what each may still ask for.

The safety check: start with Work = Available. Find an unfinished process whose Need fits in Work; pretend it runs to the end and gives back its allocation (Work += Allocation); mark it finished; repeat. If every process finishes, the state is safe.

These are the numbers of the standard textbook example. Step through the checks: P1 fits first, then P3, P4, P0 and P2. Open A process asks for more to test the request algorithm: grant a request only if, after pretending to grant it, the state is still safe.

#include <stdio.h>

#define P 5   /* processes */
#define R 3   /* resource types */

int main(void) {
    int alloc[P][R] = {{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};
    int max[P][R]   = {{7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}};
    int work[R]     = {3, 3, 2};   /* starts as Available */
    int need[P][R], finished[P] = {0};
    int sequence[P], count = 0;

    for (int i = 0; i < P; i++)
        for (int r = 0; r < R; r++) need[i][r] = max[i][r] - alloc[i][r];

    int progress = 1;
    while (progress) {             /* pass over the processes until nobody can finish */
        progress = 0;
        for (int i = 0; i < P; i++) {
            if (finished[i]) continue;
            int fits = 1;
            for (int r = 0; r < R; r++)
                if (need[i][r] > work[r]) fits = 0;
            if (fits) {            /* it can finish, and gives everything back */
                for (int r = 0; r < R; r++) work[r] += alloc[i][r];
                finished[i] = 1;
                sequence[count++] = i;
                progress = 1;
            }
        }
    }

    if (count == P) {
        printf("safe:");
        for (int k = 0; k < P; k++) printf(" P%d", sequence[k]);
        printf("\n");
    } else {
        printf("unsafe\n");
    }
    return 0;
}

The C version makes the same passes over the processes and finds the same safe sequence.

Detecting a deadlock

#include <stdio.h>

#define N 4

/* waits[i][j] = 1: process i waits for a resource that process j holds */
int waits[N][N] = {
    {0, 1, 0, 0},   /* P0 waits for P1 */
    {0, 0, 1, 0},   /* P1 waits for P2 */
    {0, 0, 0, 0},   /* P2 waits for nobody */
    {0, 0, 1, 0},   /* P3 waits for P2 */
};
int state[N];       /* 0 not seen, 1 on the current path, 2 done */

int has_cycle(int p) {
    state[p] = 1;
    for (int q = 0; q < N; q++) {
        if (!waits[p][q]) continue;
        if (state[q] == 1) return 1;            /* back to the path: a cycle */
        if (state[q] == 0 && has_cycle(q)) return 1;
    }
    state[p] = 2;
    return 0;
}

int deadlocked(void) {
    for (int p = 0; p < N; p++) state[p] = 0;
    for (int p = 0; p < N; p++)
        if (state[p] == 0 && has_cycle(p)) return 1;
    return 0;
}

int main(void) {
    printf("deadlock: %s\n", deadlocked() ? "yes" : "no");
    waits[2][0] = 1;            /* now P2 waits for P0 too */
    printf("deadlock: %s\n", deadlocked() ? "yes" : "no");
    return 0;
}

For resources with one copy each, detection is cycle-finding in the wait-for graph (an arrow Pi → Pj when Pi waits for something Pj holds). This program follows the arrows from each process with a depth-first search; finding its way back to a process on the current path means a cycle.

Mark lesson complete