TY - JOUR
T1 - Optimal Scheduling in Multiserver Queues
AU - Grosof, Isaac
N1 - Publisher Copyright:
© 2024 Association for Computing Machinery. All rights reserved.
PY - 2024/1/5
Y1 - 2024/1/5
N2 - Scheduling theory is a key tool for reducing latency (i.e. response time) in queueing systems. Scheduling, i.e. choosing the order in which to serve jobs, can reduce response time by an order of magnitude with no additional resources. Scheduling theory is well-developed in single-server systems, where one job is processed at a time. However, little is known about scheduling in multiserver systems, where many jobs are processed at once. Results are especially limited in stochastic multiserver scheduling theory. Today’s data-centers have thousands of servers, and scheduling theory is unable to analyze such systems. My thesis proves the first optimality results and first closed-form bounds on mean response time for scheduling policies in stochastic multiserver models which reflect the behavior of modern computing systems. My thesis proves novel optimality results in each of three areas: I start by studying one-server-per-job multiserver models, and prove the first results on optimal scheduling in that setting. Next, I study the multiserver-job (MSJ) model, where different jobs require different amounts of resources to be served. I prove the first characterization of mean response time for any scheduling policy in the MSJ model, as well as the first optimality results. Finally, I study the effects of scheduling on the tail of response time, rather than mean response time. I invent a novel scheduling policy, Nudge, which I prove to be the first policy to outperform FCFS’s asymptotic tail of response time. This extended abstract briefly outlines the main contributions of my thesis, describing my novel performance bounds and optimality results in each of these three areas.
AB - Scheduling theory is a key tool for reducing latency (i.e. response time) in queueing systems. Scheduling, i.e. choosing the order in which to serve jobs, can reduce response time by an order of magnitude with no additional resources. Scheduling theory is well-developed in single-server systems, where one job is processed at a time. However, little is known about scheduling in multiserver systems, where many jobs are processed at once. Results are especially limited in stochastic multiserver scheduling theory. Today’s data-centers have thousands of servers, and scheduling theory is unable to analyze such systems. My thesis proves the first optimality results and first closed-form bounds on mean response time for scheduling policies in stochastic multiserver models which reflect the behavior of modern computing systems. My thesis proves novel optimality results in each of three areas: I start by studying one-server-per-job multiserver models, and prove the first results on optimal scheduling in that setting. Next, I study the multiserver-job (MSJ) model, where different jobs require different amounts of resources to be served. I prove the first characterization of mean response time for any scheduling policy in the MSJ model, as well as the first optimality results. Finally, I study the effects of scheduling on the tail of response time, rather than mean response time. I invent a novel scheduling policy, Nudge, which I prove to be the first policy to outperform FCFS’s asymptotic tail of response time. This extended abstract briefly outlines the main contributions of my thesis, describing my novel performance bounds and optimality results in each of these three areas.
UR - http://www.scopus.com/inward/record.url?scp=85190411083&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85190411083&partnerID=8YFLogxK
U2 - 10.1145/3639830.3639844
DO - 10.1145/3639830.3639844
M3 - Article
AN - SCOPUS:85190411083
SN - 0163-5999
VL - 51
SP - 29
EP - 32
JO - Performance Evaluation Review
JF - Performance Evaluation Review
IS - 3
ER -