Adeos nanokernel for Linux kernel

We have released the initial implementation of the Adeos nanokernel. The following is a complete description of its background, its implementation, its API, and its potential uses. Please also see the press release (http://www.freesoftware.fsf.org/adeos/pr-2002-06-03.en.txt)
and the project's workspace (http://freesoftware.fsf.org/projects/adeos/).
The Adeos code is distributed under the GNU GPL.

The Adeos nanokernel is based on research and publications made in the early '90s on the subject of nanokernels. Our basic method was to reverse the approach described in most of the papers on the subject. Instead of first building the nanokernel and then building the client OSes, we started from a live and known-to-be-functional OS, Linux, and inserted a nanokernel beneath it. Starting from Adeos, other client OSes can now be put side-by-side with the Linux kernel.

To this end, Adeos enables multiple domains to exist simultaneously on the same hardware. None of these domains see each other, but all of them see Adeos. A domain is most probably a complete OS, but there is no assumption being made regarding the sophistication of what's in a domain.

To share the hardware among the different OSes, Adeos implements an interrupt pipeline (ipipe). Every OS domain has an entry in the ipipe. Each interrupt that comes in the ipipe is passed on to every domain in the ipipe. Instead of disabling/enabling interrupts, each domain in the pipeline only needs to stall/unstall his pipeline stage. If an ipipe stage is stalled, then the interrupts do not progress in the ipipe until that stage has been unstalled. Each stage of the ipipe can, of course, decide to do a number of things with an interrupt. Among other things, it can decide that it's the last recipient of the interrupt. In that case, the ipipe does not propagate the interrupt to the rest of the domains in the ipipe.

Regardless of the operations being done in the ipipe, the Adeos code does __not__ play with the interrupt masks. The only case where the hardware masks are altered is during the addition/removal of a domain from the ipipe. This also means that no OS is allowed to use the real hardware cli/sti. But this is OK, since the stall/unstall calls achieve the same functionality.

Our approach is based on the following papers (links to these papers are provided at the bottom of this message):
[1] D. Probert, J. Bruno, and M. Karzaorman. "Space: a new approach to operating system abstraction." In: International Workshop on Object Orientation in Operating Systems, pages 133-137, October 1991.
[2] D. Probert, J. Bruno. "Building fundamentally extensible application- specific operating systems in Space", March 1995.
[3] D. Cheriton, K. Duda. "A caching model of operating system kernel functionality". In: Proc. Symp. on Operating Systems Design and Implementation, pages 179-194, Monterey CA (USA), 1994.
[4] D. Engler, M. Kaashoek, and J. O'Toole Jr. "Exokernel: an operating system architecture for application-specific resource management", December 1995.

If you don't want to go fetch the complete papers, here's a summary. The first 2 discuss the Space nanokernel, the 3rd discussed the cache nanokernel, and the last discusses exokernel.

The complete Adeos approach has been thoroughly documented in a whitepaper published more than a year ago entitled "Adaptive Domain Environment for Operating Systems" and available here: http://www.opersys.com/adeos
The current implementation is slightly different. Mainly, we do not implement the functionality to move Linux out of ring 0. Although of interest, this approach is not very portable.

Instead, our patch taps right into Linux's main source of control over the hardware, the interrupt dispatching code, and inserts an interrupt pipeline which can then serve all the nanokernel's clients, including Linux.

This is not a novelty in itself. Other OSes have been modified in such a way for a wide range of purposes. One of the most interesting examples is described by Stodolsky, Chen, and Bershad in a paper entitled "Fast Interrupt Priority Management in Operating System Kernels" published in 1993 as part of the Usenix Microkernels and Other Kernel Architectures Symposium. In that case, cli/sti were replaced by virtual cli/sti which did not modify the real interrupt mask in any way. Instead, interrupts were defered and delivered to the OS upon a call to the virtualized sti.

Mainly, this resulted in increased performance for the OS. Although we haven't done any measurements on Linux's interrupt handling performance with Adeos, our nanokernel includes by definition the code implementing the technique described in the abovementioned Stodolsky paper, which we use to redirect the hardware interrupt flow to the pipeline.

In terms of implementation, the Adeos' code is rather short since we focused on setting the foundations for sharing interrupts between domains. Here are the files we added:
kernel/adeos.c: Architecture-independent domain code. arch/i386/kernel/adeos.c: Architecture-dependent domain code. arch/i386/kernel/ipipe.c: Interrupt pipeline code. include/asm-i386/adeos.h: Arch-dependent Adeos header. include/linux/adeos.h: Main (arch-independent) Adeos header.

As you can see, only the i386 is currently supported. Nonetheless, most of the architecture-dependent code is easily portable to other architectures.

We also modified some files to tap into Linux interrupt dispatching (all the modifications are encapsulated in #ifdef CONFIG_ADEOS/#endif):

        kernel/ksyms.c
        arch/i386/kernel/apic.c
        arch/i386/kernel/entry.S
        arch/i386/kernel/i386_ksyms.c
        arch/i386/kernel/i8259.c
        arch/i386/kernel/irq.c
        arch/i386/kernel/smp.c
        arch/i386/kernel/time.c
        arch/i386/kernel/traps.c
        arch/i386/mm/fault.c
        include/asm-i386/keyboard.h
        include/asm-i386/system.h

We modified the idle task so it gives control back to Adeos in order for the ipipe to continue propagation:
arch/i386/kernel/process.c

We modified init/main.c to initialize Adeos very early in the startup.

Of course, we also added the appropriate makefile modifications and config options so that you can choose to enable/disable Adeos as part of the kernel build configuration.

Here is Adeos' public API:

int adeos_register_domain(adomain_t *adp, adattr_t *attr); Register a new domain using the properties defined in the attribute.

void adeos_unregister_domain(adomain_t *adp);
Remove "adp" domain.

void adeos_renice_domain(adomain_t *adp, int newpri); Change "adp"'s priority in the ipipe.

void adeos_suspend_domain(void);
This domain is done dealing with the current interrupt. This signals the ipipe to provide the interrupt to the next ipipe stage.

void adeos_virtualize_irq(unsigned irq, void (*handler)(void), int (*acknowledge)(unsigned));
Provide a handler and an acknowledgment function for "irq".

void adeos_control_irq(unsigned irq, unsigned clrmask, unsigned
setmask);
Change the current domain's handling mask for irq "irq". "clrmask" is applied first and then "setmask" is applied.

void adeos_stall_ipipe(void);
Stall the current domain's ipipe stage. Alternative to cli.

void adeos_unstall_ipipe(void);
Unstall the current domain's ipipe stage. Alternative to sti.

void adeos_restore_ipipe(unsigned x);
Restore the ipipe from its saved state. Alternative to __restore_flags() and local_irq_restore(). This is used with the following defines:
#define adeos_test_ipipe() \
test_bit(IPIPE_STALL_FLAG,&adp_current->status)
#define adeos_test_and_stall_ipipe() \
test_and_set_bit(IPIPE_STALL_FLAG,&adp_current->status)
Which replace __save_flags and local_irq_save(), respectively.

In Linux's case, adeos_register_domain() is called very early during system startup. set_intr_gate() in arch/i386/kernel/traps.c is then modified to call on adeos_virtualize_irq() so that Linux would tell the ipipe that it needs the irq passed to set_intr_gate().

To add your domain to the ipipe, you need to:
1) Register your domain with Adeos using adeos_register_domain()
2) Call adeos_virtualize_irq() for all the IRQs you wish to be notified about in the ipipe.

