Deadlocks: Detection, Prevention and Avoidance For students.

A deadlock is a situation in an operating system where two or more processes are each waiting for a resource that another one of them holds, so none of them can ever move forward. Imagine two people each holding one end of a rope and waiting for the other end — nothing changes until someone lets go. Deadlocks can freeze programs, hang a whole computer, or block database transactions.

This matters because modern systems run hundreds of processes sharing printers, files, memory, and database locks at the same time. If the operating system has no strategy for deadlocks, a single unlucky ordering of requests can hang critical software like banking systems or hospital databases. That is why every OS designer must choose one of three strategies: detect deadlocks, prevent them, or avoid them.

Key Concepts

• The four Coffman conditions: a deadlock is possible only when all four hold at once — mutual exclusion (one process per resource), hold and wait (holding one resource while waiting for another), no preemption (resources are released only voluntarily), and circular wait (processes form a waiting circle).
• Resource allocation graph: circles are processes, squares are resources; an arrow process→resource means "waiting for", resource→process means "holding". A cycle means deadlock when each resource has a single copy.
• Detection: the OS periodically scans the graph for cycles and acts when it finds one.
• Prevention: the system is designed so that at least one Coffman condition can never occur.
• Avoidance: the OS tests every request with the Banker's algorithm and grants only safe ones.
• Recovery: after detection, kill a process in the cycle or preempt its resources and roll it back.

How It Works

1. Prevention by breaking hold-and-wait: require each process to request everything it will ever need up front, before it starts.
2. Prevention by ordering: number every resource type and force requests in increasing order — a waiting circle can then never form.
3. Avoidance with the Banker's algorithm: before granting a request, simulate the grant and check that the processes can still all finish in some order (a safe sequence).
4. Detection and recovery: scan the graph for cycles at intervals; on finding one, pick a victim process (usually the cheapest to restart), kill it or roll it back, and the survivors proceed.

Each strategy has a price: prevention wastes resources, avoidance needs every process to declare its maximum needs in advance, and detection lets deadlocks happen and then cleans up.

Worked Example

A system has 12 identical resource units. P0 holds 5 and may need up to 10 (still needs 5); P1 holds 2 and may need up to 4 (needs 2); P2 holds 2 and may need up to 9 (needs 7). Held total = 9, so available = 12 − 9 = 3. Run the Banker's safety check:

1. P0 needs 5, but only 3 are free — cannot finish.
2. P1 needs 2, and 2 ≤ 3 — it finishes and releases 2: free becomes 5.
3. P0 needs 5, and 5 ≤ 5 — it finishes and releases 5: free becomes 10.
4. P2 needs 7, and 7 ≤ 10 — it finishes.

The safe sequence P1, P0, P2 exists, so the state is safe and a matching request would be granted.

Common Misconceptions

• "Deadlock and starvation are the same." In a deadlock nobody can proceed; in starvation one process is repeatedly skipped while others keep running.
• "Prevention and avoidance are the same." Prevention statically forbids a Coffman condition; avoidance dynamically tests each request.
• "Detection stops deadlocks from happening." Detection finds a deadlock after it forms; only prevention and avoidance stop one from forming.

Real-World Applications

• Database systems, where transactions lock rows and use wait-die or wound-wait schemes.
• Operating system kernels, which enforce lock-ordering rules on internal locks.
• Automated factories, where robots share tools and workstations.
• Multithreaded web servers, where threads compete for connection pools and caches.

Deadlocks need all four Coffman conditions at once. Prevention breaks a condition up front, avoidance checks every request with the Banker's algorithm, and detection finds cycles and recovers. Picking the right strategy keeps shared resources flowing without freezes.