Software Construction

Gregor v. Bochmann

Winter 2012, 2013, 2015



Originally designed by Nicolas Gorse

The dining philosophers' problem

Concurrent programing in Java and LTSA

This laboratory is about concurrent programming as well as resource sharing and the problem of deadlocks that results from it. This lab has several parts: An introduction and several tasks.


The dining philosophers' problem is the following: There are 5 philosophers sitting around a table on which are laid out 5 plates and 5 chopsticks (the original version had 5 forks). A philosopher can do two things, either think, or eat. When he thinks, a philosopher doesn't need the chopsticks. When he gets hungry he wants to eat; then he needs to pick up the two chopsticks disposed on each side of his plate. When he has picked up both chopsticks, he can eat. When he has finished eating, the philosopher will put back the chopsticks and will start to think, until he gets hungry again.

Given the position of the chopsticks (between two plates), it is obvious that it is a resource shared among two philosophers (two processes). The situation of the 5 philosophers has been simulated by the Java classes given here (however, no implementation of the chopsticks is given). These classes include functions making it possible to represent the course of the diner graphically as illustrated by the example below.

The philosophers, just like the chopsticks are numbered from 0 to 4 starting with the top (red) in clockwise direction (trigonometrical reverse). The colors used are as follows: 0-red, 1-blue, 2-green, 3-yellow, 4-white or black if the philosopher is thinking. The free chopsticks are black and the chopsticks used have the color of the philosopher who has them in hand.


The functions you will need are provided by the GraphicTable class and are the following ones:

Task 1

You must provide an implementation of the Chopstick class. The chopsticks being a shared resource, you must provide them with mutual exclusion for their use (by using wait() and notify()).

Note that the Philosopher class contains three constants that determine the thinking time, the time between taking the first and second chopstick and the eating time of the philosophers. You may change these constants for obtaining different execution sequences for the system of 5 philosophers.

Run the Java program with zero thinking time. You should have the chance to observe a situation of deadlock caused by the fact that if all the philosophers take at the same time (or almost the same time) the chopstick which is on their left, they all will be blocked while waiting for the chopstick which is on their right to be free. The example below illustrates this case:

Did such a deadlock also show up when you were using larger thinking times ? - Explain your observations. What is the probability that such a deadlock will be reached ? - On what does this depend ? - Please explain.

Task 2

The experience with Task 1 shows that with arbitrary speeds of execution for the different philosophers, it is very rare that the possible deadlock of the program is actually reached within a short time. Therefore, in general, it is very hard to find such potential deadlocks in a given program by testing.

Now let us look at the LTSA tool and see how it can help us finding a potential deadlock. Have a look at the following Dining Philosopher models, try to understand the system specification and executed the Check Safety command to detect any potential deadlock.

Task 3

You should modify the Java program of Task 1 in order to explore some of the following situations:

  1. A way to avoid deadlock is to allow only a limited number of philosophers to eat at the same time. This concept can be easily implemented by using a counting semaphore to limit the number of philosophers which can start taking chopsticks at the same time to 4. This way, at least one philosopher will be able to eat, and thus will release the chopsticks, then allowing at least another to eat, etc. Suggestions: Write a class SemTable which limits the number of philosophers that eat simultaneously, and adapt the other classes accordingly. Will the philosophers be served in a fair manner ? - Explain.
  2. A general way to avoid deadlocks when multiple threads share multiple resources is two-phase resource reservation. Think about how the forks of the philosophers could be put into a linear order such that this reservation approach could be used for the dining philosophers. If time permits, implement this approach.
  3. If a philisopher is waiting for a fork for a given amount of time, he should release the fork. Would this behavior avoid a deadlock ? - Theoritically, what do you think is the problem of this solution ? - Do you notice the problem of this solution in your program ? - What if we made the waiting time random ? 
  4. What about letting the odd philiosophers start by left fork, while the others starts by right fork ?

For each situation, discuss whether the deadlock would be avoided. Implement the behavior by modifying the Java program of Task 1 and observe the behavior of the modified program.