Approaches to realtime Linux

Posted Oct 12, 2004 19:29 UTC (Tue) by karim (subscriber, #114)
Parent article: Approaches to realtime Linux

There are a few things that need to be pointed out:

1- I'm not sure what is meant by "kernel-mode" code, but hard-rt deterministic tasks in RTAI DO NOT need be written as kernel modules. In fact, such tasks can be written as normal shell applications that use a special RTAI syscall vector to access RTAI services, including morphing from normal Linux processes into RTAI-scheduled tasks, and hence obtaining deterministic scheduling.

2- To put Philippe's words in laymen's terms, the aim of RTAI/fusion is to allow normal Linux processes to be serviced by RTAI transparently without requiring the use of any special API. To this end, normal Linux application calls are transparently "redirected" to RTAI using the Adeos nanokernel. It must be said that while there are a few system calls already successfully diverted in this way, nanosleep() being an example, this is still a work in progress. The ultimate goal being to allow those tasks that use time-sensitive calls to obtain the performance they would obtain had they been running on a real hard-rt RTOS. Of course there are calls that cannot be "hardened". Needless to say that an open() or a read() on a file located in an ext3 partition is unlikely to be deterministic any time soon.

Personally, I believe that this approach to real-time is much more sane than threading the interrupt handlers and introducing yet another level of locks. The fact of the matter is that if we have hard-rt like that, we don't need the threading of int handlers and the likes. But if we have threaded int handlers and co., we still need hard-rt because reducing latency doesn't provide deterministic response times.

NOTE: deterministic hard-rt is not about speed, it's about determinism. While Ingo's work is great at reducing latency, it cannot guarantee response times regardless of the load, kernel configuration, and driver set. RTAI/fusion, and the Adeos interrupt pipeline on a smaller scale, can provide such guarantees.

Karim Yaghmour

Approaches to realtime Linux

Posted Oct 12, 2004 22:08 UTC (Tue) by simlo (guest, #10866) [Link] (4 responses)

Now due to this splindid article here at LWN I downloaded the latests version of RTAI and started to look at it. If it lives up to it's promises it is really great!

However, isn't Adeos/RTAI adding just an extra level of locking just as MontaVista's patch? And on top of that an extra scheduler is added!?

RTAI does sound like a more expensive solution to me. If the goal was to seperate the real time threads and the none real time threads having two different schedulers is a splindid idea. But RTAI want to make it look the same towards the programmer. I am afraid the coder will make the mitake of calling Linux system calls and break the real time behaviour of the system.

Making all these system calls unavailable from real time part would make more sense - and could justify having two scheduleres on the system. But if you want to make the systems look the same it sounds more like a temporarely solution.

Another problem is device drivers: You can't use the device drivers from normal Linux in you real time subsystem (I briefly looked at the RT-net project who have made seperate device drivers). With the idea of making Linux itself real time you can - but you might have to rewrite some to make them perform better wrt. latencies and prioritising access.

Approaches to realtime Linux

Posted Oct 14, 2004 5:02 UTC (Thu) by karim (subscriber, #114) [Link] (3 responses)

Where the line is drawn between what is "visible" and what isn't for hard-rt processes can be configurable. That's not a problem.

What is a problem is introducing subtilities in the kernel's behavior that are so convoluted as to be too complex for the majority of driver and applications writers as it is. For the past five years I have been the maintainer of the Linux Trace Toolkit. For having done that work, I can tell you that only a marginal number of programmers actually really understand how the kernel operates, and how its operation is infuenced by or influences that of user-space applications and drivers. Just last July I was speaking with Jim Gettys at the OLS and he told me how he'd love to see something as LTT integrated into the kernel because most developers out there simply have no idea what they are doing. Not because they're careless or because they don't want to know, but because their expertise is elsewhere, and they shouldn't be expected to know that much about the kernel's behavior.

This is very relevant to the current debate. The fact of the matter is that the RTAI/fusion development model is much easier to work with because the traditional developers do not need to be exposed to an API that is unlikely to be of use to them (and if the API is there, they will use it; not because they are irresponsible, but because as carefull programmers they will try to give the best out of the kernel for their application), and because those who need it get all they need from a very targeted set of services. Again, as I said earlier, making Linux respond faster does NOT solve the problem of providing deterministic hard-rt, but providing deterministic hard-rt does allow Linux to respond faster.

As for drivers, then yes real-time drivers are different from normal non-rt drivers. There is absolutely no way that all Linux drivers will become suited for hard-rt system just by redefining a few macros here and there. Hard-rt drivers require a hard-rt mindset.

If all this is about making "multi-media" respond better in Linux, then the argument can easily be made that such critical components of multi-media system ought to be deterministic hard-rt anyway. Such multi-media applications can successfully use the services of Adeos and RTAI/fusion, real hard-rt applications can't use the "better latency" schemes. Why settle for less?

Approaches to realtime Linux

Posted Oct 14, 2004 9:54 UTC (Thu) by simlo (guest, #10866) [Link] (2 responses)

(I have written some more comments under the recent article about MontaVistas's patch http://lwn.net/Articles/106011/.)

I know a bit about real-time programing on VxWorks and only a little about the Linux internals.

For performance on a normal time-sharing system it isn't a good idea to replace spinlocks with mutexes. A spinlock will perform much better than a mutex but will effectively raise the locking thread to maximum priority. Similarly, a system will perform better if interrupt-handlers are executed in interrupt context right away instead of being deferred to tasks but again interrupt context is the highest priority. I thus think it should be configureable wether a subsystem uses spinlocks or mutexes and wether the drivers you have included should be run in interrupt or deferred.

A way I could see it done is to make a macro system such that the average driver developer should do something like "GENERIC_LOCK_TYPE(CONFIG_MY_SUBSYSTEM_LOCKTYPE) lock;" instead of "spinlock_t lock;" In the configurator there should be an advanced section where you can change the new macroes away from the default . Many of them should be set such the type will become a spinlock. The configuarator should ofcourse also check for dependencies: If a lock can be taken from interrupt you have to use spinlock_t.

Similarly when you install an interrupt: It should send configureable parameter saying the wether it should run in interrupt or if not, at what priority. Again the configurator should make sure that if interrupt context is choosen the eventual lock-types must be spinlock.

This would in fact make driver development easier: You just pick that you always defer your interrupt handler to a thread and you always lock your subsystem with a mutex. Then you don't have to worry about what you can or not can do in interrupt context and while holding a spinlock. For the average coder this is the easiest approach.

All these extra parameters should be hidden for the average build-your-own kernel user but the real-time developers have to make sure that these parameters are set correctly for the specific system. I.e. all locks which can be hold for more than the accepted latency time must be set to be mutexes, but locks hold for times shorter than the accepted latency are better off being spinlocks.

I suggest the following seperation: Linux should be coded with these macroes instead of having everything always being spinlocks. In all places where spinlocks are known to be unavoidable - I guess that is really only in the very core part of the system - the spinlock must not be held for more than a few, bound number instructions. Linus's official tree should not be tested for other than the default settings. (Some of the drivers you find in Linus' tree haven't been tested either so there is nothing fundamentally new in such a policy.)

It is up to companies like MontaVista to test how you can change the various parameters and they can earn their living by selling that knowledge. It is also their job to check that the various subsystems behave nicely wrt. locking. Forinstance, if somebody wants to make a small real-time application using say a CAN device, MontaVista can then help them to verify that the specific CAN driver in question is "real-time", i.e. can't hold it's lock and thus block the real-time application for a non-deterministic amount of time. The real-time application can't ofcourse call directly into the IP stack or the filesystem or even allocate memory runtime, but will have to defer such operations to other threads. As long as all these subsystems don't spinlock for "too long" but can safely be configured to use mutexes you are in the clear.

It also MontaVista's job to tell their customer which drivers and subsystems are cleared with respect to holding spinlocks for "too long" and thus safely can be included in the kernel. The patches fixing such systems so they can be configured to use mutexes instead should be accepted into the main tree. Also patches to making execution times deterministic in various subsystem should be accepted such that these subsystems can be used in real-time applications.

So basicly I think Igno Molnar's approach is good. He just have to make it configureable. There is still way to go before you can make any real-time application at all but I don't think the path is blocked unless the main kernel developers is talked into blocking such a development. Making various subsystems be directly useable from real-time application will take a very long time making them stop interfering with real-time threads is doable with realtively non-intrusive patches.

Approaches to realtime Linux

Posted Oct 15, 2004 1:35 UTC (Fri) by karim (subscriber, #114) [Link] (1 responses)

The main reason I don't like RTAI/Fusion is that you have to make special drivers for it. If the real-time is included in the kernel you would "only" have to review the drivers and subsystems you want to call directly from you real-time threads and check their behaviour wrt. real-time. The obligation of the rest of the system is that it only holds spinlocks for a very short time and otherwise use mutexes as locks.

The point is as I made it before: for many developers, including driver developers, the kernel's behavior is not entirely clear. Add a new API and people will use it, and it will find its way into "normal" Linux drivers. And once it's everywhere we'll still be at square one in regards to finding who's influencing the latency ... The solution to this problem is to provide a very basic API that provides hard-rt while not being as simple to use as just yet another locking scheme. I believe the Adeos interrupt pipeline does this quite well for the reasons I have enumerated elsewhere, and it changes nothing to kernel's current behavior.

It is up to companies like MontaVista to test how you can change the various parameters and they can earn their living by selling that knowledge. It is also their job to check that the various subsystems behave nicely wrt. locking. Forinstance, if somebod...

Sorry, the Linux community is not about depending on any distro. The fact of the matter is that whatever new feature finds itself in the kernel out to be accessible to anyone out there who cares about that type of functionality, regardless of whether he uses Debian, MV, or if he/she builds his own from scratch. Notice that, as Jonathan points out, the existing minimal preemption functionality that's already there has not yet been adopted by all kernel developers. Certainly trying to sell this new preemption on steriods by making the case that distros will audit the kernel for their clients is likely to be received coldly.

Approaches to realtime Linux

Posted Oct 15, 2004 9:04 UTC (Fri) by simlo (guest, #10866) [Link]

Add a new API and people will use it, and it will find its way into "normal" Linux drivers.

What new API? To be honest I think there are already too many lock-APIs in the kernel and weird kind of rules of what kind of locks should be used where. What is needed is actually a cleanup such the developer only sees one API and a generic method for locking. The specific kind of lock should be set at configuration time. The developer has to worry about is to avoid deadlocks no matter what kind of locks is used, but nothing more really. By making interrupt handlers run in threads by default it will make it a easier for the driver developer as he don't have to worry about the special rules of interrupt context.

Another of my points is that there is no "one size fits all" solution. To make a real-time system you have to configure stuff for your specific application. Thus the kernel developer should not be giving a lot of new APIs and options. He shouldn't forinstance pick at what priority his interrupt has to be performed at. He should make it such that it will work no matter what the priority is - and maybe also such it works even if it runs in interrupt context still but that could be too high a demand on him.

Sorry, the Linux community is not about depending on any distro. The fact of the matter is that whatever new feature finds itself in the kernel out to be accessible to anyone out there who cares about that type of functionality, regardless of whether he uses Debian, MV, or if he/she builds his own from scratch. Notice that, as Jonathan points out, the existing minimal preemption functionality that's already there has not yet been adopted by all kernel developers. Certainly trying to sell this new preemption on steriods by making the case that distros will audit the kernel for their clients is likely to be received coldly.

There is something called experimental drivers. I tried out the ArcNet driver on 2.6.8.1. It called a NULL'ed function pointers. Not testet at all. Somebody has to test stuff - and Linus can't verify that everything have been tested in every configuration. One could say: "remove the ArcNet driver", but that would only make it much harder to get anyone to fix it. And even after I fixed it it still didn't work with SMP and preemption. I.e. you have configurations in the default kernel which simply does not work. You need someone to veryfy your configuration. That somebody can be yourself or you can buy help from a company.

Another examble is the PPC board sitting next to me on the table. Can I make Linux run it? Yes, I can, but I need an expert for it. MontaVista and other companies offers to sell be that expertice. I can buy that or I can spend approximately 2 weeks to figure it out myself.

All I say to the kernel community is: Make these things configurable, but allow the default kernel to have clauses with "If you pick these options don't expect your kernel to be stable". Let companies like MontaVista make a living of pushing into these areas. The most important thing is to avoid code forks which will make it a mess for everybody in the long run. On the other hand make the changes to the actual kernel you build from main tree minimal by make things configurable compile time.

Approaches to realtime Linux

Posted Oct 13, 2004 22:45 UTC (Wed) by bluefoxicy (guest, #25366) [Link] (1 responses)

NOTE: deterministic hard-rt is not about speed, it's about determinism. While Ingo's work is great at reducing latency, it cannot guarantee response times regardless of the load, kernel configuration, and driver set.

-- Karim Yaghmour

Purpose of the Project
The purpose of this effort is to to further reduce interrupt latency and to dramatically reduce task preemption latency in the 2.6 kernel series. Our broad objective is to achieve preemption latency bounded by the worst case IRQ disable.

-- http://source.mvista.com/linux_2_6_RT.html

Does this qualify? It's "bounded" yes? The bounding would qualify as true real-time, and the reduction of latency beyond that bound would just be a happy responsiveness bonus. Am I right? If not, please show err.

Approaches to realtime Linux

Posted Oct 14, 2004 5:31 UTC (Thu) by karim (subscriber, #114) [Link]

Have you kept a count of the number of "reduce" and "broad objective" in that phrase?

Deterministic hard-rt is not about broad objectives or reducing latencies, it's about making guarantees. As it stands, MV's PR relies on slides that show graphs with maximum interrupt disable times, whereupon they can tell crowds: "Here, we have a hard-rt system, it's maximum latency is such as such and measured by our tools." That's just crap because no matter how large a sample is used for measurement (or how long the measurement session lasts) determinism is not about spikes in a graph, it's about mathemathically/algorithmically-demonstrable time-bound operation regardless of load and driver set, and reducing the latency by threading interrupts and introducing new locking primitives does not change the problem: The Linux kernel was never architectured to be a hard-rt deterministic kernel and the drivers shipped and the applications that run on it have never been meant to provide such behavior.

I've said this elsewhere, there is no path of incremental patches that can be applied to the kernel that will make it magically become deterministic. The kernel is meant to provide a best-case scenario for all the software it interacts with: drivers and applications alike. Deterministic hard-rt is all about making guarantees, both in terms of time and in terms of resources.

The greater question that beholds kernel developers is: can the Linux kernel be made to exhibit deterministic hard-real-time bevahior while keeping it fit for the development of mainstream drivers and applications?

Don't get me wrong, reducing latency is an extremely worthy goal, and I encourage any effort in that direction. However, as much as I trust the Linux kernel development community's inventivness and adaptibility to constraints, as much as I believe that providing the type of services required for applications with extreme time-dependencies is a goal that is not reconciliable with making the Linux kernel an inviting platform for driver and application developers.

Personally, I believe that the preemptability feature, which in reality is not yet actually used by most users out there for many reasons including stability, should be dropped altogether in favor of a simple infrastructure that allows time-sensitive applications to get what they need in a Linux environment: deterministic access to outside events. I believe the Adeos interrupt pipeline is the least intrusive and the most effective way of achieving this. It is a very small patch, it provides deterministic hard-rt, it can be built upon to provide a wide-range of services (RTAI/fusion being an example), and from the API useability point of view, it clearly stands out from the rest of the kernel API as being targeted for extreme outside-event-timing-responsiveness-sensitivity and is therefore much less likely to be used by accident by a driver or application developer.