The Philosophers dinning problem, why my threads are getting race conditions?

Question

I'm trying to solve the Philosophers dinning problem in C. This is my code:

#ifndef PHILO_H
# define PHILO_H

# include <stdio.h>
# include <stdlib.h>
# include <pthread.h>
# include <unistd.h>
# include <sys/time.h>
# include <limits.h>

typedef struct s_philo {
    int             id;
    int             eats;
    int             max_eats;
    int             time_to_eat;
    int             time_to_sleep;
    int             time_to_die;
    struct timeval  last_meal_time;
    pthread_mutex_t *left_fork;
    pthread_mutex_t *right_fork;
    pthread_cond_t  *condition;
} t_philo;

void    validate_args(int argc);
int     init_philos(t_philo **philos, pthread_mutex_t **forks, char **argv, int max_eats);
int     init_threads(pthread_t **threads, pthread_t **death_threads, int n_philosophers);
long    get_elapsed_time(struct timeval *start);
long    get_ts_in_ms();
void    *dinning_handler(void *arg);
void    *death_monitor(void *arg);
void    print_red(char *msg, int id, long time);
void    print_blue(char *msg, int id, long time);
void    print_green(char *msg, int id, long time);
int     ft_atoi(const char *str);
void    exit_gracefully(t_philo *philos, pthread_mutex_t *forks);

#endif

//main.c

static void create_threads(
    pthread_t *threads, pthread_t *death_threads, \
    t_philo *philos, int n
)
{
    int i;

    i = 0;
    while (i < n)
    {
        pthread_create(&threads[i], NULL, dinning_handler, &philos[i]);
        pthread_create(&death_threads[i], NULL, death_monitor, &philos[i]);
        i++;
    }
    return ;
}

static void join_threads(pthread_t *threads, int n)
{
    int i;

    i = 0;
    while (i < n)
    {
        pthread_join(threads[i], NULL);
        i++;
    }
    return ;
}

static void destroy_mutexes(pthread_mutex_t *forks, int n)
{
    int i;

    i = 0;
    while (i < n)
    {
        pthread_mutex_destroy(&forks[i]);
        i++;
    }
    return ;
}

static void free_resources(
    pthread_t *threads, pthread_t *death_threads, \
    pthread_mutex_t *forks, t_philo *philos
)
{
    free(philos);
    free(forks);
    free(threads);
    free(death_threads);
}

int main(int argc, char **argv)
{
    pthread_mutex_t *forks;
    pthread_t       *threads;
    pthread_t       *death_threads;
    t_philo         *philos;
    int             max_eats;

    validate_args(argc);
    max_eats = -1;
    if (argc > 5)
        max_eats = ft_atoi(argv[5]);
    forks = NULL;
    threads = NULL;
    death_threads = NULL;
    philos = NULL;
    if(!init_philos(&philos, &forks, argv, max_eats))
        exit(EXIT_FAILURE);
    if(!init_threads(&threads, &death_threads, ft_atoi(argv[1])))
        exit_gracefully(philos, forks);
    create_threads(threads, death_threads, philos, ft_atoi(argv[1]));
    join_threads(threads, ft_atoi(argv[1]));
    destroy_mutexes(forks, ft_atoi(argv[1]));
    free_resources(threads, death_threads, forks, philos);
    return (0);
}

//initialize.c

#include "philo.h"

static void fill_philos(
    char **argv, pthread_mutex_t **forks, \
    t_philo **philos, int max_eats
)
{
    int i;
    int n_philosophers;

    n_philosophers = ft_atoi(argv[1]);
    i = 0;
    while (i < n_philosophers)
    {
        pthread_mutex_init(&(*forks)[i], NULL);
        (*philos)[i].id = i + 1;
        (*philos)[i].eats = 0;
        (*philos)[i].time_to_eat = ft_atoi(argv[3]);
        (*philos)[i].time_to_sleep = ft_atoi(argv[4]);
        (*philos)[i].time_to_die = ft_atoi(argv[2]);
        (*philos)[i].max_eats = max_eats;
        (*philos)[i].left_fork = &(*forks)[i];
        (*philos)[i].right_fork = &(*forks)[(i + 1) % n_philosophers];
        i++;
    }
}

int init_philos(
    t_philo **philos, pthread_mutex_t **forks, \
    char **argv, int max_eats
)
{
    int n_philosophers;

    n_philosophers = ft_atoi(argv[1]);
    (*philos) = malloc(sizeof(t_philo) * n_philosophers);
    if (!(*philos))
    {
        printf("\033[0;31mError trying to create philosophers\033[0m");
        return (0);
    }
    (*forks) = malloc(sizeof(pthread_mutex_t) * n_philosophers);
    if (!(*forks))
    {
        printf("\033[0;31mError trying to create forks\033[0m");
        return (0);
    }
    fill_philos(argv, forks, philos, max_eats);
    return (1);
}

