5 Replies - 5312 Views - Last Post: 02 March 2011 - 05:30 PM Rate Topic: -----

#1 neo187  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 23-February 11

Dining Philosophers Homework

Posted 02 March 2011 - 03:17 PM

Hi guys. So for my homework I have to implement this twist on the classic Dining Philosophers problem, i.e. a simulation of different threads running concurrently and trying to access the same resources potentially causing deadlock. The original problem is modelling the 5 philosophers grabbing their left and right fork when they all share one... The twist is them having to grab two chopsticks from a central pool... So I modified the code on Wikipedia for the original problem and turned it into the following.


import java.util.concurrent.Semaphore;
import java.util.Random;


public class Philosopher extends Thread
{
    // Shared by each instance
    private static final Random rand = new Random();
    private static int event=0;
    final static int N = 5; // five philosophers, five forks
    public static Semaphore[] fork = new Semaphore[N];
    private int oneOnTop = N;
 
    // My local stuff
    private int id;                  // Who am I
    private Semaphore myFork;        // Resource locks
    private Semaphore myNeighborsFork;
    private int meals = 10;          // Max meals
 
    /**
     * Constructor: an ID# and two shared resources
     * @param i
     * @param fork1
     * @param fork2
     */
    public Philosopher(int i, Semaphore fork1, Semaphore fork2)
    {
        id = i;
        myFork = fork1;
        myNeighborsFork = fork2;
    }
 
    /**
     * "Lazy" message queue.  Original program used a Vector<String> to
     * queue the events and displayed them at the end.  I like having
     * feedback while the program is running, but the messages are
     * sometimes displayed out of order - no biggie.
     *
     * @param str
     */
    private void postMsg(String str) {
        System.out.printf("%d %d. Chopsitcks left: %d. Philosopher %d %s\n",
                System.currentTimeMillis(), ++event, getTopOne(), id, str);
    }
 
    /**
     * Pause - waits a bit (random fraction of a second)
     */
    private void pause()
    {
        try
        {
            sleep(rand.nextInt(4000));
        } catch (InterruptedException e){}
    }
 
    /**
     * Tell philosopher to think - he waits a bit
     *
     */
    private void think()
    {
        postMsg("is thinking");
        pause();
    }
    
    private synchronized void takeOne()
    {
        oneOnTop--;
    }
    
    private synchronized void putBack()
    {
        oneOnTop++;
    }
    
     
    
    private synchronized int getTopOne()
    {
        return oneOnTop;
    }
    
    
 
    /**
     * Tell philosopher to eat.  Tries to acquire resources (forks)
     *
     * Possible modification: Doesn't change a state
     * (hungry, starving, etc.) if they can't get a fork
     *
     * Possible modification: could return a boolean indicating success
     */
    private void trytoeat()
    {
        if (getTopOne() < 2){
            postMsg("is waiting for ennough chopsticks to be on the table");
        } else {
            postMsg("is hungry and is trying to pick up two chopsticks");
        }
        pause();
        try {
            // Semaphore - waits on his own fork if necessary
            takeOne();
            myFork = fork[getTopOne() - 1];
            myFork.acquire();
 
            // He's picked up his own fork, now try and grab his neighbor's fork
            // (does not wait)
            takeOne();
            myNeighborsFork = fork[getTopOne() - 1];
            if (!myNeighborsFork.tryAcquire()) {
                // Unsuccessful, guess he's fasting today
                postMsg(">>>> was not able to get a second chopstick");
                return;
            };
 
            // Success! begins to eat
            postMsg("picked up two chopsticks and is eating meal #" + (10 - --meals));
            pause();
 
            // Now put down the forks
            postMsg("puts down his chopsticks");
            putBack();
            myNeighborsFork.release();
 
        } catch (InterruptedException e) {
            // In case the thread is interrupted
            postMsg("was interrupted while waiting for his fork");
        }
        finally { // always puts his own fork back down
            putBack();
            myFork.release();
        }
    }
 
    /**
     * philosophise until all meals are consumed
     */
    @Override
    public void run()
    {
        while (meals > 0)
        {
            think();
            trytoeat();
        }
    }
 
    /**
     *  Main program
     *  * Create resouces (forks) as semaphores
     *  * create philosophers
     *  * start philosophers
     *  * wait for completion
     */
 
