Banker’s algorithm is a deadlock avoidance algorithm. It is named so because this algorithm is used in banking systems to determine whether a loan can be granted or not.
Consider there are n account holders in a bank and the sum of the money in all of their accounts is S. Everytime a loan has to be granted by the bank, it subtracts the loan amount from the total money the bank has. Then it checks if that difference is greater than S. It is done because, only then, the bank would have enough money even if all the n account holders draw all their money at once.
Banker’s algorithm works in a similar way in computers. Whenever a new process is created, it must exactly specify the maximum instances of each resource type that it needs.
Let us assume that there are n processes and m resource types. Some data structures are used to implement the banker’s algorithm. They are:
Need[i][j] = Max[i][j] - Allocation [i][j]
This describes the behavior of the system when a process makes a resource request in the form of a request matrix. The steps are:
Available = Available - Requesti Allocationi = Allocationi + Requesti Needi = Needi - Requesti
This step is done because the system needs to assume that resources have been allocated. So there will be less resources available after allocation. The number of allocated instances will increase. The need of the resources by the process will reduce. That’s what is represented by the above three operations.
After completing the above three steps, check if the system is in safe state by applying the safety algorithm. If it is in safe state, proceed to allocate the requested resources. Else, the process has to wait longer.
Work = Available Finish[i] =false for i = 0, 1, ... , n - 1.
This means, initially, no process has finished and the number of available resources is represented by the Available array.
Finish[i] ==false Needi <= Work
If there is no such i present, then proceed to step 4.
It means, we need to find an unfinished process whose need can be satisfied by the available resources. If no such process exists, just go to step 4.
Work = Work + Allocation; Finish[i] = true;
Go to step 2.
When an unfinished process is found, then the resources are allocated and the process is marked finished. And then, the loop is repeated to check the same for all other processes.
That means if all processes are finished, then the system is in safe state.