PREV_LEC | NEXT_LEC

What You Will Learn

• What Rate Monotonic Analysis is and the class of systems it applies to
• The two rules RMA gives for assigning real-time priorities
• How to compute utilization for a set of periodic threads
• The assumptions RMA makes, and where they can bite you in practice
• A recap of processes, threads, and scheduling that ties this chapter together

Prerequisites

• The previous two lectures on timeshare and real-time scheduling policies
• Basic arithmetic with fractions/percentages — no advanced math required

The Problem RMA Solves

Choosing real-time priorities that hold up under every expected workload is genuinely tricky — tricky enough that it’s a legitimate reason to avoid real-time policies in the first place unless you truly need them. RMA, published by Liu and Layland in 1973, is the most widely used procedure for this. It applies specifically to real-time systems made of periodic threads: threads that wake up, do a bounded piece of work, and go back to sleep, over and over, at a fixed period.

Period and Utilization

Each periodic thread is described by two numbers:

• Period (T) — how often the thread must run, e.g. every 10 ms.
• Utilization (U) — the fraction of that period the thread spends actually executing, e.g. 2 ms of work every 10 ms period gives U = 2/10 = 0.20 (20%).

The goal is for every thread to finish its execution before its next period begins. RMA gives two rules that, together, guarantee this is achievable:

1. Assign the highest priority to the thread with the shortest period (and so on, down to the lowest priority for the longest period).
2. Keep total utilization below roughly 69% (the Liu & Layland bound for a large number of threads; it’s a conservative, safe threshold in practice).

Total utilization is simply the sum of each thread’s individual utilization.

Worked Example

Suppose we have three periodic threads on an embedded controller:

Total utilization = 10% + 15% + 10% = 35%, comfortably under the 69% bound, so RMA predicts this priority assignment is schedulable. If we added a fourth thread that pushed total utilization past ~69%, that would be the signal to either reduce a thread’s execution time, lengthen its period, or move some work off the real-time path entirely — not to just hope it works out.

Original Demo: A Simple RMA Utilization Checker

A small original tool, ep_rma_check, that takes period/execution-time pairs and reports total utilization plus a pass/fail against the 69% bound:

/* ep_rma_check.c
 * Computes total utilization for a set of periodic threads and
 * checks it against the RMA 69% schedulability bound.
 * Build: gcc -O2 -o ep_rma_check ep_rma_check.c
 * Run:   ./ep_rma_check
 */
#include <stdio.h>

struct ep_periodic_thread {
    const char *name;
    double period_ms;
    double exec_ms;
};

int main(void)
{
    struct ep_periodic_thread threads[] = {
        { "sensor_poll",  5.0,  0.5 },
        { "control_loop", 20.0, 3.0 },
        { "logging",      100.0, 10.0 },
    };
    int n = sizeof(threads) / sizeof(threads[0]);
    double total_utilization = 0.0;

    printf("%-14s %8s %10s %12s\n", "thread", "period", "exec", "utilization");
    for (int i = 0; i < n; i++) {
        double u = threads[i].exec_ms / threads[i].period_ms;
        total_utilization += u;
        printf("%-14s %6.1fms %8.1fms %10.1f%%\n",
               threads[i].name, threads[i].period_ms,
               threads[i].exec_ms, u * 100.0);
    }

    printf("\ntotal utilization: %.1f%%\n", total_utilization * 100.0);
    if (total_utilization < 0.69)
        printf("RMA bound (69%%): PASS, schedulable\n");
    else
        printf("RMA bound (69%%): FAIL, reduce load or periods\n");

    return 0;
}

$ gcc -O2 -o ep_rma_check ep_rma_check.c
$ ./ep_rma_check
thread           period       exec  utilization
sensor_poll        5.0ms      0.5ms       10.0%
control_loop       20.0ms     3.0ms       15.0%
logging            100.0ms    10.0ms      10.0%

total utilization: 35.0%
RMA bound (69%): PASS, schedulable

Assumptions and Limits of RMA

RMA’s guarantee assumes that interaction between threads — time spent blocked on mutexes, waiting on shared resources, or on priority inversion — is negligible. Real systems rarely satisfy that perfectly. Treat the 69% bound as a useful design-time sanity check, not a substitute for actually measuring worst-case execution time and testing under load on real hardware.

Best Practices

• Measure real execution time on target hardware before computing utilization — don’t guess.
• Leave headroom below the 69% bound; it assumes negligible blocking, which real code rarely achieves.
• If utilization is too high, first look at whether work can move out of the real-time path, before reaching for a faster CPU.
• Re-run the utilization check whenever you add or change a periodic real-time thread — it’s cheap insurance.

Chapter Summary

This chapter covered two aspects of Linux system design that show up in every non-trivial embedded application: how work is partitioned across processes and threads, and how those threads get scheduled. Linux offers a rich, well-understood C library and Unix heritage for both — the real skill is choosing the right tool: timeshare scheduling for the vast majority of work, real-time policies only for genuinely deadline-driven threads, and RMA to assign priorities among those real-time threads with confidence rather than guesswork. That’s the foundation this free linux device drivers course and free embedded systems course builds on for the chapters ahead, starting next with memory management.

FAQ

PREV_LEC | NEXT_LEC