Deadlocks in OS — Conditions, Prevention, Banker's

What is a Deadlock?

A deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for a resource held by another process in the set. None of the processes can proceed.

Classic Example: Two processes P1 and P2, two resources R1 and R2:

P1 holds R1, waiting for R2
P2 holds R2, waiting for R1
Neither can proceed -> deadlock

Necessary Conditions for Deadlock

All four conditions must hold simultaneously for a deadlock to occur (Coffman conditions):

Condition	Description
Mutual Exclusion	At least one resource must be held in a non-shareable mode. Only one process can use the resource at a time.
Hold and Wait	A process must be holding at least one resource and waiting to acquire additional resources held by other processes.
No Preemption	Resources cannot be forcibly taken from a process. A process must voluntarily release resources.
Circular Wait	A circular chain of processes exists where each process holds a resource needed by the next process in the chain.

Resource Allocation Graph

A Resource Allocation Graph (RAG) is used to detect deadlocks:

Nodes: Processes (circles) and Resources (rectangles)
Request Edge: P -> R (process P is requesting resource R)
Assignment Edge: R -> P (resource R is assigned to process P)
Deadlock Detection: If the graph contains a cycle, there may be a deadlock. If each resource has only one instance, a cycle means deadlock. If resources have multiple instances, a cycle may or may not mean deadlock.

Deadlock Prevention

Prevent deadlock by ensuring at least one of the four necessary conditions cannot hold:

Eliminate Mutual Exclusion: Make resources shareable (not always possible - e.g., printers must be exclusive)
Eliminate Hold and Wait: Require processes to request all resources at once before starting. Or release all resources before requesting new ones. Leads to low resource utilization.
Allow Preemption: If a process holding resources requests a resource that cannot be immediately allocated, preempt all its resources. Works for resources whose state can be saved (CPU registers, memory).
Eliminate Circular Wait: Impose a total ordering on resource types. Processes must request resources in increasing order. Prevents circular chains.

Deadlock Avoidance - Banker's Algorithm

The Banker's Algorithm (Dijkstra, 1965) is a deadlock avoidance algorithm. Before granting a resource request, it checks if the resulting state is safe.

A safe state is one where there exists a safe sequence - an ordering of processes such that each process can obtain all its needed resources, execute, and release them, allowing the next process to proceed.

Data structures:

Available: Number of available instances of each resource type
Max: Maximum demand of each process for each resource
Allocation: Currently allocated resources for each process
Need: Remaining resource need = Max - Allocation

Deadlock Detection and Recovery

Detection: Allow deadlocks to occur, then detect them using a wait-for graph (simplified RAG). Periodically run a detection algorithm to find cycles.

Recovery:

Process Termination: Abort one or more deadlocked processes. Either abort all deadlocked processes (expensive) or abort one at a time until deadlock is resolved.
Resource Preemption: Preempt resources from some processes and give them to others. Must handle rollback (return process to a safe state) and starvation (same process may always be chosen as victim).