Deadlock conditions and why all necessary

Deadlock

Deadlock is a situation in which two or more processes are blocked forever, each holding a resource and waiting for another resource held by some other process in the set.

Necessary conditions

1. Mutual exclusion: at least one resource is non-sharable, i.e. used by one process at a time.
2. Hold and wait: a process holds one resource while waiting for another.
3. No preemption: a granted resource can be released only by its holder.
4. Circular wait: processes P0, P1, …, Pn form a cycle where Pi waits for a resource held by P(i+1) and Pn waits for one held by P0.

Why all are necessary

Deadlock exists only when all four hold together, because each condition removes one way out.

• Without mutual exclusion: if resources were sharable (like read-only files), no process would ever need to wait for a resource, so no one would block.
• Without hold and wait: if a process had to request all its resources at once, or release what it holds before asking for more, it would never wait while holding something, so it could not block others.
• Without no preemption: if the OS could take a resource from a waiting process and give it to another, the blocked process would be unblocked and the chain would break.
• Without circular wait: if resources are ordered and requested in increasing order, the wait graph has no cycle; the last process in the chain always gets its resource and finishes, releasing resources for the others.

The first three conditions describe the environment in which deadlock can happen (they are policies of the system), and circular wait is the actual blocking situation. Since breaking any one of them prevents deadlock, each is necessary; since none is enough on its own, all four must hold together.

Example: P holds the printer and wants the scanner; Q holds the scanner and wants the printer. The printer and scanner are exclusive, each process holds and waits, neither resource can be preempted, and the waits form a cycle. If any one condition fails, deadlock does not occur.