Search

       
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.

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 is approved.

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 blocked.  

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.