Follow @jack_ganssle

The logo for The Embedded Muse For novel ideas about building embedded systems (both hardware and firmware), join the 27,000+ engineers who subscribe to The Embedded Muse, a free biweekly newsletter. The Muse has no hype, no vendor PR. It takes just a few seconds (just enter your email, which is shared with absolutely no one) to subscribe.

By Jack Ganssle


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.

The very definition of a hard real-time system is one that suffers unacceptable failure when a deadline is missed. Yet, ironically and somewhat horrifyingly, practically every multitasking embedded app avoids failure due simply to luck since the usual scheduling algorithm doesn't allow for a provably-correct bit of software. A perfect storm of interrupts and task requirements can bring the system down. We developers build in time margins. and then crouch in a metaphorical foxhole, head down, hoping that nothing goes wrong.

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 insure 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?