Deadlock in Operating Systems: Four Conditions, Banker's Algorithm, and Worked Examples

Many readers can recite the four deadlock conditions but still get stuck when the question changes shape. A cycle is mistaken for proof of deadlock, a safe state is confused with resources being available, and prevention is mixed up with avoidance. Use this decision method cold: identify the blocked set, read a resource-allocation graph, compute Need and a safe sequence, then choose the correct handling strategy. Apply each step to concrete values.

Related reading: Banker’s algorithm examples and Deadlock prevention MCQs.

Deadlock in Operating Systems: what is actually stuck

A deadlock is a set of processes in which each process waits for a resource or event that only another process in that set can release or cause. No member can progress without outside intervention. For example, P1 holds mutex L1 and requests L2, while P2 holds L2 and requests L1. This fits into the wider picture covered in Operating Systems for GATE: Deadlocks, Scheduling, Memory.

Coffman conditions for deadlock: all four must be possible

The P1 and P2 example contains all four Coffman conditions:

1. Mutual exclusion: L1 and L2 are mutexes, so each can have only one holder.

2. Hold and wait: each process keeps one lock while requesting the other.

3. No preemption: the operating system cannot safely seize a held mutex and pretend the protected update never began.

4. Circular wait: the closed chain is P1, L2, P2, L1, P1.

A deadlock requires all four conditions. Break any one, and deadlock is prevented. This checklist tells you what must be possible, but it is not a detection algorithm. In particular, when a resource type has multiple instances, finding a cycle in a resource-allocation graph does not by itself prove that the current state is deadlocked.

Use an action-based memory aid: exclusive resource, hold while asking, no forced release, closed waiting chain.

Resource-allocation graphs: when a cycle proves deadlock

In a resource-allocation graph, processes are circles, resources are squares, and dots inside a resource square show its instances. A request edge points from process to resource, such as P1 -> R2. An assignment edge points from resource to process, such as R2 -> P2.

Suppose each resource has one instance and the edges are R1 -> P1, P1 -> R2, R2 -> P2, and P2 -> R1. Tracing P1 -> R2 -> P2 -> R1 -> P1 gives a cycle. Because R1 and R2 each have exactly one instance, P1 and P2 are deadlocked.

Now give R2 two instances, one assigned to P2 and one free. P1 takes the free R2 instance, finishes, and releases R1. The graph can contain a cycle while progress remains possible. With multiple instances, a cycle is necessary but not sufficient for deadlock.

Deadlock prevention, avoidance, detection, and ignoring: choose by decision point

Prevention may require all resources upfront, breaking hold and wait; preempt and roll back only restorable resources, breaking no preemption; or impose L1 < L2 < L3 and increasing acquisition order, breaking circular wait. Mutual exclusion cannot simply be removed from an inherently non-shareable resource. Avoidance asks whether the next state stays safe. Detection asks which processes are already unable to finish.

Banker's algorithm: a complete safe-sequence and request example

Consider resource types A, B, and C with totals (10, 5, 7). Compute Need = Max - Allocation.

The row subtractions are P0: (7,5,3) - (0,1,0) = (7,4,3); P1: (3,2,2) - (2,0,0) = (1,2,2); P2: (9,0,2) - (3,0,2) = (6,0,0); P3: (2,2,2) - (2,1,1) = (0,1,1); and P4: (4,3,3) - (0,0,2) = (4,3,1).

Total Allocation is (7, 2, 5), so Available is (10,5,7) - (7,2,5) = (3,3,2). Run the safety scan:

• P1 can finish because Need (1,2,2) <= Work (3,3,2). It releases (2,0,0), so Work becomes (3,3,2) + (2,0,0) = (5,3,2).

• P3 can finish, giving (5,3,2) + (2,1,1) = (7,4,3).

• P4 can finish, giving (7,4,3) + (0,0,2) = (7,4,5).

• P0 can finish, giving (7,4,5) + (0,1,0) = (7,5,5).

• P2 can finish, giving (7,5,5) + (3,0,2) = (10,5,7).

Therefore <P1, P3, P4, P0, P2> is one valid safe sequence, not necessarily the only one.

Now test P1's request (1,0,2). It is no greater than P1's Need (1,2,2) and no greater than Available (3,3,2). Tentatively set Available to (2,3,0), P1 Allocation to (3,0,2), and P1 Need to (0,2,0). P1 can finish first and release (3,0,2), restoring Work to (5,3,2). P3, P4, P0, and P2 can then finish in the sequence above. The request may be granted. Checking Request <= Available is not enough. The provisional state must also pass the safety test.

Deadlock detection and recovery: what happens after the block

With one instance per resource type, remove the resource nodes from the resource-allocation graph to form a wait-for graph. An edge Pi -> Pj means Pi waits for a resource held by Pj. A directed process cycle identifies the deadlocked set.

With multiple instances, detection uses each process's current outstanding Request, not Max. Start Work = Available. Mark a process with zero Allocation as finished and every other process as unfinished. Repeatedly find an unfinished process with Request <= Work, mark it finishable, and add its Allocation to Work. When no more rows qualify, the unfinished processes are deadlocked.

Recovery can abort all deadlocked processes, abort one victim and rerun detection, or preempt a rollback-safe resource. Victim choice may consider work completed and resources held. Repeatedly selecting the same process causes starvation, so recovery also needs retry limits or victim history.

Deadlock questions in GATE and interviews: patterns and traps

Common questions ask you to classify a Coffman condition, interpret a graph cycle, find a safe sequence or grantable request, or calculate how many identical resources guarantee progress. If n = 3 processes and each needs at most k = 2 units of R, the guarantee is n(k - 1) + 1 = 3(1) + 1 = 4 units. With only 3 units, each process could hold one and wait for one more.

Keep four traps visible: unsafe does not mean deadlocked; a cycle proves deadlock only for single-instance resource types; Need is Max - Allocation; and free resources are not enough until the provisional state passes the safety scan. For adjacent lock correctness, read Process Synchronization and Semaphores. Then use the GATE Test Series for timed practice. The practice bank has over 160 Deadlock questions.

Deadlock in OS: the short version and next step

Use this four-step checklist:

1. Draw who holds each resource and who waits.

2. Apply the single-instance versus multi-instance cycle rule.

3. Compute Need and search for a safe sequence.

4. Identify whether the policy prevents, avoids, detects, or recovers.

Redraw both diagrams and rerun the P1 request without looking at the solution. For a full-syllabus route, continue with GATE Guidance by Sanchit Sir. To browse the wider subject, use GATE CS Exam Preparation.