What a Deadlock Is, and the System Model

A deadlock, made to happen

Two mutexes and two threads that take them in opposite orders. This is the shortest deadlock that can be written and the commonest one in real programs.

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <pthread.h>
#include <time.h>

static pthread_mutex_t first = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t second = PTHREAD_MUTEX_INITIALIZER;
static int             got_both[2];

static void pause_for(long milliseconds)
{
    struct timespec t = {milliseconds / 1000, (milliseconds % 1000) * 1000000};

    nanosleep(&t, NULL);
}

static void *takes_first_then_second(void *unused)
{
    (void)unused;
    pthread_mutex_lock(&first);
    pause_for(100);                       /* hold one, and pause: see the note */
    pthread_mutex_lock(&second);
    got_both[0] = 1;
    pthread_mutex_unlock(&second);
    pthread_mutex_unlock(&first);
    return NULL;
}

static void *takes_second_then_first(void *unused)
{
    (void)unused;
    pthread_mutex_lock(&second);          /* the OTHER order */
    pause_for(100);
    pthread_mutex_lock(&first);
    got_both[1] = 1;
    pthread_mutex_unlock(&first);
    pthread_mutex_unlock(&second);
    return NULL;
}

int main(void)
{
    pthread_t a, b;

    pthread_create(&a, NULL, takes_first_then_second, NULL);
    pthread_create(&b, NULL, takes_second_then_first, NULL);
    pause_for(1000);                      /* a whole second is plenty */

    printf("thread A got both locks: %s\n", got_both[0] ? "yes" : "no");
    printf("thread B got both locks: %s\n", got_both[1] ? "yes" : "no");
    printf("%s\n", (!got_both[0] && !got_both[1])
        ? "neither of them ever will: this is a DEADLOCK"
        : "they got through");
    return 0;                             /* leave them holding their locks */
}

$ gcc -std=c17 -Wall -Wextra -pthread -o deadlock2 deadlock2.c
$ ./deadlock2
thread A got both locks: no
thread B got both locks: no
neither of them ever will: this is a DEADLOCK
$ bad=$(for i in 1 2 3; do ./deadlock2 | tail -1; done | grep -c DEADLOCK)
$ echo "three runs, $bad of them deadlocked"
three runs, 3 of them deadlocked

Read the program against the definition. Thread A holds first and waits for second. Thread B holds second and waits for first. Each is waiting for an event, the release of a mutex, that only the other one in the set can cause, and the other one is waiting too. Every clause of the definition is satisfied, and the program will sit there for ever.

The hundred millisecond pause is there for the same reason as Chapter forty one's: it makes the bad interleaving certain rather than occasional. Take it out and the deadlock happens sometimes, which in a real program means it happens in production and not in testing.

Notice what the operating system did about it: nothing. It does not know the two threads are stuck. It sees two threads waiting on two locks, which is an entirely normal thing for threads to do. Chapters sixty four and sixty five are about a system that does look.

Four kinds of waiting, told apart

This table is the reason the definitions of this module matter, and a question will ask for the differences.

Starvation and deadlock are the pair most often confused. A starved process could run: give it the processor and it proceeds. A deadlocked process cannot: give it the processor and it goes straight back to waiting for something that will never arrive.

A livelock is the one students have not usually heard of and examiners like. The processes are not blocked at all: they are running, and their state keeps changing, and no work gets done. Two people stepping aside in a corridor, each way, for ever.

Worked example: a bank transfer

The commonest real deadlock in commercial code, and the one worth recognising.

A transfer locks the account it takes money from and then the account it puts money into.

1. Anita transfers to Bharat. Her thread locks Anita's account, then asks for Bharat's.
2. At the same moment Bharat transfers to Anita. His thread locks Bharat's account, then asks for

Anita's.

1. Neither can proceed. Two customers, two accounts, no money moved, and the bank's software

stops.

It is the same program as the one above with the locks renamed, and the fix is the same as Chapter forty one's third fix: lock the accounts in a fixed order, for example by account number, whichever way the money is going. That is Chapter sixty of this module, and it costs nothing.

What it does not mean

A deadlock is not a crash. Nothing has failed and nothing will be reported. The processes are perfectly healthy and waiting politely.

A deadlock is not a performance problem. It does not get better under a lighter load.

Two processes waiting on one resource are not deadlocked. One of them has it and will release it. A deadlock needs a cycle of waiting.

Deadlock is not confined to locks. Memory, files, devices, database rows and network connections all deadlock the same way. The resource being a lock is the commonest case and not the definition.

Quick revision

• A set of processes is deadlocked when every process in the set waits for an event that only

another process in the set can cause.

• Both clauses matter: every process, and the event can come only from inside the set. So

a deadlock is permanent and nothing outside can free it.

• System model: resources come in types, each with interchangeable instances. The

cycle is request, use, release, and a deadlock happens between request and use.

• Two things are one type if any instance satisfies a request; a colour printer and a mono

printer are two types.

• Two mutexes taken in opposite orders by two threads is the shortest deadlock there is, and the

operating system does not notice it.

• Blocked ends by itself; starved could be chosen at any moment; a livelock is

running and making no progress; deadlocked never ends.

Test yourself

1. Define a deadlock. A set of processes is deadlocked when every process in the set is

waiting for an event that can be caused only by another process in the same set.

1. Why does the definition say "every process in the set"? Because if one of them could move

it would eventually release what it holds and the others would follow. A deadlock is a closed set, not one stuck process.

1. State the three steps of using a resource. Request, use, release.
2. When are two resources of the same type? When the instances are interchangeable, so that a

request for the type is satisfied by any of them. A colour printer and a black and white printer are different types.

1. Distinguish deadlock from starvation. A starved process is ready and could run the moment

it is chosen. A deadlocked process cannot run even if it is given the processor, because what it waits for will never arrive.

1. What is a livelock? Processes that are running and changing state but making no progress,

for example two that keep standing aside for each other.

1. Write the shortest deadlock you can. Two threads and two mutexes: one takes A then B, the

other takes B then A. With any pause between the two acquisitions it deadlocks every time.