To accommodate that requirement, we added a real-time clock (RTC), nothing more than an interrupt that fired on a regular schedule. In pidgin Ada, the structure looks something like this:

loop
accept RTC
read sensors
update filters
correct steering
end loop

In this Ada-ese, the program may seem as though it's in a continuous loop. I mean, that's what loop...end loop usually means, right? But appearances can be deceiving. See that accept RTC in the first line? That identifies the code as an interrupt handler. In Ada task-speak, the handler task is blocked until the interrupt is received. When it's received, the handler runs to completion, then sits and does nothing until the next clock tick. There is no real loop there, only an interrupt handler that runs each time it's pulsed by the interrupt.

If the CPU is idle until an interrupt comes in from the RTC, what does it do in the meantime, twiddle its thumbs? No, it executes the background task, whatever that is. The pseudocode for that task often reads:

loop
perform self-test
report errors
end loop

This one is a true loop, in that it runs as fast as it can. In short, it uses all the CPU resources not absorbed by the interrupt handler. In addition to the self-test, we often give it slow tasks to run, and these can, and often do, include a Kalman filter. Kalman filters tend to be slow and require floating-point arithmetic. In the old days, floating point usually meant software floating point, so it was slow. Unlike other digital filters, the Kalman filter doesn't much care about timing; it takes the time of the measurements into account. So we let the Kalman filter take as long as it needed, chugging along in the background whenever the fast stuff wasn't running.

For the record, the code for that multivariate function minimizer ran in the background. It took as long as it took, which wasn't very long on a fast 486 with its hardware math processor.

Multitasking

I chuckle every time I see Unix/Linux described as a multitasking OS. Ditto for Windows. I suppose they are, in the lingo of computer science, but they certainly aren't what we embedded folks thought of as multitasking.

To an aerospace software engineer, multiple tasks typically mean cyclic tasks, each running at different, but fixed, rates. This approach was taken simply for expediency and out of an acceptance of the facts of life; our CPUs weren't fast enough to do everything at the fastest interrupt rate. So we ran only what needed to be done fast at the interrupt rate. Everything else was counted down from that fastest rate. In a typical multitasking system, we had cyclic tasks at rates like 1,000Hz, 500Hz, 100Hz, 20Hz, 10Hz, and 1Hz. The RTC ran, of course, at the 1,000Hz rate. Its pseudocode might be:

loop
accept RTC
do 1000Hz
if divide_by(2)
do 500Hz
endif
end loop

The 500Hz task, of course, would divide by five to call the 100Hz task, and so on. Simple.

Whenever you have multiple tasks, you confront the issue of sharing data between them. Because tasks can be interrupted by higher priority tasks, we must make sure that the data

doesn't change between accesses. Typical solutions include semaphores and mutual exclusion mechanisms.

The beauty of a cyclic scheduler is that it rarely needs such stuff. If the 1,000Hz task is running, it can be certain that slower tasks aren't. Therefore, their data is not going to change during the life of the faster task. If it needs data from them, it simply goes and reads it.

The converse is not true, but easily handled. When I'm running in, say, the 1Hz task, I have to be sure that the data I'm operating from doesn't change during my computation. So the faster task is not allowed to stuff data into the slower one; the slower one must go get it, and make a local copy. Better yet, the faster task simply passes the data as parameters:

do 500Hz(data1, data2, ...)

The compiler takes care of making the local copy.

Computer science purists will cringe at this one, but, in a pinch, I've been known to suspend interrupts during the time I'm fetching or stuffing data. It's hardly elegant, but it's fast and simple.

Build or buy?

Whenever I start a new project involving real-time systems, my first task is deciding whether to buy a commercial RTOS or "roll my own." It's not a decision to be sloughed over.

But whatever decision I make, I find that its consequences are similar to deciding whether to use someone else's code: whichever way I go, I find myself wishing, at some time or another, that I'd gone the other way.

If I roll my own RTOS, I'm faced, not only with writing my own RTOS, with all its potential for hidden and subtle bugs, but with justifying my decision to management when the task takes longer than I expected. If I use an off-the-shelf RTOS, I find myself with a system that's much more complex than I usually need, and I'm spending time climbing the learning curve when I could have been writing code. Neither approach is completely satisfying or free of risk, so we should weigh the pros and cons carefully.

Leaf through the pages of this magazine, and you'll find ads from a number of RTOS vendors. They're our advertisers, bless 'em, and all of their products are good; some are great. Most of them do their job as advertised.

Even so, I find that almost all give me more gizmos than I really need. They include all the features that users clamor for, such as the ability to dynamically create and remove tasks; sophisticated priority mechanisms, including dynamic adjustment of priorities; multiple methods for passing messages and/or data between tasks, and so on. Much of that power is wasted for many of the problems I deal with. Not only am I carrying extra baggage around in the form of mechanisms I don't really need, but even the things I do need take longer, thanks to mechanisms that are more general than I require.

