Deadlock (computer science)

[4] In a communications system, deadlocks occur mainly due to loss or corruption of signals rather than contention for resources.

Then the state of the system is examined to detect that a deadlock has occurred and subsequently it is corrected.

Deadlock avoidance requires that the operating system be given in advance additional information concerning which resources a process will request and use during its lifetime.

The term was coined by Edward A. Ashcroft in a 1975 paper[18] in connection with an examination of airline booking systems.

[19] Livelock is a special case of resource starvation; the general definition only states that a specific process is not progressing.

If more than one process takes action, the deadlock detection algorithm can be repeatedly triggered.

This can be avoided by ensuring that only one process (chosen arbitrarily or by priority) takes action.

Both processes need resources to continue execution. P1 requires additional resource R1 and is in possession of resource R2 , P2 requires additional resource R2 and is in possession of R1 ; neither process can continue.
Four processes (blue lines) compete for one resource (grey circle), following a right-before-left policy. A deadlock occurs when all processes lock the resource simultaneously (black lines). The deadlock can be resolved by breaking the symmetry.
Two processes competing for two resources in opposite order.
  1. A single process goes through.
  2. The later process has to wait.
  3. A deadlock occurs when the first process locks the first resource at the same time as the second process locks the second resource.
  4. The deadlock can be resolved by cancelling and restarting the first process.
(A) Two processes competing for one resource, following a first-come, first-served policy. (B) Deadlock occurs when both processes lock the resource simultaneously. (C) The deadlock can be resolved by breaking the symmetry of the locks. (D) The deadlock can be prevented by breaking the symmetry of the locking mechanism.