The Real-Time Linux Kernel: A Survey on PREEMPT_RT The Real-Time Linux Kernel: A Survey on PREEMPT_RT

In real-time systems, the correct execution of a real-time program depends not only on the logical correctness of the output but also on whether such results are carried out within a given time frame or deadline (Stankovic and Ramamritham 1990). The temporal determinism of the system is therefore the primary requirement to guarantee time-predictable task execution. Rather, throughput and low latencies are desirable but secondary properties. For this reason, “real time” does not mean computing as fast as possible, but rather computing as fast as required.

From a deployment standpoint, real-time programs can in fact run bare metal, i.e., with no operating system, or atop a Real-Time Operating System (RTOS). The second option is preferable when we need to handle the concurrent execution of multiple tasks in the system. In this regard, the system memory can be managed as a single address space, shared among the tasks, or as a set of virtual address spaces, to guarantee the task isolation. In the latter case, the applications usually require services to operating systems via system calls. This triggers a switch from user space to kernel space that consists of an execution mode change that enables the software to run privileged instructions and to unrestrictedly access the whole memory space. As a consequence, time-predictable executions of real-time applications based on RTOSs need to have temporal determinism also at the kernel-space level.

Generally speaking, the goals of RTOSs and General-Purpose Operating Systems (GPOSs) are conflicting, since the former aims at upper-bounding the execution time, while the latter target maximizing the average performance (Yodaiken 1999a). The Worst-Case Execution Time (WCET) is the typical metric of a real-time task, since most of the real-time scenarios require upper-bounded response times. The operating system has a significant impact on task WCET due to scheduling decisions, interferences, and system call execution.

Real-time application requirements are usually expressed as timing constraints, often as upper-bound limits. One can identify different levels or classes of constraints(Buttazzo et al. 2005; Kopetz 2011):

• Soft real time: the application goal is to maintain a Quality of Service (QoS), e.g., a video frame rate. Missing some deadlines typically implies a degradation of the QoS without any safety-critical consequences on people or things. This, however, needs to ensure an acceptable user experience.
  
• Firm real time: similar to the previous class, but in this case a missed deadline invalidates the output. Results carried out after the deadline have no value and must be discarded.
  
• Hard real time: the strictest class, where the deadline cannot be missed for any reason, since it can lead to undesirable consequences. Guaranteeing hard real-time constraints usually requires formal proofs of the entire system and classical code analyses. This class is typical of safety-critical scenarios.
  

For example, the autopilot computer in airliners is a clear example of hard real-time class applications. If a deadline is missed, it could potentially cause loss of human lives. Multimedia applications, such as video players or audio software, are usually instances of the soft real-time class. In this case, a missed deadline may cause a quality degradation of the output, without the occurrence of any safety-critical issue. Therefore, a real-time class does not depend on system characteristics, but on the consequences of missed deadlines.

Several other classifications can be found in the literature, e.g., weakly hard real time (Bernat et al. 2001) or $(m,k)-$firm real time (Hamdaoui and Ramanathan 1995). In recent years, increased interest has been shown in the concept of probabilistic hard real time (Bernat et al. 2002); i.e., the deadline is guaranteed to be met with a certain probability. This class has the advantage of being able to describe hard-to-analyze systems with classical worst-case execution time analyses. This occurs by maintaining the hard real-time requirements with a probability of failure that should be taken into account in the overall system fault analysis. However, methods currently used to guarantee and estimate probabilistic worst-case execution time are still immature and not widely accepted (Abella et al. 2015; Gil et al. 2017).

The End of Dennard's scaling (Esmaeilzadeh et al. 2011), the increasing computational power requirements, and the outbreak of nonfunctional requirements—e.g., thermal and energy constraints—along with the need to reduce development costs and time to market led to the introduction of features traditionally related to general-purpose systems to real-time embedded systems. In recent years, the spread of Cyber-Physical Systems increased the necessity of devices featuring computational capabilities comparable to the ones provided by general-purpose systems, but with safety and reliability requirements typical of an embedded system (Lee 2008). On the contrary, nonfunctional requirements, such as battery-powered devices that have low energy consumption constraints or systems in hard environmental conditions that require strong temperature control, led to the introduction of dedicated techniques that may clash with the necessity of temporal determinism.

Introducing multicore processors in real-time systems can help address the aforementioned issues and scale the performance. The drawback is that the presence of multiple computing units introduces nontrivial challenges to RTOSs. Task scheduling on multicore processors is in fact more complex and may introduce higher latencies (Anderson et al. 2006). Moreover, the execution of multiple concurrent tasks determines resource contention (Fedorova et al. 2010), which directly affects the predictability and increases the complexity of WCET evaluation (Chattopadhyay et al. 2014).

The use of Commercial-off-the-Shelf (COTS), opposite to the development of specialized hardware, considerably reduces costs and engineering efforts, but bounding guaranteeing predictability and maintaining tight latencies become complex problems. With the introduction of multicore processors, bounding latencies is even more difficult due to temporal nondeterminism originating when multiple applications are running in different cores trying to access shared resources (Pellizzoni and Caccamo 2007; Nowotsch and Paulitsch 2012). As stated in Dasari et al. (2013), the main unpredictability issues of COTS hardware are caused by the following factors: simultaneous cache accesses from different cores, controllers of shared IO and memory buses, possible interconnection networks (e.g., Nonuniform Memory Access Architecture (NUMA) (Song et al. 2016)), memory devices and controllers, hardware power-saving strategies, System Management Mode (SMM), virtual memory management, and hardware prefetching. Such mechanisms and hardware units in COTS platforms usually contain intrinsic nondeterminism and, in general, are too complex to justify a worst-case timing analysis. In fact, COTS platforms are built for GPOSs and thus tend to improve the average performance; companies producing COTS hardware are usually not interested in investing their time to improve or simply analyze real-time metrics. In addition, SMM is a special operating mode of some architectures and it is specifically built to leave to the firmware of the motherboard some sort of authority over the system, allowing it to arbitrarily interrupt the OS and execute specific low-level code. These interrupts are called System Management Interrupts (SMIs) and they typically involve low-level management of hardware devices, e.g., the control of fan speed. Even if some of these tasks are also performed by the operating system, the firmware must guarantee that a bug in the OS could not damage the hardware. SMIs are generally not predictable and may considerably increase system latencies. In 2000, these interrupt latencies were in the order of milliseconds (Kau et al. 2000) but have decreased to microseconds in recent architectures. However, these metrics have been rising again lately due to security, virtualization, and many-core features of modern processors (Macarenco et al. 2016), and in case of memory failures, SMIs may take hundreds of milliseconds to run the failure recovery routines (Gottscho et al. 2017).

