Enea^® Linux Real-Time Guide

This document is divided into the following sections:

Readers who already have a good understanding of how Linux works may want to go directly to Chapter 3, Improving the Real-Time Properties.

A task switch occurs when the currently running task is replaced by another task. In Linux, a task switch can be the result of two types of events:

In the kernel documentation the terms voluntary preemption is used instead of yield and forced preemption for what here is called preemption. The terms were chosen since, strictly speaking, preemption means "to interrupt without the interrupted threads cooperation", see http://en.wikipedia.org/wiki/Preemption_%28computing%29.

Note that the preemption model only determines when a task switch may occur. The algorithms used to determine if a switch shall be done and then which task to swap in belong to the scheduler and are not affected by the preemption model. See Section 2.2, Scheduling for more info.

Where a task can be preempted depends on if it executes in user space or in kernel space. A task executes in user space if it is a thread in a user space application, except when in a system calls. Otherwise it executes in kernel space, i.e. system calls, kernel threads, etc.

In user space, tasks can always be preempted. In kernel space, you either allow preemption at specific places, or you disallow preemption at specific places, depending on the preemption model kernel configuration.

Simplified, the choice of preemption model is a balance between responsiveness (latency) and scheduler overhead. Lower latency requires more frequent opportunities for task switches which results in higher overhead and possibly more frequent task switches.

Linux offers several different models, specified at build time:

*) These models require the PREEMPT_RT patch plus kernel configuration. See the "Target Guide" section in the Enea^® Linux User's Guide for build instructions.

The server and desktop configurations both rely entirely on yield (voluntary preemption). The difference is mainly that with the desktop option there are more system calls that may yield.

Low-latency desktop introduces kernel preemption. This means that the code is preemptible everywhere except in parts of the kernel where preemption has been explicitly disabled, as for example in spinlocks.

The preemption models RT and basic RT require the PREEMPT_RT patch, https://rt.wiki.kernel.org/index.php/Main_Page. They are not only additional preemption models as they also add a number of modifications that further improve the worst case latency. Read more about PREEMPT_RT in Section 2.4, The PREEMPT_RT Patch.

Basic RT model is mainly for debugging of RT, use RT instead. RT aims to minimize parts of the kernel where preemption is explicitly disabled.

A scheduling policy is a set of rules that determines if a tasks shall be swapped out and then which task to swap in. Linux supports a number of different scheduling policies:

The scheduling policy is a task property, i.e. different tasks can have different policies.

SCHED_FIFO and SCHED_RR are sometimes referred to as the real-time scheduling classes.

The standard way of scheduling tasks in Linux is known as fair scheduling. This means that Linux aims to give each task a fair share of the CPU time available in the system.

In a real-time system, work is deadline-constrained and the most important quality of task scheduling is to meet deadlines rather than fairness of CPU utilization. Fair scheduling may affect the time passed from when a task becomes ready for execution to when it actually starts to execute, since there may be other tasks that have not yet been allowed their share of the processor time. As an additional complication, the actual length of the delay depends on the number of tasks being active in the system and is therefore difficult to predict. In this way, the system becomes indeterministic.

There are other methods of scheduling in Linux that can be used. For instance, it is possible to use priority-based scheduling, similar in its policy to scheduling methods used in real-time operating systems. This scheduling method, referred to as SCHED_FIFO, increases the determinism when interacting tasks perform work together. It requires, however, that explicit priorities are assigned to the tasks.

As long as there are real-time tasks, i.e. tasks scheduled as SCHED_FIFO or SCHED_RR that are ready to run, they would consume all CPU power if the scheduling principles were followed. Sometimes that is the wanted behaviour, but it will also allow bugs in real-time threads to completely block the system.

To prevent this from happening, there is a real time throttling mechanism. This makes it possible to limit the amount of CPU power that the real-time threads can consume.

The mechanism is controlled by 2 parameters: rt_period and rt_runtime. The semantics is that the total execution time for all real-time threads may not exceed rt_runtime during each rt_period. As a special case, rt_runtime can be set to -1 to disable the real-time throttling.

