Deadlocks

A deadlock is a situation in which two or more processes are blocked and each is waiting for a resource held by another, so no one can proceed. Deadlocks are a concern in operating systems, databases, and distributed systems where resources such as mutexes, locks, files, or memory are shared.

Four conditions are necessary for a deadlock: mutual exclusion; hold and wait; no preemption; and circular wait (a closed chain of processes where each holds a resource needed by the next). If any one of these conditions is not present, a deadlock cannot occur.

Deadlocks can occur when resources are scarce and requests are granted incrementally, such as two threads each holding a lock while waiting for the other to release its lock. They may also arise in systems with poorly designed resource allocation or synchronization.

Prevention and avoidance strategies aim to break one of the four conditions. Approaches include enforcing resource ordering, ensuring a process requests all needed resources at once, using the Banker's algorithm for safe states with multiple resource instances, and allowing preemption of resources when necessary.

Detection and recovery mechanisms monitor resource allocation to identify deadlocks, for example via wait-for graphs; upon detection, the system may terminate one or more processes, roll back actions, or preempt resources to break the cycle. In distributed or complex systems, mixing prevention, detection, and careful design is common.

The dining philosophers problem is a classic illustration of deadlock and is used to study synchronization strategies that prevent or recover from it.