Monday, 19 October 2015

The Dining Philosophers

It seems as if this blog has been veering towards software for a while now, and this post is about as far from hardware as it's ever been --- but hey, it has LEDs!

The problem of the Dining Philosophers was first described by Dijkstra in 1965 as an example of resource allocation in concurrent (operating) systems. Briefly, five philosophers sit around a table with a bowl of spaghetti in the middle, spending their time alternately thinking and eating. There are five forks at the table, one between each philosopher, and in order to eat, a philosopher requires those adjacent to him.

Two important properties to be addressed by a solution to the problem are: safety and liveness. The first means that the solution is free from deadlock while the second requires that every philosopher eventually gets to eat. There are many solutions but the one implemented here is that proposed by Dijkstra himself: freedom from deadlock is ensured by introducing an asymmetry: the lowest numbered philosopher reaches for his right-hand fork first while the others reach for the fork on their left.

In the solution, each Philosopher is implemented as a Task and each fork as a Semaphore.

Tasks are non-preemptive, light-weight threads of control, they run until they call a blocking function, for example waiting on a Semaphore or sleeping for some time.

There are two kinds of task, the implicit one which runs setup() and loop(), and explicit ones which inherit from class Task and must provide their own stacks, here, 50 words.

In the example, the main setup() initialises the Task system and starts the explicit tasks; it then implements the behaviour of Philosopher #4 in its loop().

In the video, red LEDs indicate a thinking philosopher and green ones a philosopher eating spaghetti.

As always, the Task library is available on Github for Arduino and Energia.

No comments:

Post a Comment