Design Con 2015

Getting real (time) about embedded GNU/Linux

Robert Berger

July 20, 2010

Robert BergerJuly 20, 2010

According to the 2010 Embedded Market Study[1] the percentage of people who are not using Embedded GNU/Linux due to the lack of real-time capabilities went down from 25% in 2007 to 18% in 2010. I'll leave it up to you to interpret those numbers, but I strongly believe that it might be worth having a look at this subject.

 

What is real-time?

Real-time might, as the name implies, sometimes also be about timeliness (fast), but in my humble opinion it's usually about determinism. To be precise about event- and temporal determinism (event determinism meaning that you know the state of the outputs with a given set of inputs; temporal determinism meaning that you also know exactly the timing).

 

Coming back to real-time versus real fast - In case of an aircraft navigation system deadlines are in the tens of milliseconds, while for an airline reservation system the deadlines are at about 15 seconds.

 

The latter must be deterministic just like the former one, but does not need to be so fast. After thirty years of research there is still no universal methodology to create real-time systems and that's why in real life real-time is defined as follows:”A real-time system will pass a specified test suite.[2]” Let's stick to those wise words of Paul E. McKenny for the time being.

 

Is it possible to have a 100% deterministic real-time GNU/Linux kernel?

To answer this you need to keep in mind that the same GNU/Linux kernel code base runs on the world's fastest supercomputers as well as mobile phones. GNU/Linux was not written with real-time in mind - not even to run on supercomputers or mobile phones - but to provide by default maximum raw processing power and throughput shared in a fair way among users and processes, which is typical for multi-user multi-processing operating systems.

 

It's a monolithic kernel, which means that device drivers and scheduler reside side by side in what's called kernel space (an area which is protected from direct user space access which deals among other things with process control including I/O (input/output) and interrupt handling). GNU/Linux supports more different types of devices and processors than any other operating system ever has in the history of computing.[3]

 

So although it is possible to make the scheduler behave deterministic like one would expect from a real-time operating system you can not assume that all GNU/Linux drives are written with real-time in mind as well.

 

This means that if you don't use those drivers/configurations which destroy the real-time behavior a “real-time enabled” GNU/Linux does not behave worse than other real-time kernels. Besides you can always run GNU/Linux on top of a real-time operating system. We'll see more about this soon.

 

Why would you add real-time capabilities to GNU/Linux?

If you are after a real-time operating system which behaves deterministic with all possible configuration options and including all possible drivers I'm afraid you should look for some other solutions out there. Tell your marketing guys they'll have to find other buzzwords besides “Linux” to sell their stuff. At least for the time being it's not going to be GNU/Linux.

 

Maybe some time in the future enough companies will be willing to cooperate to build up enough critical mass for the “Comprehensive real-time GNU/Linux project”. But if you work on the majority of applications, which might need some real-time capabilities for some processes, but most processes are “not so real-time” and on top of this you would like to use and/or reuse the GNU/Linux infrastructure let's see how this can be done.

 

Adding real-time to a plain vanilla GNU/Linux kernel

So far two approaches have been successfully deployed to achieve this goal. One patches the vanilla GNU/Linux kernel to make it real-time, while the other uses a real-time operating system where GNU/Linux runs as the idle task on top of it. Let’s call the former a PREEMPT_RT patched kernel and the latter a dual kernel approach.

 

What's this all this PREEMPT-RT stuff about? RT comes from real-time, so let's first see what's the “preempt” in PREEMPT-RT. Assume you have two processes and want the second (higher priority one) to run at certain predefined times. A time tick interrupt will come along and interrupt/preempt whatever runs, the scheduler will be invoked and the lower priority process will be de-scheduled while the higher priority process will be scheduled. 

 

Remember that in a preemptive operating system it's always the highest priority process that's supposed to be running. This means that you should have only one highest priority process at the time and yes we don't want to share the CPU fairly between the processes, but give it all to the one and only highest priority process.

 

In case where we don't have a preemptive operating system but a cooperative one process one would need to give up the CPU to let process two run, so process two is doomed to run late. (Figure 1 below).

 

Figure 1. [GR-1] Preemptive versus non-preemptive scheduling.

 

