Deadlock

A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, so neither ever does. It is often seen in a paradox, like the chicken or the egg.

Deadlock detection

Often neither deadlock avoidance nor deadlock prevention may be used. Instead deadlock detection and clean up is used by employing an algorithm that tracks the circular waiting and kills one or more of the processes such that the deadlock is removed. It should be noted that this problem is undecidable in general, because the halting problem can be rephrased as a deadlock scenario. In specific environments, using specific means of locking resources, deadlock detection may be decidable; in the general case, however, it is not possible to distinguish between algorithms that are merely waiting for a very unlikely set of circumstances to occur and algorithms that will never finish due to deadlock.

Related Topics:
Avoidance - Prevention - Detection - Undecidable - Halting problem

~ ~ ~ ~ ~ ~ ~ ~ ~ ~