Admit work only when a declared deadline model can support it
Use remaining-work estimates and slack while distinguishing a feasible toy schedule, uncertain online admission, and resource-safe execution.
On this page
The question for today
What you’ll understand
- Calculate slack and a simple known-work deadline feasibility check.
- Explain why priority ordering cannot create missing capacity.
- Distinguish an estimated online deadline promise from a deterministic guarantee.
A priority queue can choose who runs next, but it cannot make an infeasible set of promises feasible. Generation adds uncertainty because remaining output work is unknown, iteration cost changes with the batch, and memory can constrain which eligible request runs. Deadline-aware serving needs a defined arrival boundary, remaining-work model, admission decision, and failure policy. A successful calculation for a small deterministic queue should be reported as exactly that, not as a guarantee about real tail latency.
Define the deadline and the remaining work
An end-to-end deadline is an absolute completion time relative to a stated request boundary. A first-token target or next-token target is a different constraint; satisfying one does not imply the others. At scheduler time t, compare the deadline with estimated remaining service and relevant waiting or transfer. A positive slack estimate is evidence within the cost model, not proof that future arrivals, output length, or device interference will stay within the estimate.
Include already committed work and supported preemption boundaries. A high-priority request arriving during a nonpreemptible chunk cannot run immediately, and an expired request needs a declared action such as rejection, cancellation, or separately labeled best effort. Keep memory admission distinct: enough bytes do not establish enough time, while a favorable deadline order does not authorize unsafe allocation. Profile known execution paths and attach uncertainty or conservative bounds when deciding what can actually be promised.
Prove only the schedule whose assumptions are known
For jobs all available at time zero on one serial server, known fixed nonnegative service times and no overhead make an earliest-deadline order easy to inspect. Every prefix must finish by its corresponding ordered deadline. Under these narrow assumptions, that order minimizes maximum lateness, and a missed prefix means no deadline-feasible permutation exists for that job set. This is not the same setting as dynamically batched GPU generation with future arrivals and unknown lengths.
Clockwork's original serving work emphasizes predictability and deadline-oriented control for a defined DNN execution setting. That motivation is useful without importing its guarantees into arbitrary language-model scheduling. In an online system, distinguish a conservative sufficient admission test from a heuristic estimated-feasibility test. Measure rejected requests and their tenant distribution alongside successes; otherwise a scheduler can improve reported accepted-request latency simply by silently refusing difficult work.
Evaluate priorities together with admission and fairness
A deadline policy can starve low-priority traffic unless the service contract defines aging, reservations, or another fairness mechanism. Conversely, granting every request urgent status cannot bypass finite capacity. Track useful completion under the intended cohort and report overload behavior rather than inspecting only the queue order. Test arrivals during long chunks, underestimated outputs, memory pressure, and cancellation to see where estimated feasibility stops matching actual behavior.
The queue lab isolates the growth caused by sustained work imbalance. Reset, set both λ=3 and μ=2, predict backlog eight at four seconds, then Play or take eight Steps. Reset and set both λ=2,μ=3 for a fresh run draining to zero at four seconds. Parameter edits retain time, so do not treat them as switching rates on accumulated backlog. The lab has no deadlines, priority classes, nonpreemptive jobs, or measured request tails; a positive service margin there cannot certify a deadline admission policy.
Work it through
Check one known-work earliest-deadline schedule
Three jobs are available at time zero on one serial server with no overhead. A costs two milliseconds and is due at three, B costs three and is due at six, C costs one and is due at seven. Service times and deadlines are exact for this fixture.
Order by deadlines as A,B,C. Their cumulative completion times are two, five, and six milliseconds.
Compare each with its deadline: 2≤3, 5≤6, and 6≤7. Every prefix satisfies the stated serial feasibility condition.
Now consider admitting D with cost two and deadline four. The ordered prefix A,D completes at four, but adding B completes at seven, beyond B's deadline six. The enlarged set fails this model's feasibility test despite each job being individually short.
The original set is feasible and the enlarged set is not under the exact all-released-at-zero serial model. A real batched engine needs a different calibrated admission argument.
The living notebook
Explore the model
Interactive lab · queue
Inspect a capacity imbalance without pretending it is a deadline test
Fresh Reset → set both λ=3,μ=2 predicts backlog 8 at t=4 s; Reset → set both λ=2,μ=3 predicts 0. Play or take eight half-second Steps. Edits retain elapsed time. This fluid model contains no deadline order, job durations, priority classes, or measured p99.
- Fluid backlog
- 4
- Net rate · λ − μ
- −1 /s
- M/M/1 mean residence
- 1 s
Fluid backlog starts at 4 and follows max(0, 4 + (λ − μ)t). The separate M/M/1 residence-time formula assumes Poisson arrivals, exponential service and λ < μ. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forPriority cannot repair missing capacity; deadline claims need their own workload and execution model.
Pause & reason
Check your understanding
Your turn
Try it yourself
At current time 20 ms, a request is due at 50 ms and has estimated remaining service 18 ms. Calculate estimated slack. If an unavoidable currently running chunk has twelve milliseconds left and was excluded from the estimate, what remains?
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Use one consistent clock and include the nonpreemptible blocking interval exactly once.
Compare with the solution
Initial estimated slack is 50−20−18=12 ms. Including the previously omitted twelve-millisecond blocking interval leaves zero estimated slack. Any further omitted transfer, decode variation, or delivery delay would make the estimate late. This does not prove the exact completion time because remaining work was estimated; it shows why an apparently comfortable priority decision can disappear when the actual scheduling boundary is included.
Keep the idea
Take it with you
- Deadline order, memory safety, and admission feasibility are separate obligations.
- Known-work serial proofs should not be generalized to unknown-length batched generation.
- Report rejected and starved traffic when evaluating deadline-oriented policies.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.