🍽️ Dining Philosophers Problem

🧠 Problem Statement

The Dining Philosophers problem is a classic example in concurrency and synchronization. It demonstrates how improper resource management can lead to deadlock and starvation in a multithreaded environment.

🪑 Scenario

• Five philosophers sit at a round table.
• Each philosopher alternates between:
  • 🧘 Thinking
  • 🍝 Eating (requires 2 forks: one on the left and one on the right)
• There are exactly 5 forks — one between each pair of philosophers.

❗ Constraints

1. A philosopher needs both the left and right fork to eat.
2. Only one philosopher can use a fork at any time.
3. Must avoid:
   • ❌ Deadlock (where everyone grabs one fork and waits forever)
   • ❌ Starvation (where someone never gets to eat)

📥 Input / Output

Input:

• 5 philosophers (threads)
• 5 forks (shared resources)
• Infinite loop of thinking and eating

Output:

• Console logs showing philosophers thinking and eating
• No deadlock or starvation should occur

💡 Intuition About Solving This Problem

The key insight is that if all 5 philosophers try to eat simultaneously, they can create a deadlock by each holding one fork and waiting for another. The solution is to limit the number of philosophers who can attempt to eat at the same time, ensuring that at least one fork remains available.

🚀 Steps to Take to Solve

1. Identify the shared resources: 5 forks
2. Recognize the deadlock condition: All philosophers holding one fork each
3. Use a semaphore to limit concurrent access: Allow only 4 philosophers to attempt eating
4. Implement proper resource acquisition order: Acquire both forks before eating
5. Ensure proper resource release: Release both forks after eating
6. Handle the semaphore: Acquire before eating, release after eating

⚠️ Edge Cases to Consider

1. Deadlock: All philosophers grab left fork simultaneously
2. Starvation: Some philosophers might never get both forks
3. Resource exhaustion: All forks being held by different philosophers
4. Thread interruption: Handling InterruptedException properly
5. Uneven distribution: Some philosophers eating more than others

💻 Code (with comments)

import java.util.concurrent.Semaphore;
import java.util.Random;

public class DiningPhilosophers {

    private static final Random random = new Random();
    private final Semaphore[] forks = new Semaphore[5];
    private final Semaphore maxDiners = new Semaphore(4); // Allow only 4 at a time

    public DiningPhilosophers() {
        for (int i = 0; i < 5; i++) {
            forks[i] = new Semaphore(1);
        }
    }

    public void lifecycleOfPhilosopher(int id) throws InterruptedException {
        while (true) {
            think(id);
            eat(id);
        }
    }

    private void think(int id) throws InterruptedException {
        System.out.println("🧘 Philosopher " + id + " is thinking.");
        Thread.sleep(random.nextInt(500));
    }

    private void eat(int id) throws InterruptedException {
        maxDiners.acquire(); // Prevent deadlock by limiting concurrent access

        forks[id].acquire(); // Left fork
        forks[(id + 1) % 5].acquire(); // Right fork

        System.out.println("🍝 Philosopher " + id + " is eating.");
        Thread.sleep(random.nextInt(500));

        forks[id].release();
        forks[(id + 1) % 5].release();

        maxDiners.release(); // Allow others to try eating
    }

    public static void main(String[] args) {
        DiningPhilosophers dp = new DiningPhilosophers();

        for (int i = 0; i < 5; i++) {
            final int philosopherId = i;
            new Thread(() -> {
                try {
                    dp.lifecycleOfPhilosopher(philosopherId);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }, "Philosopher-" + i).start();
        }
    }
}

🔍 Dry Run Example

Initial State:

• All forks are available (semaphore count = 1)
• maxDiners semaphore count = 4
• All philosophers are thinking

Step 1: Philosopher 0 wants to eat

• maxDiners.acquire() → count becomes 3
• Acquires fork 0 (left)
• Acquires fork 1 (right)
• Starts eating

Step 2: Philosopher 1 wants to eat

• maxDiners.acquire() → count becomes 2
• Tries to acquire fork 1 → blocked (Philosopher 0 has it)
• Waits for fork 1

Step 3: Philosopher 0 finishes eating

• Releases fork 0 and fork 1
• maxDiners.release() → count becomes 3
• Philosopher 1 can now acquire both forks

Result: Deadlock avoided because only 4 philosophers can attempt eating simultaneously.

⏱️ Time Complexity / Space Complexity

Time Complexity:

• Thinking phase: O(1) per philosopher
• Eating phase: O(1) per philosopher
• Overall: O(n) where n is the number of philosophers

Space Complexity:

• Forks array: O(n) where n is the number of philosophers
• Semaphores: O(n) for forks + O(1) for maxDiners
• Total: O(n)

---

🔑 Key Challenges

Challenge	Description
🔁 Deadlock	All philosophers grab left fork and wait for right — no one eats
🕒 Starvation	Some philosophers might never get forks
🧵 Concurrency	Multiple threads share limited forks

---

✅ Solution: Limit Entry Using Semaphore

💡 Idea

Use a Semaphore (maxDiners) to allow only 4 philosophers to try eating at a time.

• Ensures at least one fork is free → avoids deadlock.
• Simple and elegant solution using basic concurrency tools.

---

🔍 Why Does This Work?

• 🍽️ At most 4 philosophers can try to eat → one fork always free.
• 🔄 Forks are released after eating → others can eat too.
• 🔓 Fair and deadlock-free solution using simple semaphores.

---

👩‍🔬 Real-World Analogy

Think of 5 people trying to pick up 2 shared chopsticks to eat. If everyone grabs one chopstick and waits, no one eats.

By letting only 4 people try to eat, we ensure:

• At least one full set of chopsticks is always available
• No one gets stuck waiting forever

---

💡 Pro Tips for Interviews

• Use Semaphore or Lock for concurrency.
• Avoid symmetric resource grabbing (e.g. always grabbing left first).
• Discuss fairness and starvation explicitly.
• Mention alternative strategies: odd philosophers pick left then right, evens do the opposite.

---

✅ Summary

✅ Feature	Covered
Deadlock-free	✅ Yes
Starvation-free	⚠️ Partially
Simple and scalable	✅ Yes
Realistic	✅ Yes