Introduction

There are various algorithms for avoiding deadlocks. The simplest one is to get to know the maximum number of resources of each type that it may need.

Deadlock avoidance algorithm dynamically makes use of resource allocation state and makes sure that the circular wait state do not exists. The resource allocation state makes use of the maximum number of allocated and needed resources.

Safe State

  • Ensures that there is no deadlock by accordingly allocating the resources.
  • Arranged in a safe sequence so that say process Pi and Pj be two a process and they are being allocated resources such that Pi can still be satisfied with currently available resources and resources from Pj provided j < i
  • safe state = not deadlocked
  • unsafe state  != deadlock

Resource Allocation Graph

  • Claim Edge : A claim edge say Pi to resource say Rj is said to exists if a process may request for the resource in future. It is represented using a dashed line.
  • Cycle Detection Algorithm
    • Algorithm to detect the cycle in a graph
    • requires n2 operations where n is the number of processes
    • if a cycle is detected then the graph is in unsafe state
    • if a cycle is not found then the graph is in safe state
  • Drawback: The resource allocation graph is not applicable to the resources with multiple instances.

Banker's Algorithm