embedded software boot camp

Rate Monotonic Analysis and Round Robin Scheduling

Friday, January 22nd, 2010 by Michael Barr

Rate Monotonic Analysis (RMA) is a way of proving a priori via mathematics (rather than post-implementation via testing) that a set of tasks and interrupt service routines (ISRs) will always meet their deadlines–even under worst-case timing.  In this blog, I address the issue of what to do if two or more tasks or ISRs have equal priority and whether round robin scheduling is necessary in an RTOS to deal with that special case.

First a little background.  In order for the schedulability analysis portion of the RMA mathematics to provide meaningful results, the following assumptions must hold:

Under RMA, the relative priorities are assigned according to a simple rule: “The more often a task or ISR runs (in the worst-case), the higher its priority.” Put another way, the task or ISR with the longest period between iterations (interarrival time, if you prefer) is least important. This is because an infrequent but high-priority task could prevent a more frequent task from missing an entire iteration.

So what happens if you are using RMA to assign priorities and you wind up with two (or more) tasks or ISRs assigned equal priority? (Translation: they have the same worst-case interarrival times). Must they be assigned equal priority in the real system? What if the RTOS (in the case of tasks) or hardware (in the case of interrupts) doesn’t support round-robin scheduling–or even equal priorities with run-to-completion?

Interestingly, it turns out not to matter a bit whether you:

  1. Merge the two tasks into one (i.e., executed code for Task A then Task B).
  2. Give them equal priority, either with round robin or run-to-completion behavior.
  3. Give them adjacent unequal priorities (in either relative order).

If you run through the timing diagrams for each of the above scenarios, you’ll see that all three are equivalent. Except that the equal priority with round robin potentially suffers a performance impact from unnecessary additional context switches.

Tags: , , , ,

Leave a Reply