Dining Philosophers using semaphores

Question

I'm looking a way to solve the dining philosophers problem using semaphores, I'm quite stuck on how I should go about doing it. I've included my code below.

class ChopStick{
    private int count; 
    private boolean inuse; 
    Lock lock = new ReentrantLock(); 
    Condition notInUse = lock.newCondition(); 

    public ChopStick(){
        inuse = false;
    }

    public void pickUp(){
        lock.lock();
        try{
            while(inuse){
                try{
                    notInUse.await();
                }catch(InterruptedException e){}
            }
            inuse = true;
        }finally{lock.unlock();}
    }

    public void putDown(){
        lock.lock();
        try{
            inuse = false; 
            notInUse.signal();
        }finally{lock.unlock();}
    }
}

class Philosopher extends Thread{
    Semaphore sem;
    private ChopStick ch1,ch2; //chopsticks
    private int phil; //philosopher id

    public Philosopher(int p, ChopStick left, ChopStick right, Semaphore s){
        phil = p; 
        ch1 = left; 
        ch2 = right; 
        sem = s;
    }

    public void run() {
        while(true){
            try {
                sem.acquire();
            } catch (InterruptedException e) {}
                think(phil);
                //pickup chopsticks
                ch1.pickUp();
                ch2.pickUp();
                eat(phil);
                //putdown chopsticks
                ch1.putDown();
                ch2.putDown();
                sem.release();
            }
        }

I'm thinking of when a philosopher picks up a chopstick using sem.acquire() and then when they are finished using sem.release() but I am not sure if this is right. Is it?

Edit So I've implemented this. It seems to work but I'm not sure.

  class ChopStick{
    private Semaphore sem;
    public ChopStick(Semaphore s){
            sem = s;
    }

    public void pickUp(){
            try{
                    sem.acquire();
            }catch(InterruptedException e){}
    }
    public void putDown(){
            sem.release();
    }

Answer 1

Rather than putting a semaphore on the Philosopher, I suggest putting a semaphore on the Chopstick; the Philosopher calls acquire on the left and right chopsticks' semaphores and releases the chopsticks' semaphores when done. This would replace the ReentrantLock on the Chopstick.

To prevent deadlock, you can use tryAcquire(int permits, long timeout, TimeUnit unit) so that a Philosopher releases its left chopstick's semaphore if it fails to acquire its right chopstick's semaphores within a timeout; if you use a random timeout (e.g. between 100 and 500 milliseconds) then each Philosopher should eventually make progress.

Edit: Your new Chopstick code runs the risk of deadlock - all philosophers pick up their left chopstick and then wait forever for their right chopstick to be free. A tryAcquire will allow a philosopher to release its left chopstick if it can't acquire its right chopstick after a timeout, which will allow the philosopher to its left to proceed.

class ChopStick{
  private static Random random = new Random();

  // initialize with one permit
  private Semaphore sem = new Semaphore(1);

  public boolean pickUp(){
    try {
      // wait between 100 and 500 milliseconds
      return sem.tryAcquire(1, random.nextInt(400) + 100, TimeUnit.MILLISECONDS);
    } catch(InterruptedException e) {
      return false;
    }
  }

  public void putDown(){
    sem.release();
  }
}

class Philosopher extends Thread {
  public void run() {
    while(true){
      think(phil);
      doEat();
    }

  private void doEat() {
    if(ch1.pickup()) {
      if(ch2.pickup()) {
        eat(phil);
        ch1.release();
        ch2.release();
      else {
        ch1.release();
        doEat();
      }
    else {
      doEat();
    }
  }
}