Mach (kernel)
Mach is an operating system kernel developed at Carnegie Mellon University by Richard Rashid and Avie Tevanian to support operating system research, primarily distributed and parallel computing. Mach is often considered one of the earliest examples of a microkernel. However, not all versions of Mach are microkernels. Mach's derivatives are the basis of the operating system kernel in GNU Hurd and of Apple's XNU kernel used in macOS, iOS, iPadOS, tvOS, and watchOS.
The project at Carnegie Mellon ran from 1985 to 1994, ending with Mach 3.0, which is a true microkernel. Mach was developed as a replacement for the kernel in the BSD version of Unix, not requiring a new operating system to be designed around it. Mach and its derivatives exist within several commercial operating systems, including all those using the XNU operating system kernel, which incorporates an earlier non-microkernel version of Mach as a major component. The Mach virtual memory management system was also adopted in 4.4BSD by the BSD developers at CSRG, and appears in modern BSD-derived Unix systems such as FreeBSD.
Mach is the logical successor to Carnegie Mellon's Accent kernel. Mach's lead developer Richard Rashid has been employed at Microsoft since 1991; he founded the Microsoft Research division. Co-founding Mach developer Avie Tevanian, was formerly head of software at NeXT, then Chief Software Technology Officer at Apple Inc. until March 2006.
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 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.
However, 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 were coming to market, offering a 32-bit address space and support for a memory management unit. 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 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 system with dramatically higher performance.
This concept was picked up at Carnegie-Mellon, who adapted Aleph for the PERQ workstation and implemented it using copy-on-write. The port was successful, but the resulting Accent kernel was of limited practical use because it did not run existing software. Moreover, Accent was as tightly tied to PERQ as Aleph was to the Eclipse.
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 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 to each port.
- "messages" are collections of typed data, they can only be sent to ports—not specifically tasks or threads
Under Mach, and like UNIX, the operating system again becomes primarily a collection of utilities. As with UNIX, Mach keeps the concept of a driver for handling the hardware. Therefore, all the drivers for the present hardware have to be included in the microkernel. Other architectures based on hardware abstraction layer or exokernels could move the drivers out of the microkernel.
The main difference with UNIX is that instead of utilities handling files, they can handle any "task". More operating system code was moved out of the kernel and into user space, resulting in a much smaller kernel and the rise of the term microkernel. Unlike traditional systems, under Mach a process, or "task", 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. The kernel's job was reduced from essentially being the operating system to running the "utilities" and providing them access to the hardware.
The existence of ports and the use of IPC is perhaps the most fundamental difference between Mach and traditional kernels. Under UNIX, calling the kernel consists of an operation named a system call or trap. The program uses a library to place data in a well known location in memory and then causes a fault, a type of error. When a system is first started, its kernel is set up to be the "handler" of all faults; thus, when a program causes a fault, the kernel takes over, examines the information passed to it, then carries out the instructions.
Under Mach, the IPC system was used for this role instead. 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 sending a message requires a system call, just as a request for system functionality on other systems requires a system call, under Mach sending the message is pretty much all the kernel does; handling the actual request would be up to some other program.
Thread and concurrency support benefited by message passing with IPC mechanisms since tasks now consist of multiple code threads which Mach could freeze and unfreeze during message handling. This permits the system to be distributed over multiple processors, either by 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 do not try to write to the same region of memory from different processors. However, using Mach ports makes this well defined and easy to implement, so Mach ports were made first-class citizens in that system.
The IPC system initially had performance problems, so a few strategies were developed to improve performance. Like its predecessor, Accent, Mach used a single shared-memory mechanism for physically passing the message from one program to another. Physically copying the message would be too slow, so Mach relies on the machine's memory management unit to quickly map the data from one program to another. Only if the data is written to would it have to be physically copied, a process called "copy-on-write".
Messages were also checked for validity by the kernel, to avoid bad data crashing one of the many programs making up the system. Ports were deliberately modeled on the UNIX file system concepts. This permits 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.
Development under such a system would be 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 require only that the program 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.
Finally, under Mach, all of these features were deliberately designed to be extremely platform neutral. To quote one text on Mach:
There are a number of disadvantages, however. A 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.