CaltechAUTHORS
  A Caltech Library Service

Tail-robust scheduling via limited processor sharing

Nair, Jayakrishnan and Wierman, Adam and Zwart, Bert (2010) Tail-robust scheduling via limited processor sharing. Performance Evaluation , 67 (11). pp. 978-995. ISSN 0166-5316. http://resolver.caltech.edu/CaltechAUTHORS:20101124-110928510

[img] PDF - Published Version
Restricted to Repository administrators only
See Usage Policy.

490Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20101124-110928510

Abstract

From a rare events perspective, scheduling disciplines that work well under light (exponential) tailed workload distributions do not perform well under heavy (power) tailed workload distributions, and vice versa, leading to fundamental problems in designing schedulers that are robust to distributional assumptions on the job sizes. This paper shows how to exploit partial workload information (system load) to design a scheduler that provides robust performance across heavy-tailed and light-tailed workloads. Specifically, we derive new asymptotics for the tail of the stationary sojourn time under Limited Processor Sharing (LPS) scheduling for both heavy-tailed and light-tailed job size distributions, and show that LPS can be robust to the tail of the job size distribution if the multiprogramming level is chosen carefully as a function of the load.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1016/j.peva.2010.08.012DOIUNSPECIFIED
Additional Information:© 2010 Elsevier. Available online 16 August 2010.
Subject Keywords:GI/GI/1 queue; Scheduling; Limited processor sharing; Large deviations; Tail asymptotics; Heavy-tailed job size; Light-tailed job size; Tail-robustness
Record Number:CaltechAUTHORS:20101124-110928510
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20101124-110928510
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:21019
Collection:CaltechAUTHORS
Deposited By: Jason Perez
Deposited On:24 Nov 2010 22:49
Last Modified:26 Dec 2012 12:41

Repository Staff Only: item control page