The Dining Philosophers Problem

1. What Is the Dining Philosophers Problem?

The Dining Philosophers problem, introduced by Edsger Dijkstra, is a classic synchronization problem used to illustrate common issues in concurrent programming, especially:

• Deadlock

• Starvation

• Resource contention

Although it has little direct practical use, it is extremely important conceptually and is often used in operating systems courses and interviews.

---

2. Problem Setup

• There are 5 philosophers sitting around a circular table

• Between each pair of philosophers is one fork

• Each philosopher alternates between:

  • Thinking (does not need forks)

  • Eating (needs two forks)

Important Rules

• To eat, a philosopher must hold:

  • The fork on their left

  • The fork on their right

• Forks are shared resources

• Only one philosopher can use a fork at a time

---

3. Philosopher Behavior

Each philosopher runs the following loop:

while (1) {
    think();
    get_forks(p);
    eat();
    put_forks(p);
}

Where p is the philosopher’s ID (0 to 4).

---

4. Helper Functions

int left(int p)  { return p; }
int right(int p) { return (p + 1) % 5; }

• left(p) gives the fork to the left of philosopher p

• right(p) gives the fork to the right

• Modulo handles the circular table

---

5. The Goal

Design get_forks() and put_forks() such that:

• ❌ No deadlock

• ❌ No starvation

• ✅ Maximum possible concurrency

---

6. A Broken (Naive) Solution

Code

void get_forks(int p) {
    sem_wait(&forks[left(p)]);
    sem_wait(&forks[right(p)]);
}

void put_forks(int p) {
    sem_post(&forks[left(p)]);
    sem_post(&forks[right(p)]);
}

• Each fork is protected by a semaphore initialized to 1

• Philosophers pick up left fork first, then right fork

---

7. Why This Solution Is Broken (Deadlock)

Deadlock Scenario

1. All philosophers pick up their left fork

2. Each philosopher now waits for their right fork

3. Every right fork is already held by a neighbor

Result

Philosopher	Holds	Waiting For
P0	fork 0	fork 1
P1	fork 1	fork 2
P2	fork 2	fork 3
P3	fork 3	fork 4
P4	fork 4	fork 0

➡️ Circular wait → Deadlock

No philosopher can proceed. Everyone waits forever.

---

8. The Root Cause

The system satisfies all deadlock conditions:

• Mutual exclusion

• Hold and wait

• No preemption

• Circular wait

---

9. A Simple Solution: Breaking the Dependency

To break deadlock, we break the circular wait condition.

Key Idea

Make one philosopher pick up forks in the opposite order

---

10. Corrected Solution (Figure 31.16)

void get_forks(int p) {
    if (p == 4) {
        sem_wait(&forks[right(p)]);
        sem_wait(&forks[left(p)]);
    } else {
        sem_wait(&forks[left(p)]);
        sem_wait(&forks[right(p)]);
    }
}

• Philosopher 4 picks up right fork first

• All others pick up left fork first

---

11. Why This Works

• Circular wait is broken

• At least one philosopher can always proceed

• Deadlock is impossible

Intuition

There is no longer a cycle where everyone holds one fork and waits for another.

---

12. Limitations of This Solution

• Does not guarantee fairness

• Some philosophers may still starve

• Better solutions exist (e.g., monitors, arbitrators)

---

13. Why This Problem Matters

This problem helps you understand:

• Deadlock

• Resource ordering

• Lock acquisition strategies

• Why simple-looking solutions fail

---

14. Key Takeaways ⭐

• Dining Philosophers is a deadlock demonstration problem

• Naive locking leads to circular wait

• Deadlock can be avoided by breaking resource ordering

• Simple changes in lock acquisition order can prevent deadlock