Browse Books

From the Preface

MAIN GOAL

This book tries to give students of computer science and professional programmers a general understanding of operating systems--the programs that enable people to share computers efficiently.

To make the sharing of a computer tolerable, an operating system must enforce certain rules of behavior on all its users. One would therefore expect the designers of operating systems to do their utmost to make them as simple, efficient, and reliable as possible.

A number of operating systems made in the early 1960's had these characteristics; but in the late 1960's designers were often overambitious and built enormous systems with poor performance.

I see no inherent reason why operating systems should not reach the quality of program construction found in present compilers; this will require an understanding of the principles common to all operating systems and a consistent use of safe methods of designing large programs. It is my hope that this book will give you a start in this direction.

I assume that you are familiar with the basic structure of computers and programming languages and have some experience in writing and testing non-trivial programs. In a few cases a knowledge of elementary calculus and probability theory is also needed.

THEMES

The main theme of the book is that operating systems are not radically different from other programs. The difficulties encountered in the design of efficient, reliable operating systems are the same as those one encounters in the design of other large programs, such as compilers or payroll programs.

The historical importance of operating systems is that they led to the discovery of new principles of resource sharing, multiprogramming, and program construction. These principles have a general validity beyond operating systems, and I think that they should be taught as part of a core of computer science courses, following courses on programming languages, data structures, and computer structures.

The purpose of an operating system is to share computational resources among competing users. To do this efficiently a designer must respect the technological limitations of these resources.

Present computers consist of a small number of components (processors, store modules, and peripherals) which operate strictly sequentially. It is possible to multiplex a single processor and a small internal store (supported by a large backing store) among several computations to create the illusion that they are executed concurrently and have access to a large, homogeneous store. But these abstractions are not supported by the underlying technology, and if they are carried too far, the result is a total collapse of computational service known as thrashing.

One of the difficulties of operating systems is the highly unpredictable nature of the demands made upon them. Independent users submit jobs with varying resource requirements at irregular intervals. An operating system is expected to schedule this unpredictable mixture of jobs in such a manner that the resources are utilized efficiently and the users can expect response within reasonably predictable times!

The only way to satisfy these expectations is probably to put restrictions on the characteristics of jobs so the designer can take advantage of the expected usage of resources. This is certainly the main reason for the success of small, specialized operating systems. It also gives a plausible explanation of the failure of recent "general-purpose" operating systems which try to handle a much greater variety of jobs (in some cases for a variety of machine configurations as well).

Although most components of present computers are sequential in nature, they can work simultaneously to some extent. This influences the design of operating systems so much that the subject can best be described as the management of shared multiprogramming systems.

The main difficulty of multiprogramming is that concurrent activities can interact in a time-dependent manner which makes it practically impossible to locate programming errors by systematic testing. Perhaps, more than anything else, this explains the difficulty of making operating systems reliable.

If we wish to succeed in designing large, reliable multiprogramming systems, we must use programming tools which are so well-structured that most time-dependent errors can be caught at compile time. It seems hopeless to try to solve this problem at the machine level of programming, nor can we expect to improve the situation by means of so-called "implementation languages," which retain the traditional "right" of systems programmers to manipulate addresses freely.

I use the programming language Pascal throughout the text to define operating system concepts concisely by algorithms. Pascal combines the clarity needed for teaching with the efficiency required for design. It is easily understood by programmers familiar with Algol 60 or Fortran, but Pascal is a far more natural programming tool than these languages, particularly with respect to data structuring. As we go along, I extend Pascal with a well-structured notation for multiprogramming.

STRUCTURE

The book contains eight chapters:

Chapter 1 is an overview of operating systems. It defines the purpose of operating systems and outlines their historical development from early batch processing to recent interactive systems. It also points out the influence of technological constraints on the services offered by operating systems.

Chapter 2 on sequential processes discusses the role of abstraction and structure in problem solving and the nature of computations. It summarizes structuring principles of data and sequential programs and gives an example of hierarchal program construction.

Chapter 3 on concurrent processes emphasizes the role of reproducible behavior in program testing and compares various methods of process synchronization: simple and conditional critical regions, semaphores, message buffers, and event queues. It concludes with an analysis of the prevention of deadlocks by a hierarchal ordering of process interactions.

Chapters 2 and 3 present an abstract view of computational processes and their representation in programming languages. The following Chapters, 4 to 6, discuss techniques of implementing processes on computers with limited resources. This problem is mainly technological, and it seems unrealistic to look for a unifying view of how different kinds of components are used efficiently. I try to describe various techniques and point out under which circumstances they are successful.

Chapter 4 on processor management discusses the short-term problems of scheduling concurrent processes on a limited number of processors at the lowest level of programming. It also explains the implementation of synchronizing primitives and evaluates the influence of these abstractions on the real-time characteristics of a system.

Chapter 5 on store management considers the short-term problems of sharing an internal store of limited capacity among concurrent processes. It summarizes current store technology and explains the influence of recursive procedures, concurrent processes, and dynamic relocation on store addressing. It ends with an analysis of placement algorithms and store multiplexing.

Chapter 6 analyzes the performance of various medium-term scheduling algorithms. It uses elementary queuing theory to derive analytical results for the average response time to user requests in a single processor system with these priority rules: first-come first-served, shortest job next, highest response ratio next, and round robin. Foregound-background scheduling is discussed informally.

Chapter 7 is concerned with resource protection--the problem of ensuring that physical resources and data are accessed by well-defined operations within computations authorized to use them. This is a fundamental problem of program design which should have been presented earlier in the book, if only I understood it better. It is handled inadequately in all present operating systems. As fragments of a solution I mention two of the more systematic techniques used: the class concept in Simula 67 and the capability concept.

It is important that a designer of operating systems understand the underlying common principles. But the danger of this division of the subject into separate chapters is that you may find it difficult to see how they fit together into a working system and be unaware of the more subtle interactions between, say, process communication, store management, input/output, and preemptive scheduling.

I have therefore tried to describe a complete operating system in some detail in Chapter 8. It is a case study of the RC 4000 multiprogramming system. It is by no means an ideal system, but it is the only one I know in detail, and is regarded as a consistent, simple, and reliable design which illustrates the concepts and implementation of concurrent processes.

It should perhaps be explained why there are no chapters on input/ output and filing systems. For a particular operating system, considerations about how these tasks are handled are highly relevant. But in this book I have concentrated on the more elementary aspects of these complicated tasks, namely process synchronization, store management, scheduling, and resource protection.

VOCABULARY

In each chapter many words are first used intuitively to give you a feeling for the subject. Later I return to these words and try to give reasonably precise verbal definitions of their meaning. My use of a common word may not always agree completely with the various shades of meaning it has acquired elsewhere, but I hope to justify the usefulness of the concept behind the word and show that it is possible to describe operating systems in an informal but consistent terminology.

The most important terms are collected in a Vocabulary section at the end of the book.

LITERATURE

This book is only one designer's view of operating systems. I urge you to examine my viewpoints critically and compare them with other literature on the subject. As a guide to such a study I have included an annotated selective bibliography at the end of each chapter.

For the sake of completeness I have listed all references mentioned in the text at the end of the book.