Deadlock is a situation in which two or more processes are each waiting for a resource held by one of the others, so none can ever proceed. Like two drivers blocking a narrow lane — each waiting for the other to reverse — no-one moves and nothing gets done until something external intervenes.
What is a resource in operating system terms?
In an operating system, a resource is anything a process needs to execute: a printer, a file, a block of memory, a database record, or a network connection. Many resources can only be used by one process at a time — they are mutually exclusive. If process A holds the printer while process B holds the scanner, and A needs the scanner whilst B needs the printer, both are stuck forever. That is deadlock.
What are the four Coffman conditions for deadlock?
Edward Coffman identified in 1971 that deadlock can only occur when all four of the following conditions hold simultaneously:
| Condition | Description | Example |
|---|---|---|
| Mutual exclusion | At least one resource cannot be shared — only one process uses it at a time | A printer serves one print job at a time |
| Hold and wait | A process holds at least one resource while waiting to acquire additional resources | Process A holds the printer, waiting for the scanner |
| No pre-emption | A resource cannot be forcibly taken from a process; it must be released voluntarily | The OS cannot snatch the printer from A |
| Circular wait | A circular chain of processes exists, each waiting for a resource held by the next | A waits for B's resource; B waits for A's resource |
If even one of these four conditions is broken, deadlock cannot occur. This observation is the foundation of every deadlock prevention strategy.
How can deadlock be prevented?
Each prevention strategy targets one of the four Coffman conditions:
Break mutual exclusion — make resources shareable where possible. Read-only files can be accessed by multiple processes simultaneously. However, truly exclusive resources (a physical printer) cannot be made shareable.
Break hold and wait — require processes to request all resources they will ever need before starting. If any resource is unavailable, the process waits without holding anything. Drawback: a process must know upfront every resource it will need, which is not always possible.
Allow pre-emption — if a process is waiting for a resource, the OS takes back all resources the process currently holds and restores them later. This works for resources whose state can be saved and restored (CPU registers, memory), but not for resources like printers mid-job.
Break circular wait — assign a global ordering number to all resource types. Processes must always request resources in ascending order of their number. Since all requests go in the same direction, no circular chain can form.
What is the difference between deadlock and starvation?
These two terms are related but distinct:
| Concept | Definition | Will the process eventually run? |
|---|---|---|
| Deadlock | A set of processes are all waiting for each other — none can proceed | Never, without external intervention |
| Starvation | A process is perpetually denied the resources it needs because higher-priority processes keep taking them | Possibly — if the situation changes, it may eventually run |
Starvation can occur even without deadlock. In a priority scheduling system, a low-priority process might wait indefinitely if high-priority processes continuously arrive. Deadlock is strictly worse: it is a permanent standstill for all involved processes.
How does an operating system detect and resolve deadlock?
Rather than preventing deadlock, some systems allow it to occur and then detect and resolve it:
Detection — the OS builds a resource allocation graph: nodes are processes and resources; edges show "process holds resource" and "process is waiting for resource". If a cycle exists in the graph, deadlock is confirmed.
Resolution — the OS can:
- Kill one process in the cycle, releasing its resources.
- Roll back a process to a saved checkpoint, releasing its current resources.
- Pre-empt resources from one process and allocate them to another.
Each approach has a cost: killing a process loses work; rolling back requires checkpointing infrastructure; pre-emption may leave data in an inconsistent state.
Where does deadlock occur in real systems?
Deadlock is not a theoretical curiosity — it appears in real software:
- Database transactions — two transactions each lock one table row and try to lock the other's row. Most relational databases automatically detect this and abort one transaction.
- Multithreaded programs — two threads each lock one mutex and try to acquire the other. The lock-ordering strategy (Coffman condition 4) is the standard fix.
- Networked services — two servers each waiting for a response from the other before sending their own response.
Frequently asked questions
What is deadlock in simple terms for GCSE?
Deadlock is when two or more processes get stuck waiting for each other and cannot continue. Each holds a resource the other needs, and neither will release what it has. Without intervention from the operating system, none of them will ever finish.
What are the four Coffman conditions?
The four conditions that must all be true for deadlock to occur are: (1) mutual exclusion — a resource can only be used by one process at a time; (2) hold and wait — a process holds one resource while waiting for another; (3) no pre-emption — the OS cannot forcibly take a resource from a process; (4) circular wait — a cycle of processes exists, each waiting for the next. Remove any one and deadlock cannot happen.
What is the difference between deadlock prevention and deadlock avoidance?
Deadlock prevention eliminates one of the four Coffman conditions structurally, so deadlock is impossible by design. Deadlock avoidance allows the system to reach states where deadlock might occur, but the OS checks in advance whether granting a request could lead to deadlock and refuses if so (using algorithms like the Banker's Algorithm). Prevention is simpler; avoidance is more flexible but has overhead.
Is deadlock the same as an infinite loop?
No. An infinite loop is a single process stuck executing the same code repeatedly due to a programming error — it is consuming CPU time. A deadlocked process is blocked: it is not using the CPU; it is waiting for a resource and doing nothing. Deadlock involves at least two processes and at least two resources; an infinite loop can occur in a single process with no resource contention.
Discuss operating system concepts like deadlock with Professor Turing at aitutors.me — probing questions that build lasting understanding.