    // Main program
    public static void main(String[] args)
    {
        System.out.println("Begin");
 
        //final int N = 5; // five philosophers, five forks
 
        // Create the forks, 1 fork per philosopher
        //Semaphore[] fork = new Semaphore[N];
        for (int f = 0; f < N; f++) {
            // each fork is a single resource
            fork[f] = new Semaphore(1, true);
        }
 
        // Create the philosophers, pass in their forks
        Philosopher[] philosopher = new Philosopher[N];
        for (int me = 0; me < N; me++) {
            // determine my right-hand neighbor's ID
            int myneighbor = me + 1;
            if (myneighbor == N) myneighbor = 0;
 
            // Initialize each philosopher (no pun intended)
            philosopher[me] = new Philosopher(me, fork[me], fork[myneighbor]); // :)/>
        }
 
        // Start the philosophers
        for (int i = 0; i < N; i++) {
              philosopher[i].start();
        }
 
        // Wait for them to finish
        for (int i = 0; i < N; i++) {
          try {
            philosopher[i].join();
          } catch(InterruptedException ex) { }
        }
 
        // All done
        System.out.println("Done");
    }
}



So basically there's a counter of how many chopsitcks are left in the bowl and everytime a thread trying to reach the bowl the counter goes down by one so that everyone picks a different chopstick (as if they were stacked), and that this can only happen if there's two or more chopsticks left....

But what actually happens is that only one of them ever eats at the same time and that the chopstick counter never goes below 3 chopsticks?? And I don't get why... Here's the output:

1299104007412 24. Chopsitcks left: 3. Philosopher 3 puts down his chopsticks
1299104007414 25. Chopsitcks left: 5. Philosopher 3 is thinking
1299104007415 26. Chopsitcks left: 3. Philosopher 2 picked up two chopsticks and is eating meal #1
1299104009166 27. Chopsitcks left: 5. Philosopher 3 is hungry and is trying to pick up two chopsticks
1299104010531 28. Chopsitcks left: 3. Philosopher 2 puts down his chopsticks
1299104010531 29. Chopsitcks left: 5. Philosopher 2 is thinking
1299104010532 30. Chopsitcks left: 3. Philosopher 0 picked up two chopsticks and is eating meal #2
1299104010821 31. Chopsitcks left: 5. Philosopher 2 is hungry and is trying to pick up two chopsticks
1299104011641 32. Chopsitcks left: 3. Philosopher 0 puts down his chopsticks
1299104011641 33. Chopsitcks left: 5. Philosopher 0 is thinking
1299104011641 34. Chopsitcks left: 3. Philosopher 1 picked up two chopsticks and is eating meal #2
1299104012807 35. Chopsitcks left: 3. Philosopher 1 puts down his chopsticks
1299104012807 36. Chopsitcks left: 5. Philosopher 1 is thinking
1299104012808 37. Chopsitcks left: 3. Philosopher 4 picked up two chopsticks and is eating meal #2
1299104013207 38. Chopsitcks left: 5. Philosopher 0 is hungry and is trying to pick up two chopsticks
1299104015012 39. Chopsitcks left: 3. Philosopher 4 puts down his chopsticks
1299104015014 40. Chopsitcks left: 5. Philosopher 4 is thinking
1299104015022 41. Chopsitcks left: 3. Philosopher 3 picked up two chopsticks and is eating meal #2
1299104015722 42. Chopsitcks left: 5. Philosopher 1 is hungry and is trying to pick up two chopsticks
1299104017438 43. Chopsitcks left: 3. Philosopher 3 puts down his chopsticks
1299104017439 44. Chopsitcks left: 5. Philosopher 3 is thinking
1299104017440 45. Chopsitcks left: 3. Philosopher 2 picked up two chopsticks and is eating meal #2



When in fact they're supposed to try and use all of them and at some point stop because they've run out of chopsticks?? Anybody can see what is wrong with this code??

Thank you

Is This A Good Question/Topic? 0
  • +

Replies To: Dining Philosophers Homework

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10654
  • View blog
  • Posts: 39,565
  • Joined: 27-December 08

Re: Dining Philosophers Homework

Posted 02 March 2011 - 03:40 PM

Why don't you just use the java.util.Stack class since it's already Thread-safe? Have all your Threads try to retrieve an item from the Stack. If the Stack is empty, the Thread should wait() on it. Then when your Thread returns an item to the Stack, invoke notifyAll() on the Stack. Note that this solution does not enforce ordering of your Threads.

