Improving Nonpreemptive Multiserver Job Scheduling with Quickswap

Modern data center workloads are composed of multiserver jobs that require multiple servers in order to run. Many multiserver jobs can run in parallel as long as there are enough servers to satisfy the demand of each job. Given a stream of arriving jobs, a scheduling policy must determine which jobs to run at every moment in time to minimize the mean response time across jobs — the average time from when a job arrives to the system until it is complete. Because preemptions are often computationally expensive in data centers, the scheduling policy cannot preempt running jobs. We propose a new class of non-preemptive policies called Most Servers First with Quickswap (MSFQ). MSFQ policies prioritize jobs that demand more servers. However, they keep mean response time low by periodically granting priority to other jobs in the system. We prove conditions under which MSFQ policies stabilize the system, and analyze their mean response time. We prove that the MSFQ priority switching mechanism allows these policies to greatly outperform state-of-the-art policies that rely on simpler priority mechanisms. We validate our theoretical results via extensive simulations using traces from the Google Borg system.