Dining Philosophers
A while ago, I wrote about threading. Last week, one of the students I’m guiding for their internship, mentioned he still had to complete a programming assignment. It was about implementing the dining philosophers problem in C, using pthreads. To a student, this can be quite a challenge.
The dining philosophers problem is a very fun programming problem concerning resource locking. The origins date all the way back to 1965, a time when computers were big clunky machines with green terminals, and the operators were computer scientists wearing lab coats.
An excellent description of the problem can be found in Wikipedia.
I remember my brother once explained it to me when I was young. He loves spaghetti, so I guess the idea of the philosophers having spaghetti kind of appealed to him. He noted that, in a real world situation, the problem is easily solved by adding a director, who tells the philosophers when to eat and when to think. So, a scheduling assistant can help in solving the problem. However, the problem can also easily balance itself by doing the right kind of locking, and be solved without the use of an explicit arbiter.
In pseudo code:
proc run_thread() {
while plate not empty {
lock(left_fork)
if not trylock(right_fork) {
unlock(left_fork)
continue
}
eat from plate
unlock(right_fork)
unlock(left_fork)
}
}
In order to avoid deadlock, trylock is used rather than a hard lock. trylock is an atomic operation like bit-test-and-set; it locks only if the lock was free, and does not wait until you actually own the lock.
When locking multiple resources at once, it is good practice to unlock in the reverse order of locking, also to avoid deadlock.
Note that there is no need to sleep anywhere in the loop; waiting for short periods of time is something that a human would do, but is totally unnecessary in a computer program. (Think of all the cycles needed to load/execute the instructions in between as waiting for short periods of time!)
Starvation
In the above code, it’s possible that one philosopher finishes his plate, while the others haven’t even started yet—they are literally starving. It would be good table manners if we instructed each philosopher not to eat faster than his neighbors. This would produce automatic balancing in the use of the resources.
In pseudo-code:
if my_plate >= left_neighbor_plate or
my_plate >= right_neighbor_plate then
eat from plate
Making the wrong if-statement here results in nobody eating. You can also move this if-statement up, and refrain from trying to lock while the neighbors haven’t eaten yet. This is giving your neighbors a chance to eat, and results in spinning before the lock, but also in a higher success rate for acquiring both locks.
What’s fun is seeing how the outcome is different every time; you can actually gamble on which philosopher will finish first. Multi-threaded programs have a weird way of being undeterministic somehow.
As an exercise, and just for the fun of it, I coded up the dining philosophers problem with N philosophers in C with pthreads in less than an hour. I think that I would have had a much harder time at it when I was still a student, though.