What is deadlock? A famous joke on the internet explains it as follows:

Interviewer: Explain to us deadlock and we'll hire you!

Me: Hire me and I'll explain it to you ...

A simple deadlock can be explained as an A thread holding the L lock and trying to acquire the P lock, and, at the same time, there is a B thread holding the P lock and trying to acquire the L lock. This kind of deadlock is known as circular wait. Java doesn't have a deadlock detection and resolving mechanism (as databases have), and so a deadlock can be very embarrassing for the application. A deadlock can completely or partially block the application, can cause serious performance penalties, weird behaviors, and so on. Typically, deadlocks are hard to debug, and the only way to solve a deadlock consists of restarting the application and hoping for the best.

The dining philosophers is a famous problem used for illustrating a deadlock. This problem says that five philosophers are sitting around a table. Each of them alternates thinking and eating. In order to eat, a philosopher needs two forks in his hands—the fork from his left-hand side and the fork from his right-hand side. The difficulty is imposed by the fact that there are only five forks. After eating, the philosopher puts both forks back on the table, and they can then be picked up by another philosopher who repeats the same cycle. When a philosopher is not eating, he/she is thinking. The following diagram illustrates this scenario:

The main task is to find a solution to this problem that allows the philosophers to think and eat in such a way so as to avoid being starved to death.

In the code, we can consider each philosopher as a Runnable instance. Being Runnable instances, we can execute them in separate threads. Each philosopher can pick up two forks placed to his left and right. If we represent a fork as a String, then we can use the following code:

public class Philosopher implements Runnable {

  private final String leftFork;
  private final String rightFork;

  public Philosopher(String leftFork, String rightFork) {
    this.leftFork = leftFork;
    this.rightFork = rightFork;
  }

  @Override
  public void run() {
    // implemented below
  }
}

So, a philosopher can pick up leftFork and rightFork. But since the philosophers share these forks, a philosopher must acquire exclusive locks on these two forks. Having an exclusive lock on leftFork and an exclusive lock on rightFork is equivalent to having two forks in his hands. Having exclusive locks on leftFork and rightFork is equivalent to the philosopher eating. Releasing both exclusive locks is equivalent to the philosopher not eating and thinking.

Locking can be achieved via the synchronized keyword as in the following run() method:

@Override
public void run() {

  while (true) {
    logger.info(() -> Thread.currentThread().getName() 
      + ": thinking");
    doIt();

    synchronized(leftFork) {
      logger.info(() -> Thread.currentThread().getName() 
        + ": took the left fork (" + leftFork + ")");
      doIt();

      synchronized(rightFork) {
        logger.info(() -> Thread.currentThread().getName() 
          + ": took the right fork (" + rightFork + ") and eating");
        doIt();

        logger.info(() -> Thread.currentThread().getName() 
          + ": put the right fork ( " + rightFork 
          + ") on the table");
        doIt();
      }

      logger.info(() -> Thread.currentThread().getName() 
        + ": put the left fork (" + leftFork 
        + ") on the table and thinking");
      doIt();
    }
  }
}

A philosopher starts by thinking. After a while he is hungry, so he tries to pick up the left and right forks. If successful he will eat for a while. Afterwards, he put the forks on the table and continues to think until he is hungry again. Meanwhile, another philosopher will eat.

The doIt() method simulates the involved actions (thinking, eating, picking, and putting back the forks) via a random sleep. This can be seen in the code as follows:

private static void doIt() {
  try {
    Thread.sleep(rnd.nextInt(2000));
  } catch (InterruptedException ex) {
    Thread.currentThread().interrupt();
    logger.severe(() -> "Exception: " + ex);
  }
}

Finally, we need forks and the philosophers, see the following code:

String[] forks = {
  "Fork-1", "Fork-2", "Fork-3", "Fork-4", "Fork-5"
};

Philosopher[] philosophers = {
  new Philosopher(forks[0], forks[1]),
  new Philosopher(forks[1], forks[2]),
  new Philosopher(forks[2], forks[3]),
  new Philosopher(forks[3], forks[4]),
  new Philosopher(forks[4], forks[0])
};

Each philosopher will run in a thread, as follows:

Thread threadPhilosopher1 
  = new Thread(philosophers[0], "Philosopher-1");
...
Thread threadPhilosopher5 
  = new Thread(philosophers[4], "Philosopher-5");

threadPhilosopher1.start();
...
threadPhilosopher5.start();

This implementation seems to be OK and may even work fine for a while. However, sooner or later this implementation blocks with output as follows:

[17:29:21] [INFO] Philosopher-5: took the left fork (Fork-5)
...
// nothing happens

This is a deadlock! Each philosopher has his left fork in hand (exclusive lock on it) and waits for the right fork to be on the table (the lock is to be released). Obviously, this expectation cannot be satisfied, since there are only five forks and each philosopher has one in his hands.

In order to avoid this deadlock, there is a pretty simple solution. We just force one of the philosophers to pick up the right fork first. After successfully picking the right fork, he can try to pick the left one. In the code, this is a quick modification to the following line:

// the original line
new Philosopher(forks[4], forks[0])

// the modified line that eliminates the deadlock
new Philosopher(forks[0], forks[4])

This time we can run the application without deadlocks.