Improve Real-Time Linux Behavior on Embedded Multicore Devices



Linux has become the prevalent operating system choice for new real-time platforms; however, standard Linux is designed for overall throughput rather than for real time, and consequently needs to be modified or extended to meet high demands on both latency and determinism.

The semiconductor industry is trending towards multicore devices, and as such, the workload on many multicore processors will likely become even more multi-programmed to support a mixture of best-effort, high-throughput control applications together with low-level protocol or data-processing applications with potentially high real-time requirements. The simultaneous demand for high throughput and low latency is difficult to achieve since those characteristics are usually contradictive. So how can Linux adapt?

Real Time in Operating Systems
A real-time OS must provide a deterministic runtime environment for the entire application execution flow so that it can respond within the specified operational deadline on a system level. This implies that the task scheduler and the resource-handling API in the OS must behave in a deterministic way. When designing a system for high-throughput performance, the goal is to keep down the average latency. But when designing a real-time system, the aim is to keep the worst-case latency under a specified limit. Consequently the design of a both high-performance and real-time-capable system must take both average and maximum latency into account. Historically, “latency” has most often referred to interrupt latency without scheduling (see sidebar). But this interpretation is becoming obsolete. Drivers are today usually implemented as POSIX applications running in user-space threads as they are easier to debug, maintain and isolate from licensing issues compared to code in kernel space. The most important measure is thus the task-response latency, which includes the scheduling latency.

It is well-known that the standard Linux kernel does not provide very deterministic interrupt/scheduling latency behavior, and that under load, there is much jitter. This is the reason for the development of Linux “real-time” extensions. These extensions, often referenced as the Linux kernel preemption patch set, are but one of the approaches analyzed in this article.

Three Approaches to Enable Linux for Real-Time
Figure 1 depicts three basic design approaches for improving standard Linux real-time behavior.

  • Kernel-preemption patch approach: Standard Linux can be modified with the PREEMPT_RT kernel patch. This can be considered as a “horizontal layering” design approach since it implements a kind of para-virtualization of the interrupt management and the kernel locking mechanisms.
  • Thin-kernel/virtualization approach (minimize-avoid): Use a thin RTOS kernel layer between the hardware and Linux kernel in order to create a truly isolated virtual machine for Linux. Compared to PREEMPT_RT, this approach is an even more obvious “horizontal layering” design approach since it provides virtualization on hardware level using hypervisor technology.

Vertical-partitioning approach (avoid): A Linux SMP kernel running on a multicore processor can be configured and modified to provide resource isolation between two sets of cores; one dedicated for real-time applications and the other one for non-real-time applications. Per-core scheduling becomes less important while inter-core communication needs to be more efficient and deterministic.

121203_eis_1
Figure 1: Three approaches to enable real time in Linux systems

A: The Kernel-Preemption Patch Approach – PREEMPT_RT
The PREEMPT_RT patch provides several modifications for real-time support in the Linux kernel by mitigating the effects of resource conflicts. This is the well-known approach for adding real-time capabilities to the Linux kernel. The PREEMPT_RT patch was originally developed by Ingo Molnar and his team, and is maintained today by Thomas Gleixner among others. Most of the patches in this set have been contributed to the main line, but the kernel must be explicitly built for PREEMPT_RT.

The changes in this patch set include re-implementing some kernel locking mechanisms to enable full preemption where otherwise the Linux design states a non-preemptible region. For example, regular spinlocks are replaced with mutexes with priority inheritance, thus many interrupt handlers need to be migrated into kernel threads to become fully preemptible. In a way, PREEMPT_RT could also be seen as a kind of horizontal partitioning, since it is a patch that “para-virtualizes” and redefines the kernel locking design of the standard Linux kernel.

The patches add overhead to the locking kernel mechanisms and will decrease the throughput performance to some degree, depending on the applications. The PREEMPT_RT patch also requires adoptions in driver code and other kernel code which is not originating from kernel.org.

B: The Thin-Kernel Approach – A Hard Real-Time RTOS Kernel Layer
This design alternative, depicted in Figure 2, offers truly hard real time and the lowest figures for latency.

121203_eis_2
Figure 2: Architecture of a thin-kernel approach

The primary use of the thin kernel is to provide a hardware virtualization layer for the Linux kernel. If the actual CPU architecture offers true hardware virtualization support, the overhead introduced by the thin kernel can be kept down to as low as 2-3%.

In a thin-kernel solution, a Linux kernel image includes the thin-kernel startup in the initial phase, hiding the fact that the RTOS kernel initially boots right before the Linux kernel. From a user’s perspective, it looks like a regular Linux kernel image is booted, but in addition to the Linux user space there are also RTOS real-time partition(s) – with hard real-time capabilities – created. From Linux user space, one can load and manage the applications in the real-time partition and communicate with them using an inter-process communication (IPC) message mechanism.

The advantages of the thin-kernel approach are hard real-time support coexisting with a standard Linux kernel. The drawbacks are that the real-time and non-real-time tasks are independent, making debugging more difficult since it adds another proprietary debug and execution environment. Also, the real-time tasks do not have full Linux platform support but they may provide a limited POSIX API that, for example, provides access to the Linux file system.

