Dining Philosopher Problem

Definition

The Dining Philosopher Problem is a classic synchronization problem illustrating challenges of deadlock and resource sharing. It demonstrates how simple synchronization solutions can lead to deadlock if not carefully designed.

Problem Setup

The Scenario

        Philosopher 0
                |
       Fork 0   |   Fork 1
         \      |      /
          \     |     /
    Phil 4──┤      ├──Phil 1
           /│      │\
          / │      │ \
       Fork 4 │    │ Fork 1
              │    │
       Philosopher 3───Fork 3───Philosopher 2

Five philosophers sit around a table with:

• Five plates (one in front of each)
• Five forks (one between each pair of philosophers)

Philosopher Lifecycle

Each philosopher repeatedly:

1. Think (random amount of time)
2. Get hungry
3. Eat (requires both adjacent forks)
4. Put down forks
5. Back to thinking

The Problem

Requirement

MUST HAVE:
- Right fork
- Left fork
- Forks must be picked up one at a time
- Philosopher eats only when holding both

Goal: Ensure all philosophers can eat without deadlock/starvation

Naive Solution (DEADLOCK!)

Philosopher i:
while (true) {
    think();

    // Try to eat
    wait(fork[i]);              // Pick up left fork
    wait(fork[(i+1)%5]);        // Pick up right fork
    eat();
    signal(fork[i]);
    signal(fork[(i+1)%5]);
}

What Goes Wrong?

Time 0: All philosophers think
Time 1: All philosophers get hungry
Time 2: All pick up left fork simultaneously
        - Philosopher 0: takes fork[0]
        - Philosopher 1: takes fork[1]
        - Philosopher 2: takes fork[2]
        - Philosopher 3: takes fork[3]
        - Philosopher 4: takes fork[4]

Time 3: All try to pick up right fork
        - Philosopher 0: wait(fork[1]) → BLOCKED (Philosopher 1 has it)
        - Philosopher 1: wait(fork[2]) → BLOCKED (Philosopher 2 has it)
        - Philosopher 2: wait(fork[3]) → BLOCKED (Philosopher 3 has it)
        - Philosopher 3: wait(fork[4]) → BLOCKED (Philosopher 4 has it)
        - Philosopher 4: wait(fork[0]) → BLOCKED (Philosopher 0 has it)

Result: DEADLOCK! (Circular wait - everyone waiting for someone)

Solutions

Solution 1: Asymmetric Approach