That's it. Provided you gave Adeos appropriate handlers in step #2, your interrupts will be delivered via the ipipe.

During runtime, you may change your position in the ipipe using adeos_renice_domain(). You may also stall/unstall the pipeline and change the ipipe's handling of the interrupts according to your needs.

We currently don't support SMP, but we do have APIC support on UP.

Here are some of the possible uses for Adeos (this list is far from complete):
1) Much like User-Mode Linux, it should now be possible to have 2 Linux kernels living side-by-side on the same hardware. In contrast to UML, this would not be 2 kernels one ontop of the other, but really side-by-side. Since Linux can be told at boot time to use only one portion of the available RAM, on a 128MB machine this would mean that the first could be made to use the 0-64MB space and the second would use the 64-128MB space. We realize that many modifications are required. Among other things, one of the 2 kernels will not need to conduct hardware initialization. Nevertheless, this possibility should be studied closer.

2) It follows from #1 that adding other kernels beside Linux should be feasible. BSD is a prime candidate, but it would also be nice to see what virtualizers such as VMWare and Plex86 could do with Adeos. Proprietary operating systems could potentially also be accomodated.

3) All the previous work that has been done on nanokernels should now be easily ported to Linux. Mainly, we would be very interested to hear about extensions to Adeos. Primarily, we have no mechanisms currently enabling multiple domains to share information. The papers mentioned earlier provide such mechanisms, but we'd like to see actual practical examples.

4) By incorporating Adeos into the main kernel tree (I know my inbox is probably going to fill up because of this one), kernel debuggers' main problem (tapping into the kernel's interrupts) is solved and it should then be possible to provide patchless kernel debuggers. They would then become loadable kernel modules.

5) Drivers who require absolute priority and dislike other kernel portions who use cli/sti can now create a domain of their own and place themselves before Linux in the ipipe. This provides a mechanism for the implementation of systems that can provide guaranteed realtime response.

Of course, we are interested in hearing about comments and suggestions you have about Adeos.

Best regards,

Philippe Gerum
Karim Yaghmour

----------------------------------------------------------------------
Links to papers:
1-
http://citeseer.nj.nec.com/probert91space.html
ftp://ftp.cs.ucsb.edu/pub/papers/space/iwooos91.ps.gz (not working)
http://www4.informatik.uni-erlangen.de/~tsthiel/Papers/Space-iwooos91.ps.gz

2-
http://www.cs.ucsb.edu/research/trcs/abstracts/1995-06.shtml
http://www4.informatik.uni-erlangen.de/~tsthiel/Papers/Space-trcs95-06.ps.gz