Then there's the frustration factor. Only last year, I was listening to my colleagues bemoan their fate, because the device driver that came with a commercial RTOS was broken. They couldn't get the vendor to even admit that it was broken, much less get a commitment as to when it would be fixed. A word to the wise: if you use an off-the-shelf RTOS, get source.

Until the last few years, my build/buy decision always came down on the build side.

It's true that cyclic executives are a special case, and perhaps deserve special treatments. Today, the trend is much more towards asynchronous tasks, and especially to tasks that are dynamically created. I know that. Even so, I'm not completely convinced that complex solutions are necessary.

As recently as 1994, I was working on a contract to develop real-time software for yet another antenna controller. The customer had chosen the Motorola 68332 chip-an excellent choice, in my opinion-and I was helping him make the build/buy decision. I looked at the features the 68332 provides:

• Built-in RTC with programmable rate
• Built-in watchdog timer
• Built-in serial and parallel ports, with programmable interrupt behavior
• Built-in background debug capability
• Built-in counter-timer chip with ability to run independently of CPU

I looked at all those features, and thought, "Dang, all I have to do is write the interrupt handlers, and the RTOS is mostly done." That particular build/buy decision was easy.

During that decision-making process, I talked to a number of RTOS vendors. Most were extremely helpful and savvy, and I wouldn't have had a problem using any of their products. One company (sorry, can't recall the name) offered the RTOS complete with source code in C, for $1,000. That's cheap. It's much less than what our four-man team burned in a single day.

It's hard to justify building your own RTOS when good stuff is available so economically. Even so, we felt that the time spent learning how to use someone else's OS would probably cost more than the time to write our own. So we did. And we never regretted it.

That was then, this is now

Fast forward to 2002. Now we have super-fast processors with tons of RAM and, often, hard drives for mass storage. The problems tend to be more complex than they used to, and involve a lot more asynchronous tasks. We have RTOS vendors out the gazoo, and virtually all the systems can be counted on to come with free GNU C/C++ development tools. So do we build or buy?

I think I'm suggesting that the issue is still not clear, and that you should make the decision with considerable thought. Some problems are so complex that the notion of writing one's own OS is too horrible to contemplate. Others are simple enough that 90% of the RTOS's capabilities are going to go unused (and you're going to take both a performance and a memory hit). Each decision needs to be made based on the individual situation.

In our family room, we have one of three TiVo video recorders. If you haven't tried one, you should. We almost never watch live TV anymore, except to check on the news. By recording everything, we can fast forward through the commercials and slow-mo through the fast action. Watch Lara Croft: Tomb Raider in slo-mo and I guarantee you, you will see things that went right past you the first time. Like those slick, super-fast reload clips for her guns. Angelina rules.

But the TiVo is most definitely not real time, even in the airline reservation system sense. It records TV onto a hard disk in real time, and pulls it back off, too. But the user interface is positively glacial. How long can it take to bring up a pop-up menu? Try a TiVo, and you'll find it's a lot longer than you thought.

What's the "RTOS" in the TiVo? It's Linux. Not real-time Linux (RTLinux). Just plain Linux. I think maybe each time I press a button on the remote, it's logging me in as a new user. Or something like that.

Why use Linux for a set-top box? Well, for one thing, it comes complete with the GNU tools, which surely must be a big plus to the developers. Then there are the databases, which contain a list of channels and their program lineup. An SQL engine to access them must surely be nice. Still and all, I think the choice was a lot more pleasant for the developers than for us poor users.

RTLinux?

In previous columns, you've heard me say that I was looking forward to working with RTLinux. I've seen it working in the demos at the Embedded Systems Conferences, and it seems pretty nice. However, especially after seeing some of the uglier sides of Linux, I'm beginning to have second thoughts.

Recall that the developers solved the problem of RTLinux by first writing a real-time kernel. Then they overlay Linux, including the Linux kernel, on top of it. In effect, Linux and its kernel are running as an application on top of the real-time kernel.

It seems like a neat enough solution, and it certainly works well in demos. But think about it from a structural point of view. When one is developing a kernel for an OS, surely there has to be something better than developing two kernels, one on top of the other. Surely some efficiency has to be lost in the process.

You know me: I'm a big fan of Linux, just as I was of Unix, if only because it's a better way to go than the obvious alternatives. But I'm not a fanatic about it. I tend to judge systems by how well they work, not whether I like their heritage. And face it. The heritage of Linux is not exactly earth shaking. It's a clone of an old time-share system that was, itself, a clone of an even older time-share system-Multics. That Linux has come so far, and done so well, is a testament to the ingenuity and efforts of the people involved in its development. But the Multics/Unix heritage can be burdensome. Backward compatibility constrains solutions that might otherwise be solved in other ways.

