The Dining Philosophers Problem - Java Multithreading

HelloWorld · #1 (**permalink**) 07-02-2007, 10:06 PM

In 1971, 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:

Code:

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

PHP Code:

  public class DiningPhilosopher {

public static void main(String[] args) {

Chopstick cs = new Chopstick();

Philosopher p1 = new Philosopher(cs, cs, 1);

Philosopher p2 = new Philosopher(cs, cs, 2);

Philosopher p3 = new Philosopher(cs, cs, 3);

Philosopher p4 = new Philosopher(cs, cs, 4);

Philosopher p5 = new Philosopher(cs, cs, 5);

 

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

PHP Code:

  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 r, Chopstick l, int phil) {

this.rightStick = r;

this.leftStick = l;

this.phil = phil;

Thread t1 = new Thread(this);

t1.start();

}

 

public void run() {

for (int i = 1; i <= 10; i++) {

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

PHP Code:

  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 to this thread

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

LinkBacks (?) LinkBack to this Thread: http://www.programmerstalk.net/thread845.html
Posted By	For	Type	Date
Dining Philosophers Problem - Java	This thread	Refback	09-01-2007 05:18 PM
Dining Philosophers Problem - Java	This thread	Refback	07-18-2007 03:00 AM
Dining Philosophers Problem - Java	This thread	Refback	07-14-2007 03:54 AM