Skip to content

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Repository files navigation

philosophers — Concurrent Dining Problem

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.

Problem Statement

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.

Features

Core Synchronization

  • 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

Program Behavior

  • 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

Concurrency Features

  • 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

Architecture

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

Build & Run

make                          # Compile
./philo 5 800 200 200        # Run with parameters
make clean                    # Remove .o files
make fclean                   # Remove all build artifacts
make re                       # Rebuild

Parameters

  1. num_of_philosophers — Number of philosophers (and forks)
  2. time_to_die — Milliseconds until philosopher dies from starvation
  3. time_to_eat — Milliseconds to eat (holding forks)
  4. time_to_sleep — Milliseconds to sleep after eating

Example Usage

$ ./philo 5 800 200 200
0ms: Philosopher 1 is eating
0ms: Philosopher 2 is sleeping
2ms: Philosopher 3 is thinking
...

Technical Highlights

Deadlock Prevention

  • 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

Race Condition Prevention

  • Atomic Operations: All state updates protected by mutexes
  • Consistent Timestamp Recording: Centralized time reference
  • Safe Thread Termination: Proper synchronization on exit

Memory Management

  • No Leaks: All dynamically allocated memory freed
  • Resource Cleanup: Proper mutex destruction
  • Clean Exit: All threads successfully joined

Key Implementation Details

State Management

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;
    // ...
};

Philosopher Routine

  1. Think (random duration)
  2. Pick up left fork (mutex_lock)
  3. Pick up right fork (mutex_lock)
  4. Eat for time_to_eat milliseconds
  5. Put down both forks (mutex_unlock)
  6. Sleep for time_to_sleep milliseconds
  7. Repeat

Requirements

  • GCC/Clang compiler
  • Linux/Unix environment with POSIX threads
  • pthread.h library
  • gettimeofday() for timing

Limitations & Future Work

  • 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)

Project Stats

  • 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+)

Testing Scenarios

  1. Balanced Case (N=5, die=800, eat=200, sleep=200)

    • All philosophers should eat regularly without deadlock
  2. Stressful Case (N=4, die=410, eat=200, sleep=200)

    • Tests timing precision and deadlock prevention
  3. Single Philosopher (N=1, die=800, eat=200, sleep=200)

    • Should die after 800ms (cannot get 2 forks)
  4. Many Philosophers (N=200, die=1000, eat=100, sleep=100)

    • Tests system scalability and synchronization efficiency

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages