Deadlock is a situation in an operating system where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other blocked process. Formally:

“A deadlock occurs when a process requests a resource that is held by another waiting process, and none of the processes can proceed” .

1. Necessary Conditions for Deadlock

Deadlock can arise only if all four of the following Coffman conditions hold simultaneously :

1. Mutual Exclusion – At least one resource must be held in a non-sharable mode.
2. Hold and Wait – A process holding at least one resource is waiting to acquire additional resources held by other processes.
3. No Preemption – Resources cannot be forcibly taken from a process; they must be released voluntarily.
4. Circular Wait – A circular chain of processes exists, where each process holds at least one resource needed by the next process in the chain.

A Resource Allocation Graph (RAG) can visualize these conditions: processes and resources are nodes, with request and assignment edges; a cycle in the RAG is necessary (and, in the single-instance case, sufficient) for deadlock .

2. Strategies for Preventing Deadlock

To prevent deadlocks, the system must ensure that at least one of the Coffman conditions can never hold. Common prevention schemes are:

1. Eliminate Mutual Exclusion
   • Make resources sharable wherever possible (e.g., read-only files).
   • In practice, many resources (printers, tapes) cannot be shared, so this condition is often unavoidable .
2. Prevent Hold and Wait
   • All-at-once allocation: Require each process to request all needed resources before execution begins. If any resource is unavailable, the process waits without holding any resources.
   • One-at-a-time policy: Allow requests only when the process holds no resources; after using, it must release everything before requesting more.
   • Trade-off: Can lead to low resource utilization and possible starvation .
3. Allow Preemption
   • If a process holding some resources requests another that cannot be immediately allocated, preempt (take away) all resources it currently holds, returning them to the pool. Block the process until it can reacquire all it needs.
   • Trade-off: Complex rollback, state saving, and starvation concerns .
4. Break Circular Wait
   • Impose a total ordering on all resource types (assign each a unique number).
   • Require processes to request resources in strictly increasing order of these numbers.
   • This prevents cycles in the RAG, thus making circular wait impossible .

3. Example of Prevention by Ordering

Suppose resources R₁, R₂, R₃ are assigned numbers 1, 2, 3 respectively. A process holding R₂ may only request R₃ (higher number), never R₁. This rule ensures that no cycle can form, precluding deadlock without heavy runtime checks .