Time-function scheduling: A general approach to controllable resource management

Abstract

A large number of diverse scheduling objectives have been proposed and used in various operating system designs, including absolute/relative throughput and response time measures, predictable (i. e., low variance) performance, proportional resource allocation, avoiding indefinite postponement, and satisfying real-time constraints. Many of these objectives are in conflict, and thus most scheduling algorithms have been designed to meet only a subset of these goals. In addition to supporting multiple diverse scheduling objectives, a principal design challenge is to provide effective control over resource allocation to achieve the desired performance requirements for these simultaneous objectives. Unfortunately, most scheduling strategies do not support flexible parameterization of their algorithms to satisfy the varying performance requirements of different environments. Over the past several years we have been exploring the use of time-based functions to provide effective and flexible control over resource allocation to achieve the above scheduling objectives and performance requirements. This paper describes a general approach to resource management called time-function scheduling (TFS), which represents a generalization of our previous research activities. TFS is based on the concept of dynamic priorities that change according to general functions of the time each job has spent waiting for the resource of interest, although functions of measures other than waiting time can be used. A large and diverse set of scheduling objectives and performance requirements is achieved by employing time-functions with properties that match these requirements. Moreover, various mechanisms can be used to dynamically adjust these time-functions in response to changes in the system workload so that the desired objectives are continuously satisfied. These properties are achieved by exploiting the strong theoretical foundation of our approach, which is in stark contrast to the ad hoc and poorly understood methods employed in most existing resource allocation technologies. © 1995 ACM.