Preventing deadlocks by design

Eight threads in the program below made 800,000 transfers between 16 accounts, each transfer holding two account locks at once, and none of them ever deadlocked. No lucky timing made that safe: every thread took the lock of the lower-numbered account first, so the circular wait that a deadlock needs could never form.

That is deadlock preventiondeadlock prevention: Designing a system so that one of the four Coffman conditions can never hold, which makes deadlock impossible whatever the timing.. Every deadlock needs all four Coffman conditions, so a design that makes any one of them impossible can never deadlock, whatever the timing. Each condition can be broken, and each costs something different: locks held before they are needed, work thrown away and redone, or a rule that every line of the program must follow.

One broken condition is enough, and each has a price

Each Coffman condition has its own cure. Sharing the resource removes mutual exclusion: read-only data, or one owner thread that serves every request, leaves nobody waiting for it. Taking every lock up front removes hold and wait: a thread asks for all its locks in one step and holds nothing while it waits. Try-locktry-lock: A lock call that returns at once and says whether it got the lock, instead of waiting for it; pthread_mutex_trylock and Go's Mutex.TryLock are examples. with back-off breaks no preemption: a thread that cannot get its next lock gives back what it holds and tries again later. One global lock orderlock ordering: Preventing deadlock by giving every lock a rank and making every thread take the locks it holds together in increasing rank, so that no chain of waits can close into a cycle. removes circular wait: every thread takes its locks in increasing order, so no chain of waits can close.

Dijkstra’s five dining philosophers show the deadlock and one of these cures. When every philosopher picks up the left fork first, all five can hold one fork and wait for the other, the deadly embrace. Taking both forks in one indivisible step removes hold and wait, and Dijkstra set even that aside because a philosopher could then starve. Answer the questions below for a resource of your own:

A global lock order makes the cycle impossible

Number every lock, and let each thread take locks only in increasing number. A thread that holds lock i can then wait only for a lock numbered above i. Follow any chain of waiting threads and the numbers keep rising, so the chain can never return to its start: there is no cycle, and so no deadlock. In ordered_locks.c the number is the account number, and the thread locks the two accounts of a transfer from the lower to the higher:

// Eight threads move money between 16 accounts. Every transfer locks its two
// accounts in one global order, the lower account number first, so no cycle of
// waiting threads can ever form.
#include <inttypes.h>
#include <pthread.h>
#include <stdint.h>
#include <stdio.h>

enum { ACCOUNTS = 16, THREADS = 8, TRANSFERS = 100000 };

static struct {
  pthread_mutex_t lock;
  int64_t balance;
} accounts[ACCOUNTS];

typedef struct {
  uint64_t seed;
  long downwards; // transfers to a lower account number
} worker;

// SplitMix64: the same pseudo-random numbers on every machine.
static uint64_t next_random(uint64_t *state) {
  uint64_t z = (*state += 0x9e3779b97f4a7c15u);
  z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9u;
  z = (z ^ (z >> 27)) * 0x94d049bb133111ebu;
  return z ^ (z >> 31);
}

static void transfer(int from, int to, int64_t amount) {
  const int first = from < to ? from : to; // the global order
  const int second = from < to ? to : from;
  pthread_mutex_lock(&accounts[first].lock);
  pthread_mutex_lock(&accounts[second].lock);
  accounts[from].balance -= amount;
  accounts[to].balance += amount;
  pthread_mutex_unlock(&accounts[second].lock);
  pthread_mutex_unlock(&accounts[first].lock);
}

static void *run(void *arg) {
  worker *w = arg;
  for (int i = 0; i < TRANSFERS; i++) {
    const int from = (int)(next_random(&w->seed) % ACCOUNTS);
    int to = (int)(next_random(&w->seed) % (ACCOUNTS - 1));
    if (to >= from)
      to++; // any account but the source
    const int64_t amount = (int64_t)(next_random(&w->seed) % 100) + 1;
    transfer(from, to, amount);
    w->downwards += to < from;
  }
  return NULL;
}

static int64_t total(void) {
  int64_t sum = 0;
  for (int i = 0; i < ACCOUNTS; i++)
    sum += accounts[i].balance;
  return sum;
}

