Premium
Backfilling with guarantees made as jobs arrive
Author(s) -
Lindsay A. M.,
GallowayCarson M.,
Johnson C. R.,
Bunde D. P.,
Leung V. J.
Publication year - 2012
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.2860
Subject(s) - exploit , scheduling (production processes) , computer science , flexibility (engineering) , bounded function , function (biology) , extensibility , selection (genetic algorithm) , job scheduler , operations research , mathematical optimization , engineering , mathematics , economics , operating system , machine learning , management , computer security , cloud computing , mathematical analysis , evolutionary biology , biology
SUMMARY In this paper, we present scheduling algorithms that simultaneously support guaranteed starting times and favor jobs with system‐desired traits. To achieve the first of these goals, our algorithms keep a profile with potential starting times for every unfinished job and never move these starting times later, just as in Conservative Backfilling. To achieve the second, they exploit previously unrecognized flexibility in the handling of holes opened in this profile when jobs finish early. We find that, with one choice of job selection function, our algorithms can consistently reduce average waiting time and average bounded slowdown relative to Conservative Backfilling while still providing a guaranteed start time to each job as it arrives. In fact, in most cases, the algorithms give better performance than the more aggressive Extensible Argonne Scheduling System (EASY) backfilling algorithm, which does not provide guaranteed start times. Alternately, with a different choice of job selection function, our algorithms can focus the benefit on the widest submitted jobs, the reason for the existence of parallel systems. In this case, these jobs experience significantly lower waiting times than Conservative Backfilling with minimal impact on other jobs. Copyright © 2012 John Wiley & Sons, Ltd.