Thursday, April 5, 2012

banker's algorithm explained

The 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 a "safe-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.

http://en.wikipedia.org/wiki/Banker%27s_algorithm

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.

http://www.fearme.com/misc/alg/node149.html








  • Dijkstra's Bankers Algorithm


I have four processes and 10 instances of the same resource.

Resources Allocated | Resources Needed
Process A-1 -6
Process B -1 -5
Process C -2 -4
Process D -4- 7



We have 10 available resources and 8 of them allocated.This means we have 2 free unallocated resources.
We go through all processes to see how much resources all processes need.Process C can claim the least resource needed which is 2.Process D needs 3,Process B 4,Process A 5.

When we finish process C with 4 resources we have 4 resources available.Then we  can finish process B which needs 5 resources.Then process A which needs 5 ,and finally process D which needs 7 resources.


Resources Allocated-Resources Needed-Claim
Process A 1-6-5
Process B 1-5-4
Process C 2-4-2
Process D 4-7-3



http://stackoverflow.com/questions/1734977/dijkstras-bankers-algorithm


  • Banker's Algorithm


Assume we have nine tape drives. Consider whether or not the following states are safe or unsafe.
State    Current Loan  Maximum Need
Process A                0              3
Process B                3              5
Process C                4              7
  • Since only 7 (3+4) tape drives are currently on loan (allocated), two (2) tape drives are still available.
  • Process B can finish with only two additional tape drives.
  • Once Process B is done, it will release all 5 tape drives, making the number of available tape drives = 5.
  • With only three of these tape drives, either Process A or Process C may complete and release its tape drives.
  • This means that there are two possible safe sequences: and .
  • Thus, we say that this is a safe state.


Again assume we have nine tape drives. Consider whether or not the following states are safe or unsafe.
State    Current Loan  Maximum Need
Process A                5              7
Process B                2              5
Process C                1              3
  • Since 8 (5+2+1) tape drives are currently on loan (allocated), only one tape drive is still available.
  • None of the three processes can complete with only one additional tape drive.
  • This means that there are no safe sequences possible.
  • Thus, we say that this is an unsafe state.

No comments:

Post a Comment