7 Replies - 16051 Views - Last Post: 03 March 2009 - 07:59 AM Rate Topic: -----

#1 tdd5024  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 31-October 07

Dining Philosophers Homework

Posted 27 February 2009 - 07:32 PM

Hello everyone,

I am new to Java, but I am in a course that requires it :angry: . Oh well, I guess I'll just have to suck it up. My problem right now is multithreading, and our teacher was nice enough to give us the most unoriginal problem on it - Dining Philosophers. I have the general idea down, but I am unfortunately stuck on a simple problem. Here is my chopstick code, philosopher code, and diningphilosopher code, in that order:

public class Chopstick {

	private boolean isAvailable;

	public Chopstick(boolean isAvailable) {
	this.isAvailable = isAvailable;
	}

	public synchronized void returnChopstick() {
		isAvailable = true;
		notifyAll();
	}

	public synchronized void takeChopstick() throws InterruptedException {
		while (!isAvailable){
			wait();
		}
		isAvailable = false;
	}
}





public class Philosopher implements Runnable {

	private int index;
	private int cycles;
	private Random random = new Random();
	private Chopstick left;
	private Chopstick right;

	public Philosopher(int index, int cycles, Chopstick left, Chopstick right) {
		this.index = index;
		this.cycles = cycles;
		this.left = left;
		this.right = right;
	}

	private void print(String message) {
		System.out.print("Philosopher " + index + message);
	}

	public void run() {
		try {
			for (int i = 0; i < cycles; i++) {
				print("is thinking");
				Thread.sleep(random.nextInt(10000));
				print("is hungry");
				if (index % 2 == 1) {
					print("is grabbing left chopstick");
					left.takeChopstick();
					print("is grabbing right chopstick");
					right.takeChopstick();
				} else {
					if (index == 4) {
						print("is grabbing right chopstick");
						right.takeChopstick();
					} else {
						print("is grabbing left chopstick");
						left.takeChopstick();
						print("is grabbing right chopstick");
						right.takeChopstick();
					}
				}

				print("is eating");
				Thread.sleep(random.nextInt(10000));
				print("is putting down chopsticks");
				left.returnChopstick();
				right.returnChopstick();
				print("is finished eating");
			}
		} catch (InterruptedException e) {
			print("is interrupted");
		}
	}
}




public class DiningPhilosophers {

	public static void main(String args[]) {
		int num = 5;
		int cycles = 10;
		Chopstick[] chopsticks = new Chopstick[num];
		Philosopher[] philosophers = new Philosopher[num];
		for (int i = 0; i < num; i++) {
			chopsticks[i] = new Chopstick(true);
		}
		for (int i = 0; i < num; i++) {
			if (i > 0) {
			Chopstick left = chopsticks[i-1];
			Chopstick right = chopsticks[i];
			}
			if (i == 0) {
				Chopstick left = chopsticks[num-1];
				Chopstick right = chopsticks[i];
			}


			philosophers[i] = new Philosopher(i, num, left, right);
		}

		System.out.print("\n");
	}
}



The program doesn't like that I'm going into the negatives for the array pointer, but I tried to not do that by using the conditional if statement. Unfortunately that proposes a problem of what if the philosopher doesn't get a left and a right. So for my finale, I am asking how do I get around this problem?

Is This A Good Question/Topic? 0
  • +

Replies To: Dining Philosophers Homework

#2 F!st!cuffs  Icon User is offline

  • D.I.C Head

Reputation: 12
  • View blog
  • Posts: 153
  • Joined: 15-July 08

Re: Dining Philosophers Homework

Posted 27 February 2009 - 08:25 PM

The simple answer is you don't. The whole point to this problem is to show you the downside of threading, "Deadlock".

If you would like to get around it though you could not let them pick up either until isAvailable is true on both sides of philosiphers[i]. You could probably just use a boolean wait operator in the philosopher class.

For a good grade on this assignment make sure your program will eventually deadlock.
For self-satisfaction avoid deadlock :D
Was This Post Helpful? 0
  • +
  • -

