# Solving the Dining Philosophers Problem in Java

## **Understanding the Dining Philosophers Problem**
The Dining Philosophers problem involves a scenario where five philosophers sit around a dining table, and each philosopher alternates between thinking and eating. To eat, a philosopher must acquire both the left and right chopsticks. However, the challenge arises when multiple philosophers attempt to acquire the same chopsticks simultaneously, leading to potential issues like deadlock, livelock, and starvation.

An initial solution to this problem would be to use this method:

// ./DiningPhilosophers.java
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class DiningPhilosophers {
    public static final int NUM_PHILOSOPHERS = 5;
    private final Lock[] chopsticks = new Lock[NUM_PHILOSOPHERS];
    
    private enum Action {
        THINKING("Thinking"),
        PICKED_LEFT_CHOPSTICK("Picked up left chopstick"),
        PICKED_RIGHT_CHOPSTICK("Picked up right chopstick"),
        EATING("Eating"),
        PUT_DOWN_LEFT_CHOPSTICK("Put down left chopstick"),
        PUT_DOWN_RIGHT_CHOPSTICK("Put down right chopstick");

        private final String actionString;

        Action(String actionString) {
            this.actionString = actionString;
        }

        @Override
        public String toString() {
            return actionString;
        }
    }

    public DiningPhilosophers() {
        for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
            chopsticks[i] = new ReentrantLock();
        }
    }

    public void dine(int philosopherId) throws InterruptedException {
        Lock leftChopstick = chopsticks[philosopherId];
        Lock rightChopstick = chopsticks[(philosopherId + 1) % NUM_PHILOSOPHERS];

        while (true) {
            // Attempt to pick up chopsticks
            leftChopstick.lock();
            rightChopstick.lock();
            log(philosopherId, Action.PICKED_LEFT_CHOPSTICK);
            log(philosopherId, Action.PICKED_RIGHT_CHOPSTICK);

            // Both chopsticks acquired, eat
            eat(philosopherId);

            // Release chopsticks
            leftChopstick.unlock();
            rightChopstick.unlock();
            log(philosopherId, Action.PUT_DOWN_LEFT_CHOPSTICK);
            log(philosopherId, Action.PUT_DOWN_RIGHT_CHOPSTICK);

            // Think before retrying
            think(philosopherId);
        }
    }
    
    private void log(int philosopherId, Action action) {
        System.out.println("Philosopher " + philosopherId + ": " + action);
    }

    private void eat(int philosopherId) throws InterruptedException {
        log(philosopherId, Action.EATING);
    }

    private void think(int philosopherId) throws InterruptedException {
        log(philosopherId, Action.THINKING);
    }
}

In this initial version, philosophers lock both the left and right chopsticks simultaneously before eating. While this approach works in a basic scenario, it doesn't address the potential for deadlock, starvation, or livelock.

## **Mitigating Deadlock (Resource Ordering)**
Deadlock is a situation where each philosopher holds one chopstick and waits indefinitely for the other, creating a circular dependency. To mitigate deadlock, we must ensure that the philosophers either acquire both chopsticks simultaneously or release them if unable to do so. We can use a simple strategy: philosophers will pick up the chopsticks in a way that prevents circular waiting. For example, if a philosopher cannot acquire both chopsticks, they will release the chopstick they already hold, allowing others to use it. This ensures that all philosophers can make progress and do not get stuck in a deadlock situation:

// ... (Previous code)
public class DiningPhilosophers {
     // ... (Previous code)
    
    public void dine(int philosopherId) throws InterruptedException {
        Lock leftChopstick = chopsticks[philosopherId];
        Lock rightChopstick = chopsticks[(philosopherId + 1) % NUM_PHILOSOPHERS];

        while (true) {
            // Attempt to pick up chopsticks
            if (leftChopstick.tryLock()) {
                try {
                    log(philosopherId, Action.PICKED_LEFT_CHOPSTICK);
                    if (rightChopstick.tryLock()) {
                        try {
                            log(philosopherId, Action.PICKED_RIGHT_CHOPSTICK);
                            // Both chopsticks acquired, eat
                            eat(philosopherId);
                        } finally {
                            rightChopstick.unlock();
                            log(philosopherId, Action.PUT_DOWN_RIGHT_CHOPSTICK);
                        }
                    }
                } finally {
                    // Release the left chopstick
                    leftChopstick.unlock();
                    log(philosopherId, Action.PUT_DOWN_LEFT_CHOPSTICK);
                }
            }

            // Think before retrying
            think(philosopherid);
        }
    }
    
    // ... (Previous code)

In this snippet, we modified `dine` to attempt to acquire both left and right chopsticks and release the left chopstick if it fails to acquire both. This approach ensures that no philosopher can hold a chopstick indefinitely, breaking the possibility of a deadlock.

## **Preventing Livelock (Randomized Backoff)**

Livelock occurs when threads continuously change their state in response to the actions of other threads, leading to a situation where no progress is made. To address livelock, we can introduce some randomness in the behavior of the philosophers.

Let's enhance our Java implementation to include livelock prevention:

