Methods for Handling Deadlocks

Generally speaking, we can deal with the deadlock problem in one of three ways:

1. We can use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlock state.
   • To ensure that deadlocks never occur, the system can use either a deadlock-prevention or a deadlock-avoidance scheme.
   • Deadlock prevention provides a set of methods for ensuring that at least one of the necessary conditions (Section 1.2.1) cannot hold.
   • Design a system in such a way that the possibility of deadlock is excluded a priori (compile-time/statically, by design).
   • Deadlock avoidance requires that the OS be given in advance additional information concerning which resources a process will request and use during its lifetime. With this additional knowledge, it can decide for each request whether or not the process should wait.
   • Make a decision dynamically checking whether the request will, if granted, potentially lead to a deadlock or not. (run-time/dynamically, before it happens).
2. We can allow the system to enter a deadlock state, detect it, and recover.
   • If a system does not employ either a deadlock-prevention or a deadlock-avoidance algorithm, then a deadlock situation may arise.
   • In this environment, the system can provide an algorithm that examines the state of the system to determine whether a deadlock has occurred and an algorithm to recover from the deadlock.
   • Let deadlocks occur, detect them, and take action (run-time/dynamically, after it happens)
3. We can ignore (The Ostrich Algorithm; maybe if you ignore it, it will ignore you) the problem altogether and pretend that deadlocks never occur in the system.
   • If a system neither ensures that a deadlock will never occur nor provides a mechanism for deadlock detection and recovery, then we may arrive at a situation where the system is in a deadlocked state yet has no way of recognizing what has happened.
   • Eventually, the system will stop functioning and will need to be restarted manually.
   • In many systems, deadlocks occur infrequently (say, once per year); thus, this method is cheaper than the prevention, avoidance, or detection and recovery methods.

• Most OSs potentially suffer from deadlocks that are not even detected. Process table slots are finite resources. If a fork fails because the table is full, a reasonable approach for the program doing the fork is to wait a random time and try again.
• The maximum number of open files is similarly restricted by the size of the i-node table, so a similar problem occurs when it fills up. Swap space on the disk is another limited resource. In fact, almost every table in the OS represents a finite resource.
• The third solution is the one used by most OSs, including UNIX and Windows; it is then up to the application developer to write programs that handle deadlocks.
• If deadlocks could be eliminated for free, there would not be much discussion. The problem is that the price is high, mostly in terms of putting inconvenient restrictions on processes.
• Thus we are faced with an unpleasant trade-off between convenience and correctness. Under these conditions, general solutions are hard to find.