Rate-Monotonic Scheduling

Rate-monotonic scheduling assigns higher priority to faster tasks; it is optimal among fixed-priority policies and comes with a simple sufficiency test.

The Rule

Rate-monotonic scheduling (RMS) is a fixed-priority policy for periodic tasks: the shorter a task's period, the higher its priority. A task that must run every millisecond outranks one that runs every ten milliseconds. The assignment is static, computed once from the periods, and never changes at runtime.

Why It Is Optimal

Among all fixed-priority assignments, RMS is optimal in the sense that if any fixed-priority assignment can schedule a given set of periodic tasks, then RMS can too. This makes it the default reasonable choice when priorities are static and deadlines equal periods.

The Utilization Bound

RMS has a famous sufficient test. For n independent periodic tasks with deadlines equal to their periods, the set is schedulable if total utilization U satisfies U <= n(2^(1/n) - 1). For one task the bound is 1.0; for two it is about 0.828; as n grows it approaches ln(2), roughly 0.693. If utilization is below the bound, deadlines are guaranteed.

def rms_bound(n):
    return n * (2 ** (1.0 / n) - 1)

# example: three tasks, utilizations 0.2, 0.3, 0.1
U = 0.2 + 0.3 + 0.1        # = 0.6
print(U <= rms_bound(3))    # 0.6 <= 0.7797 -> True, schedulable

The Bound Is Sufficient, Not Necessary

The utilization bound is conservative. Many task sets above the bound are still schedulable; the bound just cannot promise it. For a precise answer, use response-time analysis, which accounts for the exact periods and execution times and can certify utilizations above the simple bound, up to 1.0 in favorable cases where periods are harmonic multiples of each other.

Assumptions and Extensions

Classic RMS assumes independent periodic tasks with no blocking. Real systems have shared resources, so it is paired with a resource protocol that bounds priority inversion. When deadlines are shorter than periods, deadline-monotonic priority assignment generalizes the rule while keeping the fixed-priority structure and its analyzability.