Resource-Request Algorithm for Process Pi

   Request = request vector for process Pi.  If Requesti [j] = k then process Pi wants k instances of resource type Rj.

1.  If Requesti £ Needi go to step 2.  Otherwise, raise error condition, since process has exceeded its maximum claim.

2.  If Requesti £ Available, go to step 3.  Otherwise Pi  must wait, since resources are not available.

3.  Pretend to allocate requested resources to Pi by modifying the state as follows:

  Available = Available = Requesti;

  Allocationi = Allocationi + Requesti;

  Needi = Needi – Requesti;;

•If safe Þ the resources are allocated to Pi.

•If unsafe Þ Pi must wait, and the old resource-allocation state is restored

Safety Algorithm

• Let Work and Finish be vectors of length m and n, respectively.  Initialize:

Work = Available

Finish [i] = false for i - 1,3, …, n.

• Find and i such that both:

1.  Finish [i] = false
2.  Needi £ Work

      If no such i exists, go to step 4.

• Work = Work + Allocationi

                      Finish[i] = true
             go to step 2.

• If Finish [i] == true for all i, then the system is in a safe state.

Data Structures for the Banker’s Algorithm

Let n = number of processes, and m = number of resources types. 

• Available:  Vector of length m. If available [j] = k, there are k instances of resource type Rj available.
• Max: n x m matrix.  If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj.
• Allocation:  n x m matrix.  If Allocation[i,j] = k then Pi is currently allocated k instances of Rj. 
• Need:  n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task.

Need [i,j] = Max[i,j] – Allocation [i,j].

Banker's Algorithm

• Multiple instances.
• Each process must a priori claim maximum use.
• When a process requests a resource it may have to wait.  
• When a process gets all its resources it must return them in a finite amount of time.

Unsafe State In Resource-Allocation Graph

Resource-Allocation Graph For Deadlock Avoidance

Resource-Allocation Graph Algorithm

• Claim edge Pi ® Rj indicated that process Pj may request resource Rj; represented by a dashed line.
• Claim edge converts to request edge when a process requests a resource.
• When a resource is released by a process, assignment edge reconverts to a claim edge.
• Resources must be claimed a priori in the system.