/ COMPUTER-FUNDAMENTAL

Banker's Algorithm

Banker’s algorithm is a DeadLock avoidance algorithm.

DeadLock Avoidance only allocate Resources in “Safe State”.
So, Banker’s algorithm only accept Safe State requests, and decline Unsafe State requests until changing to Safe State.

The concept of Banker’s algorithm

runtime2 In the above image, Bank has $20 now, but User 1, 2, and 3 still need money.

To solve the shortage,
First solution is give $10 to User 2, and wait for user 2 until he give money back to bank. When Bank get $40 from user 2, they can help user 1 or 3.
Second solution is give $20 to user 3, and wait for user 3 until get back money.
However, this method is not working with user 1 because he needs $40.
So, we can help user 1 after user 2 and 3 complete.

“Safe State” is a state that bank can give and get back money from users.

  • user2 -> user1 -> user3
  • user2 -> user3 -> user1
  • user3 -> user1 -> user2
  • user3 -> user2 -> user1

    These sequences are known as “Safe Sequence”, which can solve user’s problem. runtime2 However, in this case, user1 needs urgent $35. The bank currently have only $5. The bank cannot help anyone of users, and they will bankrupt.
    This state is known as “Unsafe State” or “DeadLock”.

    So, the banker’s algorithm is caused from “Bank must have money that can help at least one users”.

Safe State
-> a state that has Safe sequence that can allocate necessary Resource to Process without DeadLock.

Unsafe State
-> a state that does not have Safe Sequence. Unsafe State is a necessary condition to make DeadLock.

DeadLock only occur when Unsafe State exists. Unsafe State has no guarantee to make DeadLock.

Necessary conditions to operate Banker’s algorithm

  1. Maximum Money that Users can request
    -> How many resources the Process can request
  2. Current money that users can borrow
    -> how many resources the Process is holding now
  3. Available money in the bank
    -> How many resources the system has available

Process example

runtime2 P0, P1, P2 are Process, OS has 12 Drives for Resources.
Now, at “t0” time, P0 uses 5 Drives, P1 uses 2 Drives, and P2 uses 2 Drives. So, OS has 3 Drives as available Resources now.
the system is Safe State at t0 because (P1 -> P0 -> P2) is satisfied with Safe Sequence.

However, the system can be Unsafe State.
At “t1” time, P2 Process request 1 more Drive Resource, and available Resource is 2. runtime2 In this situation, P0 is impossible because it needs 5 Drives Resources.
Also P1 is not solution because, even though OS helps P1 and get back 4 Drive Resources, OS can not help P0 or P2 with 4 Drive Resources.
So, the system is Unsafe State at “t1” Time.

If we had made P2 waits until other processes had finished and released its resources, then we could have avoided the DeadLock.
The idea is imply to ensure that the system will always remain in Safe State.

Disadvantage of Banker’s algorithm

  • The prerequisites
    • Same Resource number
    • Low rate of Resource usability to prevent Unsafe State
    • Need to know the Maximum Resource numbers
    • Limited time for holding Resources

      Banker’s algorithm is not recommened.