Micro-Kernels: Micro-Kernels Ref: Liedtke paper


The “Linux is obsolete” Debate [1992](from http://www.oreilly.com/catalog/opensources/book/appa.html): The “Linux is obsolete” Debate [1992] (from http://www.oreilly.com/catalog/opensources/book/appa.html) Andy Tanenbaum: “As a result of my occupation, I think I know a bit about where operating [systems] are going in the next decade or so. Two aspects stand out: MICROKERNEL VS MONOLITHIC SYSTEM Most older operating systems are monolithic, that is, the whole operating system is a single a.out file that runs in 'kernel mode.' This binary contains the process management, memory management, file system and the rest. Examples of such systems are UNIX, MS-DOS, VMS, MVS, OS/360, MULTICS, and many more. The alternative is a microkernel-based system, in which most of the OS runs as separate processes, mostly outside the kernel. They communicate by message passing. The kernel's job is to handle the message passing, interrupt handling, low-level process management, and possibly the I/O. Examples of this design are the RC4000, Amoeba, Chorus, Mach, and the not-yet-released Windows/NT. While I could go into a long story here about the relative merits of the two designs, suffice it to say that among the people who actually design operating systems, the debate is essentially over. Microkernels have won. The only real argument for monolithic systems was performance, and there is now enough evidence showing that microkernel systems can be just as fast as monolithic systems (e.g., Rick Rashid has published papers comparing Mach 3.0 to monolithic systems) that it is now all over but the shoutin'. MINIX is a microkernel-based system. The file system and memory management are separate processes, running outside the kernel. The I/O drivers are also separate processes (in the kernel, but only because the brain-dead nature of the Intel CPUs makes that difficult to do otherwise). LINUX is a monolithic style system. This is a giant step back into the 1970s. That is like taking an existing, working C program and rewriting it in BASIC. To me, writing a monolithic system in 1991 is a truly poor idea.”


The “Linux is obsolete” Debate (cont.): The “Linux is obsolete” Debate (cont.) Andy Tanenbaum: “PORTABILITY Once upon a time there was the 4004 CPU. When it grew up it became an 8008. Then it underwent plastic surgery and became the 8080. It begat the 8086, which begat the 8088, which begat the 80286, which begat the 80386, which begat the 80486, and so on unto the N-th generation. In the meantime, RISC chips happened, and some of them are running at over 100 MIPS. Speeds of 200 MIPS and more are likely in the coming years. These things are not going to suddenly vanish. What is going to happen is that they will gradually take over from the 80x86 line. They will run old MS-DOS programs by interpreting the 80386 in software. (I even wrote my own IBM PC simulator in C, which you can get by FTP from ftp.cs.vu.nl = 192.31.231.42 in dir minix/simulator.) I think it is a gross error to design an OS for any specific architecture, since that is not going to be around all that long. MINIX was designed to be reasonably portable, and has been ported from the Intel line to the 680x0 (Atari, Amiga, Macintosh), SPARC, and NS32016. LINUX is tied fairly closely to the 80x86. Not the way to go. Don't get me wrong, I am not unhappy with LINUX. It will get all the people who want to turn MINIX in BSD UNIX off my back. But in all honesty, I would suggest that people who want a **MODERN** "free" OS look around for a microkernel-based, portable OS, like maybe GNU or something like that.”


“Linux is obsolete” (cont.): “Linux is obsolete” (cont.) Linus Torvalds: >1. MICROKERNEL VS MONOLITHIC SYSTEM True, linux is monolithic, and I agree that microkernels are nicer. With a less argumentative subject, I'd probably have agreed with most of what you said. From a theoretical (and aesthetical) standpoint linux looses. If the GNU kernel had been ready last spring, I'd not have bothered to even start my project: the fact is that it wasn't and still isn't. Linux wins heavily on points of being available now. > MINIX is a microkernel-based system. [deleted, but not so that you > miss the point ] LINUX is a monolithic style system. If this was the only criterion for the "goodness" of a kernel, you'd be right. What you don't mention is that minix doesn't do the micro-kernel thing very well, and has problems with real multitasking (in the kernel). If I had made an OS that had problems with a multithreading filesystem, I wouldn't be so fast to condemn others: in fact, I'd do my damndest to make others forget about the fiasco. [ yes, I know there are multithreading hacks for minix, but they are hacks, and bruce evans tells me there are lots of race conditions ]


“Linux is obsolete” (cont.): “Linux is obsolete” (cont.) Linus Torvalds: >2. PORTABILITY "Portability is for people who cannot write new programs" -me, right now (with tongue in cheek) The fact is that linux is more portable than minix. What? I hear you say. It's true - but not in the sense that ast means: I made linux as conformant to standards as I knew how (without having any POSIX standard in front of me). Porting things to linux is generally /much/ easier than porting them to minix. I agree that portability is a good thing: but only where it actually has some meaning. There is no idea in trying to make an operating system overly portable: adhering to a portable API is good enough. The very /idea/ of an operating system is to use the hardware features, and hide them behind a layer of high-level calls. That is exactly what linux does: it just uses a bigger subset of the 386 features than other kernels seem to do. Of course this makes the kernel proper unportable, but it also makes for a /much/ simpler design. An acceptable trade-off, and one that made linux possible in the first place.


Approaches to OS Organization: Approaches to OS Organization Macro-Kernels (aka Monolithic kernels) High-level interface over hardware System calls to provide services for process management, concurrency, memory management that all run in supervisor mode Tightly integrated code, all parts of kernel operate under one address space; can be made highly efficient But an error in one module can bring entire system down Examples: BSD Unix, Linux, older systems (e.g., OS/360) Micro-Kernels Low-level interface over hardware System calls implement minimal amount of functionality, rest is implemented outside the kernel via servers What does this mean? Return to this later Servers operate in different address spaces Examples: Mach, Spring OS (Sun)


Micro- vs. Macro-Kernel: Micro- vs. Macro-Kernel Micro-kernels offer More modular structure (though monolithic kernels can also be modular) Fault isolation: fault in one server does not bring down other services (just like user processes) System more flexible and tailorable - different strategies implemented in different servers (with different APIs) can co-exist within the same system Disadvantages of Micro-kernels (conventional wisdom) Slower (e.g., due to more address space changes) Not sufficiently flexible Liedtke argues this is not the case


What is in the Micro-Kernel?: What is in the Micro-Kernel? Functionality should determine this, not performance Traditional performance bottlenecks can be eliminated, e.g., author reports 22x faster IPC than Mach micro-kernel Put in microkernel only if leaving it outside (allowing competing implementations) would prevent implementing required OS functionality Independence between subsystems: must be able to implement an arbitrary subsystem S so that it cannot be disturbed or corrupted by another subsystem S’ Integrity: Must be a way for S1 to address S2 and establish a communication channel that can neither be corrupted nor eavesdropped by S’ Based on this principal, kernel should implement only three things Address spaces (independence) Threads and IPC (independence and integrity) Unique identifiers (integrity)


Address Spaces: Address Spaces Fundamental concepts: Initial address space that represents physical memory, three operations to implement protected address spaces above it Map Owner of address space A maps page into another address space B Page can be accessed in both address spaces Receipient has to agree Mapper can only map pages it can already access Grant Like map, but owner gives up access to the page Used in specialized cases: when a server is an intermediary passing on pages Flush If A flushes a page, the page is removed from address spaces that received the page from A through a (direct or indirect) grant or map


Example Address Space Use: Example Address Space Use A memory manager is just a process (server) managing the initial address space, entirely outside the kernel Standard pager process maps pages to memory manager process Memory managers can be stacked: one can grant parts of the physical memory to a second manager, other parts to a third memory manager [e.g., to help implement virtual machines] A pager can be a totally separate server, communicating through IPC Of course, it could also be integrated in a memory manager Allows one to easily implement specialized policies (e.g., real-time)


Threads and IPC: Threads and IPC Thread is an activity executing inside an address space Thread = registers, PC, SP, State, address space in which it executes Thread management must be part of the kernel. Why? Thread may modify (corrupt) address space For protection reasons, kernel must control accesses to a thread’s address space Follows that cross-address space communication (IPC) must also be within kernel IPC enforces rules (agreements between sender and receiver) for communications Needed for grant and map address space operations Interrupt can be viewed as hardware “threads” sending messages to other interrupt handler threads; interrupt handling code outside the micro-kernel


Unique Identifiers: Unique Identifiers Micro-kernel must assign unique identifiers (uid) for something (threads or tasks or communication channels) If S1 wants to send a message to S2, the micro-kernel must know which uid corresponds to S2


Flexibility: Examples: Flexibility: Examples Allows for multiple memory managers/pagers to be implemented outside microkernel, as discussed earlier Device drivers can be implemented outside microkernel as ordinary processes Access hardware I/O ports by having them mapped into its address space Process interrupts via IPC mechanism RPC can be implemented outside microkernel as communications servers that talk to network device drivers through IPC Unix system calls can be implemented by a Unix server process


Performance: Performance Concern: Micro-kernel based OS can suffer from poor performance due to switching between kernel and user mode, switching between address spaces, context switching between threads True? Liedtke argues no! Look at the concept, not a particular implementation


Kernel-User Mode Switches: Kernel-User Mode Switches Calling kernel from user mode essentially Indirect procedure call Switch from user to kernel stack Setting internal “kernel bit” to allow privileged instructions Cost (50 MHz x86 machine) 71 cycles for call, 36 cycles for return Measured cost (Mach kernel): 900 cycles! Liedtke argues this is a solvable implementation artifact; counter example is L3 kernel takes 15 extra cycles (plus if infrequent, 3 TLB misses, 10 cache misses) or total 123 to 180 cycles (misses cost more today)


Address Space Switches: Address Space Switches Main cost is in TLB (Translation lookaside buffer) that caches recent virtual to physical page mappings Tagged TLB: keep address space tag to distinguish between virtual addresses from different address spaces, allowing TLB to hold translations for different virtual address spaces Cost is loading TLB entries for micro-kernel when invoked; OK if microkernel has small memory footprint Untagged: must flush TLB when switching to a new process (virtual address space) Costly to reload TLB Idea: map several address spaces into one linear address space, e.g., keep small commonly used server address spaces shared with large user address spaces Liedtke argues cost can be kept low


Thread Switches and IPC: Thread Switches and IPC Similarly, RPC can be made very fast with careful design 10 microseconds round trip time for RPC on several OS’s (e.g., Spring, L3)


Memory Effects: Memory Effects Measurements of microkernel implementation (Mach + Unix server) have less efficient cache behavior compared to a monolithic (Ultrix) kernel Liedtke tracks problem down to cache misses in microkernel, which can be solved by reducing working set size of microkernel implementation (his L3 microkernel OS demonstrates this), e.g., IPC implementation


Portability: Portability Argues microkernel are inherently not portable; must be optimized to exploit hardware details to obtain reasonable performance Take advantage of hardware details for fastest possible implementation Algorithms in microkernel processor dependent Describes case study porting from 486 to Pentium So Liedtke agrees with Linus Torvalds on this issue, while (ironically) making the case for microkernels!


Summary: Summary Makes case for microkernels Modularity, flexibility Common concerns regarding performance can be overcome with careful design Methodology: Be careful with empirical measurements! You may be seeing implementation artifacts rather than fundamental behaviors