If you care about the order that your Threads access the Stack, then you should use a Semaphore. Each Thread should try to acquire a permit, eat, return the permit, then repeat.
Was This Post Helpful? 1
  • +
  • -

#3 neo187  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 23-February 11

Re: Dining Philosophers Homework

Posted 02 March 2011 - 04:16 PM

Hi!

Thanks for your reply! I've replaced my previous system with a Stack of chopsticks, now the program ends almost immediately, which I'm not sure is the expected result?? Is it because they inevitably reach deadlock? This is all the output I'm getting (which is really short in comparison to the old one as there are supposed to be 10 meals?):

Begin
1299107441006 1. Chopsitcks left: 5. Philosopher 0 is thinking
1299107441008 2. Chopsitcks left: 5. Philosopher 1 is thinking
1299107441012 3. Chopsitcks left: 5. Philosopher 2 is thinking
1299107441016 4. Chopsitcks left: 5. Philosopher 3 is thinking
1299107441025 5. Chopsitcks left: 5. Philosopher 4 is thinking
1299107441252 6. Chopsitcks left: 5. Philosopher 2 is hungry and is trying to pick up two chopsticks
1299107441298 7. Chopsitcks left: 3. Philosopher 2 >>>> was not able to get a second chopstick
1299107441299 8. Chopsitcks left: 3. Philosopher 2 is thinking
1299107441799 9. Chopsitcks left: 3. Philosopher 1 is hungry and is trying to pick up two chopsticks
1299107441855 10. Chopsitcks left: 3. Philosopher 2 is hungry and is trying to pick up two chopsticks
1299107443084 11. Chopsitcks left: 3. Philosopher 3 is hungry and is trying to pick up two chopsticks
1299107443709 12. Chopsitcks left: 3. Philosopher 0 is hungry and is trying to pick up two chopsticks
1299107443831 13. Chopsitcks left: 1. Philosopher 0 >>>> was not able to get a second chopstick
1299107443832 14. Chopsitcks left: 1. Philosopher 0 is thinking
1299107444722 15. Chopsitcks left: 0. Philosopher 4 is waiting for ennough chopsticks to be on the table
1299107444829 16. Chopsitcks left: 0. Philosopher 0 is waiting for ennough chopsticks to be on the table
Done



My New code is:
import java.util.concurrent.Semaphore;
import java.util.*;
 
  /**
   * Five Philosopher problem: How to model limited shared resources
   * http://en.wikipedia.org/wiki/Five_philosophers
   * This is an update of the original version posted on WikipediA
   * JEB 11-04-2010
   */


public class Philosopher extends Thread
{
    // Shared by each instance
    private static final Random rand = new Random();
    private static int event=0;
    final static int N = 5; // five philosophers, five forks
    public static Semaphore[] fork = new Semaphore[N];
    private int oneOnTop = N;
    private static Stack<Integer> chopsticks;
 
    // My local stuff
    private int id;                  // Who am I
    private Semaphore myFork;        // Resource locks
    private Semaphore myNeighborsFork;
    private int meals = 10;          // Max meals
 
    /**
     * Constructor: an ID# and two shared resources
     * @param i
     * @param fork1
     * @param fork2
     */
    public Philosopher(int i, Semaphore fork1, Semaphore fork2)
    {
        id = i;
        myFork = fork1;
        myNeighborsFork = fork2;
    }
 
    /**
     * "Lazy" message queue.  Original program used a Vector<String> to
     * queue the events and displayed them at the end.  I like having
     * feedback while the program is running, but the messages are
     * sometimes displayed out of order - no biggie.
     *
     * @param str
     */
    private void postMsg(String str) {
        System.out.printf("%d %d. Chopsitcks left: %d. Philosopher %d %s\n",
                System.currentTimeMillis(), ++event, chopsticks.size(), id, str);
    }
 
    /**
     * Pause - waits a bit (random fraction of a second)
     */
    private void pause()
    {
        try
        {
            sleep(rand.nextInt(4000));
        } catch (InterruptedException e){}
    }
 
    /**
     * Tell philosopher to think - he waits a bit
     *
     */
    private void think()
    {
        postMsg("is thinking");
        pause();
    }
    
    private synchronized int takeOne()
    {
        return chopsticks.pop();
    }
    
