By Jack Ganssle

RMA

Published 4/22/2007

Real time OSes are something like a billion dollar market. But the ugly secret to multitasking is that conventional round-robin schedulers are non-deterministic. It's impossible to guarantee that all of the tasks will run in a timely fashion.

A variety of other scheduling algorithms exist. Probably the best-known is Rate Monotonic Analysis. Simplifying somewhat, for a typical busy system with more than a few tasks, if the sum of (worst-case execution time of each task)/(task's period) is less than about 69%, you'll meet all deadlines if tasks are assigned priorities based on how often they run. The fastest gets the highest priorities; those that run the least often get the lowest.

RMA has been around since the 70s, and plenty of articles in Embedded Systems Design and elsewhere advocate its use. "Rate Monotonic Analysis" gets over 32,000 hits in Google. We're all using it. right?

Maybe not.

RMA scheduling absolutely requires you know how often each task runs. Do you? That can be awfully hard to determine in a real-world application responding to unpredictable inputs from the real world.

To guarantee RMA will work in any particular application, you've got to ensure the sum of execution time/task period is under about 69%. That implies we know each task's real-time behavior. Few of us do. In assembly, with simple processors devoid of cache and pipelines it's tedious but not difficult to compute execution time. In C that's impossible. Even looking at the generated assembly sheds little light on the subject since calls to the runtime package are opaque at best.

One could instrument the code to measure execution times quantitatively. Change the code, though, and it's critical to repeat the measurements. Base a design on RMA and there are significant long-term maintenance issues where perhaps plenty of changes and enhancements can be anticipated.

Recently a friend extolled the virtues of RMA. He has yet to actually use it in a real embedded system of any significance. In my travels around the embedded landscape it's rare to find a group using it. Do you? What's your experience?

Free Embedded Muse newsletter - twice/monthly, hard-hitting technical info that goes to 48,000+ engineers. Click here to sign up or enter your email here: