Dining Philosopher Problem Explained

The Dining Philosopher Problem is a classic synchronization problem that has intrigued computer scientists and engineers for decades. Originally formulated by Edsger Dijkstra in 1965, it is a quintessential illustration of the challenges associated with resource sharing and process synchronization in concurrent computing.

In this article, we delve into my implementation of the Dining Philosopher Problem, crafted as part of the rigorous curriculum at 42 coding school. The project serves as a practical application of theoretical concepts, focusing on the complexities of thread management and inter-process communication.
The mandatory part of the project emphasizes the use of threads to manage the concurrent activities of the philosophers. Each philosopher, representing a thread, must navigate the challenges of picking up and putting down forks (shared resources) in a way that avoids deadlock and ensures all philosophers can dine without conflict.

Building on the foundational implementation, the bonus section of the project transitions from threads to processes. This shift introduces a new layer of complexity, as processes require more sophisticated techniques for communication and synchronization due to their isolated memory spaces.

Mandatory Part

In this part of the project, the process begins by parsing the input from the user. Once the input has been successfully parsed, we proceed to create the philosophers. This is achieved by creating threads, each representing a philosopher, and passing the address of the corresponding data to each thread.

Parsing and creating philos:

int    _validate_args(int ac, char **av, t_data *dt)
{
    dt->nbr = ft_atoi(av[1]);
    dt->time2die = ft_atoi(av[2]);
    dt->time2eat = ft_atoi(av[3]);
    dt->time2sleep = ft_atoi(av[4]);
    dt->death = false;
    dt->start = ft_time();
    dt->ends = 0;
    dt->x = 0;
    if (ac == 6)
        dt->nbr2eat = ft_atoi(av[5]);
    else
        dt->nbr2eat = -1;
    if (dt->nbr <= 0 || dt->nbr2eat == 0 || dt->nbr > 200 || dt->time2die < 60
        || dt->time2eat < 60 || dt->time2sleep < 60)
        return (printf("Error: wrong arguments\n"), 0);
    return (1);
}

void    setphilo_data(t_philo *philo, t_fork *forks, t_data *data)
{
    int    i;

    i = 0;
    while (i < data->nbr)
    {
        philo[i].id = i + 1;
        philo[i].left = &forks[i];
        if (i == (data->nbr - 1))
            philo[i].right = &forks[0];
        else
            philo[i].right = &forks[(i + 1) % data->nbr];
        philo[i].data = data;
        pthread_mutex_init(&philo[i].stime, NULL);
        philo[i].last_meal = ft_time();
        philo[i].start = data->start;
        philo[i].eat = data->nbr2eat;
        philo[i].end = 0;
        i++;
    }
}

int    _create_tr(pthread_t *threads, t_philo *philo)
{
    int    i;

    i = 0;
    while (i < philo->data->nbr)
    {
        if (pthread_create(&threads[i], NULL, _routine, &philo[i]) != 0)
            return (0);
        i++;
    }
    return (1);
}

int    _init_mutexes(t_fork *forks, t_data *data)
{
    int    i;

    i = 0;
    while (i < data->nbr)
    {
        forks[i].id = i;
        if (pthread_mutex_init(&forks[i].mutex, NULL) < 0)
            return (0);
        i++;
    }
    return (1);
}

Philosopher Routine

The _routine function is central to each philosopher's behavior in the simulation, managing the states and actions of each philosopher thread. Here's a breakdown of the critical components of the function and its helper functions:

Unlock Forks Function

The _unlock_forks function ensures that both forks (represented by mutexes) are released when a philosopher finishes eating or encounters an error. This helps prevent deadlock and ensures other philosophers can access the forks.

Update Lock Function

The update_lock function is responsible for safely updating the philosopher's last meal time. It locks the necessary mutexes, updates the meal time, and then unlocks the mutexes. This ensures that the shared state is modified safely without race conditions.

Handler Function

The __handler function controls the philosopher's main actions within a loop:

Thinking: The philosopher first thinks, represented by checking and printing the 'T' status.
Taking Forks: The philosopher tries to take the left fork and then the right fork, printing the 'F' status for each. If they successfully acquire both forks, they proceed to eat.
Eating: After locking the forks, the philosopher updates their last meal time and prints the 'E' status. They then eat for a specified duration.
Sleeping: After eating, the philosopher releases both forks and sleeps, printing the 'S' status.

The handler also includes error checking to ensure proper resource management and exits early if necessary, unlocking forks and returning NULL.

Routine Function

The _routine function initializes each philosopher's behavior:

Alternating Start: Philosophers with even IDs start by sleeping to stagger their actions, reducing the likelihood of simultaneous fork acquisition and potential deadlock.
Main Loop: After the initial sleep (if applicable), the philosopher enters the main handler loop to perform their actions repeatedly until the simulation ends or a termination condition is met.

Key Points

