Deadlock

Deadlock occurs when two or more threads are each waiting for resources held by another thread in the same waiting cycle. Once the cycle forms, the threads cannot make progress unless something external breaks the cycle.

Deadlock may not happen immediately in a program that contains the conditions for it. The bug may depend on timing, scheduling, input, or the order in which threads reach the locks.

Dining Philosophers Problem

The dining philosophers problem is a small model of resource contention. Each philosopher alternates between thinking and eating, and each needs two forks to eat.

The usual rules are:

• A philosopher can be eating or thinking.

• Philosophers do not communicate with each other.

• A philosopher needs both the left fork and the right fork before eating.

• Each fork can be held by only one philosopher at a time.

Dining Philosophers Deadlock Scenario

A deadlock can occur if every philosopher picks up one fork and then waits for the other fork.

eat() {
   pick up right fork;
   pick up left fork;
   proceed with eating;
}

One possible execution is:

• At t = 0, every philosopher picks up the fork on the right.

• At t = 1, philosopher 1 tries to pick up the left fork, but philosopher 5 holds it.

• At t = 2, philosopher 2 tries to pick up the left fork, but philosopher 1 holds it.

• The same pattern continues around the table.

Every philosopher holds one fork and waits for a fork held by another philosopher. No philosopher can finish eating and release a fork, so the program is deadlocked.

Dining Philosophers Lock Graph

A lock graph shows the possible ordering relationships among locks. If the graph contains a cycle, a deadlock is possible.

In the first dining philosophers algorithm, forks can be acquired in an order that forms a cycle.

Avoiding Deadlock with Try-and-Release

One way to avoid deadlock is to acquire both needed resources as a single logical operation. If the second resource is not available, the thread releases the first resource and tries again later.

eat() {
   while(does not have both forks) {
      pickup left fork;
      if(can pick up right fork) {
         pick up right fork;
      } else {
         put down left fork;
      }
   }
   proceed with eating;
}

This avoids the deadlock cycle because a philosopher does not continue holding one fork while waiting forever for the other fork. The tradeoff is that the implementation is more complex and can still need fairness rules to avoid starvation or livelock.

Avoiding Deadlock with Lock Ordering

Another way to avoid deadlock is to assign a global order to resources and require every thread to acquire resources in that order.

eat() {
   pick up fork with lower number;
   pick up fork with higher number;
   proceed with eating;
}

This works because a global order removes cycles from the lock graph. If all threads acquire the lower-numbered lock before the higher-numbered lock, no thread can create a circular wait.

Dijkstra’s Solution and the Banker’s Algorithm

Dijkstra’s solution to the dining philosophers problem uses resource ordering. The same basic idea appears in the Banker’s algorithm: do not enter a resource allocation state that can lead to deadlock.

The main advantage is simplicity. Lock ordering is easy to state, easy to review, and often easy to implement. A common approach is to lock mutexes in address order or in the order they appear in a table.

The main disadvantage is reduced concurrency. Some lock acquisition orders would be safe in a specific execution, but a strict global order forbids them anyway.

Deadlock Avoidance Implementation

Deadlock avoidance prevents unsafe lock acquisition by enforcing a consistent order.

typedef struct {
   int LockNumber;
   void* LockObject;
} lock;

void multi_lock(lock* locks, int count) {
   sort(locks, count);
   for(int i = 0; i < count; i++) {
      lock(locks[i]);
   }
}

The important part is not the sorting function itself. The important part is that every caller uses the same ordering rule before acquiring more than one lock.

Deadlock Prevention Implementation

Deadlock prevention can also be done by acquiring locks with a try-and-release rule. If any lock cannot be acquired, the thread releases what it already holds and tries again.

typedef struct {
   int LockNumber;
   void* LockObject;
} lock;

void multi_lock(lock* locks, int count) {
   while(1) {
      int i = 0;
      for(i = 0; i < count; i++) {
         if(!try_lock(locks[i])) {
            for(int j = 0; j < i; j++) {
               unlock(locks[j]);
            }
            break;
         }
      }
      if(i == count) {
         return;
      }
   }
}

This approach can allow more concurrency than strict ordering, but it can also be harder to reason about. Without backoff or fairness, two threads can repeatedly interfere with each other.

Dining Philosophers Example

The systems-code-examples/dining-philosophers example can run with or without resource ordering. The default mode can deadlock. The DINING_POLICY=avoid_deadlock mode reorders forks to avoid the cycle.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#include "diners.h"
#include "millisleep.h"

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define MAX_DINERS 5
#define MAX_THINK_TIME 7
#define MAX_EAT_TIME 7
#define MAIN_THREAD_SLEEP_TIME 51

typedef struct {
    int num_philosophers;
    int think_time;
    int eat_time;
    int enumerate_resources;
} Configuration;