 // ... (Previous code)
import java.util.Random;

public class DiningPhilosophers {
    private static final Random random = new Random();
    // ... (Previous code)

    private void eat(int philosopherId) throws InterruptedException {
        log(philosopherId, Action.EATING);
        // Simulate eating time to prevent livelock
        Thread.sleep(random.nextInt(100));
    }

    private void think() throws InterruptedException {
        log(philosopherId, Action.THINKING);
        // Simulate thinking time to prevent livelock
        Thread.sleep(random.nextInt(100));
    }
}

In this section, we've introduced a random sleep period after successfully acquiring both chopsticks and after releasing the left chopstick. This random delay helps break the synchronization patterns that might lead to livelock.

## **Addressing Starvation (William Stalling's Solution)**

Starvation occurs when a thread is unable to gain access to a resource indefinitely, despite its attempts to do so. To prevent starvation in the Dining Philosophers problem, we can implement a fair distribution of resources, ensuring that each philosopher gets a chance to acquire both chopsticks. One common approach is to use a semaphore or a shared resource that limits the number of philosophers allowed to pick up chopsticks simultaneously.

Here's an extended version of your code using a semaphore:.

// ... (Previous code)
public class DiningPhilosophers {
    private static final Random random = new Random();
    private final Semaphore diningSemaphore = new Semaphore(NUM_PHILOSOPHERS - 1);
    // ... (Previous code)

    public DiningPhilosophers() {
        for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
            chopsticks[i] = new ReentrantLock();
        }
    }

    public void dine(int philosopherId) throws InterruptedException {
        Lock leftChopstick = chopsticks[philosopherId];
        Lock rightChopstick = chopsticks[(philosopherId + 1) % NUM_PHILOSOPHERS];

        while (true) {
            // Attempt to acquire dining semaphore
            diningSemaphore.acquire();

                // Attempt to pick up chopsticks
                if (leftChopstick.tryLock()) {
                    try {
                        log(philosopherId, Action.PICKED_LEFT_CHOPSTICK);
                        if (rightChopstick.tryLock()) {
                            try {
                                log(philosopherId, Action.PICKED_RIGHT_CHOPSTICK);
                                // Both chopsticks acquired, eat
                                eat(philosopherId);
                            } finally {
                                rightChopstick.unlock();
                                log(philosopherId, Action.PUT_DOWN_RIGHT_CHOPSTICK);
                            }
                        }
                    } finally {
                        // Release the left chopstick
                        leftChopstick.unlock();
                        log(philosopherId, Action.PUT_DOWN_LEFT_CHOPSTICK);
                    }

                    // Release dining semaphore
                    diningSemaphore.release();
                }

            think(philosopherId);
        }
    }

    // ... (Previous code)
}

In this extended code, a semaphore (`diningSemaphore`) is used to limit the number of philosophers allowed to pick up chopsticks simultaneously. The `acquire()` and `release()` methods are used to control access to the critical section where philosophers attempt to pick up chopsticks. This helps in preventing starvation by ensuring that all philosophers have a fair chance to acquire the necessary resources.

## **Testing the Solution**

Let's create a ``main.java`` file and add a ``Main`` class to instantiate the `DiningPhilosophers` and start the philosopher threads:

// ./Main.java
public class Main {
    public static void main(String[] args) {
        DiningPhilosophers diningPhilosophers = new DiningPhilosophers();

        for (int i = 0; i < DiningPhilosophers.NUM_PHILOSOPHERS; i++) {
            final int philosopherId = i;
            new Thread(() -> {
                try {
                    diningPhilosophers.dine(philosopherId);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }).start();
        }
    }
}

This main class creates and starts threads for each philosopher, allowing them to execute the `dine` method. Run the program and observe the output to ensure that the philosophers are dining, thinking, and releasing chopsticks appropriately.

## **Conclusion**

In this guide, we've explored the Dining Philosophers problem, its challenges, and a Java-based solution that tackles deadlock, livelock, and starvation. By leveraging locks, introducing randomness, and establishing a fair ordering of resource access, we've created a robust and efficient implementation. You can find the complete source code on GitHub [here](https://github.com/TropicolX/JavaTutorial).

## **References**
* [The Dining Philosophers Problem in Java](https://www.baeldung.com/java-dining-philoshophers)
* [The Dining Philosophers problem and different ways of solving it](https://zerobone.net/blog/cs/dining-philosophers-problem/)
* [Concurrency in Java: The Dining Philosophers Problem](https://dev.to/plainsight16/concurrency-in-java-the-dining-philosophers-problem-nko)
* [Dining Philosopher’s Problem in Java Multithreading](https://www.pranaybathini.com/2023/01/dining-philosophers-problem-in-java.html)