The Banker's algorithm is a resource allocation

Resource allocation

Resource allocation is used to assign the available resources in an economic way. It is part of resource management. In project management, resource allocation is the scheduling of activities and the resources required by those activities while taking into consideration both the resource...

 & deadlock

Deadlock

A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...

 avoidance algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 developed by Edsger Dijkstra

Edsger Dijkstra

Edsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...

 that tests for safety by simulating the allocation of pre-determined maximum possible amounts of all resources

Resource (computer science)

A resource, or system resource, is any physical or virtual component of limited availability within a computer system. Every device connected to a computer system is a resource. Every internal system component is a resource...

, and then makes a "safe-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.

The algorithm was developed in the design process for the THE operating system

Operating system

An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...

 and originally described (in Dutch

Dutch language

Dutch is a West Germanic language and the native language of the majority of the population of the Netherlands, Belgium, and Suriname, the three member states of the Dutch Language Union. Most speakers live in the European Union, where it is a first language for about 23 million and a second...

) in EWD108. The name is by analogy with the way that bankers account for liquidity constraints.

Algorithm

The Banker's algorithm is run by the operating system whenever a process

Process (computing)

In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...

 requests resources.
The algorithm avoids deadlock by denying or postponing the request if it determines that accepting the request could put the system in an unsafe state (one where deadlock could occur). When a new process enters a system, it must declare the maximum number of instances of each resource type that may not exceed the total number of resources in the system. Also, when a process gets all its requested resources it must return them in a finite amount of time.

Resources

For the Banker's algorithm to work, it needs to know three things:

• How much of each resource each process could possibly request
• How much of each resource each process is currently holding
• How much of each resource the system currently has available

Resources may be allocated to a process only if it satisfies the following conditions:

1. request ≤ max, else set error condition as process has crossed maximum claim made by it.
2. request ≤ available, else process waits until resources are available.

Some of the resources that are tracked in real systems are memory, semaphores

Semaphore (programming)

In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....

 and interface

Interface (computer science)

In the field of computer science, an interface is a tool and concept that refers to a point of interaction between components, and is applicable at the level of both hardware and software...

access.

The Banker's Algorithm derives its name from the fact that this algorithm could be used in a banking system to ensure that the bank does not run out of resources, because the bank would never allocate its money in such a way that it can no longer satisfy the needs of all its customers. By using the Banker's algorithm, the bank ensures that when customers request money the bank never leaves a safe state. If the customer's request does not cause the bank to leave a safe state, the cash will be allocated, otherwise the customer must wait until some other customer deposits enough.

Basic data structures to be maintained to implement the Banker's Algorithm:

Let n be the number of processes in the system and m be the number of resource types. Then we need the following data structures:

• Available: A vector of length m indicates the number of available resources of each type. If Available[j] = k, there are k instances of resource type R_j available.
• Max: An n×m matrix defines the maximum demand of each process. If Max[i,j] = k, then P_i may request at most k instances of resource type R_j.
• Allocation: An n×m matrix defines the number of resources of each type currently allocated to each process. If Allocation[i,j] = k, then process P_i is currently allocated k instance of resource type R_j.
• Need: An n×m matrix indicates the remaining resource need of each process. If Need[i,j] = k, then P_i may need k more instances of resource type R_j to complete task.

Note: Need = Max - Allocation.

Example

Assuming that the system distinguishes between four types of resources, (A, B, C and D), the following is an example of how those resources could be distributed. Note that this example shows the system at an instant before a new request for resources arrives. Also, the types and number of resources are abstracted. Real systems, for example, would deal with much larger quantities of each resource.

Total resources in system:
A B C D
6 5 7 6

Available system resources are:
A B C D
3 1 1 2

Processes (currently allocated resources):
A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 2 1 0

Processes (maximum resources):
A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0

Need= maximum resources - currently allocated resources
Processes (need resources):
A B C D
P1 2 1 0 1
P2 0 2 0 1
P3 0 1 4 0

Safe and Unsafe States

A state (as in the above example) is considered safe if it is possible for all processes to finish executing (terminate). Since the system cannot know when a process will terminate, or how many resources it will have requested by then, the system assumes that all processes will eventually attempt to acquire their stated maximum resources and terminate soon afterward. This is a reasonable assumption in most cases since the system is not particularly concerned with how long each process runs (at least not from a deadlock avoidance perspective). Also, if a process terminates without acquiring its maximum resources, it only makes it easier on the system.

Given that assumption, the algorithm determines if a state is safe by trying to find a hypothetical set of requests by the processes that would allow each to acquire its maximum resources and then terminate (returning its resources to the system). Any state where no such set exists is an unsafe state.