For these reasons, COTS platforms contain not only hardly analyzable cross-core interferences but also nontemporal deterministic hardware mechanisms. The specification data (e.g., maximum memory accessing latency) are not always provided by the manufacturer, making the upper-bounding of the WCET impossible. Furthermore, even if we assume a full-deterministic hardware, calculating the WCET may be too pessimistic; i.e., the computed WCET value is not suitable for any application.

The need to reduce time to market and the increasing computational power requirements are pushing toward COTS and multicore, but this collides with the aforementioned challenges. The high degree of safety required by regulations in certain applications, e.g., avionics, limits the possibility to exploit the COTS and multicore advantages due to hard real-time constraints and challenging environmental conditions. Nevertheless, companies like Boeing and Airbus are currently evaluating the possibility of using COTS components in their aerospace products (Hunter and Basciano 2015; Agrawal et al. 2017). Also, specific technical committees—e.g., IEC Technical Committee 107 for avionics—are developing standards to ensure the product quality and to allow their certification.

In this scenario, moving toward COTS multicore platforms makes the porting of non-time-predictable GPOSs to real-time environments an interesting alternative. The benefits are more evident in Linux OSs, where tons of scientific and industrial research solutions are available for a wide number of problems, from hardware to software aspects. Thanks to the high number of available libraries, often open source, the adoption of Linux as the operating system can considerably reduce costs and development effort (Raghavan et al. 2005). Complex applications, like, for instance, Graphical User Interfaces or image analysis algorithms, require immense work to be reimplemented for RTOSs, due to the common absence of state-of-the-art libraries.

In 2007, the Linux Foundation¹ was established from the merging of different Linux development associations. It is currently supported by the majority of the main stakeholders in Information Technology, including historical competitors like Microsoft Corporation. Moreover, the member list² includes stakeholders of hardware manufacturers but also from automotive, telecommunication, aerospace, and financial sectors.

The advantages and limitations of using Linux for nondesktop markets are presented in this article, specifically focusing on real-time applications. The source code accessibility and portability, the years of industrial and scientific research, and the amount of implemented algorithms and libraries have made Linux a strong alternative to commercial and specialized approaches, also in embedded environments (Henkel 2006).

Furthermore, real-time Linux has been considered by both the European Space Agency (ESA) and National Aeronautics and Space Administration (NASA) for space and ground applications, including mission-critical software (Stakem 2001; Braga et al. 2008; Leppinen 2017).

The interest in using real-time Linux is not confined to classical real-time scenarios, e.g., automotive and aerospace. On the contrary, it is employed in several other fields such as robotics and networking, but also nonembedded fields like simulation frameworks, multimedia applications, and High-Performance Computing (HPC). Section 5 presents an overview of use cases for real-time Linux. Almost all HPC infrastructures are today based on the Linux operating system. Recently, the time sensitiveness of some HPC applications emerged, increasing the interest for real-time guarantees on Linux (Flich et al. 2017; Fornaciari et al. 2018).

In 2016, the Linux Foundation started the Real-Time Linux collaborative project. ³ This project aimed at coordinating the development of kernels for the real-time environment and, in particular, the development of the PREEMPT_RT patch, which started in 2005 with the goal to increase the determinism and to reduce latencies of the Linux kernel. The project aimed also at creating a common knowledge base, starting from the already existent rt-wiki. ⁴ Another stakeholder of real-time Linux is the Open-Source Automation Development Lab (OSADL), ⁵ an organization intended to promote and support the use of open-source software in embedded environments.

The purpose of this article is to survey and review the existent literature about introducing real-time capabilities in the Linux kernel. Section 2 presents the state-of-the-art approaches focusing on alternatives to PREEMPT_RT. In Section 3, the PREEMPT_RT patch is carefully described with reference to several works in the literature. Then, Section 4 presents the experimental evaluations on the real-time performance of the patch and Section 5 the scientific and industrial use cases and derivative works of PREEMPT_RT. Previous surveys are presented in Section 6, while future works and conclusions are discussed in Section 7.

The literature on Linux real time is composed of articles from several heterogeneous sources, including a significant number of white papers and industrial technical reports. Some papers available in the literature were published in conferences without a well-defined peer-review method or as online unpublished resources. However, several of these articles—especially those written by kernel developers—have been cited in more important scientific works. Except for papers published in well-known academic proceedings, the scientific validity and the experimental conditions have to be properly evaluated before drawing any conclusion. In this survey, we adopted the following policy: articles from sources with a well-established peer review process are included; articles from untrustworthy sources are excluded, if they provide incoherent and unrealistic results or perform experiments with insufficient details in the adopted methodology and experimental setup; articles describing internals of the kernel or use cases are instead included, regardless of the publishing status, to allow the reader to explore technical insights in case of interest.

Given the previous policy, we cited, for example, articles from lwn.net—the most known website focusing on Linux internals—only if they describe a functionality of the Linux kernel and exclude any claim in terms of performance results, since no form of peer review is adopted.

Where not otherwise specified, we assume the current latest version of the Linux kernel: 4.14 (November 2017).

The most common alternative approaches to the PREEMPT_RT patch are usually based on the presence of an additional OS “pico-kernel,” in charge of managing the real-time threads. They are equivalently called cokernel, pico-kernel, nano-kernel, or dual kernel (dk) based approaches. The baseline idea here is to have the pico-kernel working as a layer between the hardware and the general-purpose Linux kernel. All the various implementations are similar in nature, mainly acting as an interrupt dispatcher and scheduler. This layer catches interrupts coming from the hardware and forwards it to real-time tasks or to Linux tasks. The scheduler is then responsible for guaranteeing that real-time tasks meet the deadline, by properly assigning the CPU. Residual CPU time is eventually allocated to general-purpose Linux.

The most common open-source cokernel approaches are RTLinux, Xenomai, and RTAI. The last two are based on the Adaptive Domain Environment for Operating System (ADEOS) layer (Yaghmour 2001) that basically acts as a broker of hardware interrupts propagating them to Xenomai or RTAI. ADEOS in fact creates separated OS domains, each one having a private address space and resources. Resource sharing (e.g., devices) among domains is possible only via ADEOS. Interrupts are managed by propagating them via a prioritized pipeline of domains, allowing the real-time kernel—and consequently, the real-time tasks—to immediately receive the interrupts. In this way, the micro-kernel (Liedtke 1995) ensures the execution of real-time tasks independently of the status and the decisions taken by the Linux kernel. In the subsequent paragraphs, the most widespread cokernel approaches are briefly described, with their framework structure depicted in Figure 1.

Fig. 1. The three different implementations of the cokernel approach: (a) RTAI, (b) Xenomai, and (c) RTLinux.

The first traces of a real-time Linux kernel can be found in the literature in the late 1990s. From the very beginning, the hardest problem to solve consisted of the impossibility of preempting the Linux kernel (Barabanov 1997). In fact, some kernel routines were characterized by long execution times, with a dramatic impact in terms of latency. In 2001, a paper from Finney (2001) proposed to use a vanilla Linux kernel for real-time tasks in a single-core system if the deadlines remain in the order of milliseconds. However, the advent of multicore and the explosion of interactive desktop applications—not necessarily real-time ones—pushed the developers to improve the system latencies to make the kernel itself preemptible since version 2.6.0 (December 2003). This version requires additional protections of critical sections also in single-processor machines, since the kernel threads themselves can be preempted.

Without any preemption at the kernel level, it is indeed impossible to consider real-time Linux at any level. This is mainly dictated by the unpredictability of the kernel execution time that is reflected to tasks, as previously explained.

Therefore, the changes introduced in the kernel enable the selection between several degrees of preemptibility, in order to satisfy the requirements of different scenarios. Currently, the vanilla kernel Linux 4.14 (November 2017) contains three levels of preemption selectable at compile time:

• PREEMPT_NONE: no forced preemption. The kernel is allowed to run without user-space preemption and the system is able to deliver the maximum throughput.
  
• PREEMPT_VOLUNTARY: the kernel provides explicit preemption points in strategic locations to reduce the latency. Part of the throughput is lost because of the tradeoff with the goal of decreasing latency.
  
• PREEMPT (formerly PREEMPT_DESKTOP): the preemption is allowed in any part of the kernel, with the exception of spinlocks and other critical regions.
  

The PREEMPT_RT patch of the Linux kernel is actually a set of patches developed by a group of kernel developers. The project was started by Ingo Molnár and the first release was based on kernel version 2.6.11 (March 2005). The goal of this project is to trade the throughput of the system with low latencies and predictability, while maintaining the single-kernel approach, to allow the developers to easily write (user-space) real-time applications.

Among the changes introduced, it is worth mentioning the introduction of two additional preemption levels (a fourth and fifth one): Preemptible Kernel or Basic RT (PREEMPT_RTB) and Fully Preemptible Kernel (PREEMPT_RT_FULL). In more detail, the latter allows the real-time tasks to preempt the kernel everywhere, even in critical sections. However, some regions can still be made nonpreemptible, like the top half of interrupt handlers and the regions protected by raw spinlocks.

During the development of the PREEMPT_RT patch, besides the new features introduced, several positive side effects have been observed. Systems where this patch is applied are more sensitive to bugs due to latency constraints (Gonçalves and de Melo 2008), allowing the kernel developers to discover more easily the bottlenecks of the kernel itself. Moreover, the patch introduced several scheduler improvements and analysis tools in the kernel mainline.

The most evident difference between the state-of-the-art approaches to real time in Linux and the PREEMPT_RT patch is the absence of a second kernel dedicated to the management of the real-time applications. This makes the implementation of real-time processes in user space similar to non-real-time ones, apart from having a special scheduling class and priority, as subsequently described in Section 3.1.6. In practice, a few further aspects must be actually considered in the development of real-time Linux applications. Simultaneously running tasks may in fact interfere from a timing perspective (Reghenzani et al. 2017). Even worse, memory swapping may lead to page faults, heavily impacting latency and predictability. This issue can be prevented by exploiting the classical protection mechanism consisting of locking the memory pages allocated to a real-time process via the mlockall system call.

Generally speaking, the PREEMPT_RT software development is completely different with respect to cokernels: an application can be executed in real-time mode without being rewritten. The programming model of cokernel approaches uses specialized system calls. For example, the API of Xenomai is divided into modules such as rt_task_*(...) for task management, rt_shm_*(...) for IPC, rt_time_*(...) for timer usage, and so forth. The API of cokernel approaches usually provides functions to deal with cyclic period tasks, typical of real-time applications. In Xenomai, it is possible to set the period of a task via the rt_task_set_periodic call, and then the task can easily wait for the next period via the rt_task_wait_period(...). This approach is easier for the developer compared to the clock_nanosleep(...) POSIX call, because the latter requires an implementation in the application of the logic to compute the amount of sleep time needed to match the period. Moreover, the clock_nanosleep(...) is a guarantee of minimum sleep time; in fact, the kernel can, theoretically, delay the execution at infinite time. Even considering the advantages of specialized programming models, they remove one of the most important advantages of using Linux in real-time environments: exploiting the already available huge set of drivers and libraries to speed up the application development process. It is worth mentioning that even if these drivers and libraries are available in Linux, additional effort may be required to make them real-time compliant. In cokernel approaches, the real-time tasks can still access Linux features using dedicated IPC calls to Linux soft real-time tasks. This part of the execution must not be time critical; otherwise, unbounded latencies may occur due to the presence of a nonhard real-time task running on top of the Linux kernel.

