The Dining Philosophers problem and different ways of solving it

24.01.2021 in Computer Science → Concurrency Last modified at: 14.03.2021

The dining philosophers problem is a well-known problem in computer science, originally formulated by Edsger Dijkstra to illustrate the possibility of deadlocks in programs where multiple threads lock and unlock multiple shared resources, such that a situation in which every thread is waiting for actions from other threads and no thread can thus continue it’s normal execution may occur. We will consider different approaches for solving this problem in the present post.

The problem

The dining philosophers problem has different formulations and variations. We will consider one classic definition:

• $n$ philosophers (philosophers $0,1,\dots,n-1$) are sitting at a round table.
• Each philosopher has a plate in front of him. Each plate has a fork to the left and to the right of it. However, if any 2 philosophers sit next to each other, they share 1 fork as illustrated below, for $n = 8$.

Each philosopher behaves independently from other philosophers, but in accordance with the following scenario:

1. Think for some time.
2. Take the right fork.
3. Take the left fork.
4. Eat food.
5. Put the left fork back.
6. Put the right fork back.
7. Repeat the whole process again, i.e. go to step 1.

If a philosopher wants to take a fork, but this fork is currently used by the neighbor, the philosopher waits until the neighbor puts the fork back before getting it. If two neighbors try to take one fork at the same time, only one of them succeeds and the other one waits.

From a programmer’s perspective, each philosopher is a thread performing these actions in an infinite loop.

// file: "Philosopher.java"
public class Philosopher extends Thread {

    private final int id;
    private final Fork leftFork;
    private final Fork rightFork;

    public Philosopher(int id, Fork leftFork, Fork rightFork) {
        this.id = id;
        this.leftFork = leftFork;
        this.rightFork = rightFork;
    }

    @Override
    public void run() {
        for (;;) {
            System.out.println("Philosopher " + id + " is thinking...");
            rightFork.take(id);
            System.out.println("Philosopher " + id + " took the right fork " + rightFork.id);
            leftFork.take(id);
            System.out.println("Philosopher " + id + " took the left fork " + leftFork.id);
            System.out.println("Philosopher " + id + " is eating...");
            leftFork.put(id);
            System.out.println("Philosopher " + id + " has put down the left fork " + leftFork.id);
            rightFork.put(id);
            System.out.println("Philosopher " + id + " has put down the right fork " + rightFork.id);
        }
    }

}

Forks are essentially resources shared under mutual exclusion. In computer science, such data structures are called monitors. In Java, they can be implemented easily with synchronized methods. As mentioned above, a fork can only be used by one philosopher at a time, so we can use the wait() method to wait in case the fork is not available, and notify() some waiting philosopher (thread) if the fork is not being used anymore:

// file: "Fork.java"
public class Fork {

    public final int id;
    private boolean forkIsOnTheTable = true;
    private int philosopherUsingThisFork;

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

    public synchronized void take(int philosopher) {

        while (!forkIsOnTheTable) {
            try {
                wait();
            }
            catch (InterruptedException ignored) {}
        }

        philosopherUsingThisFork = philosopher;

        forkIsOnTheTable = false;

    }

    public synchronized void put(int philosopher) {

        if (!forkIsOnTheTable && philosopherUsingThisFork == philosopher) {
            forkIsOnTheTable = true;
            notify();
        }

    }

}

Finally, the round table described and illustrated above can be simulated as follows:

// file: "DiningPhilosophers.java"
public class DiningPhilosophers {

    public static Philosopher[] createPhilosophers(int n) {

        Fork[] forks = new Fork[n];

        for (int i = 0; i < n; i++) {
            forks[i] = new Fork(i);
        }

        Philosopher[] philosophers = new Philosopher[n];

        for (int i = 0; i < n; i++) {

            Fork leftFork = forks[i];
            Fork rightFork = forks[(i + 1) % n];

            philosophers[i] = new Philosopher(i, leftFork, rightFork);

        }

        return philosophers;

    }

    public static void main(String[] args) {

        Philosopher[] philosophers = createPhilosophers(8);

        for (Philosopher philosopher : philosophers) {
            philosopher.start();
        }

    }

}

