Scheduling, Admission Control and Fairness

Why shortest-remaining-first minimises mean latency, what it costs the long requests, and why a bounded queue is a feature rather than a limitation.

AI SystemsGraduate⏱ 3 hours8 min readschedulingSRPTFCFShead-of-line blockingadmission control

AssumesQueueing and the Utilisation Wall

The optimum

TheoremSRPT minimises mean response time

Consider a single server, jobs arriving at arbitrary times with arbitrary known service requirements, and preemption allowed at no cost. The shortest-remaining-processing-time rule — always serve the job whose remaining work is least — minimises the mean response time $\frac1n\sum_i (d_i - a_i)$ over all scheduling disciplines, on every arrival sequence.

Assumptions

Remaining work is known. For LLM decoding it is not: output length is not known until the model emits a stop token. Approximations — predicted length, elapsed tokens as a proxy — inherit the benefit only to the extent the prediction is accurate.
Preemption is free. Iteration-level scheduling makes it nearly so for decoding, since a generation can be paused between tokens; it is not free if pausing means evicting a KV cache.
One server. The multi-server case has no comparably clean optimum.

Key idea

Mean response time is minimised by a rule that uses one piece of information — remaining work — and no information about arrival rates, distributions or the future. That is why length prediction is such a high-leverage feature in an LLM scheduler: it is the single input that the optimal policy needs.

What it costs

PropositionWhat SRPT costs the largest jobs

Under SRPT a job with remaining work $r$ is served only at instants when no job of smaller remaining work is present. Writing

\rho_{<r} \;=\; \lambda\,\E\bigl[S\,\one\{S<r\}\bigr]

for the utilisation generated by work smaller than $r$ , that job's expected response time is at least $r/(1-\rho_{<r})$ . For the largest jobs $\rho_{<r} \to \rho$ , so their delay carries the full $1/(1-\rho)$ factor even though SRPT is minimising the mean over all jobs.

What this does not say

The lower bound above is not a claim that SRPT starves large jobs catastrophically. Measured against the response time those jobs would get under a fair policy at the same load, SRPT's penalty is far smaller than the folklore suggests for most realistic size distributions — the analysis is in Bansal and Harchol-Balter's study of SRPT unfairness. What the bound does establish is that the largest jobs pay the full utilisation-wall factor, so SRPT improves the mean without improving, and sometimes while worsening, the quantile an SLO is written against.

The cost of the fair policy

PropositionHead-of-line blocking under FCFS

Under first-come-first-served on one server with Poisson arrivals, the mean wait is

\E[W_q] \;=\; \frac{\lambda\E[S^2]}{2(1-\rho)} \;=\; \frac{\rho}{1-\rho}\cdot\frac{1+c_s^2}{2}\cdot\E[S] ,

so a single very long request inflates $\E[S^2]$ and therefore the wait of every request behind it, regardless of how short those are.

Key idea

FCFS is fair in the sense of order and unfair in the sense of outcome: a 20-token request queued behind a 4000-token one waits for the whole generation. Continuous (iteration-level) batching is the standard escape — it interleaves at token granularity, so a short request's wait is bounded by one decode step rather than by a whole generation.

Admission control

Every policy so far assumes an unbounded queue. Unbounded queues are how a system converts a brief overload into an hour of timeouts: requests accepted during the spike are still being served long after the users behind them left.

PropositionA bounded queue converts latency failure into rejection

Cap the queue at $K$ waiting requests, rejecting arrivals that find it full. Then every accepted request waits at most $K\,S_{\max}$ , and for M/M/1/K the rejection probability is

P_{\text{block}} \;=\; \frac{(1-\rho)\rho^{K}}{1-\rho^{K+1}} .

Key idea

A rejection is a fast, honest failure; a timeout is a slow one that consumed capacity first. Bounding the queue is therefore not a compromise but the mechanism by which a system stays inside its latency SLO under overload — it trades an availability number, which the formula above lets you compute, for a latency guarantee. Load shedding is the same idea with a priority ordering attached.

What this does not say

Nothing here addresses fairness between tenants. SRPT and FCFS both treat the queue as undifferentiated; a multi-tenant service usually needs a guarantee that one customer's burst cannot consume another's capacity, which calls for a weighted-fair-queueing or token-bucket structure layered above whatever within-class policy is used. Those mechanisms are about isolation, and isolation is precisely what the pooling argument in Queueing and the Utilisation Wall says you pay for in delay.

References

PaperL. Schrage (1968). A Proof of the Optimality of the Shortest Remaining Processing Time DisciplineThe optimality theorem quoted here.
PaperW. E. Smith (1956). Various Optimizers for Single-Stage ProductionThe non-preemptive ancestor — shortest processing time first minimises mean flow time.
PaperN. Bansal, M. Harchol-Balter (2001). Analysis of SRPT Scheduling: Investigating UnfairnessShows the unfairness of SRPT to large jobs is much milder than commonly assumed.
PaperG.-I. Yu, J. S. Jeong, G.-W. Kim, S. Kim, B.-G. Chun (2022). Orca: A Distributed Serving System for Transformer-Based Generative ModelsIteration-level scheduling, which is what makes preemption cheap enough to consider for LLM serving.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

TheoremSRPT minimises mean response timeproof includedAmong all preemptive scheduling disciplines on one server, serving the job with least remaining work minimises the mean time in system on every arrival sequence.
PropositionWhat SRPT costs the largest jobsproof includedUnder SRPT a job can be delayed by every shorter job that arrives while it waits, so its response time is unbounded in the arrival sequence even at stable utilisation.
PropositionHead-of-line blocking under FCFSproof includedWith first-come-first-served, a request waits for the full service of everything ahead of it, so mean wait scales with the second moment of service time rather than the mean.
PropositionA bounded queue converts latency failure into rejectionproof includedCapping the queue at K bounds the waiting time by K times the service time, at the cost of a computable rejection probability.