Hybrid kernel, not NT

By: Brendan (btrotter.delete@this.gmail.com), May 13, 2006 9:48 am
Room: Moderated Discussions
Hi,

nick (anon@anon.com) on 5/13/06 wrote:
>Brendan (btrotter@gmail.com) on 5/13/06 wrote:
>>Linus Torvalds (torvalds@osdl.org) on 5/9/06 wrote:

>You're brave, to lecture Linus on the benefits of
>microkernels :)

That's not my intent - enough better qualified people have tried, I doubt Linus could switch to a micro-kernel even if he wanted to (too much existing code), and I'd be surprised if Linus returns to this thread anyway (the site was down for long enough last time).

>>>Now, basically nobody would be as stupid as to do
>>>this on a monolithic kernel. It's a pretty broken model,
>>>and since the only reason to do it is to do something that
>>>is actually pretty simple anyway (locking is very simple
>>>if you just want to have total mutual exclusion), there's
>>>just no real upside.
>>
>>Total mutual exclusion is easy until an IRQ handler needs to retrieve or store
>>data without causing potential deadlocks (i.e. IRQ handlers would either need to be lock-free or _extremely_ careful).
>
>But your microkernel driver can't do that at all though, so
>that isn't even what is being talked about.

I was only pointing out that mutual exclusion isn't so easy unless you also queue or delay IRQ delivery.

>A monolithic kernel can just as easily have the IRQ work
>deferred to process context as well.

In theory a monolithic kernel can do everything that is normally done in micro-kernels - I've never denied this (only that at some point it ceases to be a true monolithic kernel).

>>For the upsides, if the system is designed so that only one process has access
>>to each "thing" (memory buffer, piece of state information, etc), then all locks
>>are either confined within the micro-kernel itself or process specific (in the case
>>of multi-threaded processes), which reduces complexity as the majority of re-entrancy
>>concerns for the hundreds of device drivers are handled by the kernel's IPC mechanism.
>>This basically means device driver programmers either don't need to care about re-entracy
>>at all,
>
>Great now your scalability sucks, and you can do this with
>a monolithic kernel anyway as Linus points out.

The message queues are only locked when messages are being added or removed. I guess it does depend on how the messaging is done - synchronous messaging would probably suck for scalability.

>>or they need to do the same things that anyone working on multi-threaded
>>user level code does (if a device driver is implemented as a multi-threaded process).
>
>And now you have to do "hard" threaded programming. There's
>no two ways about it.