void parseCommandLine(int argc, char **argv, Configuration *config) {
    int opt;

    while ((opt = getopt(argc, argv, "n:t:e:r")) != -1) {
        switch (opt) {
            case 'n': // Number of philosophers
                config->num_philosophers = atoi(optarg);
                if (config->num_philosophers > MAX_DINERS || config->num_philosophers < 1) {
                    fprintf(stderr, "Number of philosophers must be between 1 and %d\n", MAX_DINERS);
                    exit(EXIT_FAILURE);
                }
                break;
            case 't': // Think time
                config->think_time = atoi(optarg);
                if (config->think_time > MAX_THINK_TIME || config->think_time < 0) {
                    fprintf(stderr, "Think time must be between 0 and %d seconds\n", MAX_THINK_TIME);
                    exit(EXIT_FAILURE);
                }
                break;
            case 'e': // Eat time
                config->eat_time = atoi(optarg);
                if (config->eat_time > MAX_EAT_TIME || config->eat_time < 0) {
                    fprintf(stderr, "Eat time must be between 0 and %d seconds\n", MAX_EAT_TIME);
                    exit(EXIT_FAILURE);
                }
                break;
            case 'r': // Enumerate resources
                config->enumerate_resources = 1;
                break;
            default: /* '?' */
                fprintf(stderr, "Usage: %s [-n num_philosophers] [-t think_time] [-e eat_time] [-r]\n",
                        argv[0]);
                exit(EXIT_FAILURE);
        }
    }
}

int main(int argc, char **argv) {
    Configuration config = {
        .num_philosophers = 5,      // default number of philosophers
        .think_time = 2,            // default think time in seconds
        .eat_time = 3,              // default eat time in seconds
        .enumerate_resources = 0    // default for resource enumeration: off
    };

    parseCommandLine(argc, argv, &config);

    printf("Number of Philosophers: %d\n", config.num_philosophers);
    printf("Think Time: %d seconds\n", config.think_time);
    printf("Eat Time: %d seconds\n", config.eat_time);
    printf("Enumerate Resources: %s\n", config.enumerate_resources ? "Yes" : "No");

    fork_t fork[MAX_DINERS];
    diner_t diner[MAX_DINERS];

    /* The main thread  */
    pthread_t this_thread = pthread_self();
    struct sched_param sched_parameters;
    sched_parameters.sched_priority = sched_get_priority_max(SCHED_OTHER);
    int status = pthread_setschedparam(this_thread, SCHED_OTHER, &sched_parameters);

    // the main thread monitors the state of the diners and runs at highest
    // priority so it can continue doing something, even if (or when) the other
    // threads get deadlocked.

    if (status != 0)
    {
        fprintf(stderr, "Cannot set main thread max prioirty. Fatal.\n");
        exit(1);
    }

    /* initialize the shared resources (forks) */
    for (int i = 0; i < MAX_DINERS; i++)
        fork_init(&fork[i], i);

    /* initialize the diners to link to the shared resources (forks) */
    for (int i = 0; i < MAX_DINERS; i++)
    {
        int id1 = i;
        int id2 = (i + 1) % MAX_DINERS;
        if (get_dining_policy() == FORK_REORDERING && id1 > id2)
        {
            printf("Reordered forks %d and %d\n", id1, id2);
            diner_init(&diner[i], i, &fork[id2], &fork[id1]);
        }
        else
        {
            diner_init(&diner[i], i, &fork[id1], &fork[id2]);
        }
    }

    /* start the actual threads for each diner */
    for (int i = 0; i < MAX_DINERS; i++)
    {
        printf("Creating thread %d", i);
        diner_start(&diner[i]);
    }

    /* monitor the state of the diners in the main (highest-priority) thread
     * because it is high priority, it must sleep for a short time to give
     * the diner threads a chance to do their thing.
     */
    int go_on = 1;
    while (go_on)
    {
        for (int i = 0; i < MAX_DINERS; i++)
        {
            putchar(diner[i].state);
        }
        putchar('\n');
        go_on = 0;
        for (int i = 0; i < MAX_DINERS; i++)
        {
            go_on |= diner[i].state != 'd';
        }
        millisecond_sleep(MAIN_THREAD_SLEEP_TIME);
    }

    /* assuming no deadlock happened, this code will be reached so we
     * can join with the main thread
     */

    for (int i=0; i < MAX_DINERS; i++)
    {
        diner_await(&diner[i]);
        printf("Diner id %c exited normally; state = %c\n", diner[i].id, diner[i].state);
    }

    /* locks associated with forks need to be cleaned up */
    for (int i = 0; i < MAX_DINERS; i++)
        fork_free_resources(&fork[i]);

    /* attribute object should also be freed (could do earlier, too) */
    //pthread_attr_destroy(&attr);
}

