CSC 539: Operating Systems Structure and Design
Spring 2005

HW3: Process Synchronization and Deadlock

  1. What is the meaning of the term busy waiting? What other kinds of waiting are there in an operating system? Can busy waiting be avoided altogether? Explain.
  2. Explain why spinlocks are not appropriate for single-processor systems yet are often used in multiprocessor systems.
  3. Explain why implementing synchronization primitives by disabling interrupts is not appropriate in a single-processor system if the synchronization primitives are to be used in user-level programs.
  4. Consider the deadlock situation that could occur in the dining-philosophers problem when the philosophers obtain the chopsticks one at a time. Discuss how the four necessary conditions for deadlock indeed hold in this setting. Discuss how deadlocks could be avoided by eliminating any one of the four conditions.
  5. Excluding the dining-philosophers problem, list three other examples of deadlocks that are not related to a computer system environment.
  6. In a real computer system, neither the resources nor the demands of processes for resources are consistent over long periods (months). Resources break or are replaced, new processes come and go, new resources are bought and added to the system. If deadlock is controlled by the banker's algorithm, which of the following changes can be made safely (without introducing the possibility of deadlock), and under what circumstances?
    1. Increase Available (new resources added).
    2. Decrease Available (resources permanently removed from system).
    3. Increase Max for one process (the process needs more resources than allowed; it may want more).
    4. Decrease Max for one process (the process decides it does not need that many resources).
    5. Increase the number of processes.
    6. Decrease the number of processes.
  7. Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlock free.
  8. Is it possible to have a deadlock involving only one single process? Explain your answer.
  9. Suppose that a system is in an unsafe state. Show that it is possible for the processes to complete their execution without entering a deadlock state.
  10. Consider the following snapshot of a system:

    Allocation Max Available ---------- ------- --------- A B C D A B C D A B C D P0 0 0 1 2 0 0 1 2 1 5 2 0 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 6 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6

    Answer the following questions using the banker's algorithm.

    1. What is the content of the matrix Need?
    2. Is the system in a safe state?
    3. If a request from process P1 arrives for (0,4,2,0), can the request be granted immediately?