CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities - Jones, Mike; Rosu, Marcel-C. (Association for Computing Machinery, Inc., 1997)
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.