C. LINUX REALTIME APPROACHES

The following general approaches to Linux realtime have been proposed, along with many variations on each of these themes:

1. non-CONFIG_PREEMPT
2. CONFIG_PREEMPT
3. CONFIG_PREEMPT_RT
4. Nested OS
5. href=”#5″>Dual-OS/Dual-Core
6. Migration Between OSes
7. Migration Within OS

Each of these general approaches is discussed in the following sections. Each section ends with a brief (but perhaps controversial) summary of the corresponding approach's strengths and weaknesses. I do not address “strength of community”, even though this may well be the decisive factor. After all, the technical comparision will provide sufficient flame-bait.

This document does not present measured comparisons among all of the approaches, despite the fact that such comparisons would be extremely useful. The reason for this, aside from gross laziness, is that it is wise to agree on the metrics beforehand. Therefore, the comparisons in this document are for the most part qualitative. In some cases, they are based on actual measurements, but these measurements were taken by different people on different configurations using different benchmarks. This is a prime area for future improvement.

1. non-CONFIG_PREEMPT

   This is the stock kernel, not even using preemption. Why would -anyone- think of using stock 2.6 for a realtime task? Because some realtime applications have very forgiving scheduling deadlines. One project I worked on in the early 1980s had 2-second response-time deadlines. This was quite a challenge, given that it was running on a 4MHz Z80 CPU — though, to be fair, the Z80 was accompanied by a hardware floating-point processor that was able to compute a 32-bit floating-point multiply in well under a millisecond. Modern hardware running a stock Linux 2.6 kernel would have no problem with this application. Hey, just having 32 address bits rather than only 16 would help a lot!

   1. Quality of service: soft realtime, with timeframe of 10s of milliseconds for most services. Some I/O requests can take longer. Provides full performance and scalability to both realtime and non-realtime applications.
   2. Amount of code that must be inspected to assure quality of service for a new feature: the entire kernel, every little bit of it, since the entire kernel runs with preemption disabled.
   3. API provided: POSIX with limited realtime extensions. Realtime and non-realtime applications can interact using the normal POSIX services.
   4. Relative complexity of OS and applications: everything is stock, and all the normal system calls operate as expected.
   5. Fault isolation: none.
   6. Hardware and software configurations supported: all of them. Larger hardware configurations and some device drivers can result in degraded response time.

   Strengths: Simplicity and robustness. “Good enough” realtime support for undemanding realtime applications. Excellent performance and scalability for both realtime and non-realtime applications. Applications and administrators see a single OS instance.

   Weaknesses: Poor realtime response, need to inspect the entire kernel to find issues that degrade realtime response.

2. CONFIG_PREEMPT

   The CONFIG_PREEMPT option renders much of the kernel code preemptible, with the exception of spinlock critical sections, RCU read-side critical sections, code with interrupts disabled, code that accesses per-CPU variables, and other code that explicitly disables preemption.

   1. Quality of service: soft realtime, with timeframe of 100s of microseconds for task scheduling and interrupt handling. System services providing I/O, networking, task creation, and VM manipulation can take much longer. A very small performance penalty is exacted, since spinlocks and RCU must suppress preemption.
   2. Amount of code that must be inspected to assure quality of service for a new feature:
      1. The low-level interrupt-handing code.
      2. The process scheduler.
      3. Any code that disables interrupts, which includes all interrupt handlers, both hardware and softirq.
      4. Any code that disables preemption, including spinlock critical sections, RCU read-side critical sections, code with interrupts disabled, code that accesses per-CPU variables, and other code that explicitly disables preemption.
      5. Any code that holds a lock, mutex, semaphore, or other resource that is needed by the code implementing the new feature.

   3. API provided: POSIX with limited realtime extensions
   4. Relative complexity of OS and applications: all the normal system calls operate as expected, so realtime and non-realtime processes can interact normally.
   5. Fault isolation: none.
   6. Hardware and software configurations supported: all of them. Larger hardware configurations and some device drivers can result in degraded response time.

   Strengths: Simplicity. Available now, even from distributions. Provides “good enough” realtime support for a large number of applications. Applications and administrators see a single OS instance.

   Weaknesses: Limited testing, so that some robustness issues remain. Need to inspect large portions of the kernel in order to find issues that degrade realtime response.

