Philosophers - Dining Philosophers Problem

📖 About

Philosophers is a project that simulates the classic Dining Philosophers Problem, a fundamental computer science problem in concurrent algorithm design. The simulation involves philosophers sitting at a round table, alternating between eating, sleeping, and thinking, while managing shared resources (forks) without falling into deadlock or starvation.

Through this project, I developed deep understanding of:

• Thread programming and synchronization
• Mutex management and race condition prevention
• Deadlock avoidance strategies
• Process timing and precision
• Resources sharing between threads

🎯 Project Goals

• Implement a multi-threaded simulation using POSIX threads (pthreads)
• Prevent data races through proper mutex usage
• Avoid deadlocks through careful resource management
• Ensure precise timing for philosopher actions
• Monitor philosopher states to detect death or completion

🧠 The Dining Philosophers Problem

The scenario involves:

• N philosophers sitting at a round table
• N forks placed between each pair of philosophers
• Each philosopher needs 2 forks to eat
• Philosophers alternate between eating, sleeping, and thinking
• A philosopher dies if they don't eat within a specified time

The Challenge

The challenge is to write a program that:

• Creates one thread per philosopher
• Prevents deadlock (all philosophers waiting for forks)
• Prevents data races (proper mutex protection)
• Detects when a philosopher dies from starvation
• Tracks meal counts if specified
• Reports state changes with precise timestamps

📋 Rules and Constraints

Program Arguments

./philosophers number_of_philosophers time_to_die time_to_eat time_to_sleep [number_of_times_each_philosopher_must_eat]

• number_of_philosophers: Number of philosophers (and forks)
• time_to_die: Time in milliseconds - if a philosopher doesn't start eating within this time since their last meal, they die
• time_to_eat: Time in milliseconds - duration of eating
• time_to_sleep: Time in milliseconds - duration of sleeping
• number_of_times_each_philosopher_must_eat: (Optional) - simulation stops when all philosophers have eaten this many times

Philosopher States

Each philosopher can be in one of the following states:

• 🍴 Taking a fork: Philosopher picks up a fork
• 🍝 Eating: Philosopher is eating (requires both forks)
• 😴 Sleeping: Philosopher is sleeping
• 🤔 Thinking: Philosopher is thinking
• 💀 Died: Philosopher has starved

Output Format

[timestamp_in_ms] [philosopher_id] [status]

Example:

0 1 has taken a fork
0 1 has taken a fork
0 1 is eating
200 1 is sleeping
400 1 is thinking
400 2 has taken a fork

🛠️ Implementation Details

Data Structures

typedef struct s_philos
{
    int             id;                  // Philosopher identifier
    long            last_meal_time;      // Timestamp of last meal
    int             meals_eaten;         // Number of meals consumed
    int             is_philo_full;       // Flag for completion
    pthread_mutex_t *right_fork;         // Right fork mutex
    pthread_mutex_t *left_fork;          // Left fork mutex
    pthread_t       thread;              // Philosopher thread
    t_data          *data;               // Shared data pointer
}                   t_philos;

typedef struct s_data
{
    int             num_of_phil;         // Number of philosophers
    int             time_to_die;         // Time until starvation
    int             time_to_eat;         // Duration of eating
    int             time_to_sleep;       // Duration of sleeping
    int             eat_counter;         // Required meal count
    pthread_mutex_t *forks;              // Array of fork mutexes
    pthread_mutex_t write_lock;          // Output protection
    pthread_mutex_t meal_lock;           // Meal time protection
    pthread_mutex_t stop_lock;           // Stop flag protection
    pthread_mutex_t start_lock;          // Synchronized start
    t_philos        *philos;             // Array of philosophers
    int             is_stop;             // Simulation stop flag
    long            start_time;          // Simulation start time
}                   t_data;

Key Features

1. Deadlock Prevention

• Even-numbered philosophers delay slightly before starting
• Left fork is always picked up first, then right fork
• Ensures no circular wait condition

2. Race Condition Prevention

• Multiple mutexes protect shared resources:
  • write_lock: Protects console output
  • meal_lock: Protects last meal time and meal count
  • stop_lock: Protects simulation stop flag
  • Individual fork mutexes for each fork

3. Precise Timing

• Uses gettimeofday() for millisecond precision
• Custom ms_sleep() function for accurate delays
• Prevents usleep inaccuracies through busy-wait loops

4. Monitoring System

• Dedicated watchdog thread monitors all philosophers
• Checks for death conditions every 500 microseconds
• Detects meal completion when all philosophers reach quota

5. Special Cases

• Single philosopher: Takes one fork and dies
• Graceful shutdown when death occurs or all meals completed

🛠️ Compilation

Building the Program

make

This creates the philosophers executable.

Available Make Commands

• make - Compile the program
• make clean - Remove object files
• make fclean - Remove object files and executable
• make re - Recompile everything from scratch

Compiler Flags

• -Wall -Wextra -Werror - Enable all warnings and treat them as errors
• -pthread - Link pthread library

🚀 Usage

Basic Examples

# 5 philosophers, die after 800ms, eat for 200ms, sleep for 200ms
./philosophers 5 800 200 200

# Same as above, but stop after each philosopher eats 7 times
./philosophers 5 800 200 200 7

# 4 philosophers with tight timing (should not die)
./philosophers 4 410 200 200

# Edge case: 1 philosopher (will die)
./philosophers 1 800 200 200

Expected Behavior

Success Case (No Deaths)

./philosophers 5 800 200 200

Output should show philosophers continuously eating, sleeping, and thinking with no death messages.

Completion Case

./philosophers 5 800 200 200 7

Output ends with: All philosophers finished their meals

Death Case

./philosophers 4 310 200 100

One philosopher will die because time_to_die is too short.

Testing Guidelines

# Test 1: No philosopher should die
./philosophers 5 800 200 200

# Test 2: No philosopher should die
./philosophers 4 410 200 200

# Test 3: A philosopher should die
./philosophers 4 310 200 100

# Test 4: No philosopher should die, stop when all eat 7 times
./philosophers 5 800 200 200 7

# Test 5: No philosopher should die, stop when all eat 5 times
./philosophers 2 800 200 200 5

# Test 6: Edge case with 1 philosopher (should die)
./philosophers 1 800 200 200

# Test 7: Large number of philosophers
./philosophers 200 800 200 200

📊 Implementation Structure

The project follows a modular architecture:

• philosophers.c - Main program entry, initialization, and cleanup
• philosophers.h - Header with structures and function prototypes
• routine.c - Thread routines (philosopher and watchdog)
• schedule.c - Philosopher actions (eat, sleep, think)
• utils.c - Utility functions (timing, printing, parsing)
• checks.c - State checking functions (death, fullness, stop)
• init.c - Initialization functions (arguments, mutexes)

⚙️ Technical Details

• Language: C
• Compiler: gcc
• Flags: -Wall -Wextra -Werror -pthread
• Norm: 42 Norminette
• Threading: POSIX threads (pthreads)
• Synchronization: Mutexes
• Timing: gettimeofday() for millisecond precision

🎨 Color-Coded Output

The program uses ANSI color codes for better visualization:

• 🔵 Blue: Timestamps
• 🟡 Yellow: Philosopher IDs
• 🔴 Red: Death messages
• 🟢 Green: Completion messages

📝 Notes

• All functions follow 42 Norminette coding standards
• Memory is properly managed with no leaks
• No data races
• No deadlocks occur in correct usage scenarios
• Timestamps are accurate to within 10ms
• The program handles edge cases (1 philosopher, large numbers)
• Mutexes are properly initialized and destroyed
• Threads are properly joined before cleanup

👤 Author

opopov