Rate Monotonic Scheduling

Topics: Embedded Systems

Definition

Rate Monotonic Scheduling (RMS) is a static-priority, preemptive scheduling algorithm used in real-time operating systems (RTOS) to assign fixed priorities to periodic tasks based on their periods. The deadline of each task is equal to the task period

In RMS, the priority is determined based on the period (or frequency) of the task, i.e., the lower the period, the higher the priority; similarly, the higher the frequency, the higher the priority. For example, a task running at a period of $1ms$ gets priority over a task running at $10ms$, which gets priority over a task running at $100ms$.

The schedule of tasks can be determined over the LCM of the periods of all the tasks. This is because the whole scheduling sequence repeats at the LCM. For example, with periods $20$, $5$ and $10$, the LCM is $20$, so after $20ms$ the whole schedule repeats.

RMS is widely used and preferred in several applications because of its simplicity and natural handling of periodic tasks. Moreover, it can be easily implemented with interrupts on bare-metal without the need for a RTOS.

Optimality

RMS is mathematically optimal among all fixed-priority assignment algorithms; if a task set cannot be scheduled by RMS, no other fixed-priority scheme can schedule it.

Scheduling Bound

RMS is accompanied by a scheduling bound that guarantees that all deadlines are met if the utilization satisfies the following inequality:
$U = \sum_i^n \frac{C_i}{T_i} \leq n \, (2^{1/n} - 1)$
where

• $U$ is the processor utilization
• $n$ is the number of tasks
• $C_i$ is the computation time of the task
• $T_i$ is the time period of the task

As $n$ grows, the utilization bound approaches $69.3\%$.

Example

Below is an example with 3 tasks:

• Task 1: $T_1=100$, $C_1=20$
• Task 2: $T_2 = 150$, $C_2=30$
• Task 3: $T_3=200$, $C_3=90$

Uses

RMA is widely used in hard real-time systems where missing a deadline could cause a critical failure, for example, avionics, automotive, motor control and power electronics...

References

1. https://www.embeddedrelated.com/glossary/rate-monotonic-scheduling
2. https://www.geeksforgeeks.org/operating-systems/rate-monotonic-scheduling/