3-
http://citeseer.nj.nec.com/kenneth94caching.html
http://guir.cs.berkeley.edu/projects/osprelims/papers/cachmodel-OSkernel.ps.gz

4-
http://citeseer.nj.nec.com/engler95exokernel.html
ftp://ftp.cag.lcs.mit.edu/multiscale/exokernel.ps.Z
----------------------------------------------------------------------

Looks kindof cool in theory. Have you done any benchmarking on the performance hit on Linux kernel vs baseline? What is the software patent outlook for this approach look like?

-Erik

--
Erik B. Andersen http://codepoet-consulting.com/
--This message was written using 73% post-consumer electrons--

To me this looks definitely clear of the FMSLabs patent, since RT and non-RT live side by side, not on a master-slave relationship.

/alessandro

Philippe has done some preliminary testing with dbench/tbench and he got something like < 1%. Of course, more testing is required.

Alessandro's answer is to the point. Basically, grab the papers, the code and the patent and have a look for yourself, you will see that we're clear. Apart from having the kernels side-by-side, Adeos is based on classic early '90s nanokernel work. No secrets there.

Karim

===================================================
Karim Yaghmour
[email protected]
Embedded and Real-Time Linux Expert
===================================================

Congratulations! This looks beautiful. I really do think you've wiped out the intellectual property roadblock that's been holding Linux back from penetrating the control system space at the same rate as traditional IT. Not to mention that I can look forward to a sound system where I can be *sure* my mp3s won't skip.

In my opinion, this is fundamental progress for free (as in freedom) software.

Daniel

Not unless you're loading your entire MP3 into memory, mlocking it down, and handing it off to a hard RT process. And then your control of the playback of said song through a non-RT GUI could be arbitrarily coarse, depending on load.

 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

Thanks for biting :-)

First, these days it's no big deal to load an entire mp3 into memory.

Second, and of more interest to broadcasting industry professionals and the like, it's possible to write a real-time filesystem that bypasses all the normal non-realtime facilities of the operating system, and where the latency of every operation is bounded according to the amount of data transferred. Such a filesystem could use its own dedicated disk, or, more practically, the RTOS (or realtime subsystem) could operate the disk's block queue.

If I recall correctly, XFS makes an attempt to provide such realtime guarantees, or at least the Solaris version does. However, the operating system must be able to provide true realtime guarantees in order for the filesystem to provide them, and I doubt that the combination of XFS and Solaris can do that.

Daniel

Nope, it can't.

Just bear in mind that it's next to impossible to avoid throwing the baby out with the bathwater here. Ok, so you've got an RT kernel playing your MP3 alongside your UNIX system - how do you control it? How do you switch tracks? All the latency that you were struggling with in the player is still there in the user interface.

What you really want for an MP3 player is _not_ hard RT, what you want is very reliable low-latency. Which we can do without throwing away most of UNIX.

 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

I'm not sure that I, personally, am a realtime device anyway ;-)

In the context of an mp3 playback system, worrying about whether the controls are realtime seems a little excessive. But it's not too hard to do. Just allow the RTOS to take control of the input devices, or at least to insert itself ahead of the general purpose operating system in the interrupt pipeline.

As for a GUI with realtime response characteristics, that's more challenging, but it has been done. It's also less important I'd say. You can always fall back on dedicated hardware for the realtime display.

Such concerns become very practical matters when you get into the world of industrial control systems.

I think that depends on whether you are an audiophile or not. Or a broadcaster. If you're a broadcaster, how many mp3 skips will you tolerate a year? By way of analogy, if you're a network administrator, how many unplanned reboots will you tolerate a year, if you know that by merely changing the software, you will have none? There's something to be said for reliability that is *provable*.

And who said anything about throwing away most of Unix?

Daniel

Perhaps you've never been a DJ..

Of course, but then it's no longer part of a general-purpose operating system. Baby, bathwater. It's easier to tape a Rio onto the side of your machine.

If the number is zero, you can't use the facilities of a non-RT operating system for anything except (possibly lossily) monitoring the output of such a system. If you feed an RT system with data or control from a non-RT system, it becomes a non-RT system. If you try to losslessly queue output from an RT system to a non-RT system, it becomes a non-RT system.

You did, by insisting on absolutes. Hard realtime places many restrictions on what you can do - it's like having your entire system inside an interrupt context or a signal handler.

 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

Good point. Quake deathmatch is another place where you worry a lot about your controls being realtime.

Not at all. You can still run a web browser and a download in parallel with the realtime process, that's the beauty of it. As for the realtime gui, if you're determined to build one it doesn't have to be the whole desktop. It can just be one window, much like a video overlay.

I'm don't see any fundamental roadblock here.

That doesn't follow. I ought to be able to do an apt-get dist-upgrade without the realtime application ever skipping a beat, just to pick one example off the top of the pile.

If it hurts, don't do that. I thought we'd invoked the concept of a realtime filesystem? You can log to that, and you ought to be able to run queries against it in non-realtime. You don't have to suck the entire world into your realtime application.

