Fairness and Tail Latency in Task Schedulers

A runtime’s scheduling policy is usually discussed in terms of throughput: how many tasks per second, how much time is spent in the scheduler, how evenly the cores are loaded. Those are the metrics a benchmark reports and the metrics a design document optimises. They are also the metrics that say least about what a user experiences, because a mean over a million requests is dominated by the requests that were fast and says nothing about the ones that waited.

Tail latency is the latency of the slowest few percent. It matters because a request that fans out to a hundred services is as slow as its slowest dependency, and because a queueing system’s percentiles grow with its mean so that saturation moves both. The scheduler is one of the places where the tail is created, and the policies that flatten the mean often steepen the tail.

Why the mean lies

Consider a queue served by one worker. At low utilisation the wait is near zero. For a memoryless queue the mean sojourn time is the service time divided by one minus utilisation, so at 50% utilisation it is twice the service time and at 90% it is ten times. The percentiles follow the same curve: the 99th percentile of an exponential distribution is about 4.6 times its mean, which puts it near nine service times at 50% utilisation and near forty-six at 90%. The tail therefore grows with the mean rather than independently of it, and the growth is steeper for service-time distributions with heavier tails than the exponential.

A runtime’s ready queue is not a single M/M/1 queue; it is a set of per-worker queues with stealing between them, and tasks have wildly varying service times. The qualitative conclusion survives: as a resource approaches saturation, the queue’s tail lengthens faster than its mean, and a policy that increases utilisation by batching or by deferring work increases the tail.

The second reason the mean lies is heterogeneity. A task’s latency is the sum of its queueing delay, its execution, and any time it spends suspended. A runtime that reports the mean over all tasks mixes a million fast completions with a thousand slow ones and reports a number that describes neither.

Queue discipline decides who waits

First-in-first-out is fair in the sense that no task overtakes another, and it is the wrong discipline for latency when service times vary. A short task that arrives behind a long one waits for the long one’s full duration. The expected wait under FIFO is proportional to the mean remaining service time of everything ahead, which is dominated by the long tasks.

Shortest-job-first minimises mean latency, but it requires knowing service times in advance, which a general runtime does not. The practical approximations are to prefer tasks that have already run and are likely to finish soon, or to give newly arrived tasks a small priority boost so that they are not stuck behind a backlog. Both are heuristics with failure modes: preferring tasks that have run favours long tasks that have already consumed time, and a priority boost for new arrivals starves old ones if arrivals are continuous.

Round-robin with a timeslice is the standard compromise. Every task gets a fixed quantum, and a task that exhausts it goes to the back of the queue. The tail is then bounded by the number of tasks ahead times the quantum, not by their service times, which is a much better bound when service times are heavy-tailed. The cost is context switches per quantum, and the choice of quantum is a direct trade: a small quantum bounds the tail and wastes time on switches, a large one amortises the switches and lets one task monopolise.

/* Fixed-quantum round robin over a fixed-capacity ring. */
struct task *ready[N];
unsigned head, tail;              /* tail - head is the queue length */

for (;;) {
    struct task *t = ready[head++ % N];
    if (!t) continue;
    switch_to(t);
    /* Control returns when t blocks or its quantum expires. */
    if (t->state == TASK_RUNNABLE)
        ready[tail++ % N] = t;    /* back of the line, quantum reset */
}

The quantum is where a cooperative runtime and a preemptive one diverge. A cooperative runtime can only charge a task at yield points, so the quantum is measured in checkpoints and its wall-clock equivalent varies with what the task does between them. A preemptive runtime can charge by wall-clock and enforce the quantum with a timer. The fairness guarantee is only as good as the enforcement, and enforcement is the subject of yield points and cooperative scheduling.

The scheduler is not the only queue

A request’s latency in a real runtime passes through several queues, and the scheduler’s is rarely the longest. The others are the kernel’s run queue when the runtime has more runnable threads than cores, the network stack’s backlog, the runtime’s own completion queue, and any application-level queue such as a connection pool or a bounded channel.

Each of these can dominate, and each has its own discipline. The kernel’s run queue is a fair-share scheduler with priorities and a wakeup path whose latency depends on which core the task lands on and whether that core is idle. A task woken on a busy core waits for that core; a task migrated to an idle core pays a cache-cold start. Both effects appear in the tail and neither is visible to the runtime’s own scheduler.

