During 2021 and 2022 I attended the 42 Lisboa coding school. 42 follows a learning by doing and peer-to-peer learning methodology: the syllabus consists of a series of challenges, and you must learn what it takes to solve them. One of them was the dinning philosophers problem.
Quoting Wikipedia, “in computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them”. N philosophers sit at the dining table for eating spaghetti; there is a plate in front of each philosopher and a fork in between. These philosophers haven’t yet mastered the Italian art of eating spaghetti, thus they can only eat when both forks on their right and left side are free for them to use (and obviously, two philosophers cannot share a fork at the same time). The philosophers then alternate between eating, sleeping, and thinking (it is their profession, after all). If the period a philosopher remains without eating exceeds a certain amount of time, this philosopher dies of hunger. The purpose of this project was to build a simulation which, given the number of philosophers and the amount of time they take eating and sleeping, determines if it is possible for all the philosophers to coexist happily or if one or more are destined to starvation.
One of the challenges is to prevent deadlocks, meaning a system state in which no progress is possible. An extreme example of a deadlock would be if each philosopher picks a fork and remains waiting for the second one to be free, in which case they would all eventually starve (one can also deduce from this example that philosophers get stuck in their own thoughts too easily, to the point of being unable to communicate with each other and reach an agreement). To avoid this situation, I simply check that both forks are free before locking both. Another challenge appears when there's an odd number of philosophers. In this situation, we need to make sure the one who didn't eat the longest manages to grab the forks instead of another one. Imagine the following: there are 5 philosophers; 1 and 3 eat; 2 and 4 eat; 5 and either 1 or 3 should start eating now, but instead 1 and 3 start eating again and 5 starves. In order to avoid this, a small mandatory thinking time was added when the number of philosophers is odd. In this way, the ones who just finished sleeping and started thinking will be in disadvantage in comparison to those who are thinking the longest (and thus not eating the longest).
This project was coded in C, and was an introduction to threads, mutexes, deadlocks and race conditions. You can look at the code in this GitHub repository, and also see other projects from the 42 syllabus here.