    private synchronized void putBack(int c)
    {
        chopsticks.push(c);
    }
    
     
    
    private synchronized int getTopOne()
    {
        return oneOnTop;
    }
    
    
 
    /**
     * Tell philosopher to eat.  Tries to acquire resources (forks)
     *
     * Possible modification: Doesn't change a state
     * (hungry, starving, etc.) if they can't get a fork
     *
     * Possible modification: could return a boolean indicating success
     */
    private void trytoeat()
    {
        if (chopsticks.size() < 2){
            postMsg("is waiting for ennough chopsticks to be on the table");
        } else {
            postMsg("is hungry and is trying to pick up two chopsticks");
        }
        pause();
        try {
            // Semaphore - waits on his own fork if necessary
            int c = takeOne();
            myFork = fork[c];
            myFork.acquire();
 
            // He's picked up his own fork, now try and grab his neighbor's fork
            // (does not wait)
            int c2 = takeOne();
            myNeighborsFork = fork[c];
            if (!myNeighborsFork.tryAcquire()) {
                // Unsuccessful, guess he's fasting today
                postMsg(">>>> was not able to get a second chopstick");
                return;
            };
 
            // Success! begins to eat
            postMsg("picked up two chopsticks and is eating meal #" + (10 - --meals));
            pause();
 
            // Now put down the forks
            postMsg("puts down his chopsticks");
            putBack(c2);
            myNeighborsFork.release();
            putBack(c);
            chopsticks.notifyAll();
 
        } catch (InterruptedException e) {
            // In case the thread is interrupted
            postMsg("was interrupted while waiting for his fork");
        }
        finally { // always puts his own fork back down
           
            myFork.release();
        }
    }
 
    /**
     * philosophise until all meals are consumed
     */
    @Override
    public void run()
    {
        while (meals > 0)
        {
            think();
            trytoeat();
        }
    }
 
    /**
     *  Main program
     *  * Create resouces (forks) as semaphores
     *  * create philosophers
     *  * start philosophers
     *  * wait for completion
     */
 
    // Main program
    public static void main(String[] args)
    {
        System.out.println("Begin");
        
        chopsticks = new Stack<Integer>();
 
        //final int N = 5; // five philosophers, five forks
 
        // Create the forks, 1 fork per philosopher
        //Semaphore[] fork = new Semaphore[N];
        for (int f = 0; f < N; f++) {
            // each fork is a single resource
            fork[f] = new Semaphore(1, true);
        }
        
        
        
        for (int f = 0; f< N; f++){
            try {
                chopsticks.push(new Integer(f));
            } catch(Exception ex) { }
        }
 
        // Create the philosophers, pass in their forks
        Philosopher[] philosopher = new Philosopher[N];
        for (int me = 0; me < N; me++) {
            // determine my right-hand neighbor's ID
            int myneighbor = me + 1;
            if (myneighbor == N) myneighbor = 0;
 
            // Initialize each philosopher (no pun intended)
            philosopher[me] = new Philosopher(me, fork[me], fork[myneighbor]); // :)/>
        }
 
        // Start the philosophers
        for (int i = 0; i < N; i++) {
              philosopher[i].start();
        }
 
        // Wait for them to finish
        for (int i = 0; i < N; i++) {
          try {
            philosopher[i].join();
          } catch(InterruptedException ex) { }
        }
 
        // All done
        System.out.println("Done");
    }
}



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

#4 neo187  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 23-February 11

Re: Dining Philosophers Homework

Posted 02 March 2011 - 04:30 PM

actually what I'm getting (which stops the output) is this

Exception in thread "Thread-5" java.lang.IllegalMonitorStateException
at java.lang.Object.notifyAll(Native Method)
at Philosopher.trytoeat(Philosopher.java:153)
at Philosopher.run(Philosopher.java:168)
Was This Post Helpful? 0
  • +
  • -

#5 n8wxs  Icon User is offline

  • --... ...-- -.. . -. ---.. .-- -..- ...
  • member icon

Reputation: 972
  • View blog
  • Posts: 3,878
  • Joined: 07-January 08

Re: Dining Philosophers Homework

Posted 02 March 2011 - 05:06 PM

I get:

Quote

