Next: Performance Evaluation
Up: Improving Wait-Free IPC
Previous: Identification of Fast Readers
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.
Next: Performance Evaluation
Up: Improving Wait-Free IPC
Previous: Identification of Fast Readers
hai huang
2002-03-30