Simulating and Solving Deadlocks in the Dining Philosophers Problem

Introduction to the Dining Philosophers Problem

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.

What You'll Learn

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.

The Dining Philosophers Problem

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.

First Solution for the Problem

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.

Philosopher Class Definition

Java public class Philosopher implements Runnable {private final Object leftFork; private final Object rightFork; private final int id; public Philosopher(int id, Object leftFork, Object rightFork) {this.id = id; this.leftFork = leftFork; this.rightFork = rightFork;} 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.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Java

    private void think() throws InterruptedException {
        System.out.println("Philosopher " + id + " is thinking");
        Thread.sleep((long) (Math.random() * 100));
    }

    private void eat() throws InterruptedException {
        System.out.println("Philosopher " + id + " is eating");
        Thread.sleep((long) (Math.random() * 100));
    }

Java

    @Override
    public void run() {
        try {
            while (true) {
                think();

                // Philosopher picks up left fork
                synchronized (leftFork) {
                    System.out.println("Philosopher " + id + " picked up the left fork");

                    // Philosopher picks up right fork
                    synchronized (rightFork) {
                        System.out.println("Philosopher " + id + " picked up the right fork");
                        eat();
                        System.out.println("Philosopher " + id + " put down the right fork");
                    }

                    System.out.println("Philosopher " + id + " put down the left fork");
                }
            }
        } catch (InterruptedException e) {
            System.out.println("Philosopher " + id + " was interrupted and is stopping.");
            Thread.currentThread().interrupt();
        }
    }
}

Java

public class Main {
    public static void main(String[] args) {
        int numPhilosophers = 5;
        Philosopher[] philosophers = new Philosopher[numPhilosophers];
        Object[] forks = new Object[numPhilosophers];
        Thread[] threads = new Thread[numPhilosophers];

        // Initialize forks
        for (int i = 0; i < numPhilosophers; i++) {
            forks[i] = new Object();
        }

        // Initialize philosophers and start threads
        for (int i = 0; i < numPhilosophers; i++) {
            Object leftFork = forks[i];
            Object rightFork = forks[(i + 1) % numPhilosophers];
            philosophers[i] = new Philosopher(i + 1, leftFork, rightFork);
            threads[i] = new Thread(philosophers[i], "Philosopher " + (i + 1));
            threads[i].start();
        }
    }
}

Java

@Override
public void run() {
    try {
        while (true) {
            think();

            // Order forks to prevent deadlock
            Object firstFork = leftFork;
            Object secondFork = rightFork;
            if (System.identityHashCode(leftFork) > System.identityHashCode(rightFork)) {
                firstFork = rightFork;
                secondFork = leftFork;
            }

            synchronized (firstFork) {
                System.out.println("Philosopher " + id + " picked up the first fork");

                synchronized (secondFork) {
                    System.out.println("Philosopher " + id + " picked up the second fork");
                    eat();
                    System.out.println("Philosopher " + id + " put down the second fork");
                }

                System.out.println("Philosopher " + id + " put down the first fork");
            }
        }
    } catch (InterruptedException e) {
        System.out.println("Philosopher " + id + " was interrupted and is stopping.");
        Thread.currentThread().interrupt();
    }
}

Introduction to the Dining Philosophers Problem

What You'll Learn

The Dining Philosophers Problem

First Solution for the Problem

Philosopher Class Definition

Join the 1M+ learners on CodeSignal

Philosopher Behavior: Thinking and Eating

Philosopher Thread Execution

Main Program Setup

Preventing Deadlock

Modified Philosopher Thread Execution: Deadlock Prevention

Why This Matters