Hybrid (micro)kernels

By: Paul Elliott (pelliott.delete@this.io.com), September 3, 2006 8:44 am
Room: Moderated Discussions
mas (mas769@hotmail.com) on 5/15/06 wrote:
>Don't know if you saw Tanenbaum's latest defence of microkernels but here it is if not.
I think that Prof. Tanenbaum's response to Mr. Torvalds
on the question of microkernels should be examined in
detail. The following is from:

TB> Linus' Argument
TB> Linus' basic point is that microkernels require distributed algorithms
TB> and they are nasty. I agree that distributed algorithms are hell on
TB> wheels, although together with Maarten van Steen I wrote a book
TB> dealing with them. I have also designed, written and released two
TB> distributed systems in the past decade, Amoeba (for LANs) and Globe
TB> (For WANs). The problem with distributed algorithms is lack of a
TB> common time reference along with possible lost messages and
TB> uncertainty as to whether a remote process is dead or merely
TB> slow. None of these issues apply to microkernel-based operating
TB> systems on a single machine. So while I agree with Linus that
TB> distributed algorithms are difficult, that is not germane to the
TB> discussion at hand.

I really do not understand this. Why are Mr. Torvalds arguments
not germane? Why is the following from Mr. Torvalds not germane?

T> Monolithic kernels have threads. It would be entirely
T> possible - although pretty stupid - to do a single driver
T> thread on a monolithic kernel, and have a simply queuing
T> model for delivering interrupts and requests to that driver.
T> Now, basically nobody would be as stupid as to do
T> this on a monolithic kernel. It's a pretty broken model,
T> and since the only reason to do it is to do something that
T> is actually pretty simple anyway (locking is very simple
T> if you just want to have total mutual exclusion), there's
T> just no real upside.
T> The reason microkernels often have that model is that if
T> you don't have direct interrupt delivery, and if all the
T> events are from some message queue anyway, it's just a
T> very natural way to do things. You actually tend to need
T> to do extra work to get re-entrant services and interrupts
T> delivered directly.
T> Of course, if you want good performance, heaven
T> forbid, you actually want to get interrupts delivered
T> directly, and you want to actually look at the whole
T> message queue, not just the top entry, and suddenly you
T> find that microkernels are actually in your way of
T> doing things well (or that you actually need to know
T> about things like locking, because you need to look into
T> the message queue by hand).

Professor Tanenbaum continues:

TB> Besides, most of the user-space components are drivers, and they have
TB> very straightforward interactions with the servers. All character
TB> device drivers obey pretty much the same protocol (they read and write
TB> byte streams) and all block device drivers obey pretty much the same
TB> protocol (they read and write blocks). The number of user-space
TB> servers is fairly small: a file server, a process server, a network
TB> server, a reincarnation server, and a data store, and a few more. Each
TB> has a well-defined job to do and a well-defined interaction with the
TB> rest of the system. The data store, for example, provides a
TB> publish/subscribe service to allow a loose coupling between servers
TB> when that is useful. The number of servers is not likely to grow very
TB> much in the future. The complexity is quite manageable. This is not
TB> speculation. We have already implemented the system, after all. Go
TB> install MINIX 3 and examine the code yourself.

Is all of the above correct?

TB> Linus also made the point that shared data structures are a good
TB> idea. Here we disagree. If you ever took a course on operating
TB> systems, you no doubt remember how much time in the course and space
TB> in the textbook was devoted to mutual exclusion and synchronization of
TB> cooperating processes. When two or more processes can access the same
TB> data structures, you have to be very, very careful not to hang
TB> yourself. It is exceedingly hard to get this right, even with
TB> semaphores, monitors, mutexes, and all that good stuff.
TB> My view is that you want to avoid shared data structures as much as
TB> possible. Systems should be composed of smallish modules that
TB> completely hide their internal data structures from everyone
TB> else. They should have well-defined 'thin' interfaces that other
TB> modules can call to get work done. That's what object-oriented
TB> programming is all about--hiding information--not sharing it. I think
TB> that hiding information (a la Dave Parnas) is a good idea. It means
TB> you can change the data structures, algorithms, and design of any
TB> module at will without affecting system correctness, as long as you
TB> keep the interface unchanged. Every course on software engineering
TB> teaches this. In effect, Linus is saying the past 20 years of work on
TB> object-oriented programming is misguided. I don't buy that.