3. CONFIG_PREEMPT_RT

   The CONFIG_PREEMPT_RT patch by Ingo Molnar introduces additional preemption, allowing most spinlock (now “mutexes”) critical sections, RCU read-side critical sections, and interrupt handlers to be preempted. Preemption of spinlock critical sections requires that priority inheritance be added to prevent the “priority inversion” problem where a low-priority task holding a lock is preempted by a medium-priority task, while a high-priority task is blocked waiting on the lock. The CONFIG_PREEMPT_RT patch addresses this via “priority inheritance”, where a task waiting on a lock “donates” its priority to the task holding that lock, but only until it releases the lock. In the example above, the low-priority task would run at high priority until it released the lock, preempting the medium-priority task, so that the high-priority task gets the lock in a timely fashion. Priority inheritance has been used in a number of realtime OS environments over the past few decades, so it is a well-tested concept.

   One problem with priority inheritance is that it is difficult to implement for reader-writer locks, where a high-priority writer might wish to donate its high priority to a large number of low-priority readers. The CONFIG_PREEMPT_RT patch addresses this by allowing only one task at a time to read-acquire a reader-writer lock, although it is permitted to do so recursively.

   Note that a few critical spinlocks remain non-preemptible, using the “raw spinlock” implementation.

   1. Quality of service: soft realtime, with timeframe of about 10 microseconds for task scheduling and interrupt-handler entry. System services providing I/O, networking, task creation, and VM manipulation can take much longer. Since spinlocks are replaced by blocking mutexes, some believe that the performance penalty is significant. There is likely to be some performance penalty exacted from RCU, but, with luck, this penalty will be minimal.
   2. Amount of code that must be inspected to assure quality of service by a new feature:
      1. The low-level interrupt-handing code.
      2. The process scheduler.
      3. Any code that disables interrupts, but -not- including interrupt handlers, which now run in process context.
      4. Any code that disables preemption, including raw-spinlock critical sections, code with interrupts disabled, code that accesses per-CPU variables, and other code that explicitly disables preemption.
      5. Any code that holds a lock, mutex, semaphore, or other resource that is needed by the code implementing the new feature.

   3. API provided: POSIX with limited realtime extensions.
   4. Relative complexity of OS and applications: all the normal system calls operate as expected, so realtime and non-realtime processes can interact normally.
   5. Fault isolation: none.
   6. Hardware and software configurations supported: most of them. SMP support is a bit rough, and a number of drivers have not yet been upgraded to work properly in the CONFIG_PREEMPT_RT environment. It is likely that larger hardware configurations and some device drivers can result in degraded scheduling latency, but given that normal spinlocks are now preemptible, this effect should be much less of an issue than for CONFIG_PREEMPT.

   Strengths: Excellent scheduling latencies, potential for hard realtime for some services (e.g., user-mode execution) in some configurations. A number of aspects of this approach might be incrementally added to Linux (e.g., priority inheritance for semaphores to prevent semaphore priority inversion). Applications and administrators see a single OS instance.

   Weaknesses: Limited testing, so that robustness issues remain. Large patch to Linux (~18K lines of context diff). Both realtime and non-realtime applications pay performance and scalability penalties for the realtime service.

4. Nested OS

   The Linux instance runs as a user process in an enclosing RTOS. Realtime service is provided by the RTOS, and a richer set of non-realtime services is provided by the Linux instance.

   1. Quality of service: hard realtime, with timeframe of about 10 microseconds for services provided by the underlying RTOS. More complex services (I/O, task creation, and so on) will likely take longer to execute, which may impose a significant performance and scalability penalty.
   2. Amount of code that must be inspected to assure quality of service by a new feature:
      1. All of the RTOS. One would strive to keep the RTOS quite small, the greater the number of realtime services provided, the larger the RTOS must be.
      2. Any Linux-kernel code that disables interrupts. Note that in many implementations, the Linux kernel will be prevented from disabling interrupts, since any attempt to disable interrupts will trap into the RTOS.

         If the Linux kernel runs in privileged mode, however, all bets are off. In this case, special care must be used to avoid disabling the real hardware interrupts, including such disabling within any kernel modules that might be loaded.

   3. API provided: Whatever the RTOS wants to provide, often a subset of POSIX with realtime extensions.
   4. Relative complexity of OS and applications: there are now two operating systems, both of which must be configured and administered. Applications that contain both realtime and non-realtime components must be explicitly aware of both OS instances, and of their respective APIs.
   5. Fault isolation: the following faults may propagate from the Linux OS to the underlying RTOS, or not, depending on the implementation:
      1. Excessive disabling of interrupts, if the Linux instance is permitted to disable them (hopefully not).
      2. Memory corruption, if the Linux instance is given direct access to the hardware MMU or to DMA-capable I/O devices.

   6. Hardware and software configurations supported: depends on the implementation, however, there are products with this architecture that support SMP and a reasonable variety of devices. Note that supporting a large variety of devices either requires that this support be present in the RTOS, or that Linux be granted access to the devices. In the latter case, Linux will likely have the ability to DMA over the top of the RTOS.

   Strengths: Excellent scheduling latencies. Hard-realtime support for some services in some configurations. Reasonable fault isolation for some implementations. Well-tested and robust implementations are available.

   Weaknesses: Realtime application software must deal with two separate OS instances and their respective APIs, with explicit communication. Administrators must deal with two OS instances. Non-realtime applications are likely to suffer significant performance and scalability penalties. The pair of cores will be more expensive than a single core, though one might use virtualization to emulate the two CPUs.

