There is an exercise in Bruce Eckel's Thinking in Java, on the dining philosopher's problem.
I have done the exercise, but I am not very confident whether my conclusions are right. It'd be nice, if you can review the exercise, my conclusions and tell me whether they are right or wrong.
I thank you for this.
The Exercise:
Change DeadlockingDiningPhilosophers.java so that when a philosopher is done with its chopsticks, it drops them into a bin. When a philosopher wants to eat, it takes the next two available chopsticks from the bin. Does this eliminate the possibility of deadlock? Can you reintroduce deadlock by simply reducing the number of available chopsticks?
This exercise involves three source files -- concurrency/DeadlockingDiningPhilosophers.java, concurrency/Philosopher.java & concurrency/Chopstick.java
To answer the exercise. I created a BlockingQueue<Chopstick> (this is our bin). The Philosophers, after eating for the first time, put both their left & right chopstick in the bin (the BlockingQueue<Chopstick>).
When a philosopher wishes to eat for the second time, he tries to take Chopsticks from the bin.
In this case, we don't reach a deadlock, 'cause the maximum number of chopsticks that is available in the BlockingQueue<Chopstick> is double of the original number of Chopsticks -- as the Philosophers put both their left & right chopstick in the bin.
For instance,
If there are 5 Philosophers. So, we have 5 Chopsticks, as per the constraints of the problem.
Each Philosopher puts both their chopsticks in the bin after eating for the first time.
Philosopher 1: puts two Chopsticks in the bin. Philosopher 2: puts two Chopsticks in the bin. . . Philosopher 5: puts two Chopsticks in the bin
Therefore, in the end, we have 10 Chopsticks in the BlockingQueue<Chopstick> -- double the number of original Chopsticks. So, we don't reach the Deadlock.
Period.
To reduce the number of Chopsticks, in the bin, to the original number. I modified the program -- each Philosopher puts only the left Chopstick into the bin, after eating for the first time.
From the second time on, each Philosopher takes both the Chopsticks from the bin and after eating, puts both the Chopsticks back to the bin.
To make things easier, I have a diff of the original version and modified version (with the bin, where Philosopher, puts only his left Chopstick in the bin, for the first time, when he eats) here :