W H I T E

P A P E R

Embedded Linux

–

Ready for Real-Time

Prepared by

Bill Weinberg, MontaVista Software Inc.

1
Title of White Paper
Copyright © 2001 MontaVista Software, Inc. All rights reserved. DATE

Embedded Linux – Ready for Real-Time – White Paper

Table of Contents

Introduction ..................................................................... 4

Embedded and Real-Time: Identity Crisis? .................... 4

Four Paths to Real-Time Linux ....................................... 6

Conclusion .................................................................... 10

Embedded Linux – Ready for Real-Time – White Paper

Abstract

Embedded Linux is changing the face of embedded development

and calling into question decades-old assumptions about how to

build systems with real-time requirements. This paper reviews

those assumptions and details how Linux can provide a viable

platform for a range of response-sensitive embedded applications.

Embedded Linux – Ready for Real-Time – White Paper

Embedded Linux –
Ready for Real-Time

Bill Weinberg and Claes Lundholm

1. Introduction

Embedded Linux is upsetting the established order in the development tools marketplace.
Developers are choosing Linux over traditional proprietary RTOS products for its superior
reliability, for its cost effectiveness, and for its open source and standard APIs. After almost 20
years of using products like VRTX, pSOS, and VxWorks, developers are eager to embrace Linux,
but express reservations about its ability to address real-time performance requirements. This
article responds to such concerns about Linux performance, questioning some basic assumptions
about embedded and real-time, and describing how Linux can be applied to solve a variety of
real-time problems.

2. Embedded and Real-Time: Identity Crisis?

A stroll down the aisles of a Real-Time show or the Embedded Systems Conference, or a
conversation with any number of embedded tools vendors, gives the casual observer the
impression that most if not all embedded systems applications present a hard real-time
requirement.

Figure 1.: Popular assumptions about Embedded and Real-Time – a large intersection

Embedded equals real-time, real-time equals embedded – you can use the “other guys’” OS if
you don’t really have a real-time need.

In the authors’ experience, investigation of actual developer’s requirements paints a different
picture – perhaps 10-15% of all embedded applications have a any real-time requirement, and
perhaps half of those applications actually have a demonstrable need for hard real-time.

Embedded Linux – Ready for Real-Time – White Paper

Figure 2.: Market reality – most embedded designs are non or soft real-time

Moreover, many truly hard real-time applications fall outside the domain of traditional embedded.
The remaining majority of embedded applications benefits from responsiveness, but relies on
throughput to achieve design goals – “real-fast” or “just fast enough” suffices.

Many developers, regardless of the actual hard or soft real-time needs of their application,
choose to design in an RTOS as insurance, both against unanticipated current responsiveness
needs, and against anticipated future ones.

2.1 Faster Silicon, Same Slow World

While processor clock speeds double every 12 to 18 months, the speed of real world events has
not changed appreciably in the lifetime of the embedded microprocessor. Factory floor processes
do not proceed any faster, and rockets and planes broke the sound barrier while tubes still ran
the show. Human perception of sights and sounds has not accelerated in the last 50,000 years!

Whereas a decade ago, designers had to squeeze every last cycle out of an 8 MHz 16 bit
processor design, today’s developers have rather more luxury and slack in applying 300+ MHz 32
and 64 bit CPUs to comparable real-time challenges.

General-purpose software and systems suppliers, Microsoft and Sun in particular, have leveraged
these consequences of Moore’s Law to promote the use of WindowsNT/2000 and Solaris/SPARC
in real-time, mission critical applications. And, while there exist multiple options for real-time
responsiveness in Linux, these same trends are accelerating Linux acceptance in the real-
time/embedded design domain.

2.2 How Real-Time is Your RTOS?

Before you dismiss Linux out of hand for not functioning as a traditional RTOS, take a good look
at the embedded OS you are using today. Most, if not all, self-designated real-time operating
systems contain design flaws and other not-so-obvious challenges to delivering deterministic
response times:

•

Most popular RTOS products have grown so complex that their suppliers cannot provide provable
worst-case blocking times or latencies, forcing the vendors to publish only statistical data (and by
practice only best-case and nominal data). Lacking easy access to source code and difficult
commercial terms for evaluation, most developers cannot perform a proper benchmark themselves.

Embedded Linux – Ready for Real-Time – White Paper

•

Just like typical GPOS (General Purpose OS) products, most RTOSes do not scale well, and
display both longer latencies and increased jitter as the number to tasks and other managed
objects increases.

