Conditions for Deadlock (See Fig. 3.1)

Figure 3.1: An example to Deadlock.

• Four conditions that must hold for a deadlock to be possible:
  • 1. Mutual exclusion: processes require exclusive control of its resources (not sharing), only one process may use a resource at a time
  • 2. Hold and wait: process may wait for a resource while holding others
  • 3. No preemption: process will not give up a resource until it is finished with it. Also, processes are irreversible: unable to reset to an earlier state where resources not held
  • 4. Circular wait: each process in the chain holds a resource requested by another, there exists set {$P_0$, $P_1$, $\ldots$, $P_n$ } of waiting processes such that $P_0$ waiting for resource held by $P_1$, $P_1$ waiting for resource held by $P_2$, $\ldots$, $P_{n-1}$ waiting for resource held by $P_n$, $P_n$ waiting for resource held by $P_0$
• If any one of the necessary conditions is prevented a deadlock need not occur. For example:
  • Systems with only simultaneously shared resources cannot deadlock; Negates mutual exclusion.
  • Systems that abort processes which request a resource that is in use; Negates hold and wait.
  • Preemptions may be possible if a process does not use its resources until it has acquired all it needs; Negates no preemption.
  • Transaction processing systems provide checkpoints so that processes may back out of a transaction; Negates irreversible process.
  • Systems that prevent, detect, or avoid cycles; Negates circular wait. Often, the preferred solution.