CPU reservations and time constraints
Michael B. Jones, Daniela Roşu, Marcel‐Cătălin Roşu · 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 nonreal-time workloads.This paper presents a system that can schedule multiple independent activities so that: activities can obta& 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 executedfor 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: l activities cannot violate other activities' guarantees, l 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 l 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.