All cokernel approaches require by nature invasive modifications of the kernel code, and their interactions are not trivial to be analyzed from both a functional and timing perspective. This requirement also introduces a strict dependency with respect to the kernel version, which may represent a limitation in terms of maintainability and portability. This issue does not affect PREEMPT_RT, which has the advantage of being developed directly by the Linux community. On the contrary, cokernel approaches are typically based on old Linux kernel versions. In addition, cokernel approaches are generally less stable and safe due to the complex interaction between the two kernels, which requires extra effort for real-time developers (Brown and Martin 2010).

Overall, the PREEMPT_RT patch allows the developers to operate in a real Linux environment in which they can easily reuse most of the existent libraries and tools, including all the sets of functions specified by the POSIX standard. However, as discussed later in the article, PREEMPT_RT provides less tight real-time guarantees.

Over the years, other Linux extensions or patches have been developed to address problems related to real-time scenarios. We consider $\text{LITMUS}^{\rm RT}$ (Calandrino et al. 2006) as the most relevant one. This is a kernel patch whose main goal is to provide a test bench for real-time scheduling algorithms in Linux in order to obtain their proof of concept. In order to accomplish its goal, $\text{LITMUS}^{\rm RT}$ provides a user-space interface and a suite of tracing tools. Because of its research nature, it is not suitable for real applications and production environments, especially due to the lack of quality assurance procedures and rigorous testing. In fact, merging to the Linux mainline is not a goal of this project, which remains a research and experimental prototype. Part of the effort of the $\text{LITMUS}^{\rm RT}$ community is to create an environment with realistic overheads, i.e., reducing as much as possible the Linux kernel's and other tasks’ inteference, to guarantee accurate measurements of performance metrics.

For this reason, the project is also used in comparison with the PREEMPT_RT patch, as we will show in Section 4.

Some commercial extensions were also built for real-time Linux, e.g., MontaVista Linux, Wind River Linux, and TimeSys Linux. However, the IP rights covering this software together with the nearly absent literature on them reduce our possibility to analyze and compare their approaches with PREEMPT_RT and the previous described alternatives.

In order to achieve real-time behavior of the system, several preliminary features have been added in the PREEMPT_RT patch. This subsection briefly describes the kernel features no longer part of the PREEMPT_RT patch at the time of writing. A detailed description of the improvements and further insights of the early RT patches can be found in the Rostedt and Hart (2007) article.

3.1.3 Priority Inheritance. Priority Inversion is a classical synchronization problem affecting real-time systems (Lampson and Redell 1980), in which a lower-priority task may preempt a higher-priority one. In order to clarify this concept⁶, let us assume to have three tasks $L,\ M,\ H,$ respectively, with low, medium, and high priority, as shown in Figure 3. The task $L$ is the first to arrive and to acquire a resource $R$, and then the task $M$ arrives and preempts $ L$. Subsequently, the task $H$ becomes ready, preempts $M,$ and tries to acquire $R$. However, since $R$ is locked by $L$, the task $H$ cannot run and it is therefore put to sleep. Consequently, the task $ M$ is awakened and put in execution again. In this example, the medium-priority task $M$ is indirectly preempting the high-priority $H$, since it does not allow $L$ to run and thus to release the resource $R$. Several solutions have been proposed for this. A well-known one is called priority inheritance or priority boosting (Sha et al. 1990). The basic idea is to boost the priority of the low-level tasks ($ L$) that are locking resources required by higher-priority tasks (in our case by $H$). The priority is boosted up to the level of the highest-priority task that is trying to acquire the resource. In our example, $L$ would temporarily obtain the priority of $H$.

Fig. 3. Priority inversion example (all scheduling latencies are assumed null).

In Linux, priority inheritance was implemented in the early PREEMPT_RT patch (Corbet 2006), since priority inversion is able to cause unbounded and unpredictable latencies in the system (Kang et al. 2007; Rostedt and Hart 2007). More recently, alternative solutions include the priority ceiling protocol (Carminati 2012), migratory priority inheritance (Brandenburg and Bastoni 2012), and the Probabilistic-Write/Copy-Select mechanism (Zhu et al. 2016).

The kernel preemption is one of the most important features necessary to improve the Linux real-time capabilities (Scordino and Lipari 2006). It is hard, or even impossible, to predict the kernel execution time, due to its complexity and intrinsic nondeterminism. This, in conjunction with the need to have short response times for interactive applications, leads the kernel developers to implement the preemption capability of the Linux kernel-space code to avoid unbounded latencies in application operations. In the vanilla kernel, the preemptibility can be enabled via the CONFIG_PREEMPT since version 2.6. However, the kernel cannot be preempted in interrupt-disabled sections, like during spinlocks. Spinlocks represent a locking mechanism where the lock acquisition is iteratively attempted until it is successfully performed. This behavior occurs also if the lock is already held by another thread, causing the current thread to continue “spinning,” wasting CPU time and inhibiting the possibility of being preempted. Although this mechanism may not sound very efficient, the overall performance, especially the response times, can benefit if the waiting time is small.

Besides the features described in previous sections, the most important added feature of the PREEMPT_RT patch is the removal of most of the nonpreemptible spinlocks. All the real-time features can be enabled via the CONFIG_PREEMPT_RT_FULL configuration flag. With the real-time patch applied and enabled, the spinlock_t and rwlock_t types become preemptible, while the raw_spinlock_t acts like a normal spinlock. The differentiation between spinlock_t and raw_spinlock_t was introduced with spinlock annotations in the mainline in version 2.6.33 (February 2010).