Key points:

• The program creates five shared fork_t objects and five diner_t objects.

• Each diner receives pointers to the two forks it needs.

• The default order gives each diner its normal left and right fork.

• When the policy is avoid_deadlock, the program reorders the fork pointers so each diner follows the same resource order.

• The main thread prints each diner’s state so deadlock can be observed.

//
// Created by gkt on 10/16/20.
//

#include <string.h>
#include <stdlib.h>
#include <pthread.h>

#include "diners.h"
#include "millisleep.h"

void fork_init(fork_t *fork, int value)
{
    fork->id = '0' + value;
    pthread_mutex_init(&fork->lock, NULL);
}

void fork_pickup(fork_t *fork)
{
    pthread_mutex_lock(&fork->lock);
}

void fork_putdown(fork_t *fork)
{
    pthread_mutex_unlock(&fork->lock);
}

void fork_free_resources(fork_t *fork)
{
    pthread_mutex_destroy(&fork->lock);
}

void diner_init(diner_t *diner, int id, fork_t *left, fork_t *right)
{
    diner->id = '0' + id;
    diner->state = 't';
    diner->left = left;
    diner->right = right;
}

void diner_start(diner_t *diner)
{
    pthread_attr_t attr;

    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
    pthread_create(&diner->thread, &attr, diner_run, (void *)diner);
    pthread_attr_destroy(&attr);
}

void diner_await(diner_t *diner)
{
    void *result;
    pthread_join(diner->thread, &result);
}

void diner_think(diner_t *diner)
{
    diner->state = 't';
    millisecond_sleep(rand() % MAX_THINK_TIME);
}

void diner_eat(diner_t *diner)
{
    diner->state = 'e';
    millisecond_sleep(rand() % MAX_EAT_TIME);
}

void *diner_run(void *tsd)    /* tsd should be the diner object */
{
    diner_t *diner = (diner_t *) tsd;

    for (int i = 0; i < 1000; i++)
    {

        diner_think(diner);
        diner->state = diner->left->id;
        millisecond_sleep(1);
        fork_pickup(diner->left);
        diner->state = diner->right->id;
        millisecond_sleep(1);
        fork_pickup(diner->right);
        diner_eat(diner);
        fork_putdown(diner->left);
        fork_putdown(diner->right);
    }
    diner->state = 'd';
    pthread_exit(diner);
}

enum dining_policy_t get_dining_policy()
{
    char *dining_policy = getenv("DINING_POLICY");
    if (dining_policy == NULL)
        return NO_FORK_REORDERING;

    if (strcmp(dining_policy, "avoid_deadlock") == 0)
        return FORK_REORDERING;

    return NO_FORK_REORDERING;
}

Key points:

• Each fork is protected by a pthread_mutex_t.

• fork_pickup() locks the fork mutex, and fork_putdown() unlocks it.

• diner_run() repeatedly thinks, picks up the left fork, picks up the right fork, eats, and releases both forks.

• The short sleep between fork acquisitions makes the deadlock easier to reproduce.

• get_dining_policy() reads the environment variable that selects the deadlock-avoidance policy.

//
// Created by gkt on 10/16/20.
//

#ifndef DINERS_H
#define DINERS_H

#define MAX_DINERS 5
#define MAX_THINK_TIME 7
#define MAX_EAT_TIME 7
#define MAIN_THREAD_SLEEP_TIME 51

typedef struct
{
    char id;
    pthread_mutex_t lock;
} fork_t;

typedef struct
{
    char id;
    char state;
    fork_t *left;
    fork_t *right;
    pthread_t thread;
} diner_t;

extern void fork_init(fork_t *fork, int value);

extern void fork_pickup(fork_t *fork);

extern void fork_putdown(fork_t *fork);

extern void fork_free_resources(fork_t *fork);

extern void diner_init(diner_t *diner, int id, fork_t *left, fork_t *right);

extern void diner_think(diner_t *diner);

extern void diner_eat(diner_t *diner);

extern void diner_start(diner_t *diner);

extern void diner_await(diner_t *diner);

extern void *diner_run(void *tsd);

enum dining_policy_t
{
    NO_FORK_REORDERING, FORK_REORDERING
};

extern enum dining_policy_t get_dining_policy();

#endif //DINERS_DININGPHILOSOPHERS_H

Key points:

• fork_t stores the fork id and the mutex protecting that fork.

• diner_t stores the diner id, current state, fork pointers, and pthread handle.

• The dining_policy_t enum records whether fork reordering is active.

• The header separates the shared data model from the implementation in diners.c.

Example of Deadlock in Nested Calls

Deadlock can be harder to see when locks are acquired through nested method calls.

void method1() {
   a.lock();
   method2();
   a.unlock();
}

void method2() {
   b.lock();
   c.lock();
   b.unlock();
   c.unlock();
}

