Deadlock occuring in the Dining Philosophers code

Question 1

The solution is relatively simple:

Philosopher attempts to get fork on left
SUCCEED -> Continue to step 2
FAIL -> wait (for a while)

Philosopher attempts to get fork on right
SUCCEED -> Continue to step 3
FAIL -> Release left fork and wait (for a while)

Eat and release both forks. Then wait (for a while)

The point to emphasize here is that anytime a philosopher fails to get both forks, he needs to drop any forks he is holding and wait a bit or deadlock will eventually occur.

Perhaps more importantly, what kind of moron uses two forks to eat?

-- EDIT --

Here is a quick example for the Fork

class Fork {
    public static final char FORK = '|';
    public static final char NO_FORK = ' ';
    private int id;
    private Lock lock = new ReentrantLock();

    public Fork(final int id) {
        this.id = id;
    }

    public boolean isHeld() {
        return lock.isLocked();
    }

    // returns true if successfully grabbed!
    public synchronized boolean tryToGrab() {
        return lock.tryLock();
    }

    public void letGo() {
        lock.unlock();
    }
}

Your idea of using a Semaphore object would work just as well. Good luck!

Question 2

I don't have an answer, but I have a couple of suggestions:

(1) This is minor, but don't override Thread: Override Runnable. It's a good habit, but I don't have time to explain why. Just do it.

class Philosopher implements Runnable { ... }
...
Thread t = new Thread(new Philosopher());

(2) Don't use synchronized for this kind of problem: Using java.util.concurrent.locks.Lock will give you a lot more flexibility in how you structure your code.

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

Lock[] listOfLocks = new Lock[NUM_PHILOSOPHERS];
for (int i=0 ; i<listOfLocks.length ; i++) {
    listOfLocks[i] = new ReentrantLock();
}

(3) As @Holger has pointed out, you have chosen a strategy that is prone to deadlock; You'll have to try something else. Unfortunately your strategy is deeply embedded in your code. That means a lot of re-writing for each new strategy that you try.

Think about how you might isolate the strategy from the rest of the code. What if you defined a 'Strategy' interface, and what if each of your Philosopher instances used a Strategy to grab the chopsticks.

interface Strategy {
    //returns after locking both the leftLock and the rightLock
    public void grabSticks(Lock leftLock, Lock rightLock);
}

class Philosopher implements Runnable {
    private final Strategy strategy;

    public Philosopher(Strategy strategy) {
        this.strategy = strategy;
    }

    @Override
    public void run() {
        ...
        while (...) {
            think();
            strategy.grabSticks(leftLock, rightLock);
            eat();
            leftLock.unlock();
            rightLock.unlock();
        }
    }
}

Now, each time you want to try something different, you only have to change the grabSticks() method...

...or methods! There's no reason why each Philosopher has to use the same strategy.

Is my Strategy interface good enough? It's a start anyway, but maybe you could improve on it. Could it be extended to provide the Philosophers with some more sophisticated way of cooperating than just mutely grabbing the chopsticks?

Good luck, and Have fun!

Question 3

Your strategy is to lock on the left fork (or chopstick? Seems you can’t decide…) first. But every philosopher has a different notion of “left fork”. It should be easy to image that it is possible to get into the situation where every philosopher has locked his/her “left fork” in the first step and thus no one can proceed as the “right fork” is locked by the one who sees it as his/her “left fork”.

But you should recognize that situation from your debug output…

As a hint how I would solve such a problem: It is possible to represent the entire table state within a single int value, assigning each fork one bit. So it would be enough for up to 32 philosophers. Now each philosopher will be initialized with a bitmask telling him/her, which forks (s)he needs. Then a single atomic update can be used to allocate both forks/chopsticks at once. So there is no need to deal with single forks then. The allocation may succeed for both or fail leaving the state unchanged. The only thing the philosopher has to remember, besides the invariably assigned fork bits, is whether (s)he currently owns these two forks. After (s)he has finished eating (s)he will put both forks back in a single update as well.

This strategy would solve the deadlock problem but not the theoretically possible starvation of one philosopher (though it is rather unlikely). For my real life applications that is not an issue, I never create multi-threaded code that relies on lock fairness.

But if you want to preclude the possibility of starvation entirely you can expand the algorithm described above to a subclass of AbstractQueuedSynchronizer. This class is an extension to the concept of using an atomic int to represent the state and supports waiting for the desired resources (bits) to become available. It’s class documentation describes how fair waiting can be implemented so no philosopher has to starve…