Deadlocks | Notion

CSS Optional — Paper-II, Section-A · P-II.III.IV · The single most numerically-tested OS subtopic — a Banker's Algorithm or Resource-Allocation-Graph question is nearly guaranteed most years.

1. The Four Necessary (Coffman) Conditions

All four must hold simultaneously for deadlock to be possible:

Mutual Exclusion — at least one resource is held in a non-shareable mode.
Hold and Wait — a process holding a resource is waiting to acquire more, currently held by others.
No Preemption — resources can only be released voluntarily, never forcibly taken.
Circular Wait — a cycle of processes exists, each waiting for a resource held by the next.

2. Resource-Allocation Graph (RAG)

An edge Pi → Rj means Pi has requested Rj; Rj → Pi means Rj is allocated to Pi.

Single-instance resources: a cycle in the RAG is both necessary and sufficient for deadlock.
Multiple-instance resources: a cycle is necessary but NOT sufficient — you must check whether a free instance exists that could break the cycle by satisfying a pending request (worked example on the numericals page below).

3. Handling Deadlock — Four Strategies

Strategy	Idea	Cost
Prevention	Design the system so at least one Coffman condition can never hold	Restricts resource-usage patterns, can hurt utilization
Avoidance	Grant a request only if the resulting state is still "safe" (Banker's Algorithm)	Needs advance knowledge of each process's maximum claim
Detection & Recovery	Let deadlocks happen; periodically run a detection algorithm (cycle search); recover by killing/preempting a process	Overhead of periodic checks + cost of recovery (lost work)
Ignorance ("Ostrich Algorithm")	Assume deadlocks are rare enough to just ignore	Simplest — used by most general-purpose OSes (Windows, Linux)

Denying conditions for Prevention (the most-asked pairing):

Deny Hold-and-Wait: require a process to request all resources it will ever need at once before starting (or release everything before requesting more).
Deny Circular Wait: impose a strict, total ordering on all resource types; processes may only request resources in strictly increasing order — this makes a cycle structurally impossible.
(Deny Mutual Exclusion and Deny No-Preemption are less commonly asked because many resources are inherently non-shareable/non-preemptible by nature — e.g. a printer.)

4. Banker's Algorithm (Deadlock Avoidance)

Data structures (n processes, m resource types): Available[m], Max[n][m] (each process's maximum claim), Allocation[n][m] (currently held), Need[n][m] = Max − Allocation.

Safety Algorithm: find some order in which every process's Need can be satisfied using Available plus resources released by processes finishing earlier in that order. If a complete such sequence exists, the state is safe.