5. Dual-OS/Dual-Core

   Linux and RTOS instances run side-by-side on different CPUs in the same system. The CPUs might be different physical CPUs, different hardware threads in the same CPU, or different virtual CPUs provided by a virtualizing layer, such as Xen. The two instances might or might not share memory, and, if they do share memory, there might or might not be hardware protection to prevent one OS from overwriting the other OS's memory.

   1. Quality of service: hard realtime, with timeframe of about 10 microseconds for services provided by the RTOS. More complex services (I/O, task creation, and so on) will likely take longer to execute. Since the Linux instance runs on a separate core, there need not be any performance or scalability penalty for non-realtime tasks.
   2. Amount of code that must be inspected to assure quality of service by a new feature: all of the RTOS, but only the RTOS. One would strive to keep the RTOS quite small, but the greater the number of realtime services provided, the larger the RTOS must be.
   3. API provided: Whatever the RTOS wants to provide, often a subset of POSIX with realtime extensions.
   4. Relative complexity of OS and applications: there are now two operating systems, both of which must be configured and administered. Applications that contain both realtime and non-realtime components must be explicitly aware of both OS instances and APIs, and must also be aware of whatever hardware facility is used to communicate between the realtime and non-realtime CPUs.
   5. Fault isolation: the following faults may propagate from the Linux OS to the underlying RTOS, or not, depending on the implementation:
      1. Memory corruption, but only if the Linux instance is given direct access to the RTOS's memory or to DMA-capable I/O devices that can access the RTOS's memory.
   6. Hardware and software configurations supported: depends on the implementation, however, there are products based on this approach that support SMP and a reasonable variety of devices.

   Strengths: Best possible scheduling latencies with the hardest reasonable realtime — just as good as bare metal in some implementations. Best possible fault isolation for some implementations. Well-tested and robust implementations are available. Linux can be used as is, so full performance and scalability can be provided to non-realtime tasks.

   Weaknesses: Realtime application software must deal with two separate OS instances, with explicit communication. Administrators must deal with two OS instances. “RTOSes” that provide the best latencies offer the least services — in extreme cases, the only service is execution of raw code on bare metal.

6. Migration Between OSes

   A Linux and RTOS instance run side-by-side in the same system. The two OSes might run on different physical CPUs, different hardware threads in the same CPU, different virtual CPUs provided by a virtualizing layer like Xen, or alternatively, the two OSes might use some sort of interrupt-pipeline scheme (such as Adeos) to share a single CPU.

   However, applications see a single unified environment. Applications run on the RTOS, but the RTOS provides Linux-compatible system calls and memory layout. If the application invokes a non-realtime system call, the task is transparently migrated to the Linux OS instance for the duration of that system call. This differs from the other dual-OS approaches, where the applications must be explicitly aware of the different OSes. At this writing, it appears that the two instances need to share memory, since tasks can migrate from one OS to the other.

   1. Quality of service: hard realtime, with timeframe of about 10 microseconds for services provided by the RTOS. More complex services (I/O, task creation, and so on) will likely take longer to execute. It is also possible for tasks to be “trapped” in the Linux instance, for example, if they are sleeping, but have not yet been given a chance to respond to some event that should wake them up. The performance and scalability penalties to non-realtime tasks can be expected to depend on the amount of protection provided for realtime tasks against non-realtime misbehavior — the greater the protection, the greater the expected penalty. It may be possible to provide hardware support to improve this tradeoff.
   2. Amount of code that must be inspected to assure quality of service by a new feature:
      1. All of the RTOS. One would strive to keep the RTOS quite small, but the greater the number of realtime services provided, the larger the RTOS must be.
      2. Any Linux-kernel code that disables interrupts. Note that in many implementations, the Linux kernel will be prevented from disabling interrupts, since any attempt to disable interrupts will trap into the RTOS or into the underlying software/firmware layer (e.g., Xen or Adeos).

         If the Linux kernel runs in privileged mode, however, all bets are off. In this case, special care must be used to avoid disabling the real hardware interrupts, including such disabling within any kernel modules that might be loaded.

   3. API provided: Full POSIX with realtime extensions. Anytime a task running in the context of the RTOS attempts to execute a non-realtime system call, it is migrated to the Linux instance.
   4. Relative complexity of OS and applications: there are now two operating systems, both of which must be configured and administered. However, applications can be written as if there was only one OS instance that provided the full set of services, some realtime and some not.
   5. Fault isolation: the following faults may propagate from the Linux OS to the underlying RTOS, or not, depending on the implementation:
      1. Excessive disabling of interrupts, if the Linux OS is permitted to disable hardware interrupts (hopefully not, though preventing this may require special hardware).
      2. Memory corruption, either due to wild pointer or via wild DMA.

   6. Hardware and software configurations supported: depends on the implementation, however, it is reasonable to believe that SMP and a reasonable variety of devices could be supported. Note that supporting a large variety of devices either requires that this support be present in the RTOS, or that Linux be granted access to the devices. In the latter case, Linux will likely have the ability to DMA over the RTOS.

   Strengths: Excellent scheduling latencies. Hard-realtime support for some services in some configurations. Applications see a single OS.

   Weaknesses: Administrators must deal with two OS instances. The two OSes will be extremely sensitive to each other's version and patch level, since they access each other's data structures.

