Dining Philosophers (LLD)

Problem statement (interviewer prompt)

Five philosophers sit around a table; each needs the two adjacent forks to eat. Naïvely picking the left then right fork deadlocks. Design a synchronisation policy that lets everyone eventually eat and explain the trade-offs of resource ordering, an arbiter, and the asymmetric solution.

classDiagram
  class Philosopher {
    +id : int
    +leftFork : Fork
    +rightFork : Fork
    +think()
    +eat()
  }
  class Fork {
    +id : int
    -lock : Mutex
  }
  class Strategy {
    <<interface>>
    +acquire(p : Philosopher)
    +release(p : Philosopher)
  }
  class ResourceOrdering
  class Arbiter {
    -waiter : Semaphore
  }
  class Asymmetric
  Philosopher --> Fork : holds 2
  Philosopher --> Strategy
  Strategy <|.. ResourceOrdering
  Strategy <|.. Arbiter
  Strategy <|.. Asymmetric

Resource ordering breaks the circular-wait condition; arbiter / waiter limits concurrent diners; asymmetric flips one philosopher's order.

classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;

Five philosophers, five forks, two forks needed to eat. Naïvely picking left then right fork deadlocks because every philosopher is waiting for their neighbour. The problem is a teaching device for the four conditions of deadlock.

Coffman's four conditions (Dijkstra 1971)

All four must hold for deadlock:

1. Mutual exclusion: a fork is held by at most one philosopher.
2. Hold and wait: holding one fork while waiting for another.
3. No preemption: a fork can't be taken from a philosopher.
4. Circular wait: a cycle in the resource graph.

Each solution breaks one of these.

Solution 1 — Resource ordering (breaks circular wait)

Number the forks; always pick the lower-id first.

class ResourceOrdering:
    def eat(self, p):
        first, second = sorted([p.left, p.right], key=lambda f: f.id)
        with first.lock, second.lock:
            p.do_eat()

Philosopher 4 (the last seat) picks fork 0 first instead of fork 4, breaking the cycle. Simple and effective.

Solution 2 — Arbiter / waiter (breaks hold-and-wait)

A semaphore limits diners to N-1, guaranteeing at least one philosopher can complete:

class Arbiter:
    def __init__(self, n):
        self.waiter = Semaphore(n - 1)

    def eat(self, p):
        with self.waiter:
            with p.left.lock, p.right.lock:
                p.do_eat()

Now at most 4 of 5 philosophers can hold forks simultaneously; the table cannot deadlock.

Solution 3 — Chandy/Misra (token passing)

Each philosopher starts holding the dirty fork on the lower-id side. To eat:

need a fork I don't have? ask my neighbour.
  if their fork is dirty AND I don't need it now → give it up (clean it first).
  else → keep it.

Always converges; no central arbiter; works for arbitrary topologies. Used in distributed-systems coordination.

Solution 4 — Asymmetric (Tanenbaum)

Odd philosophers pick left then right; even philosophers pick right then left.

flowchart LR
  P0[P0: L then R] --> F0((F0))
  P1[P1: R then L] --> F0
  P1 --> F1((F1))
  P2[P2: L then R] --> F1

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class P0,P1,P2 service;
    class F0,F1 datastore;

Two adjacent philosophers contend for the same fork in opposite orders — one always wins, breaking the cycle.

Starvation vs deadlock

Most of the above prevent deadlock but not necessarily starvation (philosopher 2 always loses to philosophers 1 and 3). Fair-FIFO scheduling on the underlying mutex / arbiter is the usual fix.

Class structure

classDiagram
  class Table {
    -forks : Fork[N]
    -strategy : Strategy
    +run()
  }
  class Fork {
    +id : int
    -lock : Mutex
  }
  class Philosopher {
    +id : int
    +left : Fork
    +right : Fork
    +run()
  }
  class Strategy {
    <<interface>>
    +eat(p : Philosopher)
  }
  Table *-- Fork
  Table *-- Philosopher
  Table --> Strategy

Strategy pattern makes the solution swappable; the same philosopher class runs under any policy.

Where dining philosophers connects

flowchart TB
  DP((Dining<br/>philosophers))
  TD[Threading and deadlocks<br/>Coffman conditions]
  CP[Concurrency primitives<br/>mutex + semaphore]
  PO[Pessimistic / optimistic locking<br/>DB deadlock analog]
  DL[Distributed lock<br/>same dynamics across nodes]
  TD --> DP
  CP --> DP
  PO -. DB analog .- DP
  DP -. extends to .-> DL

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class DP service;
    class TD,CP,PO,DL datastore;

Glossary & fundamentals

Tag	Concept	What it is	Page
LLD	Threading and deadlocks	the four Coffman conditions	threading-and-deadlocks
LLD	Concurrency primitives	mutex + semaphore	concurrency-primitives
LLD	Pessimistic vs optimistic locking	DB deadlock analog	pessimistic-optimistic-locking
HLD	Distributed lock	dining philosophers across nodes	distributed-lock

Quick reference

Coffman conditions

All four must hold for deadlock: 1. Mutual exclusion 2. Hold-and-wait 3. No preemption 4. Circular wait

Each solution breaks one.

Four solutions

Solution	Breaks	Note
Resource ordering	Circular wait	Simplest, just sort fork ids
Arbiter / waiter (N-1 semaphore)	Hold-and-wait	Caps concurrent diners
Chandy/Misra token passing	Circular wait	Works for arbitrary graphs
Asymmetric (odd/even reverse order)	Circular wait	Trivial 1-line change

Starvation

Deadlock-free ≠ starvation-free. Add FIFO fairness on the underlying mutex / semaphore.

Strategy pattern

Same Philosopher class; swap Strategy to switch policy.

Real-world parallels

• DB row locks → 2PL / wait-die / wound-wait analogs
• Distributed locks across nodes → same dynamics
• File-system flock contention

Refs

• Dijkstra - Co-operating Sequential Processes (1965)
• Chandy & Misra - Drinking Philosophers (1984)
• Tanenbaum - Modern OS synchronisation chapter

FAQ

What are the four Coffman conditions for deadlock?

Mutual exclusion, hold and wait, no preemption, and circular wait. All four must hold simultaneously, so breaking any one prevents deadlock.

How does resource ordering solve dining philosophers?

Number the forks and have each philosopher always pick the lower-numbered fork first; this breaks the circular wait so the resource graph can no longer form a cycle.

What is the arbiter or waiter solution?

A semaphore initialised to N-1 caps the number of philosophers eating at once, guaranteeing at least one philosopher always finds both forks free.

Does deadlock-free mean starvation-free?

No. A philosopher can lose every contention against its neighbours and never eat. Adding FIFO fairness on the underlying mutex or semaphore prevents starvation.

How does the Chandy-Misra algorithm work?

Each philosopher holds dirty forks; on request, a philosopher gives up a dirty fork it does not currently need and cleans it. The protocol converges without any central arbiter.

Related Topics

• Threading and Deadlocks: the Coffman conditions each solution breaks
• Concurrency Primitives: the mutex + semaphore primitives used here
• Distributed Lock: same dynamics generalised across nodes

Further reading

• Paper - Dijkstra - Co-operating Sequential Processes (1965)
• Paper - Chandy & Misra - The Drinking Philosophers Problem (1984)
• Book - Tanenbaum - Modern Operating Systems (synchronisation chapter)

Video walkthrough

The Dining Philosophers Problem with Java Solution : via Geekific