Philosopher Actions: Each philosopher cycles through thinking, taking forks, eating, and sleeping states.
Synchronization: Mutexes manage access to shared resources (forks and shared time data), ensuring safe and orderly execution.
Error Handling: The functions are designed to return early in case of errors, ensuring resources are properly unlocked and avoiding deadlock.
Alternating Start: Philosophers with even IDs start by sleeping, which helps prevent deadlock by reducing the chance of simultaneous fork acquisition.

This structured approach ensures that each philosopher can perform their actions without interference, demonstrating effective synchronization and resource management in a concurrent system.

#include "../philo.h"

static void    _unlock_forks(pthread_mutex_t *left, pthread_mutex_t *right)
{
    pthread_mutex_unlock(left);
    pthread_mutex_unlock(right);
}

static void    update_lock(t_philo *philo)
{
    pthread_mutex_lock(&philo->right->mutex);
    pthread_mutex_lock(&philo->stime);
    philo->last_meal = ft_time();
    pthread_mutex_unlock(&philo->stime);
}

static void    *__handler(t_philo *philo, int *i)
{
    while (!is_death(philo->data))
    {
        if (print_status(philo, 'T'))
            return (NULL);
        pthread_mutex_lock(&philo->left->mutex);
        if (print_status(philo, 'F'))
            return (pthread_mutex_unlock(&philo->stime), NULL);
        update_lock(philo);
        if (print_status(philo, 'F'))
            return (_unlock_forks(&philo->left->mutex, &philo->right->mutex),
                NULL);
        if (print_status(philo, 'E'))
            return (_unlock_forks(&philo->left->mutex, &philo->right->mutex),
                NULL);
        if (!ft_sleep(philo->data->time2eat, philo->data))
            return (_unlock_forks(&philo->left->mutex, &philo->right->mutex),
                NULL);
        _unlock_forks(&philo->left->mutex, &philo->right->mutex);
        if (print_status(philo, 'S'))
            return (0);
        ft_sleep(philo->data->time2sleep, philo->data);
        if (is_end_simulation(philo, i, &philo->eat))
            break ;
    }
    return (NULL);
}

void    *_routine(void *arg)
{
    t_philo    *philo;
    int        i;

    i = 0;
    philo = (t_philo *)arg;
    if (philo->id % 2 == 0)
    {
        if (print_status(philo, 'S'))
            return (NULL);
        if (!ft_sleep(philo->data->time2sleep, philo->data))
            return (NULL);
    }
    __handler(philo, &i);
    return (NULL);
}

Monitor (main thread)

This one is the thread who check if any philo has die or not, I have handed it with _checkloop function.

The _checkingloop function is responsible for continuously monitoring the state of each philosopher to determine if any philosopher has died during the simulation. Here's a detailed breakdown of how this function works:

Iteration Through Philosophers: The function iterates through all philosophers using the i index.
Philosopher Status Check: For each philosopher, it first checks if the philosopher has completed their required number of meals using the _ckeckphilo_end function. If the philosopher has not yet finished:
Last Meal Time Check:
- It locks the stime mutex of the philosopher to safely access the last_meal time.
- It calculates the time elapsed since the philosopher's last meal using ft_time() - philos[*i].last_meal.
Death Condition: If the elapsed time is greater than or equal to the time2die threshold:
- It locks the print mutex to print a message indicating the philosopher's death.
- The set_death function is called to update the shared data structure, marking that a death has occurred.
- It prints the death message, including the time passed since the start of the simulation and the philosopher's ID.
- It then unlocks both the stime and print mutexes.
- The data->x flag is set to 1 to indicate that a philosopher has died, and the loop breaks to end the monitoring.

Unlock Mutex: If the philosopher has not died, the function simply unlocks the stime mutex and moves to the next philosopher.

 static void    _checkingloop(int *i, t_data *data, t_philo *philos)
 {
     while (*i < data->nbr)
     {
         if (!_ckeckphilo_end(&philos[*i]))
         {
             pthread_mutex_lock(&philos[*i].stime);
             if ((ft_time() - philos[*i].last_meal) >= (uint64_t)data->time2die)
             {
                 pthread_mutex_lock(&data->print);
                 set_death(data);
                 printf("\033[0;91m%zu %d died\033[0m\n",
                     ft_time_passed(philos[*i].start), philos[*i].id);
                 pthread_mutex_unlock(&philos[*i].stime);
                 pthread_mutex_unlock(&data->print);
                 data->x = 1;
                 break ;
             }
             pthread_mutex_unlock(&philos[*i].stime);
         }
         (*i)++;
     }
 }

 // ...
 void    _handler(t_data *data)
 {
     pthread_t    *threads;
     t_philo        *philos;
     t_fork        *forks;
     int            i;

     if (!_alloc(data, &threads, &philos, &forks))
         return ;
     while (!data->x && !check_end(data))
     {
         i = 0;
         _checkingloop(&i, data, philos);
     }
     _cleanup(data, philos, forks, threads);
 }

https://github.com/flutterde/philosophers

The Dining Philosopher Problem

Table of contents