The banker's algorithm is used to avoid deadlocks in resource scheduling. To use it, you have to think like a bank. Basically, you have to put each state into a separate queue. You then use four arrays: available, allocation, maximum, and need. In terms of little O notation, the banker's algorithm is o(n2m), where n is the processes and m is the resources.
Working of banker's algorithm:
Four arrays are used to store the following information in them:
- Available [m]: This array stores the total number of resources, available or allotted both.
- Allocation [
]: or Current Allocation. This array stores the current allocation to the processes.
- Maximum Allocation []: This array stores the maximum allocation of each process.
- Need Allocation []: This array is calculated on the basis of the matrix subtraction of Maximum Allocation with Current Allocation.
A system is in a safe state if there is an order in which the resource requests for all processes can eventually be granted, preventing deadlock. The Banker's algorithm works by finding one such state. If no safe state can be found, the system is at risk of deadlock and it is not in a safe state.
Algorithm Logic
The algorith works on providing resources to the lowest requirement - deadlock process first. Once the process has expired, the resources free up for the next process and so on.
See also
Banker's rounding