Rate-Monotonic Priority Assignment and Its Utilisation Bound

Given a set of periodic tasks and a fixed priority for each, the question of whether they all meet their deadlines has an exact answer, computable by simulating the schedule up to the hyperperiod. The question of which assignment to choose is different: it is a search over orderings, and with n tasks there are n factorial of them. Rate-monotonic assignment collapses that search to a sort by period, and the fact that it does so without loss is the reason it is the default in almost every fixed-priority design.

The theorem and what “optimal” means in it

Rate-monotonic assigns higher priority to shorter periods. The Liu and Layland result is that this assignment is optimal among all fixed-priority assignments in a precise, limited sense: if any fixed-priority assignment can schedule a set of independent periodic tasks with deadlines equal to periods, then rate-monotonic can schedule that same set. The statement is about feasibility, not about slack; a different assignment may produce more slack on a particular task, but it cannot make a set feasible that rate-monotonic makes infeasible.

The scope of the claim is what makes it usable. It assumes tasks are independent, that is, they do not share resources and do not block each other; each task’s worst-case execution time is known and constant; tasks are released periodically with no jitter; and the deadline equals the period. Every one of those assumptions needs repair in a real system, and each repair weakens the result in a different way. Shared resources add a blocking term, whose treatment is the subject of priority inversion and blocking time; release jitter shifts the interference pattern; and deadlines shorter than periods require a different assignment rule.

The exchange argument behind the theorem is short. Take any feasible assignment and consider two adjacent tasks where the longer-period task has the higher priority. Swapping their priorities cannot make the schedule infeasible: the shorter-period task now runs earlier and its own interference shrinks, while the longer-period task runs later but its deadline gives it more room, and the swap can be repeated until the order is by period. Repeating it on every inversion terminates in the rate-monotonic order, so any feasible set is also feasible under rate-monotonic.

The utilisation bound and its three forms

For a set of n independent periodic tasks with deadlines equal to periods, the sufficient condition is that total utilisation stays at or below $n(2^{1/n} - 1)$. The sequence decreases with n and approaches $\ln 2 \approx 0.693$ from above, so a large task set can be guaranteed schedulable only up to about 69 percent of the processor. Small sets get a better number: one task is 100 percent, two tasks 82.8 percent, three 78 percent, four 75.7 percent, and by ten tasks the bound is about 71.8 percent.

The bound is sufficient, not necessary. A set with utilisation above the bound may still be schedulable, and one with utilisation below it is guaranteed to be. The gap is not a rounding artefact but a real property of the bound’s derivation, which uses the worst possible phasing of task releases and the worst possible ratio of execution times. Sets that are “aligned” in a favourable way exceed the bound comfortably.

The harmonic case is the one that recovers full utilisation. If every period in the set is an integer multiple of every shorter period in the set, the bound rises to 100 percent. That is why period choices matter at design time more than they appear to: a set of 2 ms, 4 ms, 8 ms and 16 ms periods can use the whole processor, while 3 ms, 4 ms, 8 ms and 16 ms is guaranteed only up to about 76 percent, the bound for four tasks. Rounding periods to a common base rate, or choosing them as multiples of the fastest, is a design decision that costs nothing at run time and recovers the quarter of the processor that the general bound withholds.

def harmonic(periods):
    """True if every period divides every longer one."""
    return all(p % q == 0 for p in periods for q in periods if q <= p)

def rm_bound(n):
    """Sufficient utilisation bound for n independent periodic tasks."""
    return n * (2.0 ** (1.0 / n) - 1.0)

# 2/4/8/16 ms: bound is 100%, utilisation of 0.5+0.25+0.125+0.0625 is fine
# 3/4/8/16 ms: not harmonic, the Liu & Layland bound applies instead

The utilisation test itself uses worst-case execution times, which are not the same as measured averages. A task that runs 200 microseconds typically but 900 in its worst path contributes 900 to the sum. Using averages inflates the apparent capacity and produces designs that pass the test and fail in the field. The measurement of a worst case is not possible by observation alone on a modern core with caches and speculative execution; the standard approach is to bound it analytically or to measure with instrumentation that closes off the paths that cannot occur, and either way to treat the number as a bound.

When deadlines are shorter than periods

The theorem’s assumption that deadlines equal periods is not a convenience; a task whose deadline is shorter than its period has a different priority ordering, and rate-monotonic can be wrong for it. The counterexample is a task with a short deadline and a long period: rate-monotonic gives it low priority because its period is long, and it misses. Deadline-monotonic assignment, which orders by relative deadline rather than by period, is the correct rule in that case, and it is optimal among fixed-priority assignments when deadlines are less than or equal to periods.

The utilisation bound does not survive that generalisation. Deadline-monotonic assignment has no comparable closed form, so the schedulability test reverts to the exact response-time computation described in response-time analysis for fixed-priority sets. In practice the utilisation test is used as a first filter and the exact test as the decision, and the exact test is not much more expensive when there are fewer than a few dozen tasks.

Where the bound stops being the right tool

Three situations make the 69 percent figure irrelevant rather than merely conservative.

The first is blocking. Any shared resource adds a term that is not utilisation and does not shrink with the bound; a task set with 50 percent utilisation and a long critical section can miss deadlines. The blocking term is computed per task, not per processor, and is added to the interference term.

The second is aperiodic work. Interrupt handlers and sporadic tasks triggered by external events have no period, so the utilisation sum is not defined for them. The standard treatment converts each sporadic task into an equivalent periodic one using its minimum interarrival time, which is valid when the minimum is known and optimistic when it is not. Event streams with a bursty arrival pattern can violate the minimum more easily than the designers expect.

The third is anything that changes at run time: dynamic task creation, mode changes, or tasks that alter their own periods. The analysis is static, and a system that reconfigures itself must re-run the analysis for each configuration or be designed so that the active set is bounded by the worst case.

A fourth, subtler case is processor speed scaling. A design that passes the utilisation test at the nominal clock may violate it when the clock is reduced to save power, because the execution times scale with the clock but the periods do not. The analysis has to be run at the slowest clock the system will use.

Utilisation as a design metric, not just a test

The most useful thing about the bound is that it makes utilisation a design-time quantity that can be traded. A task set at 60 percent has room; at 85 percent, the guarantee is gone and every addition needs the exact test; at 95 percent, the set is feasible only with a favourable phasing and any jitter may break it. Tracking the number as tasks are added makes the cost of a new feature visible in the same units as the schedule.

The bound also sets expectations for what a fixed-priority kernel can promise. A design that needs to use 95 percent of the processor for guaranteed periodic work is not a candidate for plain rate-monotonic; it needs either harmonic periods, deadlines equal to periods with an exact test, or a scheduler that is not fixed-priority, such as the deadline-driven ones discussed in earliest-deadline-first and its overload behaviour.