This is precisely the sort of design limitation we're tearing down with these hybrid realtime/non-realtime systems. Your mistake is assuming that every form of communication between the two has to be tightly coupled. It's true that the entire realtime system has to operate within the strictures of some formalism, but that's what formalisms are for. It's no more shocking a limitation than the fact that regular users aren't allowed to do all the things the superuser can do.

--
Daniel

No, the mistake is assuming that loosely coupling UNIX to RT lets you leverage much of anything from UNIX. The whole attraction of a hybrid system is the idea of building an app in a "normal" operating system on top of a realtime layer because it's much easier to code for normal operating system than realtime. Normal operating systems lets you have real stacks and memory management and paging and fast filesystems and TCP and load >= 1.

And your MP3-player example is a great one of where you don't get much out of it. You have to rewrite _everything_ to run in the RT space. Yes, doable, but how is it better from a developer perspective than the duct-taped RIO approach? Tape it inside the box with USB (there's your shared filesystem) if that makes you happier.

 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

- Compiler
- Debugger
- Editor
- GUI
- IPC
- Any program that doesn't require realtime response
- Memory protection
- Physical hardware can be shared
- I could go on...

You're fighting an uphill battle here. The question of whether users want hybrid systems or not has already been answered: it's a definite yes. At this point we're only discussing how best to do it. I hope.

That's something of an exaggeration. In fact, starting with an audio application that was well-factored in the first place, it would not be necessary to do such grunt work as breaking out the gui. A lot of the work would consist of removing cruft that was only put in there in the first place only to deal with problems inherent in trying to make a non-realtime system act as though it were realtime. It's always a pleasure to heave such dung out of an application.

If we do this properly, the first big thing you'll notice is that the latency between operating the playback volume control and the change taking effect disappears. You don't have to keep a 1,000 ms buffer any more, in an attempt to deal with potential scheduling delays.[1]

That alone is worth the price of admission.

I don't want a RIO ducttaped to the inside of my computer, and anyway, it hasn't got a fraction of the memory my personal system has. I'd consider that an inferior solution.

I already have all the hardware I need to run a combined realtime/non-realtime system right now, ready to go. You're arguing I should go out and get more, and even suggesting that a duct-taped solution is somehow superior to actually thinking the problem through and solving it properly in software. I believe we agree the software-only solution is possible, correct? It's not even particularly hard, as I see it, thanks to the way Karim has factored the problem.

[1] Assuming we either preload the mp3 or implement a realtime filesystem, the former being nothing more than a quick hack, and the latter being 'hard', but hey, if it's not hard it's not interesting, right?

Daniel

So... an RT .mp3 player task that receives asynchronous signals from a non-RT .mp3 player GUI front-end? So, we assume that the .mp3 data gets sent from the non-RT file system to the RT task (via the non-RT GUI front-end) in its entirety before it begins playing...

Other than as a play RT project, seems like a waste of effort to me... :-)

The result will be that your compiler/debugger/editor/etc. will have limited access to the CPU, and will therefore likely run slower. (The rest of the processes effectively run as "idle tasks")

mark

[email protected]/[email protected]/[email protected] __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

Your opinion is noted, however it's also noted that you didn't support it in any way.

Also, it appears you didn't read the post you responded to. Two alternatives were presented:

1) Load the whole mp3 into memory before playing it
2) Implement a filesystem with realtime response

Both approaches have their uses. The second is the one I'm interested in, if that isn't already obvious. The first is just a quick hack that will give you guaranteed-skipless audio playback, something that Linux is currently unable to do.

No no no. The compiler/debugger run under the general purpose OS, and only a stub of the debugger runs on the RTOS.

Daniel

Neither have you, at least aside from hand-waving. I've actually built a bunch of systems that were originally spec'ed to be hybrids. Wouldn't be surprised if Mark had too, given his Nortel address.

And that alternative sucks. Think scalability.

And your shared fs alternative sucks. Think abysmal disk throughput for the rest of the system. Think starvation. Think all the reasons we've been trying to clean up the elevator code times ten. And that's just for the device queue, never mind the deadlock avoidance problems. See "priority inversion".

Umm, neither can your CD player. But if you take the proper precautions to avoid it being jostled, clean your discs, and give it decent buffering, it will be more than satisfactory. Can we bring Linux up to the same standard with the pre-empt and low-latency approaches? Yes. Is this a better approach than grafting quixotic kernels onto the side of the box? Definitely.

There is a place for hard realtime. But desktop MP3 playing is not it.

 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

Err. Skipless. Need I say more?

I hope that's not an invitation to a resume war. I built, or was instrumental in building, a system that not only replaced a number of horribly expensive motor regulators with software running closed loops over a realtime network, but ran a gui, database, report generator, ladder logic, sensor inputs and two-way network interface over serial lines, all on a 486. So I know what it's like to do it all with a realtime system. I'd rather not, thankyou, not the parts that don't need it.

