Safe, portable, non-blocking interprocess communication (part 2)

Some time ago, I wrote about interprocess communication without interrupt locks, using a circular buffer. This is a really useful technique, if you want to provide buffered data transfer between a reader and a writer without introducing blocking into your application.

This approach isn’t suitable if you want to receive the most up-to-date data, for example when sampling from some external input device. Fortunately, the same source (the MASCOT design methodology), provides another approach to interprocess communication which is also non-blocking. In this case, the emphasis is on a “wait-free” protocol that guarantees the reader gets access to the most recent valid data.

This approach is based on Simpson’s four-slot algorithm. In this approach, the four slots are arranged as two pairs (left and right), and within each pair we have top and bottom slots. There are two processes: a reader process and a writer process. The writer (as its name implies) stores its data to one of the slots. It is also responsible for writing two control values:

• latest, which indicates which pair (left or right) the writer most recently wrote to;
• index, which indicates which slot of each pair (top or bottom) the writer most recently wrote to.

The reader also writes to a control value, reading, which indicates which pair is being read from.

When storing a new value the writer:

• selects the pair that is not being pointed to by reading;
• toggles the value of index for that pair;
• writes the slot pointed to by the new value of index;
• updates latest to point to the pair which has just been written to.

In the case of the diagram, if the next action is a write, this would result in index[left] is updated to point to slot B. When reading a value the reader:

• updates reading to the same value as latest;
• uses reading and the index for the pair pointed to by reading to read the specific slot.

From the diagram, if the next action is a read, slot A would be returned. Provided that you can write latest, index and reading atomically (i.e. without being interrupted part way through), this approach can be implemented without interrupt locks or other OS synchronization features – it could even be coded at the application level (rather than within the OS)

A very nice feature of this protocol results from the fact that no conditional statements are used – the protocol always executes a fixed set of statements for writing values and a fixed set of statements for reading values. From our perspective this has two interesting effects:

• It’s very easy to achieve 100% MC/DC on the reading and writing functions;
• There will be less variability in execution time from this approach than for other interprocess communication approaches.