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.

Saturday, 29 August 2015

Simple Breadboard Power Supply

It's very satisfying to build something for which you've all the parts to hand, there's no waiting around, just immediate gratification. This little build is such a thing. It's a dual-voltage (5v and 3.3v) power supply which plugs into a breadboard and is handy for projects which aren't powered from a USB tether (e.g., wireless microcontroller prototypes or projects which don't use a microcontroller at all, hard as that might be to believe).

It's loosely based on the circuit below, although I used different values for the capacitors, having first done a bit of research to discover that the 100nF ones are used to filter high-frequency noise. If I have problems with that in the future I'll add them.

Monday, 11 May 2015


Interrupted is a new approach to developing low-power, low-latency Arduino sketches, which was motivated by two observations:
  • That the default mode of programming for Arduino is busy-waiting, and
  • The runtime support for power management provided by avr-libc is basic, being charitable to it.
Taken together, these two points mean that Arduino sketches aren't easily battery-powered, while the second results in a cargo-cult of code copying. Lastly, timed sleep in Arduino is provided by delay(), which itself is busy-waiting. This increases latency, the response time to external events such as button-presses.

And so to an example; the sketch below manages a very simple hardware configuration composed of an ATtiny85, an LED and a button: the button turns the LED on and a timer turns it off again. (You could imagine such a sketch driving a Useless Machine.)

In the main loop, the CPU sleeps in select(), waking up when an event occurs on one of the devices it manages. Three events are possible here:
  • An external interrupt which occurs when the button drives pin PB2 low,
  • A pin-change when the LED on PB0 is turned on or off,
  • When the watchdog timer fires, one second after the LED comes on.
The value returned from select() indicates which event has woken it up, allowing the concise construction of state-machines. If more than one event source is ready, the one added earlier in setup() is returned, implementing a crude form of priority.

The sleep-mode entered by select() is the maximum which makes sense for the devices currently active. In this little example, SLEEP_MODE_PWR_DOWN will be chosen because external and watchdog interrupts still work in this mode.

Much credit is due to Nick Gammon, for the great work contained in his Interrupts and Power Saving Techniques for Microprocessors forum-pages.

Very similar techniques were employed in the runtimes of the Conic and Regis environments developed at Imperial College (as well as the select system call, of course).

The library has been ported to ATtiny84, ATtiny85 and ATMega328 processors and is, as always, at GitHub. Its code footprint varies, depending on the functionality required by individual sketches, but the little example above comes in at 2.5kB.

Work remains to be done on this library including porting it to Energia (i.e., the msp430 family), porting existing sketches to use it and completing the repertoire of supported devices (e.g., SPI handling).

Wednesday, 11 March 2015

A tiny ATtiny

Very tiny!
 Recently I was surprised to discover that although I've made several projects using one, I'd never built a development board around the ATtiny85. With any project there are always design choices and a couple of important ones here were:
  • Is a breadboard optional or required? If optional, you get the familiar Arduino form-factor, which can either be connected to a breadboard using jumper cables or populated with pre-built shields.
  • Design a PCB or something more ad hoc? I wanted something quickly --- I wasn't going into competition with the Teensy or Trinket.
  • If not designing your own PCB, use stripboard or protoboard? While I've never been a huge fan of protoboard, because you're basically making your own strips by blobbing solder across pads, you can get quite a high component density with it.
So I opted for the path not taken, requiring a breadboard and using protoboard, and the result is pictured above. Notice that protoboard allows the FTDI connector to be attached at right-angles to the chip (try that with stripboard!) and also exposes more of the breadboard for jumper cables (the 10k resistor connecting reset and Vcc is underneath the chip).

With the ever-useful Tiny-Safe-Boot bootloader and a bespoke entry in my arduino-tiny's boards.txt file, it's as easy as regular Arduino, at a fraction the cost!

Thursday, 19 February 2015

TinySensor Server

Well after almost a year I decided it was time to update this project with improvements to both its hardware and software.

On the hardware side, the server is still the original Raspberry Pi model B, but I've mounted the nRF24L01+ radio on a neat little Slice of Pi board. (These boards also have traces for mounting XBees with their unusual pin spacing. And they're cheap!)

