Job scheduling in the presence of multiple resource requirements

In past massively parallel processing systems, such as the Intel Paragon and the Thinking Machines CM-5, the scheduling problem consisted of allocating a single type of resource among the waiting jobs; the processing node. A job was allocated the minimum number of nodes required to meet its largest resource requirement (e.g. memory, CPUs, I/O channels, etc.). Recent systems, such as the SUN E10000 and SGI O2K, are made up of pools of independently allocatable hardware and software resources such as shared memory, large disk farms, distinct I/O channels, and software licenses. In order to make efficient use of all the available system resources, the scheduling algorithm must be able to maintain a job working set which fully utilizes all of the resources. Previous work in scheduling multiple resources focused on coordinating the allocation of CPUs and memory, using ad-hoc methods for generating good schedules. We provide new job selection heuristics based on resource balancing which support the construction of generalized K-resource scheduling algorithms. We show through simulation that performance gains of up to 50% in average response time are achievable over classical scheduling methods such as First-Come-First-Served with First-Fit backfill.