Deadlock; necessary conditions with examples

Deadlock

A set of processes is in deadlock if each process in the set is waiting for an event (usually the release of a resource) that only another process in the set can cause. None of them can proceed, so all wait forever.

Example: process P holds a printer and requests a scanner; process Q holds the scanner and requests the printer. Neither can continue.

Necessary (Coffman) conditions

All four must hold together for deadlock.

1. Mutual exclusion: a resource can be used by only one process at a time. Example: a printer; if P is printing, Q must wait.
2. Hold and wait: a process holding at least one resource is waiting to acquire more resources held by others. Example: P holds the printer and waits for the scanner.
3. No preemption: a resource cannot be forcibly taken from a process; it is released only voluntarily. Example: the printer cannot be taken from P mid-job.
4. Circular wait: there is a circular chain of processes, each waiting for a resource held by the next.

  P1 --waits for--> R2
  ^                  |
 held by          held by
  |                  v
  R1 <--waits for-- P2

Here P1 holds R1 and wants R2, while P2 holds R2 and wants R1: a cycle in the resource allocation graph.

Removing any one condition prevents deadlock.