Introduction

Linus Torvalds has announced that enhancements have been made to the Linux kernel to support preemptibility. This set of changes, available as a patch to the Linux kernel, has been maintained by Robert Love, a well-known contributor to the Linux kernel. This patch was incorporated into the source code for the main Linux development kernel and will be available in all versions of the kernel later than version 2.5.4-pre6.

At TimeSys, we believe that this is an excellent step towards reducing the average latency of the Linux kernel and should provide numerous benefits for users of Linux in desktop and server distributions. However, we must note that although this patch will help reduce the average latency of the kernel, it does little to improve upon the maximum or 'worst-case' latency that is critical to developing embedded systems.

This paper explores TimeSys' perspective on the changes made to the mainline Linux development kernel to improve its preemptibility and discusses the implications of these changes for companies who are interested in using Linux for embedded and real-time development projects.

Background

One of the most basic aspects of any modern operating system is its ability to support multiple tasks, commonly referred to as processes. Operating systems accomplish this by managing the interaction between the processes running on the machine at any given time. Multiple processes coexist on a computer system by constantly switching from one to the other in order to share resources such as processing power, peripherals, and so on. For example, after performing calculations, a process may have nothing else to do until additional input is received. Until more data arrives, that process can relinquish the system's CPU, making it available to other processes that have calculations to perform.

Within the heart of the operating system itself, interrupting one process for the benefit of another is known as preemption. The amount of elapsed time between when an event that requires some action by the operating system occurs and the point at which that request is actually serviced is known as latency.

Latency has a variety of different implications depending on the purpose for which an operating system is being used. Linux was designed as a multi-user system that supports large numbers of processes executing at any given time. Unfortunately, most desktop computer users are all too familiar with the phenomenon of their desktop computer freezing for a significant amount of time while the system is busy doing “something.” This is merely annoying in a desktop setting, but this kind of unpredictable response time in an embedded environment is totally unacceptable.

When used as a desktop or server operating system, the goal of Linux is to provide the best general performance for all processes, thereby providing the best average latency for all processes. However, when used in real-time or embedded systems, Linux must have a bounded maximum latency for the processes that are critical to one or more specific embedded or real-time applications. By definition, embedded systems must maintain some interaction with the external world. For an embedded system to function satisfactorily, this interaction must be performed in a timely manner. This makes the latency of response to external events a key way of measuring the performance and acceptability of an embedded operating system.

The new Linux kernel preemption patch decreases the average latency in the Linux kernel, which is a very positive development for the overall Linux community. On the other hand, the patch does not decrease the maximum latency, and therefore does not do enough for the needs of embedded system designers. At TimeSys, we've developed more extensive enhancements to the preemptibility of the Linux kernel, as well as other fundamental improvements in Linux scheduling, which make the TimeSys Linux kernel a more powerful and predictable solution for using Linux in embedded and real-time development projects.

Comparing TimeSys and Generic Linux Kernel Preemptibility

The preemptibility enhancements provided by the recent kernel patch provide fundamental yet isolated improvements to the Linux kernel, a major step forward for Linux. The original Linux kernel is not preemptible anywhere. Both TimeSys Linux and the new Linux preemptible kernel begin by leveraging the Symmetric Multi-Processor (SMP) capabilities provided by Linux in order to enhance preemptibility, but take very different approaches under the covers.

The new Linux preemptible kernel enables preemption except when an SMP spinlock would have been invoked. Spinlocks are simple synchronization mechanisms that cause a process that wants access to a locked resource to continuously test whether the resource is available until the existing lock on that resource is released. This allows multiple processes to be simultaneously (and safely) executing in the kernel on an SMP machine — with at most one on each processor when a shared resource is in use. The new Linux preemptible kernel changes the spinlock to disable preemption because disabling preemption on a uniprocessor system is logically equivalent to the spinlock in an SMP — the process can't be interrupted until the lock is released, which is the point at which the SMP spinlock would have been released. Unfortunately, this approach disables preemption in a large part of the Linux kernel — no kernel thread or any part of the kernel itself can continue execution until preemption is re-enabled (which is done at the point at which the SMP spinlock would have been released).

The TimeSys approach is conceptually similar, but maximizes the number of kernel threads that can continue execution because the TimeSys Linux kernel replaces SMP spinlocks with kernel mutex locks instead of disabling preemption.

Kernel mutex locks behave exactly as their name suggests — they implement a mechanism for mutually exclusive access to a shared resource that does not affect other kernel threads and processes that may be executing, unless they need access to the same shared resource. In the new Linux preemptible kernel, whenever a kernel thread needs exclusive access to a resource, all other kernel threads must wait regardless of whether they need access to that resource or not, resulting in maximum latency that is as long as the duration of the longest non-preemptible interval. As an analogy, if multiple automobiles were trying to proceed through an intersection at the same time, using a spinlock or disabling preemption would freeze all traffic in a city as each automobile passed through the intersection. In contrast, using a mutex is like adding a traffic light to an intersection — it coordinates the traffic through that specific intersection without affecting traffic anywhere else.

The following table provides some empirical performance comparisons to highlight the difference between these approaches to preemptibility, showing that adding kernel preemption to Linux helps the average latency of Linux processes but does not reduce the maximum latency of any Linux process. Unfortunately, simply adding preemption doesn't help many of the situations in which the Linux kernel must wait for other operations to complete. As mentioned earlier, latency has different implications depending on the ways in which Linux is used. On desktop and server systems, decreasing average latency is exactly the right thing to do, because this benefits the overall performance of the system. However, in embedded application development, minimizing the maximum latency of specific Linux processes is much more critical. This is the aspect of Linux preemptibility on which the TimeSys Linux kernel enhancements focus.

Table: Average kernel preemption latency comparison

The table shows that the average preemption latency for the Linux kernel before the preemption patches are applied is around 10,000 microseconds. The new kernel reduces the average preemption latency to about 1,000 microseconds. This improvement will make Linux desktop and server systems noticeably more responsive, but latencies as long as 100,000 microseconds are still visible. In contrast, the longest delay observed in TimeSys Linux GPL (which includes the TimeSys kernel preemption enhancements) on similar hardware is about 1000 microseconds, equal to the “average” latency of generic Linux with the preemptible kernel. Additionally, TimeSys Linux GPL shows an average latency of less than 50 microseconds. This difference between average and maximum latencies can have an enormous effect on application performance.

Conclusion

The recent announcement of preemptibility enhancements being incorporated into the Linux kernel validates the notion that kernel preemptibility is a fundamental underpinning of any embedded operating system. As shown by the preceding table, both the Linux preemptible kernel patch and TimeSys Linux provide improvements to the preemptibility and performance of Linux systems, though there is a substantial difference in scale. Contrary to some recent industry comments, the new Linux preemptible kernel does not make Linux into a Real-Time Operating System (RTOS). Additional enhancements to the Linux Kernel need to be made to provide the bounded response and latency for application ranging from handheld systems to set-top boxes to avionics.

Dr. Doug Locke is Vice President of Technology at TimeSys Corp.

---

---

 
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.