CPU Reservations and Time Constraints:
Efficient, Predictable Scheduling of Independent Activities

Michael B. Jones, Daniela Rosu, and Marcel-Catalin Rosu

Formats
HTML (111 KBytes)
Word '97 (1647 KBytes)
PostScript (2101 KBytes)
PowerPoint Presentation (217 KBytes)
SOSP '97 CD-ROM data

Abstract

Workstations and personal computers are increasingly being used for applications with real-time characteristics such as speech understanding and synthesis, media computations and I/O, and animation, often concurrently executed with traditional non-real-time workloads. This paper presents a system that can schedule multiple independent activities so that:

• activities can obtain minimum guaranteed execution rates with application-specified reservation granularities via CPU Reservations,
• CPU Reservations, which are of the form "reserve X units of time out of every Y units", provide not just an average case execution rate of X/Y over long periods of time, but the stronger guarantee that from any instant of time, by Y time units later, the activity will have executed for at least X time units,
• applications can use Time Constraints to schedule tasks by deadlines, with on-time completion guaranteed for tasks with accepted constraints, and
• both CPU Reservations and Time Constraints are implemented very efficiently. In particular,
• CPU scheduling overhead is bounded by a constant and is not a function of the number of schedulable tasks.

Other key scheduler properties are:

• activities cannot violate other activities' guarantees,
• time constraints and CPU reservations may be used together, separately, or not at all (which gives a round-robin schedule), with well-defined interactions between all combinations, and
• spare CPU time is fairly shared among all activities.

The Rialto operating system, developed at Microsoft Research, achieves these goals by using a precomputed schedule, which is the fundamental basis of this work.

Published in the Proceedings of the 16^th ACM Symposium on Operating Systems Principles (SOSP), Saint-Malo, France, pages 198-211, October, 1997.

Permission to make digital/hard copy of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication and its date appear, and notice is given that copying is by permission of ACM, Inc. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

SIGOPS '97 10/97 Saint-Malo, France