Page 121 - DCAP403_Operating System

Operating System

Notes
Customer Credit Used Credit Line
Andy 1 6
Barb 1 5
Marv 2 4
Sue 4 7
Funds Available 2
Max Commitment 22
Eight credits have been allocated to the various customers; two remain. The question then is:

Does a way exist such that each customer can be satisfied? Can each be allowed their maximum
credit line in some sequence? We presume that, once a customer has been allocated up to his
limit, the banker can delay the others until that customer repays his loan, at which point the
credits become available to the remaining customers. If we arrive at a state where no customer
can get his maximum because not enough credits remain, then a deadlock could occur, because
the first customer to ask to draw his credit to its maximum would be denied, and all would have

to wait.
To determine whether such a sequence exists, the banker finds the customer closest to his limit: If

the remaining credits will get him to that limit, The banker then assumes that that loan is repaid,
and proceeds to the customer next closest to his limit, and so on. If all can be granted a full credit,
the condition is safe.
In this case, Marv is closest to his limit: assume his loan is repaid. This frees up 4 credits. After
Marv, Barb is closest to her limit (actually, she’s tied with Sue, but it makes no difference) and 3
of the 4 freed from Marv could be used to award her maximum. Assume her loan is repaid; we
have now freed 6 credits. Sue is next, and her situation is identical to Barb’s, so assume her loan
is repaid. We have freed enough credits (6) to grant Andy his limit; thus this state safe.

Suppose, however, that the banker proceeded to award Barb one more credit after the credit book
arrived at the state immediately above:

Customer Credit Used Credit Line
Andy 1 6
Barb 2 5
Marv 2 4
Sue 4 7
Funds Available 1
Max Commitment 22
Now it’s easy to see that the remaining credit could do no good toward getting anyone to their
maximum.
So, to recap, the banker’s algorithm looks at each request as it occurs, and tests if granting it will
lead to a safe state. If not, the request is delayed. To test for a safe state, the banker checks to see
if enough resources will remain after granting the request to satisfy the customer closest to his
maximum. If so, that loan is assumed repaid, and the next customer checked, and so on. If all
loans can be repaid, then the request leads to a safe state, and can be granted. In this case, we see
that if Barb is awarded another credit, Marv, who is closest to his maximum, cannot be awarded
enough credits, hence Barb’s request can’t be granted —it will lead to an unsafe state3.

Banker’s Algorithm for Multiple Resources

Suppose, for example, we have the following situation, where the first table represents resources
assigned, and the second resources still required by five processes, A, B, C, D, and E.

114 LOVELY PROFESSIONAL UNIVERSITY