Implementing Wait-Free Objects on Priority-Based Systems

J. Anderson, S. Ramamurthy, and R. Jain, and
16th Annual ACM Symposium on the Principles of Distributed Computing
to appear.

Abstract: Wait-free objects are often implemented through the use of a "helping scheme," whereby one process "helps" one or more other processes to complete an operation. This paper presents several new helping schemes that can be generally applied to efficiently implement a variety of different objects on priority-based uniprocessor and multiprocessor systems. Examples of such systems include lock-free multiprocessor kernels and real-time systems. Our helping schemes reduce overhead by exploiting the way in which processes are scheduled for execution in priority-based systems. We illustrate the use of these schemes by presenting wait-free implementations of linked lists and a multi-word compare-and-swap primitive. Performance results are presented that show that on priority-based systems our object implementations are an improvement over implementations developed previously for asynchronous systems.

Get PostScript copy of this paper.

Back to Real-Time Systems Research at UNC page.