CMU-CS-03-199Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-03-199
Adam Wierman, Mor Harchol-Balter November 2003
CMU-CS-03-199.ps
Keywords: Scheduling, queueing, SRPT, shortest remaining processing
time, PSJF, preemptive shortest job first, M/GI/1, response time, SMART
For many policies in the SMART class, the mean response time and mean slowdown are not known or have complex representations involving multiple nested integrals, making evaluation difficult. In this work, we prove three main results. First, for all policies in the SMART class, we prove simple upper and lower bounds on mean response time. In particular, we focus on the SRPT and PSJF policies and prove even tighter bounds in these cases. Second, we show that all policies in the SMART class, surprisingly, have very similar mean response times. Third, we show that the response times of SMART policies are largely invariant to the variability of the job size distribution. 15 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |