Where opportunity calls parallely !

 
M A Hossain Tonu
M A Hossain Tonu
Software Engineer

The Dining Philosophers Problem - Java Multithreading

(page 1 of 1)

In 1971 (Year of our Liberation), A University Professor, Edger Djikstra gave this problem to his Computer Science students which then became popular in today's computing problems. **Enough with history... I'm too lazy writting about history... ** Feel free to add what I don't have here..

Introduction to Multithreading
The definition of multithreading can be simplified by saying that there are 2 programs those are running at the same time. However, it is important to note that assuming there is only single core CPU on your computer, these programs are only simultaneously run at the same time. There is no way single core CPU to run both program at the same time. But because the change is so fast (I'm talking here about nano seconds) which is the speed that we can't even imagine, CPU switch one program over another. So imagine diagram below:

 

Thread #1     Thread #2
I
I
I
--------------------------------------- (switch to Thread 2 at nano seconds)
                      I
                      I
                      I
--------------------------------------- (switch  back to Thread 1 at nano seconds)
I
I
I


What is Dining Philosophers Problem?

There are only 2 things that philosophers do:
1. Eat
2. Think
In order to eat, Philosopher would need two chopsticks (I think this illustration is better than fork, cuz you can eat without 2 forks... ). Each of the philosopher have one chopstick though, so he must be able to get the other chopstick. If the other chopstick is not there, then philosopher will think and wait. Note that there are many solution for this problem depending on how do you want to implement it. Illustration of the philosopher can be seen below:

 

Now how do we represent these into multithreading?

Philosophers = Threads

Food = Resources
Chopsticks = Semaphore/Locks

Remember that philosopher need two chopstick in order to get the resources, and make sure that they don't get hungry!!! They will die if they're too hungry, and also make sure that there's no situation where DEADLOCK may occurs!!!

Example of Deadlock situation:
- All philosophers holding the left chopstick at the same time, and none of them are putting the chopstick down to be used by the other philosopher.
- You can find this problem occurs on Microsoft Windows when you see the Blue Screen of Death a.k.a Blue Screen. This is when there's no resources can be accessed. I'm not sure on how exactly does this occur, someone more experienced with Operaying System may be much more understand than I do until next quarter where I'll take Operating System class ... hopefully I can explain this more...

Also, make sure that there's no STARVATION, where philosophers are getting too hungry and then die. Starvation is the time where all philosophers are taking the left chopsticks at the same time (or right) and then put them back since there's no other chopstick, and then get the right chopstick, and then put them back since there's no left chopsticks. The worst case is when they're all getting the right/left chopsticks at the same time.

Solution:
There are actually many solutions to this problem depending on how do you want to implement your program as I said in the beginning, but I'm using Round Robin solution, which is where there will be at least 1 philosophers or 2 that will eat at the same time, and then switch to the next one. However, it will do eventually getting into the DEADLOCK situation at the end... I'm not sure on how to optimize this since programmers doesn't have control over the Operating System and CPU, but of course you can still optimize it on however you want... by using boolean, bla bla... Of course, my code will not be 100% correct, so don't sue me if you get an F by using my code haha....

DiningPhilosophers.java - Main Method

public class DiningPhilosopher {
public static void main(String[] args
) {
Chopstick cs = new Chopstick
();
Philosopher p1 = new Philosopher(cscs1
);
Philosopher p2 = new Philosopher(cscs2
);
Philosopher p3 = new Philosopher(cscs3
);
Philosopher p4 = new Philosopher(cscs4
);
Philosopher p5 = new Philosopher(cscs5
);
 
Thread t1 = new Thread(p1
);
t1.start
();
Thread t2 = new Thread(p2
);
t2.start
();
Thread t3 = new Thread(p3
);
t3.start
();
Thread t4 = new Thread(p4
);
t4.start
();
Thread t5 = new Thread(p5
);
t5.start
();
}

Philosophers.java - Threads using Runnable class

import java.util.Random;
public class Philosopher implements Runnable 
{
private Random r = new Random
();
 
private Chopstick rightStick
;
private Chopstick leftStick
;
 
private int phil
;
 
public Philosopher(Chopstick rChopstick lint phil
) {
this.rightStick r
;
this.leftStick l
;
this.phil phil
;
Thread t1 = new Thread(this
);
t1.start
();
}
 
public void run
() {
for (
int i 1<= 10i
) {
try 
{
Thread.sleep(r.nextInt(3000
));
rightStick.pickUp(phil
);
leftStick.pickUp(phil
);
catch (InterruptedException ie
) {
ie.printStackTrace
();
}
}
}

 

Chopsticks.java - Shared Resources among Philosophers
I'm using Semaphore for this
What is Semaphore?
- Semaphore is basically a permit or a key to access the resources

import java.util.Random;
import java.util.concurrent.Semaphore
;
public class Chopstick 
{
private Random r = new Random
();
private Semaphore s = new Semaphore(5
);
 
private boolean leftCS false
;
private boolean rightCS false
;
 
public void pickUp(int phil
) {
try 
{
if (
s.availablePermits() == 0
) {
System.out.println("Philosopher "   phil   " is THINKING!"
);
Thread.sleep(r.nextInt(3000
));
} else {
leftCS s.tryAcquire
();
if (!
leftCS
) {
System.out.println("Philosopher "   phil   " is THINKING!"
);
Thread.sleep(r.nextInt(3000
));
} else {
System.out.println("Philosopher "   phil   " GETS THE LEFT CHOPSTICK!"
);
rightCS s.tryAcquire
();
if (!
rightCS
) {
System.out.println("Philosopher "   phil   " is WAITING!"
);
Thread.sleep(r.nextInt(3000
));
} else {
System.out.println("Philosopher "   phil   " is EATING"
);
Thread.sleep(r.nextInt(3000
));
}
}
}
catch (InterruptedException ie
) {
ie.printStackTrace
();
finally 
{
System.out.println("Philosopher "   phil   " is THINKING!"
);
s.release
();
}
}

 

Good luck and feel free to optimize it, ask questions, and add up

 

  

Rate this article

Average rating :

 

Your rating :

Comments On : The Dining Philosophers Problem - Java Multithreading
Sumon
Looks Great. Thanks
Sep 02, 2008

Would you like to comment?

Join Paracalls for a free account, or sign in if you are already a member.
Company Sign Up Form
 
Loading ...