More specifically, the throttling mechanism allows the real-time tasks to consume rt_runtime times the number of CPUs for every rt_period of elapsed time. A consequence is that a real-time task can utilize 100% of a single CPU as long as the total utilization does not exceed the limit.

The default settings are: rt_period=1000000 µs, rt_runtime=950000 µs, which gives a limit of 95% CPU utilization.

The parameters are linked to two files in the /proc file system:

Changing a value is done by writing the new number to the corresponding file. E.g.:

$ echo 900000 > /proc/sys/kernel/sched_rt_runtime_us
$ echo 1200000 > /proc/sys/kernel/sched_rt_period_us

See also https://www.kernel.org/doc/Documentation/scheduler/sched-rt-group.txt and https://lwn.net/Articles/296419

PREEMPT_RT is a set of changes to the Linux kernel source code, which when applied will make the Linux kernel more responsive to external interrupts, and more deterministic in the time for performing a task involving cooperating processes.

PREEMPT_RT aims to minimize the amount of kernel code that is non-preemptible (http://lwn.net/Articles/146861). This is accomplished by adding and modifying functionality in the Linux kernel.

The main functional changes done by PREEMPT_RT are:

PREEMPT_RT is managed as a set of patches for the Linux kernel. It is available for a selection of kernel versions. They can be downloaded from https://www.kernel.org/pub/linux/kernel/projects/rt. General information about the patches can be found from the PREEMPT_RT wiki https://rt.wiki.kernel.org/index.php/Main_Page.

It is also possible to obtain a Linux kernel with the patches already applied. A central source is https://git.kernel.org/cgit/linux/kernel/git/rt/linux-stable-rt.git. Another source is Linux from a hardware vendor, providing a Linux kernel with the patches applied. Enea Linux can be configured with or without the patches, depending on the specific customer use case.

Comparing with the total number of lines in the Linux kernel, the PREEMPT_RT patches affect a small percentage. However, it changes central parts of the kernel, which can be seen e.g. by noting that the latest patch set for the Linux 3.12 kernel contains 32 patches that affect the code in the file kernel/sched/core.c. The actual size of the PREEMPT_RT patches can be estimated from the number of files affected, and from the total number of source code lines affected. As an example, the latest patch set for the Linux 3.12 kernel https://www.kernel.org/pub/linux/kernel/projects/rt/3.12 contains 321 patches, affecting (by adding or removing lines of code) 14241 source code lines.

Functionality has been moved, over time, from the PREEMPT_RT patches into the mainline kernel. In this way, the PREEMPT_RT patch set has become smaller. As an example, the latest patch set for the older Linux 3.0 kernel https://www.kernel.org/pub/linux/kernel/projects/rt/3.0 contains 385 patches, adding or removing 16928 lines of source code, which can be compared with the corresponding numbers for the Linux 3.12 kernel (321 patches, 14241 lines), and shows that the PREEMPT_RT patch set has decreased in size.

The PREEMPT_RT functionality is activated, after the PREEMPT_RT patches have been applied and the kernel has been built, by activating a kernel configuration menu alternative. The menu alternative is named Fully Preemptible Kernel (RT).

The performance of a Linux kernel with the PREEMPT_RT patches applied can then be evaluated. A common evaluation methodology involves measuring the interrupt latency. The interrupt latency is often measured from the time of an interrupt until the time when a task, that is activated as a result of the interrupt, begins executing in user space. A commonly used tool for this purpose is cyclictest.

Additional information on results from evaluating the PREEMPT_RT performance is given e.g. in http://www.mpi-sws.org/~bbb/papers/pdf/ospert13.pdf and http://sigbed.seas.upenn.edu/archives/2014-02/ewili13_submission_1.pdf.

When deciding on the use of PREEMPT_RT, its costs and benefits should be evaluated. The use of PREEMPT_RT implies a significant change to the kernel source code. This change involves code that may be less tested and therefore less proven in use than the remaining parts of the mainline kernel.

Another aspect is maintenance. The development of the PREEMPT_RT patch set follows the development of the kernel. When the kernel version is changed, the corresponding PREEMPT_RT patch set, which may be available only after a certain time period, must then be applied to the kernel and the associated tests must be performed.

On the other hand, the use of a PREEMPT_RT-enabled kernel can lead to a system with a decreased worst case interrupt latency and a more deterministic scheduling, which may be necessary to fulfil the real-time requirements for a specific product. For a uni-core system many of the other methods, e.g. full dynamic ticks and CPU isolation, cannot be used, and can therefore make PREEMPT_RT an attractive alternative.

For additional information about the technical aspects of PREEMPT_RT see e.g. http://elinux.org/images/b/ba/Elc2013_Rostedt.pdf.

For additional information about the PREEMPT_RT development status, see e.g. http://lwn.net/Articles/572740.

Linux performs allocation of tasks to CPUs. In the default setting, this is done automatically. In a similar spirit as the default fair task scheduling, which aims at dividing the CPU time for an individual CPUs so that each task gets its fair share of processing time, the scheduler is free to move tasks around, with the goal of evenly distributing the processing load among the available CPUs.

The moving of a task is referred to as task migration. The migration is done by a part of the scheduler called the load balancer. It is invoked, on a regular basis, as a part of the processing done during the scheduler tick. The decision to move a task is based on a variety of input data such as CPU load, task behaviour etc.

For an application which requires determinism, load balancing is problematic. The time to activate a certain task, as a result of an interrupt being serviced, may depend, not only on the scheduling method used, but also on where this task is currently executing.

It is possible to statically assign tasks to CPUs. One reason for doing this is to increase determinism, for example by making the response time to external events more predictable. Assigning a task to a CPU, or set of CPUs, is referred to as setting the affinity of the task.

A mechanism both to set affinity of task and, to turn off automatic load balancing is cpuset. Cpusets make use of the Linux subsystem cgroup. See https://www.kernel.org/doc/Documentation/cgroups/cpusets.txt and https://www.kernel.org/doc/Documentation/cgroups/cgroups.txt.

If we would like to get real time performance on single CPUs systems it is necessary to adapt the entire system, e.g. using the PREEMPT_RT patch or an RTOS. This is not always necessary in a multicore system. Recently added features in the Linux kernel makes it possible to aggressively migrate sources of kernel introduced jitter away from selected CPUs. See Section 3.3.1, CPU Isolation for more information. Doing this provides bare metal-like performance on the CPUs where sources of jitter have been removed. Please note, you can also use a multicore system with CPU isolation to achieve higher throughput, although that is not the focus of this document.

One way to get real-time performance in Linux is by creating a bare metal-like environment in Linux user space. On a default setup, this is not possible since the Linux kernel need to do some regular housekeeping. It is possible to move much of this housekeeping to some dedicated CPUs, provided we have a multicore system. That leaves the other CPUs relatively untouched by the Linux kernel, unless user space triggers some kernel activity. The application that executes in this bare metal environment should avoid using libc calls and Linux system calls. See Chapter 4, Designing Real-Time Applications for more information. Since the kernel is not real-time safe, executing kernel code can have serious impacts on real-time performance.

The biggest sources of kernel jitter are the scheduler and external interrupts. The scheduler's main duty is to switch between tasks. Switching between tasks can of course cause a lot of jitter. This is only a problem if the performance critical task runs with a completely fair scheduler (CFS) policy and therefore gets preempted because of time slicing. A solution for this problem can be to move all non-critical tasks to other CPUs and/or run the critical task with real time policy and an appropriate priority.

The load balancer will try to effectively utilize all the CPUs. That might be good for throughput, but it could damage real-time performance. The obvious problem is that general purpose tasks could be moved to the real-time CPUs and real-time tasks could be moved to general purpose CPUs. The other problem is the actual work of migrating threads. This is easily solved by disabling load balancing on the CPUs that should be isolated.

The scheduler tick causes significant jitter and has negative real-time impact unless the PREEMPT_RT kernel is used. The tick can be removed with the CONFIG_NO_HZ_FULL kernel configuration. Read more about NO_HZ and the tick in Section 2.7, Dynamic Ticks (NO_HZ).

Interrupts can be a big source of jitter. Some interrupts like inter processor interrupts (IPI) and per-CPU timer interrupts need to be bound to a certain CPU. Other interrupts may be handled by any CPU in a multicore system and should be moved away from the isolated CPUs. Many timer interrupts can be removed by changing kernel configurations. See Section 2.11, Interrupts for more info.

The purpose of the tick is to balance CPU execution time between several tasks running on the same CPU. The tick is also used as a timer source for timeouts. Ticks are interrupts generated by a hardware timer and occur at a regular interval determined by the CONFIG_HZ kernel configuration, which for most architectures can be configured when compiling the kernel. The tick interrupt is a per-CPU interrupt.

Starting from Linux 2.6.21, the idle dynamic ticks feature can be configured by using the CONFIG_NO_HZ kernel configuration option. The goal was to eliminate tick interrupts while in idle, to be able to go into deeper sleep modes. This is important for laptops but can also cut down power bills for server rooms.

Linux 3.10.0 introduced the full dynamic ticks feature to eliminate tick interrupts when running a single task on a CPU. The goal here was to better support high performance computing and real-time use cases by making sure that the thread would be run undisturbed. The earlier configuration CONFIG_NO_HZ was renamed to CONFIG_NO_HZ_IDLE, and the new feature got the new configuration option CONFIG_NO_HZ_FULL.

The current implementation requires that ticks are kept on CPU 0 when using full dynamic ticks, which is not required for idle dynamic ticks. The only exception is when the whole system is idle, then the ticks can be turned off for CPU 0 as well.

Whether dynamic ticks turn tick interrupts off is a per-CPU decision.

The following timer tick options are available, extracted from the kernel configuration:

In order to make use of the full dynamic ticks system configuration you must ensure that only one task, including kernel threads, is running on a given CPU at any time. Futhermore there must not be any pending RCU callbacks or timeouts attached to the tick.

The official documentation for dynamic ticks can be found in the Linux kernel source tree https://www.kernel.org/doc/Documentation/timers/NO_HZ.txt. There is also an excellent article about it at LWN, http://lwn.net/Articles/549580.

This section will describe several power saving techniques available in Linux. These techniques does often have impact on the systems real time properties.

A technique not described here is hibernation, e.g. suspend to RAM or disk. The reason is that it is difficult to combine with real-time properties and therefore outside the scope of this manual.

I/O scheduling determines in which order block I/O reads and writes are done. The algorithms require collection of statistics concerning block device activity, which decreases determinism for an eventual real-time application writing/reading to a block device.

In such a scenario, you may want to select the Noop I/O elevator for the block device which your determinism sensitive application is reading from/writing to. However, the effect is expected to be small, and this will have side-effects for other applications accessing the same block device. It may even have negative side effects on your application depending on the type of block device, and the read/write behaviour of the application. Fortunately, the I/O scheduler can be switched in runtime, and should be selected based on the user-specific I/O load scenario.

User-space programs access services provided by the kernel by using system calls. Usually, applications do not invoke system calls directly, but rather use library wrapper functions that in turn execute system calls. A system call always involves a transition from user-space to kernel-space and back. It also involves passing parameters from the application program into the kernel, and back.

A system call becomes a source of indeterminism for the calling task, since the duration of a system call depends on the work done while executing in the kernel. The work may for example involve allocation of resources, such as memory. This may take different amounts of time, depending on the availability of the resources. A system call may even result in the calling task being blocked as a result of a resource not being available. For example, a task reading data from a file may be blocked if there is no data immediately available. At some later time, when the requested resource becomes available, the task resumes its execution. The system call can then be completed and the task can return to user space.

There may also be other tasks wanting to execute during the execution of a system call. If it is possible to switch task during the system call, one or more of these other tasks can be allowed to execute. This can clearly be advantageous if these tasks have deadlines. This type of task switch is referred to as kernel preemption.

It is possible to configure the Linux kernel so that it allows more or less possibilities of kernel preemption. In general, if the level of preemptibility is increased, the Linux kernel becomes more complex and consumes larger part of the cpu time. As a consequence, the application gets a smaller part of the cpu time and the througput performance is decreased.

Hardware indicate events to the software using interrupts. When an interrupt occurs the following is done:

All steps above are executed with all interrupts disabled, i.e. interrupt nestling is not supported. See http://lwn.net/Articles/380931/ for a discussion why nestled interrupts was removed from Linux. The patch found at https://lkml.org/lkml/2010/3/25/434 remove nestled interrupts.

Interrupt handlers can either be registered using request_irq(), or using request_threaded_irq() which registers a threaded interrupt. In both cases the interrupt handler will determine whether the interrupt is to be handled by this interrupt handler or not. The handler returns IRQ_NONE if not.

Interrupt work is normally divided into two parts: Top half and bottom half. The top half is implemented by the interrupt handler. The bottom half is implemented by soft IRQs, tasklets or work queues initiated from the top half, or by the interrupt thread in case of threaded interrupt.

See also Section 2.12, Soft IRQs and Tasklets, Section 2.13, Work Queues and Section 2.14, Threaded Interrupts.

The latency that interrupts induce on a real-time application is determined by the top half, soft IRQs and tasklets. For threaded interrupts, the priority of the interrupt thread can be adjusted to only affect the latency of less critical tasks.

Soft IRQs are intended for deferred interrupt work that should be run without all interrupts being disabled.

Soft IRQ work is executed at certain occasions, such as when interrupts are enabled, or when calling certain functions in the kernel, e.g. local_bh_enable() and spin_unlock_bh(). The soft IRQs can also be executed in the ksoftirqd kernel thread. All this makes it very hard to know when the soft IRQ work will actually be executed. See https://lwn.net/Articles/520076/ for more information about soft IRQ and real-time.

Tasklets builds on soft IRQs, and is basically a generic interface for soft IRQs. While tasklets are much preferred over soft IRQs, the synchronization between interrupt handlers and corresponding soft IRQ or tasklet is non-trivial. For this reason and for achieving better real-time properties it is recommended to use work queues or threaded interrupts whenever possible.

Work queues executes in kernel threads. This means that for work queues, preemption can occur. It also means that work performed in a work queue may block, which may be desirable in situations where resources are requested but not currently available. The reason for using work queues rather than having your own kernel thread is basically to keep things simple. Small jobs are better handled in batches in a few kernel threads rather than having a large number of kernel threads each doing their little thing.

See http://lwn.net/Articles/239633/ for a discussion about why tasklets and soft IRQs are bad and why work queues are better.

When an interrupt handler is registered using request_thread_irq() it will also have an associated interrupt thread. In this case, the interrupt handler returns IRQ_WAKE_THREAD to invoke the associated interrupt thread. If the interrupt thread is already running, the interrupt will simply be ignored.

Even if the interupt handler has an associated interrupt thread, it may still return IRQ_HANDLED to indicate that the interrupt thread does not need to be invoked this time.

There are two main advantages with using threaded interrupts:

An interrupt handler that was registered using request_irq() can be forced to run as a threaded interrupt using a kernel boot parameter named threadirqs. This will result in a short default interrupt handler to be executed instead of the registered interrupt handler, and the registered interrupt handler is run in an interrupt thread. But since the registered interrupt handler is not designed for this it may still invoke soft IRQs causing hard to predict latencies. Interrupt handlers that has been forced to be threaded runs with soft IRQ handling disabled, since they do not expect to be preempted by them.

The Linux scheduler, which handles the process scheduling, is invoked periodically. This invocation is referred to as the Linux scheduler tick.

The Linux scheduler is also invoked on demand, for example when a task voluntarily gives up the CPU. This happens when a task decides to block, for example when data that the task needs are not available.

The frequency of the scheduler tick can be configured when building the kernel. The value typically vary between 100 and 1000 Hz, depending on target.

The scheduler tick is triggered by an interrupt. During the execution of this interrupt kernel preemption is disabled. The amount of time passing, before the tick execution is finished, depends on the amount of work that needs to be done, which in turn depends on the number of tasks in the system and how these tasks are allocated among the CPUs.

In this way, the presence of ticks, with varying completion times, contribute to the indeterminism of Linux, in the sense that a task with a deadline cannot know beforehand how long it takes until it has completed its work, due to it being interrupted by the periodic ticks.

By default, the Linux kernel allows applications to allocate (but not use) more memory than is actually available in the system. This feature is known as memory overcommit. The idea is to provide a more efficient memory usage, under the assumption that processes typically ask for more memory than they will actually need.

However, overcommitting also means there is a risk that processes will try to utilize more memory than is available. If this happens, the kernel invokes the Out-Of-Memory Killer (OOM killer). The OOM killer scans through the tasklist and selects a task to kill to reclaim memory, based on a set of heuristics.

When an out of memory situation occurs, the whole system may become unresponsive for a significant amount of time, or even end up in a deadlock.

For embedded and real-time critical systems, the allocation policy should be changed so that memory overcommit is not allowed. In this mode, malloc() will fail if an application tries to allocate more memory than is strictly available, and the OOM killer is avoided. To disable memory overcommit:

$ echo 2 > /proc/sys/vm/overcommit_memory

For more information, see the man page for proc (5) and https://www.kernel.org/doc/Documentation/vm/overcommit-accounting.

RCU is an algorithm for updating non-trivial structures, e.g. linked lists, in a way that does not enforce any locks on the readers. This is done by allowing modifications to the structures to be done on a copy, and then have a publish method that atomically replaces the old version with the new.

After the data has been replaced there will still be readers that hold references to the old data. The period during which the readers can hold references to the old data is called a grace period.

This grace period ends when the last reader seeing the old version has finished reading. When this happens, an RCU callback is issued in order to free resources allocated by the old version of the structure.

These callbacks are called within the context of a kernel thread. By default these callbacks are done as a soft IRQ, adding hard to predict latencies to applications. There is a kernel configuration option named CONFIG_RCU_NOCB_CPU which combined with the boot parameter rcu_nocb=<cpu list> will relocate RCU callbacks to kernel threads. The threads can be migrated away from the CPUs in the <cpu list> giving these CPUs better real-time properties.

When using the nohz_full kernel boot parameter, nohz_full implies rcu_nocb.

For further reading, see the following links:

RCU concepts: https://www.kernel.org/doc/Documentation/RCU/rcu.txt

What is RCU (contains a lot of good links to LWN articles): https://www.kernel.org/doc/Documentation/RCU/whatisRCU.txt

Relocating RCU callbacks: http://lwn.net/Articles/522262/

Finding the right balance is an iterative process that preferably starts with establishing some benchmark. A common way to evaluate real-time properties is to measure interrupt latency by using the test application cyclictest (https://rt.wiki.kernel.org/index.php/Cyclictest), which sets a timer and measures the time interval from the expected expiration time until the task that set the timer becomes ready for execution.

For the result to be relevant, the system should also be put under stress, see e.g. http://people.seas.harvard.edu/~apw/stress, which can generate various types of stress.

If the attempts in the previous sections to improve the real-time performance are not enough, consider those described in this section.

Linux applications access memory by using virtual addresses. Each virtual address translates into a physical address with the help of hardware that uses translation tables. This feature makes it possible to address more virtual memory than there is physical memory available, assuming that not all applications need all their allocated memory at the same time.

Allocating memory will by default only reserve a virtual memory range. When the first memory access to this newly allocated virtual memory range occurs, this causes a page fault, which is a hardware interrupt indicating that the translation table does not contain the addressed virtual memory. The page fault interrupt will be handled by the Linux kernel, which will provide the virtual-to-physical memory mapping. Then the program execution can continue.

Most architectures use a cache called translation lookaside buffer, TLB, for the translation table. The TLB cache is used to speed up virtual-to-physical memory translations. A translation causes latency jitter when a looked-up address is not in the TLB, which is referred to as a TLB miss.

Virtual memory makes it possible for Linux to have memory content stored in a file, e.g. by loading an executed binary in an on-demand fashion or by swapping out seldom used memory. This is called demand paging, see http://en.wikipedia.org/wiki/Demand_paging for more information on this topic. Demand paging can cause unbound latency since it involves accessing a file or a device. Therefore, the application needs to disable demand paging by using the mlockall() function call:

mlockall(MCL_CURRENT | MCL_FUTURE)

The MCL_CURRENT will make sure that all physical memory has the expected content and that the translation table contains the needed virtual-to-physical memory mapping. This includes code, global variables, shared libraries, shared memory, stack and heap. MCL_FUTURE means that updating the translation table and initializing the physical memory, if applicable, is done during future allocations, not when accessing the memory. Future allocations can be stack growth, heap growth, shm_open(), malloc(), or similar calls like mmap().

When using mlockall(), there is a risk that Linux will allow allocating less memory. For example, the allocated memory must be available as physical memory.

Note that a call to malloc() can still show large latency variation, since now the translation table update is done within this function call instead of when accessing the memory. Not to mention that a malloc() may or may not need to ask for more virtual memory from the kernel. It is therefore recommended to allocate all needed dynamic memory at start, to avoid this jitter.

In case dynamic memory allocation needs to be done within the real-time application, there are some actions that can be performed to mitigate the malloc() latency variation. The glibc has a function called mallopt() which can be used to change the behavior of malloc(). Two interesting options are M_MMAP_MAX and M_TRIM_THRESHOLD.

See the following table for some measurements done on malloc() call time and memory access time. The measurements have been done on a system with CPU isolation.

There are a large number of "4" in the minimum latency column. This is due to the timer resolution that will not allow any smaller values. For a real-time application, the maximum latency is of the greatest importance. The measurements show that when using mlockall(), the memory access becomes more predictable, while malloc() will always have a latency that is hard to predict. Letting the real-time tasks run on dedicated CPUs, here referred to as an RT partition, also results in lower latency jitter.

An alternative is to use another heap allocator than the one provided by glibc;, an allocator which is better adapted for embedded and real-time requirements. Here are two examples:

The glibc itself uses ptmalloc (http://malloc.de/en/), which is a more SMP-friendly version of DLMalloc (http://gee.cs.oswego.edu/dl/html/malloc.html).

Since memory is slow compared to the CPU, there is usually a fast but small memory area called cache between the CPU and the memory. When an access is done to non-cached memory, the CPU needs to wait until the cache has been updated. Accessing a memory location that has not been accessed for a long time will therefore take more time than accessing a recently accessed memory location.

One obvious way to the cache problem is to disable the cache. While this would help the worst case latency it will make the average latency horrible, given that the selected architecture supports disabling the cache. You can also use CPU partitioning to let the real-time application run on the CPU alone, and making sure that this application does not access more memory than fits in the cache.

Another consequence of the per-CPU caches becomes obvious when using shared memory among tasks running on different CPUs. Such memory can be shared either by threads in the same process or by using the shm_open() function call. When such memory is updated by one task and being read by another task running on another CPU, the memory contents need to be copied. This copy usually has a minimum size, called cache line, which for many architectures is 32 bytes. A one byte write will therefore end up copying 32 bytes in this situation, which is 32 times more than might be expected.

Summary:

There are two driving forces to make applications multi-threaded:

A rule of thumb when designing a multi-threaded application is to assign one thread for each source of event, output destination and state machine for controller logic. This will usually lead to many threads, which can result in the application spending a lot of time doing task switches between those threads. A user-space scheduler can solve that problem but then the threads cannot run on different cores. You can also merge threads so that work with higher real-time requirements are kept in separate threads from work with lower real-time requirements.

To make the application truly concurrent, a good choice is to use POSIX threads, pthreads. Each pthread can run on its own core, and all pthreads within the same process are sharing memory, making it easy to communicate between the threads. Be careful however that if the threads need a lot of synchronization, the application will no longer be concurrent despite the fact that several CPUs are used. In this case the application might even become slower than having it as a single thread.

Asynchronous message passing can solve some of the synchronization problems, especially use cases where a thread with high real-time requirements can delegate work to a thread with less real-time requirements. An example of such mechanism is the POSIX functions mq_send() and mq_receive(). One challenge with message passing is how to handle flow control, i.e what to do when the queue is full.

Message passing as well as other synchronization mechanisms, e.g. the POSIX pthread_mutex_lock(), can suffer from priority inversion where a high priority task is forced to wait for a low priority task. For pthread_mutex_lock() it is possible to enable priority inheritance to avoid this problem, while for message passing this needs to be considered when designing the messaging protocol.

Example on how to set priority inheritance for a pthread mutex:

pthread_mutex_t mutex;
pthread_mutexattr_t attr;

pthread_mutexattr_init(&attr);
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
pthread_mutex_init(&mutex, &attr);

When using gcc, you need to compile the code with options "-pthread -D_GNU_SOURCE".

Summary:

I/O accesses usually end up as system calls accessing a kernel driver. This kernel driver then accesses hardware, which can have an unbound latency. The calling task will by default block during this period. It is however possible to perform asynchronous I/O to avoid being blocked. See the aio(7) man page for more information about asynchronous I/O.

The driver can add deferred work to a work queue or to soft IRQs, which can make it hard to predict latencies for a real-time application.

Furthermore, the driver might need some timeouts. If using the full dynamic ticks feature, such timeouts may cause tick interrupts to be triggered. One possible solution to this is to delegate the I/O calls to a task running on another CPU than the real-time tasks. Then the latencies caused by deferred driver work will only affect the delegated task, but not the real-time task.

Note that the I/O concerns are also applicable to text messages sent to stdout or stderr, or text read from stdin. If a device driver writes a diagnostic message from the kernel, e.g. by using the kernel function printk(), the I/O concerns applies to this message as well.

Summary:

Modern CPUs use a number of techniques to speed up code execution, such as instruction pipelines, out-of-order execution, and branch prediction. They all contribute to better average speed in code execution, but will also cause latency jitter. Read more about these topics on http://en.wikipedia.org/wiki/Instruction_pipeline, http://en.wikipedia.org/wiki/Out-of-order_execution, and http://en.wikipedia.org/wiki/Branch_prediction.

Designing real-time applications for SMP systems is more complex than designing for single-CPU systems. Typically, on SMP, all hardware resources such as I/O devices and memory are shared by the CPUs. Since all resources are shared, a low priority task could starve a high priority task, i.e. cause a priority inversion.

There are methods for scheduling multiple access to I/O devices, see Section 2.9, I/O Scheduling, but it is more tricky to manage shared memory. Currently there are no good tools for controlling multiple access to shared memory resources as there are for multiple access to I/O devices. Multiple access to shared memory is more hidden from a software perspective and is largely implemented in hardware.

A proper real-time design should consider how to deal with shared memory and memory congestion, how hyper-threading affects real-time performance, how to use NUMA to improve the execution time, and how to decrease impact of shared resource congestion; all of these topics are covered in this section.

For a deeper study in the area of resource sharing on multi-core devices, see http://atcproyectos.ugr.es/wicert/downloads/wicert_papers/wicert2013_submission_2.pdf.

The x86 architecture has an operating mode called System Management Mode, also known as SMM. It is "a special-purpose operating mode provided for handling system-wide functions like power management, system hardware control, or proprietary OEM designed code." The SMM is entered via an event called system management interrupt, SMI. SMM/SMI has a higher priority than the operating system and will therefore affect the latency. It cannot be disabled by the OS, and even if there might be other ways to disable it, it should probably be kept since it also handles thermal protection. Consequently, there is not much that can be done about it except for adding enough margins to tolerate it. Read more about SMM in http://en.wikipedia.org/wiki/System_Management_Mode.