Rate Monotonic Scheduling (RMS) Schedulability Analysis

1. The Core Principle of Rate Monotonic Scheduling

Rate Monotonic Scheduling (RMS) provides a simple, yet powerful, rule for assigning static priorities to a set of periodic tasks. The "rate monotonic" name sounds academic, but the rule is very intuitive.

The RMS Priority Assignment Rule: Assign task priorities as a monotonic function of their rate. In simple terms: The shorter a task's period (i.e., the higher its frequency), the higher its priority.

This makes sense; tasks that need to run frequently are typically more urgent. Let's watch a short video that introduces this concept and the seminal 1973 paper by Liu and Layland that established it.

RMS is an optimal static-priority scheduling algorithm. This means that if a set of periodic tasks can be scheduled using any static priority assignment, it can also be scheduled using the RMS assignment.

2. Schedulability Test 1: The Utilization Bound

Now that we know how to assign priorities, how can we prove that a set of tasks is schedulable? The first and simplest method is the utilization bound test.

First, we calculate the total CPU utilization, which is the sum of the individual utilizations of all tasks in the system.
$U_{total}={\sum }_{i=1}^n\frac{C_i}{T_i}$
Where:

• $n$ is the number of tasks.
• $C_i$ is the Worst-Case Execution Time (WCET) of task $i$.
• $T_i$ is the period of task $i$.

Liu and Layland proved that if the total utilization is below a specific bound, the task set is guaranteed to be schedulable.

The Liu & Layland Bound:
$U_{total}\le n(\sqrt[n]{2}-1)$

This formula gives us a sufficient condition. If the test passes, the task set is definitely schedulable. If it fails, the task set might still be schedulable; this test just isn't powerful enough to prove it.

For a large number of tasks ($n\to \infty$), this bound converges to $\ln (2)\approx 0.693$. This is the source of the common "70% rule of thumb" in real-time systems.

The following resource provides a clear definition of the assumptions under which this test is valid.

Let's see an example of where this simple test falls short.

This brings us to a crucial point for interviews: what do you do when the utilization test is inconclusive? You move to an exact test.

3. Schedulability Test 2: Response-Time Analysis (The Exact Test)

When the utilization test fails, we can use a more powerful method called Response-Time Analysis (RTA). This is a necessary and sufficient test: it will give a definitive yes or no answer.

The core idea is to calculate the Worst-Case Response Time (WCRT) for each task and check if it's less than or equal to the task's deadline. For RMS, we assume the deadline equals the period ($D_i=T_i$).

The WCRT of a task $i$ ($R_i$) is the sum of its own execution time ($C_i$) and the interference it experiences from all higher-priority tasks ($j\in hp(i)$).

The response time $R_i$ can be calculated using the following iterative formula:
$R_i^{(k+1)}=C_i+{\sum }_{j\in hp(i)}\lceil \frac{R_i^{(k)}}{T_j}\rceil C_j$

• $R_i^{(k)}$ is the response time at iteration $k$.
• $hp(i)$ is the set of tasks with higher priority than task $i$.
• $\lceil \frac{R_i^{(k)}}{T_j}\rceil$ is the number of times the higher-priority task $j$ can preempt task $i$ during its response window.

We solve this by starting with an initial guess (e.g., $R_i^{(0)}=C_i$) and iterating until the value stabilizes ($R_i^{(k+1)}=R_i^{(k)}$). If at any point $R_i$ exceeds its period $T_i$, the task is not schedulable, and the entire set is not schedulable.

This slide deck provides an excellent, concise overview of the RTA formula.

Practice Problem: Applying the Analysis

Let's apply both tests to a typical interview problem.

We have the following task set:

• Task T1: C1 = 20, T1 = 100
• Task T2: C2 = 30, T2 = 150
• Task T3: C3 = 90, T3 = 350

Let's analyze its schedulability.

Step 1: Assign Priorities using RMS
Based on the rule "shorter period, higher priority":

• Prio(T1) > Prio(T2) > Prio(T3)

Step 2: Perform Utilization Bound Test
First, calculate individual and total utilization:

• U1 = 20 / 100 = 0.20
• U2 = 30 / 150 = 0.20
• U3 = 90 / 350 ≈ 0.257
• U_total = 0.20 + 0.20 + 0.257 = 0.657

Now, calculate the Liu & Layland bound for $n=3$ tasks:

• U_bound = 3 * ($2^{1/3}$ - 1) ≈ 3 * (1.2599 - 1) ≈ 0.7797

Conclusion: Since $0.657\le 0.7797$, the test passes. The task set is schedulable.

In this case, the analysis is complete. However, for the sake of practice, let's imagine C3 was 100 instead of 90.

• U3 = 100 / 350 ≈ 0.286
• U_total = 0.2 + 0.2 + 0.286 = 0.686 (still schedulable)

Let's change it more drastically. Imagine C2 = 80, C3 = 100.

• U1 = 20 / 100 = 0.20
• U2 = 80 / 150 ≈ 0.533
• U3 = 100 / 350 ≈ 0.286
• U_total = 0.20 + 0.533 + 0.286 = 1.019
  Since $U_{total}>1$, this is impossible to schedule on a single core.

Let's try one more. C1=40, C2=50, C3=50.