All the sleeping mutexes have been replaced with rt_mutex type that implements priority inheritance, as well as semaphores. The patch significantly increases the preemptibility of the kernel, leaving the top-half part of interrupt handlers and the raw_spinlock_t protected critical regions the only sections still non-preemptible. This increases the response time of the system, reducing latency and improving predictability. However, it increases the number of context switches and resource contention, consequently reducing the throughput, as described in the next section. Also, as a negative effect, it increases the chances of priority inversion scenarios. The priority inheritance and ceiling protocol are also available for user-space-level mutexes, configurable via the PTHREAD_PRIO_INHERIT and PTHREAD_PRIO_PROTECT POSIX options.

As we have seen, the improvements in terms of kernel preemptibility led to a higher rate of context switches. The consequence is that PREEMPT_RT degrades the system performance in terms of throughput. Generally, most of the previously described features improve the real-time capabilities of the system, at the price of negatively impacting on the system throughput. The available literature characterizing this performance degradation will be discussed in Section 4.4.

It is also worth saying that reducing latencies does not necessarily increase the system's ability to meet deadlines, i.e., the real-time performance. In a not fully deterministic system like Linux and COTS platforms, the response time of a task job can be expressed by a random variable $X$ that follows an unknown distribution $X \sim \mathcal {A}$. Given a deadline $D$, the task is considered hard real time if

(2)

(3)

This is because $\sigma$ represents the average variation value and not the jitter ⁷ that instead represents the maximum variation. A confidence interval cannot be used to infer the presence and the magnitude of outliers (De Haan and Ferreira 2007) needed to evaluate the WCET and consequently the real-time performance. This was the starting point for the still-immature probabilistic hard real-time theory (Bernat et al. 2002), which represents an open research topic.

The difficulty in obtaining the results of Equation (1), the weakness given by Equations (2) and (3), and the immaturity of probabilistic real-time theory are the main causes of missing formal demonstrations of the real-time quality of the Linux kernel. A significant part of available works in the literature are focused on reducing the latency without formal demonstrations of a corresponding increase in predictability. This usually leads the researchers to draw conclusions from the maximum observed execution time, that is, instead, only a lower-bound of WCET. Accurate timing analyses are possible anyway when considering small sections of kernel code or isolated subsystems. Several works presented in this survey follow this approach, increasing the determinism on a particular kernel feature, even if providing an upper-bound to WCET at the application level still requires an unrealistic effort.

Since the most remarkable quality of real-time systems is the ability to meet deadlines in the tasks’ execution, the system performances are usually evaluated in terms of latency and the response-time jitter. The throughput, intended as the number of jobs periodically processed, is not a primary concern, unlike the GPOSs, where the throughput is the main performance metric. Since minimizing latencies generally entails a throughput degradation, as already discussed, some works analyzed real-time Linux by observing both metrics, as subsequently presented in Section 4.4. This makes sense because Linux has been proposed also in mixed time-criticality systems, i.e., a system characterized by a workload including tasks with different criticality levels, that run—possibly interacting among them—on the same computational platform. In two common practical approaches, a Linux OS is typically deployed as a

1. noncritical guest operating system of real-time hypervisor that separates Linux from the hard-real time OS (Burns and Davis 2013) or
   
2. full mixed-criticality multicore system, only when the timing requirements are not strictly hard (Sigrist et al. 2015).
   

Table 1 shows the performance metrics considered in the analyses cited in this survey. As expected, the most recurrent metrics are about scheduling and interrupt latencies, since they are the common overhead affecting all the real-time scenarios. I/O metrics (including GPIO and Networking) may or may not be significant, depending on the specific application. Other secondary metrics include synchronization primitive latencies, IPC communication, user-space from/to kernel-space switch time, and the impact on the overall system throughput.

Table 1. Different Metrics Used in Cited Articles Sorted by PublicationDate

Metric
Deadlock break time								X
GPIO8 latency	X	X	X				X									X
GPIO8 jitter	X	X	X				X
Interrupt latency		X		X	X	X		X	X	X	X	X	X	X		X
IPC performance	X											X			X
Network latency		X		X											X
Scheduling latency				X	X			X	X	X	X	X	X
Semaphore A/R time											X
System throughput			X			X			X		X
Timer latency9						X
User/kernel latency10		X
User space	X	X	X	X	X	X	X	?	X	X	X	X	X	X	X	X
Kernel space							X	X							X
Multicore					X			?	X	X		X	X		X
The use of user and/or kernel-space benchmarks and a SMP system are shown in last three rows. The symbol ? indicates unknown values.

A first important classification of performance analyses is the distinction between kernel-space and user-space evaluations. The possibility of running real-time processes in user space has important benefits not only from the application development perspective but also in terms of stability, safety, and security (Mehnert et al. 2002). These advantages of Linux led researchers to analyze mostly user-space scenarios. However, it is fundamental to remark that even if a real-time task runs in user space, the kernel-space execution of the system calls may have a nonnegligible impact on the task execution (Reghenzani et al. 2017).

In most of the current approaches, the estimation of the worst-case latencies is obtained through the generation of workload, by using suitable stresser programs. These, usually executed with best-effort priority level, increase the overall system load in order to test the real-time “prioritization” and isolation capabilities of the operating system. In this regard, stress (Waterland 2013) and its derivative work stress-ng (King 2013) are frequently used also in papers whose target is not represented by real-time use cases. This tool allows us to select which portion of the system and of the kernel to stress—i.e., which system call—enabling the possibility of performing fine-grained analyses. Papers that did not use stress(-ng) usually implemented custom scripts and applications in order to generate synthetic workloads. Other alternatives for workload generators are represented by dohell (typically used in Xenomai-based systems) (Community 2011) and cpuburn (Nielsen 2012).