Make one philosopher (say #0) pick up right fork first, others pick up left first:

Philosopher 0:                      Philosophers 1-4:
wait(fork[1]);  // right first       wait(fork[i]);  // left first
wait(fork[0]);  // left second       wait(fork[(i+1)%5]);  // right
eat();                              eat();
signal(fork[1]);                    signal(fork[i]);
signal(fork[0]);                    signal(fork[(i+1)%5]);

Result: Breaks circular wait! ✓

Why it Works:

• No circular wait (definition of deadlock)
• If Philosopher 0 has fork[1], can’t create cycle
• Others always pick left first

Pros: Simple, prevents deadlock Cons: Asymmetric (unfair seeming)

Solution 2: Resource Hierarchy

Number all resources (forks) and require processes acquire them in order:

Philosopher i:
int left = i;
int right = (i + 1) % 5;

// Always acquire in order (lower number first)
int first = min(left, right);
int second = max(left, right);

wait(fork[first]);   // Get lower numbered fork first
wait(fork[second]);  // Then higher numbered
eat();
signal(fork[first]);
signal(fork[second]);

Result: ✓ No circular wait

Why it Works:

• All acquire resources in same order
• Can’t have circular wait if everyone uses same order

Pros: Works for any N philosophers Cons: Requires careful numbering

Solution 3: Monitor (Highest Level)

Philosopher requests both forks atomically:

class DiningPhilosopher {
    enum State {THINKING, HUNGRY, EATING};
    State state[5];
    Condition condition[5];  // One per philosopher

    synchronized void take_forks(int i) {
        state[i] = HUNGRY;
        // Try to eat - both neighbors can't be eating
        if (state[i-1] != EATING && state[i+1] != EATING) {
            state[i] = EATING;
        } else {
            condition[i].wait();  // Wait if can't eat
        }
    }

    synchronized void put_forks(int i) {
        state[i] = THINKING;

        // Check neighbors - can they eat now?
        if (state[i-1] == HUNGRY &&
            state[(i-1)-1] != EATING &&
            state[(i-1)+1] != EATING) {
            state[i-1] = EATING;
            condition[i-1].signal();  // Wake neighbor
        }

        if (state[i+1] == HUNGRY &&
            state[(i+1)-1] != EATING &&
            state[(i+1)+1] != EATING) {
            state[i+1] = EATING;
            condition[i+1].signal();  // Wake neighbor
        }
    }
}

Philosopher i:
while (true) {
    think();
    diningPhilosopher.take_forks(i);
    eat();
    diningPhilosopher.put_forks(i);
}

Why it Works:

• Monitor provides mutual exclusion
• No two adjacent philosophers eating
• No deadlock (monitor controls resource allocation)

Pros:

• Deadlock-free
• Fair
• High-level abstraction

Cons:

• Requires careful state management
• Can be complex to implement

Solution 4: Limited Philosophers

Allow at most 4 philosophers to be hungry at once:

Semaphore capacity = 4;  // At most 4 trying to eat

Philosopher i:
while (true) {
    think();

    wait(capacity);           // Only 4 can enter
    wait(fork[i]);
    wait(fork[(i+1)%5]);
    eat();
    signal(fork[i]);
    signal(fork[(i+1)%5]);
    signal(capacity);
}

Why it Works:

• At most 4 philosophers compete for 5 forks
• With 4 philosophers, at least one can get both forks
• That one eats, releases forks, others proceed

Pros: Simple solution Cons: Reduces concurrency (not all philosophers eating when possible)

Comparison of Solutions

Why This Problem Matters

Teaches About Deadlock

The naive solution naturally leads to deadlock:

Four Conditions for Deadlock:

1. ✓ Mutual Exclusion (fork used by one)
2. ✓ Hold and Wait (philosopher holds fork, waits for another)
3. ✓ No Preemption (can’t force fork away)
4. ✓ Circular Wait (0→1→2→3→4→0)

Dining Philosopher creates all four! Good example to study deadlock.

Real-World Application

Many systems have this structure:

Banking System:
Account A → Lock A
Account B → Lock B

Transfer from A to B:
lock(A)
lock(B)
transfer()
unlock(B)
unlock(A)

If all processes deadlock same way, system hangs!

Design Principles

Shows importance of:

1. Careful resource ordering (don’t request in circle)
2. Deadlock prevention (essential design principle)
3. High-level abstractions (monitors easier than low-level locks)

Python Implementation (Monitor Solution)

import threading

class DiningPhilosopher:
    def __init__(self):
        self.state = [0] * 5  # 0=thinking, 1=hungry, 2=eating
        self.condition = [threading.Condition() for _ in range(5)]

    def take_forks(self, i):
        self.state[i] = 1  # hungry
        if (self.state[(i-1)%5] != 2 and
            self.state[(i+1)%5] != 2):
            self.state[i] = 2  # eating
        else:
            self.condition[i].wait()

    def put_forks(self, i):
        self.state[i] = 0  # thinking
        # Wake neighbors if they can eat
        for j in [(i-1)%5, (i+1)%5]:
            if (self.state[j] == 1 and
                self.state[(j-1)%5] != 2 and
                self.state[(j+1)%5] != 2):
                self.state[j] = 2
                self.condition[j].notify()

# Usage
dp = DiningPhilosopher()

def philosopher(i):
    while True:
        # think
        dp.take_forks(i)
        # eat
        dp.put_forks(i)

threads = [threading.Thread(target=philosopher, args=(i,))
           for i in range(5)]

Summary

Dining Philosopher Problem beautifully illustrates deadlock challenges in resource sharing. Naive solution deadlocks immediately. Solutions include asymmetric approach (simple but inelegant), resource hierarchy (simple and scalable), monitors (clean but complex), or limiting philosophers (reduces concurrency). Problem teaches critical lessons: deadlock requires four conditions, prevention requires careful design, and high-level abstractions simplify synchronization. Real systems use similar principles to avoid deadlock in database transactions, lock acquisition, and resource allocation.