philosophers.tsxLab · interactive

dining philosophers · deadlock & strategy

Five philosophers, five chopsticks, one fork-shared-with-each-neighbor. Each needs both before they can eat. Pick the wrong locking order and they all freeze.

Objective

Build a working intuition for deadlock: how a perfectly symmetric protocol can wedge an entire system, and how minor asymmetries (or a serializing waiter) defuse it.

Challenge

Start on naive and wait — within ~30 ticks the table deadlocks. Then switch to asymmetric or waiter and watch the meal counter climb. Bonus: which strategy has higher throughput?

strategy

naive

meals

eating

waiting

strategy

philosopher 1

thinking

meals: 0

philosopher 2

thinking

meals: 0

philosopher 3

thinking

meals: 0

philosopher 4

thinking

meals: 0

philosopher 5

thinking

meals: 0

Source

// pthreads-dp · dining philosophers · three implementations
//
//   naive:      lock(left); lock(right); eat(); unlock(both);
//               → all five grab left simultaneously → deadlock
//
//   asymmetric: odd philosophers grab right first, even grab left first
//               → breaks the symmetry, the cycle never closes
//
//   waiter:     pthread_mutex_t waiter;
//               lock(waiter); lock(left); lock(right); unlock(waiter); eat()
//               → serializes lock-acquisition; never circular

What's really happening

Deadlock requires four conditions held simultaneously (Coffman): mutual exclusion, hold-and-wait, no preemption, circular wait. Break any one and deadlock is impossible. The strategies above each break a different condition:

Asymmetric — different acquire order across some threads breaks circular wait.
Waiter — central permission breaks hold-and-wait: you can't hold any chopstick without the waiter's permission, and the waiter only gives it once both are available.
Try-lock + timeout (not shown) — gives the runtime preemption.

Modern code rarely writes raw mutexes for this — concurrent data structures (lock-free queues, channels, actors) sidestep the problem entirely. But the failure mode shows up wherever you have multiple resources, multiple acquirers, and no agreed-upon global order. Database transactions, for one.

Source

// pthreads-dp · dining philosophers · three implementations // // naive: lock(left); lock(right); eat(); unlock(both); // → all five grab left simultaneously → deadlock // // asymmetric: odd philosophers grab right first, even grab left first // → breaks the symmetry, the cycle never closes // // waiter: pthread_mutex_t waiter; // lock(waiter); lock(left); lock(right); unlock(waiter); eat() // → serializes lock-acquisition; never circular

What's really happening

Asymmetric — different acquire order across some threads breaks circular wait.
Waiter — central permission breaks hold-and-wait: you can't hold any chopstick without the waiter's permission, and the waiter only gives it once both are available.
Try-lock + timeout (not shown) — gives the runtime preemption.