Transformation Mechanism

Figure: Algorithm to find space-optimal division of fast and slow readers and the amount space required.

Figure: Task set with one writer and seven reader processes.

We have shown here how two different single-writer, multiple-reader wait-free IPC mechanisms can be modified to take into account real-time characteristics of tasks to reduce both memory and execution time overheads. In general, we can apply our transformation to other such IPC algorithms with the following steps.

Step 1.

Identify fast and slow readers for a particular system: simply apply the algorithm in Section 3.4. This will minimize the number of message buffers needed, while still ensuring temporal isolation between the writer and the fast readers.

Step 2.

Fine-tune reader sets: we may not always want to optimize for space, so we can adjust the partitioning obtained in Step 1 if needed.

Step 3.

Convert reader code to slow reader code: Typically, there are no modifications needed for slow readers, so this is just a renaming step.

Step 4.

Introduce fast reader code: The fast readers are trivially implemented -- they just read the pointer indicating the most recently written message buffer, and then read from that buffer.

Step 5.

Modify writer code to ensure temporal isolation with fast readers: this is the most significant change required. Since most algorithms have some code for selecting a buffer to write, this step usually only requires modifying the selector to ensure that the same buffer is not reused within N consecutive writes. Sometimes, this can simply be done by using the available buffers in a cyclic fashion, and having enough total buffers.

Applying these steps, we can modify existing wait-free single-writer, multiple-reader algorithms to use real-time characteristics of the tasks and reduce processing and memory costs.