CSE 410 Assignment 5

Spring 2007

Due: In class, Friday 5/25/07

Synchronization is an important topic and is somewhat tricky. Even if you don't have your own copy of the Silberschatz book, you should look at a copy in the library to be sure you understand the example problems and solutions there, rather than just skimming over them or looking for quick summaries on the web.

  1. (Silberschatz 6.3) 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? Give a brief explanation for your answers.
  2. (Silberschatz 6.4) Explain why spinlocks are not appropriate for single-processor systems, yet are often used in multiprocessor systems.
  3. (Silberschatz 6.5) 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. (Silberschatz 6.9) Show that if wait() and signal() operations are not executed atomically, then mutual exclusion may be violated.
  5. (Silberschatz 7.2) [Dining Philosophers, Dijkstra] Consider five philosophers who spend their lives thinking and eating. The philosophers share a circular table surrounded by five chairs, each belonging to one of the philosophers. In the center of the table is a bowl of rice, and the table is laid out with five single chopsticks, one between each of the philosopher's chairs. When a philosopher thinks, she does not interact with her colleagues. When a philosopher is hungry, she may eat if she can pick up the two chopsticks immediately to her left and to her right. However, a philosopher may only pick up one chopstick at a time and obviously cannot pick up a chopstick that is already being held by a neighbor. When a hungry philosopher has both chopsticks at the same time, she eats without releasing her chopsticks. When she is finished eating, she puts down both of her chopsticks and starts thinking again.
    (a) Describe how a deadlock could occur in this situation, leading to starvation of one or more philosophers because she (they) cannot acquire both of their chopsticks in order to eat.
    (b) 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.