the banker's algorithm
/ DYKE-struh (Dijkstra) /
Picture a banker with limited cash who has promised credit lines to several customers. Each customer states the maximum they could ever borrow. The banker hands out money piece by piece, but before honoring any withdrawal she mentally checks: 'If I give this out, can I still, by collecting and re-lending carefully, satisfy every customer's full limit one at a time and never run dry?' Only if the answer is yes does she pay. The banker's algorithm, invented by Edsger Dijkstra, applies exactly this reasoning to a computer allocating resources.
It works with four data structures (think of resources as money): AVAILABLE (free instances of each type), MAX (the maximum each process declared it might need), ALLOCATION (what each process currently holds), and NEED = MAX minus ALLOCATION (what each could still ask for). When a process requests resources, the algorithm has two parts. First a quick legality check: the request must not exceed the process's NEED or the AVAILABLE pool. Then it PRETENDS to grant the request, and runs the SAFETY CHECK: can it find an ordering where each process's NEED is covered by AVAILABLE plus what earlier-finishing processes release? If a safe sequence exists, the grant is committed; if not, it is rolled back and the process waits, even though the resources were physically free.
The banker's algorithm is the textbook embodiment of deadlock avoidance, but be honest about its limits: it is rarely used in real general-purpose operating systems. It requires every process to declare its MAX in advance (usually unknown), assumes a fixed set of processes and resource types, and runs the safety check — which costs on the order of m times n-squared work, for m resource types and n processes — on every single request. The result is correct and elegant but too rigid and too expensive for systems where processes come and go and needs are unpredictable, which is why most OSes ignore deadlock instead.
Available = 3. NEED: P0 = 5, P1 = 2, P2 = 7. Safety check finds the sequence P1 (needs 2, take from 3) -> finishes, releases, raising AVAILABLE; then P0; then P2 — all NEEDs met in turn. So the current state is safe and a fitting request can be granted.
The safety check searches for an ordering in which every process's remaining NEED can be met.
Despite being the famous avoidance algorithm, it is almost never used in general-purpose OSes: declaring MAX up front is usually impossible, the process/resource set is assumed fixed, and the safety check runs on every request (about m times n-squared).