deadlock

Deadlock is a situation in a multi-process or multi-threaded system in which two or more processes are unable to proceed because each is waiting for a resource held by another.

Deadlock typically arises when four conditions are present simultaneously: mutual exclusion (resources are non-sharable), hold-and-wait (processes hold one resource while requesting others), no-preemption (resources cannot be forcibly taken), and circular wait (a closed chain of requests).

In computing, deadlocks commonly occur in operating systems, databases, and distributed systems, where multiple processes compete for limited resources such as CPU time, locks, I/O devices, or memory.

A classic illustration is the dining philosophers problem, in which linked resources (forks) can lead to circular waiting if philosophers hold one fork while waiting for another.

Strategies for dealing with deadlock are categorized as prevention, avoidance, and detection with recovery. Prevention aims to prevent at least one of the four Coffman conditions.

Prevention techniques include enforcing a fixed resource ordering, requesting all needed resources at once, preempting resources, or limiting the number of concurrent resource holders.

Avoidance requires knowledge of future requests, as in the Banker’s algorithm, which decides allocations to keep the system in a safe state.

Detection involves monitoring resource allocations and waits; a cycle in a wait-for graph indicates deadlock. Recovery may involve terminating or rolling back one or more processes, or preempting resources.

Definitions vary; some use livelock and starvation as related concepts, but deadlock specifically implies progress cessation due to mutual waiting rather than continual retries.

Deadlock handling remains a design concern in operating systems, databases, and distributed systems, influencing resource management, synchronization primitives, and transaction protocols.