Policy function scheduling

Scheduling disciplines have traditionally been specified in terms of a queue structure and algorithms for routing jobs within this structure. Alternatively, a discipline may be formally defined by a policy function, a function of job and system parameters. A policy function scheduler is a parameterized scheduler that — when supplied with a specific policy function — behaves like the specified discipline. The formal definition allows performance measures of a discipline (e.g., the response function) to be expressed in terms of the defining policy function. We review the principles of formal definitions, summarize previous queueing-theoretical results concerning response functions of policy function schedulers, and extend them to multiple preemptive job classes with processor-sharing subclasses. For a large variety of disciplines and job classes, we also express the policy functions in terms of the resulting response functions. Given a desired realizable performance goal, this relation serves to determine the discipline that achieves it. Policy function schedulers with their explicit relation between policy and response functions, which we plot for several different job characteristics, thus offer increased precision in controlling the performance of a computer system.