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.
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.
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.)
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 ...
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
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.
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.