Comp111: Operating Systems
Classroom Exercise 11 Answers
In class we have studied a few different kinds of deadlock. One of
the most subtle kinds of deadlock is that of waiting for resources.
Consider four processes that must each consume four
units of a limited resource (e.g. memory) in order to complete,
after which those units are released. Suppose that one unit of the
resource is allocated or deallocated at a time, and that allocation is
atomic. Suppose that there are 9 total units available and
that each process goes through four steps of allocating one unit
followed by four steps of deallocating one unit.
- Give a completion schedule for the four processes that runs without deadlock.
Demonstrate why all processes complete.
The easiest thing to do is to serialize the four processes and only allow
one to run at a time! Since each one requires a total of 4 units,
each one can run alone with no problem.
- Consider the situation in which three of the four processes have
allocated three units each and the fourth has allocated no units.
Is this a deadlock situation? Why?
Yes. All units are allocated, and every process needs one more, and no
process will release a unit.
- Explain how the preceding scenerio can occur.
Suppose the four programs are all reading files and putting the
contents into memory. Then it is very possible that three programs
will run to the point where they have consumed 3 pages, and then each asks for a
- Using one or more locks, prevent deadlock in this case.
What should you lock? When should you lock it?
How can you both prevent deadlock and maximize throughput?
Simply putting a lock around the memory resource so that there
is exclusive access will solve the deadlock problem; using semaphores
with a concurrency of 2 will maximize throughput.
- If the four processes are constrained to allocate and deallocate
all of the memory they need in one (atomic) step, then is deadlock
It is not possible, because the process will get all it needs in one step, so there will not be a situation in which any process is awaiting resources.
- (Advanced) If four resources are given names A, B, C, D and all resources request them by name, in alphabetical order, can deadlock occur? Why?
Answer: As we will discuss next time, this is the same as locking in the same sequence each time, and there is no way -- even if one locks a subsequence -- to create a deadlock in this fashion.