philo

A highly optimized solution to the classic Dining Philosophers concurrency problem, demonstrating advanced multithreading techniques in C using POSIX threads.

Overview

The Dining Philosophers problem is a classic synchronization challenge in computer science: N philosophers sit at a round table with N forks. Each philosopher alternates between thinking, eating, and sleeping. To eat, a philosopher must acquire both the fork to their left and right. The challenge is preventing deadlock and starvation while maximizing concurrency.

         [P1]
        /    \
     (F1)    (F2)
      /        \
   [P5]        [P2]
     |          |
   (F5)        (F3)
     \          /
   [P4]------[P3]
        (F4)

Algorithm

Deadlock Prevention

The implementation uses a resource hierarchy approach to prevent deadlock:

• Even-numbered philosophers acquire their left fork first, then right
• Odd-numbered philosophers acquire their right fork first, then left

This asymmetric ordering breaks the circular wait condition that would otherwise cause deadlock.

Starvation Prevention

Multiple mechanisms prevent any philosopher from starving:

1. Initial staggered start: Odd philosophers delay slightly before their first meal, reducing initial contention
2. Additional yield for even philosophers: When the total count is odd, even philosophers yield briefly after eating to balance opportunities
3. Continuous death monitoring: A dedicated monitor thread checks each philosopher's time since last meal

Architecture

┌─────────────────────────────────────────────────────────────────┐
│                         Main Thread                             │
│  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐              │
│  │   Parse     │─▶│   Init      │─▶│   Create    │              │
│  │   Args      │  │   Mutexes   │  │   Threads   │              │
│  └─────────────┘  └─────────────┘  └─────────────┘              │
└─────────────────────────────────────────────────────────────────┘
                              │
              ┌───────────────┼───────────────┐
              ▼               ▼               ▼
┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐
│  Philosopher    │ │     Monitor     │ │    Overseer     │
│   Threads (N)   │ │     Thread      │ │    Thread       │
├─────────────────┤ ├─────────────────┤ ├─────────────────┤
│ • Think         │ │ • Check death   │ │ • Count meals   │
│ • Acquire forks │ │ • Signal stop   │ │ • Signal done   │
│ • Eat           │ │                 │ │   when target   │
│ • Release forks │ │                 │ │   reached       │
│ • Sleep         │ │                 │ │                 │
└─────────────────┘ └─────────────────┘ └─────────────────┘

Synchronization Primitives

Mutex	Purpose
forks[N]	One mutex per fork to ensure exclusive access
write_lock	Serializes output to prevent interleaved messages
donezo_mutex	Protects the global termination flag
meal_eaten_mutex	Per-philosopher mutex for meal counting
meal_time_check_mutex	Per-philosopher mutex for starvation detection

Building

make        # Compile with optimizations
make clean  # Remove object files
make fclean # Remove all build artifacts
make re     # Rebuild from scratch

Usage

./philo <num_philosophers> <time_to_die> <time_to_eat> <time_to_sleep> [meals_required]

Parameters

Parameter	Description	Constraints
num_philosophers	Number of philosophers (and forks)	1-255
time_to_die	Milliseconds until death without eating	>= 60
time_to_eat	Milliseconds to eat (holds both forks)	>= 60
time_to_sleep	Milliseconds to sleep after eating	>= 60
meals_required	Optional: simulation ends when all philosophers eat this many times	Optional

Examples

# 5 philosophers, challenging timing (will eventually die)
./philo 5 800 200 200

# 4 philosophers, comfortable timing (runs indefinitely)
./philo 4 410 200 200

# 5 philosophers, each must eat 7 times then simulation ends
./philo 5 800 200 200 7

# Single philosopher (cannot eat, will die)
./philo 1 800 200 200

# Stress test with many philosophers
./philo 200 800 200 200

Output Format

timestamp_ms philosopher_id action

Actions:

• has taken a fork - Acquired a fork
• is eating - Currently eating (holding both forks)
• is sleeping - Currently sleeping
• is thinking - Currently thinking
• died - Philosopher starved (simulation ends)

Implementation Details

Performance Optimizations

• Inline functions: Critical path functions use __attribute__((__always_inline__)) for zero-overhead calls
• Hot path marking: Thread routines marked with __attribute__((hot)) for aggressive optimization
• Busy-wait with microsleep: Uses usleep(100) in timing loops to reduce CPU usage while maintaining precision
• Stack allocation: Philosopher array allocated on stack (up to 255) to avoid heap allocation overhead

Thread Safety

• All shared state protected by appropriate mutexes
• Lock ordering prevents deadlocks in mutex acquisition
• Atomic-like operations through mutex-protected read-modify-write sequences

Edge Cases

• Single philosopher: Special handling - cannot eat (needs two forks), will inevitably die
• Odd philosopher count: Extra yield inserted to balance eating opportunities
• Zero meals required: Philosophers exit immediately without eating

License

This project is licensed under the MIT License - see the LICENSE file for details.