Attacking the Bottlenecks in Backfilling Schedulers

In Cluster Computing: The Journal of Networks, Software Tools and Applications, 3(4): 2000.

Pete Keleher, Dmitry Zotkin, and Dejan Perkovic

Backfilling is a simple and effective way of improving the utilization of space-sharing schedulers. Simple first-come-first-served approaches are ineffective because large jobs can fragment the available resources. Backfilling schedulers address this problem by allowing jobs to move ahead in the queue, provided that they will not delay subsequent jobs.

Previous research has shown that inaccurate estimates of execution times can lead to better backfilling schedules. We characterize this effect on several workloads, and show that average slowdowns can be effectively reduced by systematically lengthening estimated execution times. Further, we show that the average job slowdown metric can be addressed directly by sorting jobs by increasing execution time. Finally, we modify our sorting scheduler to ensure that incoming jobs can be given hard guarantees. The resulting scheduler guarantees to avoid starvation, and performs significantly better than previous backfilling schedulers.

	title = "Attacking the Bottlenecks in Backfilling Schedulers",
	author = "Pete Keleher and Dmitry Zotkin and Dejan Perkovic",
	journal = {Cluster Computing: The Journal of Networks},
	volume = {3},
	issue = {4},
	year = {2000},

Available: bibtex, abstract,