Using Hierarchical Scheduling to Support
Soft Real-Time Applications
in General-Purpose Operating Systems

A Dissertation
Presented to
the faculty of the School of Engineering and Applied Science
University of Virginia

In Partial Fulfillment
of the requirements for the Degree
Doctor of Philosophy
Computer Science

by

John D. Regehr

May 2001

Copyright, Abstract, Acknowledgments, Quotes
List of Figures, List of Tables
1 Introduction
 1.1 Motivation
 1.2 The Thesis
 1.3 Reasons to Use and Understand Hierarchical Scheduling
 1.4 Overview of the HLS
 1.5 Scope of the Dissertation
 1.6 Contributions
 1.7 Outline of the Dissertation
2 A Survey of Multimedia Programming Models
 2.1 Introduction
 2.2 Multimedia System Requirements
 2.3 Basis of a Taxonomy
 2.4 Applications Characterized
 2.5 Challenges for Practical Soft Real-Time Scheduling
 2.6 Conclusions
3 Application Scenarios
 3.1 A Machine Providing Virtual Web Servers
 3.2 A Home Computer
 3.3 A Corporate or Departmental Terminal Server
 3.4 Coping with Inflexible Scheduling
4 Design of the Hierarchical Scheduler Infrastructure
 4.1 Goals and Requirements
 4.2 Entities in the Scheduler Infrastructure
 4.3 The Loadable Scheduler Programming Model
 4.4 Scheduler Infrastructure Example
 4.5 Conclusion
5 Composing Scheduling Policies
 5.1 Guarantees
 5.2 Soft Real-Time Guarantees
 5.3 Converting Between Guarantees
 5.4 Conclusion
6 Issues and Examples for Scheduler Composition
 6.1 Guarantees for Multithreaded Applications
 6.2 Synthesizing Complex Behaviors from Simple Schedulers
 6.3 Other Topics
 6.4 Conclusion
7 Scheduling the Application Scenarios
 7.1 A Machine Providing Virtual Web Servers
 7.2 A Home Computer
 7.3 A Corporate or Departmental Terminal Server
 7.4 Conclusions
8 The Resource Manager
 8.1 Introduction
 8.2 Entities in the Resource Manager
 8.3 Guarantee Acquisition
 8.4 CPU Allocation Rules
 8.5 Supporting Unmodified Applications
 8.6 Implementation
 8.7 Doing Without the Resource Manager
 8.8 Conclusions
9 Implementation of HLS in a General-Purpose OS
 9.1 Background and Implementation-Level Design Decisions
 9.2 Implementation of the Hierarchical Scheduler Infrastructure
 9.3 Schedulers Implemented
 9.4 HLS Implementation Experience
 9.5 Conclusion
10 Performance Evaluation of HLS
 10.1 Test Environment and Methodology
 10.2 Cost of Basic HLS Operations
 10.3 Context Switch Times
 10.4 Overhead of High-Frequency Timer Interrupts
 10.5 Solving Problems Using Hierarchical Scheduling
 10.6 Optimizing HLS
 10.7 Conclusion
11 Augmented CPU Reservations
 11.1 Augmented Reservations and Guarantees
 11.2 Motivation: Time Stolen by the Network Stack
 11.3 Characterization of Stolen Time
 11.4 Approach
 11.5 Coping with Stolen Time
 11.6 Experimental Evaluation of Rez-C and Rez-FB
 11.7 Other Criteria for Evaluating Rez-C and Rez-FB
 11.8 Stolen Time in Other Systems and by Other Devices
 11.9 Other Approaches and Related Work
 11.10 Conclusions
12 Related Work
 12.1 Hierarchical Scheduling
 12.2 Resource Management for the CPU
13 Conclusions
 13.1 Summary of Contributions
 13.2 Future Work
A Glossary
B The Loadable Scheduler Interface
 B.1 Data Structures
 B.2 Functions Available to Schedulers
 B.3 Constants, Variables, and Types
 B.4 Functions for Loading and Unloading a Scheduler
C An Example Scheduler
Bibliography