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 (
right), and within each pair we have
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 (
right) the writer most recently wrote to;
index, which indicates which slot of each pair (
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
- toggles the value of
indexfor that pair;
- writes the slot pointed to by the new value of
latestto 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:
readingto the same value as
indexfor the pair pointed to by
readingto read the specific slot.
From the diagram, if the next action is a read, slot A would be returned. Provided that you can write
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.