•

One very popular RTOS suffers from increasingly non-deterministic memory allocation
performance over time, as its malloc-derived management scheme succumbs to ever-greater
fragmentation and free-list walking times.

•

Another, UNIX-like RTOS touts its message-based microkernel architecture, while its complex
internal state(s) and driver architecture render it incapable of delivering deterministic response
times.

•

Many RTOS file systems, despite boasts of “real-time” features like contiguous files and raw
partition access, offer lack-luster throughput and jittery response.

•

Several embedded operating systems that offer MMU-based memory protection introduce
significant jitter from both TLB spills and from poor implementation of process/thread memory
model context switches. This deficit is especially evident on low-end PowerPC processors like the
PowerQUICC (Linux happens to handle these CPUs very well!).

2.3 Hardware Impact on Real-Time

Putting the vagaries of particular embedded OS products themselves aside, it is important to note
that microprocessor hardware itself is a major impediment to determinism. Processor and system
design can have equal or even greater influence upon real-time performance than the software
running on them, for better or for worse:

Today’s cache-based CPU architectures induce large amounts of jitter from cache spill/refill
times, but given the performance enhancement that instruction and data caches offer, no one
would ever suggest running these processors with the caches turned off!

The flip side of hardware impact lies with the handling of both response and throughput-sensitive
tasks by specialized hardware that appears as intelligent peripherals to the main CPU/OS: DSPs,
specialized I/O engines like the PowerQUICC CPM, dedicated networking processors, and
programmable gate arrays. These devices remove the burden of much if not all real-time
responsiveness from the main CPU. With responsibility for real-time “descending” into hardware,
the main CPU/OS then focuses on throughput-intensive application computation, and
“housekeeping” activities.

3. Four Paths to Real-Time Linux

Linux, in its present incarnation (2.2/2.4 kernel derivatives), is not a real-time operating system by
traditional definition or functionality. To date, Linux design philosophy has emphasized throughput
over responsiveness and determinism: its scheduler employs exhaustive fairness-based thread-
selection, and can promote low priority threads to the head of the ready list, per its own criteria, to
avoid starvation.

Embedded Linux – Ready for Real-Time – White Paper

Non-Preemptible

Linux Kernel

Non-Preemptible

Linux Kernel

System Call

Execution

Flow

Pre

-emp

tio

Scheduler(s)

Non-Preemptible

Linux Kernel

Non-Preemptible

Linux Kernel

System Call

Execution

Flow

Pre

-emp

tio

Scheduler(s)

Figure 3.: Non-preemptible Linux kernel

Moreover, the Linux kernel itself is non-preemptible (again, to enhance throughput), with relatively
long blocking times – no rescheduling can take place until the kernel completes a system call or
other internal activity and prepares to return control to the calling context.

Given this history and these design constraints, let us examine how and when to use Linux in
applications previously considered the exclusive domain of the above MOLRTOSes (More Or
Less RTOSes).

3.1 Linux As-is : Real-fast as Real-time

Microsoft WindowsNTand indeed Sun/Solaris have been applied for years to at both soft and
hard real-time applications, relying on the increasing sprightliness of Wintel and SPARC
hardware to overcome the shortcomings of the general-purpose OS software running on them.
Linux can equally be applied to the real-fast for real-time solution, and offers comparable to
superior performance to the Microsoft and Sun GPOS platforms under similar loads. Where Linux
excels is in price/performance: WindowsNT (and presumably Windows2000) induces high system
costs with its insatiable appetite for RAM and CPU clock; Solaris/SPARC, a proprietary OS
running on decidedly non-commodity hardware, does not benefit from the economies that drive
down the price of WinTel machines. Linux can leverage the power of even down-rev system
hardware – its original claim to fame in the enterprise world. Linux holds its own even with as little
as 8-16 MB of RAM and sub-200 MHz clock speeds, and can address sub-millisecond response
requirements.

On more modern, and nowadays ubiquitous hardware (e. g., an 800 MHz Pentium III), an
unmodified Linux 2.4 kernel exhibits average task response times under 60 microseconds.

3.2 Giving Linux a Tune-Up: Kernel and Device Driver Optimization