The application-level queue is the one the runtime can most easily influence and the one most often ignored. A bounded channel with a FIFO discipline and a full buffer creates a queue whose length is invisible to the scheduler. A worker pool with a shared queue and a fixed thread count does the same. The tail in these structures is governed by Little’s law: the number of items in the system equals the arrival rate times the time each spends in it, so a queue that grows without bound means the wait grows without bound.

Batching and the latency-throughput trade

Every runtime batches somewhere. The event loop retrieves events in a batch; the completion interface reaps entries in a batch; the scheduler moves tasks in batches when a worker steals; the network stack coalesces packets. Batching amortises fixed costs and therefore raises throughput, and it adds latency to the first item of each batch because that item waits for the batch to fill or for the batch’s processing to reach it.

The trade is quantified by the batch size. A batch of B items costs one fixed overhead plus B per-item costs, so throughput improves as B grows. The first item’s added latency is at most the time to collect the batch, which is bounded by the batch’s arrival rate, and the last item’s added latency is the processing time of the B − 1 items ahead of it. A runtime that processes a batch of a hundred completions before returning to the event loop delays the hundredth by the processing time of ninety-nine.

The design response is to interleave: process a bounded batch, then check for higher-priority work, then continue. That bounds the tail contribution of any one batch without giving up the amortisation, at the cost of a check per batch. Runtimes that skip the check are optimising the mean.

Fairness across tenants

A runtime that serves several independent clients has a fairness question that a single-client runtime does not. If all tasks share one ready queue, a client that submits a thousand tasks gets a thousand times the CPU of a client that submits one, which may be exactly right or exactly wrong depending on the contract. Weighted fair queueing gives each client a share proportional to a weight by tracking virtual time: each client’s virtual clock advances only while its tasks run, and the scheduler picks the client with the smallest virtual time.

The mechanism is cheap in principle, one counter per client updated on each dispatch, and awkward in practice because it requires the scheduler to know which client a task belongs to. Runtimes that expose tasks as opaque objects must add a tag, and the tag must propagate to child tasks or the children escape the accounting. Structured concurrency helps here: if a task’s children are in its scope, the scope can carry the tag.

Fairness across tenants does not imply fairness within one. A weighted scheme that gives a client its share still lets that client’s own tasks starve each other if its queue discipline is FIFO and its tasks are heterogeneous. The two levels must be designed together, which is why the layered schedulers in operating systems separate the fair-share layer from the per-entity policy.

What the runtime can measure

The tail is hard to fix without instrumentation, and instrumentation is where runtimes differ most. A runtime that records, per task, the time spent runnable, the time spent suspended, the number of times it was stolen, and the carrier it last ran on can attribute a slow request to a specific cause. A runtime that records only completion counts cannot.

The cost of the instrumentation is a clock read per transition, which is tens of cycles, and a per-task record that must be sized in advance or allocated. Runtimes that care about the tail usually make this optional and sample it, recording one task in a thousand, so that the overhead is negligible and the sample is large enough to estimate percentiles. A sample of a thousand events gives a usable estimate of the median and a very rough estimate of the 99th percentile; estimating the 99.9th requires a much larger sample, which is why tail measurement is expensive and why the figures that appear in published work are usually from dedicated benchmarks rather than from production telemetry.

The honest position is that a scheduler can bound the tail it controls and cannot bound the tail it does not. The runtime’s queue discipline, quantum, and batching set a floor; the kernel’s wakeup latency, the application’s pool sizes, and the service times of the tasks themselves set the rest. A runtime that documents which of those it controls, and exposes the instrumentation to measure the others, is more useful than one that claims a latency figure without saying what it excludes.

The mechanisms that make the tail tractable are the same ones that make the system comprehensible: a bounded quantum, a queue discipline chosen for the service-time distribution, cancellation that actually stops work rather than waiting for it to finish, and timeouts accurate enough that a stuck operation is detected before it becomes a stuck request. The last of those depends on the timer facility described in hierarchical timing wheels, because a timeout that fires late is indistinguishable from a task that ran long.