With its low cost, abundant features and inherent openness, Linux provides fertile ground for creativity in embedded computing. As its importance grows, we can even expect Linux to become the platform where progress first happens. The question is, could Linux 2.6 be the breakthrough version we’ve been anticipating for embedded systems—the version that opens the floodgates to Linux acceptance? The answer is "yes."

The embedded computing universe is vast and encompasses computers of all sizes, from tiny wristwatch cameras to telecommunications switches with thousands of nodes distributed worldwide. 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. Linux 2.6 delivers enhancements to provide support across the spectrum of these embedded needs as well enhancements in the general areas of determinism, reduced memory contention, and the leveraging of POSIX for thread creation and management and task scheduling. Taken together, these enhancements serve to both "firm up" Linux for embedded computing while making it a more attractive alternative for a wider range of embedded applications.

Firming Things Up

On the "firming up" front, timing constraints are endemic in many embedded applications and must be met reliably. Linux is not yet a true real-time operating system, yet Linux 2.6 introduces improvements that make it a far more worthy platform than in the past when responsiveness was an issue. The three most significant improvements are:

• Preemption points in the kernel
• An efficient scheduler
• Enhanced synchronization

As with most general-purpose operating systems, Linux has always forbidden a process scheduler from running when a process is executing in a call. Once a task was in a system call, that task controlled the processor until the call returned, regardless of how long it took. This can cause more important tasks to be delayed while waiting for the system call to complete.

With Linux 2.6, the kernel is now preemptible to a degree, making 2.6 more responsive than 2.4 and giving implementors better control over the timing of events. Moreover, in Linux 2.6, kernel code has been salted with preemption points that enable the scheduler to run and possibly block a current process so as to schedule a higher priority process.

The 2.6 kernel can also be built with no virtual memory system, which solves a major sticking point in regard to responsiveness. Software that has to meet deadlines is incompatible with virtual memory demand paging, in which slow handling of page faults can ruin responsiveness. However, getting rid of virtual memory means the developer must ensure that there will always be enough real memory available to meet application demands.

Efficient Scheduling

Along with becoming somewhat preemptible, Linux 2.6 features a rewritten process scheduler developed to eliminate the slow algorithms of past versions. Previously, the scheduler had to look at each ready task and score its relative importance. The time required for this algorithm varied with the number of tasks and thus complex multitasking applications would suffer from slow scheduling.

In Linux 2.6, the scheduler no longer scans all tasks each time. Instead, when a task becomes ready to run it is sorted into position on a queue called the current queue. The scheduler only has to choose the task at the most favorable position on the queue. Consequently, scheduling is done in a constant amount of time. When the task is actually running, it is given a period of time it may use the processor before it has to give way to another thread. When its time slice expires, the task is moved to another queue, called the expired queue, and sorted according to its priority.

Eventually, all of the tasks on the current queue will have been executed and moved to the expired queue. When this happens, the queues are switched: the expired queue becomes the current queue, and the empty current queue becomes the expired queue. As the tasks on the new current queue have already been sorted, the scheduler can once again resume its simple algorithm of selecting the first task from the current queue. Not only is this procedure substantially faster than in the past, but it also works equally well whether there are many tasks or just a few. A comparison of test response times between 2.4 and 2.6 is shown in Figure 1.