71 Let’s Talk About the Classic Philosophers’ Dinner Problem #

In this lesson, we will introduce the classic philosopher dining problem.

Problem Description #

The philosopher dining problem is also known as the fork and knife problem or the noodle eating problem. We first describe what this problem is about, as shown in the following figure:

There are 5 philosophers, and each of them has a pair of chopsticks in front of them. In other words, they have a chopstick in their left hand and a chopstick in their right hand. Of course, there are different versions of this problem, where it could be forks and knives instead of chopsticks, because when eating steak, you need both a knife and a fork, and when eating spaghetti, you might need two forks. Here, the specific utensils used, whether chopsticks or forks and knives, is not important. What’s important is that you must hold both the left and right chopsticks simultaneously. This means that the philosopher must hold a chopstick in their left hand and a chopstick in their right hand in order to be able to eat. For the sake of understanding, we choose chopsticks, which are closest to our traditional Chinese culture, to illustrate this problem.

Why choose philosophers? Because philosophers are known for their contemplative nature, we can abstract their daily activities as thinking and then eating, and when they eat, they must use a pair of chopsticks, rather than just using one chopstick.

1. Main Process

Let’s take a look at the main process of philosophers dining. If a philosopher wants to eat, they will first try to pick up the chopstick in their left hand, and then attempt to pick up the chopstick in their right hand. If one of the chopsticks is being used by someone else, the philosopher needs to wait for that person to finish using it. Once the chopstick is returned to its original position, the philosopher can pick it up and start eating (ignoring hygiene issues). This is the main process of philosophers dining.

2. Pseudocode of the Process

Let’s take a look at the pseudocode of this process, as shown below:

while(true) { 

    // Contemplate life, the universe, and everything...
  
    think();
  
    // After contemplation, feel hungry and need to pick up chopsticks to start eating
  
    pick_up_left_chopstick();
  
    pick_up_right_chopstick();
  
    eat();
  
    put_down_right_chopstick();
  
    put_down_left_chopstick();
  
    // After finishing the meal, continue contemplating life, the universe, and everything...
  
}

while(true) represents an infinite loop. In each iteration of the loop, the philosopher first starts thinking. After a period of time (the duration of which can be random), they start to feel hungry and prepare to eat. Before eating, they must first pick up the chopstick in their left hand, then pick up the chopstick in their right hand, and only then start eating; after finishing their meal, they first put down the chopstick in their right hand and then put down the chopstick in their left hand. Because this is a while loop, the philosopher continues contemplating life and starts the next iteration. This is the entire process.

Risk of Deadlock and Resource Exhaustion #

What risks are there in this scenario? The risk is the occurrence of deadlock. As shown in the animation below:

According to our logic, after picking up the chopstick on the left, the next step is to pick up the chopstick on the right. In most cases, the philosopher on the right is thinking, so the chopstick on the right of the current philosopher is available, or if the philosopher on the right is eating, the current philosopher waits for the right philosopher to finish eating and release the chopstick, so the current philosopher can pick up the chopstick in their right hand.

However, if each philosopher simultaneously picks up the chopstick on their left, then a circular dependency is formed. In this special case, everyone is holding the chopstick in their left hand and is missing the chopstick in their right hand, so no one can start eating, and naturally, no one will put down the chopstick in their hand. This leads to deadlock, creating a situation of mutually waiting. The code is shown below:

public class DiningPhilosophers {

    public static class Philosopher implements Runnable {

        private Object leftChopstick;

        private Object rightChopstick;

        public Philosopher(Object leftChopstick, Object rightChopstick) {

            this.leftChopstick = leftChopstick;

            this.rightChopstick = rightChopstick;

        }

        @Override

        public void run() {

            try {

                while (true) {

                    doAction("Contemplate life, the universe, everything, the soul...");

                    synchronized (leftChopstick) {

                        doAction("Pick up the chopstick on the left");

                        synchronized (rightChopstick) {

                            doAction("Pick up the chopstick on the right");

                            doAction("Eat");

                            doAction("Put down the chopstick on the right");

                        }

                        doAction("Put down the chopstick on the left");

                    }

                }

            } catch (InterruptedException e) {

                e.printStackTrace();

            }

        }

        private void doAction(String action) throws InterruptedException {

            System.out.println(Thread.currentThread().getName() + " " + action);

            Thread.sleep((long) (Math.random() * 10));

        }

    }

