Chapter 21 of 38

Deadlocks

Picture a narrow one-lane bridge. A car enters from the left, another car enters from the right, and they meet in the middle. Neither can move forward, and neither wants to reverse. Both drivers wait for the other to give way, and they could wait forever.

Processes and threads can get stuck in exactly the same way. In the last few chapters (Mutex Locks & Semaphores, Classical Synchronization Problems and Monitors) we used locks to keep shared data safe. Locks solve race conditions, but they create a new danger: two threads can each hold one lock and wait for the other's lock. Nobody ever lets go. This is called a deadlock.

In this chapter we will understand what a deadlock is, see one happen in a real C program, learn the four conditions that cause it, draw it with a Resource Allocation Graph, and get an overview of how operating systems deal with it. The next two chapters cover the actual cures: prevention, avoidance, detection and recovery.


What Is a Deadlock?

A deadlock is a situation in which a set of processes is blocked forever because every process in the set is waiting for an event (usually the release of a resource) that can only be caused by another process in the same set.

The key words are "in the same set". Every process is waiting for someone else in the group, so nobody in the group can ever make progress. The OS will not "time out" the wait by itself, so the processes stay blocked until something from outside (the user, the OS, an administrator) breaks the cycle.

A simple two-process deadlock looks like this:

   P1 holds R1                 P2 holds R2
   P1 wants R2                 P2 wants R1

        +------+   wants   +------+
        |  P1  | --------> |  R2  |
        +------+           +------+
           ^                   |
      held |                   | held by
       by  |                   v
        +------+   wants   +------+
        |  R1  | <-------- |  P2  |
        +------+           +------+

   P1 waits for P2, P2 waits for P1  →  nobody moves

Real-life examples are everywhere:

  • Traffic gridlock at a crossing, where every car blocks the car on its right.

  • Two people and two keys: one has the key to the cupboard, the other has the key to the room the cupboard is in. Each refuses to hand over a key until they get the other one.

  • The Dining Philosophers from Classical Synchronization Problems: if all five philosophers pick up their left fork at the same moment, all of them wait forever for the right fork.


The System Model: Resources

To talk about deadlocks precisely, we model the system as a set of resources that processes compete for.

  • A resource type is a kind of resource: CPU, printer, a mutex lock, a file, a database row, memory pages.

  • Each type has one or more instances. A system may have 1 printer (one instance) but 4 identical tape drives (four instances). If a process asks for "a tape drive", any one of the four will do.

Every process uses a resource in three steps:

1. Request  → ask for the resource; if it is not free, WAIT (block)
2. Use      → work with it (print, write the file, update the row)
3. Release  → give it back so others can use it

Requests and releases happen through system calls or library calls: open()/close(), malloc()/free(), pthread_mutex_lock()/pthread_mutex_unlock(), sem_wait()/sem_post(), and so on.

Two more distinctions matter for deadlocks:

Kind

Meaning

Examples

Preemptable

Can be taken away from a process and given back later without harm

CPU (save registers, switch), memory pages (swap out)

Non-preemptable

Taking it away midway would break the work

Printer in the middle of a job, a lock protecting half-updated data, a DVD being burnt

Reusable

Used, released and used again; the count stays fixed

Locks, files, devices, memory

Consumable

Created and destroyed; disappears once used

Messages, signals, data in a pipe

Deadlocks are mainly a problem with non-preemptable resources. If the OS could simply take the resource away, there would be no deadlock to worry about.


A Deadlock in Real Code

Let us create a deadlock on purpose. Two threads use the same two mutexes, but they lock them in opposite order. The sleep(1) makes sure each thread grabs its first lock before trying the second, so the deadlock happens every time instead of "sometimes".

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

pthread_mutex_t lock_a = PTHREAD_MUTEX_INITIALIZER;   /* resource R1 */
pthread_mutex_t lock_b = PTHREAD_MUTEX_INITIALIZER;   /* resource R2 */

