| A TimeSys perspective on the Linux preemptible kernel |
by Dr. Doug Locke (May 28, 2002)
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.
Talk back! Do you have comments or questions on this story? talkback here
Related stories:
(Click here for further information)
|
|
|
FUEL Database on MontaVista Linux
Whether building a mobile handset, a car navigation system, a package tracking device, or a home entertainment console, developers need capable software systems, including an operating system, development tools, and supporting libraries, to gain maximum benefit from their hardware platform and to meet aggressive time-to-market goals.
Breaking New Ground: The Evolution of Linux Clustering
With a platform comprising a complete Linux distribution, enhanced for clustering, and tailored for HPC, Penguin Computing¿s Scyld Software provides the building blocks for organizations from enterprises to workgroups to deploy, manage, and maintain Linux clusters, regardless of their size.
Data Monitoring with NightStar LX
Unlike ordinary debuggers, NightStar LX doesn¿t leave you stranded in the dark. It¿s more than just a debugger, it¿s a whole suite of integrated diagnostic tools designed for time-critical Linux applications to reduce test time, increase productivity and lower costs. You can debug, monitor, analyze and tune with minimal intrusion, so you see real execution behavior. And that¿s positively illuminating.
Virtualizing Service Provider Networks with Vyatta
This paper highlights Vyatta's unique ability to virtualize networking functions using Vyatta's secure routing software in service provider environments.
High Availability Messaging Solution Using AXIGEN, Heartbeat and DRBD
This white paper discusses a high-availability messaging solution relying on the AXIGEN Mail Server, Heartbeat and DRBD. Solution architecture and implementation, as well as benefits of using AXIGEN for this setup are all presented in detail.
Understanding the Financial Benefits of Open Source
Will open source pay off? Open source is becoming standard within enterprises, often because of cost savings. Find out how much of a financial impact it can have on your organization. Get this methodology and calculator now, compliments of JBoss.
Embedded Hardware and OS Technology Empower PC-Based Platforms
The modern embedded computer is the jack of all trades appearing in many forms.
Data Management for Real-Time Distributed Systems
This paper provides an overview of the network-centric computing model, data distribution services, and distributed data management. It then describes how the SkyBoard integration and synchronization service, coupled with an implementation of the OMG¿s Data Distribution Service (DDS) standard, can be used to create an efficient data distribution, storage, and retrieval system.
7 Advantages of D2D Backup
For decades, tape has been the backup medium of choice. But, now, disk-to-disk (D2D) backup is gaining in favor. Learn why you should make the move in this whitepaper.
|
|
|
|
|
news feed