Real-Time Linux

A newlywed Brazilian grad student brought his wife to Boston for a week's vacation around his presentation and gained some hard-won experience: Never leave your valuables unattended in an international hostel. Although the hostel staff eventually recovered their passports from a trash can, $400 in cash vanished. We chipped in to get them back on their feet while musing that, well, at least they'd never make that mistake again.

Tuition at the School of Experience can be steep, so they got off lightly.

The Fourth RT Linux Workshop was hosted at Boston University, had one presentation track with parallel kickstart tutorials, and fit neatly in a single auditorium. Unlike the paired-up Embedded Systems Conference and Software Development shows held two weeks earlier and a mile closer to downtown Boston, glitzy commercial booths were completely absent and the after-hours meetings had (excellent!) home-baked cookies.

The presentations ranged from academic studies to nuts-and-bolts applications, with a liberal seasoning of kernel internals and business practicalities. The Q&A sessions after each paper demonstrated that English isn't a bad intermediate language, as even I could follow a conversation with Chinese on one end and Italian on the other.

Let's consider the meaning of "Linux," then see where the pursuit of real-time programming has gone.

Basic Linux

Linux has, if nothing else, multiple personalities: It appears on desktops, servers, handheld doodads, embedded systems, routers, and anything else you can think of. But what exactly does it mean for a device to run Linux?

