1 -- Overview
22C:112 Notes, Spring 2009
Operating systems are components of system software, so it is appropriate to begin with a look at system software in the large: System software includes at least three large-scale components, programming language implementations, middleware libraries, and operating systems. This course is concerned primarily with the latter, but we should look briefly at the former.
A key concept that spans all forms of system software is virtuality or virtualization. Resources may be physical or virtual. Virtual resources are created from underlying physical resources by software layers that create the desired virtual behavior out of what is available from lower layers.
A virtual machine is a programmable system that consists of some combination of physical and virtual resources that may be used to implement the semantics of computations performed on that machine. Where physical machines have only hardware implementing their machine languages, virtual machines include combinations of hardware and software in their implementations.
Virtual machines may be implemented by interpreters or compilers, or their primitive operations may be presented to the programmer as abstractions such as subroutines, objects, classes or methods. The JVM, the Java Virtual Machine, is a common example that is usually implemented by an interpreter that interprets J-code, the output of a Java compiler. In fact, however, every programming envrionment, whether it is implemented by an interpreter, combiler or a set of subroutine libraries, can be thought of as defining a virtual machine.
The above sections suggest that, whenever we are taling about system software, we are talking about a stack of virtual machines. For example, a programming language sitting on top of middleware sitting on top of an operating system sitting on top of a physical computer.
In describing any layer in this stack, we can speak of the transparency of that layer. An opaque layer hides details of the underlying layers in a stack of virtual machines, while a transparent layer exposes underlying layers.
Transparency can be valuable for efficiency. Middleware layers can slow down access to the operating system, and some high performance applications prefer to drill down past the middleware and directly use the underlying system calls. Even operating systems can stand in the way. Google, for example, has found that the file systems native to today's operating systems are too expensive and too limited for their needs, so for "Google-scale file systems," many developers prefer to write new file-system middleware that rests directly on a very primitive level of access to the physical disk drives.
Transparency can be dangerous. Programs that bypass middleware are generally less portable than those that rest on well defined portable user interfaces, and they can cause security headaches. Opaque virtual machines can be used to prevent user programs from placing the underlying system into unsafe states. Most of the protection mechanisms of modern operating systems that are essential to computer system security are mechanisms that create opaque spots in the virtual machine created by the operating system.
See Use of the Concept of Transparency in the Design of Hierarchically Structured Systems by D.L. Parnas and D.P. Siewiorek, Nov 1972 Tech Report or Communications of the ACM 18(7): 401-408 (1975).
In this course, we will briefly survey the history of operating systems before digging into systems from two perspectives. We will discuss systems in terms of what Microsoft refers to as the applications programmer interface, with an emphasis on how the virtual resources of the system are implemented in terms of the underlying physical system.
Our initial discussions will focus on the input/output, looking at how the primitives provided by the system interface are implemented in terms of the underlying hardware. We will begin with very simple devices such as keyboards or the (now archaic) parallel port interface, and work our way upward in terms of device complexity to devices such as disks.
On reaching the level of disks, we will enter the land of virtual resources. Disk partitions are virtual disks. So are disk files. We will look at the structure of directory managers, and in the context of file systems, take our first look at memory management.
Dynamic memory management plays a central role in all more advanced operating systems and programming language implementations, so we will discuss this next. We will look at several basic algorithms for heap management (typically a buddy system and a boundary-tag system) and then move on to discuss the mark-sweep garbage collection algorithm, ending with a brief discussion of more advanced garbage collectors.
The second major focus of the course will be on the virtualization of processor resources. We will begin this with process management, discussing system-level processes and threads as well as user-level threads. This naturally leads to a discussion of multiprocessors and multicore processors, as well as a discussion of the variety of interprocess communication and synchronization mechanisms.
Multiple processes invite the introduction of memory protection mechanisms. This, in turn, moves us to a discussion of virtual memory, both as a mechanism for solving storage management problems and as a protection mechanism. The final section of the course will transition from protection mechanisms to general issues in system-level security.
Finally, we will discuss the virtualization of communication channels, including the ISO/OSI hierarchy and how real systems such as the IP protocol stack do and do not conform to this hierarchy. Questions of transparency in hierarchic systems will drive significant parts of this discussion.
The Unix system (and its compatible descendants Linux, FreeBSD and MacOS X) will serve as running examples. The applications program interface of these systems was designed for use with the C programming language, so all exercises will be done using C.
In one sense, the C programming language is indefensible. It has a badly designed syntax, but this syntax was the basis for the design of C++, Java and C#. It has a very weak type system that is incorporated, almost entirely, into C++. Programs written in C (and C++) are therefore inherently dangerous and prone to a class of programming errors that are impossible in Java or C#. Of course, the middleware that supports both of these newer languages is all written on top of a system interface that was designed entirely in terms of C.
Weak type systems can be justified in system programming languages because there are some parts of operating systems that cannot be written in a strongly typed language. Notable among these is the memory manager, where it is essential to be able to do unchecked arithmetic on pointers. The part of the code where this is necessary is extremely small, though, and there is little excuse for using a pervasively weak type system to solve a localized problem.
Far better system programming languages have been developed, notably Ada and other descendants Pascal, but these languages have been almost entirely displaced from the marketplace by C and its descendants. Pascal's various descendants have the benefit of a generally strong typing system and a clear distinction between arrays and pointers, while permitting type controlled type violations where they are necessary.