• In my previous post, I had explained Banker’s algorithm as a “Deadlock Avoidance” technique.  We discussed basic concept of bankers’ algorithm as well as features and limitations of it.
  • In this post, I am going to discuss Deadlock Detection techniques that deals with how deadlock in the system can be detected by using different techniques and methods.
  • If a system does not implement a deadlock-prevention or a deadlock avoidance algorithm then system may have deadlock.
  • In this situation the system may use:
  1. Algorithm to check the stat of the system for possible deadlock detection.
  2. An algorithm to recover from the deadlock
  • Deadlock detection and recovery scheme includes run-time costs of maintaining and executing detection algorithm as well as possible loss of data from recovery.
  • The algorithm should be capable of detecting deadlock for both:
  1. Single instance of each resource type and
  2. Several instance of each resource type.
  1. Single Instance of each Resource Type

  • If all resources have only single instance, we can use one of the form of the resource allocation graph called a wait for graph to detect deadlock
  • We can prepare this graph from the resource-allocation graph by removing the resource nodes and collapsing the appropriate edges.
  • A deadlock exists in the system if and only if the wait-for graph contains cycle.
  • An algorithm to detect a cycle in a graph requires an order of n^2 operations, where n is the number of vertices in the graph.
  • the following diagram represents resource allocation graph as well as its corresponding wait-for-graph.

Wait-for-Graph

 

  1. Several Instance of each Resource Type

  • The wait-for graph scheme is not applicable in a system with several instance of each resource type.
  • We have to use deadlock detection algorithms that can be used for such system.
  • Such algorithm uses some time-variant data structures similar to those used in banker’s algorithm.
  1. Request: An n X m matrix to represent the current request of each process.
  2. Allocation: An n X m matrix to represent the number of resources of each type currently allocated to each process.
  3. Available:  A vector of length m to represents the number of available resources of each type.
  • Execution of deadlock detection algorithm depends on two criteria:
  1. How many processes will be affected by the deadlock if deadlock occur?
  2. How often deadlock is likely to occur?
  • Execution of deadlock detection algorithm for every resource request will add extra overhead on the system.
  • In my next post, I will explain Deadlock Recovery Scheme so please stay tuned!

Leave a Reply

Your email address will not be published. Required fields are marked *