Welcome to this lesson on concurrency programming, where we explore the Dining Philosophers problem. This lesson is part of the "Concurrency Foundations" course, and we will focus on synchronization challenges and strategies to prevent deadlocks.

In this lesson, you will:

• Understand the Dining Philosophers problem and its importance in concurrent programming.
• Learn about the dangers of deadlocks and how they occur.
• Implement a solution for the Dining Philosophers problem and see how deadlock can occur without proper synchronization.
• Discover strategies to prevent deadlocks using ordered resource acquisition.

Imagine five philosophers seated around a round table. Each philosopher alternates between thinking and eating. However, there are only five forks on the table, with one fork placed between each pair of philosophers.

The rule is that a philosopher needs two forks—the one on their left and the one on their right—to eat. After eating, they put both forks down and go back to thinking. This setup creates a challenge where philosophers must share forks.

The goal is to make sure that all philosophers can eat without falling into a deadlock, where they each hold one fork and wait indefinitely for the other.

To solve the Dining Philosophers problem, each philosopher needs to pick up the fork on their left and right in order to eat. After eating, they put both forks down and return to thinking. Let’s go step-by-step through how this solution works.

Below, each philosopher runs in its own thread and alternates between thinking and eating. When eating, they need to pick up both forks before they can eat. After eating, they release the forks so other philosophers can use them.

Java
Copy to clipboard
1public class Philosopher implements Runnable {
2    private final Object leftFork;
3    private final Object rightFork;
4    private final int id;
5
6    public Philosopher(int id, Object leftFork, Object rightFork) {
7        this.id = id;
8        this.leftFork = leftFork;
9        this.rightFork = rightFork;
10    }

Each philosopher has two forks: the leftFork and the rightFork. These forks are represented as Object instances. Forks are shared between neighboring philosophers, which creates the synchronization challenge. The id is used to give each philosopher a unique identity in the output. The constructor initializes each philosopher with their respective forks and an ID.

Java
Copy to clipboard
1    private void think() throws InterruptedException {
2        System.out.println("Philosopher " + id + " is thinking");
3        Thread.sleep((long) (Math.random() * 100));
4    }
5
6    private void eat() throws InterruptedException {
7        System.out.println("Philosopher " + id + " is eating");
8        Thread.sleep((long) (Math.random() * 100));
9    }

The think() and eat() methods simulate the philosopher thinking and eating by making the thread sleep for a random amount of time. This mimics the behavior of philosophers alternating between eating and thinking.

Java
Copy to clipboard
1    @Override
2    public void run() {
3        try {
4            while (true) {
5                think();
6
7                // Philosopher picks up left fork
8                synchronized (leftFork) {
9                    System.out.println("Philosopher " + id + " picked up the left fork");
10
11                    // Philosopher picks up right fork
12                    synchronized (rightFork) {
13                        System.out.println("Philosopher " + id + " picked up the right fork");
14                        eat();
15                        System.out.println("Philosopher " + id + " put down the right fork");
16                    }
17
18                    System.out.println("Philosopher " + id + " put down the left fork");
19                }
20            }
21        } catch (InterruptedException e) {
22            System.out.println("Philosopher " + id + " was interrupted and is stopping.");
23            Thread.currentThread().interrupt();
24        }
25    }
26}

The run() method is the core of the Philosopher class. This method contains the logic for alternating between thinking and eating. Here, we use a synchronized block to ensure that when a philosopher picks up a fork, no other philosopher can pick up the same fork until it’s put down.

The synchronized keyword ensures mutual exclusion—only one philosopher can hold a fork at any given time. The philosopher first locks the left fork, then attempts to lock the right fork. After eating, the philosopher releases both forks.

The infinite loop in the run() method makes each philosopher continuously think and eat until the thread is interrupted.

Let’s set up the program to see how this solution behaves when all philosophers are running.

Java
Copy to clipboard
1public class Main {
2    public static void main(String[] args) {
3        int numPhilosophers = 5;
4        Philosopher[] philosophers = new Philosopher[numPhilosophers];
5        Object[] forks = new Object[numPhilosophers];
6        Thread[] threads = new Thread[numPhilosophers];
7
8        // Initialize forks
9        for (int i = 0; i < numPhilosophers; i++) {
10            forks[i] = new Object();
11        }
12
13        // Initialize philosophers and start threads
14        for (int i = 0; i < numPhilosophers; i++) {
15            Object leftFork = forks[i];
16            Object rightFork = forks[(i + 1) % numPhilosophers];
17            philosophers[i] = new Philosopher(i + 1, leftFork, rightFork);
18            threads[i] = new Thread(philosophers[i], "Philosopher " + (i + 1));
19            threads[i].start();
20        }
21    }
22}

In this setup, we create five philosophers and five forks. Each philosopher is assigned a left fork and a right fork. The philosophers are created as separate threads and start executing concurrently.

In this scenario, each philosopher starts by picking up their left fork and then reaches for their right fork. The problem arises when all philosophers pick up their left fork simultaneously. They end up waiting for the right fork, which is being held by their neighbor, leading to a deadlock. As a result, none of the philosophers can eat because each is holding one fork and waiting endlessly for the other.

As we can see, the Deadlock occurs because all philosophers are competing for the same resources (forks) in an uncoordinated way. To prevent deadlock, we need to enforce an ordering on how resources are acquired. The key to preventing deadlock is to make sure that philosophers don’t all try to pick up their left fork first.

One way to achieve this is to order the forks based on their identity hash code. Each philosopher will pick up the lower-numbered fork first, ensuring that there is no circular wait condition.

Here’s how we can modify the run() method to prevent deadlock:

Java
Copy to clipboard
1@Override
2public void run() {
3    try {
4        while (true) {
5            think();
6
7            // Order forks to prevent deadlock
8            Object firstFork = leftFork;
9            Object secondFork = rightFork;
10            if (System.identityHashCode(leftFork) > System.identityHashCode(rightFork)) {
11                firstFork = rightFork;
12                secondFork = leftFork;
13            }
14
15            synchronized (firstFork) {
16                System.out.println("Philosopher " + id + " picked up the first fork");
17
18                synchronized (secondFork) {
19                    System.out.println("Philosopher " + id + " picked up the second fork");
20                    eat();
21                    System.out.println("Philosopher " + id + " put down the second fork");
22                }
23
24                System.out.println("Philosopher " + id + " put down the first fork");
25            }
26        }
27    } catch (InterruptedException e) {
28        System.out.println("Philosopher " + id + " was interrupted and is stopping.");
29        Thread.currentThread().interrupt();
30    }
31}

Here’s what happens:

• We introduce a strategy where each philosopher first decides which fork to pick up by comparing the identity hash codes of the forks.
• If the left fork has a higher hash code than the right fork, the philosopher will pick up the right fork first instead. This ensures that forks are always picked up in the same order, preventing deadlock.

This simple ordering guarantees that philosophers can never create a circular wait, which is the condition that leads to deadlock. By picking up forks in a consistent order, we ensure that all philosophers will eventually be able to eat without getting stuck.

Understanding and solving the Dining Philosophers problem is crucial for anyone diving into concurrent programming. It illustrates the synchronization challenges you’ll face in real-world systems, where resources are shared among multiple threads or processes.

By learning how to prevent deadlocks using ordered resource acquisition, you gain a valuable skill for building multithreaded applications. These strategies apply not only to this classic problem but also to systems like databases, operating systems, and application servers, where multiple threads need to coordinate their use of shared resources.

Now let's move to the practice section to apply these concepts in action!