Tail-robust scheduling using Limited Processor Sharing.

J.K. Nair, A. Wierman, A.P. Zwart

Research output: Contribution to JournalArticleAcademicpeer-review


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. © 2010 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)978-995
JournalPerformance Evaluation
Issue number11
Publication statusPublished - 2010


Dive into the research topics of 'Tail-robust scheduling using Limited Processor Sharing.'. Together they form a unique fingerprint.

Cite this