run:
Begin
1299110566077 1. Chopsitcks left: 5. Philosopher 0 is thinking
1299110566093 2. Chopsitcks left: 5. Philosopher 1 is thinking
1299110566093 3. Chopsitcks left: 5. Philosopher 2 is thinking
1299110566093 4. Chopsitcks left: 5. Philosopher 3 is thinking
1299110566093 5. Chopsitcks left: 5. Philosopher 4 is thinking
1299110566155 6. Chopsitcks left: 5. Philosopher 1 is hungry and is trying to pick up two chopsticks
1299110566858 7. Chopsitcks left: 5. Philosopher 0 is hungry and is trying to pick up two chopsticks
1299110567093 8. Chopsitcks left: 5. Philosopher 3 is hungry and is trying to pick up two chopsticks
1299110567671 9. Chopsitcks left: 3. Philosopher 0 >>>> was not able to get a second chopstick
1299110567671 10. Chopsitcks left: 3. Philosopher 0 is thinking
1299110568343 11. Chopsitcks left: 3. Philosopher 2 is hungry and is trying to pick up two chopsticks
1299110569311 12. Chopsitcks left: 3. Philosopher 4 is hungry and is trying to pick up two chopsticks
1299110569405 13. Chopsitcks left: 1. Philosopher 1 >>>> was not able to get a second chopstick
1299110569405 14. Chopsitcks left: 1. Philosopher 1 is thinking
1299110569577 15. Chopsitcks left: 1. Philosopher 1 is waiting for ennough chopsticks to be on the table
Exception in thread "Thread-3" java.util.EmptyStackException
at java.util.Stack.peek(Stack.java:85)
at java.util.Stack.pop(Stack.java:67)
at philosopher.Philosopher.takeOne(Philosopher.java:76)
at philosopher.Philosopher.trytoeat(Philosopher.java:110)
at philosopher.Philosopher.run(Philosopher.java:146)
Exception in thread "Thread-4" java.util.EmptyStackException
at java.util.Stack.peek(Stack.java:85)
at java.util.Stack.pop(Stack.java:67)
at philosopher.Philosopher.takeOne(Philosopher.java:76)
at philosopher.Philosopher.trytoeat(Philosopher.java:104)
at philosopher.Philosopher.run(Philosopher.java:146)
1299110570593 16. Chopsitcks left: 0. Philosopher 0 is waiting for ennough chopsticks to be on the table
Exception in thread "Thread-0" java.util.EmptyStackException
at java.util.Stack.peek(Stack.java:85)
at java.util.Stack.pop(Stack.java:67)
at philosopher.Philosopher.takeOne(Philosopher.java:76)
at philosopher.Philosopher.trytoeat(Philosopher.java:104)
at philosopher.Philosopher.run(Philosopher.java:146)
Exception in thread "Thread-2" java.util.EmptyStackException
at java.util.Stack.peek(Stack.java:85)
at java.util.Stack.pop(Stack.java:67)
at philosopher.Philosopher.takeOne(Philosopher.java:76)
at philosopher.Philosopher.trytoeat(Philosopher.java:104)
at philosopher.Philosopher.run(Philosopher.java:146)
Exception in thread "Thread-1" java.util.EmptyStackException
at java.util.Stack.peek(Stack.java:85)
at java.util.Stack.pop(Stack.java:67)
at philosopher.Philosopher.takeOne(Philosopher.java:76)
at philosopher.Philosopher.trytoeat(Philosopher.java:104)
at philosopher.Philosopher.run(Philosopher.java:146)
Done
BUILD SUCCESSFUL (total time: 6 seconds)


because:

    private synchronized int takeOne() {
            return chopsticks.pop();
    }



will throw the exception if the the stack is empty.

Better:

    private synchronized int takeOne() {
        if (!chopsticks.empty()) {
            return chopsticks.pop();
        }

        return 0; //// need to flag stack is empty
    }


Was This Post Helpful? 1
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10654
  • View blog
  • Posts: 39,565
  • Joined: 27-December 08

Re: Dining Philosophers Homework

Posted 02 March 2011 - 05:30 PM

A few things about the Wikipedia code. First, globals are very un-OO. Better to make a separate Bowl class to manage the Stack (and possibly the Semaphore). Second, you do not need multiple Semaphores b/c a Semaphore can have multiple permits. So if you go the Semaphore route, it should store the number of permits based on the initialize size of your Stack before starting your Threads.

The reason you are getting an IllegalMonitorStateException is b/c you are using Semaphores, not waiting on the Stack.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1