Efficient Object Sharing in Quantum-Based Real-Time Systems

J.H. Anderson, R. Jain, and K. Jeffay
Proceedings of the 19th IEEE Real-Time Systems Symposium
Madrid, Spain, December 1998
pages 346-355.

Abstract: We consider the problem of implementing shared objects in uniprocessor and multiprocessor real-time systems in which tasks are executed using a scheduling quantum. In most quantum-based systems, the size of the quantum is quite large in comparison to the length of an object call. As a result, most object calls can be expected to execute without preemption. A good object-sharing scheme should optimize for this expected case, while achieving low overhead when preemptions do occur. Our approach is to use an optimistic retry scheme coupled with the assumption that each task can be preempted at most once across two object calls. Given this preemption assumption, each object call can be retried at most once. Experimental evidence is cited that suggests that for most quantum-based systems, our preemption assumption is reasonable. Major contributions of this paper include several new retry-based shared-object algorithms for uniprocessors and multiprocessors, and scheduling analysis results that can be used in conjunction with these algorithms. We consider both conventional periodic real-time task systems implemented using a scheduling quantum, and also proportional-share systems. The retry mechanism used in our multiprocessor implementation is based on a preemptable queue-lock algorithm. Our queue-lock is much simpler than preemptable queue locks proposed previously. Experimental results are presented that show that the performance of our lock is up to 25% better than one presented at last year's RTSS, when applied in quantum-based systems.

Get a PostScript - or - PDF copy of this paper.
(An extended version of this paper is also available in PostScript and PDF form.

Back to Real-Time Systems Research at UNC page.