Idletime Scheduling with Preemption Intervals

This dissertation presents idletime scheduling, an operating system scheduling mechanism for using idle resource capacity in the background without slowing down concurrent foreground use of the system. Executing less important tasks using background capacity increases system efficiency and user-perceived performance. Operating systems fail to support transparent background capacity use: most schedulers provide only fair sharing, which can reduce foreground performance by 50% or more.

The idletime scheduler limits the impact of background use on concurrent foreground processing. It partially relaxes the work conservation principle during short preemption intervals. It provides a generic mechanism that can accommodate resources with performance characteristics that vary by orders of magnitude. The preemption interval length controls the behavior of the mechanism: short intervals aggressively utilize idle capacity; long intervals reduce the impact on foreground performance.

Experiments with an implementation for idletime network scheduling in FreeBSD maintain over 90% of foreground TCP throughput, while allowing concurrent, high-rate UDP background flows to consume up to 80% link capacity. A disk scheduler implementation maintains 80% of foreground read performance, while enabling concurrent background accesses to reach up to 70% throughput. A quantitative analysis of idletime scheduling predicts the measured performances with an error below 15%. In both cases, as well as other experiments, the idletime scheduler effectively limits the impact of background use on foreground performance.