Deadline Servers and Admission Control

A priority says a thread should run before others. A deadline says when it must finish. Neither is a guarantee unless something enforces it, and the enforcement problem is harder than the ranking problem because a thread can always consume more CPU than it declared. The mechanism that turns a declaration into an enforceable guarantee is a server: a scheduling entity with a budget and a period that runs other threads’ work on their behalf, charging that work against the budget and suspending it when the budget runs out.

The constant bandwidth server is the cleanest formulation. It gives a thread a virtual deadline and a budget, advances the deadline by a fixed period whenever the budget is replenished, and treats the thread exactly as an ordinary deadline-scheduled task from the scheduler’s point of view. The result is that any thread, whether a well-behaved periodic task or a badly written loop that occasionally runs long, can be given a bounded worst-case response time, because the server bounds the damage it can do.

The server’s state machine

A server is characterised by two numbers: a budget Q and a period P. Its bandwidth is Q/P, and that is the fraction of the CPU it is entitled to. It has two runtime variables: the remaining budget and the current absolute deadline.

When the served thread becomes runnable and the server has budget remaining, the server is scheduled like any deadline task at its current deadline. As the thread executes, the budget is decremented. Two events change the deadline.

The first is budget exhaustion. When the budget reaches zero, the server’s deadline is advanced by P and the budget is reset to Q. The thread does not stop running; it continues, but under a new deadline one period later. This is the key difference from a simple quota: the thread is never blocked outright, it is merely re-timed, and if it keeps consuming it keeps pushing its own deadline into the future until its deadline is no longer the earliest in the system, at which point it is scheduled by the ordinary deadline rule rather than by its old position. The choice of whether to re-time or to suspend until the next period is what separates a constant-bandwidth server, which re-times, from a hard reservation that guarantees a bounded service delay by suspending instead.

The second is a request that arrives when the server is idle with budget remaining from a previous activation. If the thread was idle and the remaining budget is from an old period, using it now would let the thread accumulate credit and then spend it in a burst, the same unbounded-credit problem that affects fair-share schedulers. The server therefore resets: if the current time is past the deadline minus the period, the budget is replenished and the deadline advanced, so the thread always starts a new burst with a full budget and a deadline one period ahead.

/* CBS accounting. Called when the served thread is selected and when it
   stops running. now() is the scheduler clock. */
static void cbs_update(struct server *s, uint64_t now)
{
    if (s->budget == 0) {
        /* exhausted: push the deadline one period out and refill */
        s->deadline += s->period;
        s->budget = s->max_budget;
    }
    /* an idle server must not bank unused budget across periods */
    if (now >= s->deadline - s->period) {
        s->deadline = now + s->period;
        s->budget = s->max_budget;
    }
}

static void cbs_charge(struct server *s, uint64_t ran_ns)
{
    s->budget = (ran_ns >= s->budget) ? 0 : s->budget - ran_ns;
    /* the server's deadline is what the EDF queue sorts on */
    requeue(s);
}

The now >= s->deadline - s->period test is the subtle line. It says: if more than one period has elapsed since the deadline was set, the old budget is stale and must be discarded. Without it, a server that was idle for ten periods would accumulate ten periods’ worth of budget and, on waking, could run for 10Q without being preempted by its deadline peers. That is precisely the behaviour the server exists to prevent, so the reset is not an optimisation but a correctness requirement.

Why the deadline, not the priority, is the interface

The server’s contribution is that it converts a bandwidth into a deadline. A thread with bandwidth Q/P and a request that arrives at time t receives a deadline of t + P at the moment it becomes runnable, and the scheduler can then order it against every other deadline entity in the system with the standard earliest-deadline rule. The response time it can expect is bounded by the interference from higher-deadline entities, which is exactly what schedulability analysis computes.

The alternative, giving the thread a high priority and hoping, provides no such bound, because the priority is not tied to a period and the analysis has no parameter to work with. The server’s interface is therefore strictly more informative: it asks the program to state its bandwidth requirement, and in exchange it provides a number that can be analysed.

That exchange has a cost in flexibility. A thread whose CPU demand varies cannot state a single bandwidth that is both sufficient for its peak and efficient at its average. Set Q for the peak and it reserves capacity it does not use; set Q for the average and its peaks will exhaust the budget and be pushed to later deadlines, missing whatever internal deadline it had. The usual resolution is to size the server for the peak of the important work and to place the rest in a separate, lower-bandwidth server, so that the guarantee applies to the part that needs it.

Admission control as the load-bearing element

A server without admission control is a promise with no enforcement of feasibility. Ten servers each requesting 20 percent bandwidth cannot all be satisfied on one CPU, and nothing in the server mechanism prevents the eleventh from being created. The scheduler will accept all of them, each will be pushed past its deadline, and every one will miss, the same failure that fixed priorities exhibit when oversubscribed, but now with an explicit number that was ignored.

