Ecole d'ingénieur et centre de recherche en Sciences du numérique

On fair size-based scheduling

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

Submitted on 30 June 2015, On ArXiv

By executing jobs serially rather than in parallel, size-based scheduling policies can shorten time needed to complete jobs; however, major obstacles to their applicability are fairness guarantees and the fact that job sizes are rarely known exactly a-priori. Here, we introduce the Pri family of size-based scheduling policies; Pri simulates any reference scheduler and executes jobs in the order of their simulated completion: we show that these schedulers give strong fairness guarantees, since no job completes later in Pri than in the reference policy. In addition, we introduce PSBS, a practical implementation of such a scheduler: it works online (i.e., without needing knowledge of jobs submitted in the future), it has an efficient O(log n) implementation and it allows setting priorities to jobs. Most importantly, unlike earlier size-based policies, the performance of PSBS degrades gracefully with errors, leading to performances that are close to optimal in a variety of realistic use cases.

Arxiv Bibtex

Titre:On fair size-based scheduling
Département:Data Science
Eurecom ref:4630
Copyright: © EURECOM. Personal use of this material is permitted. The definitive version of this paper was published in Submitted on 30 June 2015, On ArXiv and is available at :
Bibtex: @inproceedings{EURECOM+4630, year = {2015}, title = {{O}n fair size-based scheduling}, author = {{D}ell'{A}mico, {M}atteo and {C}arra, {D}amiano and {M}ichiardi, {P}ietro}, booktitle = {{S}ubmitted on 30 {J}une 2015, {O}n {A}r{X}iv}, address = {}, month = {06}, url = {} }
Voir aussi: