Linux Kernel 2.6: the Future of Embedded Computing, Part I
The embedded computing universe includes computers of all sizes, from tiny portable devices--such as wristwatch cameras--to systems having thousands of nodes distributed worldwide, as is the case with telecommunications switches. Embedded systems can be simple enough to require only small microcontrollers, or they may require massive parallel processors with prodigious amounts of memory and computing power. PDAs, microwaves, mobile phones and the like are a few typical examples.
With the release of kernel 2.6, Linux now poses serious competition to major RTOS vendors, such as VxWorks and WinCE, in the embedded market space. Linux 2.6 introduces many new features that make it an excellent operating system for embedded computing. Among these new features are enhanced real-time performance, easier porting to new computers, support for large memory models, support for microcontrollers and an improved I/O system. In this two-part article, we look at the improvements in the 2.6 kernel that have empowered it to make a foray into the demanding world of embedded computing.
For the uninitiated, embedded systems often need to meet timing constraints reliably. This is the most important criterion of an embedded system. Thus, a job executed after its scheduled deadline is as good as--or as bad as--a job executed incorrectly. In addition, embedded systems have access to far fewer resources than does a normal PC. They have to squeeze maximum value out of whatever is available. Often, a price difference of as little as $2 or $3 can make or break a consumer device produced on a large scale, such as wrist-watches.
Some real-world applications require the OS to be as reliable as possible, because the application is a part of a mission-critical operation. The OS should perform reliably and efficiently, if possible, under the cases of extreme load. If a crash occurs in one part of the module, it should not effect other parts of the system. Furthermore, recovery from crashes should be graceful. This more or less holds true for other non-critical embedded applications as well.
Having seen the requirements of a general embedded system, we now look at how well the Linux 2.6 kernel can satisfy these requirements. As mentioned earlier, embedded systems have stringent timing requirements. Although Linux 2.6 is not yet a true real-time operating system, it does contain improvements that make it a worthier platform than previous kernels when responsiveness is desirable. Three significant improvements are preemption points in the kernel, an efficient scheduler and improved synchronization.
As with most general-purpose operating systems, Linux always has forbidden the process scheduler from running when a process is executing in a system call. Therefore, once a task is in a system call, that task controls the processor until the system call returns, no matter how long that might take. As of kernel 2.6, the kernel is preemptible. A kernel task now can be preempted, so that some important user application can continue to run. In Linux 2.6, kernel code has been laced with preemption points, instructions that allow the scheduler to run and possibly block the current process so as to schedule a higher priority process. Linux 2.6 avoids unreasonable delays in system calls by periodically testing a preemption point. During these tests, the calling process may block and let another process run. Thus, under Linux 2.6, the kernel now can be interrupted mid-task, so other applications can continue to run even when something low-level and complicated is going on in the background.
Embedded software often has to meet deadlines that renders it incompatible with virtual memory demand paging, in which slow handling of page faults would ruin responsiveness. To eliminate this problem, the 2.6 kernel can be built with no virtual memory system. Of course, it then becomes the software designer's responsibility to ensure enough real memory always is available to get the job done.
The process scheduler has been rewritten in the 2.6 kernel to eliminate the slow algorithms of previous versions. Formerly, in order to decide which task should run next, the scheduler had to look at each ready task and make a computation to determine that task's relative importance. After all computations were made, the task with the highest score would be chosen. Because the time required for this algorithm varied with the number of tasks, complex multitasking applications suffered from slow scheduling.
The scheduler in Linux 2.6 no longer scans all tasks every time. Instead, when a task becomes ready to run, it is sorted into position on a queue, called the current queue. Then, when the scheduler runs, it chooses the task at the most favorable position in the queue. As a result, scheduling is done in a constant amount of time. When the task is running, it is given a time slice, or a period of time in which it may use the processor, before it has to give way to another thread. When its time slice has expired, the task is moved to another queue, called the expired queue. The task is sorted into this expired queue according to its priority. This new procedure is substantially faster than the old one, and it works equally as well whether there are many tasks or only a few in queue. This new scheduler is called the O(1) scheduler.
Applications involving the use of shared resources, such as shared memory or shared devices, have to be developed carefully to avoid race conditions. The solution implemented in Linux, called Mutex, ensured that only one task is using the resource at a time. Mutex involved a system call to the kernel to decide whether to block the thread or allow it to continue executing. But when the decision is to continue, the time-consuming system call was unnecessary. The new implementation in Linux 2.6 supports Fast User-Space Mutexes (Futex). These functions can check from user space whether blocking is necessary and perform the system call to block the thread only when it is required. When blocking is not required, avoiding the unneeded system call saves time. It also supports setting priorities to allow applications or threads of higher priority to have first access to the contested resource.
LinuxThreads, the current Linux thread library in Linux, is bad. In fact, "the fellow is as brain-damaged as LinuxThreads" is a common expression among kernel hackers. The improved threading model in 2.6 is based on a 1:1 threading model, one kernel thread for one user thread. It also includes in-kernel support for the new Native Posix Threading Library (NPTL). The kernel's internal threading infrastructure has been rewritten to allow the Native POSIX Thread Library to run on top of it.
NPTL brings an eight-fold improvement over its predecessor. Tests conducted by its authors have shown that Linux, with this new threading, can start and stop 100,000 threads simultaneously in about two seconds. This task took 15 minutes on the old threading model.
Along with POSIX threads, 2.6 provides POSIX signals and POSIX high-resolution timers as part of the mainstream kernel. POSIX signals are an improvement over UNIX-style signals, which were the default in previous Linux releases. Unlike UNIX signals, POSIX signals cannot be lost and can carry information as an argument. Also, POSIX signals can be sent from one POSIX thread to another, rather than only from process to process, like UNIX signals.
Embedded systems often need to poll hardware or do other tasks on a fixed schedule. POSIX timers make it easy to arrange any task to be scheduled periodically. The clock that the timer uses can be set to tick at a rate as fine as one kilohertz, so software engineers can control the scheduling of tasks with precision.
Hardware designs in the embedded world often are customized for special applications. It is common for designers to need to solve a design issue in an original way. For example, a purpose-built board may use different IRQ management than what a similar reference design uses. In order to run on the new board, Linux has to be ported or altered to support the new hardware. This porting is easier if the operating system is made of components that are well separated, making it necessary to change only the code that has to change. The components of Linux 2.6 that are likely to be altered for a custom design have been refactored with a concept called Subarchitecture. Components are separated clearly and can be modified or replaced individually with minimal impact on other components of the board support package.
By formalizing Linux's support for the slightly different hardware types, the kernel can be ported more easily to other systems, such as dedicated storage hardware and other components that use industry-dominant processor types.
In the embedded marketplace, simpler microcontrollers often are the appropriate choice when low cost and simplicity are called for. Linux 2.6 comes with the acceptance and merging of much of the uClinux project into the mainstream kernel. The uClinux project is the Linux for Microcontrollers project. This variant of Linux has been a major driver of support for Linux in the embedded market. Unlike the normal Linux ports we are accustomed to, embedded ports do not have all the features that we associate with the kernel, due to hardware limitations. The primary difference is these ports feature processors that do not feature an MMU, or memory management unit--what makes a protected-mode OS protected. Although these generally are true multitasking Linux systems, they are missing memory protection and other related features. Without memory protection, it is possible for a wayward process to read the data of, or even crash, other processes on the system. This may make them unsuitable for a multi-user system but an excellent choice for a low-cost PDA or dedicated device.
The 2.6 version of Linux supports several current microcontrollers that don't have memory management units. Linux 2.6 supports Motorola m68k processors, such as Dragonball and ColdFire, as well as Hitachi H8/300 and NEC v850. Also supported is the ETRAX family of networking microcontrollers by Axis.
With major vendors in the consumer devices market forming such associations as the Consumer Embedded Linux Forum (CELF), Linux is becoming the first choice among operating systems in the consumer devices market. To help with the consumer devices market, Linux 2.6 includes the Advanced Linux Sound Architecture, or ALSA. This state-of-the-art facility supports USB and MIDI devices with fully thread-safe, multi-processor-safe software. With ALSA, a system can run multiple sound cards and do such things as play and record at the same time or mix multiple audio streams.
Video4Linux, the system for supporting video, is all new in Linux 2.6. Although it is not backward-compatible with previous video paradigms, it is intended for the latest stable versions of radio and TV tuners, video cameras and other multimedia. And on a completely new track, Linux 2.6 includes the first built-in support for Digital Video Broadcasting (DVB) hardware. This type of hardware, common in set-top boxes, can be used to make a Linux server into a TiVo-like device, with the appropriate software.
In Part II of this article, we look at human device interfaces, networking filesystems and 64-bit machines.
Aseem R. Deshpande is a software engineer who studied at the University of Pune in India. He has been working as an embedded software developer for the past year and a half. His other interests include Grid computing and helping people to "fall". He can be contacted at aseem_deshpande@hotmail.com.
