Dining Philosophers Problem

The setting

Five philosophers sit around a round table. Between each pair lies one fork, so there are five forks in total. A philosopher alternates between thinking and eating, and to eat needs both the fork on the left and the fork on the right. Two neighbours can never use the same fork at the same time (mutual exclusion).

It looks harmless, but it models real problems: several processes each needing two locks.

The naive solution deadlocks

think()
pick_up(fork[i])
pick_up(fork[i−1])
eat()
put_down both

If all five philosophers pick up their first fork at the same moment, each holds one fork and waits for the neighbour’s fork. Nobody can proceed. This is a deadlock.

Four conditions for deadlock

A deadlock needs all four at once:

1. Mutual exclusion: a fork has one owner.
2. Hold and wait: a philosopher keeps one fork while waiting for the other.
3. No preemption: forks cannot be taken away.
4. Circular wait: P0 waits for P1, P1 for P2, …, P4 for P0.

Remove one of them and deadlock is impossible. Compare with the Banker’s algorithm (avoidance) and the wait-for graph (detection).

Fix 1: resource ordering

Number the forks and always pick up the lower-numbered fork first. Philosopher 4 (forks 4 and 3) now takes fork 3 first, while philosopher 0 (forks 0 and 4) takes fork 0 first. A cycle of waiting can no longer form, so circular wait is broken.

Fix 2: a waiter

A waiter lets at most n − 1 = 4 philosophers sit down. With 4 people and 5 forks, at least one philosopher always finds both forks free, finishes, and releases them. This is the same idea as a counting semaphore in process synchronization.

Code

import threading

forks = [threading.Lock() for _ in range(5)]
seats = threading.Semaphore(4)          # the waiter

def philosopher(i):
    left, right = i, (i - 1) % 5
    first, second = sorted((left, right))   # resource ordering
    with seats:                              # at most 4 at the table
        with forks[first]:
            with forks[second]:
                print(f"P{i} eats")

Common mistakes

• Thinking that more forks is the only fix. Changing the order or limiting entry is enough.
• Releasing the first fork when the second is busy without a back-off. This avoids deadlock but can cause livelock.
• Confusing deadlock (nobody moves) with starvation (somebody never gets a turn).