search

aenglert42 / dining_philosophers

A small project to learn the basics of threading a process and resource sharing. On the basis of the "dining philosophers problem", originally formulated by Edsger Dijkstra. Inspired by the "42 Coding School" exercise "philosophers" (February 2022).
2 stars 0 forks source link

readme

dining_philosophers

A small project to learn the basics of threading a process and resource sharing. On the basis of the "dining philosophers problem", originally formulated by Edsger Dijkstra. Inspired by the "42 Coding School" exercise "philosophers" (February 2022).

Table of contents

Introduction

Next: Approach  [Contents]

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

Description

The aim of the exercise is to write a program which does a simulation of the dining philosophers. The situation is as follows: One or more philosophers sit around a round table. Each philosopher has their own place at the table with a plate and a fork on its right-hand side.

The dish served is a very difficult kind of spaghetti, that has to be eaten with two forks. To achieve this the philosophers have to also use the fork of their neighbor. As a consequence philosophers sitting next to each other can not eat simultaneously.

The philosophers are alternatively eating, sleeping or thinking. When a philosopher has finished eating, they put the forks back on the table and start sleeping. Once awake, they start thinking. The simulation stops when a philosopher dies of starvation. This should be avoided. However philosophers don’t speak with each other and don’t know if another philosopher is about to die.

Illustration[^1] of the "dining philosophers problem": [^1]: From Wikipedia: https://en.wikipedia.org/wiki/Dining_philosophers_problem

General Rules

Arguments

The program should take the following arguments:

number_of_philosophers time_to_die time_to_eat time_to_sleep [number_of_times_each_philosopher_must_eat]

Approach

Next: Prerequisites Previous: Introduction  [Contents]

I started to learn and experiment with threads watching the videos linked in the resources. I learned how to create threads, how to pass arguments to threads and how to use mutex locks.

The following quote is a very good and funny metaphoric exlanation on threads, resourece sharing and mutex protection:

When I am having a big heated discussion at work, I use a rubber chicken which I keep in my desk for just such occasions. The person holding the chicken is the only person who is allowed to talk. If you don't hold the chicken you cannot speak. You can only indicate that you want the chicken and wait until you get it before you speak. Once you have finished speaking, you can hand the chicken back to the moderator who will hand it to the next person to speak. This ensures that people do not speak over each other, and also have their own space to talk.

Replace Chicken with Mutex and person with thread and you basically have the concept of a mutex.

Of course, there is no such thing as a rubber mutex. Only rubber chicken. My cats once had a rubber mouse, but they ate it.

Of course, before you use the rubber chicken, you need to ask yourself whether you actually need 5 people in one room and would it not just be easier with one person in the room on their own doing all the work. Actually, this is just extending the analogy, but you get the idea.[^2] [^2]: From Stack Overflow: https://stackoverflow.com/a/34558

Basically every philosopher (thread) is going to executing an infinie while loop with the philosopher's routine (eat-sleep-think-repeat, as described above), until one of them dies of starvation or all of them have eaten the number of required meals. As they should not communicate with each other, a external control instance is needed.

The tricky part of this project comes with the parallelism and the use of shared resources (e.g. the forks). To prevent data races the shared resources have to be protected using _mutexlocks. This has to be coordinated in a way that no deadlocks can occure. The -fsanitize=thread flag is very useful to identify and find potential problems.

I approached this project in three main steps. First I created the "frame" that sets up the simulation. After this I worked out the routine and ended with the external control instance.

Frame

For the frame my goal was to code the program up to the point were it would recieve the user input from the command line, do the input error checking and launch the right number of threads (given by the user input) that will run the routine. For now the routine should only print what I call the philosopher_id (the number of the philosopher from 1 to n). Once I managed that, I went on with the routine.

Routine

I changed from printing the philosopher_id to printing the required logs, as stated above. To have an easyer start, I first developed the routine without using any mutex_locks, ignoring the fact that a fork can not be used by two philosophers at the same time. When I got this going, I protected the forks of simultaneous use by locking and unlocking the corresponding mutex_locks.

Control Instance

I developed a control function that constantly loops through all the philosophers and checks if a one of them has to die or they ate all their meals. If I detect one of the mentioned cases, I set a flag (which is checked by the philosophers constantly) to indicate that the simulation has to end. I lock the log printing so that no further logs get printed after the notification of the death. The flag and all other shared variables have to be protected with mutex_locks.

Prerequisites

Next: How to launch Previous: Approach  [Contents]

How to launch

Next: Example Previous: Prerequisites  [Contents]

Compile the program via the Makefile by using make in the root directory of the repository.

Run it like this:

./philo 4 800 200 200

For a description of the arguments see: Arguments.

Example

Next: Resources Previous: How to launch  [Contents]

Terminal output for the following examples:

Example 1 Example 2 Example 3
Philosphers1 Philosphers2 Philosphers3

Resources

Next: Notes Previous: Example  [Contents]

Code Vault: Playlist - Unix Threads in C Video 1 (Short introduction to threads) - Video 7 (How to pass arguments to threads in C)

Jacob Sorber: Playlist - Programming with Threads Video 1 (How to create and join threads in C) - Video 3 (Safety and Speed Issues with Threads)

Notes

Previous: Resources  [Contents]

Depending on the performance of the Computer philosphers may die (faster) on slower computers, but live on faster ones. Especially in extreme cases for example high number of philosophers (>200) or short times to eat and/or sleep (<60 ms).