Skip to main content

​
The Classic Problem

The Dining Philosophers Problem is a classic synchronization problem in computer science, originally formulated by Edsger Dijkstra in 1965. It illustrates fundamental challenges in concurrent programming, particularly around resource allocation, deadlock, and starvation.
While the problem uses philosophers and forks as a metaphor, it represents any scenario where multiple processes compete for limited shared resources.

​
The Scenario

Imagine a group of philosophers sitting around a circular dining table. Their life consists of two activities:
  1. Thinking - Contemplating the mysteries of the universe
  2. Eating - Consuming spaghetti from a bowl in front of them
In this implementation, philosophers also sleep after eating to add another state to the simulation.

​
The Table Setup

         Fork
          |
    Philosopher 1
   /            \
Fork            Fork
   \            /
    Philosopher 2
          |
         Fork
   (circular pattern...)
There are N philosophers and N forks on the table. Each fork is placed between two philosophers.

​
The Rules

  1. Two forks required: A philosopher must pick up both adjacent forks (left and right) to eat
  2. One fork per hand: Each fork can only be held by one philosopher at a time
  3. Sequential actions: After eating, a philosopher puts down both forks, sleeps, then thinks
  4. Starvation constraint: Each philosopher must eat before a specified time (time_to_die) elapses, or they die
  5. No communication: Philosophers don’t communicate with each other

​
The Challenges

The dining philosophers problem exposes three critical challenges in concurrent systems:

​
1. Deadlock

Deadlock occurs when all philosophers simultaneously pick up their right fork and wait indefinitely for their left fork.
Deadlock Scenario: If every philosopher picks up their right fork at the same time, no one can pick up their left fork because it’s held by their neighbor. All philosophers wait forever, and the system is stuck.

​
Example Deadlock Sequence:

Time 0ms:
  Philosopher 1: picks up right fork (Fork 1)
  Philosopher 2: picks up right fork (Fork 2)
  Philosopher 3: picks up right fork (Fork 3)
  ...
  Philosopher N: picks up right fork (Fork N)

Time 1ms:
  Philosopher 1: waiting for left fork (Fork N) - HELD BY Philosopher N
  Philosopher 2: waiting for left fork (Fork 1) - HELD BY Philosopher 1
  Philosopher 3: waiting for left fork (Fork 2) - HELD BY Philosopher 2
  ...
  → DEADLOCK: Circular wait with no progress

​
Deadlock Prevention in This Implementation

The program prevents deadlock through: 
void *philo_routine(void *pointer)
{
    t_philo *philo = (t_philo *)pointer;
    
    // Even philosophers start with a 1ms delay
    if (philo->id % 2 == 0)
        ft_usleep(1);
    
    while (!dead_loop(philo))
    {
        ft_eat(philo);
        ft_sleep(philo);
        ft_think(philo);
    }
}
By delaying even-numbered philosophers by 1 millisecond, the implementation creates temporal asymmetry that prevents all philosophers from picking up forks simultaneously.

​
2. Starvation

Starvation happens when a philosopher never gets access to both forks, even though the system as a whole makes progress.
Starvation Scenario: Philosophers 1 and 3 keep eating in alternation, while Philosopher 2 (sitting between them) never gets both forks and eventually dies of hunger.

​
Starvation Prevention

The monitor thread continuously checks if any philosopher has exceeded time_to_die without eating: 
int philosopher_dead(t_philo *philo, size_t time_to_die)
{
    pthread_mutex_lock(philo->lock_meal);
    if (get_current_time() - philo->last_meal_time >= time_to_die
        && philo->eating == 0)
        return (pthread_mutex_unlock(philo->lock_meal), 1);
    pthread_mutex_unlock(philo->lock_meal);
    return (0);
}

​
Time Tracking:

  • Each philosopher’s last_meal_time is updated whenever they start eating
  • The monitor checks if current_time - last_meal_time >= time_to_die
  • If exceeded and the philosopher isn’t currently eating, they die

​
3. Race Conditions

Race conditions occur when multiple threads access shared data concurrently without proper synchronization, leading to unpredictable results.

​
Potential Race Conditions:

  1. Fork access: Two philosophers trying to grab the same fork
  2. Console output: Multiple threads printing to stdout simultaneously
  3. Death flag: Multiple threads checking/setting the simulation stop flag
  4. Meal counter: Reading and writing meal counts concurrently

​
Race Condition Prevention

The implementation uses mutexes to protect all shared resources: 
typedef struct s_table
{
    int     dead_flag;           // Protected by lock_dead
    t_mtx   lock_dead;          // Guards dead_flag
    t_mtx   lock_write;         // Guards console output
    t_mtx   lock_meal;          // Guards meal counters
    t_philo *philos;
} t_table;

typedef struct s_philo
{
    // ... other fields ...
    t_mtx   *left_fork;         // Fork mutex (shared with left neighbor)
    t_mtx   *right_fork;        // Fork mutex (shared with right neighbor)
    t_mtx   *lock_write;        // Pointer to shared write mutex
    t_mtx   *lock_dead;         // Pointer to shared dead mutex
    t_mtx   *lock_meal;         // Pointer to shared meal mutex
} t_philo;

​
Protected Operations:

Fork acquisition: 
pthread_mutex_lock(philo->right_fork);
print_message("has taken a fork", philo, philo->id);
pthread_mutex_lock(philo->left_fork);
print_message("has taken a fork", philo, philo->id);
Console output: 
void print_message(char *str, t_philo *philo, int id)
{
    pthread_mutex_lock(philo->lock_write);
    time = get_current_time() - philo->start_time;
    if (!dead_loop(philo))
        printf("%zu %d %s\n", time, id, str);
    pthread_mutex_unlock(philo->lock_write);
}
Death flag check: 
int dead_loop(t_philo *philo)
{
    pthread_mutex_lock(philo->lock_dead);
    if (*philo->dead == 1)
        return (pthread_mutex_unlock(philo->lock_dead), 1);
    pthread_mutex_unlock(philo->lock_dead);
    return (0);
}

​
The Philosopher Lifecycle

Each philosopher follows a continuous cycle:

​
State Transitions

Thinking

The philosopher contemplates. No resources are held during this state.

Eating

The philosopher holds both forks and consumes food. Updates last_meal_time and meal_counter.

Sleeping

The philosopher rests after eating. No resources are held during this state.

​
Implementation:

void *philo_routine(void *pointer)
{
    t_philo *philo = (t_philo *)pointer;
    
    if (philo->id % 2 == 0)
        ft_usleep(1);
    
    while (!dead_loop(philo))  // While not dead
    {
        ft_eat(philo);         // EATING state
        ft_sleep(philo);       // SLEEPING state
        ft_think(philo);       // THINKING state
    }
    return (pointer);
}

​
Special Cases

​
Single Philosopher

With only one philosopher and one fork, eating is impossible: 
void ft_eat(t_philo *philo)
{
    pthread_mutex_lock(philo->right_fork);
    print_message("has taken a fork", philo, philo->id);
    
    if (philo->nbr_philo == 1)
    {
        ft_usleep(philo->time_to_die);  // Wait until death
        pthread_mutex_unlock(philo->right_fork);
        return;
    }
    // ... normal eating logic ...
}
With one philosopher, they pick up the only fork, wait for time_to_die, and die. This edge case is handled explicitly.

​
Two Philosophers

With two philosophers, the problem simplifies:
  • Philosopher 1 (odd) starts immediately
  • Philosopher 2 (even) waits 1ms
  • They alternate eating without deadlock

​
Simulation Termination

The simulation ends when either:
  1. A philosopher dies: Any philosopher exceeds time_to_die without eating
  2. Meal goal reached: All philosophers eat at least max_meals times (if specified)
void *monitor(void *pointer)
{
    t_philo *philos = (t_philo *)pointer;
    
    while (1)
        if (check_if_dead(philos) == 1 || check_if_all_ate(philos) == 1)
            break;
    
    return (pointer);
}

​
Real-World Analogies

The dining philosophers problem models many real-world scenarios:
  • Database transactions: Multiple transactions competing for locks on database records
  • Operating system resources: Processes competing for CPU, memory, and I/O devices
  • Network protocols: Nodes competing for access to shared communication channels
  • Multithreaded applications: Threads competing for shared data structures
Any system where multiple concurrent entities compete for exclusive access to limited shared resources faces similar challenges.

​
Key Takeaways

  1. Concurrency is hard: Even simple scenarios like dining philosophers reveal complex synchronization challenges
  2. Mutexes are essential: Proper use of mutexes prevents race conditions and ensures data consistency
  3. Deadlock prevention requires design: Asymmetry (delayed starts) breaks circular wait conditions
  4. Monitoring is crucial: A separate monitor thread ensures fairness and detects starvation
  5. Timing matters: Precise time tracking is necessary for enforcing starvation constraints

​
Next Steps

Getting Started

Learn how to build and run the simulation

Code Architecture

Explore the implementation details and data structures

Build docs developers (and LLMs) love

Get started for freeTalk to us