Skip to content

README.md

Latest commit

 

History

History
217 lines (168 loc) · 6.3 KB

README.md

File metadata and controls

217 lines (168 loc) · 6.3 KB

🍽️ Philosophers

A solution to the classic Dining Philosophers Problem using threads and mutexes in C.

📖 Project Overview

The Dining Philosophers problem is a classic synchronization problem in computer science. It illustrates the challenges of avoiding deadlock and resource contention in concurrent programming.

The Problem

  • N philosophers sit around a circular table
  • Each philosopher alternates between eating, sleeping, and thinking
  • There is one fork between each pair of adjacent philosophers
  • A philosopher needs two forks (left and right) to eat
  • Philosophers cannot communicate with each other
  • The simulation stops when a philosopher dies of starvation

🚀 Features

  • Multi-threading: Each philosopher runs in its own thread
  • Mutex protection: Prevents race conditions and data corruption
  • Deadlock prevention: Smart fork acquisition strategy
  • Death monitoring: Separate monitor thread checks for philosopher deaths
  • Precise timing: Microsecond-level timing accuracy
  • Memory safety: Proper cleanup and error handling

🛠️ Installation

# Clone the repository
git clone [your-repo-url]
cd philosophers

# Compile the project
make

# Clean object files
make clean

# Remove all generated files
make fclean

# Recompile everything
make re

💻 Usage

./philo number_of_philosophers time_to_die time_to_eat time_to_sleep [number_of_times_each_philosopher_must_eat]

Parameters

Parameter Description Required
number_of_philosophers Number of philosophers (1-200) ✅
time_to_die Time in ms before a philosopher dies of starvation ✅
time_to_eat Time in ms a philosopher takes to eat ✅
time_to_sleep Time in ms a philosopher sleeps ✅
number_of_times_each_philosopher_must_eat Optional: simulation stops when all philosophers eat this many times ❌

Examples

# Basic simulation - 4 philosophers
./philo 4 410 200 200

# With meal limit - stops when each philosopher eats 5 times
./philo 5 800 200 200 5

# Edge case - single philosopher (should die)
./philo 1 800 200 200

# Stress test - many philosophers
./philo 100 410 200 200

📋 Output Format

The program outputs timestamped messages for each philosopher action:

[timestamp_ms] philosopher_id has taken a fork
[timestamp_ms] philosopher_id is eating
[timestamp_ms] philosopher_id is sleeping
[timestamp_ms] philosopher_id is thinking
[timestamp_ms] philosopher_id died

Example Output

0 1 has taken a fork
0 1 has taken a fork
0 1 is eating
0 3 has taken a fork
0 3 has taken a fork
0 3 is eating
200 1 is sleeping
200 3 is sleeping
200 2 has taken a fork
200 4 has taken a fork
...

🏗️ Project Structure

philosophers/
├── Makefile
├── README.md
├── includes/
│   └── philo.h              # Header file with structures and prototypes
└── srcs/
    ├── main.c               # Program entry point and initialization
    ├── parsing.c            # Input validation and parsing
    ├── routine.c            # Philosopher behavior and lifecycle
    ├── monitor.c            # Death monitoring and simulation control
    ├── utils.c              # Utility functions (time, printing, etc.)
    └── cleanup.c            # Memory cleanup and resource management

🧠 Algorithm Overview

Philosopher Lifecycle

  1. Think - Philosopher contemplates life
  2. Acquire Forks - Takes left fork, then right fork
  3. Eat - Consumes food for specified duration
  4. Release Forks - Puts down both forks
  5. Sleep - Rests for specified duration
  6. Repeat - Goes back to thinking

Deadlock Prevention

  • Odd/Even Strategy: Odd-numbered philosophers pick up left fork first, even-numbered pick up right fork first
  • Resource Ordering: Prevents circular wait conditions
  • Timeout Mechanism: Philosophers release forks if they can't acquire both

Monitoring System

  • Separate Monitor Thread: Continuously checks philosopher states
  • Death Detection: Identifies when a philosopher hasn't eaten within time_to_die
  • Meal Counting: Tracks when all philosophers have eaten enough times
  • Clean Termination: Safely stops all threads when simulation ends

Thread Safety

  • Mutexes: Protect shared resources and critical sections
  • Atomic Operations: Ensure data consistency across threads
  • Proper Synchronization: Prevents race conditions and data corruption

🧪 Testing

Test Cases

# Should not die
./philo 5 800 200 200
./philo 4 410 200 200

# Should die quickly  
./philo 1 800 200 200
./philo 4 310 200 200

# With meal limits
./philo 5 800 200 200 7
./philo 4 410 200 200 10

# Edge cases
./philo 2 400 200 200    # Minimum viable setup
./philo 200 800 200 200  # Stress test

Expected Behaviors

  • ✅ No philosopher should die in a properly configured simulation
  • ✅ Death should be reported within 10ms of occurrence
  • ✅ No race conditions or data corruption
  • ✅ Clean program termination
  • ✅ Proper resource cleanup

🐛 Common Issues & Debugging

Death Detection Issues

  • Check timing precision: Ensure microsecond-level accuracy
  • Monitor frequency: Monitor thread should check frequently enough
  • Mutex deadlocks: Verify proper mutex acquisition order

Performance Issues

  • Too many philosophers: Reduce count for better performance
  • System limits: Check pthread limits on your system
  • Memory usage: Monitor for memory leaks

Compilation Issues

# If you get pthread errors:
gcc -pthread ...

# For debugging:
gcc -g -fsanitize=thread ...

📚 Learning Objectives

This project teaches:

  • Multi-threading concepts and implementation
  • Mutex usage and synchronization
  • Race condition prevention
  • Deadlock avoidance strategies
  • Resource management in concurrent programs
  • Precise timing and performance optimization

🤝 Contributing

  1. Fork the repository
  2. Create a feature branch (git checkout -b feature/amazing-feature)
  3. Commit your changes (git commit -m 'Add amazing feature')
  4. Push to the branch (git push origin feature/amazing-feature)
  5. Open a Pull Request

📄 License

This project is part of the 42 School curriculum.