I begin this column with an apology. I did something bad, and I'm sorry.

If you were with me last month, you read about the disaster of my recent move and the fact that the movers had to wrest the keyboard from my hot, sweaty fingers to get the computer in its box. I suppose that's the reason they bunged it up during the move, trashing my RAM and perhaps my hard drives.

In that fateful column, I had promised to upload the "minimizer lite" version of the algorithm I've been working on for so long. I had checked out the algorithm in Mathcad, and verified that it worked beautifully, but I had not yet finished turning the changes into code. I figured, how hard can it be? The important deadline is to get the prose to the editors on time. Coding can take longer because I have more time in which to do it.

There's typically a two-month delay between the time I send the column to the editors at Embedded Systems Programming, and the time you get to see it. I figured it was a slam dunk that I'd get the code complete and uploaded before you saw the column saying that it was uploaded. In short, I floated a rubber check.

And it bounced.

Who would have guessed that it would take three months for me to get back online again? Usually it's a time measured in days. And who would have guessed that when I did get online, the data, including my partially finished code, would be gone to that bit bucket in the sky?

I cheated, and I got caught. Sorry. Trust me, I've already been read the riot act by my editors, and it's a lesson I learned well, the hard way.

Coming attractions

The name of the column is "Programmer's Toolbox," and my stated goal has been to provide you with tools and techniques to aid in the development of embedded systems. It occurred to me recently that you might be wondering what sorts of embedded systems I work on, that I need things like function minimizers, root crackers, and so on. Such routines seem more suited for huge math problem solvers than embedded systems.

Your embedded systems probably don't look much like mine. Even so, trust me on this: everything I've told you about came from the development of an embedded system. In fact, my interest in the minimizer came directly from a production, commercial product. That same system also used a real-time least squares fit.

The embedded systems that I work on tend to use a lot of math.

During the time I was occupied by the minimizer, many other topics attracted my attention, and were put on the back burner. Now that the minimizer is coming together, I've begun turning my attention to them. I thought you'd like to know what's coming up in the near future. Here's a partial list:

• The Nelder-Mead, or Simplex method (yet another minimizer!). This workhorse is probably the most-used minimizer for multivariate systems, and is definitely worth a look. But I'm putting it off for a time, mainly because I'm worn out with minimizers for the moment.

• Spline functions. Everybody and his brother has a spline function algorithm in his toolbox, and most of them work just fine. But I needed one that gave the derivatives of the function, as well as the fitted function. The canned routines don't do that. So I had to derive my own functions. In the process, I learned that the derivation isn't at all easy. The spline algorithm seems to be another one of those things, like Brent's method, that everyone uses but no one (or, to be more precise, few people) has bothered to derive for themselves.

• Optimal curve fits. This is not the same thing as a spline fit, because we don't necessarily require that the fitted function pass through the data points.

• The least squares fit. I covered this one once before, years ago, but it's been a long time. It's due for a revisit.

• Chebyshev polynomials, which are used to improve function approximations.

• Laplace transforms: second nature to EEs, a mystery to everyone else, and gateway to z-transforms.

• The Kalman filter. Yes, I know, others have done this in Embedded Systems Programming ("Kalman Filtering," June 2001, p. 72). As you might expect, my approach will be different.

• Nonlinear root finder. I've talked about this one several times during the effort on a minimizer, and I just happen to have the world's best algorithm in my back pocket. It's only fair that I share it with you.

Is it possible that such things are in embedded systems? Yes and no. In once sense, they must be, because I'm using these techniques. In another, though, it's worthwhile to mention that not all the software for an embedded system actually ends up in the system. When we're building an embedded system, we also need software to test it. Most days, that means a simulation that exercises the code as it would be run in the real world. Someday perhaps, I'll write an article about how to test real-time software. Or you can buy Jim Ledin's new book, Simulation Engineering (CMP Books, 2001), which covers everything you ever wanted to know about simulations. Suffice it to say here that often a very sophisticated simulation is needed to be sure that algorithms always work.

If you'd like to see me cover any other topics, don't hesitate to contact me.

And now for something completely different

But I don't want to talk about any of those things this month. Instead, I'm in the mood for a change of pace. I want to talk about real time operating systems (RTOSes). I want to because I'm seeing trends in the industry that I'm not sure I'm ready for.

Before we get too far into the notion of an RTOS, we're first going to have to define what we mean by the terms real time and embedded system. Make no mistake: I'm talking real-world definitions here, not pedagogical, theoretical definitions. In general, I tend to write about the things I've actually worked on in the past, and this column will be no different.

I used to think I knew what real-time embedded systems were. They were things like numerical process controllers, chemical plant controllers, and flight computers for things that fly or swim and blow stuff up. Now that we have computers in video recorders, telephones, and those glorified calculators called personal digital assistants (PDAs), the definition is beginning to get a little fuzzy. I used to teach a course in software engineering for my company, and the illustrator we used was a wonderful cartoonist. He drew me a picture of an engineer, running along beside a tank with a Teletype ASR-33. The caption was, "Embedded systems are hard to debug." I mean that kind of embedded system.

Likewise, it's often been said that any system can be considered real time if your definition is loose enough. Many Unix aficionados tend to say that Unix and its clone, Linux, are real-time systems. But surely, they can only be defined so loosely. To paraphrase Bill Clinton, it all depends on what "real" is.

There are two kinds of people in the world: those who categorize things into two kinds, and those who don't. Most engineers categorize real-time systems into the "hard" and "soft" varieties. A soft real-time system is one in which tasks need to be done promptly, but not at a precise time or on a precise schedule.

