Assigning Task Priorities with RMA

Embedded gurus Michael Barr and David Stewart have written a couple of great articles about assigning task priorities with RMA (the Rate Monotonic Algorithm):

  1. Introduction to Rate Monotonic Scheduling, by David Stewart and Michael Barr
  2. 3 Things Every Programmer Should Know About RMA, by Michael Barr

The first article lays out the basics: RMA is an algorithm that assigns static priorities to periodic tasks in order to maximize “schedulability.”  That’s a mouthful: 16 words, 37 syllables.  And one of the words isn’t real: “schedulability,” which means “able to be scheduled so that all tasks complete before their deadline every time.”

Let’s try again: RMA helps tasks get done in time.  That’s better: 7 words, 9 syllables.

The second article expands on the basics of RMA, giving some additional guidelines for when it should be used, especially as it applies to interrupts (which it does!).

I want to talk a bit more about the basics of RMA.  RMA is easy to describe: a task’s priority is based on how often it runs.  The task that runs the most often gets the highest priority, the task that runs the second most often gets the next highest priority, and so on.  Or, to quote the first article, “Assign the priority of each task according to its period, so that the shorter the period the higher the priority.”

RMA does not guarantee that your tasks will all complete in time; RMA does guarantee to find the optimal static prioritization assignment if one exists.  If RMA doesn’t produce a “schedulable” task set then no “schedulable” static priority scheme exists.

RMA’s greedy nature makes intuitive sense: starting at time zero, assume all tasks are ready to run.  Then run the task with the shortest period.  Since this task runs more often than any other task, it “feels” right to run it first to give it the best chance of finishing before it has to run again.  Next run the task with the next shortest period, and so on, until all tasks have been run.

Fortunately the intuition and “feel” that RMA works is backed by the fact that it does!

I’ve given a very basic overview of RMA here.  Please check out Stewart and Barr’s articles for more about RMA.