Comparison Of Backfilling Algorithms For Job Scheduling In Distributed Memory Parallel System

In this paper, we compare the performance of backfilling scheduling algorithms using multiplequeue and look-ahead with the basic aggressive strategy on a multiprocessor system. Schedulers employing backfilling algorithms in distributed-memory parallel system have been found to improve system utilization and job response time by allowing smaller jobs from back of the waiting queue to execute before the larger jobs which have arrived earlier. Backfilling algorithms also overcome the problem of starvation and waste of processing resources exhibited by algorithms like shortest job first and longest job first. We have implemented the backfilling scheduling algorithms with basic aggressive, multiple-queue, and with look-ahead strategy. We compare their performances and investigate the conditions for increasing the utilization and decreasing the fragmentation of the system resources. The look-ahead backfilling scheduling algorithm attempts to find the best packing possible given the current composition of the queue, thus maximizing the utilization at every scheduling step. It reduces the mean response time of all jobs. We use simulation to evaluate the performance of the scheduling disciplines.