WH 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
Copyright © 2001 MontaVista Software, Inc. All rights reserved 2
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.
Copyright © 2001 MontaVista Software, Inc. All rights reserved 3
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.
Copyright © 2001 MontaVista Software, Inc. All rights reserved 4
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.
Copyright © 2001 MontaVista Software, Inc. All rights reserved 5
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.
Copyright © 2001 MontaVista Software, Inc. All rights reserved 6
Embedded Linux  Ready for Real-Time  White Paper
Execution
Execution
Flow
Flow
Non-Preemptible
Non-Preemptible
Non-Preemptible
Non-Preemptible
Linux Kernel
Linux Kernel
Linux Kernel
LinuxKernel
Scheduler(s)
Scheduler(s)
Scheduler(s)
Scheduler(s)
Scheduler(s)
Scheduler(s)
System Call
System Call
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.
Copyright © 2001 MontaVista Software, Inc. All rights reserved 7
n
n
o
o
i
i
t
t
mp
mp
e
e
-
-
e
e
r
r
P
P
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
Copyright © 2001 MontaVista Software, Inc. All rights reserved 8
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.
Copyright © 2001 MontaVista Software, Inc. All rights reserved 9
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
Copyright © 2001 MontaVista Software, Inc. All rights reserved 10
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
Copyright © 2001 MontaVista Software, Inc. All rights reserved 11
Embedded Linux  Ready for Real-Time  White Paper
NOTES:
Copyright © 2001 MontaVista Software, Inc. All rights reserved 12
Embedded Linux  Ready for Real-Time  White Paper
Corporate Headquarters
United States
MontaVista Software, Inc.
1237 East Arques Ave.
Sunnyvale, CA 94085
Tel : [phone]
Fax : [phone]
email: [e-mail]
http://www.mvista.com
European Headquarters Japan Headquarters
The Netherlands Japan
MontaVista Software BV Maarssen MontaVista Software Japan, Inc.
Tel: [phone] Tel: [phone]
email: [e-mail] email: [e-mail]
Belgium
Asia Pacific Headquarters
MontaVista Software Hove
Tel: [phone]
Hong Kong
email: [e-mail]
MontaVista Software, Inc.
Tel: [phone]
France
email: [e-mail]
MontaVista Software SAS
Tel: [phone]
Singapore
email: [e-mail]
MontaVista Software Singapore Pte. Ltd.
Tel: [phone]
Germany
email: [e-mail]
MontaVista Software GmbH
Tel: [phone]
email: [e-mail]
Sweden
MontaVista Software AB
Tel: [phone]
email: [e-mail]
UK
MontaVista Software Limited
Tel: [phone]
email: [e-mail]
Powering The Embedded Revolution
Copyright © 2001 MontaVista Software, Inc. All rights reserved. MontaVista Linux is a trademark of MontaVista Software, Inc. Linux is a registered trademark of Linus
Torvalds. All other trademarks are the property of their respective owners.