In many if not all applications with a definable real-time requirement, this requirement is
constrained to definable portions of the hardware and software environment, such as handling
audio or video packets in a streaming application. While the above “real-fast” methodology could
be applied to such areas (as it is with Windows), it suffers from degradation with scaling of load –
additional clients, streams, or higher data rates result in lost packets, perceivable quality loss, and
missed deadlines for mission-critical responses. Without too much investment in time and
resources, the Linux kernel and device drivers can be tuned to offer needed responsiveness. At
MontaVista Software, we engaged in just such a tuning exercise, first building tools to measure
Linux interrupt response, and then applying them to a variety of applications on x86 and
PowerPC, and other processor architectures. To date, our customers have deployed over 250
embedded designs based on embedded Linux need or recourse to anything but standard code
and tuned drivers.

Embedded Linux – Ready for Real-Time – White Paper

Linux device drivers present developers with both a rich, tantalizing set of off-the-shelf resources,
and a potential performance trap, when those same drivers turn out to be sub-optimal, with
lengthy interrupt blocking times or other architectural flaws. The good news is that the Linux
driver model is inherently sound – even quick-and-dirty Linux drivers exhibit decent performance
(e.g., network interface drivers). And, while some might consider driver-writing a “black art”, at
least the scope of tunable code is highly constrained in function and size.

The key is to audit ALL drivers that you design into a system to insure that no one driver is a
bottleneck. Linux facilitates such audits and testing, first by being open source, and second by
featuring a dynamically installable kernel module/device driver architecture.

3.3 Kernel Substitution

Inserting a second kernel, as occurs with the use of RTLinux and RTAI, is merely a more
generalized approach to device driver tuning. Instead of just tweaking a few critical hardware
interfaces, these real-time add-ons provide a nominally generalized RTOS API and threading
model, while relegating the main Linux kernel to the status of a low priority (idle) thread under
their control. Mainstream, “normal” Linux applications and RTLinux/RTAI threads communicate
through shared memory and a limited set of other, mostly ad hoc, IPCs. RTLinux and RTAI
applications are written with the same structure as Linux kernel modules, that is, with potentially
full access to Linux internals and without full benefit of the memory-protected process-based
programming model.

Linux purists look askance at such strategies because they inject a significant non-Linux
component into the picture. At worst, their use is compared to the Viet Nam War era quip – “To
save this village, we must first burn it to the ground!” – to use Linux for real-time, we must first
throw it away! While the open source project leaders of both RTLinux and RTAI caution
developers to constrain the use of the RT components to areas of absolute necessity, creeping
use (and indeed any use) raises the risk of starving the main Linux kernel and applications.

RTLinux, RTAI, and comparable strategies are best employed when an application’s real-time
requirement exhibits a very broad scope, as in highly-loaded industrial control, signal processing,
and aerospace applications, and where the mainstream Linux APIs are leveraged for only non-
time-critical housekeeping operations.

3.4 Transparent Scheduler and Preemptible Kernel : Preserving Linux APIs

Given the general acceptance of existing Linux APIs, the cleanest path to real-time is one that
neither breaks those extant mechanisms, nor introduces one more set of APIs into the picture.
Thus, the ideal means to meeting real-time requirements is to make Linux itself more responsive.

3.4.1 Fixed Overhead Scheduler

A first step in this direction is to enforce the so-called real-time policies already present in Linux
threads repertoire (POSIX.1c), SCHED_FIFO and SCHED_RR. In stock Linux kernels, these
policies theoretically arbitrate like-priority execution for the 0-99 priority levels implied by the real-
time policies, but in reality, both the priorities and the policies are too often overridden if not
ignored outright.

A build option for MontaVista Linux enhances the scheduler to implement these policies correctly
on a priority scheme of 128 or more levels; the MontaVista schedule runs in front of the default
exhaustive fairness-based based scheduler, enforcing hard prioritization and policies on all calls
to the Linux scheduler. Should no identifiable real-time threads be available for execution, control
is then passed to the standard scheduler. This API-transparent scheme correctly implements

Embedded Linux – Ready for Real-Time – White Paper

hard prioritization, but does not address the issue of kernel preemption, and so only offers soft
real-time responsiveness.

3.4.2

Fully Preemptible Linux Kernel

Until recently, achieving a fully preemptive system (without breaking or stretching Linux APIs)
was not deemed possible by the Linux community. Interesting, there has for some time existed a
preemptible kernel technology that resides at the core of the Linux kernel itself – the standard
SMP (Symmetric Multi Processing) version of Linux, extremely popular and broadly deployed in
enterprise applications, offers highly preemptible and deterministic response when built and
configured for uni-processor systems.

