Loading learning content...
The dining philosophers problem stands as perhaps the most elegant and philosophically rich synchronization challenge in computer science. Proposed by Edsger Dijkstra in 1965 and later reformulated by Tony Hoare, it beautifully illustrates the dangers of resource contention, deadlock, and starvation in concurrent systems.
Imagine five philosophers seated around a circular table. Between each pair of adjacent philosophers lies a single chopstick (or fork, in some formulations). Each philosopher alternates between two activities: thinking and eating. To eat, a philosopher must acquire both chopsticks adjacent to them—the one on their left and the one on their right. The challenge: design a protocol that allows philosophers to eat without deadlock (all philosophers starve while holding one chopstick) or starvation (some philosopher never gets to eat).
By the end of this page, you will:\n\n• Understand the dining philosophers problem and its significance\n• Recognize deadlock conditions in resource acquisition scenarios\n• Implement multiple monitor-based solutions with different properties\n• Analyze the correctness and fairness of each solution\n• Apply these patterns to real-world multi-resource synchronization
Let's formally define the dining philosophers problem with precise constraints.
System Configuration:
Philosopher Lifecycle:
while (true) {
think(); // Non-critical section (variable duration)
pick_up_chopsticks(); // Must acquire both to eat
eat(); // Critical section (requires both chopsticks)
put_down_chopsticks();
}
Required Properties:
| State | Description | Chopsticks Held |
|---|---|---|
| THINKING | Philosopher is contemplating; chopsticks available | 0 |
| HUNGRY | Philosopher wants to eat; trying to acquire chopsticks | 0, 1, or 2 |
| EATING | Philosopher is eating; holds both chopsticks | 2 |
Why This Problem Matters:
The dining philosophers problem abstracts a common concurrent programming challenge: multiple resource acquisition. Many real-world scenarios require a thread to acquire multiple resources atomically:
| Real-World Analog | Resources | Philosophers |
|---|---|---|
| Database transactions | Multiple row locks | Transactions |
| Threading libraries | Multiple mutexes | Threads |
| Bank transfers | Source and destination accounts | Transfer operations |
| Distributed systems | Locks on multiple nodes | Distributed processes |
The techniques we develop here apply directly to these scenarios.
The obvious solution—each philosopher picks up left chopstick, then right chopstick—leads to deadlock! If all philosophers pick up their left chopstick simultaneously, each waits forever for their right chopstick held by their neighbor.
Before implementing solutions, let's rigorously analyze why the naive approach fails using the four necessary conditions for deadlock.
Coffman Conditions in Dining Philosophers:
Since all four conditions can be satisfied simultaneously, deadlock is possible. Our solutions must break at least one condition.
1234567891011121314151617181920212223242526272829
// DANGEROUS: This solution DEADLOCKS!procedure philosopher(id) { while (true) { think(); // Each philosopher picks up left first, then right pick_up(left_chopstick[id]); // All philosophers can succeed here... pick_up(right_chopstick[id]); // ...then ALL block here forever! eat(); put_down(right_chopstick[id]); put_down(left_chopstick[id]); }} // Deadlock scenario (5 philosophers):// Time T: All philosophers finish thinking// Time T+1: P0 picks up chopstick 0// P1 picks up chopstick 1// P2 picks up chopstick 2// P3 picks up chopstick 3// P4 picks up chopstick 4// Time T+2: P0 waits for chopstick 1 (held by P1)// P1 waits for chopstick 2 (held by P2)// P2 waits for chopstick 3 (held by P3)// P3 waits for chopstick 4 (held by P4)// P4 waits for chopstick 0 (held by P0)// DEADLOCK: Circular wait detected!Solution Strategies:
To prevent deadlock, we can break any of the four conditions:
| Condition | Breaking Strategy | Dining Philosophers Application |
|---|---|---|
| Mutual Exclusion | Use sharable resources | Not applicable (chopsticks must be exclusive) |
| Hold and Wait | Request all resources atomically | Philosopher acquires both or neither |
| No Preemption | Allow resource preemption | Release chopsticks if can't get both |
| Circular Wait | Impose ordering on resources | Number chopsticks, always acquire lower first |
We'll implement solutions using the Hold and Wait and Circular Wait strategies, as they're most applicable.
Monitors excel at the dining philosophers problem because they can encapsulate both the chopstick state and the coordination logic. The monitor can enforce that a philosopher either gets both chopsticks or waits, eliminating the partial-acquisition deadlock.
The first solution encapsulates all chopstick state within a monitor and ensures philosophers acquire both chopsticks atomically—either both are available and granted, or the philosopher waits. This breaks the hold and wait condition because no philosopher ever holds one resource while waiting for another.
Design Principles:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113
#include <pthread.h>#include <stdio.h> #define N 5 // Number of philosophers typedef enum { THINKING, HUNGRY, EATING } State; // Global state protected by monitorState state[N];pthread_mutex_t mutex;pthread_cond_t can_eat[N]; // Per-philosopher condition // Helper to get left and right neighbor indices#define LEFT(i) (((i) + N - 1) % N)#define RIGHT(i) (((i) + 1) % N) void init_dining() { pthread_mutex_init(&mutex, NULL); for (int i = 0; i < N; i++) { state[i] = THINKING; pthread_cond_init(&can_eat[i], NULL); }} // Test if philosopher i can eat (both neighbors not eating)void test(int i) { // Philosopher can eat if: // 1. They are hungry (want to eat) // 2. Left neighbor is not eating // 3. Right neighbor is not eating if (state[i] == HUNGRY && state[LEFT(i)] != EATING && state[RIGHT(i)] != EATING) { state[i] = EATING; pthread_cond_signal(&can_eat[i]); // Wake this philosopher }} // Philosopher entry: Try to acquire both chopsticksvoid pick_up_chopsticks(int i) { pthread_mutex_lock(&mutex); state[i] = HUNGRY; printf("Philosopher %d: HUNGRY\n", i); // Try to eat (will succeed if both neighbors not eating) test(i); // If couldn't eat, wait until we can while (state[i] != EATING) { pthread_cond_wait(&can_eat[i], &mutex); } printf("Philosopher %d: EATING\n", i); pthread_mutex_unlock(&mutex);} // Philosopher exit: Release chopsticks and wake neighborsvoid put_down_chopsticks(int i) { pthread_mutex_lock(&mutex); state[i] = THINKING; printf("Philosopher %d: THINKING\n", i); // Check if left and right neighbors can now eat // They might have been waiting for our chopsticks test(LEFT(i)); test(RIGHT(i)); pthread_mutex_unlock(&mutex);} // Philosopher thread functionvoid *philosopher(void *arg) { int id = *(int *)arg; while (1) { // Think printf("Philosopher %d: Thinking...\n", id); usleep(rand() % 1000000); // Random think time // Try to eat pick_up_chopsticks(id); // Eat usleep(rand() % 1000000); // Random eat time // Done eating put_down_chopsticks(id); } return NULL;} int main() { pthread_t threads[N]; int ids[N]; init_dining(); for (int i = 0; i < N; i++) { ids[i] = i; pthread_create(&threads[i], NULL, philosopher, &ids[i]); } for (int i = 0; i < N; i++) { pthread_join(threads[i], NULL); } return 0;}How This Solution Works:
Atomic State Check: The test(i) function checks if philosopher i can eat by atomically verifying both neighbors' states. This is safe because it runs inside the monitor (mutex held).
No Partial Holding: A philosopher transitions directly from HUNGRY to EATING only when both chopsticks are available. They never hold one while waiting for another.
Targeted Signaling: Per-philosopher condition variables allow precise wakeups. When philosopher i finishes, we only test and potentially wake their left and right neighbors.
Efficient Notification: The test() function is called both when a philosopher becomes hungry (immediate try) and when their neighbor finishes eating (reactive wake).
Using N condition variables (one per philosopher) instead of a single condition is crucial for efficiency. With a single condition, every philosopher would wake up on every signal, causing unnecessary context switches. Per-philosopher conditions enable targeted wakeups.
The second solution breaks the circular wait condition by imposing a total ordering on chopsticks. Philosophers must always acquire chopsticks in order of their numbers. This classical technique prevents cycles in the wait-for graph.
Ordering Rule:
Number chopsticks 0 to N-1. Each philosopher must first acquire the lower-numbered chopstick, then the higher-numbered one.
For philosopher i:
Special Case: Philosopher N-1
Philosopher 4 (in a 5-philosopher setup) has left=4 and right=0. They must acquire chopstick 0 first, then 4. This reversal is what breaks the circular wait!
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384
#include <pthread.h>#include <stdio.h> #define N 5 // Each chopstick is a separate mutex (representing a resource)pthread_mutex_t chopstick[N]; // Helper macros#define LEFT(i) (i)#define RIGHT(i) (((i) + 1) % N)#define MIN(a,b) ((a) < (b) ? (a) : (b))#define MAX(a,b) ((a) > (b) ? (a) : (b)) void init_chopsticks() { for (int i = 0; i < N; i++) { pthread_mutex_init(&chopstick[i], NULL); }} void pick_up_chopsticks(int id) { int left = LEFT(id); int right = RIGHT(id); // CRITICAL: Always acquire lower-numbered chopstick first // This breaks circular wait! int first = MIN(left, right); int second = MAX(left, right); printf("Philosopher %d: Acquiring chopstick %d first\n", id, first); pthread_mutex_lock(&chopstick[first]); printf("Philosopher %d: Acquiring chopstick %d second\n", id, second); pthread_mutex_lock(&chopstick[second]); printf("Philosopher %d: Has both chopsticks, eating\n", id);} void put_down_chopsticks(int id) { int left = LEFT(id); int right = RIGHT(id); // Release order doesn't matter for correctness // (but releasing in reverse order of acquisition is conventional) pthread_mutex_unlock(&chopstick[MAX(left, right)]); pthread_mutex_unlock(&chopstick[MIN(left, right)]); printf("Philosopher %d: Released chopsticks\n", id);} void *philosopher(void *arg) { int id = *(int *)arg; while (1) { printf("Philosopher %d: Thinking...\n", id); usleep(rand() % 1000000); pick_up_chopsticks(id); // Eat usleep(rand() % 500000); put_down_chopsticks(id); } return NULL;} int main() { pthread_t threads[N]; int ids[N]; init_chopsticks(); for (int i = 0; i < N; i++) { ids[i] = i; pthread_create(&threads[i], NULL, philosopher, &ids[i]); } for (int i = 0; i < N; i++) { pthread_join(threads[i], NULL); } return 0;}Why Resource Ordering Prevents Deadlock:
Consider the execution with 5 philosophers:
| Philosopher | Left Chopstick | Right Chopstick | First to Acquire | Second to Acquire |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 2 | 1 | 2 |
| 2 | 2 | 3 | 2 | 3 |
| 3 | 3 | 4 | 3 | 4 |
| 4 | 4 | 0 | 0 | 4 |
Notice that philosopher 4 acquires chopstick 0 first (not 4). This prevents the circular wait:
Lock ordering is a fundamental technique in systems programming. The Linux kernel requires strict lock ordering to prevent deadlocks. Tools like lockdep dynamically check that locks are acquired in consistent order and report violations.
A third elegant solution limits the number of philosophers who can attempt to eat simultaneously. If at most N-1 philosophers are allowed at the table, at least one philosopher can always acquire both chopsticks, ensuring progress.
Intuition:
With 5 philosophers and 5 chopsticks:
Implementation:
Use a counting semaphore (or bounded counter in a monitor) initialized to N-1 that philosophers must acquire before attempting to pick up chopsticks.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
#include <pthread.h>#include <semaphore.h>#include <stdio.h> #define N 5 pthread_mutex_t chopstick[N];sem_t table_seats; // Limits concurrent diners void init_dining() { for (int i = 0; i < N; i++) { pthread_mutex_init(&chopstick[i], NULL); } // Allow at most N-1 philosophers at table sem_init(&table_seats, 0, N - 1);} void pick_up_chopsticks(int id) { int left = id; int right = (id + 1) % N; // First, get a seat at the table (limits concurrency) // This is the key: at most N-1 philosophers try for chopsticks printf("Philosopher %d: Waiting for seat at table\n", id); sem_wait(&table_seats); // Now safe to acquire chopsticks in any order! // With N-1 philosophers, deadlock impossible printf("Philosopher %d: Got seat, acquiring chopsticks\n", id); pthread_mutex_lock(&chopstick[left]); pthread_mutex_lock(&chopstick[right]); printf("Philosopher %d: Eating\n", id);} void put_down_chopsticks(int id) { int left = id; int right = (id + 1) % N; pthread_mutex_unlock(&chopstick[right]); pthread_mutex_unlock(&chopstick[left]); // Release seat at table sem_post(&table_seats); printf("Philosopher %d: Done eating, left table\n", id);} void *philosopher(void *arg) { int id = *(int *)arg; while (1) { printf("Philosopher %d: Thinking...\n", id); usleep(rand() % 1000000); pick_up_chopsticks(id); usleep(rand() % 500000); put_down_chopsticks(id); } return NULL;}Correctness Proof:
Theorem: With at most N-1 philosophers at the table, deadlock cannot occur.
Proof:
Monitor-Based Variant:
We can implement this using a monitor instead of a semaphore:
123456789101112131415161718192021222324252627282930313233343536373839404142
// Monitor-based solution with seat limiting typedef struct { int seats_available; pthread_mutex_t mutex; pthread_cond_t seat_freed;} TableMonitor; void table_init(TableMonitor *t, int max_diners) { t->seats_available = max_diners; pthread_mutex_init(&t->mutex, NULL); pthread_cond_init(&t->seat_freed, NULL);} void take_seat(TableMonitor *t) { pthread_mutex_lock(&t->mutex); while (t->seats_available == 0) { pthread_cond_wait(&t->seat_freed, &t->mutex); } t->seats_available--; pthread_mutex_unlock(&t->mutex);} void leave_seat(TableMonitor *t) { pthread_mutex_lock(&t->mutex); t->seats_available++; pthread_cond_signal(&t->seat_freed); pthread_mutex_unlock(&t->mutex);} // Usage in philosopher:void pick_up_chopsticks_monitor(int id, TableMonitor *table) { take_seat(table); // Limit concurrency via monitor pthread_mutex_lock(&chopstick[id]); pthread_mutex_lock(&chopstick[(id + 1) % N]);}This solution is remarkably elegant: a single additional constraint (limit diners to N-1) eliminates all complexity. Philosophers can pick up chopsticks in any order—no need for ordering or complex state tracking. The limitation naturally prevents the pathological case.
All three solutions prevent deadlock, but starvation is a separate concern. A philosopher starves if they are perpetually ready to eat but never get to.
Starvation Scenarios by Solution:
Solution 1 (Atomic Acquisition):
Depends on condition variable fairness. If can_eat[i] uses FIFO ordering (most implementations do), starvation is prevented. However, if philosopher i's neighbors alternate eating, i might wait indefinitely.
Solution 2 (Resource Ordering):
Philosopher 4 (who reverses order) might starve if philosophers 0 and 3 constantly compete for chopsticks 0 and 4. The ordering prevents deadlock but doesn't guarantee fairness.
Solution 3 (Limiting Diners):
Does not directly address starvation. A philosopher might repeatedly fail to get a seat while others keep cycling. Fairness depends on the underlying semaphore/monitor implementation.
| Solution | Deadlock Free | Starvation Free | Conditions for Starvation |
|---|---|---|---|
| Atomic Acquisition | ✅ Yes | ⚠️ Conditional | If condition variables not FIFO; neighbor oscillation |
| Resource Ordering | ✅ Yes | ❌ Not guaranteed | Asymmetric ordering can favor certain philosophers |
| Limiting Diners | ✅ Yes | ⚠️ Conditional | If semaphore/seat allocation not fair |
Ensuring Fairness:
To guarantee no starvation, we can extend the atomic acquisition solution with priority aging or ticket-based ordering:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
// Fair dining philosophers with ticket-based ordering #define N 5 typedef enum { THINKING, HUNGRY, EATING } State; State state[N];unsigned long ticket[N]; // Arrival ticket for each philosopherunsigned long next_ticket; // Global ticket counter pthread_mutex_t mutex;pthread_cond_t can_eat[N]; // Test if philosopher i should eat// Only eat if: hungry, neighbors not eating, AND no earlier-arriving // hungry neighbor is waitingvoid test_fair(int i) { if (state[i] != HUNGRY) return; if (state[LEFT(i)] == EATING || state[RIGHT(i)] == EATING) return; // Fairness check: don't eat if a neighbor has an earlier ticket // and is hungry (they should go first) if (state[LEFT(i)] == HUNGRY && ticket[LEFT(i)] < ticket[i]) return; if (state[RIGHT(i)] == HUNGRY && ticket[RIGHT(i)] < ticket[i]) return; // We can eat! state[i] = EATING; pthread_cond_signal(&can_eat[i]);} void pick_up_chopsticks_fair(int i) { pthread_mutex_lock(&mutex); state[i] = HUNGRY; ticket[i] = next_ticket++; // Get arrival ticket test_fair(i); while (state[i] != EATING) { pthread_cond_wait(&can_eat[i], &mutex); } pthread_mutex_unlock(&mutex);} void put_down_chopsticks_fair(int i) { pthread_mutex_lock(&mutex); state[i] = THINKING; ticket[i] = ULONG_MAX; // Reset ticket // Test neighbors with fairness checks test_fair(LEFT(i)); test_fair(RIGHT(i)); pthread_mutex_unlock(&mutex);}With ticket-based ordering, each philosopher is guaranteed to eat within N "rounds" after becoming hungry. A philosopher waits at most for their two neighbors to eat, and those neighbors wait for their neighbors, creating a bounded chain of length N.
The dining philosophers problem models numerous real-world multi-resource acquisition scenarios. Understanding the solutions helps prevent deadlocks in production systems.
Database Transaction Deadlocks:
When transactions need to lock multiple rows:
-- Transaction A
UPDATE accounts SET balance = balance - 100 WHERE id = 1; -- Locks row 1
UPDATE accounts SET balance = balance + 100 WHERE id = 2; -- Waits for row 2
-- Transaction B (concurrent)
UPDATE accounts SET balance = balance - 50 WHERE id = 2; -- Locks row 2
UPDATE accounts SET balance = balance + 50 WHERE id = 1; -- Waits for row 1
-- DEADLOCK!
Solution: Lock rows in consistent order (e.g., by primary key):
-- Always lock lower-numbered row first
IF source_id < dest_id THEN
LOCK accounts WHERE id = source_id;
LOCK accounts WHERE id = dest_id;
ELSE
LOCK accounts WHERE id = dest_id;
LOCK accounts WHERE id = source_id;
END IF;
123456789101112131415161718192021222324252627282930313233343536
#include <mutex>#include <algorithm> class Account { mutable std::mutex mtx; int balance; int id; public: Account(int id, int initial) : id(id), balance(initial) {} // Safe transfer using lock ordering static void transfer(Account& from, Account& to, int amount) { // Always lock in consistent order by ID to prevent deadlock Account* first = &from; Account* second = &to; if (from.id > to.id) { std::swap(first, second); } // Use std::scoped_lock for exception-safe locking of multiple mutexes // (C++17: this also handles deadlock avoidance internally) std::scoped_lock lock(first->mtx, second->mtx); if (from.balance >= amount) { from.balance -= amount; to.balance += amount; } } int get_balance() const { std::lock_guard<std::mutex> lock(mtx); return balance; }};C++17's std::scoped_lock can lock multiple mutexes while automatically avoiding deadlock (using a try-and-backoff algorithm). This is the recommended approach for modern C++ code:\n\ncpp\nstd::scoped_lock lock(mutex1, mutex2, mutex3);\n// All three locked without deadlock risk\n
The dining philosophers problem elegantly illustrates the complexities of multi-resource synchronization. We've explored three distinct solutions, each breaking a different deadlock condition.
What's Next:
Having implemented three classic synchronization problems with monitors, we'll now directly compare monitor-based solutions with their semaphore-based counterparts. This comparison will crystallize the advantages and tradeoffs of each approach.
You now understand how to solve the dining philosophers problem using monitors, with multiple solution strategies that break different deadlock conditions. These patterns for multi-resource acquisition are essential for building deadlock-free concurrent systems.