Deadlock - algorithms

BANKER’S ALGORITHM

Consider an example:

There are four customers: A, B, C and D, which are analogous to four processes.
The credit unit is like the resource
The banker himself is the OS
Assume each credit unit = Rs. 1000.

Not all customers need their maximum credit immediately. Hence only 10 credit units are reserved.
Process Current Max. Free = 10
A 0 6 B 0 5 C 0 4 D 0 7

How does the Algorithm Work?

When a new process (customer) enters the system, it (he) must declare the maximum number of instances of each resource type (credit units) that it (he) may need. This number may not exceed the total number of resources (credit units) in the system. When a user (customer) requests a set of resources (credit unit), the system must determine whether the allocation of these resources will leave the system in a safe state. If it will,
the resources are allocated; otherwise, the process must wait until some other process releases enough resources. Consider current allocation to various processes is as shown below.
Process Current Max. Free = 2
A 1 6 B 1 5 C 2 4 D 4 7
Would the System be in a Safe State?
‘C’ requests 2 additional units and gets them. It then runs to completion and frees all the resources it has.
Process Current Max. Free = 4
A 1 6 B 1 5 C 0 - D 4 7
Now either ‘B’ or ‘D’ can request and run to completion. Assume ‘B’ requests 4 additional units and gets them. It then runs to completion and frees all its resources. Process Current Max. Free = 5
A 1 6 B 0 - C 0 - D 4 7
Now ‘D’ runs and requests 3 additional resources and gets them. It then runs to completion and releases all its resources.Process Current Max. Free = 9
A 1 6 B 0 - C 0 - D 0 -
Finally ‘A’ runs and requests 5 additional resources and gets them. It then runs to completion and releases all its resources. Process Current Max. Free = 10
A 0 - B 0 - C 0 - D 0 -
Here is the complete banker’s algorithm:

Several data structures must be maintained to implement banker’s algorithm. Let n be the number of processes and m be the number of resource types. The data structures needed are:
• Available : A vector of length m indicates number of available resources of each type. If Available[j] = k, there are k instances of resource type Rj available.
• Max : A n*m matrix defines the maximum demand of each process. If Max[i,j]=k, then Pi may request at most k instances of resource type Rj.
• Allocation : An n*m matrix defines the number of resources of each type currently allocated to each process. If Allocation[i,j]=k, then process Pi is currently allocated k instances of resource type rj.
• Need : An n*m matrix indicates the remaining resource need of each process. If Need[i,j]=k, then Pi may need k more instances of resource type Rj to complete its task. Need[i,j]=Max[I,j] – Allocation[I,j].

After defining the data structures, algorithm moves into two phases :
• Safety Algorithm
• Resource Request Algorithm


SAFETY ALGORITHM

The safety algorithm is for finding out whether or not a system is in a safe state. It is described below:

1. Let work and finish be vectors of length m and n
respectively. Initialize work = Available and Finish[I] = false for all I = 1, 2, …, n.
2. Find an I such that both
• Finish[I] = false
• Needi <= work
If no such I exists, go to step 4.
3. Work = work + allocationi
finish[I] = true
go to step 2

4. If finish[I] = true for all I, then the system is in a safe state. This algorithm may require an order of m * n2 operations to decide whether a state is safe.

RESOURCE – REQUEST ALGORITHM

Having determined that the system is safe, this algorithm grants the requested resources to the process. Let Request i be the request vector for process Pi. If Request[j] = k, then process Pi wants k instances of resource type Rj. When this request is made, the following actions are taken:

1. If request I <= need I, then go to step 2. Otherwise raise an error condition because the process has exceeded its maximum claim.
2. If request I <= available, go to step 3. Otherwise, Pi must wait since the resources are not available.
3. Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows:
a. Available = available – request I
b. Allocation = allocation + request I
c. Need I = Need I – request I
4. Call the Safety algorithm. If the state is safe, then transaction is completed and process Pi is allocated the resources. If the new state is unsafe, then Pi must wait and the old resource allocation state is restored.