<i>There are nine and sixty ways of constructing tribal lays, And every single one of them is right!</i> —Rudyard Kipling <i>Internationale: In the Neolithic Age</i>
Does it come as any surprise that the terms "embedded systems" and "real time" have no fixed meanings? Indeed, there are at least as many definitions as there are organizations, programs, and applications in the field. The situation becomes even more complex with regard to Linux, which has overlapping distributions, modifications (aka patches), and wholesale replacements for various chunks of the system, each with a specific design point that may or may not be obvious (or even discernible) from the documentation.
While I won't cover each of the nine and sixty ways, let's peer through the underbrush to determine what the chanting is all about over there.
Run the One You're With
As we saw in last month's column, your situation may not demand a true hard real-time operating system. Unless the program's input and output operations must occur on a precise schedule, with limited jitter and no tolerance for the occasional missed deadline, you can save yourself a considerable amount of hassle by not insisting on real-time performance.
Although the GNU/Linux design point lay in the desktop and server arena, the Linux kernel itself has evolved to include many of the POSIX real-time functions. You can, for example, define a thread to have "real time" priority so the scheduler will, at least in principle, run it before any ordinary threads. You can lock chunks of virtual memory in RAM to avoid unpredictable disk paging delays. You can even define the type of scheduling algorithm to use, specifying round-robin to ensure that each thread spends some time alone with the CPU.
Unfortunately, the kernel simultaneously impedes hard real-time execution. The key problem involves latency, the amount of time the kernel spends doing things that cannot be disturbed by any other task. The stock Linux kernel may spend tens to hundreds of milliseconds mulling its own concerns, leaving all other processes starved for attention. If it shuts off interrupts while it's pondering, the interrupt handlers also incur unpredictable delays.
Even threads with real-time priority won't execute until the kernel resumes scheduling. For applications that demand very low and very consistent latency, this can be at best annoying and, at worst, catastrophic. In any event, delays of more than a few tens of milliseconds count as "real time" only by courtesy.
Another issue involves the Linux scheduler, which examines dispatchable threads one-by-one to determine which it should execute. Even for nominally real-time threads, this imposes a delay that increases roughly linearly with the number of threads. This scheduling delay may be acceptable, depending on your application's design point, coding style, and the total number of threads.
After a user-program thread begins execution, the kernel can regain control either cooperatively through a system call or preemptively on the tick of the 10-ms system clock. This implies that even real-time threads incur at least 10 ms of scheduling jitter when a low-priority thread runs to the completion of its time slice in the absence of a system call.
Although the Linux system can preempt user programs, the kernel cannot preempt itself. As a result, the maximum scheduling latency must include the longest path through the kernel as a result of a system call, which can be very large indeed. Worse, it's an unbounded unknown, as there's no practical way to examine and tally each possible kernel code path.
Nevertheless, if your timing requirements aren't too tight (most aren't) and you value a straightforward solution (this is), the stock kernel way may be right for you.
If it isn't, you'll find that many folks have tweaked the kernel code to either overcome these limitations or push them to a different part of the system. Their changes fall into roughly two categories — patch it or supplant it.
Interior Renovation
The biggest improvement in Linux real-time performance comes from reducing kernel latency, which involves finding the longest code paths in the kernel and inserting preemption points in spots where the kernel can safely yield control to another part of itself.
The stock Linux kernel includes several dozen preemption points at key places in the code where it might otherwise stall for protracted intervals. Because the original kernel design point didn't include real-time issues, its preemption points occurred mostly in spots that improved human-scale responsiveness.
Ingo Molnar published a set of kernel patches (http://www.kernel.org/pub/linux/kernel/people/mingo/lowlatency-patches/) that added several dozen preemption points, with an eye toward improving real-time responsiveness. His changes reduced the overall kernel latency by a factor of about 50 and the resulting millisecond-range latencies became an improvement other operating systems would die for.
Additional kernel patches from, among others, Andrew Morton (http://www.uow.edu.au/~andrewm/linux/schedlat.html) reduced the scheduling latency and moved the Linux kernel into the low-millisecond area, at least on average.
MontaVista's Hard Hat Linux (http://www.mvista.com/) takes this method further by taking advantage of the kernel's Symmetric MultiProcessor (SMP) preemption points, cracking additional long paths and similar measures. By combining several sets of improvements, then measuring and verifying the effects, they offer a convenient one-stop resource for folks who'd rather just get on with their project instead of messing with the Linux kernel.
MontaVista also reduced the duration of interrupts-off kernel processing, which dramatically reduced the interrupt latency and improved the scheduler's handling of threads marked with real-time priority. If your project's design point permits a small amount of time-critical code to run in an interrupt handler, backed with bulk processing in soft real-time threads, this may be the right way for you.
A key advantage of these methods is that program development remains entirely Linux based. With simple-enough interrupt handlers, the odds of them working correctly get pretty good and you may not spend much time debugging the hard real-time part of your code. That's the optimistic view, anyhow.
The corresponding disadvantage is that your real-time code runs in kernel mode, where many of the safeguards against system damage simply aren't present. Suffice it to say that, given absolute power, even a wee mistake can absolutely corrupt your system, yea, even to the point of Necessitating the Reinstallation of the Everything.
The kernel-patching technique has another limitation brought on by the fact that it must operate within the original Linux-system design. Despite all the preemption points, some kernel (or installable module) code can, as Andrew Morton describes on his page, "simply kill its scheduling latency." Innocent user actions may occasionally invoke kernel functions with, for one reason or another, huge latencies. In some cases, those long kernel functions run with interrupts disabled for an even nastier effect on responsiveness.
Which brings up the notion of design points once again: You'd not even think of coding that sort of thing in a real-time kernel, but it works fine for normal desktop and server applications. Inserting real-time modifications into the kernel isn't the same as building a real-time kernel, although it may come fairly close when you maintain tight control over the entire system for its whole lifetime. If you can, this way can be right for you.
Truly hard real-time specs lie in the consistent submillisecond range, where software kernel patches simply can't go, and demand interrupt and scheduling latencies are unaffected by functions that users should avoid. To get there from here, we must move beyond the Linux kernel.
Firm Support
The Intel IA-32 architecture supported hardware virtualization since the 80386 days (long before it was known as IA-32, in fact), improving performance and control with each successive CPU generation. Hardware virtualization allows a sufficiently well-written program to be indistinguishable from silicon, unless you carefully count elapsed microseconds.
The Linux Real-Time Application Interface (http://www.aero.polimi.it/projects/rtai/) and Real-Time Linux (http://www.rtlinux.org/) projects use IA-32 hardware virtualization to install a small hard real-time kernel that captures the CPU's hardware interrupt machinery and provides a faked version of reality to the Linux kernel. The two projects have, as befits the Open Source movement, differing implementations and goals, but they seem to be converging on a common feature set.
In essence, both RTAI and RTLinux separate your code into hard and soft real-time sections. The hard real-time code must run under the hardware virtualization kernel, depositing and receiving data from memory buffers (via FIFOs, semaphores, and what have you) and never, ever calling a Linux kernel function.
The magic occurs when the hard real-time code returns control at the end of the interrupt that invoked it. The virtualization kernel passes control back to the Linux system, which runs as it normally would, with no knowledge of the interrupt or the real-time handler. The Linux threads read and write those same memory buffers via similar methods, processing the data without much regard to elapsed time.
When another interrupt occurs, the virtualization kernel regains control, decides what to do, and the cycle repeats. Some interrupts can be passed directly to Linux, while others trigger real-time tasks. The interrupt response time can be a consistent few tens of microseconds because the virtualization kernel controls the interrupt hardware and can preempt the entire Linux kernel without interference or damage.
Because the virtualization kernel even captures timer ticks, there are some issues, such as maintaining the Linux system clock time, that make this a bit more finicky than it seems, but the principle is straightforward enough.
As a rule of thumb, the virtualization kernel supports relatively few program-callable functions and imposes a rather strict view of what's allowable in the real-time code. In particular, niceties such as memory protection and complex I/O simply aren't there. However, you can do a lot of CPU-bound processing based on hard real-time data I/O. If your needs fit that model and your soft real-time routines can stand the delay, this can be the right way.
This being Linux, you can, of course, mix and match approaches as you like. The REDSonic Linux distribution (http://www.redsonic.com/) combines the RTAI kernel and Linux kernel patches with a resource-allocating scheduler, to provide real-time performance and low-latency dispatching. In effect, user programs can toss data between the very low-latency RTAI hardware interface and the quick-dispatching threads running under Linux.
Embedix Realtime from Lineo (http://www.lineo.com/) takes a similar approach, with either RTAI or RTLinux providing the hard real-time functions and a modified Linux kernel supporting soft real-time features. It builds on Lineo's Embedix embedded systems distribution, which is specifically tailored for smaller systems that lack the bells and whistles required by the somewhat ponderous stock Linux distributions.
I do, however, take issue with Lineo's definition of a "microprocessor" — a 32-bit CPU with 4 MB of RAM and 2 MB of flash ROM isn't a microprocessor, even if they'll sell you one on a SIMM or DIMM. Well, these days, maybe that is a microprocessor...but what shall we call those little 8051- and Microchip PIC-class thingies?
But, for small and very dedicated systems, this can be the right way.
Revolt from Below
Carrying this approach to its logical conclusion, you can slip a whole 'nother operating system beneath GNU/Linux apparat, then run all of Linux as a low-priority, very squishy real-time task. That OS presents a completely virtualized version of the hardware to Linux, faking the operation of the usual interrupt machinery, I/O ports, memory management unit, and other functions. Fairly obviously, the virtualizing system need have no DNA in common with either GNU or Linux, although some attention must be paid to getting the interfaces working correctly.
The OnCore Systems (http://www.oncoresystems.com/) microkernel takes even this notion to an extreme, in that it supports multiple operating systems simultaneously, with real-time handling of both interrupts and scheduling. OnCore's microkernel provides memory protection using the MMU hardware for the real-time code, with (optionally paged) virtual memory for all. Some delicate Linux kernel tweaks can move scheduling and interrupt handling into the OnCore kernel, for a dramatic increase in responsiveness.
Developing and debugging code for an attached real-time kernel — let alone a substrate OS — poses an additional challenge. A single interrupt or OS call may transfer code from user to kernel to real-time kernel to real-time handler to...well, you get the picture. Keeping all this straight adds yet another level of complexity to an already difficult task; don't venture here without both a clear need and a definite recognition from all parties that you're not in Flatland any more.
But, for projects that must incorporate great lumps of disparate legacy code, this may be not only the right way, but the only way to stitch all the pieces together. Don't assume that you need such complexity, but if you find you do, don't try a piecemeal approach. That surely won't be right!
It's worth mentioning that debugging any real-time project, be it hard or soft or somewhere in between, is orders of magnitude more difficult than the usual desktop apps. Be sure you can figure out exactly what happens when your code misbehaves, how you can track down, identify, and display the failing module, then understand what's required to fix it up. Software is hard and real-time software is exceedingly hard: You need all the help you can get!
Reentry Checklist
I have certainly left out more than I've covered in this column, but you should now have a hint of what's shaking in the jungle. Forgive me for omitting your favorite kernel hack or pet distribution: Each technique I mention has many implementations and each distribution includes megabytes of additional features...and every single one of them is right for someone.
Licensing and IP issues remain conspicuously missing from this discussion. Depending on whether your code runs in kernel or user space, whether it's a loadable kernel module or an interrupt handler, how you interpret the GPL text, and perhaps how viciously effective your (opponent's) lawyers are, Open Source may present a truly insuperable business opportunity. I don't have a firm grasp on the details, but I'd definitely like to know more. Can you recommend a good guide?
For my entire life, I've known without doubt that Kipling wrote "four and twenty ways." A web check shows general agreement, although some say "four and sixty," one guy insists on "five and twenty," and many prefer "writing" to "constructing." Truth is not, however, determined by majority vote, no matter how convenient that might be in some situations: All but one of them is wrong!
My collection of stuff disgorged a CD with a scanned image of "Rudyard Kipling's Verse, Inclusive Edition," copyright 1920, which I'll accept as authoritative. The moral? Don't accept everything you read, either on the Web or in print, without checking the primary sources to be sure.
Especially anything you know to be true. 'Nuff said?
DDJ
