Dinning Philosophers Problem Five philosophers are sitting on a round table caug
ID: 3905982 • Letter: D
Question
Dinning Philosophers Problem
Five philosophers are sitting on a round table caught in deep thought. Besides thinking, they have to eat every now and then or they will starve. Between each philosopher is one chopstick. In the middle of the table is a bowl of spaghetti. Two chopsticks are required in order to eat the entangled spaghetti. If a philosopher (task) wants to eat (run), he has to acquire the chopstick (resources) of both of his neighbors. He can only get the chopsticks if none of his neighbors are using them. This implies that no neighboring philosophers can eat at the same time and that at most two philosophers can eat at a time. A solution to the problem has to guarantee mutually exclusive access to the resources. Absence of deadlock and absence of starvation are important as well, however, we don’t want to address starvation at the moment.
The following is a pseudo code that shows a solution to the dinning philosophers problem. Use this pseudo code to write a multi-threaded program as a solution for this problem. Your java code will be somewhat different from the pseudo code. You have to write a similar code with Java's wait and notifyAll methods.
The monitor dining controls the distribution of the chopsticks. Monitor Dining
{ enum {thinking, hungry, eating} state[5];
void pickup (int i) {
state[i] = hungry; test(i);
if (state [i] != eating)
}
self [i].wait(); }
void putdown (int i) {
state [i] = thinking; test ((i+4) % 5); test ((i+1) % 5);
}
void test (int i) {
if ((state[(i+4) % 5] != eating) && (state[i] == hungry) && (state[(i+1) % 5] !=eating )) {
state[i] = eating; self [i].signal();
} }
void init() {
for (int i = 0; i < 5 ; i++) state[i] = thinking;
}
Each philosopher, before starting to eat, must invoke the operation pickup. This may result in the suspension of the philosopher process. After the successful completion of the operation, the philosopher may eat. Following this the philosopher invokes
the putdown operation, and may start to think. Thus, philosopher i must invoke the operations pickup and putdown in the following sequence:
diningObject.pickup( i ); ...
eat
... diningObject.putdown( i );
In thinking and eating states, you need to use the sleep method to create a random delay for each state.
-- You need to count the number of times that each philosopher gets to eat to see if starvation happens.
Hint: In Java, you cannot notify a specific thread; you just can notify a thread or all threads. Therefore, the above algorithm needs to be modified or rewritten in a different way.
Explanation / Answer
First we will have to implement the Philosophers class, this will implement the run() method from Runnable interface. Inside which we will define the doAction function. This function will correspond to the Philosophers action, of thinking, picking up the left and right fork and eating.
public class Philosopher implements Runnable {
// Member variables, methods defined earlier
@Override
public void run() {
try {
while (true) {
// thinking
doAction(System.nanoTime() + ": Thinking");
synchronized (leftFork) {
doAction(
System.nanoTime()
+ ": Picked up left fork");
synchronized (rightFork) {
// eating
doAction(
System.nanoTime()
+ ": Picked up right fork - eating");
doAction(
System.nanoTime()
+ ": Put down right fork");
}
// Back to thinking
doAction(
System.nanoTime()
+ ": Put down left fork. Back to thinking");
}
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
return;
}
}
}
Now to run the above function we'll have to create 5 fork's and 5 Philosopher objects.
public class DiningPhilosophers {
public static void main(String[] args) throws Exception {
Philosopher[] philosophers = new Philosopher[5];
Object[] forks = new Object[philosophers.length];
for (int i = 0; i < forks.length; i++) {
forks[i] = new Object();
}
for (int i = 0; i < philosophers.length; i++) {
Object leftFork = forks[i];
Object rightFork = forks[(i + 1) % forks.length];
philosophers[i] = new Philosopher(leftFork, rightFork);
Thread t
= new Thread(philosophers[i], "Philosopher " + (i + 1));
t.start();
}
}
}
In our case, we have implemented the doAction method in such a way that each Philosopher picks up the left fork first and in then the right fork, the deadlock will occour in one such case when all the five philosophers have picked up their left fork and all are in circular wait for the right fork.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.