Banker's algorithm calculator

Paste the Allocation and Max matrices from your exercise, one row per process starting with P0, numbers separated by spaces; row labels such as "P0:" are ignored. Put Available on the last line, or switch to "Total resources" if your exercise gives the totals, and press Calculate. "Next check" runs the safety algorithm one test at a time, with Work after each process finishes.

• Textbooks scan processes in different orders and so print different safe sequences. Choose the order your course uses, or type your own sequence under "Check your safe sequence" to see whether it is valid.
• "Test a request" applies the resource-request algorithm; if the request is granted, "Apply it" makes it the new state, so you can follow a chain of requests.

The banker's algorithm is a deadlock-avoidance algorithm for a system with n processes and m types of resource. Each process declares in advance the most of each resource it will ever hold, its Max. The system tracks what each holds now, its Allocation, and what is free, Available. A request is granted only if the system stays in a safe state: one from which some order exists in which every process can get its full Max, finish and release everything.

The name comes from a bank that never lends out its cash in a way that would leave it unable to satisfy all its customers' credit limits, provided each repays once it has drawn its full line.

1. Compute Need = Max − Allocation for every process. Set Work = Available and mark every process unfinished.
2. Find an unfinished process whose Need is at most Work in every resource type.
3. If there is one, assume it runs to completion: add its Allocation to Work, mark it finished, and go back to step 2.
4. If none is left that can run, the state is safe exactly when every process has finished; the order they finished in is a safe sequence.

Step 2 does not say which process to pick when several qualify, and the choice changes the sequence but never the verdict. For the default exercise above, scanning from P0 again after each finish gives ⟨P1, P0, P3, P2, P4⟩, carrying on from the next process gives ⟨P1, P3, P4, P0, P2⟩, and the state has 25 valid safe sequences in total, counted by trying every order. If your answer differs from the book's, check it here: it may be just as correct.

When process Pi asks for a vector Request:

1. If Request exceeds Pi's Need in any resource, it is an error: Pi has exceeded its declared maximum.
2. If Request exceeds Available, Pi must wait.
3. Otherwise, pretend to grant it: Available −= Request, Allocation += Request, Need −= Request, and run the safety algorithm. If the new state is safe, the request is granted; if not, Pi waits and the old state is restored.

All four outcomes from the default state, found by the model:

A safe state guarantees that deadlock cannot happen whatever the processes ask for, within their maxima. An unsafe state only loses that guarantee. With the same Allocation and Max as the default exercise but Available reduced to (1, 0, 0), no process's remaining Need fits, so the state is unsafe and has 0 safe sequences. Yet nothing is deadlocked: every process may still finish if it happens to ask for less than its maximum. The banker's algorithm refuses to enter such states at all, which makes it conservative: it sometimes makes a process wait when granting the request would have worked out.

General-purpose operating systems do not use the banker's algorithm. Processes do not declare their maximum needs in advance, they come and go, resources are added and removed, and running the safety check on every request costs about m × n² operations. Real systems prevent deadlock instead, for example by acquiring locks in a fixed global order, or detect it after the fact, as databases do by finding cycles in the wait-for graph and aborting one transaction. The algorithm survives in courses because it shows exactly what a safe state is, and in specialised systems where demands are known ahead of time.

Edsger Dijkstra developed the algorithm in the 1960s while designing the THE multiprogramming system, and described it in a Dutch manuscript, EWD108, whose title translates as "An algorithm for the prevention of the deadly embrace". It was first stated for a single resource type; A. Nico Habermann generalised it to several types in 1969. Coffman, Elphick and Shoshani's 1971 survey "System Deadlocks" set it alongside prevention and detection as the three approaches to deadlock.