Tail-robust Scheduling via Limited Processor Sharing

Speaker: 

Mr. Jayakrishnan Nair California Institute of Technology Department of Electrical Engineering MC 305-16 Pasad

Time: 

Thursday, 5 August 2010 (All day)

Venue: 

  • A-212 (STCS Seminar Room)

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.