int main(void) {
  for (int i = 0; i < ACCOUNTS; i++) {
    pthread_mutex_init(&accounts[i].lock, NULL);
    accounts[i].balance = 1000000;
  }
  const int64_t before = total();
  pthread_t threads[THREADS];
  worker workers[THREADS];
  for (int i = 0; i < THREADS; i++) {
    workers[i] = (worker){.seed = (uint64_t)i + 1, .downwards = 0};
    pthread_create(&threads[i], NULL, run, &workers[i]);
  }
  long downwards = 0;
  for (int i = 0; i < THREADS; i++) {
    pthread_join(threads[i], NULL);
    downwards += workers[i].downwards;
  }
  printf("%d threads made %d transfers between %d accounts\n", THREADS,
         THREADS * TRANSFERS, ACCOUNTS);
  printf("%ld moved money to a lower account number, so the thread locked the "
         "destination first\n",
         downwards);
  printf("total before %" PRId64 ", total after %" PRId64 "\n", before,
         total());
  return 0;
}

8 threads made 800000 transfers between 16 accounts
399757 moved money to a lower account number, so the thread locked the destination first
total before 16000000, total after 16000000

All 800,000 transfers finished and the 16 accounts still held 16,000,000 between them. In 399,757 transfers the money moved to a lower-numbered account, so the thread locked the destination before the source: the order follows the numbers, never the direction of the money. Step through the two transfers of the previous lesson under the same rule:

Real programs name the order in a few ways. Ranks give every class of lock a fixed number. A lock hierarchylock hierarchy: A lock order by levels: locks are grouped into numbered levels, and a thread that holds a lock of one level may take only locks of higher levels. groups locks into levels and lets a thread holding one level take only higher ones. Locks created at run time, such as one per account, are ordered by an id or an address. A lock-order checker records which lock each path takes inside which, and reports any two locks taken in both orders.

Enough units leave no room for deadlock

Some resources come in identical units, such as tape drives or connections in a pool. If n processes each need at most k units, n(k − 1) + 1 units rule out deadlock: even when each process holds k − 1 and waits for its last, one unit is left, so some process finishes and returns its units. Step through the worst moment for four processes that each need up to 3 drives, with 4 × 2 + 1 = 9 drives in the pool:

With every process one drive short, 8 drives were taken and the ninth let P1 finish, which freed 3 for the others. A process that needs a single unit never holds one while it waits, so it adds nothing to the count: any number of them can share one drive without deadlock.

Practise: the fewest units for any maximums

Write the bound for processes whose maximums differ, including processes that need one unit or none. The sample tests run in your browser.

def min_units(maxes):
    """Returns the fewest units of one resource with which these processes can never deadlock.

    maxes[i] is the most units process i ever holds at once; it asks for them one at a time.
    """
    # Replace this line with your code.
    return len(maxes) * (max(maxes, default=0) - 1) + 1

from units import min_units


def test_identical_processes():
    """four processes that each need up to 3 units: 4 x 2 + 1"""
    assert min_units([3, 3, 3, 3]) == 9


def test_different_maximums():
    """processes with maximums 2, 3 and 4"""
    assert min_units([2, 3, 4]) == 7


def test_one_unit_each():
    """a process that needs one unit never holds one while it waits"""
    assert min_units([1, 1, 1]) == 1


def test_one_process():
    """a single process only needs its own maximum"""
    assert min_units([5]) == 5


def test_a_process_that_needs_nothing():
    """a process with a maximum of 0 never asks for a unit"""
    assert min_units([0, 4]) == 4


def test_no_processes():
    """with no process, no unit is needed"""
    assert min_units([]) == 0

The resource bound, proved and checked against every allocation Pro: opens with a Pro, Premium or Ultimate pass

Lock order in real code: ranks, addresses, hierarchies and a checker Pro: opens with a Pro, Premium or Ultimate pass

Try-lock with back-off and all-at-once requests, measured Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

The warm-up comes with its full answer:

Three harder questions follow from this lesson: transfers between accounts created at run time, the units a pool needs and a fix that burns processor time. Choose a first move for two of them:

Key takeaways

• One Coffman condition made impossible is enough to prevent deadlock, and each of the four costs something different.
• A global lock order costs nothing at run time: every chain of waits climbs, so it cannot close.
• n processes needing at most k units each cannot deadlock with n(k − 1) + 1 units.