How to use the banker's algorithm calculator
- Enter the allocation matrix with one row per process and one column per resource type.
- Enter the maximum need matrix in the same shape.
- Enter the available resources on one line, in the same order.
- Optionally enter a request like `1: 1 0 2` for process 1 to see whether it can be granted. Read the state, a safe order if there is one, and the need matrix.
Formula
Need = maximum - allocation, for each process and resource
Work starts as the available resources, and a process can finish if its need is at most Work in every column
When a process finishes, its allocation is added back to Work
The state is safe if every process can finish in some order
To test a request, check that it is within the process's need and the available resources, grant it on paper, and run the safety test on the new state. If the new state is unsafe, the request must wait.
A textbook state with 5 processes and 3 resource types
With 3 3 2 available, the page finds that the state is safe, with a safe order of P1, P3, P0, P2, P4. When all processes have finished, the free resources are 10 5 7, which is the total of the system. The need of P0 is 7 4 3, because its maximum is 7 5 3 and it holds 0 1 0.
A request by P1 for 1 0 2 can be granted, and the new state is still safe with the same order. A request by P4 for 3 3 0 would leave the system unsafe, so it should wait. P0 asking for 0 5 0 is refused because it exceeds what P0 declared as its need.
Safe is not the same as free of waiting
A safe state means there is at least one order in which every process can get what it needs and finish, so a deadlock can be avoided. An unsafe state does not mean a deadlock has happened, only that it could happen if processes ask for their maximum. The algorithm avoids unsafe states by making a process wait.
The page tries the processes in order and takes the first that can finish, so it reports one safe order. Other safe orders may exist.
Using it for study
The method is a classic topic in operating systems courses. The page shows the need matrix and the order step by step, which makes it useful for checking homework by hand. In practice few systems use it, because processes rarely know their maximum needs in advance.
Related topics are scheduling, see the CPU scheduling simulator, and page replacement, see the cache replacement policy simulator. For performance with many processors, see Amdahl's law.
Assumptions and limits
- Each process declares its maximum need in advance and never asks for more than that.
- Resources are of fixed types and each unit of a type is equivalent.
- Processes release everything they hold when they finish.
- The page allows 1 to 12 processes and 1 to 8 resource types.
Frequently asked questions
What is the banker's algorithm?
It is a method for avoiding deadlock. Before granting a request, it checks that the system would still be in a safe state, in which all processes can eventually finish.
What is a safe sequence?
It is an order of the processes in which each can get its remaining needs from the resources free at that point, finish, and release what it holds.
How do I test a request?
Enter it as the process number, a colon and one number per resource. The page checks the need, the free resources and the safety of the new state.
Is an unsafe state a deadlock?
No. It is a state from which deadlock is possible, depending on what the processes ask for next.