    public static void main(String[] args) {

Philosopher[] philosophers = new Philosopher[5];

Object[] chopsticks = new Object[philosophers.length];

for (int i = 0; i < chopsticks.length; i++) {
    chopsticks[i] = new Object();
}

for (int i = 0; i < philosophers.length; i++) {
    Object leftChopstick = chopsticks[i];
    Object rightChopstick = chopsticks[(i + 1) % chopsticks.length];
    philosophers[i] = new Philosopher(rightChopstick, leftChopstick);
    new Thread(philosophers[i], "Philosopher " + (i + 1)).start();
}

In this code, there is an inner class called Philosopher. When creating an instance of this philosopher, which is calling the constructor, two parameters are needed: the left chopstick and the right chopstick. The Philosopher class implements the Runnable interface, and in its run method, there is an infinite loop where the doAction method is called multiple times. The definition of the doAction method is shown below, and it prints the input string and sleeps for a random amount of time.

The random sleep is used to simulate a real-life scenario, as the time for each philosopher to think, eat, and pick up chopsticks would be different. Similarly, in an actual online scenario, the time would also be different, so we use random numbers to simulate it.

Next, let’s take a look at the code inside the while loop. The philosopher will first contemplate about life, then acquire the lock for the left chopstick and print “Picked up left chopstick”. Next, the philosopher will acquire the lock for the right chopstick and print “Picked up right chopstick”, “Eating”, and “Put down right chopstick”. Then, they will exit the synchronized block for the right chopstick and release the lock. Finally, it prints “Put down left chopstick” and exits the synchronized block for the left chopstick, releasing the lock. This completes the process, and the philosopher will continue with the while loop.

Finally, let’s look at the main method. In the main method, 5 philosophers are created, and the corresponding number of chopsticks is created and initialized. Since the chopsticks are only used as lock objects, they are defined as regular Object types.

Next, we need to initialize the philosophers. Initializing a philosopher requires two input parameters: the left chopstick and the right chopstick. In this case, the previously defined chopsticks array is used to assign appropriate values to leftChopstick and rightChopstick. However, there is a special case to consider for the right chopstick of the last philosopher. Since they have already gone through the entire table, they actually pick up the first chopstick, so a modulo operation is performed here.

After creating the philosophers, each of them is passed as a Runnable object to a Thread, and a thread is created and started. After the for loop finishes, all 5 philosophers are started, and they begin to contemplate and eat. One possible execution result is shown below:

Philosopher 1 is contemplating life, the universe, and everything...
Philosopher 3 is contemplating life, the universe, and everything...
Philosopher 2 is contemplating life, the universe, and everything...
Philosopher 4 is contemplating life, the universe, and everything...
Philosopher 5 is contemplating life, the universe, and everything...
Philosopher 4 picked up left chopstick
Philosopher 5 picked up left chopstick
Philosopher 1 picked up left chopstick
Philosopher 3 picked up left chopstick
Philosopher 2 picked up left chopstick

Philosophers 1, 3, 2, 4, and 5 start contemplating almost at the same time. Assuming they contemplate for a similar amount of time, they all try to start eating at almost the same time. They all pick up the left chopstick simultaneously, and this leads to a deadlock state, where nobody can pick up the right chopstick. As a result, nobody can eat, and they are stuck in an infinite wait, which is the classic dining philosophers problem.

Various Solutions #

How should we solve this problem? There are multiple solutions, and here we will discuss a few of them. As we mentioned earlier, to solve the deadlock problem, we just need to violate any of the four necessary conditions for deadlock.

1. Waiter Inspection

The first solution is to introduce a waiter inspection mechanism. For example, we can introduce a waiter who needs to be consulted by each philosopher before they eat: “Can I go and get the chopsticks now?” The waiter will first determine if there is a possibility of deadlock if the philosopher gets the chopsticks. If so, the waiter will say: “You are not allowed to eat now.” This is one solution.

2. Leader Mediation

Based on the deadlock detection and recovery strategy discussed in the previous lecture, we can introduce a leader who conducts regular inspections. If the leader finds that a deadlock has occurred, he will take away the chopsticks from one philosopher and make him put them down. In this way, with the sacrifice of this person, the other philosophers can all eat. This is also a solution.

3. Change the Order of Chopstick Acquisition for One Philosopher

We can also use the deadlock avoidance strategy, which is to avoid deadlock logically. For example, we can change the order of chopstick acquisition for one philosopher. We can let all four philosophers first pick up the chopstick on their left and then the one on their right. However, one philosopher is different from them, as he first picks up the chopstick on his right and then the one on his left. This way, there will be no circular dependency on the same side of the chopsticks, and deadlock will not occur.

Deadlock Resolution #

Let’s write the code for “changing the order of chopstick acquisition” in order to explain this approach. The modified main method is as follows:

public static void main(String[] args) {

    Philosopher[] philosophers = new Philosopher[5];

    Object[] chopsticks = new Object[philosophers.length];

    for (int i = 0; i < chopsticks.length; i++) {

        chopsticks[i] = new Object();

    }

    for (int i = 0; i < philosophers.length; i++) {

        Object leftChopstick = chopsticks[i];

        Object rightChopstick = chopsticks[(i + 1) % chopsticks.length];

        if (i == philosophers.length - 1) {

            philosophers[i] = new Philosopher(rightChopstick, leftChopstick);

        } else {

            philosophers[i] = new Philosopher(leftChopstick, rightChopstick);

        }

        new Thread(philosophers[i], "Philosopher " + (i + 1)).start();

    }

}

The main change here is that when we instantiate the philosopher objects, we originally passed in the left chopstick first and then the right one. However, when we find that a philosopher is the last one, i.e., if (i == philosophers.length - 1), in this case, we pass the chopsticks in reverse order. This means that the philosopher’s sequence of acquiring chopsticks is also reversed: he will first pick up the chopstick on his right and then the one on his left. As a result, all philosophers can think and eat normally without deadlock occurring.

Summary #

Let’s summarize. In this lesson, we introduced the dining philosophers problem and discovered the risk of deadlock involved. We demonstrated the occurrence of deadlock with code examples. Then, we presented several solutions, such as deadlock detection and recovery, deadlock avoidance, and provided a code example for deadlock avoidance.