int init_threads(
    pthread_t **threads, pthread_t **death_threads,
    int n_philosophers
)
{
    (*threads) = malloc(sizeof(pthread_t) * n_philosophers);
    if (!(*threads))
    {
        printf("\033[0;31mError trying to create threads\033[0m");
        return (0);
    }
    (*death_threads) = malloc(sizeof(pthread_t) * n_philosophers);
    if (!(*death_threads))
    {
        printf("\033[0;31mError trying to create death threads\033[0m");
        return (0);
    }
    return (1);
}

In the main Just create and join the threads.

th_handler.c

void    *dinning_handler(void *arg)
{
    t_philo         *philo;
    struct timeval  start;

    philo = (t_philo *)arg;
    gettimeofday(&start, NULL);
    philo->last_meal_time = start;
    while (philo->max_eats == -1 || philo->eats < philo->max_eats)
    {
        print_blue("is thinking", philo->id, get_ts_in_ms());
        pthread_mutex_lock(philo->left_fork);
        pthread_mutex_lock(philo->right_fork);
        print_blue("has taken a fork", philo->id, get_ts_in_ms());
        print_green("is eating", philo->id, get_ts_in_ms());
        usleep(philo->time_to_eat * 1000);
        philo->eats++;
        gettimeofday(&philo->last_meal_time, NULL);
        pthread_mutex_unlock(philo->left_fork);
        pthread_mutex_unlock(philo->right_fork);
        print_blue("is sleeping", philo->id, get_ts_in_ms());
        usleep(philo->time_to_sleep * 1000);
    }
    return (NULL);
}

void    *death_monitor(void *arg)
{
    t_philo *philo;

    philo = (t_philo *)arg;
    while (1)
    {
        usleep(1000);
        if (get_elapsed_time(&philo->last_meal_time) > philo->time_to_die)
        {
            print_red("is dead", philo->id, get_ts_in_ms());
            exit(EXIT_FAILURE);
        }
    }
    return (NULL);
}

time_handler.c

long    get_elapsed_time(struct timeval *start)
{
    struct timeval  now;
    long            elapsed_time;

    gettimeofday(&now, NULL);
    elapsed_time = (now.tv_sec - start->tv_sec) * 1000 + (now.tv_usec - start->tv_usec) / 1000;
    return (elapsed_time);
}

long    get_ts_in_ms()
{
    struct timeval  time;

    gettimeofday(&time, NULL);
    return ((time.tv_sec * 1000) + (time.tv_usec / 1000));
}

When I test my code with the following:

number of philosophers = 4
philosopher time to die = 410ms
philosopher time to eat = 200ms
philosopher time to sleep = 200ms

No philosopher should die, but with my current code, one always die, example output:

501769404 1 is thinking
501769404 1 has taken a fork
501769404 1 is eating
501769404 2 is thinking
501769404 4 is thinking
501769404 3 is thinking
501769604 1 is sleeping
501769604 4 has taken a fork
501769604 4 is eating
501769807 1 is thinking
501769807 4 is sleeping
501769807 3 has taken a fork
501769807 3 is eating
501769815 2 is dead

Why this is happening? it is related to usleep x cpu actual time? how can I fix it?

Answer 1

I think I see where your code has a problem, but I don't want to tell you how to fix it, because figuring out for yourself how to fix it is the whole point of the Dining Philosopher's exercise.

The problem lies in how your philosophers pick up the forks.* Each philosopher unconditionally waits until they can pick up a fork with their left hand, and then they unconditionally wait until they can pick up a fork with their right hand. They will never put down a fork until 200ms after they have picked up both.

So, what happens when every fork is in a philosopher's left hand? Think about it!

In the traditional Dining Philosophers problem, you are forbidden to have the philosophers coordinate with each other through any other means except the forks. So, if you're going to use mutexes to represent the forks, a good starting point to solve the problem is to pick them up by calling pthread_mutex_trylock(...) instead of pthread_mutex_lock(...).

The simple "lock" function waits forever, but the "trylock" function can fail. When it fails—because the neighboring philosopher already is holding the fork that you want—then that's your opportunity to do something different to try to prevent the deadlock.

Good Luck!

---

*I'm starting a movement to call them "chopsticks" instead of "forks." Nobody ever eats with two forks, but if you're eating with chopsticks, then it makes sense that you can't eat until you have two of them.

Join the movement. Spread the word.