Deadlock in OS — Coffman Conditions & RAG

Section 01

The Story That Explains Deadlock

📖 Real World Analogy

The Narrow Bridge on the Mountain Pass

A narrow bridge on a Himalayan mountain road can hold only one car at a time. Two cars — one coming from Manali, one from Leh — arrive simultaneously at opposite ends. Both drivers edge forward. Neither will back up because "the other guy should reverse." Neither can move forward because the other is blocking the bridge.

Both engines run. Both drivers glare. Nobody moves. Ever.

This is a deadlock: a state where every member of a group is waiting for another member to release something they hold — while they themselves hold something the others need. No external help, no motion possible.

In an operating system, the "cars" are processes, and the "bridge" is a shared resource (printer, disk, database record, memory). When a set of processes locks up this way, the OS must either prevent it, avoid it, or detect and recover from it. That's what this chapter is about.

💡

Galvin's Definition

A set of processes is in a deadlocked state when every process in the set is waiting for an event that can be caused only by another process in the set. The event is usually acquisition of a resource. Since every process is waiting, none can trigger the event, and the wait is infinite.

Section 02

System Model — Resources and Their Life Cycle

A system consists of a finite set of resource types R₁, R₂, …, R_m. Each type has some number of identical instances: for example, "the CPU" has 8 instances (cores), "the printer" has 3 instances (three physical printers). Every process uses a resource in a strict three-step cycle.

The Request → Use → Release Cycle

A process must request a resource before using it and must release it after finishing. Request via request() syscall or wait() on a semaphore; use freely; release via release() or signal(). Deadlocks happen when a process gets stuck in step 1 (request) and never reaches step 3 (release) — while another process is stuck the same way holding what the first one needs.

Section 03

Deadlock Characterization — The Four Necessary Conditions

In 1971, Edward Coffman identified four conditions that must all hold simultaneously for a deadlock to be possible. Break any one, and deadlock cannot occur. This is the foundation of every deadlock-handling strategy.

🔒

1. Mutual Exclusion

non-sharable resource

At least one resource must be held in a non-sharable mode — only one process can use it at a time. If another wants it, it must wait. Read-only data is sharable and cannot cause deadlock. A printer, a write lock, a mutex all satisfy this condition.

🤝

2. Hold and Wait

grab some, wait for more

A process must be holding at least one resource and waiting to acquire additional resources currently held by other processes. If processes always requested all resources at once, or released everything before asking again, this condition would be broken.

🔑

3. No Preemption

must be released voluntarily

Resources cannot be forcibly taken away from a process — they can only be released voluntarily. If the OS could snatch a resource back from any process at any time (like it does with the CPU), deadlock could not persist.

🔁

4. Circular Wait

the closing loop

There must exist a set of waiting processes {P₀, P₁, …, P_n} such that P₀ waits for a resource held by P₁, P₁ for one held by P₂, and P_n for one held by P₀. A cycle.

⚠️

All Four Required

necessary AND sufficient (single-instance)

Any one of these four missing → deadlock is impossible. For systems with only one instance of each resource type, these conditions are also sufficient — a cycle in the graph guarantees deadlock. This is Coffman's classic result.

📈

Multiple Instances Caveat

cycle ≠ deadlock always

If a resource type has multiple instances, a cycle in the graph is necessary but not sufficient. The cycle may resolve itself if an instance outside the cycle becomes free. That's why real detection uses a matrix algorithm, not just cycle detection.

Section 04

🎮 Interactive — Watch a Deadlock Form Step by Step

Two processes, two resources. Each process needs both resources to finish. Watch how the wrong interleaving locks them both forever.

Deadlock Formation — click Next one action at a time

Step 0 of 5

START Two processes, two resources. Both P1 and P2 need R1 and R2 to complete. Both start ready. Watch the four Coffman conditions manifest one by one.

Section 05

Resource-Allocation Graph (RAG)

Galvin's textbook uses a graphical tool called the Resource-Allocation Graph to describe deadlock. It's a directed graph G = (V, E) where:

📋 RAG Notation

P_i

Circle. Represents a process.

R_j

Rectangle. Represents a resource type. Dots inside = instances (1 dot = 1 instance).

P_i → R_j

Request edge. Process P_i is requesting an instance of R_j.

R_j → P_i

Assignment edge. An instance of R_j is currently held by P_i.

🏆

The Cycle Rule

• If the graph has no cycle, then no deadlock exists.
• If the graph has a cycle AND each resource type has only one instance, then deadlock definitely exists.
• If the cycle involves multiple-instance resources, deadlock may or may not exist — you need the detection algorithm to be sure.

