Impact of Extending the Runtime of Underestimated Jobs in Backfilling Schedulers

In standard backfill algorithms, a job will be terminated immediately it has been processed for its estimated runtime. This drives users not to provide tight estimates to make their jobs to be scheduled earlier but at the risk of being killed. This paper presents an enhanced mechanism to tolerate underestimated jobs by continuing processing them on condition that they will not delay any other running or reserved jobs. By comparing the performance of this new mechanism with that of the standard easy backfill with simulation of real workloads, it is shown that the benefits of extending the runtime of underestimated jobs are attractive and the possible degradations are very slight.