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.
![\begin{figure}\scriptsize\rule{2.8in}{.5pt}
\begin{tabbing}
aaa\= aaa\= aaaaaaaa...
...inNumBuff = $S + F$; \\
\end{tabbing}\rule{2.8in}{.5pt}
\normalsize\end{figure}](img15.png) |
Figure:
Task set with one writer and seven reader processes.
![\begin{figure}{\small\begin{tabular}{\vert l\vert c\vert c\vert c\vert c\vert} \...
...hline
{\it Reader 6} & 500 & 25 & 475 & 49 \ \hline
\end{tabular}}
\end{figure}](img16.png) |
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