Regarding the benchmark suites, the literature provides us several proposals targeting the worst-case scenario (e.g., Mälardalen WCET Benchmarks (Gustafsson et al. 2010), PapaBench (Nemer et al. 2006)) and the average-case scenario (e.g., MiBench (Guthaus et al. 2001), Parsec (Bienia et al. 2008)). Tests on worst-case response latency instead rely on more specific tools like cyclictest (Gleixner 2010). Since it is extensively used in Linux PREEMPT_RT analyses, we dedicated a specific subsection to describe it more in detail. Cyclictest is part of a suite developed by Linux kernel maintainers, called rt-tests. ¹¹ It includes both benchmarks and stressers developed specifically to test PREEMPT_RT. Regarding third-party tools, it is necessary to mention the open-source Linux Test Project ¹² developed by several IT companies: it provides mainly functional tests, but also a condition variable latency measurement and a priority inversion stresser.

Listing 1. The simplified algorithm of cyclictest benchmark tool.

The problem of providing a general and quantitative answer to what are the actual real-time capabilities of Linux with the PREEMPT_RT patch is not clearly addressable. The complexity of a GPOS like Linux entails the practical impossibility to execute the static analyses typically performed on RTOS (Arthur et al. 2007). This is caused by the unrealistic effort required to compute the WCET for all the control paths and considering all the possible sources of interference. This, together with the nonpredictability of COTS hardware, makes it impossible to characterize upper bounds for latencies and WCET.

The common trend is not to consider Linux PREEMPT_RT as a hard real-time compliant solution. The work of Brown and Martin (2010) and the technical report of Chalas (2015) led to the conclusion that real-time Linux systems can be considered 95% hard real time. These studies compared the latencies resulting from the execution of specific applications under certain system configurations. The general idea of a 95% hard real-time system is that deadline misses are tolerated if they occur with a probability lower than $5\%$. However, the timespan to be considered is not specified, making this classification not really convincing. A similar classification, but with 99% constraint, was proposed for the Ach IPC RT Library (Dantam et al. 2015). These classes recall somehow the concept of a probabilistic hard real-time system (Bernat et al. 2002), in which the WCET of a task can be provided in a probabilistic sense. However, the fact that the constraints get satisfied seems to suffer the same nondeterministic issues of the hard real-time class: how can one formally demonstrate that the probability of missing the deadline is not underestimated? Probabilistic real time is based on statistical theories; however, the theoretical results are still preliminary and controversial.

Aware of the conceptual limitations of the hard real timeness of the PREEMPT_RT patch, we now present the experimental evaluations. As previously stated, the following data are extremely dependent on the hardware platform, the benchmarks, and the system configuration. Accordingly, the reader should carefully take into account these factors before making any further conclusions.

A direct comparison between Linux PREEMPT_RT and other real-time operating systems is usually performed considering metrics like system or interrupt latencies. Xenomai, RTAI, and RTLinux are generally considered systems able to meet hard real-time constraints (Barbalace et al. 2008; Buttazzo 2011) and thus frequently used as references. Some works also took into account $\text{LITMUS}^{\rm RT}$.

An extensive comparison between PREEMPT_RT and Xenomai was proposed in 2010 by Brown and Martin (2010). In this work, several experimental evaluations were performed, mainly on GPIO and response time latencies/jitters. This paper classified Linux as a 95% hard real-time system, since it showed the ability to maintain a GPIO switch frequency equivalent to Xenomai with a probability of 95% on the long run. The paper also suggested a decision flow chart to select the best approach to use for real-time in Linux.

In 2013, a recent version of PREEMPT_RT was compared with $\text{LITMUS}^{\rm RT}$ (Cerqueira and Brandenburg 2013). Both provided similar scheduling latencies in an idle system (max $10-15\mu s$); PREEMPT_RT obtained a similar latency for CPU-bound workload (max $\sim 17\mu s$); instead, $\text{LITMUS}^{\rm RT}$ considerably degrades (max $\sim 47 \mu s$). As discussed in Section 2.5, $\text{LITMUS}^{\rm RT}$ essentially introduced changes on the Linux scheduling part. In fact, the authors proposed the integration of the $\text{LITMUS}^{\rm RT}$ scheduling algorithm with the PREEMPT_RT patch as a future work. Linux was also compared to Windows CE and QNX Neutrino RTOS (Fayyad-Kazan et al. 2013a), generally showing lower real-time performance with respect to these commercial solutions. However, Linux outperformed Windows CE in average performance metric values and in synchronization primitive latencies.

In 2014, Garre et al. (2014a; Garre et al. 2014b) showed that RTAI and Xenomai can reach task switch times on average less than $1\mu s$, while PREEMPT_RT cannot break the microsecond barrier. The evaluation was performed running two threads with a busy loop containing a scheduler yield syscall. For the worst-case scenario, PREEMPT_RT reached similar results compared to RTAI ($\sim 20\mu s$), even if it still cannot compare to Xenomai ($\sim 2\mu s$). Similar results were obtained by the developers of the Ach IPC library (Dantam et al. 2015) when they compared Xenomai and PREEMPT_RT in 2015.

It is possible to conclude that, generally, RTOS and cokernel approaches still outperform Linux PREEMPT_RT in terms of real-time performance, while Linux is better on average performance, as expected by its GPOS nature. The next section presents the impact of PREEMPT_RT on system throughput.

As already discussed in Section 1, unlike GPOSs, the performance goal of an RTOS is not to maximize the system throughput. An RTOS must be characterized by predictability, responsiveness, and low latency. In fact, system throughput and latency are two metrics usually in tradeoff. In this section, we aim at summarizing the works that evaluated the negative impact of PREEMPT_RT on system throughput.

When using PREEMPT_RT, we saw that the improved kernel predictability implies a higher number of context switches compared to the vanilla kernel. This is the main cause of throughput degradation. Furthermore, mechanisms like Priority Inheritance (see Paragraph 3.1.3) introduce additional complexity in kernel space and a consequent increase of overhead.

