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.