🍽️ Dining Philosophers Solution

Overview

This project implements a robust solution to the classic Dining Philosophers Problem using multithreading and mutex synchronization in C. The solution prevents deadlocks and starvation through asymmetric resource acquisition and urgency-based scheduling, ensuring efficient and fair resource allocation.

Problem Statement

The Dining Philosophers Problem illustrates challenges in concurrent resource allocation:

• Philosophers sit at a round table with spoons (shared resources) between them.
• Each philosopher requires two adjacent spoons to eat.
• Challenges to avoid:
  • Deadlock: All philosophers hold one spoon, causing a circular wait.
  • Starvation: Some philosophers are unable to acquire both spoons.

Solution Architecture

graph TD
    A[Main Thread] -->|Spawns| B[Philosopher Threads]
    A -->|Spawns| C[Monitor Thread]
    B -->|Executes| D[Philosopher Lifecycle]
    C -->|Monitors| E[Death/Meal Conditions]
    D -->|Attempts| F[Acquire Spoons]
    D -->|Performs| G[Eat]
    D -->|Releases| H[Release Spoons]
    E -->|Triggers| I[Terminate Simulation]

Loading

Key Features

🔒 Deadlock Prevention

• Asymmetric Spoon Acquisition:
  • Even-indexed philosophers pick up the right spoon first.
  • Odd-indexed philosophers pick up the left spoon first.
  • Breaks the circular wait condition by enforcing non-uniform acquisition order.

⚡ Starvation Prevention

• Urgency-Based Scheduling:

  death_threshold = die_time * 0.75;
  is_urgent = (time_since_last_eat > death_threshold);

  • Urgent philosophers (nearing starvation) release spoons faster (100µs vs. 1000µs).
  • Ensures no philosopher waits indefinitely.

🔄 Synchronization Mechanisms

• Protected Resources:
  • Spoon availability (spoon->guard mutex).
  • Last meal time (m_last_eat mutex).
  • Simulation state (m_is_over mutex).
  • Output synchronization (print_lock mutex).

👁️ Efficient Monitoring

• A dedicated monitor thread checks conditions every 1ms:

  while (1) {
      now_time = get_time() - start_time;
      status = check_all_philos(...);
      if (status != 0) break;
      wait_ms(1);
  }

Compilation & Usage

Compilation

make

Execution

./philo [philos] [die_time] [eat_time] [sleep_time] [meals]

Arguments

Argument	Description	Constraints
philos	Number of philosophers	1–200
die_time	Time (ms) before a philosopher starves	≥60
eat_time	Time (ms) to eat	≥60
sleep_time	Time (ms) to sleep	≥60
meals	(Optional) Meals per philosopher	Positive integer

Example

./philo 5 800 200 200 7

• 5 philosophers, 800ms death timer, 200ms eating, 200ms sleeping, stop after 7 meals per philosopher.

Output Example

0 1 has taken a fork
0 1 is eating
200 1 is sleeping
200 2 has taken a fork
200 2 is eating
400 1 is thinking
...
800 3 died

Simulation Rules

• Each philosopher must eat before die_time expires.
• Requires two adjacent spoons to eat.
• Spoons are returned after eating.
• Simulation terminates when:
  • Any philosopher dies.
  • All philosophers complete the specified meals (if provided).

Implementation Highlights

Philosopher Routine

void philosopher_routine(t_philosopher *philosopher) {
    while (!is_ended(philosopher)) {
        if (philosopher->config->max_meals > 0 &&
            philosopher->eat_count >= philosopher->config->max_meals)
            break;
        
        // Check meal urgency
        time_since_last_eat = (get_time() - config->start_time) - last_eat;
        is_urgent = (time_since_last_eat > death_threshold);
        
        // Asymmetric spoon acquisition
        if (philosopher->place % 2 == 0)
            pick_up_left_first(philosopher);
        else
            pick_up_right_first(philosopher);
            
        handle_eating_or_wait(philosopher, is_urgent);
    }
}

Spoon Acquisition Logic

void try_grab_spoon(t_spoon *spoon, int *grabbed, t_philosopher *philosopher) {
    while (!is_ended(philosopher)) {
        pthread_mutex_lock(&spoon->guard);
        if (!spoon->taken) {
            spoon->taken = 1;
            *grabbed = 1;
            pthread_mutex_unlock(&spoon->guard);
            print_status("has taken a fork", philosopher);
            return;
        }
        pthread_mutex_unlock(&spoon->guard);
        usleep(100); // Non-busy waiting
    }
}

Performance Optimizations

• Staggered Starts:

  stagger_time = (place * eat_time) / total_philos;

• Non-blocking Checks: Uses usleep() to avoid busy-waiting.
• Efficient Timing: Leverages gettimeofday() for millisecond precision.
• Selective Urgency: Prioritizes only high-risk philosophers.

Validation & Error Handling

• Input Validation:
  • Ensures numeric arguments, positive values, and integer overflow protection.
• Resource Cleanup:
  • Destroys mutexes, frees memory, and joins threads properly.

Getting Started

1. Clone the repository:

   git clone <repository-url>

2. Compile the program:

   make

3. Run with desired parameters:

   ./philo 5 800 200 200