Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 2012 | metadata_only
Journal Article

Many Flows Asymptotics for SMART Scheduling Policies


Scheduling policies that favor small jobs have received growing attention due to their superior performance with respect to mean delay, e.g., Shortest Remaining Processing Time (SRPT) and Preemptive Shortest Job First (PSJF). In this paper, we study the delay distribution of a generalization of the class of scheduling policies called SMART (because policies in it have "SMAll Response Times"), which includes SRPT, PSJF, and a range of practical variants, in a discrete-time queueing system under the many sources large deviations regime. Our analysis of SMART in this regime (large number of flows and large capacity) hinges on a novel two-dimensional (2-D) queueing framework that employs virtual queues and total ordering of jobs. We prove that all SMART policies have the same asymptotic delay distribution as SRPT, i.e., the delay distribution has the same decay rate. In addition, we illustrate the improvements SMART policies make over First Come First Serve (FCFS) and Processor Sharing (PS). Our 2-D queueing technique is generalizable to other policies as well. As an example, we show how the Foreground-Background (FB) policy can be analyzed using a 2-D queueing framework. FB is a policy, not contained in SMART, which manages to bias towards small jobs without knowing which jobs are small in advance.

Additional Information

© 2011 IEEE. Manuscript received March 31, 2010; accepted June 26, 2011. Date of publication October 25, 2011; date of current version January 27, 2012. This paper was presented in part at the Proceedings of ACM Sigmetrics, June 2006. Recommended by Associate Editor S. Mascolo.

Additional details

August 22, 2023
August 22, 2023