A Caltech Library Service

On the effect of inexact size information in size based policies

Wierman, Adam (2006) On the effect of inexact size information in size based policies. ACM SIGMETRICS Performance Evaluation Review, 34 (3). pp. 21-23. ISSN 0163-5999. doi:10.1145/1215956.1215966.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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].

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2006 Association for Computing Machinery. I am grateful to Varun Gupta and Misja Nuyens for there helpful feedback on developing the SMART, class, and for all of the valuable feedback I received at the MAMA workshop.
Issue or Number:3
Record Number:CaltechAUTHORS:20201104-085827475
Persistent URL:
Official Citation:Adam Wierman. 2006. On the effect of inexact size information in size based policies. SIGMETRICS Perform. Eval. Rev. 34, 3 (December 2006), 21–23. DOI:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106422
Deposited By: Tony Diaz
Deposited On:04 Nov 2020 19:41
Last Modified:16 Nov 2021 18:54

Repository Staff Only: item control page