Lab-9

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.

Introduction

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:

• GraphicTable() : Constructor of the class without any parameter. This starts the graphical interface.
• isHungry(int) : Allows to indicate that the philosopher whose number is passed as parameter is hungry. This will make its plate being of the associated color.
• isThinking(int) : Allows to indicate that the philosopher whose number is passed as parameter is thinking. This will make its plate being black.
• takeChopstick(int, int) : Allows to indicate that the philosopher whose number is passed as first parameter took the chopstick whose number is passed as second parameter. That will make the chopstick being of the same color as the color of the philosopher's plate.
• releaseChopstick(int, int) : Allows to indicate that the philosopher whose number is passed as first parameter released the chopstick whose number is passed as second parameter. That will make the chopstick being black.

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:

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

• Describe your observations and explain the results obtained in a few words.
• Explain why LTSA finds all potential deadlocks, while they are difficult to find by testing.
• Note: you may also increment the number of philosophers in the system in order to check how complex a system the LTSA tool is able to handle. Note that there exist more powerful tools doing similar work, as for instance SPIN.
• Consider the following Dining Philosopher systems:
  • philosophers - standard version.lts
  • philosophers - standard version - taking left or right.lts
  • philosophers - abstract version.lts
  • philosophers - standard version - with counting active philosophers.lts

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.