By running the listed program, we can observe different concurrent scenarios of philosophers thinking, competing for forks and eating. For example, I got the following output, after which the program neither terminated nor printed anything else:

Philosopher 0 is thinking...
Philosopher 1 is thinking...
Philosopher 2 is thinking...
Philosopher 3 is thinking...
Philosopher 0 took the right fork 1
Philosopher 0 took the left fork 0
Philosopher 0 is eating...
Philosopher 0 has put down the left fork 0
Philosopher 0 has put down the right fork 1
Philosopher 1 took the right fork 2
Philosopher 1 took the left fork 1
Philosopher 1 is eating...
Philosopher 1 has put down the left fork 1
Philosopher 1 has put down the right fork 2
Philosopher 1 is thinking...
Philosopher 0 is thinking...
Philosopher 2 took the right fork 3
Philosopher 4 is thinking...
Philosopher 5 is thinking...
Philosopher 3 took the right fork 4
Philosopher 1 took the right fork 2
Philosopher 0 took the right fork 1
Philosopher 0 took the left fork 0
Philosopher 0 is eating...
Philosopher 0 has put down the left fork 0
Philosopher 1 took the left fork 1
Philosopher 1 is eating...
Philosopher 1 has put down the left fork 1
Philosopher 1 has put down the right fork 2
Philosopher 1 is thinking...
Philosopher 2 took the left fork 2
Philosopher 2 is eating...
Philosopher 2 has put down the left fork 2
Philosopher 2 has put down the right fork 3
Philosopher 2 is thinking...
Philosopher 0 has put down the right fork 1
Philosopher 0 is thinking...
Philosopher 4 took the right fork 5
Philosopher 6 is thinking...
Philosopher 7 is thinking...
Philosopher 5 took the right fork 6
Philosopher 2 took the right fork 3
Philosopher 1 took the right fork 2
Philosopher 0 took the right fork 1
Philosopher 6 took the right fork 7
Philosopher 7 took the right fork 0

By reading this output upwards, we can see that the last thing each philosopher did was to take the right fork. After that, all philosophers need to take the left fork, so all of them wait for each other to return the right fork after eating, but no one can eat, so the program comes to a deadlock state.

By the way, in most cases if you run this program, it will probably hang after a lot more operations, but we can provoke a deadlock (the situation described above) by adding Thread.yield() before leftFork.get(id); in the run() method of the Philosopher class. This will recommend the JVM to reschedule threads after the current philosopher has taken only one fork.

The simplest possible scenario leading to a deadlock can be illustrated with the following diagram:

In this diagram, inclined arrows should be understood as lock-actions where the order in which threads perform them doesn’t matter. On the other hand, the horizontal line means that the threads should be “synchronized” at this point.

Avoiding the deadlock with a semaphore

The program comes to a deadlock if there are $n$ threads, such that the last operation each thread performed is locking a fork. We can use an $n-1$-permit semaphore to ensure that this never happens:

// file: "Philosopher.java"
import java.util.concurrent.Semaphore;

public class Philosopher extends Thread {

    private static final Semaphore semaphore = new Semaphore(7);

    private final int id;
    private final Fork leftFork;
    private final Fork rightFork;

    public Philosopher(int id, Fork leftFork, Fork rightFork) {
        this.id = id;
        this.leftFork = leftFork;
        this.rightFork = rightFork;
    }

    @Override
    public void run() {
        for (;;) {
            System.out.println("Philosopher " + id + " is thinking...");
            semaphore.acquireUninterruptibly();
            rightFork.take(id);
            System.out.println("Philosopher " + id + " took the right fork " + rightFork.id);
            leftFork.take(id);
            semaphore.release();
            System.out.println("Philosopher " + id + " took the left fork " + leftFork.id);
            System.out.println("Philosopher " + id + " is eating...");
            leftFork.put(id);
            System.out.println("Philosopher " + id + " has put down the left fork " + leftFork.id);
            rightFork.put(id);
            System.out.println("Philosopher " + id + " has put down the right fork " + rightFork.id);
        }
    }

}

