Mach

History

Name

The developers rode bicycles to lunch through rainy Pittsburgh's mud puddles, and Tevanian joked the word "muck" could form a backronym for their Multi-User (or Multiprocessor Universal) Communication Kernel. Italian CMU engineer Dario Giuse later asked project leader Rick Rashid about the project's current title and received "MUCK" as the answer, though not spelled out but just pronounced . According to the Italian alphabet, he wrote "Mach". Rashid liked Giuse's spelling "Mach" so much that it prevailed.

Unix pipes

A key concept in the original Unix operating system is the idea of a pipe. A pipe is an abstraction allowing data to be moved as an unstructured stream of bytes between programs. Using pipes, users can link together multiple programs to complete tasks, feeding data through several consecutive small programs. This contrasts with typical operating systems of the era, which require a single large program that can handle the entire task, or alternately, used files to pass data, which was resource-expensive and time-consuming.

Pipes were built on the underlying input/output system. This system is, in turn, based on a model where drivers are expected to periodically "block" while they wait for tasks to complete. For instance, a printer driver might send a line of text to a line printer and then have nothing to do until the printer completes printing that line. In this case, the driver indicates that it was blocked, and the operating system allows some other program to run until the printer indicates it is ready for more data. In the pipes system the limited resource was memory, and when one program filled the memory assigned to the pipe, it would naturally block. Normally this would cause the consuming program to run, emptying the pipe again. In contrast to a file, where the entire file has to be read or written before the next program can use it, pipes made the movement of data across multiple programs occur in a piecemeal fashion without any programmer intervention.

Implementing pipes in memory buffers forced data to be copied from program to program, a time-consuming and resource intensive operation. This made the pipe concept unsuitable for tasks where quick turnaround or low latency was needed, such as in most device drivers. The operating system's kernel and most core functionality was instead written in a single large program. When new functionality, such as computer networking, was added to the operating system, the size and complexity of the kernel grew, too.

New concepts

Unix pipes offered a conceptual system that could be used to build arbitrarily complex solutions out of small cooperating programs. These smaller programs were easier to develop and maintain, and had well-defined interfaces that simplified programming and debugging. These qualities are even more valuable for device drivers, where small size and bug-free performance was extremely important. There was a strong desire to model the kernel on the same basis of small cooperating programs.

One of the first systems to use a pipe-like system underpinning the operating system was the Aleph kernel developed at the University of Rochester. This introduced the concept of ports, which were essentially a shared memory implementation. In Aleph, the kernel was reduced to providing access to the hardware, including memory and the ports, while conventional programs using the ports system implemented all behavior, from device drivers to user programs. This concept greatly reduced the size of the kernel, and permitted users to experiment with different drivers simply by loading them and connecting them together at runtime. This greatly eased the problems when developing new operating system code, which would otherwise require the machine to be restarted. The overall concept of a small kernel and external drivers became known as a microkernel.

Aleph was implemented on Data General Eclipse minicomputers and was tightly bound to them. This machine was far from ideal, since it required memory to be copied between programs, which resulted in considerable performance overhead. It was also quite expensive. Nevertheless, Aleph proved that the basic system was sound, and went on to demonstrate computer clustering by copying the memory over an early Ethernet interface.

Around this time a new generation of central processors (CPUs) were coming to market, offering a 32-bit address space and (initially optional) support for a memory management unit (MMU). The MMU handled the instructions needed to implement a virtual memory system by keeping track of which pages of memory were in use by various programs. This offered a new solution to the port concept, using the copy-on-write (COW) mechanism provided by the virtual memory system. Instead of copying data between programs, all that was required was to instruct the MMU to provide access to that same memory. This system would implement the interprocess communications (IPC) system with dramatically higher performance.

Mach

The major change between these experimental kernels and Mach was the decision to make a version of the existing 4.2BSD kernel re-implemented on the Accent message-passing concepts. Such a kernel would be binary compatible with existing BSD software, making the system immediately available for everyday use while still being a useful experimental platform. Additionally, the new kernel would be designed from the start to support multiple processor architectures, even allowing heterogeneous clusters to be constructed. In order to bring the system up as quickly as possible, the system would be implemented by starting with the existing BSD code, and gradually re-implementing it as inter-process communication-based (IPC-based) programs. Thus Mach would begin as a monolithic system similar to existing UNIX systems, and progress toward the microkernel concept over time.