#3 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8347
  • View blog
  • Posts: 31,912
  • Joined: 06-March 08

Re: Dining Philosophers Homework

Posted 27 February 2009 - 10:09 PM

Don't really understand what you are trying to do... and how you can have a problem running this program because this program won't even compile.

In DiningPhilosophers:

philosophers[i] = new Philosopher(i, num, left, right);

left and right are not defined so the compiler will complaint
Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8347
  • View blog
  • Posts: 31,912
  • Joined: 06-March 08

Re: Dining Philosophers Homework

Posted 27 February 2009 - 10:33 PM

OK corrected your left and right Chopsticks
but this code does nothing...
I guess you ned a philopher[i].start() somewhere

public class DiningPhilosophers {

	public static void main(String args[]) {
		int num = 5;
		int cycles = 10;
		Chopstick left = null, right = null;
		Chopstick[] chopsticks = new Chopstick[num];
		Philosopher[] philosophers = new Philosopher[num];
		for (int i = 0; i < num; i++) {
			chopsticks[i] = new Chopstick(true);
		}
		for (int i = 0; i < num; i++) {
			if (i > 0) {
				left = chopsticks[i-1];
				right = chopsticks[i];
			}
			if (i == 0) {
				left = chopsticks[num-1];
				right = chopsticks[i];
			}


			philosophers[i] = new Philosopher(i, num, left, right);
		}

		System.out.print("\n");
	}
}


Was This Post Helpful? 0
  • +
  • -

#5 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8347
  • View blog
  • Posts: 31,912
  • Joined: 06-March 08

Re: Dining Philosophers Homework

Posted 27 February 2009 - 10:44 PM

I added a println() in the print() method of philosopher because all output were on the same line

   private void print(String message) {
		System.out.println("Philosopher " + index + " " + message);
	}



And added the code to start the thread

			philosophers[i] = new Philosopher(i, num, left, right);
			Thread thread = new Thread(philosophers[i]);
			thread.start();



By the way the "cycles" variable in DiningPhilosophers is not used.
And here is the output... is that what you are expecting ?