The Slice of Pi board (left) with radio and status LEDs
While I had the soldering iron out, I added a couple of status LEDs (see picture). The green one indicates recent activity on the radio, while the red one indicates a timeout but also flashes every time a packet is received. Both of them are driven by a single GPIO line on the Pi. (This was motivated by the radio cutting out on the Pi, probably due to the original Heath-Robinson jumper cable arrangement, and since its transplant it's behaved perfectly.)

On the software side, there are now quite a few little daemons, each doing one thing well:
  • A wireless hub, running RF24-rpi, sends packets received on a TCP socket,
  • A wired hub, running remotely, polls a legacy 1-wire sensor network and sends its readings on another TCP socket,
  • A multiplexor, connected to the two data sources above, sends their streams to its connected clients, described next,
  • A MySQL client writes readings to a database,
  • A status client manages the LEDs described above,
  • An RRD client maintains a round-robin database,
  • An lcdproc client updates a wireless LCD display.
All of these are, as usual, on GitHub.

Future software components planned for this system include a simple weather service to inject local weather data into the stream, and a client for one of the various IoT services now becoming widespread. (Here is a fairly recent overview of some of these.)

Wednesday, 3 December 2014

Space Invaders!

When I was a teenager Space Invaders arrived and changed the world. I must have put pounds into that machine in the local chipper, in the days when chips cost shillings. It never occurred to me that you could actually buy one of your own until one of my brother's friends' fathers did. (Come to think of it though, if I'd kept all of the cash I put into various machines, I probably could have had one of my own. I believe this is known as delayed gratification.)

Same Hardware, Different Processor!

Fast-forward 30-odd years and I'm sitting there blogging about an emulation of an 8-bit microcomputer of similar vintage. Hmm...

Space Invaders hardware comprises an Intel 8080 clocked at 2MHz, 8k ROM, 1k RAM and 7k memory-mapped video RAM. (An Emutalk thread has all the details and the ROMs.) The most difficult part is definitely the CPU but that only has to be done once to open up a whole world of crap games.

There are dozens of 8080 emulations out there, of varying quality. (Most of them written solely for this game!) I picked one and remixed it in the spirit of the 6502 emulator I made for the UK101; it plugs into that framework quite easily.

When a moderately-complex project like this links for the first time, the natural thing to do is upload it, more in hope than expectation, and when it fails, start debugging. The best way to do this is with a test-suite, preferably one which someone else has written in advance. (This worked out really well for my 6502 core thanks to Klaus Dormann's excellent 6502 tester.)

For the 8080, all searches led to a 'CPU exerciser'. Rather than testing a single instruction in isolation, this program runs a group of operations with different arguments and merging the resulting CPU state into a checksum as it goes. If the final checksum obtained by 'your' CPU is the same as one from a real chip, you know (to a high probability anyway) that your implementation is good for the instructions tested. (Luckily, that page documents results from real CPUs so there's no need to dig up an old 8080 board.)

If that sounds daunting, it is! Fortunately a preliminary test is also provided which tests the instructions required to run the exerciser itself. This helped fix a few bugs on its own and, since it used the CP/M "bdos conout" operation to report success, raised the interesting possibility of implementing a virtual 8080-based CP/M machine. I subsequently found a slightly more complex set of tests in another emulator's repository which helped find enough bugs to get all-but-two of the exerciser's tests passing.

(Timings of the exerciser indicate that my 8 year-old Lenovo laptop runs an emulated 8080 about 80x faster than the 2MHz 8080 for which it was intended. I haven't timed it on a Stellaris Launchpad however.)

Adventures in Dremel

So, despite the fact that some bugs remain in the emulation, enough of it is working to run Space Invaders properly. It runs at correct speed because it is driven by a timer interrupt (emulated with Energia's millisecond timer) and therefore we didn't need to bother keeping track of individual instruction timings, which all of the CPU emulators I looked at did. (Most of them were similar in other ways too, indicating a common influence, perhaps in this document.)

Just like the real thing, if you're 6" tall.

You can find the whole thing at Github, as usual.