Mach kernel
|
|
Mach is an operating system kernel developed at Carnegie-Mellon University to support operating system research, primarily distributed and parallel computation. It is one of the earliest examples of a microkernel, and still the standard by which similar projects are measured.
The project at CMU ran from 1985 to 1994, ending with Mach 3.0. A number of other efforts have continued Mach research, including the University of Utah's Mach 4. Today further experimental research on Mach appears ended, although the system is in use in a number of commercial operating systems, notably Mac OS X.
Mach is the logical successor to CMU's Accent kernel. The lead developer on the Mach project, Richard Rashid, has been working at Microsoft since 1991 in various top-level positions revolving around the Microsoft Research division. Another of the original Mach developers, Avie Tevanian, was formerly head of software at NeXT and today is Chief Software Technology Officer at Apple Computer.
| Contents |
Traditional kernels
The ultimate "classic" operating system is Unix, so any discussion of more modern systems must start with that one.
Unix was the culmination of many years of development towards modern systems. In the decade preceding Unix, computers had grown enormously in power - to the point where computer operators were looking for new ways to get people to use the spare time on their machines. One of the major developments during this era was time sharing, whereby a number of users would be given small slices of computer time in sequence, but at such a speed that it appeared they were each connected to their own, slower, machine.
The development of time share systems led to a number of problems. One was that users, particularly at universities where the systems were being developed, seemed to want to hack the system. Security and permissioning became a major focus of the Multics effort for just this reason. Another ongoing issue was properly handling computing resources: Users spend most of their time staring at the screen instead of actually using their computers' resources, and the time share system should give the CPU time to an active user during these periods. Finally, the systems typically offered a memory hierarchy several layers deep, and partitioning this expensive resource led to major developments in virtual memory systems.
Unix is an example of a system that took many of the ideas that were floating around in the industry and synthesized them into a simpler and cleaner whole. As the operating system took shape, its programmers came to a key realization: The purpose of the computer is to transform one data file into another. Thus, they decided to model every high-level device as a file. For instance, printers were represented as a "file" at a known location; when data was copied into the file, it would print out. Similar concepts existed in other systems of the era, but they tended to virtualize devices at a lower level - that is, both printers and files would be instances of some lower level concept. Virtualizing the system at the file level allowed users to manipulate the entire system using their existing file management utilities and concepts, dramatically simplifying operation. It also made programming easier; almost all programs have to deal with files at some time, under Unix those same concepts drive most other devices as well.
Another key innovation of Unix was allowing programmers to manipulate those files using a series of small programs, rather than a single, complex one. Using the concept of pipes, users could complete operations in stages, feeding a file through a series of single-purpose tools. Although the end result was the same, using smaller programs in this way dramatically increases flexibility, allowing the user to modify their workflow by adding or removing programs from the chain. Additionally, this made development of Unix applications far easier; developers had to concentrate only on the functionality they were interested in, while pre-written programs could be used to fill in any missing functionality.
In the Unix model the "operating system" consists of two parts; one is the huge collection of utility programs that drive most operations, the other the kernel that runs them. Under Unix the distinction between the two is fairly thin from a programming standpoint, the kernel is a program given some special privileges and running in a protected supervisor mode. The kernel's job is to act as a program loader and supervisor for the small utility programs making up the rest of the system and to provide locking and I/O services for these programs, beyond that most of the system was expected to be run outside the kernel.
Over the years the computing model changed, and Unix's everything-is-a-file no longer seemed as universally applicable as it had before. For instance, although a terminal could be treated as a file, a glass printer in a way, the same did not seem to be true for a GUI. Networking was another thorny problem, although some parts of the system could definitely be considered file-like at higher levels, developers still needed to be able to access the packet-oriented lower levels. As the capability of computers grew, Unix became increasingly cluttered with code; while early kernels might have had 100,000 lines of code, modern kernels have much more. For example, Linux, a Unix successor, has over 33 million lines.
As a computer's kernel grows, a number of problems become evident. One of the most obvious is that its memory footprint increases, even if the developer is not interested in many of its features. This is mitigated to some degree by increasing sophistication of the virtual memory system, but not all computers have virtual memory. In order to reduce the kernel's footprint, extensive surgery needs to be performed to carefully remove the unneeded code. Often, non-obvious dependencies that exist between parts of the kernel make this very difficult.
Another, less obvious, problem is a result of the fact that programs are tightly bound to the memory they use and the "state" of their processor. In machines with more than one processor, the former is usually not an issue, as all the processors share a common memory (in modern systems at least). However, the processor state is not so easy an issue to address in multi-processor machines. In order to allow a kernel to run on such a system, it has to be extensively modified to make it "re-entrant" or "interruptible", meaning that it can be called in the midst of doing something else. Once this conversion is complete, programs running at the same time on another processor can call the kernel without causing problems.
This task is not difficult in theory, but in a kernel with million lines of code it becomes a serious problem in practice. Adding to the problem is the fact that there is often a performance "hit" for implementing re-entrant code, meaning that such a conversion makes the system run slower on the vast majority of systems in the world -- those with a single processor.
The biggest problem with the monolithic kernels, or monokernels, was sheer size. The code was so extensive, that working on such a large system was tedious.
Mach concepts
After some initial steps it became clear to many that Unix's concept of everything-as-a-file simply no longer worked on modern systems. Nevertheless those same developers lamented the loss of flexibility that the original concept offered. So what if there was some other level of virtualization that made the system "work" once again?
The key abstraction in Unix was the pipe, what was needed was a pipe-like concept that worked at a much more general level, allowing any sort of information to be passed between programs. It appeared that such a system did exist: using inter-process communication, or IPC, a pipe-like system could be built that would move any sort of information between two programs, as opposed to file-like information. While many systems, including most Unices, had added various IPC implementations over the years, these were special-purpose libraries only really useful for one-off tasks.
CMU started experimentation along these lines under the Accent operating system project, using an IPC system based on shared memory. Accent was a purely experimental system and developed in an ad-hoc fashion over a period of time, so it tended to be somewhat messy. Additionally Accent's usefulness for research was limited because it was not Unix-compatible, and Unix was already the de-facto standard for almost all OS research. Finally, Accent was tightly coupled with the hardware platform it was developed on, and at the time in the early 1980s it appeared there would soon be an explosion of new platforms, many of them massively parallel.
Mach started largely as an effort to produce a cleanly-defined, Unix-based, highly portable Accent. The result was a short list of generic concepts:
- a "task" is a set of resources that enable "threads" to run
- a "thread" is a single unit of code running on a processor
- a "port" defines a secure pipe for IPC between tasks
- "messages" are passed between programs on ports
Mach developed on Accent's IPC concepts, but made the system much more Unix-like in nature, even able to run Unix programs with little or no modification. To do this Mach introduced the concept of a port, representing each endpoint of a two-way IPC. Ports had security and rights like files under Unix, allowing a very Unix-like model of protection to be applied to them. Additionally Mach allowed any program to be handed privileges that would normally be given to the kernel only, in order to allow user-space programs handle things like interacting with hardware.
Under Mach the operating system again becomes primarily a collection of utilities. Instead of utilities handling files, however, they could handle any task at all. More code was moved out of the kernel and into user-space, resulting in a much smaller kernel and the rise of the term micro-kernel. Unlike traditional systems, under Mach a process (task in Mach-speak) can consist of a number of threads. While this is common in modern systems, Mach was the first system to define tasks and threads in this way.
Ports and IPC is perhaps the most fundamental difference between Mach and traditional kernels. Under Unix, calling the kernel consists of an operation known as a syscall or trap. The program, using a library, places data in a well known location in memory and then causes a fault, a type of error. When the system is first started the kernel is set up to be the "handler" of all faults, so when the program causes a fault the kernel takes over, examines the information passed to it, and then carries out the instructions. In order to process the fault, the system executes what is known as a context switch, pausing the user program and then starting the kernel. This is a fairly expensive operation.
Under Mach, the IPC system was used for this role instead. In order to call system functionality, a program would ask the kernel for access to a port, then use the IPC system to send messages to that port. Although the messages were triggered by syscalls as they would be on other kernels, under Mach that was pretty much all the kernel did -- handling the actual request would be up to some other program.
The use of IPC for message passing leads to a huge benefit. Since tasks consisted of multiple threads, and it was the code in the threads that used the IPC mechanism, it was very easy for Mach to freeze and unfreeze threads while the message was handled. This allowed the system to be distributed over multiple processors, either using shared memory directly as in most Mach messages, or by adding code to copy the message to another processor if needed. In a traditional kernel this is difficult to implement, the system has to be sure that different programs don't try to write to the same memory from different processors. Under Mach this was well defined and easy to implement, it was the very process of accessing that memory, the ports, that was made a first-class-citizen of the system.
It was obvious to the developers that performance of the IPC system would be a potential problem, but it was felt that there were a number of solutions that should minimize the impact. In particular, Mach used a single shared-memory mechanism for physically passing the message from one program to another, relying on the machine's memory management unit (MMU) to quickly map the data from one program to another (physically copying it in memory would be too slow). Only if the data was written to would it have to be physically copied, a process known as copy-on-write.
Ports were deliberately modeled on the Unix file system concepts. This allowed the user to find ports using existing file system navigation concepts, as well as assigning rights and permissions as they would on the file system. This is similar in concept to the way that the web is navigated using a file-system syntax, and for similar reasons. Messages were also checked for validity by the kernel, to avoid bad data crashing one of the many programs making up the system.
Finally, under Mach, all of these features were deliberately designed to be extremely platform neutral. To quote one text on Mach:
Unlike UNIX, which was developed without regard for multiprocessing, Mach incorporates multiprocessing support throughout. Its multiprocessing support is also exceedingly flexible, ranging from shared memory systems to systems with no memory shared between processors. Mach is designed to run on computer systems ranging from one to thousands of processors. In addition, Mach is easily ported to many varied computer architectures. A key goal of Mach is to be a distributed system capable of functioning on heterogeneous hardware.
Mach explored the concept that we now refer to as a microkernel. Instead of having all of the code for the operating system in a single large kernel, the majority of the code would instead be located in smaller programs known as servers which would run like any other program. The kernel's job was reduced from essentially "being" the OS, to maintaining the servers and scheduling their access to hardware.
Development under such a system would be enormously easier. Not only would the code being worked on exist in a traditional program that could be built using existing tools, it could also be started, debugged and killed off using the same tools. With a monokernel a bug in new code would take down the entire machine and require a reboot, whereas under Mach this would only require that program to be restarted. Additionally the user could tailor the system to include, or exclude, whatever features they required. Since the operating system was simply a collection of programs, they could add or remove parts by simply running or killing them as they would any other program.
There are a number of disadvantages, however. One relatively mundane one is that it is not clear how to find ports. Under Unix this problem was solved over time as programmers agreed on a number of "well known" locations in the file system to serve various duties. While this same approach worked for Mach's ports as well, under Mach the operating system was assumed to be much more fluid, with ports appearing and disappearing all the time. Without some mechanism to find ports and the services they represented, much of this flexibility would be lost.
Development
Mach was initially hosted as additional code written directly into the existing 4.2BSD kernel, allowing the team to work on the system long before it was complete. Work started with the already functional Accent IPC/port system, and moved on to the other key portions of the OS, tasks and threads and virtual memory. As portions were completed various parts of the BSD system were re-written to call into Mach, and a change to 4.3BSD was also made during this process.
By 1986 the system was complete to the point of being able to run on its own on the DEC VAX. Although doing little of practical value, the goal of making a microkernel was realized. This was soon followed by versions on the IBM PC/RT and for Sun Microsystems 68030-based workstations, proving the system's portability. By 1987 the list included the Encore Multimax and Sequent Balance machines, testing Mach's ability to run on multiprocessor systems. A public Release 1 was made that year, and Release 2 followed the next year.
Throughout this time the promise of a "true" microkernel was not yet being delivered. These early Mach's included the majority of 4.3BSD in the kernel, a system known as POE, resulting in a kernel that was actually larger than the Unix it was based on. The goal, however, was to move the Unix layer out of the kernel into user-space, where it could be more easily worked on and even replaced outright. Unfortunately performance proved to be a major problem, and a number of architectual changes were made in order to solve this problem.
The resulting Mach 3 was released in 1990, and generated intense interest. A small team had built Mach and ported it to a number of platforms, including complex multiprocessor systems which were causing serious problems for older-style kernels. This generated considerable interest in the commercial market, where a number of companies were in the midst of considering changing hardware platforms. If the existing system could be ported to run on Mach, it would seem it would then be easy to change the platform underneath.
Mach received a major boost in visibility when the OSF announced they would be hosting future versions of OSF/1 on Mach 2.5, and were investigating Mach 3 as well. Mach 2.5 was also selected for the NeXTSTEP system and a number of commercial multiprocessor vendors. Mach 3 led to a number of efforts to port other operating systems to the kernel, including IBM's Workplace OS and several efforts by Apple Computer to build a cross-platform version of the Mac OS.
For some time it appeared that every operating system in the world would be based on Mach by the late 1990s.
Performance problems
When Mach was first being seriously used in the 2.x versions, performance was slower than traditional kernels, perhaps as much as 25%. This cost was not considered particularly worrying, however, because the system was also offering multi-processor support and easy portability. Many felt this was an expected and acceptable cost to pay. In fact the system was hiding a serious performance problem, one that only became obvious when Mach 3 started to be widely used, and developers attempted to make systems running in user-space.
Recall that under a traditional kernel a syscall requires an expensive operation known as a context switch. This causes the running program to pause while the kernel completes processing the request and hands back the results. Thus the complete request-response requires two context switches, one to enter the kernel, another to return control to the calling program.
In early versions of Mach the process wasn't all that different. The caller would use the IPC system to pass in the request, placing data in memory and then triggering the kernel. The kernel would then "map" the memory into its own space (a translation of addresses) and then run as normal. Mapping was somewhat expensive, and explained the majority of Mach's overhead compared to traditional systems.
When Mach 3 attempted to move the operating system into user-space, the overhead suddenly became overwhelming. In this case consider the simple task of asking the system for the time. Under a true user-space system, there would be a server handling this request. The caller would trigger the IPC system to run the kernel, causing a context switch and memory mapping. The kernel would then examine the contents of the message to see if the caller had rights to call the server, and if so, do another mapping into the server's memory and another context switch to allow it to run. The process then repeats to return the results, adding up to a total of four context switches and memory mappings, as well as two runs of the code to check the rights and validity of the messages.
To put numbers to this, a call into the BSD kernel on a 486DX-50 requires about 20 microseconds (μs). The same call on the same system running Mach 3 required 114 μs. Given a syscall that does nothing, a full round-trip under BSD would require about 40 μs, whereas on a user-space Mach system it would take just under 500 μs. In detailed testing published in 1991, Chen and Bershad found overall system performance was degraded by up to 66% compared to a traditional kernel.
This was not the only source of performance problems. Another centered on the problems of trying to handle memory properly when physical memory ran low and paging had to occur. In the traditional monokernels the authors had direct experience with which parts of the kernel called which others, allowing them to fine tune their pager to avoid paging out code that was about to be used. Under Mach this wasn't possible because the kernel had no real idea what the operating system consisted of. Instead they had to use a single one-size-fits-all solution that added to the performance problems. Mach 3 attempted to address this problem by providing a simple pager, relying on user-space pagers for better specialization. But this turned out to have little effect. In practice, any benefits it had were wiped out by the expensive IPC needed to call it in.
Some of these problems would exist in any system that had to work on multiple processors, and in the mid-1980s it appeared the future market would be filled with these. In fact, this evolution did not play out as expected. Multiprocessor machines were used for a brief time in server applications in the early 1990s, but then faded away. Meanwhile commodity CPUs grew in performance at a rate of about 60% a year, magnifying any ineffeciency in code. Worse, the speed of memory access grew at only 7% a year, meaning that the cost of accessing memory grew tremendously over this period, and since Mach was based on mapping memory around between programs, any "cache miss" made IPC calls excrutiatingly slow.
Regardless of the advantages of the Mach approach, these sorts of real-world performance hits were simply not acceptable. As other teams found the same sorts of results, the early Mach enthusiasm quickly disappeared. After a short time the development community seemed to conclude that the entire concept of using IPC as the basis of an operating system was inherently flawed.
Potential solutions
When Mach was first developed it seemed the natural evolution of the system would be to a collection of servers making up the operating system. This dream died when Mach 3 systems were first being used. Under such a system the IPC overhead would be even more egregious, as the majority of a system like Unix consists of one part of the kernel calling another. If such a system were truly broken out, each of these calls would likewise trigger additional IPCs and even more delays. It was clear any simple system based on this concept simply wouldn't work.
This does not mean the multi-server system is entirely impossible, however, it's just more work. The developers have to be careful to isolate code into modules that do not call from server to server. For instance, the majority of the networking code would be placed in a single server, thereby minimizing IPC for normal networking tasks. Under Unix this isn't very easy, however, because the system is based on using the file system as the basis for everything from security to networking.
Most developers instead stuck with the original POE concept of a single large server providing the operating system functionality. In order to ease development, they allowed the operating system server to run either in user-space or kernel-space. This allowed them to develop in user-space and have all the advantages of the original Mach idea, and then move the debugged server into kernel-space in order to get better performance. Several operating systems have since been constructed using this method, known as co-location, among them Lites (a port of 4.4BSD Lite), MkLinux, OSF/1 and NeXTSTEP/OPENSTEP/Mac OS X. The Chorus microkernel made this a feature of the basic system, allowing servers to be raised into the kernel space using built-in mechanisms.
Mach 4 attempted to address these problems, this time with a more radical set of upgrades. In particular, it was found that program code was typically not writable, so potential hits due to copy-on-write were rare. Thus it made sense to not map the memory between programs for IPC, but instead migrate the program code being used into the local space of the program. This led to the concept of "shuttles" and it seemed performance had improved, but the developers moved on with the system in a semi-usable state. Mach 4 also introduced built-in co-location primitives, making it a part of the kernel itself.
In all of these tests the IPC performance was found to be the main contributor to the problem, accounting for about 73% of the lost cycles. By the mid-1990s, work on microkernel systems was largely dead. Although the market generally believed that all modern operating systems would be microkernel based by the 1990s, today the only widespread desktop use is in Apple's Mac OS X, using a co-located server running on top of a heavily modified Mach 3.
The Next Generation
Further analysis demonstrated that the IPC performance problem was not as obvious as it seemed. Recall that a single-side of a syscall took 20 μs under BSD and 114 μs on Mach running on the same system. Of the 114, 11 was the context switch, identical to BSD. An additional 18 were used by the MMU to map the message between user-space and kernel space. This adds up to only 31 μs, longer than a traditional syscall, but not by much.
The rest, the majority of the actual problem, was due to the kernel performing tasks such as checking the message for port access rights. While it would seem this is an important security concern, in fact, it only makes sense in a Unix-like system. For instance, a single-user operating system running on a cell phone might not need any of these features, and this is exactly the sort of system where Mach's pick-and-choose operating system would be most valuable. Likewise Mach caused problems when memory had been moved by the operating system, another task that only really makes sense if the system has more than one address space. DOS and the early Mac OS had a single large address space shared by all programs, so under these systems the mapping is a waste of time.
These realizations led to a series of second generation microkernels, which further reduced the complexity of the system and placed almost all functionality in the user space. For instance, the L4 kernel includes only seven functions and uses 12k of memory, whereas Mach 3 includes about 140 functions and uses about 330k of memory. IPC calls under L4 on a 486DX-50 take only 5 μs, faster than a Unix syscall on the same system, and over 20 times as fast as Mach. Of course this ignores the fact that L4 is not handling permissioning or security, but by leaving this to the user-space programs, they can select as much or as little overhead as they require.
The potential performance gains of L4 are tempered by the fact that the user-space applications will often have to provide many of the functions formerly supported by the kernel. In order to test the end-to-end performance, MkLinux in co-located mode was compared with an L4 port running in user-space. L4 added about 5%-10% overhead, compared to Mach's 15%, all the more interesting considering the double context switches needed.
These newer microkernels have revitalized the industry as a whole, and many formerly dead projects such as the GNU Hurd have received new attention as a result.
External links
- The Mach project at CMU (http://www-2.cs.cmu.edu/afs/cs/project/mach/public/www/mach.html)
- THE MACH SYSTEM (http://library.nocrew.org/lib/os/Mach.txt)
- - an excellent introduction to Mach concepts
- A comparison of Mach, Amoeba and Chorus (http://www.cdk3.net/oss/Ed2/Comparison.pdf)
- Towards Real Microkernels (http://rtsl.cs.ccu.edu.tw/upload/paper/(2002-12-05)%20Toward%20Real%20Microkernels.ppt)
- - contains numerous performance measurements, including those quoted in the article
- 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
- Rick Rashid's page at Microsoft Research (http://www.microsoft.com/presspass/exec/rick/default.asp)de:Mach (Kernel)
es:Mach kernel fr:Mach (informatique) it:Kernel Mach nl:Mach kernel ja:Mach pl:Mach (system operacyjny)