Implementing Rate Monotonic Analysis

Learners will assign task priorities based on execution frequency to mathematically guarantee schedulability in a fixed-priority environment.

Implementing Rate Monotonic Analysis

In this lesson, you will learn how to assign task priorities based on execution frequency to mathematically guarantee that your real-time system will always meet its deadlines.

Rate Monotonic Analysis (RMA) is a deterministic approach to scheduling in a fixed-priority environment. The core principle is simple yet powerful: the shorter the task period, the higher the priority.

In a Rate Monotonic (RM) system, we assign priorities to tasks based on their frequency of execution. A periodic task that runs every 10ms is assigned a higher priority than a task that runs every 50ms. By following this assignment, we ensure that if a set of tasks is schedulable under any fixed-priority assignment, it is guaranteed to be schedulable under RM.

The Schedulability Test

To determine if your system is guaranteed to meet all deadlines, we check the total CPU utilization ( $U$ ). For a set of $n$ tasks, where $C_i$ is the Worst-Case Execution Time (WCET) and $T_i$ is the period:

$U = \sum_{i=1}^{n} \frac{C_i}{T_i} \le n(2^{1/n} - 1)$

For a single task, the bound is 100%. As $n$ approaches infinity, the bound converges to $\ln(2) \approx 0.693$ . If your total utilization is below this threshold, the system is mathematically guaranteed to meet all deadlines.

Practical Implementation

Imagine you have two periodic tasks in your RTOS:

// Task A: Frequency 20Hz (Period = 50ms), WCET = 10ms
// Task B: Frequency 5Hz (Period = 200ms), WCET = 40ms

// Utilization = (10/50) + (40/200) = 0.2 + 0.2 = 0.4
// Threshold for n=2: 2 * (2^(1/2) - 1) ≈ 0.828

Since 0.4 is well below 0.828, these tasks are guaranteed to be schedulable. You would implement this in your RTOS by assigning Task A a higher integer priority value than Task B, ensuring the kernel preempts Task B whenever Task A’s timer expires.

Key Takeaway: By assigning higher priorities to tasks with shorter periods, you satisfy the requirements for Rate Monotonic Analysis, allowing you to mathematically verify your system's stability before a single line of application code runs.