Note: Although the due time is March 25, I will be away during the week of March 22 (and without email access). Hence, you should start ahead thinking about this assignment, and discuss with me your questions, doubts, etc. before March 20. During my absence, the lectures will be given by Prof. Dale Miller, and he will collect the Hws on March 25.
- Catuscia Palamidessi
The usual activity of a philosopher is thinking. However, from time to time, he gets hungry and tries to eat some rice. In order to eat, he needs to grab both the chopsticks at his left and at his right. He can grab only one chopstick at the time, and, of course, only if the neighbour is not already holding it. Once the philosopher succeeds to grab both chopsticks, he eats some rice, then releases the chopsticks, and goes back to thinking.
The typical problems which arise in this situation are
One way to solve the two problems mentioned above is by introducing the rule that each philosopher should, before attempting to grab the chopsticks, take a "ticket" from a common box. If the philosopher succeed to obtain a ticket, then he can try to take the chopsticks, and eat. Afterwards, he should put the tickets back in the box. In the box there are n-1 tickets, so that the situation described above (generating deadlock or global starvation) can never occur.
Implement the "Dining Philosophers" in Java, representing each philosopher as an active object (thread), and each chopstick as a passive object, following the idea of the "tickets box" described above to avoid deadlock/global starvation.
The classes of the philosophers, the chopsticks, and the tickets box should have the following interface:
interface Chopstick_interface {
boolean is_free();
void take();
void release();
}
interface Tickets_box_interface {
boolean tickets_available();
void take_ticket();
void release_ticket();
}
interface Philosopher_interface {
void run();
}
Add the following main program:
public class Dining_philosophers {
public static void main(String[] args) {
int n = args.length; // n = number of philosophers
Philosopher[] phils = new Philosopher[n]; // references to n philosophers
Tickets_box b = new Tickets_box(n - 1); // creates box with tickets
Chopstick c_0 = new Chopstick(0);
Chopstick left = c_0;
for (int i = 0; i < n-1; i++) {
Chopstick right = new Chopstick(i+1);
phils[i] = new Philosopher(args[i],left,right,b);
left = right;
}
phils[n-1] = new Philosopher(args[n-1],left,c_0,b);
for (int i = 0; i < n; i++) {
phils[i].start();
}
}
}
Make sure that your objects
signal the various activities going on,
so that, when executed, you obtain an output like
the following, in the case of 5 philosophers:
mix 31% java Dining_philosophers Plato Aristotle Zeno Eraclito Parmenide Plato is thinking Aristotle is thinking Zeno is thinking Eraclito is thinking Parmenide is thinking Plato is trying to eat ... Plato is eating ... Plato is thinking Aristotle is trying to eat ... Aristotle is eating ... Aristotle is thinking Zeno is trying to eat ... Eraclito is trying to eat ... Parmenide is trying to eat ... Zeno is eating ... chopstick 3 already taken ... Parmenide is eating ... Eraclito is thinking Parmenide is thinking Zeno is thinking Plato is trying to eat ... Plato is eating ... Plato is thinking Aristotle is trying to eat ... Aristotle is eating ... Aristotle is thinking Eraclito is trying to eat ... Eraclito is eating ... Eraclito is thinking Parmenide is trying to eat ... Parmenide is eating ... Parmenide is thinking Zeno is trying to eat ... Zeno is eating ... Zeno is thinking Plato is trying to eat ... Plato is eating ... Plato is thinking Aristotle is trying to eat ... Eraclito is trying to eat ... Parmenide is trying to eat ... Zeno is trying to eat ... Plato is trying to eat ... tickets unavailable ... chopstick 1 already taken ... chopstick 2 already taken ... chopstick 3 already taken ... chopstick 4 already taken ... Plato is thinking Aristotle is eating ... Aristotle is thinking Eraclito is thinking Parmenide is thinking Zeno is thinking Plato is trying to eat ... Plato is eating ... Plato is thinking Aristotle is trying to eat ... Aristotle is eating ... Aristotle is thinking Eraclito is trying to eat ... Eraclito is eating ... Eraclito is thinking Parmenide is trying to eat ... Parmenide is eating ... Parmenide is thinking Zeno is trying to eat ... Zeno is eating ... Zeno is thinking ^Z Suspended mix 32%You don't need to obtain exactly this output; The above is just to give you an idea.
Please make sure that your program can be compiled and executed on Unix.
The format of the input should be as follows:
% java Dining_philosophers n1 n2 n3 n4 ... nMwhere n1 n2 n3 n4 ... nM is a sequence of names (the names of the philosophers).
Note: I know that there are lots of Java implementations of the Dining Philosophers available on the web, with fancy graphical features and diverse solutions to the deadlock problem. For the purpose of this assignment, however, you should stick to the interface described above and to the "tickets box" solution. Furthermore, you should not worry about graphical tools, a simple printed output like the above is more than sufficient.
If you want to see a typical demo of the problem, with 7 philosophers, go to http://www.personal.leeds.ac.uk/~ecldh/diners/RunDiners.html and wait a few minutes. Do not look at the code, because the solution is completely different and incompatible with the above interface.