Ziv Scully

A New Toolbox for Scheduling Theory Degree Type: Ph.D. in Computer Science
Advisor(s): Mor Harchol-Balter, Guy E. Blelloch
Graduated: August 2022

Abstract:

Queueing delays are ubiquitous in many domains, including computer systems, service systems, communication networks, supply chains, and transportation. Queueing and scheduling theory provide a rigorous basis for understanding how to reduce delays with scheduling, including evaluating policy performance and guiding policy design. Unfortunately, state-of-the-art theory fails to address many practical concerns. For example, scheduling theory seldom treats nontrivial preemption limitations, and there is very little theory for scheduling in multiserver queues.

We present two new, broadly applicable tools that greatly expand the reach of scheduling theory, using each to solve multiple open problems. The first tool, called "SOAP", is a new unifying theory of scheduling in single-server queues, specifically the M/G/1 model. SOAP characterizes the delay distribution of a broad space of policies, most of which have never been analyzed before. Such policies include the Gittins index policy, which minimizes mean delay in low-information settings, and many policies with preemption limitations. The second tool, called "WINE", is a new queueing identity that complements Little's law. WINE enables a new method of analyzing complex queueing systems by relating them to simpler systems. This results in the first delay bounds for SRPT (shortest remaining processing time) and the Gittins index policy in multiserver queues, specifically the M/G/k model.

Thesis Committee:
Mor Harchol-Balter (Co-Chair)
Guy E. Blelloch (Co-Chair)
Alan Scheller-Wolf
Anupam Gupta
Adam Wierman (California Institute of Technology)
Baliji Prabhakar (Stanford University)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Keywords:
Queueing theory, scheduling, response time, sojourn time, M/G/1, M/G/k, heavy tails, light tails, priority queues, Least Attained Service (LAS), Shortest Remaining Processing Time (SRPT), Shortest Expected Remaining Processing Time (SERPT), Gittins index policy, Multi-Level Processor Sharing (MLPS), limited priority levels, preemption checkpoints, job size estimates