computer science//real-time computing//real-time scheduling//rate-monotonic scheduling
Rate-monotonic scheduling is a fixed-priority real-time scheduling rule that gives the highest priority to the task with the shortest period, and it is the default way to arrange the tasks of an autopilot, a drive or any RTOS application so that their deadlines can be proven. The fastest loop preempts everything slower: the 1 kHz IMU filter interrupts the 500 Hz attitude loop, which interrupts the 100 Hz estimator, and so on down to logging.
Rate-monotonic scheduling is a fixed-priority real-time scheduling rule that gives the highest priority to the task with the shortest period, and it is the default way to arrange the tasks of an autopilot, a drive or any RTOS application so that their deadlines can be proven. The fastest loop preempts everything slower: the 1 kHz IMU filter interrupts the 500 Hz attitude loop, which interrupts the 100 Hz estimator, and so on down to logging.
Liu and Layland proved in 1973 a sufficient test. With nnn periodic tasks, each with worst-case execution time CiC_iCi and period TiT_iTi, all deadlines are met if
U=∑i=1nCiTi≤n(21/n−1).U=\sum_{i=1}^{n}\frac{C_i}{T_i}\le n\left(2^{1/n}-1\right).U=i=1∑nTiCi≤n(21/n−1).
The Liu-Layland bound is 1 for one task, 0.83 for two, 0.74 for five, and tends to ln2≈0.69\ln 2\approx0.69ln2≈0.69. Passing it guarantees every deadline. Failing it proves nothing: the set may still be schedulable, and response-time analysis gives the exact answer task by task.
A CPU budget table puts this to work on a 480 MHz flight controller (illustrative figures of the right order): IMU and filters every 1 ms taking 0.10 ms (10 %), attitude and mixer every 2 ms taking 0.12 ms (6 %), EKF every 10 ms taking 0.80 ms (8 %), position control every 20 ms taking 0.20 ms (1 %), logging and telemetry every 20 ms taking 1.00 ms (5 %). Total utilization is 30 %, well under the 0.74 bound for five tasks.
The 70 % left over is not waste: it absorbs interrupts, bursts and next month's feature. Logging sits last in priority, with a buffer, because an SD write can block for tens of milliseconds; planning does not fit at all by design and runs on a companion computer that sends setpoints at 20 to 50 Hz (autopilot).
The rule is optimal among fixed-priority policies when deadlines equal periods; with shorter deadlines the variant orders by deadline instead (deadline-monotonic).
Its strength against earliest deadline first is predictability under overload: the tasks that miss are the slowest ones, chosen at design time. The guarantees assume shared resources are locked with priority inheritance, or priority inversion breaks them.