🎮 Interactive — Build a Resource-Allocation Graph

RAG Construction — three processes, three single-instance resources

Step 0 of 7

START Empty graph: 3 processes (P1, P2, P3) and 3 single-instance resources (R1, R2, R3). We'll add edges step by step until a cycle forms — proving deadlock.

Section 06

Methods for Handling Deadlocks — Overview

Galvin lists three broad strategies plus one non-strategy that most commercial systems use.

🚫

Prevention

before it happens

Structurally break at least one of the four Coffman conditions in the system design. Deadlock becomes impossible. Often expensive.

🏠

Avoidance

while running

Use extra information about future resource needs (Banker's algorithm) to grant requests only when safe. Reject risky requests even if resources are free.

🔍

Detection + Recovery

let it happen, then fix

Allow deadlocks to occur. Run a periodic detection algorithm; when found, terminate or preempt processes to break the deadlock.

🕵️

Ignore ("Ostrich")

Windows & Linux default

Pretend deadlocks never happen. If one occurs, the user notices, reboots, and life goes on. Cheap; used in most consumer OSes because deadlocks are rare and fixes are costly.

Section 07

Deadlock Prevention — Break the Four Conditions

Condition to Break	How	Cost / Problem
Mutual Exclusion	Make resources sharable (e.g. read-only files, spooling for printers).	Impossible for intrinsically non-sharable resources like mutex locks or printers writing directly.
Hold and Wait	Either request all resources at once, or release everything before requesting more.	Low utilisation (resources held but not used) and possible starvation.
No Preemption	If a process holding some resources requests more that cannot be granted, forcibly take all its current resources.	Only works for state that can be saved and restored, like CPU or memory — not printers.
Circular Wait	Impose a total ordering on all resource types and require every process to request in increasing order.	Most practical. Widely used in production kernels.

🔑

Why Ordered Locking Works

If every process acquires locks in the same global order (say mutex A always before mutex B), no circular chain can form. This one rule prevents 90% of production deadlocks and is the pattern followed in Linux, PostgreSQL, and most C++ codebases.

Section 08

Deadlock Avoidance — The Safe State Concept

A state is safe if the system can allocate resources to each process in some order and still avoid deadlock. Formally, there must exist a safe sequence ⟨P₁, P₂, …, P_n⟩ such that for each P_i, the resources P_i can still request can be satisfied by the currently available resources plus resources held by all P_j with j < i.

Safe vs Unsafe vs Deadlock — Set Relationship

⚠️

Unsafe ≠ Deadlock

An unsafe state may lead to deadlock, but doesn't have to. However, once you enter an unsafe state, the OS can no longer guarantee that deadlock will not occur. Avoidance algorithms are conservative — they reject requests that would put the system into an unsafe state even if deadlock is not certain.

📁

Coming Up Next — Banker's Algorithm

The most famous implementation of avoidance is Dijkstra's Banker's Algorithm, which uses Available, Max, Allocation, and Need matrices to run a safety check before granting every resource request. We cover it in depth — with a fully interactive walkthrough of the classic 5-process, 3-resource example — in the next tutorial.

Section 09

Deadlock Detection

If we don't prevent or avoid, we must detect. The detection algorithm scans the current state of the system periodically and answers a single question: is there a set of processes that can no longer make progress? It uses Available, Allocation, and the current Request matrix (what each process is asking for right now).

# Deadlock Detection Algorithm — for m resource types
Work    = Available
Finish  = [Allocation[i] == 0 for i in processes]  # idle procs trivially "finished"

while exists i such that Finish[i] == false and Request[i] <= Work:
    Work      = Work + Allocation[i]                    # pretend process finishes and releases
    Finish[i] = true

if exists i where Finish[i] == false:
    return "DEADLOCK: processes with Finish[i]==false are deadlocked"
else:
    return "NO DEADLOCK"

📈

Single-Instance Shortcut — Wait-For Graph

If every resource type has only one instance, we can collapse the Resource-Allocation Graph into a wait-for graph: an edge P_i → P_j means "P_i is waiting for P_j". A cycle in this simpler graph directly proves deadlock. Databases use exactly this technique.

⏰

When to Run Detection?

Run detection frequently (every 10 seconds) → catches deadlocks fast but wastes CPU. Run rarely (once an hour) → cheaper but users notice the freeze. A common heuristic: run only when CPU utilisation drops below a threshold — a plunge in utilisation often signals many processes are blocked.

Section 10

Recovery from Deadlock

Once detection reports a deadlock, we must break it. Galvin lists two families of solutions.

💀 Process Termination

Strategy	Trade-off
Kill all deadlocked processes	Clean but expensive — lots of work lost
Kill one at a time, re-check	Minimises loss but repeated detection cost
Pick lowest-priority victim	Preserves important work
Pick shortest-remaining	Least CPU wasted on restart
Pick fewest-resources-held	Frees the most for others

🔁 Resource Preemption

Concern	Solution
Which resources to preempt?	Minimise cost — pick cheap-to-restore ones
What to do with victim?	Roll back to a checkpoint state
Prevent starvation?	Cap number of times a process can be victim
Restore state after preemption?	Requires checkpointing infrastructure

🎮 Interactive — Recovery by Process Termination

Recovery — terminating processes to break the deadlock cycle

Step 0 of 4

START Three processes form a deadlock cycle. Each has a termination cost (based on work done so far, priority, or resources held). The OS must pick a victim to kill.

Section 11

Comparison — Which Method to Choose?

Method	When to Use	Overhead	Real-World Example
Prevention	Safety-critical systems	Design-time discipline	Airplane control software, medical devices
Avoidance	When max needs are known in advance	High — safety check per request	Real-time systems with known workloads
Detection	Long-running server processes	Periodic algorithm cost	Database systems (Oracle, PostgreSQL, MySQL)
Ignore	Consumer OS, deadlocks rare	Zero	Windows, macOS, Linux desktop

🔑

Galvin's Practical Advice

Most general-purpose OSes use the Ostrich algorithm: ignore the problem unless the user complains. It's cheap and deadlocks are rare in desktop use. Databases, which see deadlocks often, use detection + rollback. Real-time systems that must never fail use prevention.

Section 12

Real-World Applications

🖥️

Database Systems

Oracle, PostgreSQL, MySQL run wait-for-graph deadlock detection. When found, they pick one transaction to abort (usually the one with the least work done) and roll back.

wait-for graph, victim selection

💾

Linux Kernel Locks

Linux uses lockdep — a runtime tool that tracks lock acquisition order and warns developers when they detect a potential ordering-violation deadlock in kernel code.

lockdep, prevention by ordering

📡

Distributed Systems

Distributed deadlock is even harder because there's no global view. Solutions include timeouts, wound-wait, and cautious wait — extensions of the basic model.

wound-wait, wait-die, chord

🔄

Java's Deadlock Detection

JVM's ThreadMXBean provides findDeadlockedThreads() at runtime. Profiler tools like VisualVM highlight cycles in the object monitor wait graph.

ThreadMXBean, jstack

🛡️

Avionics & Medical

DO-178C-certified software (aviation) and IEC 62304 (medical) require formal proof of no deadlock. Prevention by resource ordering is mandated.

formal verification, ordered acquire

🎮

Game Engines

Multi-threaded engines like Unity's Job System avoid deadlock by making dependencies explicit — jobs can only wait on jobs, and a topological sort catches cycles at scheduling time.

DAG scheduling, Unity Jobs

Section 13

Golden Rules — Deadlock Handling

🔑 Galvin's Non-Negotiable Rules

A deadlock requires all four Coffman conditions to hold simultaneously: mutual exclusion, hold-and-wait, no-preemption, and circular wait. Break any one and deadlock is impossible.

The single most practical prevention technique is ordered lock acquisition — impose a global order on all locks and require every thread to acquire them in that order. Prevents 90% of production deadlocks.

In the Resource-Allocation Graph, no cycle ⇒ no deadlock. Cycle with single-instance resources ⇒ definite deadlock. Cycle with multi-instance resources ⇒ possibly deadlock — run detection.

A safe state guarantees no deadlock. An unsafe state may lead to deadlock. Deadlock is a subset of unsafe, not equal to it.

Deadlock avoidance requires each process to declare its maximum resource need in advance — often unrealistic in practice. When it is realistic, the Banker's Algorithm (covered in the next tutorial) is the classical solution.

The detection algorithm uses the current Request matrix (what processes are asking for right now) instead of a declared Max. It answers: "is the current state deadlocked?"

When choosing a victim for termination, minimise cost: pick the process with least work done, least remaining time, or lowest priority. Set a limit on how many times a process can be victimised to prevent starvation.

Most consumer operating systems use the Ostrich algorithm — pretend deadlocks don't exist. It's the right choice when deadlocks are rare and prevention is expensive.

Databases treat deadlocks as normal. Every transaction handler must be able to catch a deadlock-abort exception, back off, and retry. This is the standard pattern in Oracle, PostgreSQL, and MySQL.