In other words, the idea of this solution is to make sure only $n - 1$ threads at most are “stuck” in the dangerous zone - between lines rightFork.get(id); and leftFork.get(id);. With this change to the Philosopher class, deadlock’s aren’t possible anymore.

One philosopher can just be left-handed

We can systematically analyze the deadlock occurring in the program if we consider 4 necessary conditions for a deadlock, according to Edward Coffman:

1. Mutual exclusion — at least one held resource must be non-sharable.
2. Hold and wait — there exists at least one process holding a resource and waiting for another one.
3. No preemption — resources cannot be preempted. For example, it is impossible to force a thread to release a lock safely.
4. Circular wait — Processes wait for each other in a cycle.

Turning to the present problem, we see directly that the first 3 conditions hold.

We can analyze whether the circular-condition holds by constructing the so-called precedence-graph. For each resource (in this case, for each fork), we create a node. If it is possible, that process $P_i$ in some state locks resource $a$ and waits for resource $b$, then node $(a, b)$ should be added to the graph:

Clearly, there is a cycle in this graph, so a state in which all threads wait for each other is possible (Circular-wait condition holds).

In order to make the graph acyclic, it is sufficient to just flip the direction of one arbitrary arrow. In terms of the problem, this means changing the behavior of one philosopher to first take the left fork, and then the right one. It doesn’t matter in which order forks are put back on the table. So, this change will prevent deadlocks:

// file: "Philosopher.java"
public class Philosopher extends Thread {

    private final int id;
    private final Fork leftFork;
    private final Fork rightFork;

    public Philosopher(int id, Fork leftFork, Fork rightFork) {
        this.id = id;
        this.leftFork = leftFork;
        this.rightFork = rightFork;
    }

    @Override
    public void run() {
        for (;;) {
            System.out.println("Philosopher " + id + " is thinking...");
            if (id == 0) {
                leftFork.take(id);
                System.out.println("Philosopher " + id + " took the left fork " + leftFork.id);
                rightFork.take(id);
                System.out.println("Philosopher " + id + " took the right fork " + rightFork.id);
            }
            else {
                rightFork.take(id);
                System.out.println("Philosopher " + id + " took the right fork " + rightFork.id);
                leftFork.take(id);
                System.out.println("Philosopher " + id + " took the left fork " + leftFork.id);
            }
            System.out.println("Philosopher " + id + " is eating...");
            leftFork.put(id);
            System.out.println("Philosopher " + id + " has put down the left fork " + leftFork.id);
            rightFork.put(id);
            System.out.println("Philosopher " + id + " has put down the right fork " + rightFork.id);
        }
    }

}

This code changes the behavior of philosopher 0 — now this philosopher first takes the left fork, leading us to the following acyclic precedence graph:

Even more efficient solution

When possible, it is a good idea to get rid of long paths in the precedence graph, because this will improve the overall concurrency of the system. In this case, we can make even philosophers first take the left fork and odd ones — the right fork first. This idea leads us to the following precedence graph:

and the little change in code:

// file: "Philosopher.java"
public class Philosopher extends Thread {

    private final int id;
    private final Fork leftFork;
    private final Fork rightFork;

    public Philosopher(int id, Fork leftFork, Fork rightFork) {
        this.id = id;
        this.leftFork = leftFork;
        this.rightFork = rightFork;
    }

    @Override
    public void run() {
        for (;;) {
            System.out.println("Philosopher " + id + " is thinking...");
            if (id % 2 == 0) {
                leftFork.take(id);
                System.out.println("Philosopher " + id + " took the left fork " + leftFork.id);
                rightFork.take(id);
                System.out.println("Philosopher " + id + " took the right fork " + rightFork.id);
            }
            else {
                rightFork.take(id);
                System.out.println("Philosopher " + id + " took the right fork " + rightFork.id);
                leftFork.take(id);
                System.out.println("Philosopher " + id + " took the left fork " + leftFork.id);
            }
            System.out.println("Philosopher " + id + " is eating...");
            leftFork.put(id);
            System.out.println("Philosopher " + id + " has put down the left fork " + leftFork.id);
            rightFork.put(id);
            System.out.println("Philosopher " + id + " has put down the right fork " + rightFork.id);
        }
    }

}