Anatomy of real-time Linux architectures

From soft to hard real-time

Summary:  It's not that Linux® isn't fast or efficient, but in somecases fast just isn't good enough. What's needed instead is the ability todeterministically meet scheduling deadlines with specific tolerances. Discover thevarious real-time Linux alternatives and how they achieve real time—from theearly architectures that mimic virtualization solutions to the options availabletoday in the standard 2.6 kernel.

Tag this!Update My dW interests (Log in | What's this?) Skip to help for Update My dW interests

Date:  15 Apr 2008
Level:  Intermediate
PDF:  A4 and Letter (86KB | 11 pages)Get Adobe® Reader®
Activity:  13964 views
Comments:   0 (Add comments)

This article explores some of the Linux architectures that support real-timecharacteristics and discusses what it really means to be a real-timearchitecture. Several solutions endow Linux with real-time capabilities, andin this article I examine the thin-kernel (or micro-kernel) approach, thenano-kernel approach, and the resource-kernel approach. Finally, I describe thereal-time capabilities in the standard 2.6 kernel and show you how to enable anduse them.

Defining real time and its requirements

The following definition of real time sets the stage for discussingreal-time Linux architectures. This definition comes from Donald Gillies in theRealtime Computing FAQ (see Resources for a link):

A real-time system is one in which the correctness of the computationsnot only depends upon the logical correctness of the computation but also upon thetime at which the result is produced. If the timing constraints of the system arenot met, system failure is said to have occurred.

More in Tim's Anatomy of...series on developerWorks

• Anatomy of the Linux SCSI subsystem
• Anatomy of the Linux file system
• Anatomy of the Linux networking stack
• Anatomy of the Linux kernel
• Anatomy of the Linux slab allocator
• Anatomy of Linux synchronization methods
  
  
• All of Tim's Anatomy of... articles
• All of Tim's articles on developerWorks

In other words, the system must be deterministic to guarantee timing behavior inthe face of varying loads (from minimal to worst case). Note that the above definitionsays nothing about performance, because real time isn't about speed: It's aboutpredictability. For example, using a fast modern processor, Linux can provide atypical interrupt response of 20μs, but occasionally the response can be muchlonger. This is the fundamental problem: It's not that Linux isn't fast orefficient, it's just that it isn't deterministic.

Some examples will demonstrate what all this means. Figure 1 shows the measure ofinterrupt latency. When an interrupt arrives (the event), the CPU isinterrupted and enters interrupt processing. Some amount of work is done todetermine what event occurred and, after a small amount of work, the required taskis dispatched to deal with the event (a context switch). The time betweenthe arrival of the interrupt and dispatching of the required task (assuming it'sthe highest-priority task to dispatch) is called the response time. Forreal time, the response time should be deterministic and operate within a knownworst-case time.

Context switching

One useful example of this process is the standard airbag in vehicles today. Whenthe sensor that reports a vehicle collision interrupts the CPU, the operatingsystem should quickly dispatch the task that deploys the airbag rather than allowother, non-real-time processing to interfere. An airbag that deploys a secondlater than it should is worse than no airbag at all.

In addition to bringing determinism to interrupt processing, task scheduling thatsupports periodic intervals is also needed for real-time processing. ConsiderFigure 2. This figure demonstrates periodic task scheduling. Many control systemsrequire periodic sampling and processing. At a defined period (p), aparticular task must execute for system stability. Consider a vehicle anti-lockbraking system (ABS). This control system samples the speed of each wheel on avehicle and controls each brake's pressure (to stop it from locking up) at up to20 times per second. For the control system to work, sensor sampling and controlmust be performed at periodic intervals. This means that other processing must bepreempted to allow the ABS task to execute at the desired periods.

Hard real-time vs. soft real-time systems

An operating system that can support the desired deadlines of the real-time tasks(even under worst-case processing loads) is called a hard real-time system.But hard real-time support isn't necessary in all cases. If an operating systemcan support the deadlines on average, it's called a soft real-time system.Hard real-time systems are those in which missing a deadline can have acatastrophic result (such as deploying an airbag too late or allowing brakepressure to slip for too long). Soft real-time systems can miss deadlines withoutthe overall system failing (such as losing a frame of video).

Now that you have some insight into real-time requirements, let's look at some ofthe Linux real-time architectures to see what level of real time they support andhow.

Back to top

Thin-kernel approach

The thin-kernel (or micro-kernel) approach uses a second kernel as an abstractioninterface between the hardware and the Linux kernel (see Figure 3). Thenon-real-time Linux kernel runs in the background as a lower-priority task of thethin kernel and hosts all non-real-time tasks. Real-time tasks run directly on thethin kernel.

The primary use of the thin kernel (other than hosting the real-time tasks) isinterrupt management. The thin kernel intercepts interrupts to ensure that thenon-real-time kernel cannot preempt the operation of the thin kernel. This allowsthe thin kernel to provide hard real-time support.

Although the thin kernel approach has its advantages (hard real-time supportcoexisting with a standard Linux kernel), the approach does have drawbacks. Thereal-time and non-real-time tasks are independent, which can make debugging moredifficult. Also, non-real-time tasks do not have full Linux platform support (thethin kernel execution is called thin for a reason).

Examples of this approach include RTLinux (now proprietary and owned by WindRiver Systems), Real-Time Application Interface (RTAI), and Xenomai.

Back to top

Nano-kernel approach

Where the thin kernel approach relies on a minimized kernel that includes taskmanagement, the nano-kernel approach goes a step further by minimizing the kerneleven more. In this way, it's less a kernel and more a hardware abstraction layer(HAL). The nano-kernel provides for hardware resource sharing for multipleoperating systems operating at a higher layer (see Figure 4). Because thenano-kernel abstracts the hardware, it can provide prioritization for higher-layeroperating systems and, therefore, support hard real time.

Note the similarities between this approach and the virtualization approach forrunning multiple operating systems. In this case, the nano-kernel abstracts thehardware from the real-time and non-real-time kernels. This is similar to the waythat hypervisors abstract the bare hardware from the guest operating systems. SeeResources for more information.

An example of the nano-kernel approach is the Adaptive Domain Environment forOperating Systems (ADEOS). ADEOS supports multiple concurrent operating systemsrunning simultaneously. When hardware events occur, ADEOS queries each operatingsystem in a chain to see which will handle the event.

Back to top

Resource-kernel approach

Another architecture for real time is the resource-kernel approach. This approachadds a module to a kernel to provide reservations for various types of resources.The reservations guarantee access to time-multiplexed system resources (CPU,network, or disk bandwidth). These resources have several reserve parameters, suchas the period of recurrence, the required processing time (that is, the amount oftime needed for processing), and the deadline.

The resource kernel provides a set of application program interfaces (APIs) toallow tasks to request these reservations (see Figure 5). The resource kernel canthen merge the requests to define a schedule to provide guaranteed access usingthe task-defined constraints (or return an error if they cannot be guaranteed).Using a scheduling algorithm such as Earliest-Deadline-First (EDF), the kernel canthen be used to handle the dynamic scheduling workload.

One example of a resource kernel implementation is CMU's Linux/RK, whichintegrates a portable resource kernel into Linux as a loadable module. Thisimplementation evolved into the commercial TimeSys Linux/RT offering.

Back to top

Real time in the standard 2.6 kernel

While all the approaches discussed so far are architecturally interesting, theyall operate around the periphery of the kernel. Instead, what if the standardLinux kernel incorporated the necessary changes to support real time?

Today, in the 2.6 kernel, you can get soft real-time performance through a simplekernel configuration to make the kernel fully preemptable (see Figure 6). In thestandard 2.6 Linux kernel, when a user space process makes a call into the kernel(through a system call), it cannot be preempted. This means that if a low-priorityprocess makes a system call, a high-priority process must wait until that call iscomplete before it can gain access to the CPU. The new configuration optionCONFIG_PREEMPT changes this behavior of the kernel byallowing processes to be preempted if high-priority work is available to do (evenif the process is in the middle of a system call).

But this configuration option has a trade-off. Although the option enables softreal-time performance and even under load makes the operating system execute moresmoothly, it does so at a cost. That cost is slightly lower throughput and a smallreduction in kernel performance because of the added overhead of theCONFIG_PREEMPT option. This option is useful fordesktop and embedded systems, but it may not be right in all scenarios (forexample, servers).

The new O(1) scheduler

Another useful configuration option in the 2.6 kernel is for high-resolutiontimers. This new option allows timers to operate down to 1μs resolution (ifsupported by the underlying hardware) and also implements timer management with ared-black tree for efficiency. Using the red-black tree, large numbers of timerscan be active without affecting the performance of the timer subsystem (O(logn)).

With a little extra work, you can get hard real-time support with the PREEMPT_RTpatch. The PREEMPT_RT patch provides several modifications to yield hard real-timesupport. Some of the changes include reimplementing some of the kernel lockingprimitives to be fully preemptable, implementing priority inheritance forin-kernel mutexes, and converting interrupt handlers into kernel threads so thatthey are fully preemptable.

Back to top

Summary

Linux is not only a perfect platform for experimentation and characterization ofreal-time algorithms, you can also find real time in Linux today in the standardoff-the-shelf 2.6 kernel. You can get soft real-time performance from the standardkernel or, with a little more work (kernel patch), you can build hard real-timeapplications.

This article gave a brief overview of some of the techniques used to bringreal-time computing to the Linux kernel. Numerous early attempts used athin-kernel approach to segregate the real-time tasks from the standard kernel.Later, nano-kernel approaches came on the scene that appear very much like thehypervisors used in virtualization solutions today. Finally, the Linux kernelprovides its own means for real time, both soft and hard.

Although this article has skimmed the top of the real-time methods for Linux, theResources section provides more information on where toget additional information and other useful real-time techniques.

Resources

Learn

• In Tim's article "Virtual Linux" (developerWorks, December 2006), learn how the thin-kernel and nano-kernel approaches to real time borrow from the virtualization architectures so popular and useful today.
  
  
• In Tim's article "Inside the Linux scheduler" (developerWorks, June 2006), read more about the O(1) scheduler in the 2.6 kernel.
  
  
• Read all of Tim's Anatomy of... articles on developerWorks.
  
  
• Read all of Tim's Linux articles on developerWorks.
  
  
• The Realtime Computing FAQ is a great place to start learning about real-time computing. It covers the basics of Portable Operating System Interface (POSIX), real-time operating systems, and pointers for real-time analysis.
  
  
• "Real-time Control Systems" (PDF) is an interesting tutorial by A. Gambier that introduces the design of real-time control systems and discusses various scheduling algorithms.
  
  
• The proceedings of the 6th Real-time Linux Workshop (held November 2007) include papers and resources to help you explore the cutting edge of real-time Linux.
  
  
• The early RTLinux, the RTAI, and Xenomai have all applied the thin-kernel approach. Though the application was slightly different for each, the overall approach has proven valuable.
  
  
• ADEOS is a hardware abstraction layer (HAL), or nano-kernel, that provides real-time capabilities in the Linux kernel. It has also been used for symmetric multiprocessor (SMP) clustering and kernel debugging.
  
  
• "Portable RK: A Portable Resource Kernel for Guaranteed and Enforced Timing Behavior" describes a component that provides guaranteed access to time-multiplexed resources (such as the CPU, network, or disk) through a reservation API.
  
  
• Red-black tree is a self-balancing binary search tree. Although the algorithm itself is complex, it is extremely efficient in practice and operates in O(log n) time.
  
  
• The PREEMPT_RT patch provides hard real-time capabilities in a standard 2.6 Linux kernel. These pages provide details on installing and using the RT_PREEMPT configuration as well as a useful FAQ.
  
  
• In this priority inversion scenario, a lower-priority task holds a resource that a higher-priority task requires. (This problem occurred on Mars in the Pathfinder probe using Wind River's VxWorks.) The solution to this problem is priority inheritance, which increases the priority of a lower-priority task to allow it to run and release the resource.
  
  
• Novell recently announced their SUSE Linux Enterprise Real-Time (SLERT) version 1.0. This distribution contains kernel updates and POSIX real-time support for real-time applications. Two advancements include CPU shielding and on-the-fly priority assignment .
  
  
• Xenomai/SOLO announced migration away from the co-kernel approach to a tighter integration with the Linux kernel layer. This approach supports traditional POSIX (user-space) programming.
  
  
• In the developerWorks Linux zone, find more resources for Linux developers, and scan our most popular articles and tutorials.
  
  
• See all Linux tips and Linux tutorials on developerWorks.
  
  
• Stay current with developerWorks technical events and Webcasts.
  
  

Get products and technologies

• Order the SEK for Linux, a two-DVD set containing the latest IBM trial software for Linux from DB2®, Lotus®, Rational®, Tivoli®, and WebSphere®.
  
  
• With IBM trial software, available for download directly from developerWorks, build your next development project on Linux.
  
  

Discuss

• Get involved in the developerWorks community through blogs, forums, podcasts, and community topics in our new developerWorks spaces.
  
  

About the author

His engineering background ranges from the development of kernels forgeosynchronous spacecraft to embedded systems architecture andnetworking protocols development. Tim is a Consultant Engineer forEmulex Corp. in Longmont, Colorado.

Comments

0 comments | Sign inAdd commentReport inappropriate content

Add a comment

The field indicated with an asterisk (*) is required to complete this transaction.

Be the first to add a comment