Tata Institute of Fundamental Research

Tail-robust Scheduling via Limited Processor Sharing

Speaker: Mr. Jayakrishnan Nair California Institute of Technology Department of Electrical Engineering MC 305-16 Pasad
Date: Thursday, 5 Aug 2010 (all day)
Venue: A-212 (STCS Seminar Room)

(Scan to add to calendar)
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. We show 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.