Example

We can show that the state given in the previous example is a safe state by showing that it is possible for each process to acquire its maximum resources and then terminate.

1. P1 acquires 2 A, 1 B and 1 D more resources, achieving its maximum
   • [available resource: <3 1 1 2> - <2 1 0 1> = <1 0 1 1>]
   • The system now still has 1 A, no B, 1 C and 1 D resource available

1. P1 terminates, returning 3 A, 3 B, 2 C and 2 D resources to the system
   • [available resource: <1 0 1 1> + <3 3 2 2> = <4 3 3 3>]
   • The system now has 4 A, 3 B, 3 C and 3 D resources available
2. P2 acquires 2 B and 1 D extra resources, then terminates, returning all its resources
   • [available resource: <4 3 3 3>-<0 2 0 1>+<1 2 3 4> = <5 3 6 6>]
   • The system now has 7 A, 4 B, 5 C and 4 D resources
3. P3 acquires 1 B and 4 C resources and terminates
   • [available resource: <5 3 6 6> - <0 1 4 0> + <1 3 5 0> = <6 5 7 6>
   • The system now has all resources: 6 A, 5 B, 7 C and 6 D
4. Because all processes were able to terminate, this state is safe

Note that these requests and acquisitions are hypothetical. The algorithm generates them to check the safety of the state, but no resources are actually given and no processes actually terminate. Also note that the order in which these requests are generated – if several can be fulfilled – doesn't matter, because all hypothetical requests let a process terminate, thereby increasing the system's free resources.

For an example of an unsafe state, consider what would happen if process 2 was holding 1 more unit of resource B at the beginning.

Requests

When the system receives a request for resources, it runs the Banker's algorithm to determine if it is safe to grant the request. The algorithm is fairly straight forward once the distinction between safe and unsafe states is understood.

1. Can the request be granted?
   • If not, the request is impossible and must either be denied or put on a waiting list
2. Assume that the request is granted
3. Is the new state safe?
   • If so grant the request
   • If not, either deny the request or put it on a waiting list

Whether the system denies or postpones an impossible or unsafe request is a decision specific to the operating system.

Example

Starting in the same state as the previous example started in, assume process 3 requests 2 units of resource C.

1. There is not enough of resource C available to grant the request
2. The request is denied

On the other hand, assume process 3 requests 1 unit of resource C.

1. There are enough resources to grant the request
2. Assume the request is granted
   • The new state of the system would be:

Available system resources
A B C D
Free 3 1 0 2

Processes (currently allocated resources):
A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 2 2 0

Processes (maximum resources):
A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0

1. Determine if this new state is safe
   1. P1 can acquire 2 A, 1 B and 1 D resources and terminate
   2. Then, P2 can acquire 2 B and 1 D resources and terminate
   3. Finally, P3 can acquire 1B and 3 C resources and terminate
   4. Therefore, this new state is safe
2. Since the new state is safe, grant the request

Finally, from the state we started at, assume that process 2 requests 1 unit of resource B.

1. There are enough resources
2. Assuming the request is granted, the new state would be:

Available system resources:
A B C D
Free 3 0 1 2

Processes (currently allocated resources):
A B C D
P1 1 2 2 1
P2 1 1 3 3
P3 1 2 1 0

Processes (maximum resources):
A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0

1. Is this state safe? Assuming P1, P2, and P3 request more of resource B and C.
   • P1 is unable to acquire enough B resources
   • P2 is unable to acquire enough B resources
   • P3 is unable to acquire enough B resources
   • No process can acquire enough resources to terminate, so this state is not safe
2. Since the state is unsafe, deny the request

Limitations

Like other algorithms, the Banker's algorithm has some limitations when implemented. Specifically, it needs to know how much of each resource a process could possibly request. In most systems, this information is unavailable, making it impossible to implement the Banker's algorithm. Also, it is unrealistic to assume that the number of processes is static since in most systems the number of processes varies dynamically. Moreover, the requirement that a process will eventually release all its resources (when the process terminates) is sufficient for the correctness of the algorithm, however it is not sufficient for a practical system. Waiting for hours (or even days) for resources to be released is usually not acceptable.

Further reading

• "Operating System Concepts" by Silberschatz, Galvin, and Gagne (pages 259-261 of the 7th edition) (1977), published as pages 308–312 of Edsger W. Dijkstra, Selected Writings on Computing: A Personal Perspective, Springer-Verlag, 1982. ISBN 0-387-90652-5

External links

• Deadlock Recovery, Avoidance and Prevention