Banker's algorithm

Banker's algorithm is a resource allocation and deadlock avoidance method designed by Edsger Dijkstra during work on the THE operating system and first described, in Dutch, in the note EWD108. Each process declares in advance the largest number of instances of every resource type it may ever claim, and the system keeps three records: the maximum each process could request, what each process currently holds, and what is still available. Before granting a request the algorithm pretends to grant it and then checks whether the resulting state is safe, meaning there is some order in which every process could obtain its stated maximum, finish and give its resources back. A request that keeps the system in a safe state is granted, and one that would not is refused or made to wait. The name comes from a bank that never lends money in a way that leaves it unable to satisfy all its customers. Its main limits are that real processes rarely know their maximum needs in advance and that the number of processes is not fixed in practice.