OS, , ,
  • In my last post I had explained about “Deadlock Detection” techniques in which I explained how we can detect if system has deadlock or not.
  • During the deadlock detection step if we found that system has deadlock than we have to take some steps to solve the deadlock by applying different deadlock recovery techniques. So in this post I am going to focus on how a deadlock can be recovered by using some deadlock recovery techniques.
  • When a deadlock detection algorithm detects that system has deadlock then we have two options:
  1. One possibility is to inform the operator that deadlock is created and let the operator to handle it manually.
  2. Second possibility is to recover the system from deadlock automatically.
  • There are two options for breaking a deadlock.
  1. Terminate one or more process to break the circular wait (Recovery by process termination).
  2. Preempt some resources from one or more deadlocked processed

  1. Recovery by Process Termination

  • In this method we terminate one or more deadlocked process for deadlock recovery.
  • We can either terminate all deadlocked process or one process at a time until the recover from deadlock.
  1. Abort all Deadlocked Process
  • In this method, all deadlocked processes are aborted. It guarantees to break the deadlock.
  • But this method has higher cost because deadlocked processes may have done some task so, aborting them will result in loss of data and they may have to recompute later when they restart.

  1. Abort one Process at a time until Deadlock break

  • This method terminates process one by one until deadlock break but this method adds extra overhead on the system because after terminating each process deadlock detection algorithm needs to execute to check if the system has still deadlock.
  • Aborting a process may result in possible data loss if process has done some task.
  • Termination of process should be done with a minimum cost.
  • Selection of process for termination should consider the following factors:
  1. What the priority of the process is?
  2. How much work has been done and how long it would take to complete?
  3. How many and what type of resources are used by the process?
  4. How many additional resources will be required to complete?
  5. Whether the process is interactive or both?
  6. How many processes will be required to terminate?

  1. Recovery by Checkpoint and Rollback (Resource Preemption)

  • Some operating system provides deadlock recovery by using checkpoint and rollback.
  • Checkpointing is saving enough state of a process so that process can restart from that checkpoint state later.
  • Autosaving facility of a file is an example of checkpointing.
  • Cost of checkpointing depends on the implemented algorithms.If deadlock is detected, one or more processes are restarted from their last checkpoint.
  • Restarting a process from a checkpoint is called rollback.
  • Rollback is similar to familiar undo command of the windows based operating system which is used to cancel effect of last performed command.
  • Deadlock recovery is normally used where deadlocks rare and cost of recovery are low.
  • Checkpoint can also be used for reliability and reduce startup costs.