Since throughput is not the primary concern of real-time developers and researchers, only a few articles are available in the literature analyzing its degradation when the PREEMPT_RT patch is applied. The Arthur et al. (2007) paper is probably the first work focusing on this aspect. The authors used LMBench (McVoy et al. 1996), a suite of benchmarks, to compare various UNIX system metrics, e.g., memory, IPC latencies, network bandwidth, and system call overheads. They concluded that the PREEMPT_RT patch does not significantly influence the system performance. However, the metrics selected in this paper are not representative of the throughput degradation, since most of the metrics are related to system latencies. Already in the first years of the PREEMPT_RT patch, Jeong et al. (2007) noticed that the actual throughput may be reduced by a factor of 5, but bounding the frequency of context switches may help to maintain an acceptable performance level. Later, the same authors analyzed the throughput degradation in Seo et al. (2009) experiencing a worst-case degradation of 10 times. However, we must consider that these works refer to two very different kernel versions. From 2007 to 2009, Linux and the PREEMPT_RT patch have deeply evolved with the introduction of further mechanisms.

The most valuable analysis of throughput degradation is probably the paper of Litayem and Saoud (2011). The authors tested both latencies and system throughput, using, respectively, cyclictest and unixbench (Smith et al. 2011). They compared the results for Xenomai, PREEMPT_RT, and the vanilla Linux kernel.¹³ Unexpectedly, Xenomai outperformed PREEMPT_RT in terms of throughput. In particular, PREEMPT_RT performed very badly in multicore scenarios, showing a 49% degradation compared to the vanilla Linux kernel. However, we have to consider that, since the kernel version used was older than 2.6.39 (the exact used version is missing in the paper), the Big Kernel Lock (BKL) might have had a big impact in multicore performance degradation due to the higher resource contention. In fact, later in 2014, Fayyad-Kazan et al. (2014) showed that there were clear improvements (up to 35%) compared to kernel version 2.6.33, due to the BKL removal.

In this section, we present a list of of both industrial and scientific use cases available in the literature, relying on the exploitation of the PREEMPT_RT patch. The discussion follows the chronological order of publication.

The first use case was carried out in 2007 by IBM Research: a work on a real-time Java virtual machine (RTJVM) (Auerbach et al. 2007). In this scenario, PREEMPT_RT has bound latencies for the Java garbage collector, allowing the execution of a classical soft real-time application: a music synthesizer. The following year, another real-time Java application (Plšek et al. 2008) aimed at exploiting PREEMPT_RT for the kernel preemptibility and the high-resolution timers.

In 2009, Kume et al. (2009) showed how the PREEMPT_RT patch can be effective also for real-time control of a robotic arm, performing inverse kinematic calculations. The maximum response-time jitter experienced was in fact on the order of $ 100\mu s$. They also tested the real-time capability by producing a periodic square wave, obtaining a response-time jitter of just $ 17 ns$. In the same year, two other classes of use cases were proposed: avionic (Schoofs et al. 2009) and networking (Goldoni et al. 2009). In the former, Linux was used as a simulator of the final hardware to allow rapid development of the avionics software. With the use of PREEMPT_RT, they were able to simulate the embedded systems with comparable latencies, and even if the system could not guarantee hard real-time constraints, it correctly ran the simulations. In the latter case, the authors proposed a tool to estimate the available bandwidth of a network path. They used an active probing strategy, i.e., injecting traffic packet to estimate the bandwidth. In order to reduce the noise in the observations and consequently increase the estimation quality, they applied PREEMPT_RT to obtain accurate timing measurements.

In 2010, a couple of industrial network use cases were introduced: the work of Baumgartner and Schoenegger (2010) and the patent of Khawer and So (2010). The first one implemented the hard real-time POWERLINK protocol in a Linux machine and analyzed the maximum achievable transmission rate according to the real-time constraints and variable system load. The patent instead presented a middleware layer for the implementation of device drivers able to meet real-time requirements in Real Link Control (RLC) networks. In the same year, Schoepfer et al. (2010) presented a complex robotic arm application, where Linux played the role of the outmost level of control.

In 2011, another real-time Ethernet protocol, EtherCAT, was used in conjunction with PREEMPT_RT in the work of Mercado et al. (2011). Kacmarik et al. (2011) wrote a Linux device driver communicating with an FPGA PCIe card in order to implement a GNSS (Global Navigation Satellite System) receiver. The hardware of the system was voluntarily kept simple, leaving to the device driver the management of interrupts and of the GNSS protocol. This implied the necessity of meeting timing deadlines, successfully accomplished by the PREEMPT_RT patch. Weisbach et al. (2011) investigated the effects of device drivers on a PREEMPT_RT system, showing that using a user-space driver did not compromise the real-time capabilities. In the same year, we had a couple of other robotic use cases, exploiting the cokernel approach. The first one was by Medina et al. (2011), in which an RTAI system performed the computation for the control part and a PREEMPT_RT system provided real-time speech synthesis and recognition. The second one was by Kaneko et al. (2011), where the PREEMPT_RT system was actually used as the hard real-time system.

In 2012, Bonestroo (2012) published a master's thesis on a tripod robot using a control algorithm implemented on a PREEMPT_RT system. He remarked on the necessity of a ready-to-use system, because RTAI or Xenomai would be too expensive in terms of required setup time. Sakamoto and Kondo (2012) presented a passive robotic medical application in which the Linux system was in charge of reading measurements and carrying out the force-feedback data to motors. A six-legged robot, controlled by several hardware PI¹⁴ controllers that receive the set point from a gait algorithm run on a PREEMPT_RT system with a loop frequency of 100Hz, was presented by Bombled and Verlinden (2012).

