Scheduling of a Relaxed Backfill Strategy with Multiple Reservations

Backfilling is well known in parallel job scheduling to increase system utilization and user satisfaction over traditional non-backfilling scheduling algorithms, which allow small jobs from the back of the queue to execute before larger jobs arriving earlier, and resources could be reserved to protect the latter from starvation. This paper proposed a relaxed backfill scheduling mechanism supporting multiple reservations, and investigated its effectiveness in reducing the average waiting time and average slowdown of jobs by using simulations with real traces. Different from existing relaxed scheduling, which restrict the maximum number of reservations to one, this new mechanism can support the relaxation of multiple reservations and works efficiently in scheduling by successful avoidance of raising chain reactions in relaxing the start times of multiple already existing reservations. Experimental results suggest that although the performances of both the relax-based backfilling and the strict backfill depend on the accuracy of runtime estimates, reservation depths, traces and system load alike, the former scheduling is more flexible and generally more effective in reducing the average waiting time and average slowdown of jobs, without loss of utilization.