Graduate School and Research Center in Digital Sciences

Revisiting size-based scheduling with estimated job sizes

Dell'Amico, Matteo; Carra, Damiano; Pastorelli, Mario; Michiardi, Pietro

MASCOTS 2014, IEEE 22nd International Symposium on Modeling analysis and simulation of computer and telecommunication systems, September 9-11, 2014, Paris, France / Also published on ArXiv

We study size-based schedulers, and focus on the impact of inaccurate job size information on response time and fairness. Our intent is to revisit previous results, which allude to performance degradation for even small errors on job size estimates, thus limiting the applicability of size-based schedulers. We show that scheduling performance is tightly connected to workload characteristics: in the absence of large skew in the job size distribution, even extremely imprecise estimates suffice to outperform size-oblivious disciplines. Instead, when job sizes are heavily skewed, known size-based disciplines suffer. In this context, we show - for the first time - the dichotomy of over-estimation versus under-estimation. The former is, in general, less problematic than the latter, as its effects are localized to individual jobs. Instead, under-estimation leads to severe problems that may affect a large number of jobs. We present an approach to mitigate these problems: our technique requires no complex modifications to original scheduling policies and performs very well. To support our claim, we proceed with a simulation-based evaluation that covers an unprecedented large parameter space, which takes into account a variety of synthetic and real workloads. As a consequence, we show that size-based scheduling is practical and outperforms alternatives in a wide array of usecases, even in presence of inaccurate size information. 

Document Doi Arxiv Bibtex

Title:Revisiting size-based scheduling with estimated job sizes
Department:Data Science
Eurecom ref:4268
Copyright: © 2014 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @inproceedings{EURECOM+4268, doi = {}, year = {2014}, title = {{R}evisiting size-based scheduling with estimated job sizes}, author = {{D}ell'{A}mico, {M}atteo and {C}arra, {D}amiano and {P}astorelli, {M}ario and {M}ichiardi, {P}ietro}, booktitle = {{MASCOTS} 2014, {IEEE} 22nd {I}nternational {S}ymposium on {M}odeling analysis and simulation of computer and telecommunication systems, {S}eptember 9-11, 2014, {P}aris, {F}rance / {A}lso published on {A}r{X}iv}, address = {{P}aris, {FRANCE}}, month = {03}, url = {} }
See also: