Introduction

Tolstoy opens Anna Karenina with a famous quote: “Happy families are all alike; every unhappy family is unhappy in its own way.” Similarly: reliable real-time systems are all alike; every unreliable real-time system is unreliable in its own way. In a real-time system, if you miss as much as one deadline, you've under performed. There are a multitude of ways to go wrong, and only one way to do things right.

Lately, the question of whether (and how) Linux can be made to serve the needs of real-time applications has been the subject of much debate, in a discussion made complicated by a multitude of definitions for real-time. We see the terms “hard”, “firm”, and “soft” real-time being used. These, along with “guarantee”, “deterministic”, “preemptible”, “fully preemptible”, and “latency”, often pepper the discussions.

In this article, we review the methods available to serve the needs of applications that involve performance deadlines. We shall see that although precise requirements vary from application to application, there are a number of fundamental issues that are almost always of concern. Since multiple vendors provide differing approaches, it is natural that no one solution will serve all applications best. Through this article, we hope to assist developers in evaluating the value of various alternatives relative to their specific applications.

Our objective is to provide insight into the various choices vendors have made in creating their unique approaches. What good is a preemptible kernel? What advantage is there in having my application running in kernel-space? What disadvantage?

Note that this article does not cover some important issues that may be as important to you in your choice of either a vendor or an approach as is real-time performance or architecture. For example, we will not cover adherence to standards, the breadth and quality of development tools, or pricing and licensing approaches.

Overview of Some Alternatives

Real-time versions of Linux differ greatly in both how and how much they help with the real-time problem. The solutions differ both in the length of the guaranteed response time, and in the circumstances in which they guarantee performance. We will discuss the alternatives with respect to a task that must not be unduly delayed. We call such a task a real-time task.

Many developers prefer to have their application run in user-space, instead of kernel-space. Some of the approaches to real-time require your code to run in kernel-space. Code running in kernel-space, as compared to user-space, is often more difficult to debug, is more likely to crash or hang the system, and is less convenient to communicate with for user-space tasks. The choice of kernel-space is generally made out of a desire to avoid delays that the Linux kernel may impose on user-space programs. We'll examine this issue in several places.

The second kernel approach

Two approaches to kernel-space real-time are RTLinux and RTAI. Both RTLinux and RTAI allow you to run any number of Linux processes, each performing any desired activity. This freedom in Linux processes occurs because RTLinux/RTAI prevents Linux processes from maintaining control of the system whenever RTLinux/RTAI tasks (or interrupts), need to execute.

When you use either RTLinux or RTAI, you are actually running another operating system in addition to Linux. This other operating system is limited in its capabilities. These limitations are what allow for deterministic response time — on the order of 15 microseconds.

Alternatively, you can think of the RTLinux/RTAI tasks as operating within Linux kernel-space. With RTLinux/RTAI, Linux only gets to run when the real-time operating system isn't running. In this approach, the real-time tasks are written to the API of RTLinux or RTAI, not to the Linux API. In practice, applications generally also have user-space tasks that communicate with the RTLinux/RTAI tasks. As a result, these user-space tasks are subject to the delays of Linux that we shall discuss.

In reality, RTLinux or RTAI do nothing to help Linux itself be real-time. But, you can also use an enhanced Linux in conjunction with RTLinux or RTAI. Thus, even if the underlying real-time operating system (RTLinux/RTAI) isn't doing anything, you can achieve more reliable performance for processes that are running within Linux itself. But remember, you are limited in what can be reliably accomplished within Linux processes.

One should also be aware that there is nothing magical about the RTLinux/RTAI approach. It is still possible to end up with unreliable performance in their tasks. It just requires more irresponsible behavior. Within Linux user-space tasks, by contrast, without some fixes and more careful design you'll be much less likely to achieve reliable performance.

RTAI offers an alternative to kernel-space operation, in the form of LXRT. LXRT supports the same API as RTAI, but via tasks that run in user-space. LXRT tasks can provide hard real-time response as long as the LXRT task is not in a Linux system call. This is better than ordinary Linux tasks. LXRT tasks will benefit from an improved Linux kernel, if they make system calls. This is because LXRT tasks will suffer from kernel preemption problems when making Linux system calls, just as ordinary Linux tasks do.