Philosopher 1 is thinking
Philosopher 3 is thinking
Philosopher 0 is thinking
Philosopher 2 is thinking
Philosopher 4 is thinking
Philosopher 3 is hungry
Philosopher 3 is grabbing left chopstick
Philosopher 3 is grabbing right chopstick
Philosopher 3 is eating
Philosopher 1 is hungry
Philosopher 1 is grabbing left chopstick
Philosopher 1 is grabbing right chopstick
Philosopher 1 is eating
Philosopher 2 is hungry
Philosopher 2 is grabbing left chopstick
Philosopher 0 is hungry
Philosopher 0 is grabbing left chopstick
Philosopher 0 is grabbing right chopstick
Philosopher 4 is hungry
Philosopher 4 is grabbing right chopstick
Philosopher 3 is putting down chopsticks
Philosopher 3 is finished eating
Philosopher 3 is thinking
Philosopher 3 is hungry
Philosopher 3 is grabbing left chopstick
Philosopher 3 is grabbing right chopstick
Philosopher 3 is eating
Philosopher 1 is putting down chopsticks
Philosopher 1 is finished eating
Philosopher 1 is thinking
Philosopher 0 is eating
Philosopher 2 is grabbing right chopstick
Philosopher 3 is putting down chopsticks
Philosopher 3 is finished eating
Philosopher 3 is thinking
Philosopher 2 is eating
Philosopher 1 is hungry
Philosopher 1 is grabbing left chopstick
Philosopher 2 is putting down chopsticks
Philosopher 2 is finished eating
Philosopher 2 is thinking
Philosopher 3 is hungry
Philosopher 3 is grabbing left chopstick
Philosopher 3 is grabbing right chopstick
Philosopher 3 is eating
Philosopher 2 is hungry
Philosopher 2 is grabbing left chopstick
Philosopher 2 is grabbing right chopstick
Philosopher 0 is putting down chopsticks
Philosopher 0 is finished eating
Philosopher 0 is thinking
Philosopher 4 is eating
Philosopher 1 is grabbing right chopstick
Philosopher 4 is putting down chopsticks
Philosopher 4 is finished eating
Philosopher 4 is thinking
Philosopher 3 is putting down chopsticks
Philosopher 3 is finished eating
Philosopher 3 is thinking
Philosopher 2 is eating
Philosopher 2 is putting down chopsticks
Philosopher 2 is finished eating
Philosopher 2 is thinking
Philosopher 1 is eating
Philosopher 4 is hungry
Philosopher 4 is grabbing right chopstick
Philosopher 4 is eating
Philosopher 3 is hungry
Philosopher 3 is grabbing left chopstick
Philosopher 3 is grabbing right chopstick
Philosopher 3 is eating
Philosopher 0 is hungry
Philosopher 0 is grabbing left chopstick
Philosopher 2 is hungry
Philosopher 2 is grabbing left chopstick
Philosopher 1 is putting down chopsticks
Philosopher 1 is finished eating
Philosopher 1 is thinking
Philosopher 2 is grabbing right chopstick
Philosopher 4 is putting down chopsticks
Philosopher 0 is grabbing right chopstick
Philosopher 0 is eating
Philosopher 4 is finished eating
Philosopher 4 is thinking
Philosopher 4 is hungry
Philosopher 4 is grabbing right chopstick
Philosopher 1 is hungry
Philosopher 1 is grabbing left chopstick
Philosopher 3 is putting down chopsticks
Philosopher 2 is eating
Philosopher 3 is finished eating
Philosopher 3 is thinking
Philosopher 0 is putting down chopsticks
Philosopher 0 is finished eating
Philosopher 0 is thinking
Philosopher 4 is eating
Philosopher 1 is grabbing right chopstick
Philosopher 0 is hungry
Philosopher 0 is grabbing left chopstick
Philosopher 3 is hungry
Philosopher 3 is grabbing left chopstick
Philosopher 2 is putting down chopsticks
Philosopher 2 is finished eating
Philosopher 3 is grabbing right chopstick
Philosopher 3 is eating
Philosopher 1 is eating
Philosopher 2 is thinking
Philosopher 4 is putting down chopsticks
Philosopher 4 is finished eating
Philosopher 4 is thinking
Philosopher 0 is grabbing right chopstick
Philosopher 1 is putting down chopsticks
Philosopher 1 is finished eating
Philosopher 1 is thinking
Philosopher 0 is eating
Philosopher 3 is putting down chopsticks
Philosopher 3 is finished eating
Philosopher 2 is hungry
Philosopher 2 is grabbing left chopstick
Philosopher 2 is grabbing right chopstick
Philosopher 2 is eating
Philosopher 4 is hungry
Philosopher 4 is grabbing right chopstick
Philosopher 1 is hungry
Philosopher 1 is grabbing left chopstick
Philosopher 0 is putting down chopsticks
Philosopher 4 is eating
Philosopher 0 is finished eating
Philosopher 0 is thinking
Philosopher 1 is grabbing right chopstick
Philosopher 2 is putting down chopsticks
Philosopher 2 is finished eating
Philosopher 2 is thinking
Philosopher 1 is eating
Philosopher 0 is hungry
Philosopher 0 is grabbing left chopstick
Philosopher 1 is putting down chopsticks
Philosopher 1 is finished eating
Philosopher 1 is thinking
Philosopher 4 is putting down chopsticks
Philosopher 0 is grabbing right chopstick
Philosopher 0 is eating
Philosopher 4 is finished eating
Philosopher 4 is thinking
Philosopher 2 is hungry
Philosopher 2 is grabbing left chopstick
Philosopher 2 is grabbing right chopstick
Philosopher 2 is eating
Philosopher 1 is hungry
Philosopher 1 is grabbing left chopstick
Philosopher 2 is putting down chopsticks
Philosopher 2 is finished eating
Philosopher 4 is hungry
Philosopher 4 is grabbing right chopstick
Philosopher 0 is putting down chopsticks
Philosopher 0 is finished eating
Philosopher 0 is thinking
Philosopher 4 is eating
Philosopher 1 is grabbing right chopstick
Philosopher 1 is eating
Philosopher 4 is putting down chopsticks
Philosopher 4 is finished eating
Philosopher 1 is putting down chopsticks
Philosopher 1 is finished eating
Philosopher 0 is hungry
Philosopher 0 is grabbing left chopstick
Philosopher 0 is grabbing right chopstick
Philosopher 0 is eating
Philosopher 0 is putting down chopsticks
Philosopher 0 is finished eating

