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.

Sunday, 11 October 2015


When it comes to debugging programs, the first tool in my toolbox for compiled languages like C or C++ is usually 'print'. I don't tend to bust out a debugger unless I'm in an IDE such as IntelliJ.

This can pose problems for me in a relatively print-challenged environment, such as msp430 on Linux. Last night I had found myself in just this situation when I found myself musing on why the msp430 upload tool was called mspdebug. A quick search found a nice manual and a few minutes later I was debugging away.

Here's a sample transcript:

With the sketch already uploaded to the board, this script shows how to:

  • Generate a name-list from the sketch's Elf file
  • Import these symbols into the debugger
  • Set a breakpoint by name in the program
  • Run the sketch up to the breakpoint
  • Single-step the program once the breakpoint has been reached.
If you're interested, the sketch is a rather convoluted version of Blink.