A Framework for Implementing Objects and Scheduling Tasks in Lock-Free Real-Time Systems

J.H. Anderson, and S. Ramamurthy
Proceedings of the 17th IEEE Real-Time Systems Symposium
Washington, DC, December 1996
(to appear).

Abstract: We present an integrated framework for developing real-time systems in which lock-free algorithms are employed to implement shared objects. There are two key objectives of our work. The first is to enable functionality for object sharing in lock-free real-time systems that is comparable to that in lock-based systems. Our main contribution toward this objective is an efficient approach for implementing multi-object lock-free operations and transactions. A second key objective of our work is to improve upon previously proposed scheduling conditions for tasks that share lock-free objects. When developing such conditions, the key issue is to bound the cost of operation ``interferences''. We present a general approach for doing this, based on linear programming. Experimental results are presented that show that lock-free objects implemented within our framework outperform lock-based implementations in a variety of settings. These experiments involve tasks that perform single- and multi-object operations on queues and balanced trees.

Get a PostScript copy of this paper.

Back to Real-Time Systems Research at UNC page.