Skip to content

README.md

Latest commit

 

History

History
199 lines (152 loc) · 6.94 KB

README.md

File metadata and controls

199 lines (152 loc) · 6.94 KB

Philosophers 🍽️

A C implementation of the classic Dining Philosophers Problem using POSIX threads. This project demonstrates thread synchronization, mutex usage, and deadlock prevention in concurrent programming.

Problem Overview

The Dining Philosophers Problem is a classic synchronization problem used to illustrate challenges in concurrent programming:

  • N philosophers sit around a circular table
  • N forks are placed between each pair of adjacent philosophers (one fork between two philosophers)
  • Each philosopher alternates between thinking and eating
  • A philosopher needs both forks (left and right) to eat
  • When done eating, forks are released and other philosophers can use them

The challenge is to create a solution where all philosophers can eat without deadlock or starvation.

Key Features

✅ Multi-threaded Architecture — Each philosopher runs as a separate thread
✅ Mutex-based Synchronization — Fork access controlled with pthread mutexes
✅ Deadlock Prevention — Safe fork acquisition ordering
✅ Death Monitoring — Background thread monitors philosopher survival
✅ Thread-safe Logging — Synchronized output prevents race conditions
✅ Configurable Simulation — Customize number of philosophers and timings via CLI

Requirements

  • OS: Linux/macOS/Unix
  • C Compiler: GCC or Clang
  • POSIX Threads: pthread library (included on most Unix-like systems)
  • Make: Standard make utility

Compilation

make              # Compile the project
make clean        # Remove object files
make fclean       # Remove all generated files
make re           # Rebuild from scratch

Usage

./philo <number_of_philosophers> <time_to_die> <time_to_eat> <time_to_sleep> [number_of_times_each_philosopher_must_eat]

Arguments

Argument Description
number_of_philosophers Number of philosophers and forks (must be > 0)
time_to_die Time (in ms) a philosopher can survive without eating
time_to_eat Time (in ms) it takes to eat
time_to_sleep Time (in ms) a philosopher sleeps after eating
number_of_times_each_philosopher_must_eat (Optional) Simulation ends when all philosophers have eaten this many times

Example Runs

# 5 philosophers, max 800ms before death, 200ms to eat, 200ms to sleep
./philo 5 800 200 200

# Same as above, each philosopher must eat at least 7 times
./philo 5 800 200 200 7

# Edge case: single philosopher (will always die)
./philo 1 800 200 200

Output Format

<timestamp> <philosopher_id> <action>

Actions:

  • has taken a fork — Philosopher picked up a fork
  • is eating — Philosopher is eating (has both forks)
  • is sleeping — Philosopher is sleeping
  • is thinking — Philosopher is thinking
  • died — Philosopher died from starvation

Example output:

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

Implementation Details

Thread Synchronization

  • pthread_mutex_t protects shared resources:

    • forks — Array of mutexes representing table forks
    • print_lock — Ensures atomic print operations
    • stop_prog — Protects the death flag
    • meal_lock — Protects philosopher meal count

  • Fork Allocation: Philosopher i uses forks i and (i+1) % n

  • Monitor Thread: Background thread checks if any philosopher exceeded time_to_die since last meal

Key Functions

Function Purpose
routine() Main philosopher behavior loop (eating, sleeping, thinking)
monitor_dead() Background thread checking for philosopher deaths
take_start_left_fork() Acquire left fork with proper timing
take_start_right_fork() Acquire right fork with proper timing
print_action() Thread-safe logging of philosopher actions

Project Structure

.
├── Makefile                 # Build configuration
├── philo.h                  # Header with struct definitions and prototypes
├── README.md                # This file
└── src/
    ├── main.c               # Entry point and thread creation
    ├── routine.c            # Philosopher behavior loop
    ├── monitor_dead.c       # Death detection system
    ├── init.c               # Data structure initialization
    ├── validate_data.c      # Input validation
    ├── ft_atoi.c            # String to integer conversion
    ├── get_time_in_ms.c     # Millisecond timestamp utility
    └── utils_routine.c      # Helper functions for philosopher routine

Technical Highlights

🔒 Thread Safety

  • Proper mutex initialization and cleanup
  • Prevents race conditions on shared variables
  • Synchronized access to fork resources

⏱️ Precise Timing

  • Millisecond-precision timestamps
  • Accurate death detection
  • Proper sleep mechanisms for philosophers

🎯 Robust Design

  • Input validation for all command-line arguments
  • Graceful error handling
  • Resource cleanup on exit

Data Structures

typedef struct philo {
    int           id;              // Philosopher ID
    int           count_meals;     // Meals eaten so far
    long long     last_meal;       // Timestamp of last meal
    pthread_t     thread;          // Thread ID
    pthread_mutex_t *left_fork;    // Reference to left fork
    pthread_mutex_t *right_fork;   // Reference to right fork
    pthread_mutex_t meal_lock;     // Protects meal count
    struct s_data *data;           // Global data reference
} t_philo;

typedef struct s_data {
    int           num_philo;       // Number of philosophers
    int           time_to_die;     // Max ms without eating
    int           time_to_sleep;   // Sleep duration
    int           time_to_eat;     // Eating duration
    int           died;            // Death flag
    int           must_eat;        // Meals required to finish (-1 if unlimited)
    long long     start_time;      // Simulation start time
    pthread_mutex_t *forks;        // Array of fork mutexes
    pthread_mutex_t print_lock;    // Protects stdout
    pthread_mutex_t stop_prog;     // Protects death flag
    t_philo       *philos;         // Array of philosophers
} t_data;

Notes

⚠️ Single Philosopher: A philosopher alone will always die because they cannot pick up both forks.

⚠️ Timing Precision: Results may vary slightly based on system load. The time_to_die should be reasonably larger than time_to_eat to reach a stable state.

✅ Testing: Try configurable numbers of philosophers to observe different synchronization patterns:

  • Small numbers (2-3): Observe fork contention
  • Medium numbers (5-10): Observe typical behavior
  • Large numbers (100+): Observe system resource usage

Author

mkhavari
Created: May 2025

This project is part of the 42 School curriculum (Rank 03), demonstrating proficiency in concurrent programming with C and POSIX threads.