In 2013, Yun et al. (2013) evaluated the real-time performance of the PREEMPT_RT patch for a big physics experiment HPC application. Conversely from the previous cases, here the authors experienced no advantages or even worse results compared to the standard Linux. However, as also stated by the authors, the system was not carefully configured and tuned. This may have generated the conditions for unexpected latencies. A very well-received medical surgery framework was presented by Hannaford et al. (2013). This used the PREEMPT_RT patch to ensure real-time capabilities. Since no tight guarantees could be provided, the safety standards limited the use of this framework in research. Still, in 2013, Nguyen et al. (2013) implemented a broadcast/multicast communication system based again on a cokernel system, including RTAI and PREEMPT_RT Linux. Unfortunately, the authors did not provide further details on the configuration and integration of this mixed system.

Moving to 2014, we found four works worth mentioning: (1) Gabrielli et al. (2014) presented an over-LAN transmission system for audio applications using a COTS platform equipped with Linux Debian patched with PREEMPT_RT in order to reduce the cost of introducing specialized hardware; (2) a patent by Khawer and Easwaran (2014) scaled the previous patent to bigger multicell telecommunication networks; (3) a humanoid robotic application by Smith et al. (2014) was programmed in a mixed C++ and Java environment and based on a Linux PREEMPT_RT system in order to guarantee acceptable levels of latency for motor control; and (4) Verschueren et al. (2014) implemented a car-driving visual algorithm, in which the Linux system gets the car position and orientation from a camera (at $100 Hz$) and issues control inputs for the car.

In 2015, the PREEMPT_RT patch was again used for a network application by Mao et al. (2015). The work implemented a Radio Access Network over a container cloud system with the usual goal of minimizing the latencies.

In 2016, Zappulla et al. (2016) presented a spacecraft simulator based on the RT patch, providing also an analysis of the operating system latencies, bounded by $100 \mu s$. In the same year, Dalbert (2016) presented a master's thesis on the implementation of a real-time field bus system with Linux PREEMPT_RT. One of the most recent works is the application of the patch to the Robot Operating System (ROS) described in the tutorial of Lages (2016).

In 2017, Cheng et al. (2017) tried to port a 3D printer system to PREEMPT_RT Linux, but unfortunately the required $1 \mu s$ resolution by stepper motors cannot be achieved. Even if a $ 1 \mu s$ resolution is hard to achieve by PREEMPT_RT or other Linux variants, again the article did not provide any information on how the kernel was configured, preventing further discussions on this. In the same year, Tan et al. (2017) presented a case study where the Linux PREEMPT_RT was used for the control of a synchrotron operating at a $5kHz$ cycle rate. As with other use cases, the selection of PREEMPT_RT was dictated by the need to reduce the development effort.

Finally, in 2018, it has been used to reduce the kernel latencies that can hinder the PCIe interconnection performance of a distributed real-time heterogeneous system (Erickson et al. 2018).

Linux PREEMPT_RT has also found space in virtualization-based systems. Some works used it as a test bench to compare the real-time capabilities of the hypervisor (Fayyad-Kazan et al. 2013b; Aichouch et al. 2013a; Sheridan-Barbian 2015). In 2010, Yu et al. (2010) proposed a scheduler for the Xen hypervisor able to correctly manage real-time guests. This filled the lack shown by the standard Xen scheduler in meeting real-time requirements, even for maximum priority guests.

In other scenarios, Linux PREEMPT_RT has also been deployed as host operating system in conjunction with the Kernel-based Virtual Machine (KVM). KVM substantially consists of a kernel module that allows the user to run a guest operating system. In this regard, the first work available is Schild et al. (2009), who evaluated the overhead in terms of latencies introduced by KVM over a Linux PREEMPT_RT system. They found that the impact of KVM on interrupt latencies is lower than $ \le 3 \mu s$. The same year, Kiszka (2009) presented a detailed analysis of the real-time capabilities of Linux PREEMPT_RT when used as both the host and guest OS, in conjunction with the KVM hypervisor. They quantified the overall system overhead in the range from $15\%$ to $25\%$ including scheduling latency obtained in the guest operating system under $ \lt 1ms$. Later approaches for industrial control systems include the work by Ghosh and Sampath (2011) and by Sampath and Rao (2011), the last focused on QEMU.

Aichouch et al. (2013b) instead presented a preliminary evaluation of $\text{LITMUS}^{\rm RT}$ in terms of scheduling and interrupt latencies in two scenarios: (1) installed as main RTOS and (2) virtualized on top of a Linux PREEMPT_RT with QEMU/KVM virtualization system. An automotive scenario was presented by Hamayun et al. (2014), where several possible solutions were evaluated, including cokernel approaches. However, at the end they suggested a custom RTOS that, besides the high development cost, allows the system to meet the hard real-time constraints required by automotive environment.

A mixed work was proposed by Zuo et al. (2010), who used a vanilla Linux kernel with KVM as host and Linux PREEMPT_RT as guest. They identified an acceptable average latency ($\lt 26 \mu s$) but a nonacceptable worst-case latency ($ \gt 1 ms$). They observed how most of the latency spikes were caused by SMI enabled in the host machine.

The PREEMPT_RT patch showed good results in latency optimization in cloud computing. In 2015, Mao et al. (2015) used Docker (a container-based virtualization system) over a PREEMPT_RT Linux system, noticing an improvement in terms of latency reduction on both the host and containers.

In this section, we briefly mention a couple of derivative works/uses of the PREEMPT_RT patch.

The ChronOS Linux (Dellinger et al. 2011) is a Linux kernel variant that includes the PREEMPT_RT patch. It is focused on the implementation of different schedulers for multiprocessor systems aimed at improving the scheduling of both real-time and best-effort applications. In fact, it has been used in different scientific works, in particular for the development of scheduling algorithms.

Finally, a specialized derivative work was presented by Wings et al. (2015) as a variant of LinuxCNC (i.e., a Linux distribution for CNC machines). The idea was to implement a real-time Ethernet interface in LinuxCNC using PREEMPT_RT to increase the real-time capabilities at the kernel level, thus removing the legacy RTAI interface, which cannot support the required user-space driver.