This project has been created as part of the 42 curriculum by vpogorel.
This project is about implementing a solution to the classic philosphers dining problem. We have a few philosophers sitting around a circular table. Between each pair of philosophers lies a spoon. To eat, a philosopher must hold two spoons — one in each hand. In the middle of the table is the shared limited food.
The key to solving the Dining Philosophers is to ensure two properties simultaneously:
- No deadlock: the system always makes progress — no philosopher is stuck forever waiting.
- No starvation: every philosopher who wants to eat will eventually get a turn.
The philosphers dining problem refers to the classical synchronization problem in an operating system and illustrates the issue when mutiple threads or processes access shared resources in memory without coordination.
Without careful design, competing threads can fall into:
- deadlocks: All threads wait forever for resources held by others.
- Racecondition: unpredictable behaviour of variables in common
This problem is a well-known synchronization challenge in concurrent programming, used to illustrate how multiple threads can share resources safely without conflicts.
Number the spoons and philosophers from 0 through n – 1 clockwise. Each Philosopher can reach two spoons: on the right or left side.
In order to avoid deadlocks each philosopher should grap opposite forks.
A even numbered Philosopher should pick up the left spoon first, then the right spoon. A odd numbered Philosopher should pick up the right speen first, then the left spoon. If another philosopher is already holding the right or left spoon, he waits until it is available.
If the number of philosopher is even, the result will be that all even numbered philosophers will eat, then all odd numbered philosophers will eat, and so on. This way, no philosopher wait forever and the system will make progress. If the number of philosopher is odd, then result will be two groups of philosophers one will eat and the other one will wait.
In the following animation you will see 4 philosophers.
if n even : t_die > 2*t_eat + t_sleep, then all philosphers will survive.
For this limit we assume that the a philosopher will have to wait at most one time for the spoon, then he will eat and sleep. So the time that a philosopher will wait is at most 2*t_eat + t_sleep.
if n odd : t_die > 3*t_eat + t_sleep, then all philosphers will survive.
For this limit we assume that a philosopher will have to wait at most two times for the spoon, then he will eat and sleep. So the time that a philosopher will wait is at most 3*t_eat + t_sleep.
One another limit for both cases could be t_die > 4 * t_eat + t_sleep.
But the limits can depend on the mutex locking, print delays, CPU scheduling and context switches. The limits could is probably higher than the ones mentioned above and we should add some margin to be sure that all philosphers will survive.
One possible way to implement the solution is by using mutexes and threads from the library thread.h.
A thread is the smallest execution unit which the CPU can process and would represent a philosopher. On the other hand the spoons could be represented by mutexes which are kind of locks. When a philosopher graps a fork no one can get access to the same object.
void grap_fork(t_philosopher *p, pthread_mutex_t *fork)
{
pthread_mutex_lock(fork);
print_message(p, "has taken a fork");
}
void grap_forks(t_philosopher *p)
{
if (p->id % 2 == 0)
{
grap_fork(p, p->lfork);
grap_fork(p, p->rfork);
}
else
{
grap_fork(p, p->rfork);
grap_fork(p, p->lfork);
}
}
Another way to improve timing is to delay some philosophers at the start so they begin in a better position.
void *routine(void *arg)
{
t_philosopher *p;
...
if (p->id % 2 != 0)
ft_usleep(p, 100);
...
return (NULL);
}
philosophers/
├─ Makefile
├─ README.md
├─ include/
│ └─ philo.h
├─ src/
│ ├─ free.c // functions to free memory from heap
│ ├─ init.c // allocates and initializes philos, mutex locks and threads
│ ├─ monitore.c // monitores all simulation condition(death of philos, starvation)
│ ├─ routine1.c // grap forks
│ ├─ routine.c // philosopher loop eat(), sleep_time(), thinking()
│ ├─ threads.c // thread create/join
│ ├─ time.c // time functions
│ └─ utils.c // allocation, destroy, print message
└─ tests/
└─ scenarios.sh // quick runs for common/edge cases
|
└─ picures/
└─ 0012.jpg
./Philosophers n t_die t_eat t_sleep must_eatnnumber of philosophers and forkst_dietime in ms that past after the last meal. After that duration a philospher will starve to death.t_eattime in ms that a philosopher needs during eatingt_sleeptime in ms that a philosopher needs during sleepingmust_eatnumber of times each philosopher should eat atleast
Output:
time_past | i-philosopher | state of a philosopher(thinking, eating, grabing or sleeping)
./Philosophers 5 400 200 200
Output:
0 0 is thinking
0 0 has taken a fork
0 0 has taken a fork
0 0 is eating
0 1 is thinking
0 1 has taken a fork
0 2 is thinking
0 3 is thinking
200 0 is sleeping
200 3 has taken a fork
200 3 has taken a fork
200 3 is eating
200 1 has taken a fork
200 1 is eating
401 0 is thinking
401 0 died
We had to test with valgrind tool=helgrind for dataraces and deadlocks.
Clone the repo:
git clone https://github.com/WaPoco/PhilosophersChange directory:
cd Philosophers
Create the binary:
make
Clean up at the end:
make fclean