Fattened backfilling: An improved strategy for job scheduling in parallel systems

摘要

Job scheduling is a very important topic in parallel systems. Although there exist algorithms that theoretically provide optimal performance, in general, they are too complex for implementation in real production systems. The simplest and most feasible approach that provides efficient and fair scheduling is backfilling. In fact, backfilling is used in many real production systems. Scheduling policies have been widely studied and discussed, but there is still a big field of research to be explored, since most scheduling algorithms are motivated by performance, but also by the psychology of queuing and the fairness concept. In this article, we propose an algorithm (fattened backfilling) that provides more backfilling opportunities, and is consequently more efficient. In particular, our algorithm allows short jobs to move forward if they do not delay the first job of the queue more than the average waiting time of the already finished jobs. The results of our simulations show a great improvement in response time and waiting time in most of the cases, with improved or similar slowdown values. Hence, we can conclude that fattened backfilling outperforms conservative and EASY backfilling, and, due to its simplicity, it is recommended for implementation in modern scheduling systems.