Comp111: Operating Systems
Classroom Exercise 12 Answers
The Bankers' Algorithm
In class we have studied the banker's algorithm
for avoiding deadlock. Suppose we have three processes and four
resources, in the following situation:
In the above, "Totals" indicate total resources available.
| ||Totals |
- Prove that this situation is safe by giving a schedule under which
all processes can complete.
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.
- 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
- 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?
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.
- 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?
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.
- 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?
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.
- 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.
- (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