Banker's algorithm

Last updated

Banker's algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources, and then makes an "s-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.

Contents

The algorithm was developed in the design process for the THE operating system and originally described (in Dutch) in EWD108. [1] When a new process enters a system, it must declare the maximum number of instances of each resource type that it may ever claim; clearly, that number 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:

Resources may be allocated to a process only if the amount of resources requested is less than or equal to the amount available; otherwise, the process waits until resources are available.

Some of the resources that are tracked in real systems are memory, semaphores and interface 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. [2] 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:

Note: Need[i,j] = Max[i,j] - Allocation[i,j]. n=m-a.

Example

Total system resources are: 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 (possibly needed 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 resource it only makes it easier on the system. A safe state is considered to be the decision maker if it's going to process ready queue.

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.

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 needs 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
  2. 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
  3. 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 5 A, 3 B, 6 C and 6 D resources
  4. 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
  5. Because all processes were able to terminate, this state is safe

For an example of an unsafe state, consider what would happen if process 2 was holding 1 units 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 straightforward 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 1 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 1 B and 3 C resources and terminate
    4. Therefore, this new state is safe
  2. Since the new state is safe, grant the request


Final example: 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 5 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
importnumpyasnpn_processes=int(input("Number of processes? "))n_resources=int(input("Number of resources? "))available_resources=[int(x)forxininput("Claim vector? ").split(" ")]currently_allocated=np.array([[int(x)forxininput(f"Currently allocated for process {i+1}? ").split(" ")]foriinrange(n_processes)])max_demand=np.array([[int(x)forxininput(f"Maximum demand from process {i+1}? ").split(" ")]foriinrange(n_processes)])total_available=available_resources-np.sum(currently_allocated,axis=0)running=np.ones(n_processes)# An array with n_processes 1's to indicate if process is yet to runwhilenp.count_nonzero(running)>0:at_least_one_allocated=Falseforpinrange(n_processes):ifrunning[p]:ifall(i>=0foriintotal_available-(max_demand[p]-currently_allocated[p])):at_least_one_allocated=Trueprint(f"{p} is running")running[p]=0total_available+=currently_allocated[p]ifnotat_least_one_allocated:print("Unsafe")break# exitelse:print("Safe")

Limitations

Like the 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.

Related Research Articles

<span class="mw-page-title-main">Mutual exclusion</span> In computing, restricting data to be accessible by one thread at a time

In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurrent thread of execution is already accessing said critical section, which refers to an interval of time during which a thread of execution accesses a shared resource or shared memory.

<span class="mw-page-title-main">Memory management</span> Computer memory management methodology

Memory management is a form of resource management applied to computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when no longer needed. This is critical to any advanced computer system where more than a single process might be underway at any time.

<span class="mw-page-title-main">Deadlock (computer science)</span> State in which members are blocking each other

In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lock. Deadlocks are a common problem in multiprocessing systems, parallel computing, and distributed systems, because in these contexts systems often use software or hardware locks to arbitrate shared resources and implement process synchronization.

In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple threads and avoid critical section problems in a concurrent system such as a multitasking operating system. Semaphores are a type of synchronization primitive. A trivial semaphore is a plain variable that is changed depending on programmer-defined conditions.

<span class="mw-page-title-main">Cache coherence</span> Computer architecture term concerning shared resource data

In computer architecture, cache coherence is the uniformity of shared resource data that ends up stored in multiple local caches. When clients in a system maintain caches of a common memory resource, problems may arise with incoherent data, which is particularly the case with CPUs in a multiprocessing system.

In computer science, rate-monotonic scheduling (RMS) is a priority assignment algorithm used in real-time operating systems (RTOS) with a static-priority scheduling class. The static priorities are assigned according to the cycle duration of the job, so a shorter cycle duration results in a higher job priority.

<span class="mw-page-title-main">Dining philosophers problem</span> Problem used to illustrate synchronization issues and techniques for resolving them

In computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them.

In computer science, a smart pointer is an abstract data type that simulates a pointer while providing added features, such as automatic memory management or bounds checking. Such features are intended to reduce bugs caused by the misuse of pointers, while retaining efficiency. Smart pointers typically keep track of the memory they point to, and may also be used to manage other resources, such as network connections and file handles. Smart pointers were first popularized in the programming language C++ during the first half of the 1990s as rebuttal to criticisms of C++'s lack of automatic garbage collection.

In computer science, a ticket lock is a synchronization mechanism, or locking algorithm, that is a type of spinlock that uses "tickets" to control which thread of execution is allowed to enter a critical section.

In computer graphics, the Liang–Barsky algorithm is a line clipping algorithm. The Liang–Barsky algorithm uses the parametric equation of a line and inequalities describing the range of the clipping window to determine the intersections between the line and the clip window. With these intersections it knows which portion of the line should be drawn. So this algorithm is significantly more efficient than Cohen–Sutherland. The idea of the Liang–Barsky clipping algorithm is to do as much testing as possible before computing line intersections.

The air traffic control radar beacon system (ATCRBS) is a system used in air traffic control (ATC) to enhance surveillance radar monitoring and separation of air traffic. It consists of a rotating ground antenna and transponders in aircraft. The ground antenna sweeps a narrow vertical beam of microwaves around the airspace. When the beam strikes an aircraft, the transponder transmits a return signal back giving information such as altitude and the Squawk Code, a four digit code assigned to each aircraft that enters a region. Information about this aircraft is then entered into the system and subsequently added to the controller's screen to display this information when queried. This information can include flight number designation and altitude of the aircraft. ATCRBS assists air traffic control (ATC) surveillance radars by acquiring information about the aircraft being monitored, and providing this information to the radar controllers. The controllers can use the information to identify radar returns from aircraft and to distinguish those returns from ground clutter.

A "production system" is a computer program typically used to provide some form of artificial intelligence, which consists primarily of a set of rules about behavior, but it also includes the mechanism necessary to follow those rules as the system responds to states of the world. Those rules, termed productions, are a basic representation found useful in automated planning, expert systems and action selection.

Robot software is the set of coded commands or instructions that tell a mechanical device and electronic system, known together as a robot, what tasks to perform. Robot software is used to perform autonomous tasks. Many software systems and frameworks have been proposed to make programming robots easier.

A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers.

Software incompatibility is a characteristic of software components or systems which cannot operate satisfactorily together on the same computer, or on different computers linked by a computer network. They may be components or systems which are intended to operate cooperatively or independently. Software compatibility is a characteristic of software components or systems which can operate satisfactorily together on the same computer, or on different computers linked by a computer network. It is possible that some software components or systems may be compatible in one environment and incompatible in another.

In theoretical computer science and network routing, Suurballe's algorithm is an algorithm for finding two disjoint paths in a nonnegatively-weighted directed graph, so that both paths connect the same pair of vertices and have minimum total length. The algorithm was conceived by John W. Suurballe and published in 1974. The main idea of Suurballe's algorithm is to use Dijkstra's algorithm to find one path, to modify the weights of the graph edges, and then to run Dijkstra's algorithm a second time. The output of the algorithm is formed by combining these two paths, discarding edges that are traversed in opposite directions by the paths, and using the remaining edges to form the two paths to return as the output. The modification to the weights is similar to the weight modification in Johnson's algorithm, and preserves the non-negativity of the weights while allowing the second instance of Dijkstra's algorithm to find the correct second path.

Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs the queue will be searched for the process closest to its deadline. This process is the next to be scheduled for execution.

The Chandy–Misra–Haas algorithm resource model checks for deadlock in a distributed system. It was developed by K. Mani Chandy, Jayadev Misra and Laura M Haas.

<span class="mw-page-title-main">Centripetal Catmull–Rom spline</span> Variant form of the Catmull-Rom spine

In computer graphics, the centripetal Catmull–Rom spline is a variant form of the Catmull–Rom spline, originally formulated by Edwin Catmull and Raphael Rom, which can be evaluated using a recursive algorithm proposed by Barry and Goldman. It is a type of interpolating spline defined by four control points , with the curve drawn only from to .

In computer science, interference freedom is a technique for proving partial correctness of concurrent programs with shared variables. Hoare logic had been introduced earlier to prove correctness of sequential programs. In her PhD thesis under advisor David Gries, Susan Owicki extended this work to apply to concurrent programs.

References

  1. ↑ Dijkstra, Edsger W. Een algorithme ter voorkoming van de dodelijke omarming (EWD-108) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. ( transcription ) (in Dutch; An algorithm for the prevention of the deadly embrace )
  2. ↑ Silberschatz, Galvin, & Gagne (2013). Operating System Concepts, 9th Edition. Wiley. p. 330. ISBN   978-1-118-06333-0.{{cite book}}: CS1 maint: multiple names: authors list (link)

Further reading


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.