Non-preemptive Datacenter Scheduling via Scaling Cycles

Modern data center servers process multiple jobs in parallel to improve performance. However, each job demands some subset of a server's resources (e.g., CPUs, memory, storage), and a set of jobs can run in parallel only if there are sufficient computational resources to meet each job's needs. Given a stream of arriving jobs, a scheduling policy must choose a set of jobs to run in parallel at every moment in time. While prior work has studied the stability and mean response time of various scheduling policies in this setting, the vast majority of this work assumes that jobs can be preempted at any time with no overhead. In practice, however, datacenter jobs accumulate significant state as they run, making preemption costly or even impossible. In these limited preemption scenarios, little is known about the optimal way to schedule jobs and avoid excessive preemption overhead.

We consider a model of a datacenter server processing non-preemptible jobs on the fluid scale. We show that, when jobs are non-preemptible, it is difficult to both stabilize the system and maintain high server utilization. We derive a class of policies that asymptotically minimizes the amount of wasted server resources in some cases. While our policies are optimal when job resource demands are simple, we show how the problem becomes more difficult as job resource demands become more varied. We then discuss potential approaches for deriving optimal policies in these more complex cases.