OS-Deadlock Avoidance and Bankers Algorithm

Deadlock can be avoided by being careful when resources are allocated. The most famous deadlock avoidance algorithm is Dijkstra’s Banker’s a...

Deadlock can be avoided by being careful when resources are allocated. The most famous deadlock avoidance algorithm is Dijkstra’s Banker’s algorithm, because it involves a banker who makes loans and receives payments from a given source of capital.

DIJKSTRA’S BANKERS ALGORITHM:

Resource of the same type for example consider the allocation of a quantity, t, of identical tape drives.

1.  An operating system shares a fixed number of equivalent tape drives, t, among a fixed number of users u. Each user specifies in advance the maximum number of tape drives required during the execution of the job on the system.
2.  The operating system will accept a users request if that users maximum need for tape drives does not exceed it.
3.  A user may obtain or release tape drives one by one. Sometimes, a user may have to wait to obtain an additional tape drive, but the operating system guarantees a finite wait. The current number of tape drives allocated to a user will never exceed that user’s stated maximum need.
4.  If the operating system is able to satisfy a user’s maximum need for tape drives, then the user guarantees that the tape drives, then the user guarantees that the tape drives will be used and released to the operating system within a finite time.
5.  The current state of the system is called Safe if it is possible for the operating system to allow all current users to complete their jobs withing a finite time. If not, then the current system state is called Unsafe.

Now suppose there are n user.

Loan(i) represents user i’s current loan of tape drives. Max(i) be the maximum need of user i. Claim (i) be the current claim of a user where a user’s claim is equal to his maximum need minus the user’s current loan.

BANKER’S ALGORITHM RESOURCE ALLOCATION:

In Dijkstra’s Banker’s Algorithm “Mutual Exclusion”, “wait-for”, and “no-preemption” conditions are allowed. The system grants request that result in safe states only. A users request that would result in an unsafe state is repeatedly denied until that request can eventually be satisfied.

Weaknesses in the Bankers Algorithm:

1.  The algorithm requires fixed number of resources to allocate. Since resources require service, either because of breakdowns or maintenance. So resource cannot be fixed.
2.  The algorithm requires users remain fixed. In todays multiprogrammed systems, the user is constantly changing.
3.  The algorithm requires that the banker grant all requests within a finite time. Clearly much better guarantees than this are needed in real systems.
4.  Similarly, the algorithm requires that clients repay all loans within a finite time. Much better guarantees than this are needed in real systems. 
5. The algorithm requires that users state their maximum needs in advance. It is difficult to predict the users maximum need