Comp111: Operating Systems
Classroom Exercise 11
Fall 2018

group member 1: ____________________________ login: ______________
group member 2: ____________________________ login: ______________
group member 3: ____________________________ login: ______________
group member 4: ____________________________ login: ______________
group member 5: ____________________________ login: ______________
group member 6: ____________________________ login: ______________
group member 7: ____________________________ login: ______________
group member 8: ____________________________ login: ______________

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.

  1. Give a completion schedule for the four processes that runs without deadlock. Demonstrate why all processes complete.

  2. 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?
  3. Explain how the preceding scenerio can occur.

  4. 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?

  5. If the four processes are constrained to allocate and deallocate all of the memory they need in one (atomic) step, then is deadlock possible? Why?

  6. (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?