java - Deadlock occuring in the Dining Philosophers code

Question

Here's my implementation of the Philosopher dinner concurrence problem:
5 philosophers where each one extends Thread:

the problem is everytime the program finish inside a deadlock. I tried different solutions but no one fixed the problem.
maybe someone can give me an help.

this is my program:

import java.util.concurrent.ThreadLocalRandom;

class Fork {
    public static final char FORK = '|';
    public static final char NO_FORK = ' ';
    int id;

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

class Philosopher extends Thread {
    public static final char PHIL_THINKING = '-';
    public static final char PHIL_LEFT_FORK = '=';
    public static final char PHIL_EATING = 'o';
    private final int id;

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

    @Override
    public void run() {
        final int tableOffset = 4 * id;
        final Object leftLock = S5Philosophers.listOfLocks[id];
        final Object rightLock = S5Philosophers.listOfLocks[(id + 1)
                % S5Philosophers.NUM_PHILOSOPHERS];
        final int table__farL = tableOffset + 0;
        final int table__left = tableOffset + 1;
        final int table_philo = tableOffset + 2;
        final int table_right = tableOffset + 3;
        final int table__farR = (tableOffset + 4)
                % (4 * S5Philosophers.NUM_PHILOSOPHERS);

        while (!isInterrupted()) {
            try {
                Thread.sleep(S5Philosophers.UNIT_OF_TIME
                        * (ThreadLocalRandom.current().nextLong(6)));
            } catch (final InterruptedException e) {
                break;
            }
            // Try to get the chopstick on the left
            synchronized (leftLock) {
                synchronized (S5Philosophers.class) {
                    S5Philosophers.dinerTable[table__farL] = Fork.NO_FORK;
                    S5Philosophers.dinerTable[table__left] = Fork.FORK;
                    S5Philosophers.dinerTable[table_philo] = PHIL_LEFT_FORK;
                }

                try {
                    sleep(S5Philosophers.UNIT_OF_TIME * 1);
                } catch (final InterruptedException e) {
                    break;
                }
                // Try to get the chopstick on the right
                synchronized (rightLock) {
                    synchronized (S5Philosophers.class) {
                        S5Philosophers.dinerTable[table_philo] = PHIL_EATING;
                        S5Philosophers.dinerTable[table_right] = Fork.FORK;
                        S5Philosophers.dinerTable[table__farR] = Fork.NO_FORK;
                        //notify();
                    }
                    try {
                        sleep(S5Philosophers.UNIT_OF_TIME * 1);
                    } catch (final InterruptedException e) {
                        break;
                    }
                    // Release fork
                    synchronized (S5Philosophers.class) {
                        S5Philosophers.dinerTable[table__farL] = Fork.FORK;
                        S5Philosophers.dinerTable[table__left] = Fork.NO_FORK;
                        S5Philosophers.dinerTable[table_philo] = PHIL_THINKING;
                        S5Philosophers.dinerTable[table_right] = Fork.NO_FORK;
                        S5Philosophers.dinerTable[table__farR] = Fork.FORK;
                        //notify();
                    }
                }
            }
        }
    }
}

public class S5Philosophers {
    public static final int NUM_PHILOSOPHERS = 5;
    public static final int UNIT_OF_TIME = 50;
    public static final Fork[] listOfLocks = new Fork[NUM_PHILOSOPHERS];
    public static char[] dinerTable = null;

    static {
        for (int i = 0; i < NUM_PHILOSOPHERS; i++)
            listOfLocks[i] = new Fork(i);
    }

    public static void main(final String[] a) {
        final char[] lockedDiner = new char[4 * NUM_PHILOSOPHERS];
        for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
            lockedDiner[4 * i + 0] = Fork.NO_FORK;
            lockedDiner[4 * i + 1] = Fork.FORK;
            lockedDiner[4 * i + 2] = Philosopher.PHIL_LEFT_FORK;
            lockedDiner[4 * i + 3] = Fork.NO_FORK;
        }
        final String lockedString = new String(lockedDiner);

        // safe publication of the initial representation
        synchronized (S5Philosophers.class) {
            dinerTable = new char[4 * NUM_PHILOSOPHERS];
            for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
                dinerTable[4 * i + 0] = Fork.FORK;
                dinerTable[4 * i + 1] = Fork.NO_FORK;
                dinerTable[4 * i + 2] = Philosopher.PHIL_THINKING;
                dinerTable[4 * i + 3] = Fork.NO_FORK;
            }
        }

        for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
            final Thread t = new Philosopher(i);
            // uses this solution to allow terminating the application even if
            // there is a deadlock
            t.setDaemon(true);
            t.start();
        }

        System.out.println("The diner table:");
        long step = 0;
        while (true) {
            step++;

            String curTableString = null;
            synchronized (S5Philosophers.class) {
                curTableString = new String(dinerTable);
            }
            System.out.println(curTableString + "   " + step);

            if (lockedString.equals(curTableString))
                break;
            try {
                Thread.sleep(UNIT_OF_TIME);
            } catch (final InterruptedException e) {
                System.out.println("Interrupted.");
            }
        }
        System.out.println("The diner is locked.");
    }
}

Answer 1

The solution is relatively simple:

1. Philosopher attempts to get fork on left
   SUCCEED -> Continue to step 2
   FAIL -> wait (for a while)
2. Philosopher attempts to get fork on right
   SUCCEED -> Continue to step 3
   FAIL -> Release left fork and wait (for a while)
3. 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!