Deadlock in Operating Systems: Four Conditions, Handling Methods and a Worked Banker's Algorithm

Deadlock questions mix definitions, graphs and matrix arithmetic. Memorising four conditions cannot tell you whether a state or a new request is safe. The Deadlock in Operating Systems: Four Conditions, Banker's Algorithm, and Worked Examples connects the complete concept map to its first request walkthrough. A separate three-process matrix makes the stronger check possible: compare one grantable request with one request that passes the first two tests but still produces an unsafe state.

Related reading: Deadlock conditions and Deadlock prevention MCQs.

Deadlock in an operating system: what permanently waiting means

A deadlock is a set of processes where each waits for an event, normally a resource release, that only another member can cause. None can advance.

P0 holds single-instance R1 and requests R2. P1 holds R2 and requests R1. In the graph, R1 -> P0 and R2 -> P1 are assignment edges; P0 -> R2 and P1 -> R1 are request edges. Neither process can finish.

With one instance of every resource type, a cycle proves deadlock. With multiple instances, a cycle is necessary but not sufficient by itself because another instance may let a process finish.

In starvation, one process may wait indefinitely while others continue. In livelock, processes change state without useful progress. A deadlocked set cannot advance.

The four Coffman conditions for deadlock

The earlier cycle contains all four conditions. Non-shareable R1 and R2 give mutual exclusion. Holding one while requesting another gives hold and wait. No forced removal gives no preemption. The closed chain gives circular wait.

Every deadlock requires all four. Breaking any one prevents deadlock, but seeing broad signs of all four does not prove that a multi-instance system is currently deadlocked.

Deadlock prevention, avoidance, detection and recovery

These strategies differ mainly in when they act.

Ignoring deadlock is also a policy choice when its practical cost is judged lower than continuous handling.

Lock ordering is a direct prevention example. Give R1 order 1 and R2 order 2, then require increasing-order requests. P1 can no longer hold R2 and request R1, so the earlier cycle cannot form.

Safe, unsafe and deadlocked states before Banker's algorithm

A safe sequence is an order in which each process's Need can be met by current Work. When a process finishes, its Allocation returns to Work. Compute each component separately:

Need = Max - Allocation

A safe state is not deadlocked. An unsafe state may not be deadlocked now, but has no safety guarantee. Every deadlocked state is unsafe. A physically available request is refused if its provisional state is unsafe.

The safety test is:

1. Set Work = Available and Finish[i] = false for every process.

2. Find an unfinished process for which Need[i] <= Work component by component.

3. Let it finish, set Work = Work + Allocation[i], and mark it finished.

4. Repeat until all processes finish, or until no unfinished process fits.

5. Call the state safe only if every process can finish.

Banker's algorithm worked example: find and verify a safe sequence

Use three processes and resource types A and B. Total resources are (6,3).

Total Allocation is (1+1+2, 0+1+0) = (4,1), so Available = (6,3) - (4,1) = (2,2).

Apply the safety test from Work (2,2):

1. P1 fits because Need (1,2) <= Work (2,2). It releases (1,1), so Work becomes (3,3).

2. P0 fits because (3,1) <= (3,3). It releases (1,0), so Work becomes (4,3).

3. P2 fits because (2,2) <= (4,3). It releases (2,0), so Work returns to the total (6,3).

Therefore <P1, P0, P2> is a valid safe sequence.

Test P1's request (1,1) from the original state. It is no greater than Need (1,2) or Available (2,2). Provisionally, Available becomes (1,1), P1 Allocation becomes (2,2), and P1 Need becomes (0,1). P1 can finish, giving Work = (1,1) + (2,2) = (3,3). P0 and P2 then finish, so the request can be granted.

Now test P0's request (1,1) from the same original state. It also passes Request <= Need and Request <= Available, but the provisional Available is (1,1). The remaining Needs are P0 (2,0), P1 (1,2), and P2 (2,2). None fits Work (1,1), so the provisional state is unsafe, not already deadlocked. Deny the request.

Deadlock detection and recovery when avoidance is not used

For single-instance types, a wait-for graph removes resource nodes. Draw Pi -> Pj when Pi waits for a resource held by Pj. The opening example becomes P0 -> P1 and P1 -> P0; the cycle identifies deadlock.

With multiple instances, initialise Work = Available. A process holding nothing cannot belong to the deadlocked set, so set its Finish flag to true when Allocation is zero; set Finish to false for every process holding resources. While an unfinished row has Request <= Work, release that row's Allocation into Work and flip its Finish flag. The false flags left when the scan stalls identify the deadlocked processes. Current Request replaces the maximum Need used by Banker's safety test.

Recovery may terminate every deadlocked process or choose victims in turn. Preempt only restorable resources; use checkpoints or rollback where supported. Count prior rollbacks in the victim cost to avoid repeatedly choosing one process.

How deadlock questions test reasoning, plus the traps to check

Typical tasks ask which condition a policy breaks, whether a cycle proves deadlock, how to compute Need and Available, whether a safe sequence exists, and whether a request preserves safety.

Use this trap checklist:

• Do not confuse Request with Need.

• Subtract total Allocation from system totals before starting.

• Compare vectors component by component, not by their sums.

• Add a completed process's Allocation, not its Max, to Work.

• Do not call every unsafe state deadlocked.

• Do not treat a cycle as proof when a resource type has multiple instances.

Place deadlock beside scheduling and memory management with Operating Systems for GATE: How to Study Deadlocks, Scheduling and Memory. Use GATE CS Exam Preparation to choose the next subject.

Deadlock in OS: the short version and the next practice step

• Identify the complete waiting set.

• Test all four Coffman conditions.

• Read graph cycles with the instance-count caveat.

• Keep prevention, avoidance and detection distinct.

• Compute Need and Available component by component.

• Grant a request only if its provisional state retains a safe sequence.

As a retrieval check, reproduce the Work vectors for <P1, P0, P2> without looking. Then rerun P1's (1,1) and P0's (1,1) requests from the original state. Reusing the state left by the first request would answer a different problem.

Choose by what you need. GATE Guidance by Sanchit Sir gives a structured OS sequence containing Deadlock. If the theory is clear and you want OS practice, use the GATE Test Series.