Comp111: Operating Systems
Classroom Exercise 8 Answers
Deadlock
Fall 2017

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. Answer: 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.
  3. 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?
    Answer: Yes. All units are allocated, and every process needs one more, and no process will release a unit.
  4. Explain how the preceding scenerio can occur.
    Answer: 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 fourth page.
  5. 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?
    Answer: 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.
  6. 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?
    Answer: 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.
  7. (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.