I'll leave that to people who appreciate quality mp3 playback to decide.

What kind of argument is that? It sounds like: because our current block interface sucks, all block interfaces suck, and always will. On the contrary, I believe our current interface sucks precisely because it is not built according to sound principles of realtime design.

You seem to be all in favor of giving up before you start. That's not how Linux was built.

No you can't. Grief.

Daniel

No, the above is a theoretical argument about how optimizing disk access and locking works that's in no way specific to Linux. Remember, hard RT is trades throughput for latency guarantees. Worst case for this is devices queues for disks. Go through the thought experiment of what happens when an RT task and a !RT task interleave disk access. Worse, what happens when they're creating files (and all the locking that entails) in the same directory.

 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

This is a mantra I keep hearing repeated, and it is a myth. The correct version goes more like: "in a realtime system, meeting deadlines is more important than efficiency". That doesn't mean you can't have both, and please see my earlier description of the realtime system c/w gui, running on a 486. Oh wait, it also ran on a 386. 16 Mhz.

I mentioned somewhere that the realtime filesystem would get its own volume. That's a big help, because it means that the entire filesystem can run in the RTOS, and we only have to worry about the block queue, which is an interesting and tractable problem from the realtime point of view. Obviously, we want the RTOS to operate the block queue, and yes, we want it to be efficient.

Our current block queue design would benefit a lot from the kind of thinking that would be required to make it realtime.

Daniel

You know that spinning disks do some recalibrations?

Whatever marketing tries to imply with "realtime volumes" - the technology only tries to make better promises (think of AV disks for better sustained rate).

LynxOS (now LynuxWorks) has some patents for priority based IO. And yes, I know about "resource kernels" and alike.
But that does not count for spinning disks: they are *not* predictable. And think about the shared bus like PCI - out of *hard realtime* when not talking about worst cases in ranges of seconds.

It's my impression that some do thermal recalibration and some don't:

http://www.pctechguide.com/04disks.htm
"recalibration"

This article indicates that disks with servo information encoded on the platter don't need to do thermal recalibration, thus being better suited to multimedia playback. Which makes sense to me.

Typically, hard disk specs include 'full stroke seek, maximum', for which 28 ms seems to be a typical number for 7200 RPM drives. If a particular drive ever performs outside the claimed maximum then it's performing out of spec. I suppose that we would need to qualify disks, to see which fail to perform to spec, and I am sure there are some that do fail. That's the first thing I'd do if developing a realtime block driver: run random seeks on typical disks for a few days at a time and see what the maximum latency really is.

The need to turn in reliable performance for multimedia apps seems to have made thermal calibration a thing of the past, but thanks for raising the issue.

Oh, more of those one-click realtime patents ;-) Do you have any pointers?

The disk doesn't have to turn in 100% rock solid performance, it just has to perform within an envelope of latency and throughput. Again, I'm sure that some do and some don't, so it's a blacklist/whitelist problem.

video cards, which lock the bus for extended periods in order to turn in better benchmark numbers. This is another blacklist/whitelist problem. In general, the jitter introduced by the pci bus is going to be far below the 10 usec range or so required for very high performance realtime work, and way, way below what would be required for a realtime block driver.

Daniel

Ok, seems that I am a bit outdated (here) :-)

http://www.lynuxworks.com/products/whitepapers/patentedio.php3

In the upper right corner you can see the patent number. Try a search for patent on this side.

This doesn't have anything to do with realtime prioritization of a block driver. Anyway, I didn't go as far as looking at the claims, but from the description on the web page it looks pretty feeble. It seems to be concerned with management of priority of softirq handlers to avoid priority inversion, with a rather slipshod definition of priority inversion given on the page. I doubt RTAI has a lot to fear from this patent, especially as the owner has hitched its cart to the Linux horse, and likely realizes what a bad idea it is to apply cattle prods to said horse.

Daniel

I'm thinking along the lines of a 2Ghz P4 box performing skipless .mp3 playing, that is not able to compile the Linux kernel in anything less than 24 hours.

This is where this reasoning takes us. "It's skipless it must be better!"

mark

P.S. My .mp3 player doesn't skip when I perform heavy compiles. With
the low-latency patches, this record should only improve. Hammers are for nails.

[email protected]/[email protected]/[email protected] __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

So, you're worried that the realtime processing is going to suck performance? Don't worry about that. Really. Take a look at how Adeos works and add up the cycles consumed by the whole thing. It's insignificant.

Just handling the timer interrupt with an iret consumes more cycles by far than all the interrupt pipeline overhead. You're imagining inefficiency where there is none.

It's definitely better to be skipless, now we want to have our cake and eat it too. We can.

Daniel

I haven't actually (different side of the company). I've talked to a few people that have (in Nortel), and done a little research on the side.

The biggest peave I have against RT is that people think it is the solution to everything. The *idea* that somebody would want an RT .mp3 player for their designer desktop machine causes this feeling I have to be quite exaggerated. If I wanted to mock an RT-supporter I would have joked "why don't you write a .mp3 player in RT too?" and here I see it being presented as a valid application for RT.

