L4 microkernel family
|
|
Template:NPOV L4 is, collectively, a family of related computer programs. They are microkernels that are becoming well known in the computer industry for their excellent performance and small footprint. Originally L4 was a single product, a highly-tuned Intel i386 kernel designed and implemented by Jochen Liedtke. Since then the system has seen dramatic development in a number of directions, notably in producing a more platform-independent version known as Pistachio, as well as ports to a number of different hardware architectures.
| Contents |
First generation microkernels
One of the key concepts in the Unix operating system is the use of a large number of small programs that can be strung together to complete a task. Instead of a large text-manipulation program, for instance, Unix users could "pipe" the source text file through a series of single-purpose utility programs to achieve the same end. Although the results were the same, the Unix model allowed for considerably more flexibility; the user could add or remove parts of the pipeline using existing commands for launching programs. It also made development much easier, as each program was small and dedicated to a single role, making it much easier to understand and debug.
Under Unix, the "operating system" consists of many of these utilities along with the master control program, the kernel. The kernel's job is to schedule execution of the rest of the programs on the system, as well as control all hardware to avoid problems if two programs attempt to access the same device at the same time. In order to mediate such access, the kernel was given special rights on the system, running in supervisor mode. Although it was a program like any other, the extra privileges led to the concept of programs running in user-space and kernel-space.
Originally the kernel was fairly small, but as the capability of computers grew the number of devices the kernel had to control also grew. Many of these no longer fit into a model based on files; for instance, you can't effectively treat networking as a file. More and more code was included into the kernel to handle these sorts of tasks, and the kernels grew. Modern Unix systems are extremely large; the Linux kernel consists of 33 million lines of code.
Microkernels were an attempt to break out of the ever-growing kernels and return to a system in which most tasks would be completed by stringing together a series of smaller operations. The key problem under Unix had been trying to model the entire world as files, which no longer seemed to apply. Instead the microkernels took a step back and considered pipes as a specific example of a much more general concept, inter-process communications, or IPC. IPC could be used to emulate Unix-style pipes, but it could also be used for practically any other task, passing data at high speed between programs.
With IPC the operating system can once again be built up of a number of small programs. Networking could be removed from the kernel and placed in a separate user-space program, which would be called by other programs on the system. All hardware support would be handled in this fashion, with programs for networking, file systems, graphics, etc. These system-related programs were known as servers in Mach-speak, and as the Mach model served as the basis for most microkernel development, these names have stuck.
The system would look as if it had a full Unix kernel, the fact that the networking support was being "handed off" would be invisible. That system would be considerably easier to maintain; instead of a single 33 million-line kernel, there would be a series of smaller programs instead. Additionally the user could choose what capabilities they needed and run only those programs, allowing them to tailor the system for their needs. The same sort of changes to a traditional kernel, now being referred to as a monolithic kernel or monokernel, is very difficult due to the high level of interconnections between parts of the system.
The role of the kernel in such a system is limited. In addition to providing basic task management (starting and stopping other programs), it would have to provide the IPC system and provide security. When booting the kernel would start up a series of servers to handle the hardware on the system, granting those servers additional rights as needed. New programs, those being started by the user, would use the IPC system to access hardware, calling the kernel to pass along messages after being checked for rights and validity. To handle these tasks, Mach included the concept of ports, which introduced filesystem-like endpoints into the IPC system, complete with rights for other programs to use them. For instance, a network server would hold the write permissions to the networking hardware, and keep a number of ports open for reading to allow other programs to call it. Other programs could not take over the networking hardware without the kernel specifically granting this access, and only after the networking server agreed to give up those rights.
The collection-of-servers model offered many advantages over traditional operating systems. By placing the majority of code in well-separated programs, development on such a system was considerably easier. Developing new networking stacks on a classic monolithic kernel (monokernel) required the entire kernel to be recompiled and rebooted, hard-crashing the machine if there was a bug. With a microkernel there was little chance that an updated networking system would do anything other than inconvenience you and require that one program to be relaunched. It also offered considerably more security and stability for the same reasons. Additionally the kernel itself was much smaller; later versions of Mach were only 44,000 lines of code.
Mach was originally intended to be a replacement for classic Unixen, and for this reason contained many Unix-like ideas. For instance, Mach used a permissioning and security system patterned on Unix's file system. Since the kernel was privileged (running in kernel-space) it was possible for malfunctioning or malicious programs to send it commands that would cause damage to the system, and for this reason the kernel checked every message for validity. Additionally most of the functionality was to be located in user-space programs, so this meant there needed to be some way for the kernel to grant these programs additional privileges, to operate on hardware for instance.
Some of Mach's more esoteric features were also based on this same IPC mechanism. For instance, Mach was able to support multi-processor machines with ease. In a traditional kernel extensive work needs to be carried out to make it re-entrant or interruptable, as programs running on different processors could call into the kernel at the same time. Under Mach, the bits of the operating system are isolated in servers, which are able to run, like any other program, on any processor. Although in theory the Mach kernel would also have to be re-entrant, in practice this isn't an issue because its response times are so fast it can simply wait and serve requests in turn. Mach also included a server that could forward messages not just between programs, but even over the network, which was an area of intense development in the late 1980s and early 1990s.
Unfortunately the use of IPC for almost all tasks turned out to have serious performance impact. Mach 3 systems running Unix were often 50% slower than their monokernel counterparts. Studies showed the vast majority of this performance hit, 73% by one measure, was due to the overhead of the IPC. And this was measured on a system with a single large server providing the operating system; breaking the system down further into smaller servers would only make the problem worse. It appeared the goal of a collection-of-servers was simply not possible.
Many attempts were made to improve the performance of Mach and Mach-like microkernels, but by the mid-1990s much of the early intense interest had died. The concept of an operating system based on IPC appeared to be dead, the idea itself flawed.
A second look
In fact further study of the exact nature of the performance problems turned up a number of interesting facts. One was that the IPC itself was not the problem: there was some overhead associated with the memory mapping needed to support it, but this added only a small amount of time to making a call. The rest, 80% of the time being spent, was due to additional tasks the kernel was running on the messages. Primary among these was the port rights checking and message validity. In tests on a 486DX-50 a standard Unix system call took 21 usecs to complete, on Mach 114. Only 18 usecs of this was hardware related, the rest was the Mach kernel running various routines on the message.
It was this realization that led a number of developers to re-examine the entire microkernel concept in the mid-1990s. Mach was adding considerable overhead to the IPC in order to support concepts that weren't really useful in anything but a Unix context. On a single-user system, like a cell phone for instance, permissions and rights checking was of considerably less importance. While Mach claimed to be a microkernel, it seemed that it actually contained far more ideas than it needed to, the IPC system was a classic example of a distributed cost.
Jochen Liedtke set out to prove that a thinner IPC layer, careful attention to performance, and machine-specific (as opposed to platform independant) design could yield massive real-world performance improvements. Instead of Mach's complex IPC system, his L3 simply passed the message without any additional overhead. Security and rights were considered to be duties of other user-space servers, if those services were needed at all. Additionally, L3 used a variety of mechanisms to physically pass the message, tuning each call to make maximal use of the hardware support (in registers), whereas Mach used a one-size-fits-all mechanism that sacrified speed for portability. The result of these changes was a massive reduction in IPC overhead. On the same system where Mach required 114 microseconds for even the smallest of messages, L3 could send the same message for less than 10. The overall time for a syscall was less than half that of Unix, as opposed to five times under Mach.
After using L3 Liedtke came to realize that several other Mach concepts were also misplaced. The result was the even simpler L4, so simple that it was also highly portable. It appears in retrospect that the vast majority of the performance problems could be solved without resorting to anything other than fresh design.
For instance, another major bottleneck in Mach compared to monokernels is that in a true "collection-of-servers" system the kernel had no real way to know how to effectively page memory. Developers using monokernels could, and did, spend considerable time trying to understand the exact nature of memory use in the kernel, and then tuning their system to take advantage of this knowledge. On a microkernel the developer had no idea what the system was made up of, and no way to closely monitor memory use except in specific cases.
Liedtke decided the solution to this problem was to simply remove paging from the kernel altogether, and allow each application to apply the sort of tuning formerly applied only to the monokernels. Under an L4 system the operating system (as opposed to the kernel) is expected to provide paging services, potentially in many varieties, allowing the developer to pick the one best suited to their workload. The kernel's role is reduced to knowing that such systems exist and providing a mechanism for supporting them. Under L4, this requires a total of three functions, grant, map and unmap.
In the end the philosophy of the design became minimallist; as the L4/MIPS authors stated, A feature should be in the microkernel if and only if security requires that the feature be implemented in privileged mode. This contrasts with Mach's, which focussed on cross-platform portability, multi-processor support and a host of other "next big things".
It is important to note that an operating system based on L4 has to provide services that the older generation microkernels included internally. For instance, in order to implement a secure Unix-like system, servers will have to provide the rights management that Mach included in the kernel. Additionally the messages will still have to be checked for validity, at least in most cases. Given this it remains unclear if the end-to-end performance of a "real world" operating system based on L4 will run significantly faster than one built on Mach. That said, tests of a Linux ported to run on top of L4, one ported to run on Mach (MkLinux) and the basic Linux system itself showed clear performance gains for L4. Even in the best case MkLinux was 15% slower than the monokernel, whereas L4 was about 5-10% slower. Additional development of certain portions of the Linux system, not carried out for the testing, was likely to improve this to some degree.
Ongoing development
Liedtke's original version of L4 was built for speed. In order to wring out every bit of performance, many of the critical sections were written in assembler language. His work caused a minor revolution in operating system design circles, and soon it was being studied by a number of universities, and not long after, IBM where Liedtke moved. At IBM a new version of L4 was created, Lemon Pip, followed by an effort to create a cross-platform version in C++, Lime Pip.
L4 development was also picked up at the University of Karlsruhe, where they developed L4Ka::Hazelnut, a C++ version that was intended to be run on any 32-bit machine. They were trying to determine if the overhead of a high-level language like C++ would offset the ease of programming that such a system would offer. The effort was a success, performance was still excellent, and with its release the Lime Pip project at IBM was ended. Hazelnut was eventually completely re-written for portability, 64-bit support and better performance, resulting in L4Ka::Pistachio.
Development also took place at the University of New South Wales, where developers attempted to study porting L4 to new platforms. Their work resulted in L4/MIPS and L4/Alpha, resulting in Liedtke's original version being retroactively named L4/x86. With the release of Pistachio, which they also worked on, development of these versions has ended.
Fiasco is a further development of the original L4 that includes hard real-time support, which is used as the basis of the DROPS operating system. For real-time use "fast" is not enough, so the Fiasco kernel is entirely re-entrant, allowing it to be interrupted at any time. Like other developments of the original L4, Fiasco is also written in C++ for readability and portability reasons. Fiasco also has a number of limitations originally intended to improve speed through reduced resource requirements, the most serious being a limitation to 256MB of RAM. Development appears to be dormant.
Almost all development today appears to be on the Pistachio kernel. The University of New South Wales now uses Pistachio to continue their experiments in portability, and the Pistachio kernel is now offered on a wide variety of hardware. Other teams explore real-time support, rolling in Fiasco-like concepts. Development of the basic kernel also continues at the University of Karlsruhe, who are working towards a new "Version 4" API (which Pistachio currently implements in beta).
The GNU Hurd project is considering adopting the L4 microkernel in place of Mach. Currently, a design which aims to address the short comings of Mach within the L4 framework exists and the developpers are working on fleshing out an implementation.
External links
- L4Hq (http://www.l4hq.org/) - L4 headquarters, community site for L4 projects
- L4Ka (http://www.l4ka.org) - Implementations L4Ka::Pistachio and L4Ka::Hazelnut
- The Performance of µ-Kernel-Based Systems (http://os.inf.tu-dresden.de/pubs/sosp97/)
- - contains an excellent performance comparison of Linux running as a monokernel, on Mach 3 and on L4. The numbers used in this article are taken primarily from this source.
- Fiasco (http://os.inf.tu-dresden.de/fiasco/) – A free C++ implementation for x86 and ARM processors
- UNSW (http://www.cse.unsw.edu.au/~disy/L4/) - Porting on DEC Alpha and MIPS architecture
- L4Linux (http://os.inf.tu-dresden.de/L4/LinuxOnL4/) - Linux running on L4 microkernel
- DROPS (http://os.inf.tu-dresden.de/drops/) - The Dresden Real-Time Operating System Project
- China Comp L4 Research Group (http://www.xtrj.org/china-ukernel/l4.htm) - The China Computer uKernel L4 Research Groupde:L4