Prof. Tanenbaum seems to be saying that data hiding (encapsulation)
prevents race conditions. That is wrong, data hiding does not by
itself prevent race conditions. Furthermore, it is so obviously wrong
that I do not understand how a respected professor of Computer Science
at a major university could even suggest it. Perhaps I am missing
something. Please tell me if I have make a mistake.

Suppose you have Evil_struct in a non object oriented, multi threaded
program or operating system. Evil_struct is accessed modules all over
the system, so that encapsulation is not being properly
used. Furthermore, Evil_struct is accessed by different threads so
that race conditions are possible. Suppose that you believe in OO, so
you go in and encapsulate every thing. You make Evil_struct a private
data member of Was_evil_class, and you fix it so that the only way to
access Evil_struct is by calling Was_evil_class' methods. Have you
eliminated race conditions? No! If you call Was_evil_class' methods
from different threads you can still get a race condition while the
methods access Evil_struct. The good thing about encapsulation is that
you now know where the race conditions are. They are usually inside
Was_evil_class' methods. It is also pretty easy to fix the race
conditions once found. Make Was_evil_class a resource and acquire a
resource lock around those sections of code where the race conditions

In the microkernel design it is not data hiding that prevents race
conditions, but rather the single threaded handling of an object's
methods, so that each method runs to completion without being
interrupted by another. This would be equivalent to acquiring a
resource lock for the entire time that any method runs. This is a
heavy handed one size fits all approach, as the resource lock may only
be need for a short section of code to stop race conditions.

Let us do a thought experiment, let us take the microkernel design and
change it let us remove the message queue or the rendezvous with with
a single thread, and instead make calls to a method immediately and
directly on a uniquely created (for each call) thread. This is a
thought experiment, so we are not worried about performance. We still
do all the stuff with the MMU so address spaces are still
separated. If we were to use this design, race conditions would still
be possible. We would have to worry about the "semaphores, monitors,
mutexes, and all that good stuff" that professor Tanenbaum is so
concerned about. But, we would be able to handle these race conditions
in any effective way, instead of being forced to use the microkernel's
one size fits all approach.

But single threaded handling of messages is NOT part of the Object
Oriented paradigm! The problems Mr. Torvalds is complaining about are
not caused by encapsulation, but rather by the single threaded
handling of messages, and that is not an OO feature! Therefore
Mr. Torvalds cannot be accused of thought crimes against the object
oriented ideology. It is true that Linux is coded in C but that does
not prevent people from thinking about issues in a OO way, and it does
not prevent OO implementation methods, coded by hand, from being used
where appropriate.

TB> Once you have decided to have each module keep its grubby little paws
TB> off other modules' data structures, the next logical step is to put
TB> each one in a different address space to have the MMU hardware enforce
TB> this rule. When applied to an operating system, you get a microkernel
TB> and a collection of user-mode processes communicating using messages
TB> and well-defined interfaces and protocols. Makes for a much cleaner
TB> and more maintainable design. Naturally, Linus reasons from his
TB> experience with a monolithic kernel and has arguably been less
TB> involved in microkernels or distributed systems. My own experience is
TB> based on designing, implementing, and releasing multiple such
TB> operating systems myself. This gives us different perspectives about
TB> what is hard and what is not.

Is it not true that all the run time overhead of using the MMU to
enfore this rule, could have been avoided by doing the checking at
design-compile-link time? Does this not make Mr. Torvalds' idea of a
OS compiling, constraint checking, computer language look good?
Mr. Torvalds does not need checkers, he has got hundreds of volunteer
eyeballs looking at his code. The person who needs checking is the
academic who is trying to get a research OS off the ground. Why don't
the academics work on such a compiler, instead of pouring more effort
into the rat hole of microkernels?

Is it not true that in order to make such checking easy, the
microkernel advocates force us to use an "event loop" style of
programming instead of a more natural threaded aproach? Is this not
what Mr. Torvalds is complaining about, rather than the red-herring of

If the "thought experiment" mentioned above were optimized, would it
not provide a way to use the MMU to do address space checking (if that
were needed) without forcing us into a convoluted "event-loop" style
of programming that breaks your algorithm into little pieces?

It has been 14 years since proffessor Tanenbaum said that "Linux is
obsolete" and "it's all over but the shoutin'. Why don't the
microkernels advocates have something that can compete with Linux in
its own problem space?

Are microkernels not just another form of "Bondage and Disipline"
programming from academia?

TB> For a different take on the whole issue of reliable operating systems,
TB> see this piece by Jonathan Shapiro entitled Debunking Linus's Latest.

Also worth reading is this criticism of microkernels from the TUNES
< 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
Body: No Text
How do you spell purple?