Question

1. Explain how does Baker’s algorithm works? Explain all the types of pointers it has and their complete functions. [25 points]

Answer 1

Banker's algorithm:

The Banker's algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes a "S-state" check to test for possible activities, before deciding whether allocation should be allowed to continue.

WORKING PROCEDURE:

It checks if allocation of any resource will lead to deadlock or not,or is it safe to allocate a resource to a process and if not then resource is not allocated to that process. Banker's algorithm is generally used to find if a safe sequence exists or not. But here we will determine the total number of safe sequences and print all the safe sequences. Determining a safe sequence (even if there is only 1) will assure that system will not go into deadlock.

FUNCTIONS & POINTERS :

The important notations used in Banker's algorithm are

Available

Max

Allocation

Need

Let 'n' be the number of processes in the system and 'm' be the number of resource types.

1.Available:

• It is a 1-D array of size 'm' indicating the number of available resources of each type.
• Available [ j ] =k means there are 'k' instances of resource type R_j .

2.Max :

• It is a 2-D array of size 'n*m' that defines the maximum demand of each process in a system.
• Max[ i,j ] = k means process Pi  may request at most 'k' instances of resource type R_j.

3.Allocation:

• It is a 2-D array of size 'n*m' that defines the number of resources of each type currently allocated to each process.
• Allocation [ i ,j]= k means process P_i is currently allocated 'k ' instances of resource type R_j.

_{​​​​​​​4.Need:}

• It is a 2-D array of size 'n*m' that Indicates the remaining resources need of each process.
• Need [i ,j]=k means process P_i currently need 'k ' instances of resource type R_j for its execution.
• Need [i ,j] = Max [i,j] - Allocation [i,j].

Allocation_{​​​​​​i} specifies the resources currently allocated to process Pi  

and Need_i specifispecifies the additional resources that process P_i may still request to complete its task.

Banker's algorithm consists of Safety algorithm and Resource request algorithm.