RT is definately useful. This is especially true of any sort of dedicated hardware that must serve data at close to full capacity with almost zero chance of data loss or lag. (Such as telephone switches)

It isn't a toy. It is much harder to code an RT application, and the fact that hardware is running an RT application ensures that overall performance will suffer. The RT requirement is not a natural addition to an operating system such as Linux, which is why it is very effective to execute Linux as if it was a non-RT task.

I like the idea of Adeos, and nanokernels. I like the idea of RT, and I like the fact that the Open Source community is interested in all of these topics. It means that solutions such as VxWorks now have real competition, and they will be forced to make their large price tag purchase real value for customers, or customers will shop elsewhere.

Just... an .mp3 player for a desktop environment? This is a joke. Maybe the RTOS can perform my compiles too? That way will be able to accurately predict how long it will take to compile linux-2.4.18 each and every time. A desktop environment has very few, if *any* real time requirements, and those that do should be implemented in dedicated hardware, and not on the main CPU. (i.e. SCSI, hard drives, ethernet cards, ...)

It appears that Daniel didn't read my post that he accused me of composing before reading the post that he thinks I didn't read. He doesn't need to look far above to see (as quoted):

"So, we assume that the .mp3 data gets sent from the non-RT file system to the RT task (via the non-RT GUI front-end) in its entirety before it begins playing..."

To me this looks a lot like "Load the whole mp3 into memory before playing it", except I bothered to include vague details about how to accomplish this.

The alternative still sucks, and isn't scalable (i.e. none of this post is a disagreement with Oliver...), but more than that, it seems like a horrible waste of effort except as a proof-of-concept demo like "Hello World!". It is a joke that shows the exact feeling that some of us have that people think RT solves everything in all of its glory.

Summary: Linux + RTOS should never become VxWorks.

In fact, if fewer people thought that RT was more than a specialized solution to a very specific problem domain, I wouldn't have such negative feelings for the people that do.

I have a hammer in my toolbox too. That doesn't mean I use it to fix every thing that breaks at my house.

mark

[email protected]/[email protected]/[email protected] __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

I'm also not against such approaches.
As I worked for QNX I liked to provoke my Canadian coworkers with arguments like: RTLinux is able to swap - not bad for a hack ;-)

http://groups.google.de/groups?selm=378b7d25%240%24199%40nntp1.ba.best.com&output=gplain

When talking about hard realtime it's all about worst case considerations. Average does not count (then you are talking about *soft realtime* -> like multimedia apps, where only the quality counts). So you could only tell how long your compile lasts at *maximum*

As I said before: the OS is only the foundation for realtime *systems*

Yes, given that vxworks is more like a realtime executive (but this seems to change: only true when running without VxVMI? )

http://www.windriver.com/products/html/vxwks5x_ds.html

spot on. this is why i use a dsp card on my studio workstation; latency doesn't change (therefore no clicks/pops) when you move the mouse rapidly. it sticks right on whatever i set it to (13ms on my card, the newer ones can do around 1ms)

can't say the same for vst (host cpu powered) instruments/effects. controller latency DOES matter.

sadly all the host software for the card needs windows or macos. linux is MUCH better than windows in areas like this, after all the work Sir Morton has done to clean up latency. a thousand blessings upon his house :-)

j.

toyota power: http://indigoid.net/

Hi,

I understand that this is, but does anyone know what exactly our opportunities in this corner are?

He's a Sir now? Sorry, Sir Andrew, I didn't know that ;-)

Regards,
Thunder
--
ship is leaving right on time | Thunder from the hill at ngforever
empty harbour, wave goodbye |
evacuation of the isle | free inhabitant not directly
caveman's paintings drowning | belonging anywhere

Hi!

10 skips a year is probably okay for broadcaster, "normal" stations using cds are worse than that.
Pavel

(about SSSCA) "I don't say this lightly.  However, I really think that the U.S.
no longer is classifiable as a democracy, but rather as a plutocracy." --hpa

Also, unless one plans on playing 10+ .mp3's simulataneously on the same piece of hardware, I would make a bet that the electric company, or the computer itself would 'skip' before the dedicated computer 'skipped'. In either case, real time, or no real time, the system will skip.

mark

[email protected]/[email protected]/[email protected] __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

You're both being silly. The point is not mp3 skips per year, the point is:
is anything less than perfection tolerable, when you know perfection is within reach? If it helps, forget I ever said 'mp3' and think 'signal processing' instead.

I'll go further and say we need realtime processing in our desktops, not only for signal processing but for more mundane things like moving the mouse cursor smoothly (yes, this is another item that sucks in Linux). Sorry, I'm a perfectionist, and I like precision. If you're not and you don't, just say so, and we'll understand each other perfectly.

OK, I'm done with the 'do we really need realtime' FAQ item.

Daniel

It's called a hardware cursor... :-)

mark

[email protected]/[email protected]/[email protected] __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

It's called an omiscient harware cursor. It knows how and where to draw itself without being told :-)

Daniel

Hi!