The recent announcement of RTLinux V3.0 pre-7 also introduces user-space real-time in RTLinux. In this model, a function in user address space may be activated by an interrupt or timer. This function is much like a signal handler. It cannot make system calls, however. The function is activated from RTLinux, and thus is not delayed by Linux.

RTAI with LXRT is commercially available from and supported by Lineo. RTLinux is commercially available from and supported by its creator, FSMLabs. Both are also available as open source software, for free public download.

Basic performance issues

There are two issues with respect to other Linux processes delaying the execution of the required real-time task.

• Another process may be executing instead of your real-time process.

• Another process may have caused Linux to do something that keeps your process from getting to run.

Prioritization:

To ensure that your real-time process runs ahead of some other less important process, your real-time process must be assigned a higher priority than the lesser task. It also requires that Linux somehow honor that priority. However, Linux was not designed to merely honor priorities; instead, it takes additional factors into account in an effort to maximize overall system throughput.

Standard Linux implements what is called a “fair” scheduling model. That is, your process can be expected to run within a bounded amount of time. However, the upper bound of that time may not be acceptable. In order to improve the real-time responsiveness of Linux, a number of vendors have added fixed priority scheduling enhancements. With a fixed priority system, your real-time process gets to execute more quickly when it becomes ready. Fixed priority enhancements have been added by TimeSys to its Linux/RT OS, and are also available from MontaVista in its real-time Linux scheduler. REDSonic's RED-Ice Linux also provides sophisticated scheduling alternatives.

Interrupts:

There are two aspects to the ability of other user processes to postpone your real-time task:

• Another process, through its making of a system call, might have caused the kernel to disable interrupts, to enter a non-preemptible section, or to enter a locked critical section.

• Another process might indefinitely delay the execution of your real-time process because of priority inversion.

Clearly, if interrupts are disabled, your real-time process can't be awakened by the arrival of the interrupt from your real-time device. Or, even if it is awakened, it may not get a chance to run because Linux wants to finish the system call of the first process before it does a context switch. Or, your process can't make progress in the kernel because you need to acquire a lock held by another process.

Priority inversion occurs when a lower priority process holds a resource, for example a semaphore, that your real-time process needs. Your real-time process will not get the semaphore until the lower priority process gives it up. Now, suppose a third process, one with intermediate priority, is CPU bound. In that case, it is possible that the low priority process never gets access to the CPU, and so never completes the critical section of code required to release the semaphore. As a result, your real-time process is indefinitely postponed!

There are several different approaches to avoiding the interrupt-disabling problem.

Tricking Linux, with respect to interrupt disabling

The first solution, the one adopted by RTLinux and RTAI, is to have the real-time processes run under a separate (small) operating system and not have interrupts disabled for anything but extremely short time periods.

With RTLinux/RTAI, Linux is never actually allowed to disable interrupts. Instead, they handle all interrupts within their own dedicated operating system. When Linux makes a request to disable interrupts, RTLinux/RTAI notes the request. RTLinux/RTAI then ensures that Linux behaves, with respect to critical sections, as though it had indeed disabled interrupts. This is accomplished by RTLinux/RTAI emulating interrupt enable/disable functions and “gating” interrupt requests to Linux in an appropriate manner. Victor Yodaiken, the creator of RTLinux, holds a patent on this technique.

Improving the Linux scheduler

Another approach to circumventing the delayed response problem involves improving the Linux kernel's preemption algorithm. What is desired, is for a real-time process to immediately preempt a lower priority (“non-real-time”) process that happens to be running.

Given a fixed-priority scheduler, if the non-real-time process was executing user space code, it will immediately be preempted by the newly ready real-time task. If the process is in the midst of a system call, standard Linux will usually allow the task to complete the system call before context switching to the newly ready real-time task.

If the process may be preempted while performing the system call then we say that the kernel is preemptible.

The Linux kernel can do a little work, check to see if the current user task should be preempted, do a little more work, check again, . . . , and so on. It's the time between these checks that causes the delay in preemption. This is the approach taken by the low latency patch developed by Ingo Molnar.

An alternative approach is to allow the kernel to be preempted any time it is not in a “critical” section of code. This approach is used in the kernel enhancement recently announced by MontaVista.

There are, however, three major downsides to increasing the responsiveness of Linux by adding additional preemption points to reduce latency:

1. It makes the kernel code harder to follow, and thus harder to maintain. Anyone who has looked at the kernel code much will probably appreciate this concern.

