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 thelast_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
andprint
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); }