On mid-range Pentium systems, these kernels exhibit task response / preemption latencies
averaging under 2.5 microseconds!

MontaVista Software is building and shipping its standard MontaVista Linux kernel with user
selectable options to build such a preemptible kernel for a variety of embedded applications, by
applying the company’s open source “preemption patch” to its standard configurations for x86/IA-
32, PowerPC, StrongARM/XScale, ARM, MIPS, and SHE architectures.

3.4.3

The Preemption Patch

The MontaVista preemptible kernel patch modifies the definition (implementation) of the SMP
kernel’s primary IPC, the spinlock, changing it from its SMP specific implementation to a
preemption lock. In the preemption scenario, as in its SMP application, the locking function acts
as a control on reentrancy to critical sections of kernel code.

Additionally, the preemptible kernel patch modifies the interrupt handling software to allow
rescheduling on return from interrupt if a higher priority process has become executable, even if
the interrupted process was running in kernel mode (provided the process is not in a critical and
locked region). SMP spin unlocks are also redefined to return the system to a preemptible state,
and check if an immediate context switch is needed.

Lastly, the kernel build definition for a uniprocessor target system is modified to include the
spinlocks construct (implemented as preemption locks). Through these basic changes, the Linux
kernel becomes generally preemptible (with short non-preemptible regions corresponding to the
spinlocked regions in an SMP kernel). Process level responsiveness is dramatically improved,
both on average and worst cases.

3.4.4 Preemption and Throughput

At a simplistic level, changing a uniprocessor kernel to add internal reentrancy management
means “more code” and hence “more time” spent traversing that code. Thus, theoretically, such a
preemptible kernel will exhibit reduced throughput. However, at the heart of the throughput issue
is the question of a balanced system design, and overall design objectives. How important is a
more responsive Linux? In a world of streaming media, responsiveness is every bit as important
as throughput.

A demonstration of the preemptible kernel performing simple audio processing shows that even a
trivial load on non-preemptible Linux causes user process delays that exceed the threshold of the
human ear (Figure 4.) Loads typically include both compute and I/O intensive operations like
building the Linux kernel (make, gcc, file system), performing massive file copies/transfers,
exercising network files systems (NFS) and running the NIST POSIX.1 test suites.

Embedded Linux – Ready for Real-Time – White Paper

Figure 4.: Audible glitching from loading a stock Linux 2.4 kernel while streaming audio

(the red line at 3 ms represents audible effects)

Figure 5.: Minimal jitter from loading a preemptible Linux 2.4 kernel while streaming audio

With preemption enabled, these delays are vastly reduced, with no audible distortion (Figure 5.).

4.0 Acceptance of the MontaVista Preemptible Kernel

Since its initial inception as an open source project in mid 2000, the MontaVista Preemptible
Kernel has received extremely positive reviews from embedded developers, open source
hackers, and third-party evaluations in the press.

4.1 Linux Journal 2001 Editor’s Choice Award

Linux Journal recognized the importance of MontaVista’s contribution to open source and
embedded/real-time by awarding the 2001 Editor’s Choice for Best Real-Time Tool to the
MontaVista preemptible kernel patch, in particular for how it enhanced performance of multimedia
clients on heavily loaded systems. See

http://www.linuxjournal.com/article.php?sid=5525

Embedded Linux – Ready for Real-Time – White Paper

4.2 Acceptance into the Linux 2.5 Kernel Tree

An even greater hallmark of acceptance of MontaVista real-time technology was the inclusion of
the preemptible kernel technology into the 2.5 experimental kernel, a precursor to its general
adoption for future standard versions of Linux. See

http://www.linuxdevices.com/news/NS3989618385.html

5.0 Conclusion

Linux, is undeniably changing the face of embedded development and pervasive computing.
While past instances of UNIX-type operating systems, including standard Linux itself, were
arguably inappropriate for embedded and real-time (size, speed, storage, CPU support),
embedded Linux is proving itself to be scalable and sprightly enough for up to 95% of embedded
developers real-time requirements.

Multiple options exist for imbuing embedded Linux with more deterministic response
characteristics. With the advent of fully preemptible, open source kernel configurations/builds like
those from MontaVista, developers with real-time needs and a desire to build their applications on
an open platform like Linux, can enjoy enhanced determinism without giving up the open APIs
and broadly supported core architecture that drew them to Linux in the first place