You could use messaging between the threads and have lock-free multi-threaded processes (not that I'd recommend it). The point is that the only thing you'd need to be careful of is data shared between these threads, rather than needing to acquire a lock every time the driver touches it's own data.

>>Also, a micro-kernel is often small enough that the equivelent of a "big kernel
>>lock" is practical, meaning you could have one lock in the entire system in addition
>>to any "processes specific" locks, and no other locks.
>
>I don't know what systems that thing would run on, but it
>wouldn't be any big ones, that's for sure.

That depends what the OS is designed for and how fast the slowest kernel function is.

>>Another potential advantage is NUMA systems, where you can set the CPU affinity
>>on a device driver so that it's always run on a CPU that is "close" to the I/O controller
>>used by the device. This doesn't apply to things like
>
>No, this is not. Because if the data is coming from / going
>to somewhere off node, you must send it across nodes anyway.
>And now you *also* have control information (messages) going
>across nodes as well.

For control information you've got a choice - access the control data across nodes, or access the device driver code and it's local state across nodes. Unless everything (control data, code and state) is on the same node it can't be "perfect" regardless of what you do (for all kernel designs).

I already said it doesn't apply to some devices. For some things the communication between the device driver and it's device is more than the communication between the client and the device driver, especially if the device driver maintains it's own queues or buffers (e.g. scatter-gather I/O or a sound card driver where the incoming audio data is mixed with existing data before being sent to the device).

>>Then there's I/O port protection, where the kernel could be designed to grant a process access to specific I/O ports rather than all I/O ports (which can't be done on 80x86 when device drivers run at CPL=0). This is the only way I can think of to prevent security holes in device drivers from being used to mess with the chipset, PCI configuration space, etc. On an unrelated point, there's probably no reason why Linux couldn't do this for "device drivers" that already run as user-processes, like the X server (for one scenario, see http://www.securityfocus.com/columnists/402 ).

>... so, I thought you were going to come up with things that
>Linux/mono kernels can't do?

On 80x86 you can't prevent code running at CPL=0 from accessing any I/O port it likes. The X server can be fixed easily because it's a user-level process, but for the remaining millions of lines of code you're screwed. I guess that's normal - if there's a security vulnerability in any of those millions of lines of code you'd be screwed anyway, regardless of whether all I/O ports can be accessed or not.

>>It runs for 5 years with no problems, then someone wants to plug in a new PCI device
>>to handle increased load. The hardware is designed to handle this without downtime
>>and the kernel supports hot-plug PCI so you'd think it could be done without downtime.
>>Unfortunately the kernel is 5 years old and the device is new so you need to have
>>downtime to update the kernel because of the new device driver. Someone's bound
>>to say that Linux supports dynamically loaded modules, and in theory they'd be right
>>(but in practice the kernel would've changed too much in 5 years to allow that possibility).
>
>Actually, someone will say that this is nothing to do with
>micro and monolithic kernels. If your microkernel's
>interfaces have also evolved, then you need to backport the
>driver; conversely, there is no reason why the Linux driver
>couldn't be backported.

IMHO there's only one reason for changing the interfaces used by device drivers in a micro-kernel - poor initial design (which is possible I guess, but unlikely if the micro-kernel is mature enough to be used on computers that matter).

>>Lastly there's booting. If device drviers are seperate processes, then the "device
>>detection" code (PCI bus scan, etc) can start the processes/device drivers as it
>>finds them and continue, such that all device drivers are initialized in parallel.
>>This could be extended to system services - for example, as soon as a storage device
>>driver completes it's initialization suitable file system code is loaded, as soon
>>as the video card is initialized a "virtual terminal" is started, etc. Doing device
>>detection, device driver initialization, system service startup, file system checks
>>(and possibly X server and GUI startup) all in parallel would slash boot times noticeably.
>
>No reason why a monolithic kernel cannot do this.

Should I wait for you to add this to Linux? I'd be grateful.... :-)

>>There's already people trying to do "parallel system service startup" - I even saw
>>one web page saying they reduced a 3 minute boot time down to 100 seconds using this method.
>
>That's probably parallel userspace booting, and the time
>savings are due to overlapping IO and computation.

For the computer I'm using there's a delay within the SCSI driver's intialization where the entire machine does nothing for about 15 seconds. I'd assume overlapping I/O with other I/O would help...

>>It'd probably be possible for Linux (or any monolithic system) to do all of the
>>above, just like you can probably make a truck drive on water if you add enough
>>"work arounds". It's not quite the same as something originally designed for the
>>purpose though (like a boat), and you'd have to wonder at what point the monolithic kernel ceases to be monolithic.
>
>I don't follow your logic. If a microkernel wasn't designed
>to do any of the above and you just added "work arounds" to
>it as well, what's the difference?!?

If a micro-kernel wasn't designed to do any of the above, then it'd probably be a monolithic/hybrid kernel anyway.

>>IMHO the whole "micro-kernel vs. monolithic" thing (and OS design in general) comes
>>down to compromises - balancing performance, features and development time to achieve
>>a desired end result. For different end results, different compromises are made along the way.
>
>Perhaps, but you have failed to make any case.

Only because a monolithic kernel can use the same techniques as a micro-kernel, not because a monolithic kernel can do these things without pretending to be a micro-kernel.

We've both forgotten, but my original comment was about running device drivers as processes, not really about monolithic vs. micro-kernel.

>>My prefered method is to have a scheduler that gives "interrupt handling" threads
>>a higher priority than all other threads, such that their message queues are (under
>>normal circumstances) empty anyway. A message sent from a lower priority thread
>>to one of these high priority threads causes an immediate thread switch followed
>>by message/IRQ delivery. More complex device drivers would be multi-threaded, consisting
>>of a very high priority thread for dealing with the hardware and handling IRQs,
>>and another thread for dealing with "client requests", etc. The price (as compared
>>to a traditional monolithic OS) is extra interrupt latency caused by the context
>>switches (but there isn't a need to scan the message queue in this case).
>
>That's the performance Linus is talking about. Linux
>actually has a realtime patchset which implements interrupt
>threads (which will be much lighter weight than a full
>userspace switch and tlb flush). However performance for
>interrupt heavy workloads like networking unsurprisingly
>sucks with it.

I'm not sure what this patch would do - does it delay IRQ delivery until a realtime thread blocks (to prevent IRQ handling from messing up CPU time allocated to the realtime thread)? A context switch and TLB flush isn't free, but it's not that expensive either - between 2 us and 20 us for a 25 MHz 80486 (depending on a lot of things).


Cheers,

Brendan
< Previous Post in ThreadNext Post in Thread >
TopicPosted ByDate
Hybrid (micro)kernelsTzvetan Mikov2006/05/08 04:41 PM
  Hybrid (micro)kernelsS. Rao2006/05/08 06:14 PM
  Hybrid (micro)kernelsBill Todd2006/05/08 06:16 PM
    Hybrid (micro)kernelsTzvetan Mikov2006/05/08 07:21 PM
      Hybrid (micro)kernelsnick2006/05/08 07:50 PM
      Hybrid (micro)kernelsBill Todd2006/05/09 01:26 AM
        There aren't enough words...Rob Thorpe2006/05/09 02:39 AM
          There aren't enough words...Tzvetan Mikov2006/05/09 03:10 PM
            There aren't enough words...Rob Thorpe2006/05/15 12:25 AM
        Hybrid (micro)kernelsTzvetan Mikov2006/05/09 11:17 AM
          Hybrid (micro)kernelsBill Todd2006/05/09 04:05 PM
  Hybrid (micro)kernelsrwessel2006/05/08 11:23 PM
    Hybrid kernel, not NTRichard Urich2006/05/09 06:03 AM
      Hybrid kernel, not NT_Arthur2006/05/09 07:06 AM
        Hybrid kernel, not NTRob Thorpe2006/05/09 07:40 AM
          Hybrid kernel, not NT_Arthur2006/05/09 08:30 AM
            Hybrid kernel, not NTRob Thorpe2006/05/09 09:07 AM
              Hybrid kernel, not NT_Arthur2006/05/09 09:36 AM
                Linux vs MacOSX peformance, debunked_Arthur2006/05/18 07:30 AM
                  Linux vs MacOSX peformance, debunkedRob Thorpe2006/05/18 08:19 AM
                    Linux vs MacOSX peformance, debunkedAnonymous2006/05/18 12:31 PM
        Hybrid kernel, not NTLinus Torvalds2006/05/09 08:16 AM
          Hybrid kernel, not NTAndi Kleen2006/05/09 02:32 PM
            Hybrid kernel, not NTmyself2006/05/09 03:24 PM
              Hybrid kernel, not NTmyself2006/05/09 03:41 PM
              Hybrid kernel, not NTBrendan2006/05/09 05:26 PM
                Hybrid kernel, not NTLinus Torvalds2006/05/09 08:06 PM
                  Hybrid kernel, not NTBrendan2006/05/13 01:35 AM
                    Hybrid kernel, not NTnick2006/05/13 04:40 AM
                      Hybrid kernel, not NTBrendan2006/05/13 09:48 AM
                        Hybrid kernel, not NTnick2006/05/13 07:41 PM
                          Hybrid kernel, not NTBrendan2006/05/13 09:51 PM
                            Hybrid kernel, not NTnick2006/05/14 05:57 PM
                              Hybrid kernel, not NTBrendan2006/05/14 10:40 PM
                                Hybrid kernel, not NTnick2006/05/14 11:46 PM
                                  Hybrid kernel, not NTBrendan2006/05/15 04:00 AM
                                    Hybrid kernel, not NTrwessel2006/05/15 07:21 AM
                                      Hybrid kernel, not NTBrendan2006/05/15 08:55 AM
                                        Hybrid kernel, not NTLinus Torvalds2006/05/15 09:49 AM
                                          Hybrid kernel, not NTnick2006/05/15 04:41 PM
                                          Hybrid kernel, not NTtony roth2008/01/31 02:20 PM
                                    Hybrid kernel, not NTnick2006/05/15 06:33 PM
                                      Hybrid kernel, not NTBrendan2006/05/16 01:39 AM
                                        Hybrid kernel, not NTnick2006/05/16 02:53 AM
                                          Hybrid kernel, not NTBrendan2006/05/16 05:37 AM
                  Hybrid kernel, not NTAnonymous2008/05/01 10:31 PM
                    Following the structure of the treeMichael S2008/05/02 04:19 AM
                      Following the structure of the treeDean Kent2008/05/02 05:31 AM
                        Following the structure of the treeMichael S2008/05/02 06:02 AM
                        Following the structure of the treeDavid W. Hess2008/05/02 06:48 AM
                          Following the structure of the treeDean Kent2008/05/02 09:14 AM
                            Following the structure of the treeDavid W. Hess2008/05/02 10:05 AM
                              LOL!Dean Kent2008/05/02 10:33 AM
                              Following the structure of the treeanonymous2008/05/02 03:04 PM
                                Following the structure of the treeDean Kent2008/05/02 07:52 PM
                                Following the structure of the treeFoo_2008/05/03 02:01 AM
                                  Following the structure of the treeDavid W. Hess2008/05/03 06:54 AM
                                    Following the structure of the treeDean Kent2008/05/03 10:06 AM
                                      Following the structure of the treeFoo_2008/05/04 01:06 AM
                                        Following the structure of the treeMichael S2008/05/04 01:22 AM
            Hybrid kernel, not NTLinus Torvalds2006/05/09 05:19 PM
              Microkernel Vs Monolithic KernelKernel_Protector2006/05/09 09:41 PM
                Microkernel Vs Monolithic KernelDavid Kanter2006/05/09 10:30 PM
                  Sigh, Stand back, its slashdotting time. (NT)Anonymous2006/05/09 10:44 PM
                  Microkernel Vs Monolithic Kernelblah2006/05/12 08:58 PM
                  Microkernel Vs Monolithic KernelRob Thorpe2006/05/15 01:41 AM
          Hybrid kernel, not NTAnalGuy2006/05/16 03:10 AM
            Theory versus practiceDavid Kanter2006/05/16 12:55 PM
              Distributed algorithmsRob Thorpe2006/05/17 12:53 AM
              Theory versus practiceHoward Chu2006/05/17 02:54 AM
                Theory versus practiceJS2006/05/17 04:29 AM
          Play online poker, blackjack !!! Gamezonex2007/08/16 01:49 PM
  Hybrid (micro)kernelsphilt2006/05/14 09:15 PM
    Hybrid (micro)kernelsLinus Torvalds2006/05/15 08:20 AM
      Hybrid (micro)kernelsLinus Torvalds2006/05/15 11:56 AM
        Hybrid (micro)kernelsRob Thorpe2006/05/16 01:22 AM
          Hybrid (micro)kernelsrwessel2006/05/16 11:23 AM
            Hybrid (micro)kernelsRob Thorpe2006/05/17 12:43 AM
              Hybrid (micro)kernelsrwessel2006/05/17 01:33 AM
                Hybrid (micro)kernelsRob Thorpe2006/05/19 07:51 AM
                  Hybrid (micro)kernelsrwessel2006/05/19 12:27 PM
      Hybrid (micro)kernelstechIperson2006/05/15 01:25 PM
      Hybrid (micro)kernelsmas2006/05/15 05:17 PM
        Hybrid (micro)kernelsLinus Torvalds2006/05/15 05:39 PM
          Hybrid (micro)kernelsColonel Kernel2006/05/15 09:17 PM
            Hybrid (micro)kernelsWink Saville2006/05/15 10:31 PM
              Hybrid (micro)kernelsLinus Torvalds2006/05/16 10:08 AM
                Hybrid (micro)kernelsWink Saville2006/05/16 09:55 PM
          Hybrid (micro)kernelsrwessel2006/05/16 11:31 AM
            Hybrid (micro)kernelsLinus Torvalds2006/05/16 12:00 PM
        Hybrid (micro)kernelsBrendan2006/05/16 01:36 AM
        Hybrid (micro)kernelsPaul Elliott2006/09/03 08:44 AM
          Hybrid (micro)kernelsRob Thorpe2006/09/04 09:25 AM
      Hybrid (micro)kernelsphilt2006/05/16 12:55 AM
        Hybrid (micro)kernelspgerassi2007/08/16 07:41 PM
  Another questionable entry on Wikipedia?Chung Leong2006/05/18 10:33 AM
  Hybrid (micro)kernelsisrael2006/05/20 04:25 AM
    Hybrid (micro)kernelsRob Thorpe2006/05/22 08:35 AM
Reply to this Topic
Name:
Email:
Topic:
Body: No Text
How do you spell purple?