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)

ARM Cross Compiler on Windows

Instead of using commercial suite such as RealView, I decided to set up my own cross compiler and development enviroment. The target ARM device has a > 2.6 linux kernel running, and host as usual is on Windows.

• Install Cygwin with gcc packages and other make tools selected.

• Get the source for cross compiler
  

Dan Kegel's crosstool project provides a fully automated build script covering plenty of different architectures and compiler versions. The latest stable version can be found at http://www.kegel.com/crosstool/ or svn from googlecode:

svn checkout http://crosstool.googlecode.com/svn/trunk crosstool

There is a good reference on wikipage for other options.

• Build the cross compiler in your enviroment for your target device
  

After checking out the source code, you will find several shell scripts named demo-*.sh under /src. Open the file for the architecture you require, in this case ARM, thus I chosed the demo-arm.sh file. This script has one line for each known working toolchain for this architecture. An example of the demo-arm.sh looks like this:

RESULT_TOP=/opt/crosstool

[...]

#eval `cat arm.dat gcc-4.1.0-glibc-2.2.2.dat` sh all.sh --notest

eval `cat arm.dat gcc-4.1.0-glibc-2.3.2.dat` sh all.sh --notest

If you require a gdbserver to build, you need to add --gdb to the end of the eval command. Running this shell script will build the cross compiler and gcc binaries for you under /opt/crosstool/gcc-4.1.0-glibc-2.3.2/arm-unknown-linux-gnu/bin. You will be likely to get errors as crosstool shell script won't support space in windows style directory in your HOME enviroment setting, however with not so helpful error message "...incorrect number of arguments". To get over this, 

$ printenv HOME

/cygdrive/c/Documents and Settings/

$ HOME=/cygdrive/c/DOCUME~1/

$ ./demo-arm-softfloat.sh

• It seems a neat idea to install remote file system plugins on Eclipse (+ CDT package as I am using C++). It turned out to be quite a hurdle! I will try to post my tuning on Eclipse (on Windows) to use the cross compiler we just had and transfer binary across to remote Linux OS.

Open source target motion control - Part I

I have always wanted to be a pioneer to introduce an open source ARM based dual core processor into machinery control. Most of the machine control platform right now are either based on third party generic design motion controller (i.e. Baldor) or in-house microcontroller and DSP based for very specific control application. 

Basically, we need a host enviroment, a target-simulation enviroment and a real target device to do the work. In simplest term, it roughly go like this: develop and then port your programs from host to the target-simulator, and then download the image to the target device.

• Host, in this case I use Ubuntu
• Target-simulator (or a cross-compiling platform). Install Scratchbox on Ubuntu Hardy
• Target device, the latest dual core automotive control SoC device DIOPSIS from Atmel

wget http://repository.maemo.org/stable/3.1/maemo-scratchbox-install_3.1.sh 

chmod +x maemo-scratchbox-install_3.1.sh 

sudo ./maemo-scratchbox-install_3.1.sh -d

/scratchbox/sbin/sbox_adduser USER yes

/scratchbox/login

[1] For the inconsistency detected by ld.so: rtld.c: 1192: dl_main: Assertion ‘(void *) ph->p_vaddr == _rtld_local._dl_sysinfo_dso’ failed! problem, it’s necessary to disable “vdso”:

echo 0 | sudo tee /proc/sys/vm/vdso_enabled

[2] For problems when building packages (mmap: permission denied when building), it’s necessary to reduce the mmap minimum address:

echo 4096 | sudo tee /proc/sys/vm/mmap_min_addr

[3] To make these changes permanent across reboots, one can add these settings to /etc/sysctl.conf:

vm.vdso_enabled = 0

vm.mmap_min_addr = 4096

Then run

sudo sysctl -p

Unfortunately, I am running scratchbox in Ubuntu Hardy, which in turn is within a virtual box on Windows XP SP2... Anyway, the fact is you will not be able to access network within scratchbox after the installation. Somehow this is not a problem if you install on Debian distributions (this shows how much scratchbox people love Debian!)

What you need to do is to modify the following two conf files:

• /scratchbox/etc/nsswitch.conf (change nameserver to the correct IP address in your subnetwork)
  
• /scratchbox/etc/resolv.conf (change the line "hosts: xxxx" to "hosts: files dns")
  

One caveat is that you will not be able to change these two files IN scratchbox, even you do chmod 666 magic. You have to logoff scratchbox and change these two files outside. (Display hidden port and programs which are using them, netstat -nap)

Now you can use apt or wget to install packages onto your target simulation linux device. Here is a quite template list for /etc/apt/sources.list. Mine are

deb http://ftp.us.debian.org/debian/ stable main contrib non-free

deb-src http://ftp.us.debian.org/debian/ stable main

deb http://security.debian.org/ stable/updates main contrib non-free

After the enviroment is ready, one of my first step was to get my favorite messaging middleware onto ARM + Linux combination - zero messaging queue.  Malo has reported that he has successfully done the porting. Somehow I found there are many more quite involved problems. I will find some other time to list them all.

Be aware that if you are trying to build latest version of autotools or GNU M4 for marco scipting you will find them in " /usr/local/bin", rather than the "/scratchbox/tools/bin". So make sure in your sh script file you are referring to the correct location to use the right version.

Some useful links:

Boost

http://www.internettablettalk.com/forums/showthread.php?t=8241

http://linux.zipitwireless.com/wiki/Scratchbox

http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dai0221a/ar01s02s01.html

Change the size of existing image