Hybrid kernel, not NT

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

Linus Torvalds (torvalds@osdl.org) on 5/9/06 wrote:
---------------------------
>Brendan (btrotter@gmail.com) on 5/9/06 wrote:
>>myself (-@-.com) on 5/9/06 wrote:
>>>
>>>You don't get freed from those things in a microkernel
>>>either - those disadvantages are inherent to both models.
>>>Nobody said that a monolithic kernel fixes everything
>>>magically.
>>
>>If a device driver is running as a single-threaded process,
>>why would it need any re-entrancy locking at all?
>
>Why do you think that has anything to do with microkernels?

Because in my experience monolithic kernel designers dismiss the possibility, while micro-kernel designers prefer to implement device drivers as seperate processes. You are correct of course - it's entirely possible to implement device drivers in a monolithic system in a similar manner...

>Monolithic kernels have threads. It would be entirely
>possible - although pretty stupid - to do a single driver
>thread on a monolithic kernel, and have a simply queueing
>model for delivering interrupts and requests to that driver.
>
>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).

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, 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). 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.

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 network device drivers very much (as message data and/or shared memory can't easily be tied to a specific NUMA domain) but would benefit some things - e.g. file system code and the disk device driver both running on the correct NUMA node. Of course Linux can probably do this with kernel threads too.

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).

Then there's hardware changes. For example, consider a server with hot-plug PCI. 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).

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. 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.

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.

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.

>The reason microkernels often have that model is that if
>you don't have direct interrupt delivery, and if all the
>events are from some message queue anyway, it's just a
>very natural way to do things. You actually tend to need
>to do extra work to get re-entrant services and interrupts
>delivered directly.
>
>Of course, if you want good performance, heaven
>forbid, you actually want to get interrupts delivered
>directly, and you want to actually look at the whole
>message queue, not just the top entry, and suddenly you
>find that microkernels are actually in your way of
>doing things well (or that you actually need to know
>about things like locking, because you need to look into
>the message queue by hand).

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).

>In general, locking isn't the problem in drivers, the hw
>is. Undocumented, buggy, and with strange interactions
>("Oh, DMA doesn't work properly with that other chipset?").
>
>(Admittedly, equally often the driver problem is all the
>infrastructure, and the fact that you have about a zillion
>drivers that use old and broken rules that it turns out
>doesn't work really well when you have a thousand disks
>directly connected. Oh, well).

Unfortunately those problems don't go away regardless of what you do (unless you limit yourself to a well-defined architecture, like the Commodore64)... :-)


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?