7. Migration Within OS

   A Linux instance runs on multiple CPUs, either different physical CPUs, different hardware threads in the same CPU, or different virtual CPUs provided by a virtualizing layer such as Xen. Some (but not all!) of the CPUs are designated as realtime CPUs. If a task running on a realtime CPU executes a trap or system call that contains non-deterministic code sequences, the task is migrated to a non-realtime CPU to complete execution of the trap or system call, then migrated back. This prevents any non-realtime execution of a given realtime task from interfering with that of other realtime tasks. Interrupts can be directed away from realtime CPUs. Such interrupt redirection is supported on a few architectures, and has in fact been used for realtime support since at least the 2.4 kernel.

   1. Quality of service: unknown at present. This approach is expected to provide hard realtime with timeframe of about 10 microseconds for services provided on the realtime CPUs. More complex services (I/O, task creation, and so on) will likely take longer to execute. It is also possible for tasks to be “trapped” on the non-realtime CPUs, for example, if they are sleeping, but have not yet been given a chance to respond to some event that should wake them up. Since a stock non-CONFIG_PREEMPT Linux may be used, there need be no performance or scalability penalty for non-realtime tasks, nor for realtime tasks that execute only realtime operations. There can be a significant migration penalty when realtime tasks frequently execute non-realtime operations.
   2. Amount of code that must be inspected to assure quality of service by a new feature:
      1. Any part of the Linux kernel that is permitted to execute on the realtime CPUs. This would normally be only the realtime portions of the scheduler and the low-level interrupt and trap handling code (the actual interrupts and traps would be migrated, if necessary).
      2. Any critical section of any lock acquired by the portion of the Linux kernel that is permitted to execute on the realtime CPUs.

   3. API provided: Full POSIX with realtime extensions.
   4. Relative complexity of OS and applications: There is but one OS, though it has a bit of added complexity due to the migration capability. Applications see only one OS.
   5. Fault isolation: the following faults may propagate from the non-realtime CPUs to the realtime CPUs:
      1. Holding a lock, mutex, or semaphore for too long, when that resource must be acquired by code that is permitted to run on the realtime CPUs.
      2. Memory corruption, either due to wild pointer or via wild DMA.

   6. Hardware and software configurations supported: all configurations, though single-CPU systems must have some sort of virtualizing facility so that the OS sees at least two virtual CPUs.

   Strengths: Excellent scheduling latencies. Hard-realtime support for some services in some configurations. Applications and administrators see a single OS and API. Full performance and scalability for non-realtime and for pure-realtime tasks.

   Weaknesses: Migration overhead. Strictly theoretical, as no implementations exist. Requires multiple CPUs, either real or virtual.

Continue HERE . . .

1. INTRODUCTION
2. DESIRABLE PROPERTIES
3. LINUX REALTIME APPROACHES
4. SUMMARY

 
This article was originally published on LinuxDevices.com and has been donated to the open source community by QuinStreet Inc. Please visit LinuxToday.com for up-to-date news and articles about Linux and open source.