Several degrees of real-time behavior are available in GNU/Linux starting from none, which is the standard Linux behavior, followed by

 

CONFIG_PREEMPT_VOLUNTARY, which utilizes explicit preemption points and CONFIG_PREEMPT_(DESKTOP), which uses implicit preemption points up to CONFIG_PREEMPT_RT which enables full blown preemption.

 

Please note that from none to PREEMPT_RT the latency versus throughput trade off can be observed. Throughput decreases while determinism increases and vice versa.

The degrees of determinism available for GNU/Linux

1) PREEMPT_NONE. That's the default scheduler of a vanilla GNU/Linux kernel. It's geared towards maximum raw processing power and throughput. Every process gets it's fair share of  the CPU as it is  typical for a classical Unix multi-user environment. By default processes can not be preempted while they execute system calls and since, among other things, the timing behavior of some kernel services is non deterministic the whole thing is not deterministic as well.

 

2) PREEMPT_VOLUNTARY. Around 2001 Ingo Molnar and later on Andrew Morton introduced preemption points in long running pieces of code, which is widely known as “low-latency patches”. This  reduces the latency at the cost of slightly lower throughput. This enables reacting to interactive events by allowing a low priority process to voluntarily preempt itself even if it is in kernel mode executing a system call.[4]

 

3) PREEMPT_(DESKTOP). Explicit preemption points are hard to find, so Robert Love and others went out to seek for implicit preemption points. Among other things spinlocks and interrupt return code were modified to implement implicit preemption points.

 

A spinlock is, similar to a mutex, used to protect access to shared resources. It's usually implemented by a hardware test and set operation. When a process attempts to access a resource that is in use by another process, the “blocked” process(es) will “spin” (busy wait) until the resource becomes available. 

 

This option further reduces the latency of the kernel by making all kernel code that is executing in a critical section preemptible.  The latency is further reduced at the cost of slightly lower throughput and a slight runtime overhead to kernel code.[4]

 

4) PREEMPT_RT[GR-2]. The goal of the real-time preemption patch is to make fixed priority preemptive scheduling (i.e. POSIX SCHED_FIFO and SCHED_RR classes) as close as possible to their ideal behavior and all this with no impact for users/processes not interested in real-time. (Figure 2, below)

 

Figure 2. {GR-2] PREEMPT-RT

 

This can be achieved by executing all activities in a “schedulable thread” context.  It's maintained by Ingo Molnar and Tom Gleixner and the design is fully preemptible and deterministic with respect to scheduling, interrupt handling and high resolution timers. It supports priority inheritance and preemptible hard- and soft interrupts.

 

It might be interesting to note that PREEEMPT_RT is driven by embedded,  industrial and enterprise communities, which means that determinism is slowly getting more important than throughput for some applications even for the enterprise people.

 

It's ideal for applications where it's difficult to separate the real-time from the non real-time part. Real-time applications are written in user space utilizing the POSIX API and mainline drivers can be used with the restrictions mentioned above.  At the moment more than 80% of the PREEMPT_RT patch is in the mainline GNU/Linux kernel and there are no further fundamental issues open, which means that it is sooner or later going to be the “standard” GNU/Linux real-time solution.

 

What's this dual kernel stuff about? [GR-3]

Dual kernel GR3 approaches (Figure 3, below) are driven by embedded and industrial communities.  There are many implementations like RTLinux/GPL, XM/eRTL, Real-Time Core, XtratuM, seL4, PaRTiKle to name a few. Dual kernel implementations are trying to solve two different issues. One is the safety/security domain, which we are not going to cover here, the other is real-time.

 

Figure 3. [GR-3] DUAL KERNEL

 

The most prominent real-time community projects seem to be RTAI [5] and Xenomai[6]. RTAI aims for the lowest technically feasible latencies, while Xenomai is after portability and maintainability and providing RTOS skins in order to ease the porting of legacy applications to Linux. 

 

Both solutions will support PREEMPT-RT once it's fully in the mainline kernel. For dual kernel implementations an extra software layer is introduced between the hardware and the GNU/Linux kernel to manage real-time tasks separately from it. This means that a semantic separation between real-time and non real-time domains is required by design and GNU/Linux can be seen as the idle task of a real-time kernel.

 