Examples of a thin-kernel approach are Xenomai and the Real-Time Application Interface (RTAI).

C: The Vertical-Partitioning Approach – CPU Resource Shielding
The strategy with the vertical-partitioning approach is to create kernel resource isolation “barriers” between sets of cores – “core clusters” – so that different applications can run on the same processor simultaneously without affecting the characteristics of each other. This is often called “CPU resource shielding.” The goal is to isolate a shielded set of cores into a real-time domain such that its local per-CPU schedulers are not in any way affected by the potential massive load that the applications outside this real-time domain generate in terms of kernel-resource locking scenarios or thread preemptions.

121203_eis_3
Figure 3: Vertical partitioning with CPU resource shielding

Figure 3 exemplifies a Linux SMP kernel, vertically divided into two types of execution partitions or domains, where non-critical applications for throughput are located to the non-shielded cores in the non-real-time partition, and applications that require real-time task response latency and a deterministic behavior are located to the shielded cores in one or more real-time partitions. This requires some changes in the behavior of the applications in the real-time partition:

  • Disable the regular load balancing in the Linux kernel for shielded cores
  • Explicitly bind IRQs that belong to the real-time application to a shielded core.
  • Move the IRQs and kernel threads not belonging to real-time applications to the non-shielded cores.
  • Disable the local timer interrupts (but this removes the ability for the local scheduler to enforce time sharing and to do some book-keeping of resources).

While the full POSIX API is present, extensive use of the POSIX API will affect both soft and firm real-time characteristics, i.e., the ability to meet deadlines in time and with minimal jitter. So on the set of shielded cores in the real-time partition, the design must explicitly avoid an extensive use of the normal POSIX API that would potentially suffer from resource conflicts in the kernel call implementations. Omitting the API is not an option as existing solutions would lack any kind of OS API for services such as task management, timeout management and communication. Such a poor environment is undesirable, so a user-space real-time (RT) runtime environment that offers those services in a deterministic, low-intrusive and multicore scalable way needs to be defined.

Vertical Partitioning with RT environment inside

121203_eis_4
Figure 4: Vertical partitioning inside, with RT runtime environment in user space and RT module in kernel

Figure 4 depicts the RT Run Time execution environment in the real-time partition. It provides a low-overhead, deterministic and OS-agnostic API to services like inter-process communication (IPC), timeout management, memory/buffer management and thread management in user space. The RT runtime environment provides necessary support to implement different kinds of scheduling environments. A light-weight task scheduler may be implemented using a restricted set of native pthreads in Linux, or as a user-space light-weight thread package.

The RT runtime environment should implement such a high-speed IPC "backplane" between the real-time partition and the “outside” by using lock-less techniques and user-space queues. This "backplane" does not only provide a channel to or from the real-time domain, it also provides a high-speed IPC network between applications spread over the cores of the entire SMP Linux processor. It is a challenge to design such an IPC backplane for high speed as well as scalability, yet not affecting the real-time characteristics in the real-time domain.

Summary and Conclusions
Two horizontal partitioning approaches have been outlined: the commonly accepted kernel-preemption patch PREEMPT_RT that improves the real-time responsiveness to POSIX applications, and the hard real-time thin RTOS kernel which acts as a hardware abstraction layer for Linux and provides an OS API for real-time applications outside Linux.

One vertical partitioning approach was treated, namely CPU resource shielding with IPC and RT runtime environment in user space based on standard SMP Linux and equipped with a high-performance and scalable IPC mechanism. This alternative strives to improve the overall design in order to avoid the kernel resource conflicts instead of making workarounds to minimize the effects from them.

In systems with SMP Linux on multiple cores, the vertical partitioning method will most likely provide the ability to give both high general-purpose throughput capabilities and good real-time capabilities. The fact that the standard Linux kernel design continuously improves with regard to the kernel-resource separation on core basis, i.e., the “space-partitioning capabilities,” is a promising foundation for the vertical-partitioning approach as being a good solution for next-generation, Linux-based embedded multicore platforms.

 


christoffersson_michael

Michael Christofferson has over 30 years experience in software development for deeply embedded systems and telecom networking systems. He spent the first 8 years of his career with Raytheon in defense communications, specifically with remote-controlled signal and communications intelligence systems (SIGINT/COMINT). That was followed by 8 years in the telecom/datacom market working for such companies as GTE Telecom, Sprint, Data General Telecommunications and Pulse Communications. For the past 14 years, Mr. Christofferson has moved into sales, marketing and business development for leading industry RTOS, embedded development tools and middleware providers. These have been Ready Systems, then Microtec, then Mentor Graphics and now finally Enea for whom he has served since 1998. He is currently director of product management at Enea. Mr. Christofferson received a B.S. in physics from Bradley University in 1972, and an M.S. in physics from the University of Michigan in 1974. For more information please visit enea.com or contact us at info@enea.com.

Share and Enjoy:
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google
  • TwitThis