Bankers Algorithm in OS

What is the Bankers Algorithm in OS?

A process in OS can request a resource, can use the resource, and can also release it. There comes a situation of deadlock in OS in which a set of processes is blocked because it is holding a resource and also requires some other resources at the same time that are being acquired by other processes.

So to avoid such a situation of deadlock, we have the Bankers algorithm in Operating System.

Bankers algorithm in OS is a deadlock avoidance algorithm and it is also used to safely allocate the resources to each process within the system.

It was designed by Edsger Dijkstra. As the name suggests, Bankers algorithm in OS is mostly used in the banking systems to identify whether a loan should be given to a person or not.

To understand this algorithm in detail, let us discuss a real-world scenario. Supposing there are 'n' account holders in a particular bank and the total sum of their money is 'x'.

Now, if a person applies for a loan (let's say for buying a car), then the loan amount subtracted from the total amount available in the bank gives us the remaining amount and that should be greater than 'x', then only the loan will be sanctioned by the bank.

It is done keeping in mind about the worst case where all the account holders come to withdraw their money from the bank at the same time. Thus, the bank always remains in a safe state.

Bankers algorithm in OS works similarly. Each process within the system must provide all the important necessary details to the operating system like upcoming processes, requests for the resources, delays, etc.

Based on these details, OS decides whether to execute the process or keep it in the waiting state to avoid deadlocks in the system. Thus, Bankers algorithm is sometimes also known as the Deadlock Detection Algorithm.

Implementation of Bankers Algorithm in OS

Implementing Bankers Algorithm in C++

Output:

Code Explanation

In the above C++ code, we have implemented the Bankers algorithm in OS and at the start, we have initialized allocation matrix (indicating the already allocated resources to each process of different kinds), max matrix (indicating the maximum number of resources that can be allocated to each process) and available array (indicating the currently present available resources in the system). With the help of the max matrix and allocation matrix, we will calculate need matrix (indicating the required resources to be allocated of different types by each process). $(Need)i = (MAX)i - (Allocation)i$

After that, we need to allocate resources to each process such that needed resources <= available resources for each process. If in case, available resources are less than the needed resources (say for P1), the system will move on to the next process (say P2) for allocation and will return back to P1 only after checking all the remaining processes in a loop.

If available resources are allocated to a process, the then available array will be updated and allocated resources of that process will be added to the available array. In the end, we just need to check that if all the processes are allocated the desired number of resources then the system is in a safe state and we will print the safe state sequence (indicating which process has been allocated the resources first).

There are some important data structure terms that are used in the above C++ code to implement Bankers' algorithm in OS and they are as follows: 1. Available: Example: Available[i] = k indicates that there are 'k' instances of resource type 'Rj' available within the system. 2. Max: Example: Max[i][j] = k indicates that process 'Pi' can request for maximum k instances of resource type 'Rj' within the system. 3. Allocation: Example: Allocation[i][j] = k indicates that currently process ‘Pi’ is allocated ‘k’ instances of resource type 'Rj' within the system. 4. Need: Example: Need [i, j] = k indicates that ‘Pi’ process presently requires ‘k’ instances of resource type ‘Rj’ for its execution. 5. Finish Example: Finish[i] = true indicates that process Pi has been allocated all the required number of resources by the system.

While implementing or working with Bankers algorithm in OS, it is quite important to keep a track of three things:

1. How many resources of each type, a process can request for and it is denoted by the [MAX] array.
2. How many resources of each type, a process is currently holding or allocated and it is denoted by [ALLOCATION] array.
3. How many resources of each type are currently available within the system and it is denoted by the [AVAILABLE] array.

Banker's Algorithm consists of two algorithms

1. Safety Algorithm - Safety algorithm check for the safe state of the system. If system is in safe state with any of the resource allocation permutation then deadlock can be avoided.

Steps in Safety Algorithm are:

• Step-1: Let there be two vectors Work and Finish of length m and n, respectively. Work array represents the total available resources of each type (R0,R1,R2,...Rm) and Finish array represents if the particular process Pi has finished execution or not.It can have a boolean value of true/false.

Initially all process are assumed to be unfinished so for all i Finish[i] = false.

• Step-2: Need is also an array of size m for each process.We can iterate over each process from i=0,1,2,3... to n and find if any process Pi exist for which Need[i]<Work[i] and Finish[i]=false.

If no such process exist and finish[i]= false for all process, then the system is not in safe state as there is no such process which can complete its execution from the available resources. So, the system can go in deadlock state. If Finish[i]= true for all process then proceed to step 4.

• Step-3: If any process exist for which Need<Available as in step2 then allocate those resources to that particular process and increase the allocated array for that process by Allocated[i].

Once this process is executed then proceed to step-2 and repeat for other process untill all the process complete there execution and Finish[i]= true for all i=0,1,2,3...n.

• Step-4 : If finish[i]=true for all i=0,1,2,3..n then the syatem is considered to be in safe state.

Number of operations required in the worst case in safety algorithm = $m*n^2$

2. Resource request algorithm - Resource request algorithm checks if the request can be safely granted or not to the process requesting for resources.

If a process Pi request for c instances for resource of type j then it can be represented as Request[i,j]=c.

Steps in Resource request algorithm :

• Step-1: If Request[i,j]<= Need[i,j] then it means the process is requesting for resources less than or eqaul its need for execution.If Request[i,j]>Need[i,j] then an error flag can be raised stating that process is requesting for resources beyond its need.If Request[i,j]<= Need[i,j] then proceed to step2.
• Step-2: If Request[i.j]<Available[i,j] then it means the requested resources are availble in the sytem and can be allocated to the process.If Request[i.j]<Available[i,j] then proceed to step-3 else the process has to wait for the available resource to be greater than equal to the requested resources.
• Step-3 - Now, if Request[i.j]<Available[i,j] then resource are allocated to the process Pi and the Available[i,j],Allocation[i,j]and Need[i,j] will updated as given below:

If the above resource allocation is safe then the transaction is completed and Pi is allocated its resources for execution.But, if the new state of the system is unsafe then the process Pi has to wait for the resources to fullfil its request demands and the old allocation state is again restored.

Examples of Bankers Algorithm in OS

Example 1.

In this example, we have a process table with number of processes that contains allocation field (for showing the number of resources of type: A, B and C allocated to each process in the table), max field (for showing the maximum number of resources of type: A, B, and C that can be allocated to each process) and also, the available field (for showing the currently available resources of each type in the table).

Considering the above processing table, we need to calculate the following two things:

Q.1 Calculate the need matrix? Q.2 Is the system in a safe state?

Ans.1 We can easily calculate the entries of need matrix using the formula: $(Need)i = (Max)i - (Allocation)i$

Ans.2 Let us check for safe sequence:

1. For process P0, Need = (4, 3, 2) and Available = (3, 2, 1) Clearly, the resources needed are more in number than the available ones. So, now the system will move to process the next request.

2. For Process P1, Need = (2, 2, 1) and Available = (3, 2, 1) Clearly, resources needed are less than equal to the available resources within the system. Hence, request of P1 is granted.

$Available = Available + Allocation$ = (3, 2, 1) + (2, 1, 2) = (5, 3, 3) (New Available)

3. For Process P2, Need = (6, 1, 2) and Available = (5, 3, 3) Clearly, the resources needed are more in number than the available ones. So, now the system will move to process the next request.

4. For Process P3, Need = (8, 4, 4) and Available = (5, 3, 3) Clearly, the resources needed are more in number than the available ones. So, now the system will move to process the next request.

5. For Process P4, Need = (1, 1, 1) and Available = (5, 3, 3) Clearly, resources needed are less than equal to the available resources within the system. Hence, request of P4 is granted.

$Available = Available + Allocation$ = (5, 3, 3) + (1, 1, 2) = (6, 4, 5) (New Available)

6. Now again check for Process P2, Need = (6, 1, 2) and Available = (6, 4, 5) Clearly, resources needed are less than equal to the available resources within the system. Hence, request of P2 is granted. $Available = Available + Allocation$ $= (6, 4, 5) + (3, 0, 1) = (9, 4, 6) (New Available)$

7. Now again check for Process P3, Need = (8, 4, 4) and Available = (9, 4, 6) Clearly, resources needed are less than equal to the available resources within the system. Hence, request of P3 is granted.

$Available = Available + Allocation$ $= (9, 4, 6) + (0, 2, 0) = (9, 6, 6) (New Available)$

8. Now again check for Process P0, Need = (4, 3, 2), and Available (9, 6, 6) Clearly, the request for P0 is also granted.

Safe sequence: $< P1, P4, P2, P3, P0 >$

The system has allocated all the required number of resources to each process in a particular sequence. Therefore, it is proved that the system is in a safe state.

Constraints of Bankers Algorithm

The only constraint in Banker's algorithm is that Available should always satisfy atleast on the process resource need so that the sytem doesn't land up in unsafe state and the algorithm has to roll back to original allocated state.

Advantages of Bankers Algorithm in OS

• Bankers algorithm in OS consists of [MAX] array attribute which indicates the maximum number of resources of each type that a process can hold. Using the [MAX] array, we can always find the need of resources for a particular process. $[Need] = [MAX] - [Allocated]$
• This algorithm helps in detecting and avoiding deadlock and also, helps in managing and controlling process requests of each type of resource within the system.
• Each process should provide information to the operating system about upcoming resource requests, the number of resources, delays, and about how long the resources will be held by the process before release. This is also one of the main characteristics of the Bankers algorithm.
• Various types of resources are maintained by the system while using this algorithm, that can fulfill the needs of at least one process type.
• This algorithm also consists of two other advanced algorithms for maximum resource allocation.

Disadvantages of Bankers Algorithm in OS

• Bankers algorithm in OS doesn't allow a process to change its maximum need of resources while processing.
• Another disadvantage of this algorithm is that all the processes within the system must know about the maximum resource needs in advance.
• It requires a fixed number of processes for processing and no additional process can be started in between.
• This algorithm allows all the resource requests of the processes to be granted in a fixed finite period of time, but the maximum time period is one year for allocating the resources.