Dining Philosophers Problem: 5 Classic Deadlock Solutions

Problem Description

Five philosophers sit around a circular table. Each philosopher alternates between thinking and eating. To eat, a philosopher must pick up both the left and right chopsticks (forks). A chopstick can be used by only one philosopher at a time. After eating, the philosopher puts down both chopsticks and resumes thinking.

Five philosophers around a round table:
    Chopstick 1
    /          \
Philosopher 5  Philosopher 1
  |              |
Chopstick 4      Chopstick 2
    \          /
      Philosopher 4
        |
    Chopstick 3
      Philosopher 3

Rules:
1. Philosopher either thinks or eats
2. Eating requires both left and right chopsticks
3. One chopstick can be used by only one philosopher at a time
4. After eating, put down chopsticks and continue thinking

Why This Is a Problem

Starvation Scenario

If every philosopher simultaneously picks up the left chopstick and then waits for the right one, each holds one chopstick while the right chopstick is held by the neighbor. All five are stuck waiting forever — deadlock.

If each philosopher simultaneously:
1. Picks up left chopstick
2. Waits for right chopstick
3. But right chopstick is held by neighbor
4. Neighbor is also waiting for the other chopstick

Result: All five hold one chopstick, waiting for the other
    Deadlock! Nobody can eat!

Code Simulation

The naive implementation uses a semaphore per chopstick. Each philosopher executes:

#define N 5
Semaphore forks[N];  // one semaphore per chopstick

void philosopher(int i) {
    while (TRUE) {
        think();
        P(&forks[i]);           // pick up left chopstick
        P(&forks[(i+1)%N]);     // pick up right chopstick
        eat();
        V(&forks[i]);           // put down left chopstick
        V(&forks[(i+1)%N]);     // put down right chopstick
    }
}

This code deadlocks because every philosopher acquires the left chopstick then blocks on the right, which is already held by the next philosopher.

Solution 1: Waiter (Server) Solution

Idea

Limit the number of philosophers who may simultaneously attempt to pick up chopsticks. Introduce a waiter semaphore initialized to N‑1 (4 for 5 philosophers). At most four philosophers can be in the critical section, guaranteeing at least one can acquire both chopsticks.

Code

#define N 5
Semaphore forks[N];
Semaphore server = 4;  // at most 4 philosophers

void philosopher(int i) {
    while (TRUE) {
        think();
        P(&server);                 // ask waiter: may I pick up chopsticks?
        P(&forks[i]);
        P(&forks[(i+1)%N]);
        eat();
        V(&forks[i]);
        V(&forks[(i+1)%N]);
        V(&server);                 // tell waiter I am done
    }
}

Analysis

Pros: Simple and effective. Cons: Reduces concurrency (at most N‑1 philosophers can eat simultaneously).

Solution 2: Odd‑Even Strategy

Idea

Break symmetry by having odd‑numbered philosophers pick up left then right, while even‑numbered philosophers pick up right then left. Adjacent philosophers then contend for different chopsticks first, preventing circular wait.

Code

void philosopher(int i) {
    while (TRUE) {
        think();
        if (i % 2 == 0) {          // even: right then left
            P(&forks[(i+1)%N]);
            P(&forks[i]);
        } else {                   // odd: left then right
            P(&forks[i]);
            P(&forks[(i+1)%N]);
        }
        eat();
        V(&forks[i]);
        V(&forks[(i+1)%N]);
    }
}

Analysis

Pros: Completely eliminates deadlock. Cons: Breaks symmetry, may be less fair.

Solution 3: Atomic Acquisition (Pick Up Both at Once)

Idea

Require that a philosopher acquires both chopsticks atomically — either both are obtained or none. Implemented with an AND‑semaphore operation that waits on two semaphores simultaneously.

Code

// AND‑semaphore operations
void P_all(Semaphore *S1, Semaphore *S2) {
    // atomically wait on both semaphores
    wait(S1);
    wait(S2);
}

void V_all(Semaphore *S1, Semaphore *S2) {
    signal(S2);
    signal(S1);
}

void philosopher(int i) {
    while (TRUE) {
        think();
        P_all(&forks[i], &forks[(i+1)%N]);
        eat();
        V_all(&forks[i], &forks[(i+1)%N]);
    }
}

