@techreport{HarcholBalterCrovellaPark98,
  author	= {Harchol-Balter, M. and Crovella, M. E. and Park, S.},
  title		= {The Case for {SRPT} Scheduling in {Web} Servers},
  institution	= {MIT Lab for Computer Science},
  year		= {1998},
  month		= oct,
  number	= {MIT-LCS-TR-767},
  URL		= {http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-767.pdf},
  abstract	= {The Shortest-Remaining-Processing-Time (SRPT) scheduling policy is known to be the optimal policy for minimizing mean response time, but it is rarely employed in computing systems for a number of reasons. These reasons include: lack of knowledge of task size, fear of starvation of the large tasks, concern over pre-emption overhead, and lack of empirical evidence on the performance benefits of switching to SRPT. In this paper we argue that the special characteristics of Web servers and Web workloads make the usual objections to SRPT less persuasive. We start by arguing that it is possible for Web servers to extract task sizes for a large fraction of tasks. We then compare SRPT to an alternative policy (processor sharing (PS)) which we use as an idealization of typical scheduling policies currently used in Web servers. Our comparisons are made both analytically (assuming Poisson arrivals and an empirically-derived file size distribution) and on trace-driven simulations using logs from operating Web servers. With respect to performance, we show that at high server utilization, the SRPT policy can reduce mean waiting time and mean slowdown over PS by well over an order of magnitude. With respect to our main concern, starvation, we show that although starvation is in fact a problem under SRPT for many workloads, in the particular case of Web workloads, starvation even for the largest one percent of all tasks is far lower under SRPT than under PS. Lastly, we argue that pre-emption overhead is lower under SRPT than under currently used policies. Although our model is a simplified model of real Web servers, our results suggest that SRPT is an attractive alternative to current scheduling policies in Web servers.}
}