Achieving service rate objectives with decay usage scheduling

Decay usage scheduling is a priority- and usage-based approach to CPU allocation in which preference is given to processes that have consumed little CPU in the recent past. The author develops an analytic model for decay usage schedulers running compute-bound workloads, such as those found in many engineering and scientific environments; the model is validated from measurements of a Unix system. This model is used in two ways. First, ways to parameterize decay usage schedulers are studied to achieve a wide range of service rates. Doing so requires a fine granularity of control and a large range of control. The results show that, for a fixed representation of process priorities a larger range of control makes the granularity of control coarser, and a finer granularity of control decreases the range of control. A second use of the analytic model is to construct a low overhead algorithms for achieving service rate objectives. Existing approaches require adding a feedback loop to the scheduler. This overhead is avoided by exploiting the feedback already present in decay usage schedulers. Using both empirical and analytical techniques, it is shown that the algorithm is effective and that it provides fairness when the system is over- or under-loaded