I guess the problem would be more interesting with a single pair of Chopsticks

This post has been edited by pbl: 27 February 2009 - 11:14 PM

Was This Post Helpful? 0
  • +
  • -

#6 F!st!cuffs  Icon User is offline

  • D.I.C Head

Reputation: 12
  • View blog
  • Posts: 153
  • Joined: 15-July 08

Re: Dining Philosophers Homework

Posted 27 February 2009 - 11:38 PM

I tweaked the philosopher class a little bit so it would pick up which ever chopstick is available. The IsAvailable() method just returns the isAvailable variable so if it's not there he won't pick it up. If you run this a few times it will eventually deadlock where everyone will grab the left chopstick and wait for the right one for all the cycles. You will probably need to fix or tweak a few things but this and pbl's fixes should get you going.
public class Philosopher implements Runnable {

	private int index;
	private int cycles;
	private Random random = new Random();
	private Chopstick left;
	private Chopstick right;
	private int HasChopsticks;

	public Philosopher(int index, int cycles, Chopstick left, Chopstick right) {
		this.index = index;
		this.cycles = cycles;
		this.left = left;
		this.right = right;
		this.HasChopsticks = 0;
	}

	private void print(String message) {
		System.out.print("\nPhilosopher " + index + message);
	}

	public void run() {
		try {
			for (int i = 0; i < cycles; i++) {
				if ( HasChopsticks == 0 ) {
					print(" is thinking");
					Thread.sleep(random.nextInt(3000));
				}
				print(" is hungry");
				if (left.IsAvailable()) {
					print(" is grabbing left chopstick");
					left.takeChopstick();
					HasChopsticks += 1;
					Thread.sleep(random.nextInt(3000));
				} else if (right.IsAvailable()) {
					print(" is grabbing right chopstick");
					right.takeChopstick();
					HasChopsticks += 1;
					Thread.sleep(random.nextInt(3000));
				} 
				if ( HasChopsticks == 2 ) {
					print(" is eating");
					Thread.sleep(random.nextInt(3000));
					print(" is putting down chopsticks");
					left.returnChopstick();
					right.returnChopstick();
					print(" is finished eating");
					HasChopsticks = 0;
				} else {
					print(" is waiting for chopstick");
					Thread.sleep(random.nextInt(3000));
					
				}

				
			}
		} catch (InterruptedException e) {
			print(" is interrupted");
		}
	}
}


Was This Post Helpful? 0
  • +
  • -

#7 tdd5024  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 31-October 07

Re: Dining Philosophers Homework

Posted 28 February 2009 - 09:58 AM

wow, this topic gained alot of speed in a short amount of time. Thank you all for your inputs, I was just looking for help with the for loop in the main program where the chopsticks were designated.

And I was trying to make a program with a single set of chopsticks. There are the same amount of chopsticks as philosophers at the table. Or atleast that's what I thought I was doing.

Again, thank you very much for your inputs.
Was This Post Helpful? 0
  • +
  • -

#8 tdd5024  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 31-October 07

Re: Dining Philosophers Homework

Posted 03 March 2009 - 07:59 AM

I got to the point of using wait and notify to not deadlock and run the program efficiently, however, I am also supposed to implement ArrayBlockingQueue for the Chopstick. So here is my code, in DiningPhilosopher, Philosopher, and Chopstick order. My problem here is I am reaching deadlock and I have no clue how to stop it. Are there any suggestions?

