On the effect of inexact size information in size based policies

Recently, there have been a number of scheduling success stories in computer applications. Across a wide array of applications, the simple heuristic of "prioritizing small jobs" has been used to reduce user response times with enormous success. For instance, variants of Shortest-Remaining-Processing-Time (SRPT) and Preemptive-Shortest-Job-First (PSJF) have been suggested for use in web servers [5, 12], wireless applications [6], and databases [8]. As a result of the attention given to size based policies by computer systems researchers, there has been a resurgence in analytical work studying these policies. However, the policies studied in theory, e.g. SRPT and PSJF, are idealized versions of the policies implemented by practitioners. In particular, the intricacies of computer systems force the use of complex hybrid policies in practice, though these more complex policies are still built around the heuristic of "prioritizing small jobs." Thus, there exists a gap between the results provided by theoretical research and the needs of practitioners. This gap results from three primary disconnects between the model studied in theory and the needs of system designers. First, in designing systems, the goal is not simply to provide small response times; other performance measures are also important. Thus, idealized policies such as SRPT and PSJF are often tweaked by practitioners to perform well on secondary performance measures (e.g. fairness and slowdown) [3, 11, 12]. Second, the overhead involved in distinguishing between an infinite number of different priority classes typically causes system designers to discretize policies such as SRPT and PSJF so that they use only a small number of priority classes (5-10) [5, 11]. Third, in many cases information about the service demands (sizes) of jobs is inexact. For instance, when serving static content, web servers have exact knowledge of the sizes of the files being served, but have inexact knowledge of network conditions. Thus, the web server only has an estimate of the true service demand [7, 12]