Linux real time kernel scheduling

While I am working on a real time design on TCP/IP protocol stack, I have the chance to clear the thread of real time scheduling capability on Linux 2.6 kernel and its variants. With O(1) scheduling and real time priority (0 - 99) task and scheduling policy support, standard Linux 2.6 kernel offers soft real time scheduling capability. The defer of the bottom half of interrupt also minimises the interference (delay) to scheduler via softirq and tasklet. I really like the double priority list (active and expired) design in the runqueue where the O(1) scheduling comes from and time slicing calculation, independent to the number of process in the run queue (and wait queue).

RT patch:

There is a hardcore test to prove Ingo's contribution. There are many detailed analysis of Real time Linux patch. This patch is maintained by Ingo Molnar, who is responsible for many other nice features in 2.6 kernel including O(1) priority and time slice calculation, CFS scheduler etc. In a nutshell, RT patch implemented both hard and soft interrupt service function as tasks. Hence instead of running in separate interrupt context, they will be running in kernel task context. RT patch also changed the spinlock from disabling preemption to mutex and introduce localised critical section. Priority inheritance is used to resolve the typical priority inversion problem. Again, this patch is known providing soft real time scheduling, with the best efforts.

RTAI:

RTAI (Real-Time Application Interface) is a real-time extension for the Linux kernel. It supports several architectures:

• x86 (with and without FPU and TSC)
  
• x86-64
  
• PowerPC
  
• ARM (StrongARM; ARM7: clps711x-family, Cirrus Logic EP7xxx, CS89712, PXA25x)
  
• MIPS
  

RTAI provides deterministic response to interrupts, POSIX compliant and native RTAI real-time tasks. It consists mainly of two parts:

• An Adeos-based patch to the Linux kernel which introduces a HAL (hardware abstraction layer)
  
• A broad variety of services which make real-time programmers' lives easier. RTAI does provide implementations for scheduling policies as RMS, and EDF other than the standard ones offered by Linux 2.6 kernel such as SCHED_FIFO, SCHED_RR, SCHED_OTHER (where dynamic priority scheduling is enabled). SCHED_FIFO and SCHED_RR are normally used for real time tasks which are both static priority scheduling and both do not allow lower priority tasks to preempt higher priority ones, even when allocated time slices are exhausted (in SCHED_RR case). RTAI has a finer timer and also introduces a real time (non-blocking) FIFO for deterministic data transfer between tasks. The heart of RTAI implementation is the HAL layer between Linux kernel and different hardware, which makes this layer very much platform-dependent. The other arguable feature introduced by RTAI is allowing user space tasks to be scheduled via LXRT interface to achieve hard real time performance. It was reported that RTAI is integrated most desirable with Vanilla kernel (2.6.19).
• Here is a good example project to start from. If you wish to carry out a quantative comparison of how much boost RTAI brings to you, this post gives a few bench mark measurements. Just in case, I put the installation guide here as well. To port your existing Linux programs to take advantage of RTAI, you might want to start from LXRT APIs. At last, if you want a quick summary to take away, here is your PPT. With a worse case report at 48 us scheduling latency and jitter in the range of 10's microseconds on its LXRT branch, RTAI is my favorite.

Xenomai:

Originally from RTAI/fusion branch, Xenomai focuses on extensibility, portability, and maintainability while RTAI is focused on performance such as real time scheduling, latencies, etc. A good comparison article could be found here.

Supported architectures are:

• x86: from i386 to latest Pentiums and AMD's, UP and SMP
  
• x86_64
  
• PowercPC (follows DENX tree):
  
• Freescale family: PowerQUICC I, PowerQUICC II, PowerQUICC III, ..
  
• AMCC family: 405, 440, ..
  
• PowercPC 64 (follows DENX tree):
  
• PA6T
  
• IA64 (discontinued since v2.5)
  
• ARM cores:
  
• Integrator/CP ARM 1136
  
• PXA
  
• SA1100-based
  
• Freescale iMX21/csb535fs
  
• Atmel at91rm9200 (tested on CSB637)
  
• Samsung S3C24xx
  
• Intel ixp4xx
  
• Atmel at91sam926x
  
• Motorola i.MX family
  
• Analog Devices Blackfin BF52x, BF53x, BF54x and BF56x
  

I do like the robot project from Hannover. A good serial port driver comparison between RTAI and Xenomai is available on Capitain. The other major focus of the Xenomai project is to help creating emulators of traditional RTOS APIs that ease the migration from these systems to a GNU/Linux-based real-time environment. As of now, the following real-time interfaces

are available:

• pSOS+ emulator
  
• VRTXsa emulator
  
• VxWorks emulator
  
• uITRON implementation

I could really see Xenomai playing an interesting role in the real time virtulisation applications rather than providing powerful generic emulation interfaces for multiple RTOSes. Minute virtual machine in Xenomai comes with a graphical debugger named Xenoscope that allows tracing the execution of real-time software at source code level in a simulated environment. This tool shows precisely how the multiple threads running in the system work together sharing the resources of a given real-time interface (e.g. who is locking a semaphore, which thread has been readied or suspended by a given system call, and so on).

-------------------------

- Real time application  -

-------------------------

-     RTOS emulators     -

-------------------------

-  Xenomai nanokernel  -

-------------------------

-   Host software arch    -

-      (e.g. RTAI-x86)      -

-------------------------

RTLinux (To be updated)