CPU reservations and time constraints

Publisher Website
Google Scholar
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 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: 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.

This publication has 13 references indexed in Scilit: