The Dining Philosophers - Practice Coding Problems

The Dining Philosophers - Problem

Concurrency Medium

Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.

Rules:

Each philosopher must alternately think and eat
A philosopher can only eat when they have both left and right forks
Each fork can be held by only one philosopher at a time
After eating, philosophers must put down both forks
No philosopher should starve (deadlock prevention required)

Implementation:

Implement the function void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork) where:

philosopher is the ID (0-4) of the philosopher who wants to eat
pickLeftFork and pickRightFork are functions to pick up forks
eat is the function to let the philosopher eat
putLeftFork and putRightFork are functions to put down forks

Five threads will simultaneously call this function. Design a deadlock-free solution that prevents starvation.

Input & Output

Example 1 — Basic Philosopher Eating

$ Input: philosopher = 0, actions = [pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork]

› Output: Philosopher 0 successfully eats

💡 Note: Philosopher 0 acquires fork 0 (left) and fork 1 (right), eats, then releases both forks in proper order.

Example 2 — Multiple Philosophers

$ Input: philosophers = [0, 1, 2] wanting to eat simultaneously

› Output: All philosophers eventually eat without deadlock

💡 Note: Using asymmetric approach: P0 (even) picks right first, P1 (odd) picks left first, P2 (even) picks right first. This prevents circular waiting.

Example 3 — All Philosophers Competing

$ Input: All 5 philosophers (0, 1, 2, 3, 4) want to eat at same time

› Output: System remains deadlock-free, all philosophers eventually eat

💡 Note: Semaphore approach allows max 4 philosophers to compete, guaranteeing at least one can acquire both forks and complete the eating cycle.

Constraints

5 philosophers numbered 0 to 4
5 forks placed between adjacent philosophers
Multiple threads call wantsToEat() simultaneously
Must prevent deadlock and starvation
Each philosopher alternates between thinking and eating

Visualization

Tap to expand

Understanding the Visualization

Setup

5 philosophers sit around circular table with 5 forks between them

Challenge

Each needs both adjacent forks to eat, but naive approach causes deadlock

Solution

Break symmetry with asymmetric fork ordering to prevent circular wait

Key Takeaway

🎯 Key Insight: Break circular symmetry - even philosophers pick right first, odd pick left first

Asked in

G Google 45 M Microsoft 38 a Amazon 42 f Meta 35

The key insight is breaking symmetry to prevent circular waiting deadlock. The asymmetric fork ordering approach works best: even philosophers pick right fork first, odd philosophers pick left fork first. This guarantees at least one philosopher can always complete eating. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Semaphore with Limited Seats	O(1)	O(1)	Allow maximum 4 philosophers to attempt eating simultaneously using semaphores
Global Lock Solution	O(1)	O(1)	Use a single global mutex to serialize all eating attempts
Asymmetric Fork Ordering	O(1)	O(1)	Break symmetry by making even/odd philosophers pick forks in different orders

Semaphore with Limited Seats — Algorithm Steps

Acquire semaphore permit (max 4)
Pick up left fork
Pick up right fork
Eat
Put down both forks
Release semaphore permit

Visualization

Tap to expand

Step-by-Step Walkthrough

Semaphore Limit

Maximum 4 philosophers can attempt eating

Fork Competition

4 philosophers compete for 5 forks

Guaranteed Success

At least one philosopher can always get both forks

Code -

solution.c — C

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

typedef struct {
    pthread_mutex_t forks[5];
    sem_t semaphore;
} DiningPhilosophers;

void initDiningPhilosophers(DiningPhilosophers* obj) {
    for (int i = 0; i < 5; i++) {
        pthread_mutex_init(&obj->forks[i], NULL);
    }
    sem_init(&obj->semaphore, 0, 4);
}

void wantsToEat(DiningPhilosophers* obj,
               int philosopher,
               void (*pickLeftFork)(),
               void (*pickRightFork)(),
               void (*eat)(),
               void (*putLeftFork)(),
               void (*putRightFork)()) {
    int leftFork = philosopher;
    int rightFork = (philosopher + 1) % 5;
    
    sem_wait(&obj->semaphore);
    
    pthread_mutex_lock(&obj->forks[leftFork]);
    pickLeftFork();
    pthread_mutex_lock(&obj->forks[rightFork]);
    pickRightFork();
    eat();
    putRightFork();
    pthread_mutex_unlock(&obj->forks[rightFork]);
    putLeftFork();
    pthread_mutex_unlock(&obj->forks[leftFork]);
    
    sem_post(&obj->semaphore);
}

void mockAction() {}

int main() {
    DiningPhilosophers dp;
    initDiningPhilosophers(&dp);
    wantsToEat(&dp, 0, mockAction, mockAction, mockAction, mockAction, mockAction);
    printf("Philosopher 0 finished eating\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Constant time semaphore and fork operations

✓ Linear Growth

Space Complexity

O(1)

Requires 5 fork mutexes plus 1 semaphore (constant space)

✓ Linear Space

23.4K Views

Medium Frequency

~30 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Semaphore with Limited Seats — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler