Introduction
A deadlock is a state in which a set of processes are each waiting for a resource held by another process in the same set, so that none of them can ever proceed. Deadlocks are a classic concern in operating systems whenever multiple processes compete for a finite set of reusable resources such as mutexes, printers, memory buffers, or database locks. Understanding exactly when a deadlock can arise starts with the four necessary conditions identified by Coffman, Elphick, and Shoshani in 1971.
Cricket analogy: A deadlock is like two teams each refusing to take the field until the other hands over the only working set of stumps first, so neither match ever starts, a scenario the Coffman conditions from 1971 formally describe for finite shared resources like grounds, umpires, or equipment.
Explanation
A deadlock can occur only if all four of the following conditions hold at the same time: (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 must be released voluntarily. (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, until Pn is waiting for a resource held by P0. All four conditions are necessary; if any one is broken, deadlock cannot occur. This is exactly why prevention techniques target breaking one of these conditions.
Cricket analogy: Mutual Exclusion is one set of stumps usable by only one team at a time; Hold and Wait is a team holding the bat while waiting for the ball to become free; No Preemption means umpires can't forcibly take the bat away; Circular Wait is team A waiting on team B's ground while B waits on A's - break any one and the standoff can't happen.
Example
/* Classic circular-wait scenario with two threads and two mutexes */
#include <pthread.h>
#include <stdio.h>
pthread_mutex_t lockA = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lockB = PTHREAD_MUTEX_INITIALIZER;
void *thread1(void *arg) {
pthread_mutex_lock(&lockA); /* holds A */
printf("thread1 acquired A, waiting for B\n");
pthread_mutex_lock(&lockB); /* waits for B, held by thread2 */
/* ... critical section ... */
pthread_mutex_unlock(&lockB);
pthread_mutex_unlock(&lockA);
return NULL;
}
void *thread2(void *arg) {
pthread_mutex_lock(&lockB); /* holds B */
printf("thread2 acquired B, waiting for A\n");
pthread_mutex_lock(&lockA); /* waits for A, held by thread1 */
/* ... critical section ... */
pthread_mutex_unlock(&lockA);
pthread_mutex_unlock(&lockB);
return NULL;
}Analysis
In this program, thread1 locks A then tries to lock B, while thread2 locks B then tries to lock A. If both threads run far enough to grab their first lock before either reaches the second lock call, all four Coffman conditions hold: mutexes are non-shareable (mutual exclusion), each thread holds one lock while waiting on another (hold and wait), locks cannot be stolen (no preemption), and thread1 waits on thread2 which waits on thread1 (circular wait of length two). Neither thread can ever proceed — this is a genuine, reproducible deadlock. This scenario is commonly represented with a resource-allocation graph, where a cycle among process and resource nodes visually confirms the circular wait.
Cricket analogy: Two teams each lock their own dressing room then reach for the shared team bus keys the other holds - if both grab their dressing room first, all four Coffman conditions hold and neither team ever boards, a standoff a resource-allocation graph would show as a cycle between two teams and two resources.
Key Takeaways
- Deadlock requires all four Coffman conditions simultaneously: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait.
- Breaking any single one of the four conditions makes deadlock impossible for that resource-allocation pattern.
- A resource-allocation graph with a cycle (and single-instance resources) is a reliable visual indicator of a potential deadlock.
- Inconsistent lock ordering across threads is the most common real-world cause of circular wait.
Practice what you learned
1. Which of the following is NOT one of the four necessary conditions for deadlock?
2. The 'No Preemption' condition means:
3. In a resource-allocation graph with only single-instance resource types, what confirms a deadlock?
4. Why must ALL four Coffman conditions hold for a deadlock to occur?
5. Two threads lock mutex A then B, and B then A respectively, in the same order both times. What is most likely?
Was this page helpful?
You May Also Like
Introduction to Deadlocks
Get a high-level preview of what deadlock is and the four necessary conditions that must all hold for it to occur.
Deadlock Prevention and Avoidance
How to stop deadlocks before they happen: prevention breaks a Coffman condition; avoidance uses the Banker's Algorithm.
Deadlock Detection and Recovery
Letting deadlocks occur, detecting them via cycle/graph algorithms, and recovering through termination or preemption.
Mutex and Semaphores
Compare mutexes and binary/counting semaphores as tools for enforcing mutual exclusion and coordinating threads.