CMU-CS-02-118
Computer Science Department
School of Computer Science, Carnegie Mellon University


CMU-CS-02-118

Asymptotic Convergence of Scheduling Policies with Respect to Slowdown

Mor Harchol-Balter, Karl Sigman*, Adam Wierman

April 2002

CMU-CS-02-118.ps
CMU-CS-02-118.pdf


Keywords: Scheduling, service discipline, M/G/1, slowdown, large jobs, convergence, limiting, work conserving, SRPT, shortest remaining processing time, PS, processor sharing, LRPT, longest remaining processing time


We explore the performance of an M/GI/1 queue under various scheduling policies from the perspective of a new metric: the slowdown experienced by largest jobs. We consider scheduling policies that bias against large jobs, towards large jobs, and those that are fair, e.g., Processor-Sharing. We prove that as job size increases to infinity, all work conserving policies converge almost surely with respect to this metric to no more than 1/(1 - p), where p denotes load. We also find that the expected slowdown under any work conserving policy caXn be made arbitrarily close to that under Processor-Sharing, for all job sizes that are sufficiently large.

19 pages

Mor Harchol-Balter, harcol@cs,cmu.edu
Adam Wierman, [email protected]

*Department of Industrial Engineering and Operations Research, Columbia University, [email protected]

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]