HLS: A Framework for Composing Soft Real-Time Schedulers

John Regehr and John A. Stankovic


University of Utah, School of Computing
50 South Central Campus Drive, Room 3190
Salt Lake City, Utah 84112-9205

Department of Computer Science
School of Engineering and Applied Science
University of Virginia
151 Engineer's Way, P.O. Box 400740
Charlottesville, VA 22904-4740


Hierarchical CPU scheduling has emerged as a way to (1) support applications with diverse scheduling requirements in open systems, and (2) provide load isolation between applications, users, and other resource principals. Most existing work on hierarchical scheduling has focused on systems that provide a fixed scheduling model: the schedulers in part or all of the hierarchy are specified in advance. In this paper we describe a system of guarantees that permits a general hierarchy of soft real-time schedulers -- one that contains arbitrary scheduling algorithms at all points within the hierarchy -- to be analyzed. This analysis results in deterministic guarantees for threads at the leaves of the hierarchy. We also describe the design, implementation, and performance evaluation of a system for supporting such a hierarchy in the Windows 2000 kernel. Finally, we show that complex scheduling behaviors can be created using small schedulers as components and describe the HLS programming environment.

In Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS 2001), pages 3-14, London, UK, December 3-6 2001.

Copyright 2001 IEEE.

Citation information:

  author =       "John Regehr and John A. Stankovic",
  title =        "{HLS}: {A} Framework for Composing Soft Real-Time
  booktitle =    "Proceedings of the 22nd IEEE Real-Time Systems
                 Symposium (RTSS 2001)",
  pages =        "3--14",
  address =      "London, UK",
  month =        dec,
  year =         "2001",

John Regehr <regehr@cs.utah.edu>
Last modified: Fri May 31 10:45:28 MDT 2002