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.
Philosopher 4 thinks Philosopher 3 finished thinking Philosopher 3 is hungry Philosopher 3 wants left chopstick Philosopher 3 got left chopstick Philosopher 3 wants right chopstick Philosopher 0 finished thinking Philosopher 0 is hungry Philosopher 0 wants left chopstick Philosopher 0 got left chopstick Philosopher 0 wants right chopstick Philosopher 0 got right chopstick Philosopher 0 eats Philosopher 1 finished thinking Philosopher 1 is hungry Philosopher 1 wants left chopstick Philosopher 2 finished eating Philosopher 2 released left chopstick Philosopher 3 got right chopstick Philosopher 3 eats Philosopher 2 released right chopstick Philosopher 2 thinks Philosopher 1 got left chopstick Philosopher 1 wants right chopstick
The functions you will need are provided by the GraphicTable class and are the following ones:
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:
Philosopher 0 is hungry Philosopher 0 wants left chopstick Philosopher 0 got left chopstick Philosopher 1 is hungry Philosopher 1 wants left chopstick Philosopher 1 got left chopstick Philosopher 2 is hungry Philosopher 2 wants left chopstick Philosopher 2 got left chopstick Philosopher 3 is hungry Philosopher 3 wants left chopstick Philosopher 3 got left chopstick Philosopher 4 is hungry Philosopher 4 wants left chopstick Philosopher 4 got left chopstick Philosopher 0 wants right chopstick Philosopher 1 wants right chopstick Philosopher 2 wants right chopstick Philosopher 3 wants right chopstick Philosopher 4 wants right chopstick
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.
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.
You should modify the Java program of Task 1 in order to explore some of the following situations:
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.