0.7.1 Dijkstra's Banker's Algorithm for Deadlock Prevention
The Banker's Algorithm is a strategy for deadlock prevention.
In an operating system, deadlock is a state in which two or more
processes are "stuck" in a circular wait
state. All deadlocked processes are waiting for resources held by
other processes. Because most systems are non-preemptive (that
is, will not take resources held by a process away from it), and
employ a hold and wait
method for dealing with system resources (that is, once a process gets
a certain resource it will not give it up voluntarily), deadlock is a
dangerous state that can cause poor system performance.
One reason this algorithm is not widely used in the real world is
because to use it the operating system must know the maximum amount of
resources that every process is going to need at all times.
Therefore, for example, a just-executed program must declare up-front
that it will be needing no more than, say, 400K of memory. The
operating system would then store the limit of 400K and use it in the
deadlock avoidance calculations.
The Banker's Algorithm seeks to prevent deadlock by becoming involved
in the granting or denying of system resources. Each time that a
process needs a particular non-sharable resource, the request
must be approved by
The banker is a conservative loaner. Every time that a process makes
a request of for a resource to be ``loaned'' the banker takes a careful
look at the bank books and attempts to determine whether or not a
deadlock state could possibly arise in the future if the loan request
This determination is made by ``pretending'' to grant the request and
then looking at the resulting post-granted request system state.
After granting a resource request there will be an amount of that
resource left free in the system, f. Further, there may be other
processes in system. We demanded that each of these other processes
state the maximum amount of all system resources they needed to
terminate up-front so, therefore, we know how much of each resource
every process is holding and has claim to.
If the banker has enough free resource to guarantee that even one
process can terminate, it can then take the resource held by that
process and add it to the free pool. At this point the banker can
look at the (hopefully) now larger free pool and attempt to guarantee
that another process will terminate by checking whether its claim can be met. If the banker can guarantee that all jobs in
system will terminate, it approves the loan in question.
If, on the other hand, at any point in the reduction the banker cannot
guarantee any processes will terminate because there is not enough
free resource to meet the smallest claim, a state of deadlock can
ensue. This is called an unsafe state. In this case the loan
request in question is denied and the requesting process is usually
The efficiency of the Banker's algorithm depends greatly on how it is
implemented. For example, if the bank books are kept sorted by
process claim size, adding new process information to the table is
O(n) but reducing the table is simplified. However if the table is
kept in no order, adding a new entry is O(1) however reducing the
table is less efficient.