Analysis

Pros: Conceptually clean. Cons: Requires AND‑type atomic operation, not universally available.

Solution 4: Hierarchical (Resource Ordering) Strategy

Idea

Assign a global order to chopsticks (1…5). Each philosopher always picks up the lower‑numbered chopstick first. This imposes a total ordering on resource acquisition, breaking the circular‑wait condition.

Code

Semaphore forks[N];
int left = i;            // lower‑numbered chopstick
int right = (i+1)%N;     // higher‑numbered chopstick

void philosopher(int i) {
    while (TRUE) {
        think();
        // always acquire lower‑numbered chopstick first
        if (left < right) {
            P(&forks[left]);
            P(&forks[right]);
        } else {
            P(&forks[right]);
            P(&forks[left]);
        }
        eat();
        V(&forks[left]);
        V(&forks[right]);
    }
}

Analysis

Pros: Breaks circular wait. Cons: Requires global coordination to assign numbers.

Solution 5: Monitor Solution

Idea

Encapsulate the state and synchronization in a monitor. The monitor guarantees mutual exclusion automatically. Each philosopher calls pickup(i) and putdown(i); the monitor tracks states (THINKING, HUNGRY, EATING) and signals waiting philosophers when neighbors are not eating.

Code

monitor DiningPhilosophers {
    enum {THINKING, HUNGRY, EATING} state[5];
    condition self[5];

    procedure pickup(int i) {
        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING) {
            self[i].wait();
        }
    }

    procedure putdown(int i) {
        state[i] = THINKING;
        test((i + 4) % 5);  // check left neighbor
        test((i + 1) % 5);  // check right neighbor
    }

    procedure test(int i) {
        if ((state[(i + 4) % 5] != EATING) &&
            (state[i] == HUNGRY) &&
            (state[(i + 1) % 5] != EATING)) {
            state[i] = EATING;
            self[i].signal();
        }
    }
}

void philosopher(int i) {
    while (TRUE) {
        think();
        DiningPhilosophers.pickup(i);
        eat();
        DiningPhilosophers.putdown(i);
    }
}

Analysis

Pros: Safer, easier to understand; compiler enforces mutual exclusion. Cons: Monitors not supported in all languages.

Problem Variations

1. Starvation‑Free Version

Add fairness: a philosopher cannot starve indefinitely; after prolonged hunger they must eventually obtain chopsticks.

2. Limited Resources

Chopsticks may break or be fewer than philosophers.

3. Multiple Resource Types

Generalize to arbitrary resource combinations; generic solution is resource ordering.

Real‑World Analogues

Database Connection Pool

Database connections = chopsticks; processes requesting connections = philosophers. Pool size = N. Deadlock occurs when N processes each hold one connection and wait for another.

Thread Pool Deadlock

Thread A holds lock 1 and waits for lock 2; Thread B holds lock 2 and waits for lock 1 → deadlock. Fix: acquire locks in a fixed global order.

Summary: Lessons from the Dining Philosophers

The Dining Philosophers problem is the classic model for deadlock. The four necessary conditions for deadlock are:

Mutual Exclusion: a chopstick can be used by only one philosopher.

Hold and Wait: a philosopher holds one chopstick while waiting for another.

No Preemption: a chopstick cannot be forcibly taken.

Circular Wait: A waits for B, B waits for C, …, A waits for A.

Each solution breaks one of these conditions:

Waiter: breaks Hold and Wait.

Odd‑Even: breaks Circular Wait.

Atomic Acquisition: breaks atomicity of acquisition.

Hierarchical: breaks Circular Wait via ordering.

Monitor: encapsulates synchronization to avoid errors.

Remember: The Dining Philosophers problem is the best case for understanding deadlock. Master it, and you master the core of deadlock!

Key Takeaways:

The Dining Philosophers problem demonstrates the four necessary conditions for deadlock.

Solution 1 (Waiter): limit the number of processes simultaneously waiting for resources.

Solution 2 (Odd‑Even): break the symmetry of acquisition order.

Solution 3 (Atomic Acquisition): acquire all required resources atomically.

Solution 4 (Hierarchical): enforce a fixed global order for resource acquisition.