Deadlock: Conditions, Prevention, Avoidance, Detection & Recovery

In multiprogramming systems, multiple processes often compete for limited system resources like CPU, memory, printers, or files. Sometimes, two or more processes end up waiting indefinitely for resources that are held by each other. This situation is known as a deadlock.

Understanding deadlocks is essential to design systems that are safe, efficient, and free from indefinite blocking.

What is a Deadlock?

A deadlock is a condition in which a group of processes are permanently blocked, each waiting for a resource that the other holds, and none of them can proceed.

Example:
Process A holds Resource 1 and waits for Resource 2. Process B holds Resource 2 and waits for Resource 1. Neither can continue, resulting in a deadlock.

Necessary Conditions for Deadlock

A deadlock can occur only if all four of the following conditions hold simultaneously:

• Mutual Exclusion: At least one resource must be held in a non-shareable mode.
• Hold and Wait: A process is holding at least one resource and waiting to acquire others held by other processes.
• No Preemption: Resources cannot be forcibly removed from the holding process; they must be released voluntarily.
• Circular Wait: A closed chain of processes exists, where each process holds one resource and waits for another held by the next process in the chain.

These conditions are necessary but not sufficient. If even one is broken, a deadlock can be prevented.

Deadlock Prevention

Deadlock prevention aims to eliminate one or more of the necessary conditions, ensuring that a deadlock cannot occur.

Examples:

• Prevent Hold and Wait: Require all resources to be requested at once before execution.
• Allow Preemption: If a process is waiting, forcibly take resources from others.
• Avoid Circular Wait: Impose a global ordering on resource acquisition (e.g., always request resources in a specific order).

Drawback:

Deadlock prevention may lead to low resource utilization and reduced concurrency, as it restricts how resources are requested.

Deadlock Avoidance – Banker’s Algorithm

Deadlock avoidance strategies ensure the system never enters an unsafe state.

Banker’s Algorithm is the most famous deadlock avoidance technique. It works by simulating whether granting a resource request leads the system into a safe state.

Key Concepts:

• The system asks: “If I grant this resource, can all processes still complete eventually?”
• If yes, the state is safe, and the request is approved.
• If no, the request is denied temporarily.

Analogy:

Like a banker who lends money only if it’s guaranteed that all clients can eventually pay back without causing a crisis.

Drawback:

Requires prior knowledge of maximum resource requirements of each process, which is not always practical.

Deadlock Detection and Recovery

If a system does not use prevention or avoidance, it must include a method to detect and recover from deadlocks.

Detection:

• Periodically check for circular wait conditions using a Resource Allocation Graph or wait-for graph.
• Involves checking if a cycle exists in resource dependencies.

Recovery:

Once a deadlock is detected, the system must break it. Possible strategies include:

• Terminate Processes: Kill one or more processes involved in the deadlock.
• Resource Preemption: Take resources away from some processes.
• Rollback: Roll processes back to a safe state and restart.

Drawback:

• Killing processes or forcibly removing resources may lead to data loss or inconsistency.
• Frequent detection checks can be resource-intensive.