Deadlock Avoidance

Requires that the system has some additional a priori information available

 Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need
 The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition
 Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes

Safe State

  • When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state
  • System is in safe state if there exists a sequence <P1, P2, …, Pn> of ALL the processes in the systems such that for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with j < I
  • That is:
    • If Pi resource needs are not immediately available, then Pi can wait until all Pj have finished
    • When Pj is finished, Pi can obtain needed resources, execute, return allocated resources, and terminate
    • When Pi terminates, Pi +1 can obtain its needed resources, and so on

  • Basic Facts

  • If a system is in safe state ⇒ no deadlocks
  • If a system is in unsafe state ⇒ possibility of deadlock
  • Avoidance ⇒ ensure that a system will never enter an unsafe state.

  • Safe, Unsafe, Deadlock State


    Avoidance algorithms

  • Single instance of a resource type => Use a resource-allocation graph
  • Multiple instances of a resource type => Use the banker’s algorithm