Deadlock - Necessary and Sufficient Condition

Necessary and Sufficient Condition

A deadlock situation can arise if and only if all of the following conditions hold simultaneously in a system:

1. Mutual Exclusion: At least one resource must be non-shareable. Only one process can use the resource at any given instant of time.
2. Hold and Wait or Resource Holding: A process is currently holding at least one resource and requesting additional resources which are being held by other processes.
3. No Preemption: The operating system must not de-allocate resources once they have been allocated; they must be released by the holding process voluntarily.
4. Circular Wait: A process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource. In general, there is a set of waiting processes, P = {P₁, P₂, ..., P_N}, such that P₁ is waiting for a resource held by P₂, P₂ is waiting for a resource held by P₃ and so on till P_N is waiting for a resource held by P₁.

These four conditions are known as the Coffman conditions from their first description in a 1971 article by Edward G. Coffman, Jr. Unfulfillment of any of these conditions is enough to preclude a deadlock from occurring.