having dinner with the philosophers

The Dining Philosophers problem is a classic problem in Computer Science that in order to be solved, it requires an algorithm design with multi-threading and precise synchronization. And for my next project at 42, I'll solve it coding in C.

I knew it was going to be a challenge.

I already had some knowledge of multi-threading. Thanks to Rayan Slim's Java Multithreading course. By the way, Rayan's courses are always the best, he is very straightforward, I admire a lot his teaching methodology, and his courses also have a support group on Discord.

But I knew that multi-threading in C had to be different than in Java, because in Java we can use any object as a lock, using a synchronized block. In C we would have to use mutex and I had never heard of it before.

The Dining Philosophers problem

So let me introduce the problem:

• We have a n number of philosophers sitting on a table.
• There are as many forks as philosophers.

To eat this kind of spaghetti, they need two forks, one on each hand. So they can't be eating all at the same time: there aren't enough forks for all of them to do that.

There are also some other important factors:

• time_to_eat That's the time a philosopher spends eating.
• time_to_die If a philosopher doesn't eat for this amount of time, it will starve to death. So we have to synchronize all the philosophers to avoid having a death.
• time_to_sleep After eating, a philosopher has to put both forks on the table and start sleeping for this amount of time.

The philosophers alternate between the states of eating, sleeping, or thinking.

When a philosopher dies, a message announcing his death should be displayed no more than 10 ms after the actual death of the philosopher.

Possible problems

When dealing with multi-threads, there are two main problems we have to deal with: data races and deadlocks.

A data race occurs when multiple threads share the same resource. So, having a variable that can be accessed and modified by other threads can lead to a problem when a thread is modifying the value of the variable at the same time that another thread tries to read it. This leads to undefined or unpredictable behavior in the program.

To avoid the data race in C, we can use a mutex, which is a way of locking certain parts of your code. We need to lock every time a thread is going to modify or access the value of a shared variable and unlock it when the changes are done. If during this time another thread tries to access this variable, it will pause on the lock and only continue after the other thread has unlocked it.

But of course, this can lead to another problem: deadlocks.

A deadlock happens when two or more threads are locked forever, waiting for each other. This can happen in our Dining Philosophers problem if all the philosophers grab one fork. They will be locked forever waiting for another fork to be available (because they need two forks to eat) and will eventually die from starvation. That's why all of our philosophers must be well synchronized.

My implementation

In my implementation of the dining philosophers, each philosopher is a thread, and we have a central thread that I call maestro to constantly check if a philosopher is dead or if they've all eaten a certain number of times.

Here are the two structures I used in my program:

typedef struct s_table
{
	int				philo_num;
	int				time_starve;
	int				time_eat;
	int				time_sleep;
	int				eat_num;
	int				stop;
	long int		start_time;
	pthread_t		*thread;
	pthread_mutex_t	*stop_lock;
	pthread_mutex_t	*print_lock;
	pthread_mutex_t	**forks;
}				t_table;

typedef struct s_philo
{
	int				id;
	int				l_fork;
	int				r_fork;
	int				is_eating;
	int				eat_counter;
	long int		last_meal;
	pthread_t		*thread;
	pthread_mutex_t	*eat_lock;
	t_table			*table;
}				t_philo;

I made each fork a mutex, and in our t_table we have an array with all the forks, and each t_philo has the index of his left fork and right fork.

With the function gettimeofday() we save the time of the last meal on the variable last_meal.

And we have other important mutexes like eat_lock, stop_lock and print_lock. To change the variables related to eating, variables that indicate the stop of the program, and also each time I print something, I use the print_lock, this way the print messages will never get mixed up and we won't have extra messages being printed after the death of a philosopher or the stop of the program.

Also, I thought it was very important to not have an array of t_philo, this way it's impossible for a philosopher to communicate with each other. They simply have no access to each other.

You can check my code on this GitHub repository:

GitHub - marcioflaviob/philosophers_42

Contribute to marcioflaviob/philosophers_42 development by creating an account on GitHub.

GitHubmarcioflaviob