Deadlocks in OS: Conditions, Prevention, Banker's Algorithm & Examples
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).
Deadlocks OS state trace
Deadlocks OS state trace
Event 1: a process requests a resource related to Deadlocks
Event 2: the kernel checks permissions, availability, and current state
Event 3: the scheduler or manager decides whether to run, wait, block, or fail
Event 4: the process observes the result and continues or handles the error
Deadlocks small simulation
Deadlocks small simulation
Input: P1, P2, P3
Resource/state: limited
Rule: apply the Deadlocks policy step by step
Output: show which process runs, waits, completes, or is denied
Always write the before-state and after-state for each step.