void method3() {
   c.lock();
   method2();
   method4();
   c.unlock();
}

void method4() {
   d.lock();
   d.unlock();
}

Here, method3() locks c and then calls method2(), which tries to lock c again after locking b. Depending on the lock type and the rest of the program, this can produce self-deadlock or contribute to a larger lock-ordering cycle.

Multi-Lock Solutions in Windows

Windows provides WaitForMultipleObjects() for waiting on multiple kernel objects.

The objects can include events, mutexes, semaphores, timers, and other waitable handles. This gives Windows programs a system-level way to wait for one or more synchronization objects.

Multi-Lock Solutions in Linux and Minix

Linux and Minix do not provide a general multi-lock operation for normal pthread mutexes.

The usual guidance is to avoid multi-locking when possible. When multiple locks are necessary, use a consistent ordering rule. For shared-memory semaphores, virtual address order is not reliable across processes, so the order should come from a shared table, array index, or explicit lock number.

Deadlock with Correct Lock Ordering

Lock ordering prevents circular wait, but it does not prevent every way a program can stop making progress.

A thread can still lock a resource and fail to release it. Common causes include missing unlock calls, crashes while holding a lock, infinite loops inside critical sections, and monitor conditions that never become true. These failures are often harder to handle because the lock order may be correct while the program state is not.

Starvation

Starvation occurs when one or more threads wait indefinitely because other threads keep getting access to the resource first.

Starvation is closely related to scheduling fairness. A program can avoid deadlock and still be unfair enough that one thread makes little or no progress.

Starvation Example

This example holds a lock while performing blocking I/O. That can make other threads wait much longer than necessary.

Queue _queue = new Queue();
Mutex _mutex = new Mutex();

void add() {
   int value = 0;
   while(1) {
      _mutex->Lock();
      while(_queue->count() > 0) {
         value += _queue->Dequeue();
         printf("current value = %d\n", value);
      }
      _mutex->Unlock();
   }
}

void read_values() {
   while(1) {
      int value = 0;
      _mutex->Lock();
      scanf("%d\n", &value);
      _queue->Enqueue(value);
      _mutex->Unlock();
   }
}

The first thread holds the lock while calling printf(). The second thread holds the lock while calling scanf(). Both operations can block, and while either one blocks the other thread cannot enter the critical section.

Reducing Starvation

One simple improvement is to keep blocking I/O outside the critical section.

Queue _queue = new Queue();
Mutex _mutex = new Mutex();

void add() {
   int value = 0;
   while(1) {
      _mutex->Lock();
      while(_queue->count() > 0) {
         value += _queue->Dequeue();
         _mutex->Unlock();
         printf("current value = %d\n", value);
         _mutex->Lock();
      }
      _mutex->Unlock();
   }
}

void read_values() {
   while(1) {
      int value = 0;
      scanf("%d\n", &value);
      _mutex->Lock();
      _queue->Enqueue(value);
      _mutex->Unlock();
   }
}

This version does not hold the lock during printf() or scanf(). The critical section is shorter, and the average wait time for the lock is reduced.

Guidelines to Avoid Starvation

Starvation is less likely when locks are held for short, predictable periods.

Useful guidelines include:

• Keep critical sections short.

• Avoid blocking I/O while holding a lock.

• If a computation is long-running, design it so the lock can be released periodically.

• Copy the needed data while holding the lock, then do expensive work after releasing it.

• Use synchronization libraries that provide fairness guarantees when fairness matters.

Livelock

Livelock occurs when threads keep running but repeatedly take actions that prevent progress.

It can happen in deadlock-avoidance code when two threads both release and retry at the same time.

void thread1() {
   while(1) {
      a.lock();
      if(b.trylock()) {
         /* do work */
         b.unlock();
      }
      a.unlock();
   }
}

void thread2() {
   while(1) {
      b.lock();
      if(a.trylock()) {
         /* do work */
         a.unlock();
      }
      b.unlock();
   }
}

One possible sequence is:

• thread1 locks a.

• thread2 locks b and fails to lock a.

• thread1 fails to lock b and releases a.

• thread2 releases b.

If the pattern repeats, both threads continue executing but neither completes the protected work. Backoff, ordering, or a coordinator can break the livelock.

Lock Fairness

Lock fairness means that threads waiting for a lock have similar average wait times.

Fair locks can reduce starvation and make execution more predictable. Common approaches include FIFO wait queues and, less commonly, schedulers that use timing history.

Fairness Tradeoffs

Fairness has a cost because selecting the next owner of a lock is not the same as immediately running that thread.

A fair lock can reduce throughput when a thread repeatedly locks and unlocks a short critical section. An unfair lock may let the same thread reacquire the lock quickly, which can improve locality and throughput but can also starve other threads.