public class DiningPhilosopher2 {

	Scanner newScanner = new Scanner(System.in);

	public static void main(String args[]) {
		int num = 0;
		int cycles = 0;
		Scanner newScanner = new Scanner(System.in);
		System.out.print("How many philosophers are dining tonight? ");
		num = newScanner.nextInt();
		System.out.print("\n");
		while (num <= 1) {
			System.out.print("How many philosophers are dining tonight? ");
			num = newScanner.nextInt();
			System.out.print("\n");
		}
		System.out.print("How many cycles will they go through? ");
		cycles = newScanner.nextInt();
		System.out.print("\n");
		while (cycles <= 0) {
			System.out.print("How many cycles will they go through? ");
			cycles = newScanner.nextInt();
			System.out.print("\n");
		}
		Chopstick2 left2 = null, right2 = null;
		Chopstick2[] chopsticks = new Chopstick2[num];
		Philosopher2[] philosophers = new Philosopher2[num];
		for (int i = 0; i < num; i++) {
			chopsticks[i] = new Chopstick2();
		}
		for (int i = 0; i < num; i++) {
			if (i > 0) {
				left2 = chopsticks[i - 1];
				right2 = chopsticks[i];
			}
			if (i == 0) {
				left2 = chopsticks[num - 1];
				right2 = chopsticks[i];
			}


			philosophers[i] = new Philosopher2(i, cycles, left2, right2);
			Thread thread = new Thread(philosophers[i]);
			thread.start();
		}


		System.out.print("\n");
	}
}



public class Philosopher2 implements Runnable {

	private int index;
	private int cycles;
	private Random random = new Random();
	private Chopstick2 left2;
	private Chopstick2 right2;
	private int hasChopsticks;
	private boolean isAvailable;

	public Philosopher2(int index, int cycles,
			Chopstick2 left2, Chopstick2 right2) {
		this.index = index;
		this.cycles = cycles;
		this.left2 = left2;
		this.right2 = right2;
		this.hasChopsticks = 0;
	}

	private void print(String message) {
		System.out.println("Philosopher " + index + message);
	}

	public void run() {
		try {
			for (int i = 0; i < cycles; i++) {
				if (hasChopsticks == 0) {
					print(" is thinking");
					Thread.sleep(random.nextInt(10000));
				}
				print(" is hungry");
				if (index == 0) {
					print(" is grabbing left chopstick");
					left2.takeChopstick2();
					hasChopsticks += 1;
					if (hasChopsticks == 1) {
						print(" is grabbing right chopstick");
						right2.takeChopstick2();
						hasChopsticks += 1;
					}
					if (hasChopsticks == 2) {
						print(" is eating");
						Thread.sleep(random.nextInt(3000));
						print(" is putting down chopsticks");
						left2.returnChopstick2();
						right2.returnChopstick2();
						print(" is finished eating");
						hasChopsticks = 0;
					}
				} else if (index != 0) {

					print(" is grabbing right chopstick");
					right2.takeChopstick2();
					hasChopsticks += 1;
					if (hasChopsticks == 1) {
						print(" is grabbing left chopstick");
						left2.takeChopstick2();
						hasChopsticks += 1;
					}
					if (hasChopsticks == 2) {
						print(" is eating");
						Thread.sleep(random.nextInt(3000));
						print(" is putting down chopsticks");
						left2.returnChopstick2();
						right2.returnChopstick2();
						print(" is finished eating");
						hasChopsticks = 0;
					}
				}
			}
		} catch (InterruptedException e) {
			print(" is interrupted");
		}
	}
}



public class Chopstick2 {

	private ArrayBlockingQueue chopstick = new ArrayBlockingQueue(1);

	public Chopstick2() {
	}

	public synchronized void returnChopstick2() throws InterruptedException {
		chopstick.put(1);
	}

	public synchronized void takeChopstick2() throws InterruptedException {
		chopstick.take();
	}
}



Thanks for your help! :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1