Over the past 40 years, the fundamental structure of operating systems has undergone a significant evolution. In this lecture, we will look at the range of variation.
The first generation of operating system, frequently called a monitor,
typically running on a machine with no memory protection mechanism,
could generally be described by a map of the machine's memory showing
what system components resided in each range of memory addresses:
_________
| | Interrupt handlers \
|_________| \
| | Resident library > The operating system
|_________| /
| | Command language interpreter /
|_________|
| | \
| | \
| | > Available to user programs
| | /
|_________| /
The order of these components in the memory of the machine could vary,
depending on what memory addresses were dedicated to hardware functions
and depending on the availability of any protection mechanism.
The function of the code within the system could be divided up more finely as follows:
This kind of system typified mainframe operating systems designed for first and second-generation computers, in the 1950's and the early 1960's. These systems ran only one application at a time. Minicomputers, the small computers of the 1960's and 1970's, were sold with similar operating systems, and the first generation of operating systems for personal computers were again similar. Even early versions of MacOS and MS/DOS were basically designed on this model -- a sophisticated graphical user interface can be built using an archaic operating system architecture!
The first generation of memory protection mechanisms were quite simple, typically a single register, the protection register, in the CPU that was ignored in user mode and used in protected mode. In user mode, it was illegal to perform I/O operations or to use memory addresses less than the protection register. In system protected mode, all addresses were legal. With this added hardware and a carefully written operating system, user programs could not crash the system, and while this is valuable, but this hardware offered a new possibility.
A timesharing monitor was intended to provide a virtual personal computer to each interactive user. Typically each interactive users had a keyboard-printer as a terminal; the two dominant brands were Teletype, and the IBM 2740/2741 (based on the Selectric typewriter mechanism). The Teletype had a 110 baud asynchronous serial interface and used ASCII, while the IBM 2740/2741 ran at 150 baud and used proprietary IBM character sets.
A multitasking monitor was intended to provide multiple virtual computers, one to each task running on the machine, where most of the tasks were not necessarily interactive. One task might communicate with the machine operator, while others would run batch jobs and yet others might intereact with mechanisms attached to the computer.
In fact, these two classes of systems differ more in the way users perceive the system than they do in necessary internal details. In the 1960's, when these ideas were new and system programmers were exploring what was possible, the similarities were frequently thoroughly obscured by poor understanding of what was being done.
The first generation of timesharing and multitasking systems was based on a very simple idea. At any moment, only one user program would be loaded in main memory, while the others were stored on secondary memory -- in early times, typically drum memory, but disk would be typical today. When it came time to change form one user program to another, the entire user area of memory would be written out to secondary memory, and then the code and data of the next user program would be read in from secondary memory. This exchanging of programs was called swapping.
Swapping may seem slow, but even in the 1960's, drums and disks frequently rotated at 20 or more revolutions per second, and the storage capacity of one track was frequently about the size of the user area of memory. As a result, the basic swap operation took under 1/10th of a second, and if a typical user program was allowed to use the CPU for on the order of one second at a time, swapping only consumed 10% of the time, an acceptable overhead.
Swapping allows multiple processes to share the CPU, but the cost of context switching from one process to the next is quite high. If all of the processes are trustworthy and small, they can easily all be resident, and the context switching expense can be quite low; all that needs to be done when switching from one process to the next is to save the registers of one and restore the registers of the next.
Early (and many modern) real-time systems used this model, and if there is a rudimentary protection mechanism, this may be combined with swapping, so that trusted resident tasks can be run while untrusted user tasks are swapped. Several successful early timesharing systems were built on this model.
More complex memory proteciton mechanisms allow more! If the memory protection mechanism creates one virtual address space per user process, we can run one user process while the previous is being swapped out and the next is being swapped in. This assumes, of course, that we have sufficient memory for at least two user processes.
The simplest sufficient memory protection mechanism allowing this has two registers in the CPU, a base and a bound register. In user mode (but not in protected mode), the base register is added to all virtual addresses in order to compute the physical address, and the virtual address is illegal if it exceeds the bound register. Variations on this simple mechanism were used by such important computers as the DEC PDP-10 and the CDC 6600 (both were very successful timesharing systems, and the 6600 is generally seen as the first supercomputer).
Segmented address translation systems offer more. For example, if the memory address space is divided into two segments, one may be used for access to the user program, and the other for access to the user's data. If two users are running the same program, context switching from one user to the next involves changing only the data segment and the other registers, so we can avoid paying the price for swapping code.
Paged address translation offers finer granularity of sharing, so two processes could share some code pages, have other code pages that are private, and perhaps share some data pages as well. The Berkeley Timesharing System running on the SDS 940 computer was the first system I know of to fully exploit this possibility in the second half of the 1960's, but it was built in the shadow of the MIT/GE/Bell MULTICS project, and when MULTICS finally worked a year or two later, it was far more complete in its exploitation of these ideas.
Demand paging allows swapping to be done one page at a time, with only a few pages of each user program resident in memory at any time. We will discuss this more, later, but the important thing to realize is that demand paged memory management is, in many ways, an independend idea that can be applied to any of the system structures outlined previously.
Up to this point, the resident code of the operating system has been viewed as being fairly unstructured, but a software engineer looking at the bulk of the code within the system typically can identify a number of layers, each of which builds the programming environment on which higher layers are built. The designers of the Multics system were the first to attempt to fully exploit this in the mid 1960's. Many hierarchies have been proposed, here is one:
The MULTICS project responded to this idea of hierarchical decomposition of system function by proposing a general protection mechanism that allowed each layer in the hierarchy to be protected from misuse by any layer above it. They developed a hardware model that supported at least 8 layers, and they built a software model on top of this that supported 64 layers, so that user programs could be divided into layers in the same way.
This was a mixed success. It turns out that our software is not strictly hierarchical, with more privileged and less privileged components. Nonetheless, this model has given us a key bit of terminology that lasts to this day:
The kernel is the innermost layer of the system. (Computer people or notorious for misspelling the word kernel -- it is a common word! We speak figuratively of the kernel of truth in an idea, the innermost part of the idea that is true, even though it is covered in layers of falsehood, and we speak literally of a kernel of wheat, the actual seed that lies inside layers of chaff.)
The reaction to the complexity of Multics and to the shortcomings of the Multics protection model began around 1970. The cleanest statement of this reaction was that an operating system should consist of a very small kernel that served only to establish multiple protected domains with controlled communication channels between domains. One can then speak of operating system structure in terms of a map of the domains and their interactions. Some of these domains will form natural hierarchies, but this is not required.
Modern operating systems such as Mach and Amoeba clearly illustrate the kernel-domain model. Older systems such as UNIX can be considered to abuse the term kernel because the UNIX (or Linux) kernel is immense. It is true, however, that many system functions in UNIX are handled each in their own domain by processes called daemons, so UNIX is an example of a system on the borderline between the archaic systems that dominated this discussion and the modern systems that are the focus of this course.