• U1 = 40 / 100 = 0.4
• U2 = 50 / 150 ≈ 0.333
• U3 = 50 / 350 ≈ 0.143
• U_total = 0.4 + 0.333 + 0.143 = 0.876
  Here, $U_{total}(0.876)>U_{bound}(0.7797)$, but $U_{total}<1$. The utilization test is inconclusive. We must use RTA.

Step 3: Perform Response-Time Analysis (for the inconclusive case)
Let's analyze the set: T1(C=40, T=100), T2(C=50, T=150), T3(C=50, T=350).

• Task T1 (Highest Priority):

  • It has no higher-priority tasks to interfere.
  • $R_1=C_1=40$.
  • Check: Is $R_1\le T_1$? Is $40\le 100$? Yes. T1 is schedulable.

• Task T2 (Medium Priority):

  • It can be preempted by T1.
  • $R_2^{(0)}=C_1+C_2=40+50=90$. (A common initial guess is the sum of WCETs of itself and all higher tasks).
  • $R_2^{(1)}=C_2+\lceil \frac{R_2^{(0)}}{T_1}\rceil C_1=50+\lceil \frac{90}{100}\rceil \times 40=50+1\times 40=90$.
  • The value has stabilized at 90. So, $R_2=90$.
  • Check: Is $R_2\le T_2$? Is $90\le 150$? Yes. T2 is schedulable.

• Task T3 (Lowest Priority):

  • It can be preempted by T1 and T2.
  • $R_3^{(0)}=C_1+C_2+C_3=40+50+50=140$.
  • $R_3^{(1)}=C_3+\lceil \frac{R_3^{(0)}}{T_1}\rceil C_1+\lceil \frac{R_3^{(0)}}{T_2}\rceil C_2$
    $=50+\lceil \frac{140}{100}\rceil \times 40+\lceil \frac{140}{150}\rceil \times 50$
    $=50+(2\times 40)+(1\times 50)=50+80+50=180$.
  • $R_3^{(2)}=50+\lceil \frac{180}{100}\rceil \times 40+\lceil \frac{180}{150}\rceil \times 50$
    $=50+(2\times 40)+(2\times 50)=50+80+100=230$.
  • $R_3^{(3)}=50+\lceil \frac{230}{100}\rceil \times 40+\lceil \frac{230}{150}\rceil \times 50$
    $=50+(3\times 40)+(2\times 50)=50+120+100=270$.
  • $R_3^{(4)}=50+\lceil \frac{270}{100}\rceil \times 40+\lceil \frac{270}{150}\rceil \times 50$
    $=50+(3\times 40)+(2\times 50)=50+120+100=270$.
  • The value has stabilized at 270. So, $R_3=270$.
  • Check: Is $R_3\le T_3$? Is $270\le 350$? Yes. T3 is schedulable.

Final Conclusion (for the modified set): Since all tasks are schedulable, the task set is schedulable, even though it failed the simple utilization test.

4. Answering the Interview Question

The analysis above is the core of what you need. For a top-tier company, you must also discuss the limitations and assumptions.

Question: "You have a set of periodic real-time tasks. How would you determine if they can meet their deadlines on a single-core processor?"

Your Answer Structure:

1. State the model: "Assuming the tasks are independent and preemptible, with deadlines equal to their periods, we can use Rate Monotonic Scheduling (RMS). This is an optimal static-priority algorithm."
2. Assign Priorities: "First, I'd assign priorities based on the RMS rule: the task with the shortest period gets the highest priority."
3. Perform the Sufficient Test: "Next, I'd perform the simple utilization bound test. I'd calculate the total CPU utilization ($\sum C_i/T_i$) and compare it against the Liu and Layland bound ($n(2^{1/n}-1)$). If the total utilization is below this bound, the system is provably schedulable."
4. Perform the Exact Test: "If the utilization test is inconclusive (i.e., total utilization is above the bound but less than 100%), I would then perform an exact schedulability test using Response-Time Analysis. I would iteratively calculate the worst-case response time for each task, accounting for its own execution time and preemption by higher-priority tasks. If every task's response time is less than or equal to its period, the system is schedulable. Otherwise, it is not."
5. Acknowledge Real-World Complexity: "Finally, it's critical to acknowledge that this analysis relies on several assumptions. In a real system, I would need to account for factors that introduce blocking, such as shared resource contention (mutexes), I/O operations, and non-preemptible critical sections. The blocking time must be factored into the schedulability analysis, which leads to topics like priority inheritance protocols."

Conclusion

You are now equipped to perform a formal schedulability analysis, a key skill for any senior embedded engineer. You know not only the simple "rule of thumb" but also the exact test that provides a definitive answer, and you can frame this knowledge within the context of a real-world system's complexities.

Key Takeaways:

• RMS Priority Assignment: Shorter period means higher priority.
• Utilization Bound Test: A quick, sufficient test. If U_total ≤ n(2^(1/n)-1), the system is schedulable.
• Response-Time Analysis: An iterative, exact test. A system is schedulable if and only if every task's worst-case response time is less than its deadline.
• Interview Strategy: Articulate the two-test process and acknowledge the simplifying assumptions of the formal model.

Preview of the Next Lesson:

We've discussed how high-priority tasks preempt lower-priority ones. But what exactly happens in the processor during this preemption? In the next lesson, we will dissect the mechanics of a context switch, detailing precisely what processor state is saved, how the stack is managed, and the performance cost of this fundamental RTOS operation.