Types of Deadlock in an Operating System
A deadlock happens when each process in a group holds one resource and waits for another resource held by someone else in the same group. None of them can continue, and none of them will give up what it holds.
The word "types" means two different things in this question, so it helps to separate them early.
Some courses ask for the kinds of deadlock, grouped by what the processes wait on. Others ask for the four conditions that must all be true for any deadlock to form. Both lists are below.
The four kinds of deadlock
There is no single official list. Operating system textbooks split deadlock into resource deadlock and communication deadlock, and practice adds two more that you will meet in real code.
| Kind | What the process waits for | Example |
|---|---|---|
| Resource deadlock | A non-shareable resource such as a printer, a file or a memory block. | Process A holds the printer and wants the scanner. Process B holds the scanner and wants the printer. |
| Communication deadlock | A message that never arrives. | A waits for a reply from B, and B waits for a reply from A. |
| Thread or lock deadlock | A lock held by another thread in the same process. | Thread 1 holds lock X and wants lock Y. Thread 2 holds lock Y and wants lock X. |
| Database deadlock | A row or table lock held by another transaction. | Two transactions update the same two rows in opposite order. |
Communication deadlock is the usual form in distributed systems. No physical resource is held, so the detector has to look at message waits instead.
Database engines handle their own case. Most of them detect the cycle, abort one transaction, and return an error so your code can retry.
The four conditions that cause a deadlock
These four are known as the Coffman conditions. All four must hold at the same moment. Remove any one of them and a deadlock cannot form.
| Condition | Meaning |
|---|---|
| Mutual exclusion | At least one resource can be held by only one process at a time. |
| Hold and wait | A process holds one resource while waiting for another. |
| No preemption | A resource can be released only by the process holding it. |
| Circular wait | A closed chain exists where each process waits on the next one. |
Circular wait is a condition, not a separate kind of deadlock. Some lists call it a fourth type, which confuses the two questions.
A worked example with two locks
Two threads move money between two accounts. Each thread locks both accounts before it writes.
Thread 1 transfers from account A to account B. It locks A, then asks for B.
Thread 2 transfers from account B to account A. It locks B, then asks for A.
If both threads get their first lock before either asks for the second, both wait forever. All four conditions are present at once.
The fix is one line of policy. Always take locks in a fixed order, such as the lower account number first. That removes circular wait.
The four ways a system handles deadlock
| Strategy | What it does | Cost |
|---|---|---|
| Prevention | Design so one Coffman condition can never hold. | Lower resource use, more rigid code. |
| Avoidance | Check each request and grant it only if the system stays safe. | Needs each process to declare its maximum need in advance. |
| Detection and recovery | Let deadlocks happen, find the cycle, then break it. | Detection runs cost time, and recovery loses work. |
| Ignore it | Assume deadlocks are rare and restart when one occurs. | Chosen by most general purpose operating systems. |
The Banker's algorithm belongs to avoidance. It grants a request only when at least one order of completion still exists for every process.
It is rarely used in practice. Few programs can state their maximum resource need before they start.
How recovery works
Detection builds a wait-for graph and looks for a cycle. Once a cycle is found, the system has three ways out.
- Process termination. Kill every process in the cycle, or kill them one at a time until the cycle breaks.
- Resource preemption. Take a resource from one process and give it to another, then restart the victim later.
- Rollback. Return one process to an earlier checkpoint and let it run again from there.
Each choice needs a victim. Systems usually pick the process with the least work completed, so the least effort is lost.
Watch for starvation. If the same process is always chosen, it never finishes.
How to Prepare
- Learn the four conditions before the four kinds. Interviewers ask you to name a condition and then remove it. That is the whole answer.
- Practice the lock ordering fix. Write the two-account transfer, reproduce the deadlock, then fix it with a fixed lock order.
- Know the difference from livelock. In a deadlock nothing moves. In a livelock the threads keep acting but make no progress.
- Drill the concurrency topics. Grokking Multithreading and Concurrency for Coding Interviews covers locks, semaphores and deadlock in code.
- Place it in a design answer. Grokking System Design Fundamentals shows where locks and timeouts belong in a larger system.
- Rehearse the explanation. Try it in a mock interview and see the types of mock interview available.
GET YOUR FREE
Coding Questions Catalog
$99
$197
$72