Actually, I believe such systems existed. Mouse was plugged to the video card, and video card did mouse decoding.
Pavel

(about SSSCA) "I don't say this lightly.  However, I really think that the U.S.
no longer is classifiable as a democracy, but rather as a plutocracy." --hpa

What stops you from providing non-sleeping messaging scheme primitives in Adeos?

Adeos -> Client: Use virtual interrupt vectors and use your ipipe
for it.

Client -> Adeos: Provide Emission of this virtual interrupts in Adeos.

Also some kind of shared memory and a "commit" for this memory is needed in Adeos. Allocation of this memory should be up to the requester of this memory, so Adeos doesn't need to wait for it and neither does the RTOS on the other end.

With that primitives (plus some atomic magic ;-)) you can build non-sleeping messaging.

Karim, is sth. like this planned or is it senseless?

Regards

Ingo Oeser

Science is what we can tell a computer. Art is everything else. --- D.E.Knuth

Hello Ingo,

All this looks like classic nanokernel capabilities, so this is definitely within Adeos' reach. SPACE, for instance, defines an abstraction called "Portals" which are used for cross-domain communication and can be implemented using exceptions (in the SPACE papers exception == interrupt).

Karim

===================================================
Karim Yaghmour
[email protected]
Embedded and Real-Time Linux Expert
===================================================

When did Solaris ever support xfs?

no, but the combination of xfs and irix has
made a lot of folks happy - and xfs/linux
is coming along nicely as well...

Joe

                                     ^^^^			

Heh, I can only protest that Oxymoron also missed that thinko..

Improving the average latency of systems is a worthy goal, and there's no denying that 'sorta realtime' has its place, however it's no substitute for the real thing. A soft realtime system screws up only on occasion, but - bugs excepted - a hard realtime system *never* does.

Daniel

Engineering assumption. Your hardware and/or software always contains at least one bug. Therefore even in hard real time you must design and code for the failure case. Hard real time is just doing everything humanly possible to meet it's deadlines.

The difference with soft real time, is that something that is humanly possible to do was left off.

Despite the strong relationship to mathematics there are no absolutes in computer science. Especially hard real time.

Eric

It's XFS with a realtime volume under Irix.
With the React extension Irix is also capable of "hard realtime". But these days the term realtime is a lot misused - and leeds to assumption of a better "system".

Yes, in theory. You define hard realtime system in a clean room. Even QNX4 couldn't provide hard realtime when creating new processes. You had to start them beforehand - so you needed good system design. The OS is just a small part of that.

Even vxworks had problems with priority inversion ... and so on.

With Adeos, you'd make the non-realtime OS do all the hard work of starting the process, such as allocating the memory and locking it down, then (one of) the realtime OS(es) just inserts the process into its queue. Once in the queue, the new process can exhibit realtime behavior, but until that time there are no deadline guarantees and the realtime application should not rely on any. In other words, forking a realtime process to handle an event in real time is a poor idea.

Similarly, loading a realtime driver to control some device that just came online is not in general going to be a realtime process, but we don't really care. A machine starts when it starts (think about your car in the winter) but once running, we expect it to keep running without a hiccup.

Here, the Adeos pipeline design exhibits a really nice property: you can stack realtime OSes one on top of one another, so you could for example, have one RTOS entirely optimized for microsecond-scale events, another for millisecond-scale events, and a third for events with timings measured in seconds. Each has a completely independent set of locks. Alternatively, a slower-scale process can be forbidden from acquiring a lock of a faster-scale process, but the reverse can be permitted.

Daniel

Ramfs, for example. The easiest way to pin the sucker in page cache, no matter what the VM has to say about it. :)

Rob

So will we soon be seeing a port of RTAI to a linux kernel module which is implemented as a separate Adeos domain, allowing RTAI apps to bypass US patent 5995745? A quick glance over that patent leaves me uncertain whether this indeed bypasses the fundamental "invention" of a "process for running a general purpose computer operating system using a real time operating
system". It still looks to me like a real time operating system
(Adeos) running real time and non-real time tasks with a general purpose operating system as one of the non-real time tasks... Could you summarize (for non-lawyers such as myself) how this bypasses the claims in the patent?

Hopeful is,

-Erik

--
Erik B. Andersen http://codepoet-consulting.com/
--This message was written using 73% post-consumer electrons--

But the point is exactly that adeos is not a real-time operating system. It is not an operating system at all.

Besides, adeos is not a "circumvention device" to run RT-and-non-RT at the same time. It's a nano-kernel meant to run several independent OS's at once, as well as kernel debuggers and a lot of other stuff. Did you notice Karim is the author and maintainer of the linux trace toolkit?

I'll quote the patent for you:

A process for [...] providing a general purpose operating system as one of the non-real time tasks; preempting the general purpose operating system as needed for the real time tasks; and preventing the general purpose operating system from blocking preemption of the non-real time tasks.

Nothing of this is in adeos. And nothing of this will be in the adeosized RTAI.

/alessandro, living in a swpat-free country (with other problems, though :)