According to DistroWatch (http://www.distrowatch.com/), you can install any of over 100 different Linux distributions (aka "distros"), each designed with a particular use and user in mind. In fact, DistroWatch doesn't count embedded distributions, so Linux distros for nonPC-oid gizmos are grossly underrepresented.

The single common point of all those distributions is the Linux kernel, the heart of "the operating system," which provides the features and facilities we now take for granted from computer-based systems. The kernel handles memory allocation, networking, file systems, I/O drivers, and all the classic OS functions. The kernel doesn't include much in the way of a user interface, however, and few creature comforts.

The various distributions surround that common kernel with whatever collection of programs they deem appropriate. Because most of those programs descend from the GNU project's family of code, once you figure out how one distribution works you'll be at least acquainted with the others. Each distro includes a few unique programs, whether for installation or to provide specific tools. Just to keep you on your toes, the exact location of various configuration and system files tends to differ, for no good reason that I've ever understood.

You need not start with a Linux distribution. You can fetch the latest kernel source code from http://www.kernel.org/, include or exclude various features, tweak it as you like, compile it, and install the resulting binary file (perhaps you can see a problem already) on whatever hardware you choose. This process presupposes you have a functional Linux development system, deep expertise, and a stout heart, but this may be precisely what's required for a new embedded system.

That minimal system, with just the kernel and nothing else, is "running Linux" in the purest sense. Of course, without any programs the kernel isn't going to be doing anything particularly useful. Add the special-purpose program of your dreams, however, and you're in complete control.

Most people and most companies have other things to do than hammer out kernel adaptations from scratch, so you'll find a variety of embedded distributions tailored to specific CPUs, hardware platforms, and intended uses. The rule of thumb here says that the code itself will be freely available, but expect to pay for the expertise required to get it running on your system if you're not up to speed.

Basic Time

The fundamental Linux design presumes a fairly substantial 32-bit CPU with memory-management hardware, a filesystem of some sort, and the usual human-oriented I/O gear. Although the kernel has been successfully adapted to greater and lesser architectures, the more weird the system, the less it behaves like Linux.

For example, memory management provides bedrock isolation between various tasks running under the kernel's control. By separating their memory addresses and prohibiting one task from meddling with another's internal affairs, Linux can prevent many of the problems that afflict systems with less rigid controls.

But suppose you're using a Motorola Coldfire CPU that lacks a memory-management unit (MMU)? With some diligent effort, you can rip out the kernel code that uses the MMU, adapt the memory allocation routines to work with pure physical addresses, and still call the result "Linux." Which is precisely what the folks at Lineo did some years back.

Incidentally, Lineo subsequently became Embedix, which was recently absorbed by Metroworks, now a Motorola subsidiary. Amazing how these things work out, isn't it?

The original Linux kernel implemented an OS for a human-operated computer along the general UNIX concept of a multitasking interactive system. It was most definitely not designed as an embedded operating system, much less a real-time OS, so the kernel tends to behave in ways that maximize fairness across tasks and increase overall throughput.

A real-time OS, on the contrary, can ensure that a specific task runs at a particular time or at a fixed rate regardless of how many other tasks clamor for attention. Its timing facilities have microsecond accuracy, rather than the milliseconds common to desktop systems. It may place restrictions on memory use, I/O handling, and anything else needed to ensure predictable task timing.

Surprisingly enough, the Linux kernel can be contorted to support those requirements. As with any development effort, of course, the first few iterations of the real-time kernel code provided proofs of concept rather than production code.

What's new and different? The various kernel modifications, programming techniques, and associated knowledge base have become stable enough for real applications written by pretty much ordinary folks. Although real-time programming requires careful design and implementation to avoid races and deadlocks and mysterious bugs, these problems are both known and solvable. The fact that you need not be a particularly deep wizard nor build the OS infrastructure by hand means that you can concentrate on getting your job done.

Faster Time

The 2.6 kernel version, which should be out Right About Now, will have greatly reduced kernel latency. Older kernels had latencies that could range up to hundreds of milliseconds, even if the average was under 10 milliseconds. These improvements began with Robert Love's low-latency kernel patches and are now incorporated directly in the kernel code.

Latency refers to the time elapsed between a hardware interrupt, whether from an external device or a system timer, and the system's response. A real-time system must, by definition, have sufficiently low latency to service interrupts quickly enough, whatever those terms mean in the particular application.

Stock Linux can be used in slow real-time applications that tolerate a response within few hundred milliseconds, which actually suffices for many purposes. Kernel 2.6 reduces latencies to the millisecond range, which means even more applications will be do-able with out-of-the-box Linux distributions.

This will smooth out desktop multimedia applications and produce a more responsive user interface even under heavy loads, essentially without requiring any user-level system tuning. What's good for real-time turns out to be good for the rest of us, too.

In the embedded world, however, you must take into account events that don't affect desktop computing. A real-time task that incurs virtual memory paging probably won't meet its next deadline and you must be aware of rogue apps (the X Windows system was mentioned with some heat) that can disable interrupts for extended periods that might not disturb your contemplation of a PC's display.

Latency is not the entire story, either. If you're driving a stepper motor, as some of the folks at the Workshop were doing, you must have not only fast response with low jitter, but also a high repetition rate. If the total path length from the interrupt through your handler and back out of the kernel approaches the total time between interrupts, the system won't get anything else done.

Unfortunately, reducing that path length requires substantial changes that distort the kernel beyond recognition. The favored approach inserts a real-time layer beneath the Linux kernel to handle interrupts and schedule real-time tasks.

Both RTLinux (http://www.fsmlabs.com/) and RTAI (http://www.aero. polimi.it/~rtai/) add a special-purpose, real-time kernel that runs the Linux kernel as a low-priority task. Getting Linux out of the loop drops latencies to microseconds and boosts periodic rates over 10 KHz. You must, however, program outside the normal Linux model without most of the facilities, protections, and creature comforts available to standard user programs.

A group at the National Optical Astronomy Observatories applied RTAI to Red Hat 7.3 in an adaptive optics module for one of their telescopes. The closed-loop correction runs at 4 KHz to produce ground-based viewing rivaling the Hubble Space Telescope. Their pictures were most impressive: http://www.noao.edu/ image_gallery/html/im0760.html.

The periodic interrupt rate can hit 10 s in stepper motor drivers for machine tool controllers. At that pace, the actual interrupt handlers must have very, very little code to avoid soaking up the entire CPU, but it can be done!

Blindsided by Moore

You'll recall from last month's column that about 3/4 of the microcomputers produced each year have 4- or 8-bit CPUs. Of the remainder, a sliver of a fraction currently run Linux because it presumes a 32-bit CPU with a generous hunk of memory.

Moore's Law, the famed doubling of capacity every two years or so, applies across the board. The most visible effect is probably in retail PCs, which have achieved performance levels far beyond the needs of mere mortals.

As of December 2002, you can buy a Dell dual-Xeon box complete with Windows XP for under $2000 direct to your door. The retail price for a dual-CPU system board with a pair of CPUs and a gig of RAM is hovering around $500. If you were OEMing that stuff into an embedded gizmo the cost might drop under $300.

With those prices in mind, Concurrent Computer Corp. (http://www.ccur.com/) has a Red-Hat-based Linux distro called "RedHawk" featuring shielded processors and a variety of development tools. Basically, one CPU handles all the mundane kernel stuff while another CPU executes only real-time interrupts and processes. In essence, Moore's Law allows them to make the latency problem go away by throwing increasingly cheap hardware at it.

Concurrent Computer uses the now-standard low-latency patches, plus some additional tweaking to reduce the effect of kernel spin locks. RedHawk exhibits an interrupt response time of a few tens of microseconds on a 1.4-GHz shielded CPU. This applies even during heavy system loads, because the other CPU handles all the normal system functions.

Zero-Cost embedded systems, where additional programmer-months of effort pay off in reduced unit cost, cannot afford this approach just yet. For high-end systems positioned deep in the Zero-Delay market segment, where reduced development time means everything, an extra CPU or three (there are no stock three-way systems) could pay off handsomely.

Works In Progress

With reasonable real-time response now built into the Linux kernel and hard real-time response becoming standardized, what's left? Several academic papers proposed solutions to problems that only become apparent after you've got most of the hard real-time machinery working fine.

Because RTLinux and RTAI run the Linux kernel (and, thus, the normal user interface) as the lowest-priority task, a heavily loaded system can have a glacial GUI. Worse, a rogue real-time task can suffocate the Linux kernel by soaking up all available CPU cycles. Although it may be hard to imagine, errors happen—your code, a do-until() loop, an external event that never occurs. Pity.

The only recovery involves the Big Red Switch, but Linux aficionados display a serious aversion to system resets.

Avoiding that faux pas requires resource reservation to both allot each task a specific fraction of the CPU cycles on a specific schedule and enforce that allocation. If your real-time task requires, say, 200 s of CPU time every millisecond, a reservation supervisor can guarantee the Linux kernel gets the remaining 80 percent. The user interface and other nonreal-time tasks can always execute, so you remain in control and the system up-time counter continues to tick.

In addition to temporal protection, quality-of-service reservations for network communications, memory protection for real-time tasks, and access to real-time facilities from user mode are all getting considerable attention. Each of these efforts will extend real-time performance in ways that should pay off for ordinary users in a few years.

Sounds good to me!

Contact Release

The Proceedings of the Fourth Real-Time Linux Workshop will be available at http://www.realtimelinuxfoundation.org/. As you may have guessed, this is a shoestring operation and your membership will support their web bandwidth.

The folks at Aeolean put together an excellent summary of the real-time Linux world that includes a huge, linked bibliography at http://www.aeolean.com/html/ RealTimeLinux/RealTimeLinuxReport.jsp. This was a NIST contract project.

DDJ