A Fork in the Road for my OS

[JohnnyTheDon]

Now that you've mentioned him, even Jochen Liedtke said this. Take a look over his work for a better understanding of this.

From Jochen Liedtke's presentation at the 15th ACM Symposium on Operating System Principles:

Microkernels can have adequate performance if they are architecture-dependent.They increase portability, though they themselves are non-portable. In this sense, they can be seen as a hardware abstraction layer. Previous microkernels perform poorly because they derive from monolithic kernels.

He doesn't say HALs are bad. He says that microkernels are essentially HALs themselves.

It uses segmentation (which isn't even available in 64-bit mode)

Doesn't mean segmentation has to be used. In fact some of the L4 variants don't use segmentation. IIRC L4ka::Pistachio uses paging, and it does support x86_64.

[Love4Boobies]

However, I would like to note that they make the rest of the system highly portable, as opposed to (more) monolithic kernels.

And microkernels aren't HALs themselves. Abstraction is not their purpose (e.g. how is the scheduler part of HAL?). Besides, they're meant to be small and rewriting them isn't a big issue anyway, so I can't see why anyone would bother writing a HAL if all that does is decrease performance just so there's a uniform (standard) way of doing things across all (incompatible) platforms.

Maybe there's a L4 that uses paging but I'll have to reasearch it. I have no idea if it really performs good.

The way I give my microkernel a boost is having asynchronous IPC (via shared pages - there's also a library for transactional memory). What I personally think to be the real bottleneck with microkernels is backward compatibility (read: C standard library). Everyone wants to use the C standard library for compatibility with different applications and that can only be done via message passing (or some other sort of synchronous IPC mechanism).

[Colonel Kernel]

Ooooh! Microkernel fight! This is the most exciting thread I've seen in a few years.

@Love4Boobies:
Theoretical arguments are interesting, but I prefer to look to what's been commercially successful when evaluating what does or doesn't work. QNX is a commercially successful real-time OS. Based on this I have to assume it has good performance characteristics. It is a microkernel, and it has a sort of HAL (BSP). Therefore, your generalization is provably false.

[Love4Boobies]

I will say no more until I look into it more but that doesn't mean I won't have anything to say afterwards And yes, it totally makes sense that commercial success means good performance, yet I haven't seen any good microkernels and they are not normally used in commercial OSes. I'm going to put this QNX to the test

[Troy Martin]

http://groups.google.com/group/comp.os. ... d95d?tvc=2

[Love4Boobies]

We're not arguing about monolithic kernels vs. microkernels. We're talking about how well they perform and how portable they are By the way, I read that microkernels are a pain because distributed algorithms are a pain. I'm not sure I got that right, if someone could explain...

[JohnnyTheDon]

We're not arguing about monolithic kernels vs. microkernels. We're talking about how well they perform and how portable they are

If you're talking about how well they perform and how portable they are, you have to be comparing their portability and performance to something. This isn't necessairily monolithic vs. mirokernel but it is microkernel vs. alternatives.

As both L4 and QNX have proven, microkernels can be fast. You can say their benchmarks aren't the best, that they aren't popular, but that doesn't mean microkernels are slow. Making overly generalized statements like "Let's face it, microkernels are SLOW" is a bad idea if you can't prove your position.

[Love4Boobies]

Well, they only perform reasonably well in certain situations. Can you show the contrary?

EDIT: I'd like to note that I'm a microkernel person, myself...

[Colonel Kernel]

By the way, I read that microkernels are a pain because distributed algorithms are a pain. I'm not sure I got that right, if someone could explain...

Are you referring to what Linus said in the latest incarnation of the Torvalds vs. Tanenbaum debate? IIRC, his key point there was that it's easier to manage key shared data structures in one big address space rather than in a distributed way in a bunch of separate processes. IMO, this is somewhat of a straw man born of the facts that Linus has never himself developed a microkernel, and that he tends to exaggerate in order to win arguments.

However, there is an important point in what he says, given the changing hardware topology. With many-core processors, it's going to become very inefficient to keep a single copy of each major kernel data structure (free page lists, scheduler queues, virtual address space descriptors, page tables, etc.) and share it between all the CPUs due to extra bus traffic caused by cache synchronization. I think there will be an increasing trend towards having CPU-local versions of these data structures, and needing to synchronize between them. Keeping them coherent can be tricky, but if things are designed well, it shouldn't be needed very often (e.g. -- Keeping CPU-local pools of threads to run, and balancing between CPUs only occasionally or when a CPU becomes idle).

Well, they only perform reasonably well in certain situations. Can you show the contrary?

Nope, I think you're right actually. QNX is a real-time OS and probably runs well on 1 to 2 CPU cores, but I'd be surprised if it scaled much beyond that given its reliance on synchronous message-copying IPC. L4 does well on IPC micro-benchmarks, but I'm skeptical that this can translate into good overall system performance.

There is one fast microkernel out there that I know of: Singularity. It's fast because its IPC involves passing pointers around because everything lives in Ring 0 by default.

[JohnnyTheDon]

<OT>

With many-core processors, it's going to become very inefficient to keep a single copy of each major kernel data structure (free page lists, scheduler queues, virtual address space descriptors, page tables, etc.) and share it between all the CPUs due to extra bus traffic caused by cache synchronization. I think there will be an increasing trend towards having CPU-local versions of these data structures, and needing to synchronize between them.

</OT>

Never thought of that... Does the Linux kernel do (or have plans for doing) this kind of separation of data structures? And wouldn't this be easier with a microkernel, because you can give one server an affinity for running on one core, and another on another core, etc. Then you could rely on shared memory to do asynchronous message passing (or use registers if the server is running on the same core).

Also, wouldn't any scheme where you synchronize structures between processors include the need for copying structures and be directed by IPIs or shared memory, all of which involve the use of the bus (unless its an older SMP system with a dedicated APIC bus).

[Colonel Kernel]

Never thought of that... Does the Linux kernel do (or have plans for doing) this kind of separation of data structures?

Not sure as I'm not a Linux expert.

And wouldn't this be easier with a microkernel, because you can give one server an affinity for running on one core, and another on another core, etc. Then you could rely on shared memory to do asynchronous message passing (or use registers if the server is running on the same core).

I think it's easier with a microkernel because you have a lot fewer important shared data structures in kernel space. For things like file systems, the in-memory structures can be managed in a separate server process quite easily. The trick is to make the server process scale to a lot of requests. My comments were about data structures that nearly always go in the kernel itself, whether micro or not.

Also, wouldn't any scheme where you synchronize structures between processors include the need for copying structures and be directed by IPIs or shared memory, all of which involve the use of the bus (unless its an older SMP system with a dedicated APIC bus).

Yes, but the idea is that this synchronization wouldn't be needed very often compared to how often the structures are accessed by individual CPUs. Right now, if you implement a lock-free data structure naively and share it between multiple CPUs, even if the CPUs are working on different parts of the data structure the performance can suck because of accidental sharing (i.e. -- different parts of the structure accessed by different CPUs are too close together and end up in the same cache line, causing cache ping-pong between CPUs). So you can have frequent contention and not even know it. If you keep things totally separate, this problem goes away by design.

[JohnnyTheDon]

Ah, okay that make sense. The idea of separating kernel structures between processors and synchronizing them when necessary sounds like a great idea. Will probably do this in my own kernel eventually.