RB-FIFIT—A Cluster Job Scheduling Algorithm Combining Firstfit, Reservation and Backfilling

Cluster job management is an essential part of cluster system software, with job scheduling algorithm being the core of cluster job management system. Different job scheduling strategy affects both efficiency of the cluster system and job response time. Firstfit scheduling algorithm is a well-rounded algorithm and has been widely developed in cluster job management systems. Conventional Firstfit algorithm focuses on mitigating resource fragmentation while missing the problem of job starvation. JMS is the Job Management System for Dawning Super Server, with P-FIFT （priority-based firstfit） being the job scheduling algorithm for it. In this paper, with consideration of the reservation algorithm and backfilling algorithm, RB-FIFT job scheduling algorithm is proposed as an improved job scheduling algorithm for JMS. A new experimental result shows that comparing to conventional Firstfit algorithm and P-FIFT, RB-FIFT can solve both the issues of job starvation and resource fragmentation, which improves the throughput and resource utilization of the system.