When some folks talk about a system being "real time," they mean that it must complete its work in a time that's short compared to whatever the user considers a reasonable wait. By that definition, any OS is an RTOS. Except perhaps the old batch processing OSes, which still exist in some business mainframes. Airline reservation and point-of-sale systems are "real time" in the sense that we'd like a response the same day. But that hardly qualifies as a real-time system in the usual sense, and most of us don't accept such a definition.

Soft real-time embedded systems might include printers, cellphones, PDAs, and digital video recorders.

Hard real-time systems must perform their duties either at regular, specified time intervals, or respond within time intervals that are tightly controlled, both in response time and in jitter-the variation in response from step to step. Such systems tend to control things and have digital filters inside. If the system doesn't do things on schedule, data gets missed and the filters don't work properly. Since most of the systems I work on end up flying, or otherwise calculating based on streaming data, they tend to be very, very hard.

I'll leave it to the academics to find definitions that are completely unambiguous. As one Supreme Court justice said concerning pornography, "I may not be able to define it, but I know it when I see it."

Why an RTOS?

The first question we should ask ourselves is do we even need an RTOS? The first microcomputers didn't. When Intel first introduced their 8080 microprocessor (a real piece of work, by the way, which I've praised before as a breakthrough of biblical proportions), they wrote up one of those ads masquerading as an application note, showing an 8080 controlling a traffic light. Four pressure pads, six sets of light bulbs. That was the extent of their imagination.

You don't need much of an RTOS for a system to run a traffic light.

(Good as Intel was in their design of the chip, I don't think they ever, in their wildest dreams, envisioned personal computers, CP/M and 64KB Altairs, Osbornes, Morrows and Kaypros. It was the hobbyists that saw the potential of the 8080 and the later chips like Z80, 6800, and 6502. Guys like Gary Kildall, Bob Albrecht, Dennis Allison, Carl Helmers, and the two Steves: Jobs and Wozniak.)

A few years ago, I attended one of Robert Ward's conference presentations on the taxonomy of real-time, embedded systems. I won't begin to try to fill Robert's shoes, but the "RTOS" for that traffic light controller was right there at the beginning of his taxonomy. In pseudocode, it is:

do something
do it again

Or, if you prefer something more structured:

loop forever
do something
end loop

That's it. No multitasking; no interrupt handler; no TCP/IP stack. No priority queues. No classes. No persistent objects, except in the sense that everything was persistent, until you turned the power off.

The first program I wrote for the 8080, back in 1976, worked this way. It was a controller for a satellite-tracking antenna and it worked by performing a Kalman filter on the tracking data. If I'd known enough in those days to write pseudocode at all, it would have been:

loop forever
take a measurement
update the state
point the antenna
end loop

Maybe I should have thrown in some initialization, but really, that was about it. Timing was not an issue. You took a measurement as soon as you could, which meant as soon as you finished processing the last one. What else did the CPU have to do?

About the same time, I also wrote a program for an even earlier chip, the 4-bit 4040, to control a cold forge machine. It looked like this:

while !E-stop loop 
drop a blank into place
move the anvil to its position
whang it with the forge
retract them both (finished part falls out)
end loop

Oh, there were a bunch of safety related tests, like checking the Emergency-stop button before every operation, and also readings of the control buttons and sensors, to tell if we were doing the right thing. But basically, that was the program. Again, we had no need for even a timer, because as soon as the CPU was finished with one loop, we wanted it to do it all again.

You'd be surprised how often this simple structure works. Back before the Internet, there were bulletin board systems (BBSes) and CompuServe. Ward Christensen developed both a program and a protocol for transferring data over phone lines, called Modem7. It worked pretty doggone well, better in some ways than AOL. (Think of it: no flashy pop-ups, no self-regenerating porn ads, no computer viruses attached to e-mail.)

The problem with Modem7 was the classic one of chicken vs. egg. Though not at all large by modern standards, Modem7 was not the kind of thing you wanted to type into your assembler. You needed to download it, and before you could do that, you needed Modem7. Catch-22.

To get around that little problem, they came up with a bootstrap program called Boot7, whose only function was to download Modem7. I had a listing for Boot7, but somehow I made a mistake typing it in, so I couldn't get online.

To at least get me talking, I wrote my own modem program. Here it is, in all its glory:

char key = ' ';
while key != ^Q loop
if (char in serial buffer)
c = getchar
write c to CRT
endif
if (key == inkey)
send key to modem
endif
end loop

Incidentally, thanks to heavy use of well-done BIOS functions by Teletek, the manufacturer, that little gem used exactly 19 bytes of Z80 assembler language. Not bad, eh? No megabyte RAMs needed, thank you very much.

Later, I added a rudimentary-not even circular-text buffer. Acting on a control key (probably ^D), I'd start capturing downloaded text into the buffer (being careful not to overflow it-a caution modern programmers seem to sometimes forget). I'd run the program under DDT, the CP/M debugger, and after I was done, I'd write the buffer to a file. The program kept a character count to tell me how many sectors to write. Not elegant, I admit, but it let me download Boot7, with which I downloaded Modem7, with which, well, you get the picture.

Is there a message in all these war stories? You bet there is: "Don't use an RTOS when you don't need one."

On being on time

In the aerospace industry, most gadgets are just a smidge more complicated than the simple, loop-as-fast-as-you-can systems I've described. The main issue that characterizes control systems in the aerospace world is time.

Typically, an aerospace system reads things like gyro and accelerometer outputs, and uses them as the source for steering commands. As I hinted earlier, such systems tend to use digital filters of a fairly high order. What characterizes such filters is that the measurements must be made as on-time as one can manage. The filters depend on measurements taken at regularly spaced intervals.