42 (VIII): philosophers, threads at the table

so_long had a window and sprites (I told you about it in 42 (VII): so_long, the first game); philosophers has nothing to look at: a terminal that prints lines and, if you do it wrong, a program that hangs or declares dead those who are alive. It's the classic dining philosophers problem: N philosophers around a circular table, one fork between each pair, and to eat you need both of the ones next to you. If one doesn't eat within the given time, they die, and the log (the program's diary) has to say so without mixing lines or adding anything afterwards.

The truth problem

Here data isn't sorted: threads are coordinated (a thread is a line of work inside the program; several threads run at the same time). The danger has three faces. Deadlock, a circular block where each thread waits for the one next to it: if all the philosophers grab the left fork first, they all end up waiting for the right one forever. Race conditions, when two threads touch the same data without coordinating: the moment of the last meal is written by one thread and read by another; without protection, every so often someone dies by error or survives being dead. And time precision: usleep, the pause offered by the system, doesn't sleep exactly what you ask it to, and half a millisecond of drift is the difference between a philosopher alive and a philosopher dead.

How I solved it

One thread per philosopher and one mutex per fork (a mutex is a lock: while one thread holds it, no other can pass). Against deadlock, in the absence of a cycle: the even-numbered philosophers grab the right fork first and the odd-numbered ones grab the left first; this way nobody gets stuck in a circle. Against races, minimal and guarded shared state: the stop flag (the signal that orders everything to stop) and the log have their mutex, and each philosopher protects their own last-meal moment and meal counter with their own mutex. A monitor in the main thread walks the table every half millisecond checking whether someone has exceeded the time or whether everyone has eaten their share, and when it's time to stop everything, it stops it. To sleep with precision I did a sleep in small chunks that checks the stop flag, and an initial offset between even and odd philosophers so they don't all start at once with the same hunger. The case of a single philosopher, with a single fork, goes its own way: it grabs it, the log says so, and dies.

A curiosity: I have two repositories for this project, philosophers and 42_philosophers. The first one worked, but I repeated it with the neater structure I had been learning; comparing them is seeing how my way of breaking down a problem had changed.

What I take away

Philosophers left me with a healthy distrust: the concurrency bug doesn't show up every time, it shows up one in fifty executions, so I ended up running the program in loops of hundreds of executions before saying it was fine. I also understood that a mutex isn't magic but discipline: knowing exactly who touches which data and protecting only what needs it. And that the classic problems of the sixties and seventies keep teaching things that no modern tutorial explains so well.