Structure of monolithic and microkernel-based operating systems, respectively

A microkernel is a minimal computer operating system kernel which, in its purest form, provides no operating-system services at all, only the mechanisms needed to implement such services, such as low-level address space management, thread management, and inter-process communication (IPC). A computer is a Machine that manipulates data according to a list of instructions. An operating system (commonly abbreviated OS and O/S) is the software component of a Computer system that is responsible for the management and coordination In Computer science, the kernel is the central component of most computer Operating systems (OS In Computing, an address space defines a range of discrete addresses each of which may correspond to a physical or virtual Memory register, a network host A thread in Computer science is short for a thread of execution. Inter-Process Communication ( IPC) is a set of techniques for the exchange of data among two or more threads in one or more processes. If the microkernel has a kernelmode-usermode distinction, the microkernel is the only part of the system executing in a kernel mode. The actual operating-system services are provided by "user-mode" servers. These include device drivers, protocol stacks, file systems and user-interface code. In computing a device driver or software driver is a Computer program allowing higher-level computer programs to interact with a Hardware device A protocol stack (sometimes communications stack) is a particular software implementation of a Computer networking protocol suite In Computing, a file system (often also written as filesystem) is a method for storing and organizing Computer files and the data they contain to make The user interface (or Human Computer Interface) is the aggregate of means by which people&mdash the users '&mdash interact with the System

This results in a system structure that is drastically different from the monolithic kernels of the mass market. A monolithic kernel is a kernel architecture where the entire kernel is run in Kernel space in Supervisor mode. The latter traditionally have a vertically-layered structure, where applications obtain services by performing a specific system call for each service. In Computing, a system call is the mechanism used by an application program to request service from the Kernel. In contrast, a microkernel-based system features a horizontal structure, where system services are obtained by executing an IPC system call addressed to a particular server.

Microkernels are closely related to exokernels. Exokernel is an Operating system kernel developed by the MIT Parallel and Distributed Operating Systems group and also a class of similar operating systems They also have much in common with hypervisors, but the latter make no claim to minimality, and are specialized to supporting virtual machines. In Computing, a hypervisor, also called virtual machine monitor, is a virtualization platform that allows multiple Operating systems to run on In Computer science, a virtual machine (VM is a Software implementation of a machine (computer that executes programs like a real machine The L4 microkernel is frequently used as a hypervisor, which indicates that a microkernel is a possible implementation of a hypervisor. L4 is a family of second-generation Microkernels based on theoriginal designs and implementations by German Computer scientist Jochen Liedtke. The term nanokernel is historically used to differentiate from earlier microkernels which contained actual system services, but the minimality principle used by Jochen Liedtke in the design of the L4 microkernel implies that these terms have the same meaning; microkernel is the modern terminology. Jochen Liedtke (1953 &ndash 10 June 2001) was a German Computer scientist, noted for his work on Microkernels especially the creation L4 is a family of second-generation Microkernels based on theoriginal designs and implementations by German Computer scientist Jochen Liedtke.

Introduction

Early operating system kernels were rather small, partly because computer memory was limited. As the capability of computers grew, the number of devices the kernel had to control also grew. Early versions of UNIX had kernels of quite modest size, even though those kernels contained device drivers and file system managers. Unix (officially trademarked as UNIX, sometimes also written as Unix with Small caps) is a computer When address spaces increased from 16 to 32 bits, kernel design was no longer cramped by the hardware architecture, and kernels began to grow. (See History of Unix). Unix (officially trademarked as UNIX, sometimes also written as Unix with Small caps) is a computer

Berkeley UNIX (BSD) began the era of big kernels. In addition to operating a basic system consisting of the CPU, disks and printers, BSD started adding additional file systems, a complete TCP/IP networking system, and a number of "virtual" devices that allowed the existing programs to work invisibly over the network. In Computing, a file system (often also written as filesystem) is a method for storing and organizing Computer files and the data they contain to make A protocol stack (sometimes communications stack) is a particular software implementation of a Computer networking protocol suite This growth continued for several decades, resulting in kernels with millions of lines of source code. In Computer science, source code (commonly just source or code) is any sequence of statements or declarations written in some Human-readable As a result of this growth, kernels were more prone to bugs and became increasingly difficult to maintain.

The microkernel was designed to address the increasing growth of kernels and the difficulties that came with them. In theory, the microkernel design allows for easier management of code due to its division into user-space services. "kernel space" redirects here For mathematical definition see Null space. This also allows for increased security and stability resulting from the reduced amount of code running in kernel mode.

For example, if a networking service crashed due to buffer overflow, only the networking service's memory would be corrupted, leaving the rest of the system still functional. In Computer security and programming, a buffer overflow, or buffer overrun, is an anomalous condition where a process attempts to On a traditional monolithic kernel, the overflow could possibly corrupt the memory of other drivers and possibly the kernel itself, which could crash the entire system.

Inter-process communication

Inter-process communication (IPC) is any mechanism which allows separate processes to communicate with each other, usually by sending messages. Inter-Process Communication ( IPC) is a set of techniques for the exchange of data among two or more threads in one or more processes. A message in its most general meaning is an object of Communication. (Shared memory is strictly speaking also an inter-process communication mechanism, but the acronym IPC usually only refers to message passing, and it is the latter that is particularly relevant to microkernels. In Computing, shared memory is a memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies ) This allows the operating system to be built from a number of small programs called servers, which are used by other programs on the system, invoked via IPC. Most or all support for peripheral hardware is handled in this fashion, with servers for device drivers, network protocol stacks, file systems, graphics, etc.

IPC can be synchronous or asynchronous. Asynchronous IPC is analogous to network communication: the sender dispatches a message and continues executing. The receiver checks (polls) for the availability of the message by attempting a receive, or is alerted to it via some notification mechanism. Asynchronous IPC requires that the kernel maintains buffers and queues for messages, and deals with buffer overflows; it also requires double copying of messages (sender to kernel and kernel to receiver). In synchronous IPC, the first party (sender or receiver) blocks until the other party is ready to perform the IPC. It does not require buffering or multiple copies, but the implicit rendezvous can make programming tricky. Most programmers prefer asynchronous send and synchronous receive.

First-generation microkernels typically supported synchronous as well as asynchronous IPC, and suffered from poor IPC performance. Jochen Liedtke identified design and implementation of the IPC mechanisms as the underlying reason for this poor performance. Jochen Liedtke (1953 &ndash 10 June 2001) was a German Computer scientist, noted for his work on Microkernels especially the creation In his L4 microkernel he pioneered techniques that lead to an order-of-magnitude reduction of IPC costs. L4 is a family of second-generation Microkernels based on theoriginal designs and implementations by German Computer scientist Jochen Liedtke. ^[1] These include an IPC system call that supports a send as well as a receive operation, making all IPC synchronous, and passing as much data as possible in registers. Furthermore, Liedtke introduced the concept of the direct process switch, where during an IPC execution an (incomplete) context switch is performed from the sender directly to the receiver. A context switch is the Computing process of storing and restoring the state ( context) of a CPU such that multiple processes can share If, as in L4, part or all of the message is passed in registers, this transfers the in-register part of the message without any copying at all. Furthermore, the overhead of invoking the scheduler is avoided; this is especially beneficial in the common case where IPC is used in an RPC-type fashion by a client invoking a server. Remote procedure call ( RPC) is an Inter-process communication technology that allows a Computer program to cause a Subroutine or procedure to Another optimization, called lazy scheduling, avoids traversing scheduling queues during IPC by leaving threads that block during IPC in the ready queue. Once the scheduler is invoked, it moves such threads to the appropriate waiting queue. As in many cases a thread gets unblocked before the next scheduler invocation, this approach saves significant work. Similar approaches have since been adopted by QNX and Minix 3. QNX (pronounced either Q-N-X or Q-nix is a commercial Unix-like Real-time operating system, aimed primarily at the Embedded systems market MINIX 3 is a project to create a small highly reliable and functional Unix-like Operating system.

In a client-server system, most communication is essentially synchronous, even if using asynchronous primitives, as the typical operation is a client invoking a server and then waiting for a reply. As it also lends itself to more efficient implementation, modern microkernels generally follow L4's lead and only provide a synchronous IPC primitive. Asynchronous IPC can be implemented on top by using helper threads. However, versions of L4 deployed in commercial products have found it necessary to add an asynchronous notification mechanism to better support asynchronous communication. This signal-like mechanism does not carry data and therefore does not require buffering by the kernel. A signal is a limited form of Inter-process communication used in Unix, Unix-like, and other POSIX -compliant operating systems

As synchronous IPC blocks the first party until the other is ready, unrestricted use could easily lead to deadlocks. Furthermore, a client could easily mount a denial-of-service attack on a server by sending a request and never attempting to receive the reply. Therefore synchronous IPC must provide a means to prevent indefinite blocking. Many microkernels provide timeouts on IPC calls, which limit the blocking time. In Telecommunication and related engineering (including Computer networking and programming) the term timeout or time-out has several meanings In practice, choosing sensible timeout values is difficult, and systems almost inevitably use infinite timeouts for clients and zero timeouts for servers. As a consequence, the trend is towards not providing arbitrary timeouts, but only a flag which indicates that the IPC should fail immediately if the partner is not ready. This approach effectively provides a choice of the two timeout values of zero and infinity. Recent versions of L4 and MInix have gone down this path (older versions of L4 used timeouts, as does QNX).

Servers

Microkernel servers are essentially daemon programs like any others, except that the kernel grants some of them privileges to interact with parts of physical memory that are otherwise off limits to most programs. In Unix and other computer multitasking Operating systems a daemon (ˈdiːmən or /ˈdeɪmən/ is a Computer program that runs in the background This allows some servers, particularly device drivers, to interact directly with hardware.

A basic set of servers for a general-purpose microkernel includes file system servers, device driver servers, networking servers, display servers, and user interface device servers. This set of servers (drawn from QNX) provides roughly the set of services offered by a monolithic UNIX kernel. QNX (pronounced either Q-N-X or Q-nix is a commercial Unix-like Real-time operating system, aimed primarily at the Embedded systems market The necessary servers are started at system startup and provide services, such as file, network, and device access, to ordinary application programs. With such servers running in the environment of a user application, server development is similar to ordinary application development, rather than the build-and-boot process needed for kernel development.

Additionally, many "crashes" can be corrected for by simply stopping and restarting the server. Crash-only software refers to Computer programs that handle failures by simply restarting without attempting any sophisticated recovery (In a traditional system, a crash in any of the kernel-resident code would result in the entire machine crashing, forcing a reboot. ) However, part of the system state is lost with the failing server, hence this approach requires applications to cope with failure. A good example is a server responsible for TCP/IP connections: If this server is restarted, applications will experience a "lost" connection, a normal occurrence in networked system. The Internet Protocol Suite (commonly TCP/IP) is the set of Communications protocols used for the Internet and other similar networks For other services, failure is less expected and may require changes to application code. For QNX, restart capability is offered as the QNX High Availability Toolkit. ^[2]

In order to make all servers restartable, some microkernels have concentrated on adding various database-like techniques like transactions, replication and checkpointing in order to preserve essential state across single server restarts. A Computer Database is a structured collection of records or data that is stored in a computer system A database transaction is a unit of work performed against a Database management system or similar system that is treated in a coherent and reliable way independent of other Replication is the process of sharing information so as to ensure consistency between redundant resources such as Software or Hardware components to improve reliability Checkpointing is a technique for inserting Fault tolerance into Computing systems An example is ChorusOS, which was targeted at high-availability applications in the telecommunications world. ChorusOS is a Microkernel Real-time operating system designed for Embedded systems. Chorus included features to allow any "properly written" server to be restarted at any time, with clients using those servers being paused while the server brought itself back into its original state. However, such kernel features are incompatible with the minimality principle, and are therefore not provided in modern microkernels, which instead rely on appropriate user-level protocols.

Device drivers

Device drivers frequently perform direct memory access (DMA), and therefore can write to arbitrary locations of physical memory, including over kernel data structures. In computing a device driver or software driver is a Computer program allowing higher-level computer programs to interact with a Hardware device Direct memory access ( DMA) is a feature of modern Computers and Microprocessors that allows certain hardware subsystems within the computer to access system Such drivers must therefore be trusted. It is a common misconception that this means that they must be part of the kernel. In fact, a driver is not inherently more or less trustworthy by being part of the kernel.

While running a device driver in user mode does not necessarily reduce the damage a misbehaving driver can cause, in practice it is beneficial for system stability in the presence of buggy (rather than malicious) drivers: memory-access violations by the driver code itself (as opposed to the device) may still be caught by the memory-management hardware. Furthermore, many devices are not DMA-capable, their drivers can be made untrusted by running them in user mode. Recently, an increasing number of computers feature IOMMUs, many of which can be used to restrict a device's access to physical memory. In Computing, an input/output memory management unit ( IOMMU) is a Memory management unit (MMU that connects a DMA -capable I/O bus ^[3] (IBM mainframes have had IO MMUs since the IBM System/360 Model 67 and System/370. System/360|History of CP/CMS|History of IBM The IBM System/360 Model 67 ( S/360-67) was an important IBM mainframe model in the late 1960s. The IBM System/370 (often S/370) was a model range of IBM mainframes announced on June 30, 1970 ) This also allows user-mode drivers to become untrusted.

User-mode drivers actually predate microkernels. The Michigan Terminal System (MTS), in 1967, supported user-space drivers, the first operating system to be designed with that capability. Michigan Terminal System ( MTS) is an Operating system for the IBM System/360 and its successors that was developed jointly by the following institutions ^[4] Historically, drivers were less of a problem, as the number of devices was small and trusted anyway, so having them in the kernel simplified the design and avoided potential performance problems. This led to the traditional driver-in-the-kernel style of UNIX, Linux, and Windows. ^[5] With the proliferation of various kinds of peripherals, the amount of driver code escalated and in modern operating systems dominates the kernel in terms of code size.

Essential components & minimality

As a microkernel must allow building arbitrary operating-system services on top, it must provide some core functionality. At the least this includes:

• some mechanisms for dealing with address spaces — this is required for managing memory protection;
• some execution abstraction to manage CPU allocation — typically threads or scheduler activations; and
• inter-process communication — required to invoke servers running in their own address spaces. In Computing, an address space defines a range of discrete addresses each of which may correspond to a physical or virtual Memory register, a network host A thread in Computer science is short for a thread of execution. Inter-Process Communication ( IPC) is a set of techniques for the exchange of data among two or more threads in one or more processes.

This minimal design was pioneered by Brinch Hansen's Nucleus and the hypervisor of IBM's VM. Per Brinch Hansen (November 13 1938 - July 31 2007 was a Danish-American Computer scientist known for Concurrent programming theory The RC 4000 Multiprogramming System was an Operating system developed for the RC 4000 Minicomputer in 1969 CP/CMS|History of CP/CMS VM (often VM/CMS) refers to a family of IBM Virtual machine Operating systems used on IBM System/370 It has since been formalised in Liedtke's minimality principle:

A concept is tolerated inside the microkernel only if moving it outside the kernel, i. e. , permitting competing implementations, would prevent the implementation of the system's required functionality. ^[6]

Everything else can be done in a user program, although device drivers implemented as user programs may require special privileges to access I/O hardware.

Related to the minimality principle, and equally important for microkernel design, is the separation of mechanism and policy, it is what enables the construction of arbitrary systems on top of a minimal kernel. The Separation of mechanism and Policy is a fundamental design principle in the field of Computer science. Any policy built into the kernel cannot be overwritten at user level and therefore limits the generality of the microkernel. ^[7] Policy implemented in user-level servers can be changed by replacing the servers (or letting the application chose between competing servers offering similar services).

For efficiency, most microkernels contain schedulers and manage timers, in violation of the minimality principle and the principle of policy-mechanism separation.

Start up (booting) of a microkernel-based system requires device drivers, which are not part of the kernel. In Computing, booting ( booting up) is a bootstrapping process that starts Operating systems when the user turns on a Computer system In computing a device driver or software driver is a Computer program allowing higher-level computer programs to interact with a Hardware device Typically this means that they are packaged with the kernel in the boot image, and the kernel supports a bootstrap protocol that defines how the drivers are located and started. Some microkernels simplify this by placing some key drivers inside the kernel (in violation of the minimality principle), LynxOS and the original Minix are examples. LynxOS does not refer to the operating system for the Atari Lynx Game console. MINIX is a Unix-like computer Operating system based on a Microkernel architecture. Some even include a file system in the kernel to simplify booting. In Computing, a file system (often also written as filesystem) is a method for storing and organizing Computer files and the data they contain to make

A key component of a microkernel is a good IPC system. Inter-Process Communication ( IPC) is a set of techniques for the exchange of data among two or more threads in one or more processes. Since all services are performed by usermode programs, efficient means of communication between programs are essential, far more so than in monolithic kernels. The design of the IPC system makes or breaks a microkernel. To be effective, the IPC system must not only have low overhead, but also interact well with CPU scheduling.

Performance

Obtaining a service is inherently more expensive in a microkernel-based system than a monolithic system. ^[7] In the monolithic system, the service is obtained by a single system call, which requires two mode switches (changes of the processor's privilege level). The concept of privilege level refers to protecting resources on a CPU. In the microkernel-based system, the service is obtained by sending an IPC message to a server, and obtaining the result in another IPC message from the server. This requires a context switch if the drivers are implemented as processes, or a function call if they are implemented as procedures. A context switch is the Computing process of storing and restoring the state ( context) of a CPU such that multiple processes can share In addition, passing actual data to the server and back may incur extra copying overhead, while in a monolithic system the kernel can directly access the data in the client's buffers.

Performance is therefore a potential issue in microkernel systems. Indeed, the experience of first-generation microkernels such as Mach and Chorus showed that systems based on them performed very poorly. Mach is an Operating system Microkernel developed at Carnegie Mellon University to support operating system research primarily distributed and parallel ^[8] However, Jochen Liedtke showed that Mach's performance problems were the result of poor design and implementation, and specifically Mach's excessive cache footprint. Jochen Liedtke (1953 &ndash 10 June 2001) was a German Computer scientist, noted for his work on Microkernels especially the creation In Computer science, a cache (kæʃ like "cash") is a collection of data duplicating original ^[6] Liedtke demonstrated with his own L4 microkernel that through careful design and implementation, and especially by following the minimality principle, IPC costs could be reduced by more than an order of magnitude compared to Mach. L4 is a family of second-generation Microkernels based on theoriginal designs and implementations by German Computer scientist Jochen Liedtke. L4's IPC performance is still unbeaten across a range of architectures. ^[9][10][11]

While these results demonstrate that the poor performance of systems based on first-generation microkernels is not representative for second-generation kernels such as L4, this constitutes no proof that microkernel-based systems can be built with good performance. It has been shown that a monolithic Linux server ported to L4 exhibits only a few percent overhead over native Linux. ^[12] However, such a single-server system exhibits few, if any, of the advantages microkernels are supposed to provide by structuring operating-system functionality into separate servers.

A number of commercial multi-server systems exist, in particular the realtime systems QNX and Integrity. QNX (pronounced either Q-N-X or Q-nix is a commercial Unix-like Real-time operating system, aimed primarily at the Embedded systems market INTEGRITY is a Real-time operating system (RTOS produced and marketed by Green Hills Software. No comprehensive comparison of performance relative to monolithic systems has been published for those multiserver systems. Furthermore, performance does not seem to be the overriding concern for those commercial systems, which instead emphasize simplicity for the sake of robustness. An attempt to build a high-performance multiserver operating system was the IBM Sawmill Linux project. ^[13] However, this project was never completed.

It has been shown in the meantime that user-level device drivers can come close to the performance of in-kernel drivers even for such high-throughput, high-interrupt devices as Gigabit Ethernet. ^[14] This seems to imply that high-performance multi-server systems are possible.

Security

The security benefits of microkernels have been frequently discussed. ^[15][16] In the context of security the minimality principle of microkernels is a direct consequence of the principle of least privilege, according to which all code should have only the privileges needed to provide required functionality. In Information security, Computer science, and other fields the principle of least privilege, also known as the principle of minimal privilege or just Minimality requires that a system's trusted computing base (TCB) should be kept minimal. The trusted computing base (TCB of a Computer system is the set of all hardware, Firmware, and/or software components that are critical to its As the kernel (the code that executes in the privileged mode of the hardware) is always part of the TCB, minimizing it is natural in a security-driven design.

Consequently, microkernel designs have been used for systems designed for high-security applications, including KeyKOS, EROS and military systems. KeyKOS is a persistent, pure capability-based Operating system for the IBM S/370 mainframe Computers It allowed EROS ( The Extremely Reliable Operating System) is an Operating system developed by The EROS Group LLC In fact common criteria (CC) at the highest assurance level (EAL7) has an explicit requirement that the target of evaluation be “simple”, an acknowledgment of the practical impossibility of establishing true trustworthiness for a complex system. The Common Criteria for Information Technology Security Evaluation (abbreviated as Common Criteria or CC) is an International standard ( ISO /

Recent work on microkernels is focusing on formal specifications of the kernel API, and formal proofs of security properties of the API. The first example of this is a mathematical proof of the confinement mechanisms in EROS, based on a simplified model of the EROS API. ^[17] More recently, a comprehensive set of machine-checked proofs has been performed of the properties of the protection model of the seL4 version of L4. ^[18]

Some projects go even further, aiming at complete formal verification, i. e. a mathematical proof that the kernel's implementation is consistent with its specification, which then provides a guarantee that the properties proved about the API actually hold for the real kernel. This degree of assurance goes beyond even CC EAL7. Such proofs are being attempted for Coyotos and seL4. Coyotos is a capability-based security-focused Microkernel Operating system being developed by The EROS Group LLC

See also

• Kernel (computer science)
  • Exokernel, a research kernel architecture with a more minimalist approach to kernel technology. In Computer science, the kernel is the central component of most computer Operating systems (OS Exokernel is an Operating system kernel developed by the MIT Parallel and Distributed Operating Systems group and also a class of similar operating systems
  • Hybrid kernel
  • Monolithic kernel
  • Modular kernel
  • Nanokernel
• Trusted computing base

Notes

Further reading

• scientific articles about microkernels (on CiteSeer), including:
  • Dan Hildebrand (1992). CiteSeer is a public search engine and Digital library for scientific and academic papers "An Architectural Overview of QNX". Proceedings of the Workshop on Micro-kernels and Other Kernel Architectures: 113–126. ISBN 1-880446-42-1.   - the basic QNX reference.
  • Tanenbaum, A. , Herder, J. and Bos, H. (May 2006). "Can We Make Operating Systems Reliable and Secure?". Computer: 44–51.   -the basic reliable reference.
  • Black, D. L. , Golub, D. B. , Julin, D. P. , Rashid, R. F. , Draves, R. P. , Dean, R. W. , Forin, A. , Barrera, J. , Tokuda, H. , Malan, G. , and Bohman, D. (March 1992). "Microkernel Operating System Architecture and Mach". J. of Information Processing 14(4).   - the basic Mach reference.
  • Heiser, Gernot; Uhlig, Volkmar and LeVasseur, Joshua (January 2006). "Are Virtual-Machine Monitors Microkernels Done Right?". ACM SIGOPS Operating Systems Review 40 (1): 95–99. ACM. doi:10.1145/1113361.1113363. A digital object identifier ( DOI) is a permanent identifier given to an Electronic document.  
• MicroKernel page from the Portland Pattern Repository
• The Tanenbaum-Torvalds debate
  • The Tanenbaum-Torvalds Debate, 1992.01.29
  • Tanenbaum, A. The Portland Pattern Repository ( PPR) is a repository for computer programming design patterns It was accompanied by a companion website WikiWikiWeb, which The Tanenbaum-Torvalds debate is a debate between Andrew S Tanenbaum and Linus Torvalds, regarding Linux and kernel architecture in general S. "Can We Make Operating Systems Reliable and Secure?".
  • Torvalds, L. Linus Torvalds about the microkernels again, 2006.05.09
  • Shapiro, J. "Debunking Linus's Latest".
  • Tanenbaum, A. S. "Tanenbaum-Torvalds Debate: Part II".