Comp111: Operating Systems
Classroom Exercise 12 Answers
The Bankers' Algorithm
Fall 2018

In class we have studied the banker's algorithm for avoiding deadlock. Suppose we have three processes and four resources, in the following situation:
Requested Granted Deficit
R1R2R3R4 R1R2R3R4 R1R2R3R4
P14231 - P10000 = P14231
P22144 P20122 P22022
P35122 P35111 P30011
5 2 4 4
In the above, "Totals" indicate total resources available.

  1. Prove that this situation is safe by giving a schedule under which all processes can complete.
    Answer: Starting with P3, we allocate the missing units and P3 can complete. Then P2 can complete next, followed by P1. Thus the situation is safe.
  2. Under what conditions does a process in a Banker's Algorithm tableau remain runnable?
    Answer: A process is runnable whenever all deficits are 0. If there is a non-zero deficit, the process awaits assignment of resources and is blocked. A process also remains runnable if it is currently runnable and a request is rejected due to creation of an unsafe state.
  3. Suppose that we start with the above configuration and P1 asks for 3 more units of R4. Is that allocation safe? Why or why not?
    Answer: Oops. This one was mis-worded. The reason is that P1 isn't runnable, so it can't ask for 3 more units of R4. The following answer is a bit weird because of that: It is safe, because the same schedule will still work to complete all tasks.

    At a deeper level, this is inaccurate, because P1 can't ask for 3 more units of R4 until the schedule has run almost to the end.

  4. Suppose that we start again from the above configuration and that P3 asks for 1 more unit of R3. Is that allocation safe? Why or why not?
    Answer: Oops. P3 isn't runnable until its needs are met. The following answer is thus incomplete: This is unsafe, because there are no more units to allocate, so that P3, which must be the first to complete, can no longer complete.
  5. Suppose that we start again from the above configuration and that P2 unexpectedly cancels all of its requests for R3(e.g., in response to a signal), after which P3 asks for 1 more unit of R3. Is that allocation safe? Why or why not?
    Answer: Now the situation is safe, because P3 can still go first.

    Note that the Banker's Algorithm allows for cancellation; cancellations bubble a process up in the completion schedule just as requests bubble a process down.

  6. Why does the algorithm have to model situations in which resources are requested, available, and not granted?

    The simple answer is that when a process ends, there is a time between when it releases its resources and when they are re-allocated via scheduling. So the algorithm must account for that possibility. The actual granting is -- of course -- tied to the scheduler!

    At a deeper level, the algorithm is designed for situations in which many requests occur asynchronously and the actual granting may take a long time, e.g., to move things around. While granting is going on, 'requests' can still be coming in. The 'requesting' and 'granting' phases have a producer-consumer relationship. It is advantageous to be able to decide whether to grant without actually granting; this gives the "no" responses more quickly than if requesting and granting were coupled.

    However, that is not even the core of the answer. Separating requests from grants allows processes to over-subscribe resources in safe ways that would not be possible if there was no separation between requests and grants.

    Note that a decision to grant -- without resources available -- blocks the process until the grant actually occurs.

  7. (Advanced) Recall that malloc does not send a signal or kill the application when enough memory is not available, but rather, returns 0 to the application. In the context of this discussion, why is that behavior "preferable" to killing the process?
    Answer: Just because malloc doesn't succeed immediately doesn't mean that resources won't be available later. The Banker's Algorithm assures that if we remain safe, resources will eventually become available. So, rather than killing the process with the failed malloc, we send it an indication that it should wait.