Mach started largely being an effort to produce a clearly defined, UNIX-based, highly portable Accent. The result was a short list of generic concepts:

a "task" is a set of system resources that produce "threads" to run

a "thread" is a single unit of execution, existing within the context of a task and shares the task's resources

a "port" is a protected message queue for communication between tasks; tasks own send and receive rights (permissions) to each port.

"messages" are collections of typed data, they can only be sent to ports—not specifically tasks or threads

Mach developed on Accent's IPC concepts, but made the system much more UNIX-like in nature, making it possible to run UNIX programs with little or no modification. To do this, Mach introduced the port, representing each endpoint of a two-way IPC. Ports had a concept of permissions like files under UNIX, permitting a very UNIX-like model of protection to be applied to them. Additionally, Mach allowed any program to handle privileges that would normally be given to the operating system only, in order to permit user space programs to handle things such as controlling hardware.

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, 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 any practical value, the goal of making a microkernel was realized. This was soon followed by versions on the IBM RT PC 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 had not yet been delivered. These early Mach versions included the majority of 4.3BSD in the kernel, a system known as a POE Server, resulting in a kernel that was actually larger than the UNIX it was based on. The idea, 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 architectural changes were made in order to solve this problem. Unwieldy UNIX licensing issues also plagued researchers, so this early effort to provide a non-licensed UNIX-like system environment continued to find use, well into the further development of Mach.

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 that were causing serious problems for older-style kernels. This generated considerable interest in the commercial market, where a number of companies were considering changing hardware platforms. If the existing system could be ported to run on Mach, it seemed it would then be easy to change the platform underneath.

Mach received a major boost in visibility when the Open Software Foundation (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 parts for the microkernel, including IBM's Workplace OS and several efforts by Apple to build a cross-platform version of the classic Mac OS. Support for running DOS applications in a Mach 3.0 environment was demonstrated by researchers, following on from earlier work running the classic Mac OS and MultiFinder under Mach 2.5. A research project at Digital Equipment Corporation investigated the feasibility of hosting OpenVMS on top of the Mach 3 kernel, and created a proof of concept with a subset of VMS' features.

Performance issues

Mach was originally intended to be a replacement for classical monolithic UNIX, and for this reason contained many UNIX-like ideas. For instance, Mach provided a permissions and security system similar to that used by UNIX's file system. Since the kernel was privileged (running in kernel-space) over other OS servers and software, 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 operating system 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, e.g. to directly access hardware.

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 reentrant or interruptible, 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 reentrant, in practice this is not 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. Benchmarks on 1997 hardware showed that Mach 3.0-based UNIX single-server implementations were about 50% slower than native UNIX.

Study of the exact nature of the performance problems turned up a number of interesting facts. One was that the IPC 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 benchmarks on an 486DX-50, a standard UNIX system call took an average of 21μs to complete, while the equivalent operation with Mach IPC averaged 114μs. Only 18μs of this was hardware related; the rest was the Mach kernel running various routines on the message. 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.

Potential solutions

IPC overhead is a major issue for Mach 3 systems. The concept of a multi-server operating system is still promising, though it still requires some research. 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.

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, MkLinux, OSF/1, and NeXTSTEP/OPENSTEP/macOS. 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 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.

By the mid-1990s, work on microkernel systems was largely stagnant, although the market had generally believed that all modern operating systems would be microkernel based by the 1990s. The primary remaining widespread uses of the Mach kernel are Apple's macOS and its sibling iOS, which run atop a heavily modified hybrid Open Software Foundation Mach Kernel (OSFMK 7.3) called "XNU" also used in OSF/1. In XNU, the file systems, networking stacks, and process and memory management functions are implemented in the kernel; and file system, networking, and some process and memory management functions are invoked from user mode via ordinary system calls rather than message passing; XNU's Mach messages are used for communication between user-mode processes, and for some requests from user-mode code to the kernel and from the kernel to user-mode servers.

Second-generation microkernels

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 were due to 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 29μ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 a cell phone or robot 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 have a single large address space shared by all programs, so under these systems the mapping did not provide any benefits.

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 (version 2) includes only seven system calls 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 29%.

Software based on Mach

The following is a list of operating system kernels derived from Mach and operating systems with kernels derived from Mach: