Dining Philosopher’s Problem is one of the problem classic problems of multi threading and thread synchronization.
Statement and Explanation
Here we have five philosophers sitting around a dining table which has five
plates and five forks as shown in the image below. All they do is thinking and
eating.
Here forks are the shared objects. Each fork is shared between two
philosophers.
They will be thinking when they do not have access to both the forks. When
they get both forks, they will eat. Our task is to synchronise this sharing of
forks so that circular wait do not happens. In circular wait, every
philosopher gets a fork and will be waiting for another fork which is acquired
by another philosopher.
If this happens, no one gets to eat and will be waiting indefinitely.
Here we need to create five threads, one for each philosopher. Also, we need to create five fork objects.
For each philosopher, we give two shared fork objects. Everyone gets the forks in the order of left first and right next except last philosopher.
what’s the reason might be?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class DCControl { | |
public static void main(String[] args) { | |
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]; | |
if (i == philosophers.length - 1) { | |
philosophers[i] = new Philosopher(rightFork, leftFork); | |
} else { | |
philosophers[i] = new Philosopher(leftFork, rightFork); | |
} | |
Thread thread = new Thread(philosophers[i], "Philosopher " + (i + 1)); | |
thread.start(); | |
} | |
} | |
} |
The reason is a circular wait condition might arise if forks given in Left
first right next order. I recommend to experiment and try it out.
The main logic is initially every philosopher will be thinking for a random
amount of time. This will make someone to get a kick start instead of
following the same order every time.
Here we are using synchronised block to get the access to monitor. In the
previous examples we have used synchronised method.
Here, the philosopher acquires left fork first and then right fork next
and when he finishes eating, he will relieve the access in the reverse order.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Philosopher implements Runnable { | |
private Object leftFork; | |
private Object rightFork; | |
public Philosopher(Object leftFork, Object rightFork) { | |
this.leftFork = leftFork; | |
this.rightFork = rightFork; | |
} | |
@Override | |
public void run() { | |
try { | |
while (true) { | |
doAction("Thinking"); | |
synchronized (leftFork) { | |
doAction("Picked up left fork"); | |
synchronized (rightFork) { | |
doAction("Picked up right fork-eating"); | |
doAction("Put down right fork"); | |
} | |
doAction("Put down left fork"); | |
} | |
} | |
} catch (InterruptedException e) { | |
e.printStackTrace(); | |
} | |
} | |
private void doAction(String action) throws InterruptedException { | |
System.out.println( | |
Thread.currentThread().getName() + " " + action); | |
Thread.sleep(((int) (Math.random() * 3000))); | |
} | |
} |
The same will go on indefinitely. Do experiment with the code and reason the
random sleep time.
Output
The output looks something like this.
Post a Comment