USENIX 2002 Annual Conference - Technical Program Abstract
Improving Wait-Free Algorithms for Interprocess
Communication in Embedded Real-Time Systems
Hai Huang, Padmanabhan Pillai, and Kang G. Shin,
Real-Time Computing Laboratory, Department of Electrical Engineering and Computer Science, The University of Michigan
Concurrency management is a basic requirement for interprocess
communication in any multitasking system. This usually takes the form of
lock-based or other blocking algorithms. In real-time and/or
time-sensitive systems, the less-predictable timing behavior of lock-based
mechanisms and the additional task-execution dependency make
synchronization undesirable. Recent research has provided non-blocking and
wait-free algorithms for interprocess communication, particularly in the
domain of single-writer, multiple-reader semantics, but these algorithms
typically incur high costs in terms of computation or space complexity, or
both. In this paper, we propose a general transformation mechanism that
takes advantage of temporal characteristics of the system to reduce both
time and space overheads of current single-writer, multiple-reader
algorithms. We show a 17-66% execution time reduction along with a
14-70% memory space reduction when three wait-free algorithms are
improved by applying our transformation. We present three new algorithms
for wait-free, single-writer, multiple-reader communication along with
detailed performance evaluation of nine algorithms under various
- View the full text of this paper in
The Proceedings are published as a collective work, © 2002 by the USENIX Association. All Rights Reserved. Rights
to individual papers remain with the author or the author's employer.
Permission is granted for the noncommercial reproduction of the complete
work for educational or research purposes. USENIX acknowledges all
trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
- To become a USENIX Member, please see our Membership Information.