Aside from its open-source nature, which is certainly a big plus, Linux has a lot going for it in that wonderful, GNU toolset. I'm just not convinced that RTLinux is going to be efficient enough. Hey, if I'm questioning the need for even an RTOS of any kind, I can't exactly recommend the heck out of RTLinux, can I?

Is there an alternative? Perhaps so. We have a couple of true RTOSes that are also in the open-source tradition. One is C/OS, from Jean Labrosse. The other is Red Hat's eCOS.

How's this for an alternative to RTLinux? Start with either of the true RTOSes. Add a compatibility layer that will emulate not the Linux kernel itself, but the view that the applications see of it. That way, Linux applications, including the GNU toolset, will work on the system, but we can also access the RTOS kernel for our real-time apps. Think about it.

At least one variant of real-time Linux (www.timesys.com) does not use the kernel-atop-kernel approach. I just learned about this one and will be looking into it in the near future. If any readers know of other alternatives, please e-mail me.

Interrupt-driven

I'm going to close this month's offering with a really slick little real-time, cyclic exec that I ran across years ago, and fell in love with. It's just like one I mentioned earlier, with one important exception:

loop
accept RTC
do 1000Hz
enable interrupts
if divide_by(2)
do 500Hz
endif
end loop

See that third line, enable interrupts? That's the key to the whole thing. Once the high-speed stuff is done, the interrupts are enabled so that another one can come in. Then the slower tasks can go about their business, happily taking their time, while the high-speed task gets interrupted again.

In general, when we write an interrupt handler, we want to leave the interrupts disabled for the minimum amount of time. This reduces jitter to a minimum. But in this case, the entire program is, in effect, an interrupt handler! It works because interrupts are enabled again, as soon as possible. The tasks are themselves reentrant, so all of them, except the bottom level, can be called more than once.

Customers of mine have often had trouble understanding this architecture, and I've tried to think of simple diagrams to show the behavior of the design. The best I've been able to come up with is the analogy of a pinball machine, with countdown counters in place, as in Figure 1.

Figure 1 Real-time pinball

Imagine that a ball enters the pinball machine at the top, passing through the 1,000Hz task. It then drops through to the bottom. But every second time, it's diverted to the 500Hz task. Similarly, in the 500Hz task, most of the balls fall through, but one out of five is diverted to the 100Hz task, and so on.

Once the system gets going, we can conceivably have different balls in various stages, passing through every single one of the tasks. If the code is truly reentrant, as it should be, we could even have multiple balls in a given path. Our only requirement is that the balls (interrupts) don't come in so fast that the tasks choke on them. The entire program is, in effect, an interrupt handler, and every bit of it is reentrant.

Remember how an interrupt works. When an interrupt comes in, the current context is saved on the stack, and the handler starts to work. In this case, if another interrupt comes in, that context is also stacked, and yet another instance of the handler is started. We only require that the average rate of interrupts is low enough to keep the stack from overflowing.

It's a slick solution, and I've seen it used in more than one life-critical system. In those systems, we used switches to make sure that task overruns didn't occur. Each was a simple semaphore that got tested and set at the top of each task, and cleared at the end. But even that mechanism is more stringent than it needs to be. As you can see from the discussion of stacked contexts above, multiple instances of a given task can be working, as long as the stack doesn't grow forever by too many interrupts. A simple test on the stack depth can detect that condition.

The design has the features I mentioned earlier: passing data between tasks takes a minimum of handshaking, and, in the low-to-high speed direction, takes none at all.

Keep it simple

So what's my point? Am I trying to put all our RTOS-vending advertisers out of business? Am I anti-Linux? No, not at all. I'm simply saying, let the punishment fit the crime; let the solutionfit the problem.

I'm a big believer in the KISS principle(Keep It Simple, Sam). Albert Einstein said, "Things should be made as simple as possible, but not any simpler." Or, as the great race car designer Harry Miller put it, "Simplify, and add lightness."

Maybe that new embedded gimcrack you're building doesn't really need full-up Linux, or RTLinux. Maybe a good, solid RTOS will do. Maybe it doesn't need an RTOS—a cyclic exec will do. Maybe even a simple while-loop and some interrupt handlers will do.

Don't be in such a hurry to start, that you forget to do your build/buy study. You get no points for building the world's most complex alarmclock.

Jack W. Crenshaw is a senior software engineer at Spectrum-Astro in Gilbert, AZ. He is also the author of Math Toolkit for Real-Time Programming, from CMP Books. He holds a PhD in physics from Auburn University. Jack enjoys contact and can be reached via e-mail at jcrens@earthlink.net.