usenix conference policies
You are here
Improving Wait-Free Algorithms for Interprocess Communication in Embedded Real-Time Systems
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 experimental conditions.
author = {Hai Huang and Padmanabhan Pillai and Kang G. Shin},
title = {Improving {Wait-Free} Algorithms for Interprocess Communication in Embedded {Real-Time} Systems},
booktitle = {2002 USENIX Annual Technical Conference (USENIX ATC 02)},
year = {2002},
address = {Monterey, CA},
url = {https://www.usenix.org/conference/2002-usenix-annual-technical-conference/improving-wait-free-algorithms-interprocess},
publisher = {USENIX Association},
month = jun
}
connect with us