42-Philosophers

Parallel/Concurrent Programming, Multi-threading, Interprocess Communication and Execution Context in C

Final Grade :

Overview

This project is a version of the Dining Philosophers problem. A given number of philosophers sit around a table with a huge plate of pasta at the center. Each philosopher :

• May only be in one state at a time : thinking, eating or sleeping.
• Has only 1 fork, but needs 2 forks to eat (he will have to borrow one from either his left or right neighbor)
• A philosopher will follow this routine :
  • Grab 2 forks and start to eat for a given amount of time : tte (time to eat)
  • Put down the 2 forks he was holding and sleep for a given amount of time : tts (time to sleep)
  • Wake up and think if he has the time to
• If a philosopher spends more than a given amount of time (parameter "time to die" or ttd) between the start of 2 meals, he will die starving

The goal is to try to have the philosophers live as long as possible. To do so, it is necessary to optimize the access to the forks. This is of course a metaphor :

• Each philosopher is a thread (mandatory part) or a process (bonus part)...
• They share access to data (forks), but should not use it at the same time (avoid dataraces)
• They have to follow a pattern preventing from having everyone doing the same thing at the same time (synchronization with mutexes for mandatory part, mutexes AND semaphores for the bonus part)
• They must avoid at all cost being in a dead-end situation (deadlock). For example, if there are only 2 philosophers and each of them grabs a fork, they will be locked in a situation where each one of them tries to grab a 2nd fork to eat. After some time, both of them will die.

Constraints

Clean code :

• No dataraces
• No memory leaks
• No zombie process

No communication between philosophers, ie. one philosopher cannot ask information about the state of another, nor tell the others philosophers that he is about to die.
The program needs to shutdown nicely in case of error (thread creation failure, process creation failure).

Implemented Solution

For both projects, the allowed functions did not include the "try" version (pthread_mutex_trylock and sem_trywait). Moreover, for the bonus part, we couldn't use the function to get the value of the semaphore (sem_getvalue).
This increases the difficulty of the projet because :

• Mandatory part :
  • You cannot try to acquire data access (pthread_mutex_trylock), and change your mind. Once you demand access to it, you will remain blocked until it is available...
  • But you can use a shared memory address (pointer) between the philosophers so they can write/read info about themselves/others. Threads only have their own stack and context. They do share the heap.
• Bonus part :
  • You still cannot try to acquire data access (sem_trywait), and change your mind. Once you demand access to it, you will remain blocked until it is available...
  • You CANNOT use a shared memory address (pointer) between the philosophers.
  • You also CANNOT use the semaphore to share data (sem_getvalue)

This led to the following :

Mandatory part :

• Each philosopher is a thread spawned by the main thread
• After spawning the last philosopher, the main thread become a monitoring thread
• When a philosopher dies or the meal count is achieved, the monitoring thread write this info in a memory area shared between all the threds so they can stop

Bonus part :

• Each philosopher is a child process spawned by the father process
• After spawning the last philosopher, the father process become a monitoring process
• Each philosopher process will spawn 2 threads :
  • A meal_goal_monitor deamon in charge of checking if the all the philosophers have eaten the requested amount of time
  • A dead_monitor deamon in charge of checking if one of the philosophers died starving
  Each of theses threads are in a blocked state (sem_wait) and can be unlocked by the monitoring process. Doing so will terminate the other deamon before rejoining the main thread and exit nicely

Usage

Dependencies

First and foremost, make sure you have the following packages installed on your machine :

• Docker
• Make

Install

Clone the repo on your machine and go to project directory :

  git clone https://github.com/fleblay/42-Philosophers && cd !#:2:t

Go to the mandatory...:

  cd philo

Or bonus part...:

  cd philo_bonus

Build the executable:

  make

Run the program with the following syntax :

  ./philo number_of_philosophers ttd tte tts [number_of_times_each_philosopher_must_eat]

Or this one for the bonus part :

  ./philo_bonus number_of_philosophers ttd tte tts [number_of_times_each_philosopher_must_eat]

The last parameter is optional : if all philosophers have eaten at least number_of_times_each_philosopher_must_eat times, the simulation stops. If not specified, the simulation stops when a philosopher dies.

ROX (Return On Experience)

Knowledge acquired during this project

• Parallel Programming using POSIX Threads. Mutual Exclusion concept (mutexes) and deadlock.
• Parallel Programming using process. Interprocess Communication (IPC) using semaphores (signal and files)