/ft_philosophers

42 São Paulo - Philosophers

Primary LanguageCMIT LicenseMIT

42 São Paulo - Philosophers

42 São Paulo License Code size in bytes Lines of code Top language Last commit

Build Norminette v3

An age-old threaded problem in pure C.

📜 Table of Contents

🧐 About

A C implementation of the classic Dining Philosophers Problem by Edsger Dijkstra, with threads, mutexes, forks and semaphores.

✅ Checklist

  • Makefile should explicitly name all source files (make dump_sources).
  • Make must compile without relinking
    • make all shouldn't recompile/rearchive any objects or sources.
    • Add .keep to object dirs
  • Compiles with workspace's cc (clang version 12.0.1)
    • Switch Makefile's clang-12 to CC before submitting.
  • Test in workspaces
  • Written in C.
  • Follows norminette 3.3.51
  • Should not quit unexpectedly (segmentation fault, bus error, double free, etc.)
  • All allocated heap memory properly freed, no memory leaks.
    • Use gcc -fsanitize=leak flag.
    • Check memory leaks with valgrind.
  • Compiles with -Wall -Wextra -Werror
  • No global variables.
  • Receive 4-5 arguments.
    • number_of_philosophers: number of philosophers and forks.
    • time_to_die (ms)
      • Philosophers should die if they didn't eat since the BEGINNING of their last meal/beggining of the simulation.
    • time_to_eat (ms)
    • time_to_sleep (ms)
    • number_of_times_each_philosopher_must_eat (OPTIONAL)
  • Index philosophers from 1 to number_of_philosophers.
  • Program log:
    • timestamp_in_ms X has taken a fork
    • timestamp_in_ms X is eating
    • timestamp_in_ms X is sleeping
    • timestamp_in_ms X is thinking
    • timestamp_in_ms X died
  • Log messages shouldn't mix up with each other.
  • Death message should print before 10 ms.
  • Philosophers should avoid dying.
  • No data races.

Mandatory

  • Program name philo
  • Turn in Makefile, *.h, *.c , .gitignore in directory philo/
  • Makefile rules: $(NAME) all clean fclean re
  • Allowed functions:
    • memset printf malloc free write usleep
    • gettimeofday pthread_create pthread_detach
    • pthread_join pthread_mutex_init pthread_mutex_destroy
    • pthread_mutex_lock pthread_mutex_unlock
    • libft FORBIDDEN
  • Philosophers alternatively eat, sleep or think (in that order)
  • Should calculate if philosopher will die and die.
  • There are as many forks as philosophers
  • Philosophers need to grab left_fork and right_fork before they can eat.
  • Create a thread for each philosopher.
    • Deal with lone philosopher separately.
  • Create a mutex for each fork.
  • Program ends when any one philosopher dies from starvation
  • Program ends when each philosopher ate number_of_times_each_philosopher_must_eat
  • Guardian Thread:
    • Checks whether any philosopher died/should be dead.
    • Check if everyone ate their last meal.
    • Polling + Mutex
  • Pass all testers

Bonus

  • Program name philo_bonus
  • Turn in Makefile, *.h, *.c , .gitignore in directory philo_bonus/
  • Makefile rules: $(NAME) all clean fclean re
  • Allowed functions:
    • memset printf malloc free write fork kill exit
    • pthread_create pthread_detach pthread_join usleep gettimeofday
    • waitpid sem_open sem_close sem_post sem_wait sem_unlink
    • libft FORBIDDEN
  • Create a process for each philosopher.
  • Create a semaphore the forks.

🏁 Getting Started

📦 Dependencies

You will need git, make and clang-12:

$ sudo apt-get install git make clang-12

🖥️ Installing

Clone the repo and build with make:

$ git clone --recurse-submodules https://github.com/librity/ft_philosophers.git
$ cd ft_philosophers/philo
$ make

This should create a philo executable in the root folder:

./philo

📝 Notes

Helgrind error: lock order "0x4AAB040 before 0x4AAB068" violated

Potential Deadlock Diagram Impossible Deadlock Diagram

🛸 42 São Paulo

Part of the larger 42 Network, 42 São Paulo is a software engineering school that offers a healthy alternative to traditional education:

  • It doesn't have any teachers and classes.
  • Students learn by cooperating and correcting each other's work (peer-to-peer learning).
  • Its focus is as much on social skills as it is on technical skills.
  • It's completely free to anyone that passes its selection process - The Piscine

It's an amazing school, and I'm grateful for the opportunity.

📚 Resources

memset()

printf()

malloc()

free()

write()

usleep()

gettimeofday()

pthread_create()

pthread_detach()

pthread_join()

pthread_mutex_init()

pthread_mutex_destroy()

pthread_mutex_lock()

pthread_mutex_unlock()

sem_open()

sem_close()

sem_post()

sem_wait()

sem_unlink()

pthread.h

Data Races

Atomic Types

semaphore.h

Tutorials

Boards

C Quirks

Valgrind

Helgrind Lock Order Violated Error

nice

Visualizers

Testers

Videos

Python Multithreading