A solution to the classic concurrent programming challenge using POSIX threads, mutexes, and semaphores. Demonstrates core systems programming concepts including thread synchronization, deadlock prevention, and race condition handling.
N philosophers sit at a round table with N forks. Each philosopher needs 2 forks (left and right) to eat. The challenge is to prevent deadlock, starvation, and implement proper synchronization so philosophers can eat, sleep, and think indefinitely.
Challenge: Implement a deadlock-free, starvation-free dining solution using only POSIX threads and synchronization primitives.
- Mutex-Based Locking: Each fork is protected by a mutex to prevent simultaneous access
- Deadlock Prevention: Asymmetric fork pickup (odd/even philosopher ordering)
- Starvation Prevention: Philosophers wait fairly for fork access
- Race Condition Safety: All shared resources are properly synchronized
- Philosopher States: eating → sleeping → thinking → (back to eating)
- State Logging: Timestamps and state transitions printed to stdout
- Death Detection: Monitors inactivity timeout and detects philosopher death
- Clean Termination: All threads joined and resources freed
- Thread Creation: POSIX
pthread_create()for each philosopher - Mutex Operations:
pthread_mutex_lock/unlock()for fork synchronization - Time Management: Microsecond precision with
gettimeofday() - Philosopher Monitoring: Single monitoring thread tracks philosopher states
Main Thread
↓
├─ Philosopher Thread 1
│ ├─ Fork (left)
│ ├─ Fork (right)
│ └─ routine()
├─ Philosopher Thread 2
│ └─ ...
└─ Philosopher Thread N
└─ ...
All forks protected by mutexes
All state changes logged with timestamps
make # Compile
./philo 5 800 200 200 # Run with parameters
make clean # Remove .o files
make fclean # Remove all build artifacts
make re # Rebuild- num_of_philosophers — Number of philosophers (and forks)
- time_to_die — Milliseconds until philosopher dies from starvation
- time_to_eat — Milliseconds to eat (holding forks)
- time_to_sleep — Milliseconds to sleep after eating
$ ./philo 5 800 200 200
0ms: Philosopher 1 is eating
0ms: Philosopher 2 is sleeping
2ms: Philosopher 3 is thinking
...- Asymmetric Fork Pickup: Even philosophers pick left fork first, odd philosophers pick right fork first
- Timeout Monitoring: Ensures no philosopher waits indefinitely
- No Circular Wait: Resource ordering prevents circular dependencies
- Atomic Operations: All state updates protected by mutexes
- Consistent Timestamp Recording: Centralized time reference
- Safe Thread Termination: Proper synchronization on exit
- No Leaks: All dynamically allocated memory freed
- Resource Cleanup: Proper mutex destruction
- Clean Exit: All threads successfully joined
struct s_philo {
int id;
int meals_eaten;
long last_meal_time;
pthread_t thread;
pthread_mutex_t *left_fork;
pthread_mutex_t *right_fork;
// ...
};- Think (random duration)
- Pick up left fork (mutex_lock)
- Pick up right fork (mutex_lock)
- Eat for time_to_eat milliseconds
- Put down both forks (mutex_unlock)
- Sleep for time_to_sleep milliseconds
- Repeat
- GCC/Clang compiler
- Linux/Unix environment with POSIX threads
pthread.hlibrarygettimeofday()for timing
- No support for semaphores in this version (see bonus)
- No priority-based fork allocation
- Single monitoring thread (could use condition variables for efficiency)
- Fixed thread count at runtime (no dynamic philosopher addition/removal)
- Lines of Code: ~400 (core logic)
- Number of Commits: 10+ logical phases
- Build Time: < 1 second
- Memory Leaks: 0 (validated with Valgrind)
- Maximum Philosophers: Limited by system resources (typically 1000+)
-
Balanced Case (N=5, die=800, eat=200, sleep=200)
- All philosophers should eat regularly without deadlock
-
Stressful Case (N=4, die=410, eat=200, sleep=200)
- Tests timing precision and deadlock prevention
-
Single Philosopher (N=1, die=800, eat=200, sleep=200)
- Should die after 800ms (cannot get 2 forks)
-
Many Philosophers (N=200, die=1000, eat=100, sleep=100)
- Tests system scalability and synchronization efficiency