Mastering 42
holy_graphcoreexplainers

Philosophers

by bhagenlo

written for version 10

Welcome, welcome, to one of the more famous thought experiments/problem statements of Computer Science. Formulated by Edsger Dijkstra in 1965, it has challenged (or plagued?) students ever since.

In our case, the problem statement goes the following:

  • There are N philosophers at a round table, as well as N forks. Each fork lies in between two philosophers.
  • Philosophers alternately eat, sleep and think, in that order.
  • To be able to eat, philosophers have to pick up both the forks left and right to them.
  • When they've finished eating, they have to put them down again.

So far, that sounds like a project where one can come up with any ideas/algorithms for figuring out cooperation between agents, then test them against each other, and think about which one to use when.

Sadly, that is not the case. The problem statement goes on:

  • Philosophers don't speak with each other.
  • Philosophers don't know whether another philosopher is about to die.

And gone is the open space for creativity. In exchange for that, you learn about threads, mutexes, and how to create proper abstractions. Which, at least, is quite nice too.

#Prerequisites

Before even thinking about how to handle a problem as complex as the Dining Philosophers (concurrent problems always are – our brains are just not good at this by nature), it's super useful to first create working tools. And that's what we're gonna do.

To find those, we start out by finding out what exactly the important functions from the subject do. You'll definitely need to manage time, threads and mutexes. (If you don't know what the latter two are, now is the time ;))

And we start out with time:

#1. gettimeofday()

This function returns a timeval struct, which looks like that:

struct timeval {
    time_t      tv_sec;     /* seconds */
    suseconds_t tv_usec;    /* microseconds */
};

Clearly, you don't want to work with this. We're interested in the µs that passed since the start of our simulation. So, I'd strongly advise you to create a tool (-> write a function) that returns a proper UTC timestamp (in µs) to you.

Next, threads:

#2. pthread_*

Again, find out what the three of them (create, join and detach) do.

Create a small working examples with (N) threads in which:

  • Each thread prints their ID.
  • The main thread waits for all the others to complete.
  • The main thread doesn't wait fo the others to complete.
  • Completed threads return a value.

And if you, for some case, found out that you'd rather use wrapper around those functions, please do so.

Finally, mutexes:

#3. pthread_mutex_*

Well, find out what they do.

And again. Create some working examples, and write a wrapper when you see fit.

#During

Now, finally. You're able to start working on our algorithm. Have fun! :)

But keep in mind that:

  • You don't produce a locked state: Neither a deadlock nor a lifelock.
  • Philosophers aren't allowed to speak with each other.

#Cleaning Up

There shouldn't be that much to be done here. Grab yourself the eval sheet (or a tester), and off you go :)

#Aftercare

Now that you're done, I can say it out loud:

Almost everything you used or did in this project was bad practice.

If you want or need to write a concurrent program, then:

  1. Don't use C. Use languages that are suited for that.
  2. Don't even think of writing everything by hand. Use libraries.
  3. Don't use anything that might block (like mutexes and semaphores), except you must. Use things relying on the Actor Model instead.
  4. Avoid (global) mutable state as early as modeling your problem. (Hint: You rarely need it.)

#Pointers
← fract_ol

Found something to improve? Edit this page on Github!

minishell →