Banker's algorithm
Banker's algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources, and then makes a check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.
Source:
Wikipedia
Simulation
On this page you find an interactive simulation of Banker's Algorithm.
All values in blue can be interactivley changed. When you hover over a blue value, the background becomes yellow and you can update the value by pressing a numeric key. If you input an invalid number the background for a short while changes to red and then goes back to yellow with the value unchanged.
For example, you can change the below value to anything between 0 and 9 except for 7.
Try to change me:
0
State 0 (Safe)
Number of resources
4
Number of tasks
4
Reset
This is the Banker's algorithm safety check of State 0.
| Max | Allocation | Need | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Task | A | B | C | D | A | B | C | D | A | B | C | D | |
| 0 | 1 | 0 | 2 | 3 | 0 | 0 | 0 | 1 | 1 | 0 | 2 | 2 | done |
| 1 | 1 | 0 | 2 | 2 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | done |
| 2 | 3 | 3 | 3 | 4 | 1 | 3 | 0 | 0 | 2 | 0 | 3 | 4 | done |
| 3 | 4 | 4 | 3 | 4 | 2 | 1 | 0 | 0 | 2 | 3 | 3 | 4 | done |
| Available | |||||
|---|---|---|---|---|---|
| Step | A | B | C | D | Choice |
| 1 | 2 | 0 | 2 | 2 | 0 (1) |
| 2 | 2 | 0 | 2 | 3 | 1 |
| 3 | 3 | 0 | 3 | 4 | 2 |
| 4 | 4 | 3 | 3 | 4 | 3 |
| 5 | 6 | 4 | 3 | 4 | SAFE |
State 0 is
safe!
Request (Valid)
Request
(
A
2
,
B
0
,
C
0
,
D
0
)
by task
3
Check if the request is valid:
Request
(2, 0, 0, 0)
Request
(2, 0, 0, 0)
≤
≤
Avalable
(2, 0, 2, 2)
Need
(2, 3, 3, 4)
True
True
The request is valid.
State 0 (Safe)
The request (2, 0, 0, 0)
by task 3 is valid, but may granting the request potentially cause a deadlock in the future?
If the request is granted, we will subtract the request from Available (Step 1), subtract the request from the Need of task 3 and add the request to the Allocation of task 3. Before we make this calculation, let's highlight the values in State 0 that would need to be updated.
| Max | Allocation | Need | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Task | A | B | C | D | A | B | C | D | A | B | C | D | |
| 0 | 1 | 0 | 2 | 3 | 0 | 0 | 0 | 1 | 1 | 0 | 2 | 2 | done |
| 1 | 1 | 0 | 2 | 2 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | done |
| 2 | 3 | 3 | 3 | 4 | 1 | 3 | 0 | 0 | 2 | 0 | 3 | 4 | done |
| 3 | 4 | 4 | 3 | 4 | 2 | 1 | 0 | 0 | 2 | 3 | 3 | 4 | done |
| Available | |||||
|---|---|---|---|---|---|
| Step | A | B | C | D | Choice |
| 1 | 2 | 0 | 2 | 2 | 0 (1) |
| 2 | 2 | 0 | 2 | 3 | 1 |
| 3 | 3 | 0 | 3 | 4 | 2 |
| 4 | 4 | 3 | 3 | 4 | 3 |
| 5 | 6 | 4 | 3 | 4 | SAFE |
State 1 (Unsafe)
This is the Banker's algorithm safety check of State 1 with values changed when transitioning from State 0 to State 1 highlighted.
| Max | Allocation | Need | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Task | A | B | C | D | A | B | C | D | A | B | C | D | |
| 0 | 1 | 0 | 2 | 3 | 0 | 0 | 0 | 1 | 1 | 0 | 2 | 2 | done |
| 1 | 1 | 0 | 2 | 2 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | done |
| 2 | 3 | 3 | 3 | 4 | 1 | 3 | 0 | 0 | 2 | 0 | 3 | 4 | |
| 3 | 4 | 4 | 3 | 4 | 4 | 1 | 0 | 0 | 0 | 3 | 3 | 4 | |
| Available | |||||
|---|---|---|---|---|---|
| Step | A | B | C | D | Choice |
| 1 | 0 | 0 | 2 | 2 | 1 |
| 2 | 1 | 0 | 3 | 3 | 0 |
| 3 | 1 | 0 | 3 | 4 | UNSAFE |
Request (Denied)
State 1 is not safe and may cause a deadlock in the future. The reuest is denied.