The problem here is the "quick glance" (no offense intended). The most important part of a patent is its claims. In the case of the rtlinux patent, there are 11 claims. There are 2 sorts of claims, independent claims and dependent claims. In this patent, there are 2 independent claims and 9 claims that depend on these 2 root claims. If you can show that a method is not an implementation of those 2 root claims, you're clear.

The 2 root claims in this patent are claim 1 & 7. Both of these contain the following statements [1]:

First, the introductory phrase doesn't match. Any RTOS above Adeos does not run Linux. The RTOS does not catch all interrupts and decide which ones go to Linux and which don't. In fact, it is very possible that the RTOS isn't even aware of Linux's existence. All it sees is Adeos with which it interacts to get everything it needs. Furthermore, the RTOS has no idea if someone else is before him in the ipipe.

As for the claims, we just need to take a look at "a" and "b" to see that it doesn't match:
a) Adeos is certainly not an RTOS and it certainly doesn't have any "tasks". It doesn't even have a scheduler. All it does is distribute hardware resources to whoever asks for them. Note that "Exokernel" for instance, did have a "round-robin" scheduler. So even if Adeos had a scheduler, it would still be considered a nanokernel.
b) This one doesn't apply to Adeos for the same reasons as "a". Also this phrase doesn't apply to any RTOS above Adeos because any such RTOS need not even know Linux is there. All it needs to know is that it has to call on adeos_suspend_domain() to go into a dormant state when it doesn't have any more "ready" tasks. In no way does it have a "Linux" task, as RTLinux and RTAI clearly do.

Karim

[1]
http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=%275,995,745%27.WKU.&OS=PN/5,995,745&RS=PN/5,995,745

===================================================
Karim Yaghmour
[email protected]
Embedded and Real-Time Linux Expert
===================================================

no offense taken. I'm not a lawyer, so much beyond a quick glance teaches me very little when reading such things.

Thanks much for the explanation -- that was exactly what I was hoping to see. Very very cool.

-Erik

--
Erik B. Andersen http://codepoet-consulting.com/
--This message was written using 73% post-consumer electrons--

Just one thing. Patents are not just for lawyers. In fact, patents are supposed to explain to anyone vested in the art how to implement the "invention"
. In this case, this means that anyone who has a knowledge of operating system architecture should be able to read this patent and understand it for what it is.

Thanks, glad you like it :)

Karim

===================================================
Karim Yaghmour
[email protected]
Embedded and Real-Time Linux Expert
===================================================

For anyone who's interested, here's a pointer to *all* the claims of the rtlinux patent:

http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=%275,995,745%27.WKU.&OS=PN/5,995,745&RS=PN/5,995,745

And here's a pointer to a nice tutorial on how to read patent claims:

http://www.tms.org/pubs/journals/JOM/matters/matters-9511.html

Daniel

Hi!

Sounds interesting...

Also, unlike UML, kernels are not protected from each other.

So if your FreeBSD+Linux combination crashes, you do not know if Linux or FreeBSD caused it.

This is same approach rtLinux takes, right?
Pavel

Philips Velo 1: 1"x4"x8", 300gram, 60, 12MB, 40bogomips, linux, mutt,
details at http://atrey.karlin.mff.cuni.cz/~pavel/velo/index.html.

I sent this earlier to Pavel, but it seems that it hasn't made it to the LKML:

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

Hello Pavel,

Thanks.

True, if they do physical accesses in each other's areas there's a problem. But we're assuming 2 things here:
1) You are using stable kernels.
2) See the next answer.

No one said that you can't have an early domain in the pipeline that specifically deals with this

No, Have you seen the explanation I provided earlier to Erik:
http://marc.theaimsgroup.com/?l=linux-kernel&m=102309926620900&w=2

Adeos is clearly different from anything that is part of the rtlinux patent.

Karim

===================================================
Karim Yaghmour
[email protected]
Embedded and Real-Time Linux Expert
===================================================

Since Linux can run with kernel space controlled by MMU mappings and with a few sanity checks in the PCI mapping code it should be possible to make it reasonably robust. It would have to corrupt its kernel page table mappings and then corrupt itself to scribble through them to fail.

Going beyond that is hairy because you then need to virtualise the hardware interfaces and also run the kernel in ring 3 with seperate guarded page tables

It accomplishes the same thing in a different way. Karim's interrupt pipline approach also exposes some interesting new capabilities to the client operating systems. The ability to add/remove clients from the pipeline seems very powerful.

Daniel

Hello Pavel,

Thanks.

True, if they do physical accesses in each other's areas there's a problem. But we're assuming 2 things here:
1) You are using stable kernels.
2) See the next answer.

No one said that you can't have an early domain in the pipeline that specifically deals with this

No, Have you seen the explanation I provided earlier to Erik:
http://marc.theaimsgroup.com/?l=linux-kernel&m=102309926620900&w=2

Adeos is clearly different from anything that is part of the rtlinux patent.

Karim

===================================================
Karim Yaghmour
[email protected]
Embedded and Real-Time Linux Expert
===================================================