Abstract: Scheduling policies are at the heart of computer systems. The right scheduling policy can dramatically reduce response times, ensure fairness, provide class-based priority, etc., without requiring additional resources. While stochastic response time analysis (e.g. in the M/G/1 queueing model) of different scheduling policies has been the focus of many theoretical papers, results are limited to analyzing a relatively small number of simple scheduling policies, such as first-come, first served (FCFS) and shortest remaining processing time (SRPT), with each requiring its own ad-hoc analysis.

We introduce an extremely broad class of scheduling policies called SOAP: Schedule Ordered by Age-based Priority. The SOAP class contains virtually all previously analyzed policies, including FCFS and SRPT, as well as a wide array of policies which have never been analyzed before, such as shortest expected remaining processing time (SERPT) and the famously complex Gittins policy. We give a universal response time analysis that works for any SOAP policy, enabling us to analyze SERPT, Gittins, and other previously intractable policies. We conclude with several examples of applying our analysis to the design of new scheduling policies for computer systems.

Paper link
https://ziv.codes/publications/#soap-one-clean-analysis-of-all-age-based-scheduling-policies

Bio:  Ziv Scully is a graduate student in Computer Science at CMU advised by Mor Harchol-Balter and Guy Blelloch. He graduated from MIT in 2016 with a BS in Mathematics with Computer Science. He is the recipient of an NSF Graduate Fellowship and an ARCS Foundation scholarship. Ziv’s research focus is optimizing and analyzing computer systems and algorithms from a stochastic perspective, including job scheduling, load balancing, combinatorial optimization under uncertainty, and parallel algorithms. Recent publications of his have been recognized with awards from the INFORMS Applied Probability Society (Best Student Paper Prize finalist, 2018), IFIP PERFORMANCE (Best Student Paper Award winner, 2018), and ACM SIGMETRICS (Outstanding Student Paper Award winner, 2019).