Introduction to Deadlocks

Analogy categoryAnalogies

Introduction

Deadlock is a state in which two or more processes (or threads) are each waiting for a resource that another process in the same set holds, so none of them can ever proceed. Unlike a race condition, which is a timing bug, deadlock is a structural problem with how resources are requested and held; once all participants are blocked waiting on each other, the system cannot resolve the situation without external intervention. This topic previews the concept at a high level; the next module covers detection, prevention, and avoidance in depth.

🏏

Cricket analogy: Picture two batsmen who both dive for the same run and end up stranded mid-pitch, each refusing to move back until the other does; that mutual standstill, not a mistimed shot, is deadlock rather than a fleeting timing error like a mix-up.

Requirements

Coffman (1971) showed that deadlock can occur only if all four of the following conditions hold simultaneously: (1) Mutual Exclusion — at least one resource must be held in a non-shareable mode, so only one process can use it at a time; (2) Hold and Wait — a process holding at least one resource is waiting to acquire additional resources currently held by other processes; (3) No Preemption — resources cannot be forcibly taken away from a process; they can only be released voluntarily by the process holding them; (4) Circular Wait — there exists a set of waiting processes {P0, P1, ..., Pn} such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, and so on, with Pn waiting for a resource held by P0. All four conditions are necessary; breaking any single one is sufficient to prevent deadlock, which is the basic idea behind prevention strategies covered later.

🏏

Cricket analogy: A single bat and helmet shared by two waiting batsmen (mutual exclusion), each holding pads while waiting for the bat (hold and wait), the umpire unable to confiscate the bat mid-over (no preemption), and both refusing to yield in a circular standoff (circular wait) together produce deadlock.

Example

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

pthread_mutex_t lock_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_b = PTHREAD_MUTEX_INITIALIZER;

void *thread1(void *arg) {
    pthread_mutex_lock(&lock_a);
    printf("Thread 1: locked A, trying B...\n");
    sleep(1); /* give thread2 time to lock B, forcing the deadlock */
    pthread_mutex_lock(&lock_b);   /* blocks forever: thread2 holds B, wants A */

    printf("Thread 1: acquired both locks\n");
    pthread_mutex_unlock(&lock_b);
    pthread_mutex_unlock(&lock_a);
    return NULL;
}

void *thread2(void *arg) {
    pthread_mutex_lock(&lock_b);
    printf("Thread 2: locked B, trying A...\n");
    sleep(1);
    pthread_mutex_lock(&lock_a);   /* blocks forever: thread1 holds A, wants B */

    printf("Thread 2: acquired both locks\n");
    pthread_mutex_unlock(&lock_a);
    pthread_mutex_unlock(&lock_b);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, thread1, NULL);
    pthread_create(&t2, NULL, thread2, NULL);
    pthread_join(t1, NULL);   /* program hangs forever: classic deadlock */
    pthread_join(t2, NULL);
    return 0;
}

Analysis

This program never terminates. Thread 1 locks lock_a then tries to lock lock_b; Thread 2 locks lock_b then tries to lock lock_a. After the sleep, each thread holds one lock and blocks forever waiting for the other, exhibiting all four Coffman conditions: mutual exclusion (each mutex is held by only one thread), hold-and-wait (each thread holds one lock while waiting for another), no preemption (pthread_mutex_lock cannot be forcibly revoked from a thread), and circular wait (Thread 1 waits on Thread 2's lock and vice versa). A simple fix that breaks circular wait is to impose a global lock ordering — for example, always lock lock_a before lock_b in every thread — which is one of the prevention techniques explored in the next module.

🏏

Cricket analogy: Two fielders each grab a different piece of equipment (helmet, gloves) then wait on the other's item to complete their gear, freezing warm-up; the fix is a fixed order — always collect helmet before gloves — breaking the circular wait.

Key Takeaways

Deadlock occurs when a set of processes/threads are each waiting for a resource held by another member of the same set, with no way to proceed.
The four Coffman conditions — Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait — are all necessary for deadlock to occur.
Breaking even one of the four conditions is enough to prevent deadlock.
A classic real-world cause is inconsistent lock ordering across threads, as shown by the two-mutex example.
Deadlock is a structural/design issue, distinct from a race condition, which is a timing issue; the next module covers prevention, avoidance, and detection in depth.

Practice what you learned

1. Which of the following best defines deadlock?

2. Which of these is NOT one of the four Coffman necessary conditions for deadlock?

3. In the two-mutex example (Thread 1 locks A then wants B; Thread 2 locks B then wants A), which condition specifically describes the shape of the waiting?

4. Why is it true that breaking just ONE of the four Coffman conditions is enough to prevent deadlock?

Was this page helpful?

Monitors

Topics covered

#OperatingSystemsStudyNotes#OperatingSystems#IntroductionToDeadlocks#Deadlocks#Requirements#Example#Analysis#StudyNotes#SkillVeris#ExamPrep