ALL 20 CHAPTERS COVERED
,The Art of Multiprocessor Programming
Solutions to Exercises
Chapter 1
September 24, 2009
,2
Figure 1: Traditional dining table arrangement according to Dijkstra.
Exercise 1. The Dining Philosophers problem was invented by E. W. Dijk-
stra, a concurrency pioneer, to clarify the notions of deadlock and starvation
freedom. Imagine five philosophers who spend their lives just thinking and
feasting. They sit around a circular table with five chairs. The table has a big
plate of rice. However, there are only five chopsticks (in the original formula-
tion forks) available, as shown in Fig. 1. Each philosopher thinks. When he
gets hungry, he sits down and picks up the two chopsticks that are closest to
him. If a philosopher can pick up both chopsticks, he can eat for a while. After
a philosopher finishes eating, he puts down the chopsticks and again starts to
think.
1. Write a program to simulate the behavior of the philosophers, where each
philosopher is a thread and chopsticks are shared objects. Notice that you
must prevent a situation where two philosophers hold the same chopstick
at the same time.
2. Amend your program so that it never reaches a state where philosophers
are deadlocked, that is, it is never the case that each philosopher holds
one chopstick and is stuck waiting for another to get the second chopstick.
3. Amend your program so that no philosopher ever starves.
4. Write a program to provide a starvation-free solution for any number of
philosophers n.
Solution Figure shows the Fork class. Figure shows a simple, deadlock-
prone solution, while Figure shows a solution that avoids deadlock by having
even-numbered philosophers pick up the left chopstick first, and odd-numbered
philosophers pick up the right one.
, 3
1 public class Fork {
2 boolean taken;
3 int id ;
4 public Fork(int myID) {
5 id = myID;
6 }
7 public synchronized void get() throws InterruptedException {
8 while (taken) {
9 wait ();
10 }
11 taken = true;
12 }
13 public synchronized void put() {
14 taken = false;
15 notify ();
16 }
17 }
Figure 2: The Fork class
Exercise 2. For each of the following, state whether it is a safety or liveness
property. Identify the bad or good thing of interest.
1. Patrons are served in the order they arrive.
2. What goes up must come down.
3. If two or more processes are waiting to enter their critical sections, at least
one succeeds.
4. If an interrupt occurs, then a message is printed within one second.
5. If an interrupt occurs, then a message is printed.
6. The cost of living never decreases.
7. Two things are certain: death and taxes.
8. You can always tell a Harvard man.
Solution Note that students often come up with creative alternative expla-
nations!
1. Safety: serving patrons out of order is a bad thing which must never
happen.
2. Liveness: eventually the coming-down state transition occurs.
,The Art of Multiprocessor Programming
Solutions to Exercises
Chapter 1
September 24, 2009
,2
Figure 1: Traditional dining table arrangement according to Dijkstra.
Exercise 1. The Dining Philosophers problem was invented by E. W. Dijk-
stra, a concurrency pioneer, to clarify the notions of deadlock and starvation
freedom. Imagine five philosophers who spend their lives just thinking and
feasting. They sit around a circular table with five chairs. The table has a big
plate of rice. However, there are only five chopsticks (in the original formula-
tion forks) available, as shown in Fig. 1. Each philosopher thinks. When he
gets hungry, he sits down and picks up the two chopsticks that are closest to
him. If a philosopher can pick up both chopsticks, he can eat for a while. After
a philosopher finishes eating, he puts down the chopsticks and again starts to
think.
1. Write a program to simulate the behavior of the philosophers, where each
philosopher is a thread and chopsticks are shared objects. Notice that you
must prevent a situation where two philosophers hold the same chopstick
at the same time.
2. Amend your program so that it never reaches a state where philosophers
are deadlocked, that is, it is never the case that each philosopher holds
one chopstick and is stuck waiting for another to get the second chopstick.
3. Amend your program so that no philosopher ever starves.
4. Write a program to provide a starvation-free solution for any number of
philosophers n.
Solution Figure shows the Fork class. Figure shows a simple, deadlock-
prone solution, while Figure shows a solution that avoids deadlock by having
even-numbered philosophers pick up the left chopstick first, and odd-numbered
philosophers pick up the right one.
, 3
1 public class Fork {
2 boolean taken;
3 int id ;
4 public Fork(int myID) {
5 id = myID;
6 }
7 public synchronized void get() throws InterruptedException {
8 while (taken) {
9 wait ();
10 }
11 taken = true;
12 }
13 public synchronized void put() {
14 taken = false;
15 notify ();
16 }
17 }
Figure 2: The Fork class
Exercise 2. For each of the following, state whether it is a safety or liveness
property. Identify the bad or good thing of interest.
1. Patrons are served in the order they arrive.
2. What goes up must come down.
3. If two or more processes are waiting to enter their critical sections, at least
one succeeds.
4. If an interrupt occurs, then a message is printed within one second.
5. If an interrupt occurs, then a message is printed.
6. The cost of living never decreases.
7. Two things are certain: death and taxes.
8. You can always tell a Harvard man.
Solution Note that students often come up with creative alternative expla-
nations!
1. Safety: serving patrons out of order is a bad thing which must never
happen.
2. Liveness: eventually the coming-down state transition occurs.