2. Additional preemption points may actually reduce, rather than increase, overall throughput. This might be caused by the extra code and context switches, but also because extra code may cause additional register spills and cache misses. On the other hand, as Kevin Morgan of MontaVista points out, the sooner you get an I/O process started, the sooner it gets its device doing work.

3. Another issue is that preemption points may cause severe problems such as locking up the system, as has been reported by Mark Christiansen.

A solution for priority inversion, is to have a low priority process temporarily “inherit” the priority of the high priority real-time process. Consequently it wakes up, finishes its critical section, and gives up the semaphore. One source of this solution for priority inversion in Linux is available from TimeSys.

Hedging your bets

The Linux kernel enhancements may sometimes be used together; but sometimes, they are mutually exclusive. For example, the Resource Kernel from TimeSys provides an alternative to the scheduling for Linux. However, if you have user processes making system calls, then you can have delays caused by the kernel that cause your application to miss a deadline. Thus, it may also be desirable to add improvements to the preemptibility of the Linux kernel in order to improve the application's overall reliability.

Summary of real-time Linux alternatives

In this table, we provide a feature matrix that gives a coarse overview of alternative real-time system features, and where they may be obtained. The matrix makes it clear that for some features, there are competing approaches. For example, MontaVista, RED-Linux, and TimeSys all have replacement schedulers for user-space tasks in Linux. Here are some notes regarding the entries in the table:

• Separate real-time kernel — means that a different operating system handles interrupts and devices, and this operating system runs Linux as a separate task.
  
• User space programming — means that an application can have real-time tasks executing in user space.
  
• Improved Linux kernel preemption — means that they have modified the Linux kernel to shorten the periods for which the kernel may not be preempted.
  
• Fully preemptible Linux kernel — means that they have modified the Linux kernel so that it may be preempted unless the kernel specifically forbids it as opposed to the normal kernel which may be preempted only when the kernel specifically allows it.
  
• Precise scheduling within Linux — means that higher priority processes immediately preempt lower priority processes. Note that with standard Linux other factors are taken into account besides priority.
  
• Solution for priority inversion within Linux — means that they have provided a means to avoid a high priority task from waiting on a blocked, lower priority task. Note that FSMLabs considers priority inheritance a “hack” and recommends that developers avoid situations where its use would be required.
  
• Fast interrupt response, < 1 mS — means that properly written tasks for their system will be able to be reliably begun within 1 millisecond following receipt of the associated hardware interrupt. Note that for RTAI and RTLinux this time may be much faster, perhaps on the order of 15 microseconds.
  
• Moderate interrupt response, < 5 mS — means that properly written tasks for their system will be able to be reliably begun within 5 milliseconds following receipt of the associated hardware interrupt. This response time is sufficient for many applications, for example many audio applications.
  
• Improved precision for time/timers within Linux — means that there is an alternative method that is more precise than the standard resolution of 10 mS.

TimeSys Linux/RT adds real-time capabilities to Linux via a “resource kernel” (RK), which is implemented as a loadable module. This module provides an API that user-space tasks can employ to gain improved preemption, precise scheduling, priority inversion avoidance, and improved precision for timing. In the matrix, “within RK” indicates that the capability is provided via the system calls of the API within the resource kernel, since these benefit from improved preemption. The notation “with RK, without RTAI” indicates that it is a capability provided to tasks that make use of the RK API, but that you cannot use the RK (and its API) if you are using RTAI — since the two add-ons are mutually exclusive.

You can see, from the feature matrix, that no single product offers an all-inclusive set of real-time capabilities. As a result, several companies offer multiple alternative technologies (such as scheduler enhancements plus RTLinux/RTAI), in order to support a broader range of real-time requirements.

---

Author's bio: Kevin Dankwardt is founder and President of K Computing, a Silicon Valley training and consulting firm. He has spent most of the last 9 years designing, developing, and delivering technical training for such subjects as Unix system programming, Linux device drivers, real-time programming, and parallel-programming for various organizations world-wide. He received his Ph.D. in Computer Science, in 1988. He may be contacted at [email protected].

---

 
This article was originally published on LinuxDevices.com and has been donated to the open source community by QuinStreet Inc. Please visit LinuxToday.com for up-to-date news and articles about Linux and open source.