Deadlock in Operating Systems: Four Conditions, Prevention, Avoidance and Banker’s Algorithm
Why deadlocks happen, how to break each Coffman condition, and a worked Banker’s algorithm example.
Coding problems with instant test-case feedback
Write Python, C++, C or JavaScript in your browser and see which hidden tests pass.
A deadlock is a state where a set of processes each wait for a resource held by another process in the set, so none of them can ever continue. It is a favourite topic in OS rounds and MCQ tests because it combines theory (the four conditions) with a calculation (the Banker’s algorithm).
1. The four necessary conditions (Coffman conditions)#
A deadlock can occur only if all four hold at the same time. Break any one and deadlock is impossible.
| Condition | Meaning | One way to break it |
|---|---|---|
| Mutual exclusion | A resource can be held by only one process at a time | Make resources shareable (e.g. read-only files); not always possible |
| Hold and wait | A process holds resources while waiting for more | Request all resources at once, or release before requesting |
| No preemption | Resources cannot be taken away forcibly | Allow the OS to preempt and roll back |
| Circular wait | P1 waits for P2, P2 for P3 … Pn for P1 | Number resources and always request them in increasing order |
Lock ordering, which breaks circular wait, is the technique real programs use most. If every thread always takes lock A before lock B, the A–B cycle cannot form.
2. Four strategies for handling deadlock#
- Prevention: design the system so one of the four conditions can never hold.
- Avoidance: let processes declare their maximum needs and only grant a request if the system stays in a safe state (Banker’s algorithm).
- Detection and recovery: allow deadlocks, detect cycles in the wait-for graph, then kill or roll back a process.
- Ignore it (the ostrich approach): used by general-purpose OSes like Linux and Windows for most resources, because deadlocks are rare and the other methods are costly.
Practise placement aptitude on the real test pattern
TCS NQT, Infosys, Wipro, Accenture and Cognizant style mocks with section-wise analysis.
3. Banker’s algorithm: a worked example#
Three processes share 10 instances of one resource type. Each has a maximum need and a current allocation. Available = 10 − (allocated total).
| Process | Max | Allocated | Need (Max − Allocated) |
|---|---|---|---|
| P0 | 7 | 2 | 5 |
| P1 | 4 | 3 | 1 |
| P2 | 6 | 2 | 4 |
4. Running the safety check#
Allocated total = 7, so Available = 3. Find a process whose Need ≤ Available, let it finish, and add its allocation back to Available.
P1 needs 1 ≤ 3, finishes, Available = 3 + 3 = 6. P0 needs 5 ≤ 6, finishes, Available = 6 + 2 = 8. P2 needs 4 ≤ 8, finishes. Safe sequence: P1 → P0 → P2, so the state is safe.
If P0 now asks for 2 more, pretend to grant it: Available = 1, P0 Need = 3. Only P1 (need 1) can run, giving Available = 4; then P0 (need 3) runs, Available = 8; then P2. Still safe, so the request is granted.
| 1 | def is_safe(available, need, allocated): |
| 2 | work = available |
| 3 | done = [False] * len(need) |
| 4 | order = [] |
| 5 | while len(order) < len(need): |
| 6 | progressed = False |
| 7 | for i, finished in enumerate(done): |
| 8 | if not finished and need[i] <= work: |
| 9 | work += allocated[i] # process i finishes, releases its resources |
| 10 | done[i] = True |
| 11 | order.append(f"P{i}") |
| 12 | progressed = True |
| 13 | if not progressed: |
| 14 | return False, order # nobody can finish: unsafe |
| 15 | return True, order |
| 16 | |
| 17 | print(is_safe(3, need=[5, 1, 4], allocated=[2, 3, 2])) |
| 18 | # (True, ['P1', 'P0', 'P2']) |
An unsafe state means a deadlock might happen if processes ask for their maximum. It is not yet a deadlock. Interviewers like this distinction.
Test Your Concept Mastery
Verify your retention on: Deadlock in Operating Systems: Four Conditions, Prevention, Avoidance and Banker’s Algorithm
Requiring every thread to acquire locks in a fixed global order prevents deadlock by breaking which condition?
Banker’s algorithm is an example of deadlock…
Ready for a full proctored assessment?
Take a free aptitude mock on a real company pattern, with a worked solution for every question.
