The Banker's Algorithm for Deadlock Avoidance

• Assume N Processes $P_i$, M Resources $R_j$
• Availability vector $Avail_j$, units of each resource (initialized to maximum, changes dynamically)
• Let $Max_{ij}$ be an $N\times M$ matrix
• $Max_{ij}=L$ means Process $P_i$ will request at most $L$ units of $R_j$
• $Hold_{ij}$ Units of $R_j$ currently held by $P_i$
• $Need_{ij}$ Remaining need by $P_i$ for units of $R_j$
• $Need_{ij}= Max_{ij} - Hold_{ij}$, for all $i,j$
• Resource Request
  • At any instance, $P_i$ posts its request for resources in vector $REQ_j$ (i.e., no hold-and-wait)
  • Step 1: verify that a process matches its needs.
    if $REQ_j > Need_{ij}$ abort -error, impossible
  • Step 2: check if the requested amount is available.
    if $REQ_j > Avail_j$ goto Step 1 -Pi must wait
  • Step 3: provisional allocation (i.e., guess and check).
    $Avail_j = Avail_j - REQ_j$
    $Hold_{ij} = Hold_{ij} + REQ_j$
    $Need_{ij} = Need_{ij} - REQ_j$
    if isSafe() then grant resources (system is safe) else cancel allocation; goto Step 1-Pi must wait
• isSafe
  • Find out whether the system is in a safe state. Work and Finish are two temporary vectors.
  • Step 1: initialize.
    $Work_j = Avail_j$ for all $j$; $Finish_i = false$ for all $i$
  • Step 2: find a process $P_i$ such that
    $Finish_i = false$ and $Need_{ij}\le Work_j$, for all $j$
    if no such process, goto Step 4
  • Step 3: $Work_j = Work_j + Hold_{ij}$
    (i.e., pretend it finishes and frees up the resources)
    $Finish_i = true$ goto Step 2
  • Step 4: if $Finish_i = true$ for all $i$
    then return true-yes, the system is safe
    else return false-no, the system is NOT safe
• What is safe?
  • Safe with respect to some resource allocation
    • very safe
      $NEED_i \le AVAIL$ for all Processes $P_i$. Processes can run to completion in any order.
    • safe (but take care)
      $NEED_i > AVAIL$ for some $P_i$
      $NEED_i \le AVAIL$ for at least one $P_i$ such that There is at least one correct order in which the processes may complete their use of resources.
    • unsafe (deadlock inevitable)
      $NEED_i > AVAIL$ for some $P_i$
      $NEED_i \le AVAIL$ for at least one $P_i$ But some processes cannot complete successfully.
    • deadlock
      $NEED_i > AVAIL$ for all $P_i$ Processes are already blocked or will become so as they request a resource.