Admission control is the test performed when a server is created. The condition for a set of servers under EDF is that the sum of bandwidths is at most one:

$$\sum_i \frac{Q_i}{P_i} \le 1$$

This is necessary and, for servers with deadlines equal to periods on a single processor, sufficient. A request that would violate it is refused, and the refusal is the useful part: it moves the failure from run time, where it appears as a missed deadline under load, to configuration time, where it appears as an error from a call that can be handled.

The sufficiency has assumptions that a real system must check. The Q/P sum test ignores blocking from shared resources, so a server whose threads take locks can miss deadlines even when the sum is below one; the blocking term must be added, and its size depends on the locking protocol as described in Priority Inversion and Inheritance. The test also assumes the budget is the true worst case, which means the declared Q must be an upper bound on actual execution: an under-declared budget produces a server that is throttled mid-work and misses its own deadline, and the throttling looks like a scheduler failure rather than a configuration error.

/* Admission test for a new server on a single CPU. Blocking and switch
   overhead are not included; callers that take locks must add a term. */
static int admit(struct server_set *set, uint64_t q, uint64_t p)
{
    if (q == 0 || q > p)
        return -EINVAL;                 /* bandwidth outside (0, 1] */
    if (set->total_q_p + (double)q / (double)p > 1.0)
        return -EBUSY;                  /* would oversubscribe the CPU */
    set->total_q_p += (double)q / (double)p;
    return 0;
}

The q > p check is not pedantry. A server with a budget larger than its period has bandwidth greater than one, which is meaningless on a single CPU and, if admitted, breaks the invariant that the sum is a fraction. Rejecting it at the boundary is cheaper than discovering the arithmetic inconsistency later.

Composition and the accounting of overhead

Servers compose, and the composition is where the bandwidth arithmetic gets interesting.

A server can contain other servers. The outer server’s budget is consumed by the execution of the inner one, and the inner one’s deadline logic runs against the outer one’s available budget. The bandwidth of the composite is at most the minimum of the outer bandwidth and the sum of the inner bandwidths, and the admission test applies recursively: the inner servers must sum to at most the outer server’s bandwidth, and the outer must fit in the root’s capacity.

This is the mechanism that makes a container’s CPU limit enforceable in a way a weight is not. A container with a bandwidth reservation and a set of threads inside it can have the threads scheduled by any policy, fair share or fixed priority, while the container as a whole is bounded by the server. The bound holds regardless of how many threads the container creates, which is exactly the property that per-thread weighting cannot provide and that the hierarchy in Hierarchical Fair Share and Lag Accounting provides only in the proportional sense.

The overhead term is the part that admission tests often omit and that matters at small budgets. Each activation of a server costs a scheduling decision, and each budget exhaustion costs a deadline update and a requeue. A server with a period of one millisecond and a budget of one hundred microseconds is exhausted and re-armed ten times a second, and each exhaustion is a fixed charge against the CPU that is not in Q. At small P the overhead becomes a significant fraction of the bandwidth, and the sum test that ignores it will admit a set that cannot actually be served. The practical rule is to keep P large relative to the switch cost, a period in the milliseconds rather than the microseconds, and to include an overhead allowance in the test when the periods are short.

What the guarantee excludes

A server bounds the CPU time its threads can consume. It does not bound how long they wait, and the distinction is the most common misreading of what a bandwidth reservation means.

A thread with a 10 percent bandwidth reservation receives at most one tenth of the processor in every interval longer than a period, and in the limit receives that share on average over any sufficiently long interval. Its worst-case response time to a single request is determined by when the server’s next replenishment falls and by how much higher-deadline work is ahead of it, which can be many periods if the system is heavily loaded. A reservation is a throughput guarantee, not a latency guarantee, and a workload that needs a response within a specific time needs its period set to that time, with the bandwidth cost that implies.

The second exclusion is that the server bounds only work it can see. A thread that makes a system call which blocks has its execution charged to the server up to the block, and the kernel work performed on its behalf afterwards is not. On a machine where the dominant cost is in the kernel, in file system operations, network processing, or page faults, the reservation covers a fraction of the actual cost and the accounting understates the load. The gap between user-visible CPU accounting and true cost is the same one described in Tick Accounting and How a Slice Is Measured, and it is not closed by adding a server.

The third is that the guarantee is per-CPU. On a multiprocessor, a server’s bandwidth is defined against the capacity of the processor it runs on, and a thread that migrates between processors has its deadline computed against a single processor’s clock. Global deadline scheduling across processors is not optimal in the way single-processor EDF is: the Dhall effect described under multiprocessor EDF means a set of tasks whose total utilization is only slightly above 1 can miss deadlines regardless of how many processors are available, and a server layer on top inherits that bound. Claiming a single-processor guarantee on an m-processor machine requires either partitioning the servers to processors or accepting the reduced capacity.