Dining philosophers

There is a famous synchronization problem called "The Dining Philosophers." You may have met it in an operating systems course. The statement of the problem goes like this:
There are n philosophers who live in a small college, and all they do is eat and think. The philosophers sit at a round table. On the left and right of each philosopher is a single chopstick, which is shared by the two philosophers on each side of it, and in the middle of the table is a bowl of sphagetti, which requires two chopsticks to eat. From time to time a philosopher gets hungry, and picks up the two chopsticks, one at a time, eats until he is satified, then sets the chopsticks down, each in its proper place.
Missing from the problem statement are a number of conditions for a good solution.
  1. All of the philosophers are running as independent threads.
  2. Only one philosopher may use a chopstick at a time. If the philosopher on the right of the chopstick has picked it up, the philosopher on the left cannot pick it up, and thus cannot eat, until the other philosopher sets it down.
  3. It is undesirable for a philosopher to starve to death.
Often we add other conditions, which have nothing to do with dining or philosophers, but seem important for computer systems,
  1. The philosopher threads shouldn't take up too much CPU time with the transition between thinking and eating. For example, it isn't great for a philosopher to sit in a loop waiting for a chopstick to be set down (this is called busy-waiting) not because the philosopher has something better to do, but because the CPU might be used for something more useful -- like shovelling virtual sphagetti into another philosopher's mouth.
  2. The philosophers should run essentially the same code in each philosopher thread. This requirement makes no sense from a philosopher point of view, but it makes the problem easier to think about and the assignment easier to grade.
The dining philosophers problem was originally posed as a challenge for the Semaphore datastructure, which had been suggested as an alternative to busy-waiting for synchronization.

My sample code (below) uses busy-waiting, so after you fix the deadlock/starvation problems, you might want to fix that as well.

In order for there to be an issue in Java, each philosopher should run as a Java thread.

Oracle provides a tutorial on synchronization at: http://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html Java object locks are approximately semaphores, but synchronization in Java is both easier and more complicated than locking. You can solve the problem using only locks, but using sychronized blocks is easier to think about, as well as more in the spirit of the language.

So here's a sample output for a run of the problem

Philosopher 1 sits down Philosopher 2 sits down Philosopher 3 sits down Philosopher 1 gets hungry Philosopher 2 is thinking Philosopher 3 gets hungry Philosopher 1 eats Philosopher 2 gets hungry Philosopher 3 is hungry, but can't eat Philosopher 1 finishes eating Philosopher 2 eats Philosopher 2 finishes eating Philosopher 3 eats Philosopher 1 is thinking Philosopher 2 gets hungry Philosopher 3 finishes eating Philosopher 1 gets hungry Philosopher 2 eats Philosopher 2 finishes eating Philosopher 3 gets hungry Philosopher 1 eats ...
Here each output line is printed by the appropriate thread, which obviously must know its own number, as well as which are its two chopsticks and whether they are available or in use. After each printout, the coroutine yields, so that one of the other threads can run. Whether a philosopher gets hungry or not is controlled by a random number generator. Whether a hungry philosopher can eat is controlled by the availability of the chopsticks (apparently the sphaghetti is inexhaustible.)

Sample code

Here is some sample code to start with. (Although you can ignore it if you'd rather.)

The sample code runs for awhile, then stops, or deadlocks. At that point, all three philosophers want to eat, but each has exactly one of the necessary chopsticks, so none of them can continue.

I stuck in all the

possiblyYields();
calls to speed up the failure; Java threads may be pre-empted at any time, but if they do not call yield() to voluntarily let some other runnable thread have the CPU, the output will have long strings of each thread going through its activity cycle.

The possiblyYields() lines do not create the problem, they just let it happen sooner.

Hints, or how I think you should solve the problem

Java lets you have synchronized methods, and synchronized blocks of code within methods.

synchronized methods use the object of which they are a method as a lock, so that in the common case in which the datastructure whose integrity is being sustained is part of the object properties, the methods which touch it can be part of the same critical section. Unfortunately, in my sample code the relevant datastructures are static, that is, each of the philosophers is using the same chopsticks array as all of the others. But each of the philosopers is running as a method in a different diners instance. So making the various methods synchronized does no good.

synchronized code blocks explicitly mention the object to lock on. So each of the philosopher instances can use the same object, and a logical one might be the chopsticks array.

The Wikipedia article on the dining philosophers problem provides a description of two solutions. Because this is a classic problem, there are dozens of solutions on the web, but many of them aren't completely relevant here.

Besides, you have to explain what your code does, which is going to be difficult if you just download someone else's solution.

I don't required that your solution run in an Android phone, but you may decide that doing so is more fun. One extra problem about doing that is the requirement that all input and output on the phone must take place in a single thread. And the Android library does not provide System.out.println, so you'll have to use a Textview object in your user interface, and use .setText() to change the text it is displaying, and finally .invalidate() to get the user-interface thread to redisplay the object with the new text.

You will turn in

  1. A listing of your Java code implementing a (proposed) solution to the philosophers problem, which must run each philosopher as a separate thread, since that was the point of this assignment.
  2. A word document