Funny things happening in the non real-time domain have potentially only minimal impact on the real-time domain. Real-time applications can be written in user space or in kernel space where less libraries are available then in user space and the licensing is GPL.

 

If you go easy with system calls the performance of a real-time application in user space is similar to the one in kernel space and you have access to many more libraries. Following a dual kernel approach you might be able to use the best of both worlds by moving deterministic applications into the real-time kernel domain at the cost of throughput and the non real-time stuff into user space at the cost of determinism. 

 

One of the biggest challenges with dual kernel implementations is that they will most likely never go into the GNU/Linux mainline kernel.  It's a huge effort for the maintainer of a dual-kernel solutions to keep up with the fast paced GNU/Linux kernel release cycle, which happens approximately every 2 months.

 

On the other hand it's possible to fix mainline latency issues which would not go into mainline and it's possible to provide a solution compatible with many different kernel versions. Xenomai 2.5.0 for example works with kernels from 2.4.25 up to 2.6.34+.

 

What will the future bring for PREEMPT-RT?

Currently it's mainly used on mainstream processors and multiprocessor systems where the performance you get is comparable with dual-kernel solutions. One of the reasons for this is that dual-kernel solutions utilize naïve locking schemes which are fast, but do not scale well to multiprocessor systems.

 

The fact that you need a recent glibc with priority inheritance enabled is no problem for those kind of platforms. Initially it will be used for “not so hard” real-time systems, but there is definitely potential and with the proper kernel configuration it is very usable. Please note that it might be tricky for the novice to come up with a “proper” kernel configuration.

 

What will the future bring for dual-kernel?

There are no user space dependencies. That's why besides mainstream processors also machines can be supported which do not have stable mainline real-time support and architectures which are not mainline yet. What I mean here are low end architectures which run for example uClinux on Blackfin and Nios2. As already mentioned above a migration path to PREEMPT-RT will be provided.

 

Conclusion

Real-time together with GNU/Linux seems to be on the rise, but there is no “one-fits-it-all” solution to bring real-time capabilities to it.  The reason is that there is no silver bullet to make something as big and complex as GNU/Linux 100% real-time aware since this is extremely costly in terms of maintenance.

 

Just keep in mind that, as noted above,  one needs to keep up with the fast development cycle of 2 months practiced by the GNU/Linux kernel community.  Remember what I mentioned at the beginning? ”

 

A real-time system will pass a specified test suite.[2]” No matter what solution you want to try you should come up with a suitable test suite and it's not trivial to do this. Especially on a low end platform when you already stress the capabilities of it you need to be very specific about your target application and you will need to invest more care to come up with a test suite.

 

Looking into my crystal balls it seems that in the future it will be pretty straight forward to switch between PREEMPT_RT and dual kernel solutions so you will be able to pick what fits best your application needs.

 

(Robert Berger is Embedded Software Specialist at Reliable Embedded Systems. He is also project manager for the Linux Driver Project, IEEE lecturer for professional activities, speaker at various events on embedded systems and moderates various “Embedded Systems Professionals” forums all over the world wide web. His specialties are training and consulting in real-time systems as well as Embedded GNU/Linux. )

 

References:

[1] Embedded Market Study 2010 - http://www.techonline.com/learning/webinar/224000228

[2] http://www.rdrop.com/users/paulmck/realtime/paper/RTvsRF.2009.09.30b.pdf

[3] Beautiful Code - O'Reilly Media, June 2007, ISBN: 978-0-596-51004-6

[4] documentation of GNU/Linux kernel configuration

http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=kernel/Kconfig.preempt;h=bf987b95b3560fbd0a7d8a820335100a55e1d105;hb=master

http://www.kernel.org/pub/linux/kernel/projects/rt/patch-2.6.33.4-rt20.bz2

[5] RTAI https://www.rtai.org/

[6] Xenomai http://www.xenomai.org

 


< Previous
Page 1 of 2
Next >

Loading comments...

Parts Search Datasheets.com

KNOWLEDGE CENTER