void *thread1(void *arg) {
    (void)arg;
    pthread_mutex_lock(&lock_a);
    printf("T1: got lock A, now waiting for lock B\n");
    sleep(1);                         /* give T2 time to grab B */
    pthread_mutex_lock(&lock_b);      /* blocks forever */
    printf("T1: got both locks\n");
    pthread_mutex_unlock(&lock_b);
    pthread_mutex_unlock(&lock_a);
    return NULL;
}

void *thread2(void *arg) {
    (void)arg;
    pthread_mutex_lock(&lock_b);
    printf("T2: got lock B, now waiting for lock A\n");
    sleep(1);                         /* give T1 time to grab A */
    pthread_mutex_lock(&lock_a);      /* blocks forever */
    printf("T2: got both locks\n");
    pthread_mutex_unlock(&lock_a);
    pthread_mutex_unlock(&lock_b);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    setvbuf(stdout, NULL, _IONBF, 0);   /* print immediately */
    pthread_create(&t1, NULL, thread1, NULL);
    pthread_create(&t2, NULL, thread2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("main: both threads finished\n");
    return 0;
}

We compile it and run it under timeout, which kills the program after 5 seconds (otherwise it would hang forever):

gcc -std=c17 -Wall -Wextra -pthread deadlock.c -o deadlock
timeout 5 ./deadlock; echo "exit status: $?"
T1: got lock A, now waiting for lock B
T2: got lock B, now waiting for lock A
exit status: 124

The two "waiting" lines may appear in either order because the threads run concurrently, but the end result is always the same: "got both locks" and "main: both threads finished" are never printed. Exit status 124 means timeout had to kill the program.

What does the OS see while the program is stuck? We ran it in the background and looked at its threads with ps -L -o pid,lwp,stat,wchan:16,comm (process IDs will differ on your machine, and the WCHAN name depends on the kernel version; this was Linux 6.18):

    PID     LWP STAT WCHAN            COMMAND
  14832   14832 Sl+  futex_do_wait    deadlock
  14832   14834 Sl+  futex_do_wait    deadlock
  14832   14835 Sl+  futex_do_wait    deadlock

All three threads (main, T1 and T2) are in state S (sleeping), waiting inside the kernel's futex code, which is what Linux uses to put a thread to sleep on a mutex. top showed 0.0% CPU. This is an important observation:

A deadlocked process does not burn CPU. It just sleeps forever. From outside it looks like a program that has "hung" or "frozen".

The OS did not complain, did not print a warning and did not fix it. Ordinary Linux will happily let your threads deadlock. We will see why in the "Ignore it" strategy below.


The Four Necessary Conditions (Coffman Conditions)

In 1971, Coffman, Elphick and Shoshani showed that a deadlock can arise only if all four of the following conditions hold at the same time:

Condition

Meaning

In our C program

1. Mutual exclusion

At least one resource is non-sharable: only one process can use it at a time.

A mutex can be held by only one thread.

2. Hold and wait

A process holds at least one resource while waiting to get more.

T1 holds A while waiting for B.

3. No preemption

A resource cannot be forcibly taken away; it is released only voluntarily by the process holding it.

Nobody can snatch lock A from T1.

4. Circular wait

There is a chain P0 → P1 → … → Pn → P0 where each process waits for a resource held by the next one.

T1 waits for T2 (lock B), T2 waits for T1 (lock A).

Why are all four needed? Remove any one and the deadlock cannot form:

  • If resources were sharable (like a read-only file), nobody would have to wait at all.

  • If a process could not hold while waiting, it would never block another process while being blocked itself.

  • If resources could be preempted, the OS could take one away and break the jam.

  • If there were no cycle, some process at the end of the waiting chain would not be waiting for anyone, would finish, release its resources, and the chain would unwind.

Note that the four conditions are necessary, not sufficient. They tell you when a deadlock can happen. Circular wait actually implies hold and wait (everyone in the cycle holds something and waits for something), so the conditions are not fully independent, but they are listed separately because each one suggests a different way to prevent deadlocks. That is exactly what Deadlock Prevention & Avoidance (Banker's Algorithm) builds on.

Memory trick: "My House Needs Cleaning" → Mutual exclusion, Hold and wait, No preemption, Circular wait.


Resource Allocation Graph (RAG)

A Resource Allocation Graph is a directed graph that shows, at one moment in time, which process holds which resource and which process is waiting for which resource. It is the standard way to draw and reason about deadlocks.

  • Process node: drawn as a circle, written here as (P1).

  • Resource node: drawn as a rectangle, with one dot per instance, written here as [R1 ••] for 2 instances.

  • Request edge P → R: process P has requested R and is waiting for it.

  • Assignment edge R → P: an instance of R has been given to P. (In a drawing it starts from a specific dot.)

When a request is granted, the request edge P → R turns into an assignment edge R → P. When P releases R, the assignment edge disappears.

Example 1: No cycle, no deadlock

   (P1) ──► [R1 •] ──► (P2) ──► [R2 •] ──► (P3)

   P2 holds R1 and waits for R2.  P1 waits for R1.
   R2 is held by P3, and P3 is not waiting for anything.

P3 is not waiting, so it will finish and release R2. Then P2 gets R2, finishes and releases R1. Then P1 gets R1. Everybody finishes. No cycle → no deadlock.

Example 2: Cycle with single-instance resources → deadlock

   (P1) ──► [R2 •] ──► (P2)
     ▲                   │
     │                   ▼
   [R1 •] ◄──────────────┘

   P1 holds R1, waits for R2.   P2 holds R2, waits for R1.
   Cycle: P1 → R2 → P2 → R1 → P1

This is our C program drawn as a graph. Every resource has exactly one instance, so the cycle means each process is waiting for an instance that is definitely held by another process in the cycle. Deadlock.

Example 3: Cycle with multiple instances, but NO deadlock

Now let R1 have 2 instances and R2 have 1 instance.

   R1 (2 instances): one held by P2, one held by P3
   R2 (1 instance) : held by P1

   P1 ──► R1      (P1 waits for an instance of R1)
   P2 ──► R2      (P2 waits for R2)
   P3             (holds one R1, not waiting for anything)

   Cycle: P1 → R1 → P2 → R2 → P1

There is a cycle, but P3 is outside it and is not waiting. P3 finishes and releases its instance of R1. That instance goes to P1, so P1 finishes and releases R2. Then P2 gets R2 and finishes. Cycle, but no deadlock.

Example 4: Same graph, one more request → deadlock

Take Example 3 and suppose P3 also requests R2 before releasing its R1:

   P1 ──► R1,  P2 ──► R2,  P3 ──► R2
   Free instances: R1 = 0, R2 = 0

Both instances of R1 are held by P2 and P3, and both of them are now waiting for R2. R2 is held by P1, and P1 is waiting for R1. No process can finish, so no process will ever release anything. There are now two cycles (P1 → R1 → P2 → R2 → P1 and P1 → R1 → P3 → R2 → P1), and nobody outside them can help. Deadlock.

The rules to remember

What the graph shows

Conclusion

No cycle

No deadlock (guaranteed)

Cycle, and every resource type has exactly one instance

Deadlock (guaranteed). The cycle is necessary and sufficient.

Cycle, and some resource types have several instances

Deadlock may or may not exist. You must check whether some process can still finish (Examples 3 and 4). The systematic check is the detection algorithm in Deadlock Detection & Recovery.


Deadlock vs Starvation vs Livelock

These three are often confused in interviews. All of them mean "a process is not making progress", but for different reasons.

Deadlock

Starvation

Livelock

What happens

A group of processes all wait for each other forever

One process waits for a very long (possibly unbounded) time while others keep getting the resource

Processes keep changing state in response to each other but never make real progress

State of processes

Blocked (sleeping)

Ready or waiting, but always passed over

Running (busy, using CPU)

Can it end by itself?

No, never

Yes, if the competition dies down

Possibly, by luck in timing

Example

T1 holds A wants B, T2 holds B wants A

A low-priority process in strict priority scheduling (see Priority Scheduling)

Two people in a corridor who both step left, then both step right, again and again

Typical fix

Prevention, avoidance, detection and recovery

Aging, fair queues

Random back-off delays

A deadlock always causes starvation of the processes involved, but starvation does not imply deadlock.

A livelock in code often looks like a "polite" thread that uses pthread_mutex_trylock(): if it cannot get the second lock, it releases the first and tries again immediately. If two threads do this in perfect step, both keep grabbing and releasing forever. Adding a small random delay before retrying usually fixes it.


How Can an OS Handle Deadlocks?

There are four broad strategies:

Strategy

Idea

Cost

1. Prevention

Design the system so that at least one of the four conditions can never hold.

Restrictive; can waste resources or reduce concurrency.

2. Avoidance

Allow all four conditions, but before granting each request, check that the system stays in a safe state. Needs to know each process's maximum needs in advance (Banker's algorithm).

Run-time check on every request; needs advance information that real programs rarely have.

3. Detection and recovery

Let deadlocks happen, periodically detect them, then break them by killing processes or preempting resources.

Detection overhead; lost work when recovering.

4. Ignore it (Ostrich algorithm)

Pretend deadlocks never happen. If one does, the user or admin restarts the program or machine.

Zero overhead; occasional hang.

Strategies 1 and 2 are covered in Deadlock Prevention & Avoidance (Banker's Algorithm), and strategy 3 in Deadlock Detection & Recovery.

What do real systems actually do?

It surprises many students, but general-purpose operating systems like Linux, Windows and macOS mostly use the ostrich approach for user programs. The kernel does not run the Banker's algorithm on your mutexes, and as our C program showed, it will let your threads deadlock forever.

Why? Because deadlocks in a well-written system are rare, while the cost of avoidance (knowing maximum needs, checking every request) would be paid on every single lock operation. It is the programmer's job to avoid deadlocks, usually by always taking locks in a fixed order.

That said, deadlock handling is used where it pays off:

  • Database systems such as MySQL InnoDB and PostgreSQL detect deadlocks between transactions and roll back one of them (a victim). We will see a real example in Deadlock Detection & Recovery.

  • Inside the Linux kernel, a debugging tool called lockdep (the lock validator) records the order in which kernel locks are taken and warns developers when it sees an order that could lead to a deadlock, even before one actually happens.

  • Some resources are designed to be preemptable so that deadlock over them is impossible, for example CPU time and memory pages.


A Classic Numerical: Minimum Resources to Avoid Deadlock

This type of question is very common in GATE and university exams.

A system has R identical instances of a resource and n processes. Process Pi needs at most mi instances to finish. What is the minimum R that guarantees no deadlock?

Think about the worst case. A deadlock is most likely when every process is just one instance short of finishing. In that case process Pi holds mi − 1 instances, all instances are used up, and everyone waits.

If we have even one more instance than that, some process can get its last instance, finish, and release everything it holds, which lets the others finish one by one. So:

Deadlock is possible       if   R  ≤  Σ (mᵢ − 1)
Deadlock is impossible     if   R  ≥  Σ (mᵢ − 1) + 1

Minimum R  =  Σ (mᵢ − 1) + 1

If all n processes need the same maximum k:

Minimum R  =  n(k − 1) + 1

Worked examples

Q1. 3 processes, each needs 2 printers. Minimum printers for no deadlock?

R = 3 × (2 − 1) + 1 = 4
Check with R = 3: each process holds 1 and waits for 1 more → deadlock possible.

Q2. Three processes need at most 3, 4 and 5 tape drives respectively. Minimum drives?

R = (3 − 1) + (4 − 1) + (5 − 1) + 1 = 2 + 3 + 4 + 1 = 10
Deadlock at R = 9: allocation (2, 3, 4) uses all 9, everyone needs 1 more.

Q3 (reverse question). A system has 10 identical resources and each process needs at most 3. What is the maximum number of processes that can run without any possibility of deadlock?

Need  n(3 − 1) + 1 ≤ 10   →   2n ≤ 9   →   n ≤ 4.5   →   n = 4
With n = 5: each holds 2 → 10 used, all need 1 more → deadlock possible.

We checked all of these answers with a small brute-force program that tries every possible allocation and looks for a state where no process can get what it needs.


Common Mistakes

  • "A cycle in the RAG always means deadlock." Only when every resource in the cycle has a single instance. With multiple instances, a cycle is necessary but not sufficient.

  • "Deadlock and starvation are the same." Deadlocked processes can never proceed. A starving process could proceed; it is just unlucky or unfairly treated.

  • "Any one of the four conditions causes deadlock." All four must hold at the same time. Breaking any one is enough to prevent deadlock.

  • "A deadlocked program is using 100% CPU." No, deadlocked threads are blocked and use no CPU. A program spinning at 100% CPU is more likely in an infinite loop or a livelock.

  • "The OS will detect and fix my deadlock." Not for ordinary mutexes on Linux or Windows. You must design your locking so that deadlock cannot happen.

  • Getting the minimum-resource formula wrong by one. Σ(mi − 1) is the largest R where deadlock is still possible. The answer is that value plus one.


Interview Questions

What is a deadlock?

A set of processes is deadlocked when each process in the set is waiting for an event (usually a resource release) that only another process in the same set can cause. None of them can ever proceed.

What are the four necessary conditions for deadlock?

Mutual exclusion, hold and wait, no preemption, and circular wait. All four must hold simultaneously for a deadlock to occur.

In a resource allocation graph, does a cycle imply deadlock?

If every resource type has a single instance, yes. If some resource types have multiple instances, a cycle means deadlock is possible but not certain. No cycle always means no deadlock.

What is the difference between deadlock and starvation?

In deadlock, a group of processes wait for each other in a cycle and none can ever proceed. In starvation, a process waits indefinitely because others keep getting preference, but it could proceed if it were chosen. Aging fixes starvation; it does not fix deadlock.

What is a livelock?

A situation where processes are not blocked but keep reacting to each other (for example, repeatedly releasing and retrying locks) without making progress. Unlike deadlock, the processes are running and using CPU.

What is the ostrich algorithm and why do real OSes use it?

Ignoring deadlocks and letting the user or administrator restart things if one occurs. Linux and Windows do this for application locks because deadlocks are rare and the overhead of preventing or avoiding them on every request would be high.

n processes each need at most k instances of a resource. What is the minimum number of instances for a deadlock-free system?

n(k − 1) + 1. In the worst case each process holds k − 1 and waits for one more; one extra instance lets some process finish and release its resources.

Give an example of how two threads can deadlock using mutexes.

Thread 1 locks A then tries to lock B, while thread 2 locks B then tries to lock A. If each gets its first lock before the other's second request, both wait forever. Always locking A before B in every thread prevents it.


Summary

  • A deadlock is a set of processes each waiting for a resource held by another process in the same set; none can ever proceed.

  • Processes use resources in three steps: request → use → release. Deadlocks come from non-preemptable resources.

  • Four necessary conditions (all at once): mutual exclusion, hold and wait, no preemption, circular wait.

  • A Resource Allocation Graph has request edges P → R and assignment edges R → P. No cycle → no deadlock. Cycle with single instances → deadlock. Cycle with multiple instances → maybe.

  • Deadlocked threads sleep and use no CPU. Livelocked threads run but make no progress. Starving threads could run but keep being passed over.

  • Handling strategies: prevention, avoidance, detection and recovery, or ignore. Mainstream OSes ignore deadlocks among application locks; databases detect and recover.

  • Minimum instances to guarantee no deadlock: Σ(mi − 1) + 1.

Next, we will learn how to make deadlocks impossible by breaking one of the four conditions, and how the famous Banker's algorithm keeps a system safe, in Deadlock Prevention & Avoidance (Banker's Algorithm).