15 May 2026 3 min read

The Dining Philosophers Problem — Concurrency and Deadlock

The Dining Philosophers Problem is a classic thought experiment in concurrent programming. It illustrates the challenges of resource allocation, deadlock, and starvation in multi-threaded systems. This article explains the problem and its practical solutions.

Key sources: "Concurrency in Go" by Katherine Cox-Buday, E. W. Dijkstra's original paper, "Operating Systems: Design and Implementation" by Tanenbaum.

The Problem

Five philosophers sit around a circular table. Each philosopher alternates between two activities: thinking and eating.

Between each pair of philosophers is a single fork. A philosopher needs both forks (the one on the left and the one on the right) to eat.

The philosophers share the forks. They never speak to each other. They have no way to coordinate beyond picking up and putting down forks.

The challenge: design a regimen that allows every philosopher to eat without any philosopher starving.

Why This Matters

This problem directly models real concurrency scenarios:

Database transactions competing for row locks
Threads waiting for shared resources
Distributed systems acquiring distributed locks
Processes contending for memory or I/O devices

Every concurrent system faces the same fundamental issue: multiple actors need exclusive access to limited resources.

The Deadlock Scenario

A naive solution: each philosopher picks up the left fork first, then the right fork, eats for a while, then puts both down.

def philosopher(id):
    while True:
        think()
        pick_up(left_fork)    # Picks up left fork
        pick_up(right_fork)   # Picks up right fork
        eat()
        put_down(left_fork)
        put_down(right_fork)

This fails when all five philosophers pick up their left fork simultaneously. Each holds one fork and waits for the right fork, which is held by their neighbor. Nobody can proceed. The system is deadlocked.

Deadlock requires four conditions (Coffman conditions):

Mutual exclusion: Resources cannot be shared
Hold and wait: Processes hold resources while waiting for others
No preemption: Resources cannot be forcibly taken
Circular wait: A cycle of waiting processes exists

Breaking any one condition prevents deadlock.

Solution 1: Resource Hierarchy (Breaking Circular Wait)

Number the forks 1 through 5. Each philosopher picks up the lower-numbered fork first, then the higher-numbered fork.

def philosopher(id):
    left = id
    right = (id + 1) % 5

    first = min(left, right)
    second = max(left, right)

    while True:
        think()
        pick_up(first)    # Lower-numbered fork first
        pick_up(second)   # Higher-numbered fork second
        eat()
        put_down(first)
        put_down(second)

With this ordering, the last philosopher (picking up fork 5 and then fork 1) will pick up fork 5 first, then fork 1. Since one philosopher gets fork 5 before others can reach for it, the circular wait is broken.

This is the most common solution. It is simple, provably correct, and deadlock-free.

Solution 2: The Waiter (Breaking Hold and Wait)

Introduce a centralized coordinator — a waiter — who grants permission to pick up forks.

type Waiter struct {
    forks [5]sync.Mutex
}

func (w *Waiter) AcquireForks(left, right int) {
    // Atomically acquire both forks or neither
    w.forks[left].Lock()
    w.forks[right].Lock()
}

func (w *Waiter) ReleaseForks(left, right int) {
    w.forks[left].Unlock()
    w.forks[right].Unlock()
}

A philosopher asks the waiter for both forks. The waiter only grants permission if both forks are available. The philosopher cannot hold one fork while waiting for another.

This breaks the hold-and-wait condition. However, the waiter becomes a bottleneck and a potential single point of failure.

Solution 3: Limiting the Number of Philosophers (Breaking Circular Wait)

Allow at most four philosophers to sit at the table at any time. With four philosophers and five forks, at least one philosopher can always acquire both forks.

var sem = make(chan struct{}, 4) // At most 4 philosophers can compete

func philosopher(id int) {
    for {
        think()
        sem <- struct{}{} // Acquire a seat
        pickUp(forks[id])
        pickUp(forks[(id+1)%5])
        eat()
        putDown(forks[id])
        putDown(forks[(id+1)%5])
        <-sem // Release the seat
    }
}

This is simple and effective. The semaphore limits concurrency to N-1 philosophers, guaranteeing progress.

Solution 4: Asymmetric Philosophers (Breaking Circular Wait)

Designate some philosophers as left-handed (pick up left fork first) and others as right-handed (pick up right fork first).

def philosopher(id):
    if id % 2 == 0:  # Even: left-handed
        pick_up(left_fork)
        pick_up(right_fork)
    else:  # Odd: right-handed
        pick_up(right_fork)
        pick_up(left_fork)

    eat()
    put_down(left_fork)
    put_down(right_fork)

With this configuration, at least one philosopher can always acquire both forks because the asymmetry prevents the circular wait from forming.

Starvation

Deadlock is not the only problem. Even without deadlock, a philosopher might starve — repeatedly failing to acquire both forks because neighbors are always eating.

Solutions that prevent deadlock may still allow starvation. Ensuring fairness requires additional mechanisms like a queue (first-come, first-served) or a token-passing scheme.

Key Takeaways

The Dining Philosophers Problem models resource contention in concurrent systems.
Deadlock occurs when every participant waits for resources held by others.
Breaking any one of the four Coffman conditions prevents deadlock.
The resource hierarchy (ordered resource acquisition) is the simplest practical solution.
Starvation is a separate problem from deadlock — a system can be deadlock-free but still unfair.
In Go, channels and mutexes provide the tools to implement all of these solutions.

Design principle: Whenever multiple threads acquire multiple locks, enforce a consistent lock ordering to prevent deadlock.