Improving Multiresource Job Scheduling with Markovian Service Rate Policies

Modern cloud computing workloads are composed of multiresource jobs that require a variety of computational resources in order to run, such as CPU cores, memory, disk space, or hardware accelerators. A server can run a set of multiresource jobs in parallel if the total resource demands of those jobs do not exceed the resource capacity of the server. Given a stream of arriving multiresource jobs, a scheduling policy must decide which jobs to run in parallel at every moment in time in order to minimize the mean response time across jobs --- the average time between when a job arrives to the system until it is completed. We develop and analyze a new class of policies for scheduling multiresource jobs called Markovian Service Rate (MSR) policies. An MSR policy precomputes several candidate schedules, sets of jobs that can run in parallel, and then switches between these candidate schedules randomly according to a continuous-time Markov chain. While prior scheduling policies are either computationally complex, analytically intractable, or result in high mean response time, we develop an analysis of MSR policies to prove that they are both computationally simple and can guarantee low mean response time. We also show that these policies perform well in practice using simulations based on traces from the Google Borg cluster scheduler. This abstract summarizes our full paper.