An Analytical Treatment of Policy Function Schedulers

This paper presents an analysis of time-sharing computer facilities using scheduling algorithms defined in terms of priority functions. We consider the class of algorithms in which a job's priority is defined by the difference between the time it spent in the system and an arbitrary function F of its attained service, where F is called the policy function. Our main result, the average response time for a job conditioned on its service requirement, applies to a broad class of policy functions. The derivation is based on the model of a processor-sharing M/G/1 queuing system and does not use transforms. The analysis is simplified by the decomposition of a non-Markovian process. Properties of the average response time resulting from policy function schedulers are discussed and related to those of other known time-sharing scheduling algorithms. For the examples of linear, exponential, and composite policy functions we plot the response times. We demonstrate the flexibility and the limitations of policy functions with respect to the discriminatory treatment of short jobs versus long ones and discuss the optimal selection of a policy function with respect to a given overall performance criterion.