Abstract

It has been a central research topic to schedule job over appropriate computing nodes of clusters in the research of cluster computing so far. In existing researches about such topic, the FCFS algorithm (First-Come-First-Served Algorithm) is commonly used due to its simplicity. Backfilling scheduling that small jobs are moved ahead in the schedule can fill the resources gap that is generated by FCFS. However, existing backfilling scheduling algorithms are only available for one queued job backfilled to schedule and generate waste of some resource gaps. In this paper, the problem of the parallel job scheduling in clusters is studied. We present an efficient and effective algorithm based combinational backfilling strategy, which can select multiple jobs combined from the waiting job queue to backfill to maximize the use of idle resources. An empirical study verifies that our algorithm can attain the lower average waiting time of jobs and higher utilization of resources than existing representative backfilling algorithms.

Paper Details