Getting real (time) about embedded GNU/Linux - Embedded.com

Getting real (time) about embedded GNU/Linux

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

What is real-time?

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

Coming back to real-time versus real fast – In case of anaircraft navigation system deadlines are in the tens of milliseconds, while foran 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 stillno universal methodology to create real-time systems and that's why in reallife real-time is defined as follows:”A real-time system will pass a specifiedtest suite.[2]” Let's stick to those wise words of Paul E. McKenny for the timebeing.

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

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

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

So although it is possible to make the scheduler behavedeterministic like one would expect from a real-time operating system you cannot assume that all GNU/Linux drives are written with real-time in mind aswell.

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

Why would you addreal-time capabilities to GNU/Linux?

If you are after a real-time operating system which behavesdeterministic with all possible configuration options and including allpossible 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 beGNU/Linux.

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

Adding real-time to aplain vanilla GNU/Linux kernel

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

What's this all thisPREEMPT-RT stuff about? RT comes from real-time, so let's first see what'sthe “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 interruptwill come along and interrupt/preempt whatever runs, the scheduler will beinvoked and the lower priority process will be de-scheduled while the higherpriority process will be scheduled.

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

In case where we don't have a preemptive operating systembut a cooperative one process one would need to give up the CPU to let processtwo 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 inGNU/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 upto CONFIG_PREEMPT_RT which enablesfull blown preemption.

Please note that from none to PREEMPT_RT the latency versusthroughput trade off can be observed. Throughput decreases while determinismincreases and vice versa.

The degrees ofdeterminism available for GNU/Linux

1) PREEMPT_NONE . That'sthe default scheduler of a vanilla GNU/Linux kernel. It's geared towardsmaximum raw processing power and throughput. Every process gets it's fair shareofthe CPU as it istypical for a classical Unix multi-userenvironment. By default processes can not be preempted while they executesystem calls and since, among other things, the timing behavior of some kernelservices is non deterministic the whole thing is not deterministic as well.

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

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

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

This option further reduces the latency of the kernel bymaking all kernel code that is executing in a critical sectionpreemptible.The latency is furtherreduced at the cost of slightly lower throughput and a slight runtime overheadto kernel code.[4]

4) PREEMPT_RT[GR-2]. The goal of the real-time preemption patch is to make fixed priority preemptivescheduling (i.e. POSIX SCHED_FIFO and SCHED_RR classes) as close as possible totheir ideal behavior and all this with no impact for users/processes notinterested 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'smaintained by Ingo Molnar and Tom Gleixner and the design is fully preemptibleand deterministic with respect to scheduling, interrupt handling and highresolution timers. It supports priority inheritance and preemptible hard- andsoft interrupts.

It might be interesting to note that PREEEMPT_RT is drivenby embedded,industrial and enterprisecommunities, which means that determinism is slowly getting more important thanthroughput for some applications even for the enterprise people.

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

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

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

Figure 3. [GR-3] DUAL KERNEL

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

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

Funny things happening in the non real-time domain havepotentially only minimal impact on the real-time domain. Real-time applicationscan be written in user space or in kernel space where less libraries areavailable then in user space and the licensing is GPL.

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

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

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

What will the futurebring for PREEMPT-RT?

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

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

What will the futurebring for dual-kernel?

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

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 toit.The reason is that there is nosilver bullet to make something as big and complex as GNU/Linux 100% real-timeaware since this is extremely costly in terms of maintenance.

Just keep in mind that, as noted above,one needs to keep up with the fastdevelopment 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]” Nomatter what solution you want to try you should come up with a suitable testsuite and it's not trivial to do this. Especially on a low end platform whenyou already stress the capabilities of it you need to be very specific aboutyour target application and you will need to invest more care to come up with atest suite.

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

(RobertBerger is Embedded Software Specialist at Reliable Embedded Systems. He is also project manager for the Linux Driver Project, IEEE lecturer for professionalactivities, speaker at various events on embedded systems and moderates various“Embedded Systems Professionals” forums all over the world wide web. Hisspecialties are training and consulting in real-time systems as well asEmbedded 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] BeautifulCode – 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

The degrees ofdeterminism available for GNU/Linux

1) PREEMPT_NONE . That'sthe default scheduler of a vanilla GNU/Linux kernel. It's geared towardsmaximum raw processing power and throughput. Every process gets it's fair shareofthe CPU as it istypical for a classical Unix multi-userenvironment. By default processes can not be preempted while they executesystem calls and since, among other things, the timing behavior of some kernelservices is non deterministic the whole thing is not deterministic as well.

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

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

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

This option further reduces the latency of the kernel bymaking all kernel code that is executing in a critical sectionpreemptible.The latency is furtherreduced at the cost of slightly lower throughput and a slight runtime overheadto kernel code.[4]

The goal of the real-time preemption patch is to make fixed priority preemptivescheduling (i.e. POSIX SCHED_FIFO and SCHED_RR classes) as close as possible totheir ideal behavior and all this with no impact for users/processes notinterested 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'smaintained by Ingo Molnar and Tom Gleixner and the design is fully preemptibleand deterministic with respect to scheduling, interrupt handling and highresolution timers. It supports priority inheritance and preemptible hard- andsoft interrupts.

It might be interesting to note that PREEEMPT_RT is drivenby embedded,industrial and enterprisecommunities, which means that determinism is slowly getting more important thanthroughput for some applications even for the enterprise people.

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

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

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

Figure 3. [GR-3] DUAL KERNEL

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

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

Funny things happening in the non real-time domain havepotentially only minimal impact on the real-time domain. Real-time applicationscan be written in user space or in kernel space where less libraries areavailable then in user space and the licensing is GPL.

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

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

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

What will the futurebring for PREEMPT-RT?

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

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

What will the futurebring for dual-kernel?

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

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 toit.The reason is that there is nosilver bullet to make something as big and complex as GNU/Linux 100% real-timeaware since this is extremely costly in terms of maintenance.

Just keep in mind that, as noted above,one needs to keep up with the fastdevelopment 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]” Nomatter what solution you want to try you should come up with a suitable testsuite and it's not trivial to do this. Especially on a low end platform whenyou already stress the capabilities of it you need to be very specific aboutyour target application and you will need to invest more care to come up with atest suite.

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

(RobertBerger is Embedded Software Specialist at> Reliable Embedded Systems. He is also project manager for the Linux Driver Project, IEEE lecturer for professionalactivities, speaker at various events on embedded systems and moderates various“Embedded Systems Professionals” forums all over the world wide web. Hisspecialties are training and consulting in real-time systems as well asEmbedded 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] BeautifulCode – 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


Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.