Deadlocks

A deadlock state occurs when two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes. Principally there are three methods for dealing with deadlocks.

• Use some protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlocks state.
• Allow the system to enter deadlock state, detect it, and then recover.
• Ignore the problem all together, and pretend that deadlocks never occur i the system. This solution is the one used by most operating system including UNIX.

A deadlock situation may occur if and only if four necessary conditions hold simultaneously in the system: mutual exclusion, hold and wait, no preemption, and circular wait. To prevent deadlocks, we ensure that at least one of the necessary conditions never holds.

Another method for avoiding deadlocks that is less stringent than the prevention algorithms is to have a prior information on how each process will be utilizing the resources. The banker's algorithms, for example, needs to know the maximum number of each resource class that may be requested by each process. Using this information, we can define a deadlocks-avoidance algorithm.

If a system does not employ a protocol to ensure that deadlocks will never occur, then a detection-and-recovery scheme must be employed. A deadlocks detection algorithms must be involved to determine whether a deadlock has occurred. If a deadlock is detected, the system must recover either by terminating some of the deadlocked process, or by preempting resources form some of the deadlocked process.

In a system that selects victims for rollback primarily on the basis of cost factors, starvation may occur. As a result, the selected process never completes its designated task.