Most current operating systems cannot prevent deadlocks. When a deadlock occurs, different operating systems respond to them in different non-standard manners. Most approaches work by preventing one of the four
Coffman conditions from occurring, especially the fourth one. Major approaches are as follows.
Ignoring deadlock In this approach, it is assumed that a deadlock will never occur. This is also an application of the
Ostrich algorithm. This approach was initially used by
MINIX and
UNIX.
Detection Under the deadlock detection, deadlocks are allowed to occur. Then the state of the system is examined to detect that a deadlock has occurred and subsequently it is corrected. An algorithm is employed that tracks resource allocation and process states, it rolls back and restarts one or more of the processes in order to remove the detected deadlock. Detecting a deadlock that has already occurred is easily possible since the resources that each process has locked and/or currently requested are known to the
resource scheduler of the operating system. •
Process termination: one or more processes involved in the deadlock may be aborted. One could choose to abort all competing
processes involved in the deadlock. This ensures that deadlock is resolved with certainty and speed. But the expense is high as partial computations will be lost. Or, one could choose to abort one process at a time until the deadlock is resolved. This approach has a high overhead because after each abort an algorithm must determine whether the system is still in deadlock. Several factors must be considered while choosing a candidate for termination, such as priority and age of the process.
Prevention Deadlock prevention works by preventing one of the four Coffman conditions from occurring. • Removing the
mutual exclusion condition means that no process will have exclusive access to a resource. This proves impossible for resources that cannot be
spooled. But even with spooled resources, the deadlock could still occur. Algorithms that avoid mutual exclusion are called
non-blocking synchronization algorithms. • The
hold and wait or
resource holding conditions may be removed by requiring processes to request all the resources they will need before starting up (or before embarking upon a particular set of operations). This advance knowledge is frequently difficult to satisfy and, in any case, is an inefficient use of resources. Another way is to require processes to request resources only when it has none; First, they must release all their currently held resources before requesting all the resources they will need from scratch. This too is often impractical. It is so because resources may be allocated and remain unused for long periods. Also, a process requiring a popular resource may have to wait indefinitely, as such a resource may always be allocated to some process, resulting in
resource starvation. (These algorithms, such as
serializing tokens, are known as the
all-or-none algorithms.) • The
no preemption condition may also be difficult or impossible to avoid as a process has to be able to have a resource for a certain amount of time, or the processing outcome may be inconsistent or
thrashing may occur. However, the inability to enforce preemption may interfere with a
priority algorithm. Preemption of a "locked out" resource generally implies a
rollback, and is to be avoided since it is very costly in overhead. Algorithms that allow preemption include
lock-free and wait-free algorithms and
optimistic concurrency control. If a process holding some resources and requests for some another resource(s) that cannot be immediately allocated to it, the condition may be removed by releasing all the currently being held resources of that process. • The final condition is the
circular wait condition. Approaches that avoid circular waits include disabling interrupts during critical sections and using a hierarchy to determine a
partial ordering of resources. If no obvious hierarchy exists, even the memory address of resources has been used to determine ordering and resources are requested in the increasing order of the enumeration. == Livelock ==