Principles of Computer System Design: An Introductionby Jerome H. Saltzer, M. Frans Kaashoek
This text identifies, examines, and illustrates fundamental concepts in computer system design that are common across operating systems, networks, database systems, distributed systems, programming languages, software engineering, security, fault tolerance, and architecture. Through carefully analyzed case studies from each of these disciplines, it demonstrates how… See more details below
This text identifies, examines, and illustrates fundamental concepts in computer system design that are common across operating systems, networks, database systems, distributed systems, programming languages, software engineering, security, fault tolerance, and architecture. Through carefully analyzed case studies from each of these disciplines, it demonstrates how to apply these concepts to tackle practical system design problems. To support the focus on design, the text identifies and explains abstractions that have proven successful in practice such as, remote procedure call, client/service organization, file systems, data integrity, consistency, and authenticated messages. Most computer systems are built using a handful of such abstractions. The text describes how these abstractions are implemented, demonstrates how they are used in different systems, and prepares the reader to apply them in future designs.
This unique book is offered in an online / offline split: Chapters 1-6 are included in the book available from Morgan Kaufmann in print or ebook form. Chapters 7-11 are available online under a Creative Commons license. Download them for free at http://www.elsevierdirect.com/companion.jsp?ISBN=9780123749574Features:
• Concepts of computer system design guided by fundamental principles. • Cross-cutting approach that identifies abstractions common to networking, operating systems, transaction systems, distributed systems, architecture, and software engineering. • Case studies that make the abstractions real: naming (DNS and the URL); file systems (the UNIX file system); clients and services (NFS); virtualization (virtual machines); scheduling (disk arms); security (TLS). • Numerous pseudocode fragments that provide concrete examples of abstract concepts. • Extensive support. The authors and MIT OpenCourseWare provide on-line, free of charge, open educational resources, including additional chapters, course syllabi, board layouts and slides, lecture videos, and an archive of lecture schedules, class assignments, and design projects.
Read an Excerpt
Principles of Computer System DesignAn Introduction
By Jerome H. Saltzer M. Frans Kaashoek
MORGAN KAUFMANNCopyright © 2009 Jerome H. Saltzer and M. Frans Kaashoek
All right reserved.
Overview 2 1.1 Systems and Complexity 3 1.1.1 Common Problems of Systems in Many Fields 3 1.1.2 Systems, Components, Interfaces, and Environments 8 1.1.3 Complexity 10 1.2 Sources of Complexity 13 1.2.1 Cascading and Interacting Requirements 13 1.2.2 Maintaining High Utilization 17 1.3 Coping with Complexity I 19 1.3.1 Modularity 19 1.3.2 Abstraction 20 1.3.3 Layering 24 1.3.4 Hierarchy 25 1.3.5 Putting it Back Together: Names make Connections 26 1.4 Computer Systems are the Same but Different 27 1.4.1 Computer Systems have no Nearby Bounds on Composition 28 1.4.2 d(technology)/dt is Unprecedented 31 1.5 Coping With Complexity II 35 1.5.1 Why Modularity, Abstraction, Layering, and Hierarchy aren't Enough 36 1.5.2 Iteration 36 1.5.3 Keep it Simple 39 What The Rest of this Book is About 40 Exercises 41
This book is about computer systems, and this chapter introduces some of the vocabulary and concepts used in designing computer systems. It also introduces "systems perspective", a way of thinking about systems that is global and encompassing rather than focused on particular issues. A full appreciation of this way of thinking can't really be captured in a short summary, so this chapter is actually just a preview of ideas that will be developed in depth in succeeding chapters.
The usual course of study of computer science and engineering begins with linguistic constructs for describing computations (software) and physical constructs for realizing computations (hardware). It then branches, focusing, for example, on the theory of computation, artificial intelligence, or the design of systems, which itself is usually divided into specialities: operating systems, transaction and database systems, computer architecture, software engineering, compilers, computer networks, security, and reliability. Rather than immediately tackling one of those specialties, we assume that the reader has completed the introductory courses on software and hardware, and we begin a broad study of computer systems that supports the entire range of systems specialties.
Many interesting applications of computers require
* fault tolerance
* coordination of concurrent activities
* geographically separated but linked data
* vast quantities of stored information
* protection from mistakes and intentional attacks
* interactions with many people
To develop applications that have these requirements, the designer must look beyond the software and hardware and view the computer system as a whole. In doing so, the designer encounters many new problems—so many that the limit on the scope of computer systems generally arises neither from laws of physics nor from theoretical impossibility, but rather from limitations of human understanding.
Some of these same problems have counterparts, or at least analogs, in other systems that have, at most, only incidental involvement of computers. The study of systems is one place where computer engineering can take advantage of knowledge from other engineering areas: civil engineering (bridges and skyscrapers), urban planning (the design of cities),mechanical engineering (automobiles and air conditioning),aviation and space flight, electrical engineering, and even ecology and political science. We start by looking at some of those common problems. Then we will examine two ways in which computer systems pose problems that are quite different. Don't worry if some of the examples are of things you have never encountered or are only dimly aware of. The sole purpose of the examples is to illustrate the range of considerations and similarities across different kinds of systems.
As we proceed in this chapter and throughout the book, we shall point out a series of system design principles, which are rules of thumb that usually apply to a diverse range of situations. Design principles are not immutable laws, but rather guidelines that capture wisdom and experience and that can help a designer avoid making mistakes. The astute reader will quickly realize that sometimes a tension, even to the point of contradiction, exists between different design principles. Nevertheless, if a designer finds that he or she is violating a design principle, it is a good idea to review the situation carefully.
At the first encounter of a design principle, the text displays it prominently. Here is an example, found on page 16.
Each design principle thus has a formal title ("Avoid excessive generality") and a brief informal description ("If it's good for ..."), which are intended to help recall the principle. Most design principles will show up several times, in different contexts, which is one reason why they are useful. The text highlights later encounters of a principle such as: avoid excessive generality. A list of all of the design principles in the book can be found on the inside front cover and also in the index, under "Design principles".
The remaining sections of this chapter discuss common problems of systems, the sources of those problems, and techniques for coping with them.
1.1 SYSTEMS AND COMPLEXITY
1.1.1 Common Problems of Systems in Many Fields
The problems one encounters in these many kinds of systems can usefully be divided into four categories: emergent properties, propagation of effects, incommensurate scaling, and trade-offs.
22.214.171.124 Emergent Properties
Emergent properties are properties that are not evident in the individual components of a system, but show up when combining those components, so they might also be called surprises. Emergent properties abound in most systems, although there can always be a (fruitless) argument about whether or not careful enough prior analysis of the components might have allowed prediction of the surprise. It is wise to avoid this argument and instead focus on an unalterable fact of life: some things turn up only when a system is built.
Some examples of emergent properties are well known. The behavior of a committee or a jury often surprises outside observers. The group develops a way of thinking that could not have been predicted from knowledge about the individuals. (The concept of—and the label for—emergent properties originated in sociology.) When the Millennium Bridge for pedestrians over the RiverThames in London opened, its designers had to close it after only a few days. They were surprised to discover that pedestrians synchronize their footsteps when the bridge sways, causing it to sway even more. Interconnection of several electric power companies to allow load sharing helps reduce the frequency of power failures, but when a failure finally occurs it may take down the entire interconnected structure. The political surprise is that the number of customers affected may be large enough to attract the unwanted attention of government regulators.
126.96.36.199 Propagation of Effects
The electric power inter-tie also illustrates the second category of system problems—propagation of effects—when a tree falling on a power line in Oregon leads to the lights going out in New Mexico, 1000 miles away. What looks at first to be a small disruption or a local change can have effects that reach from one end of a system to the other. An important requirement in most system designs is to limit the impact of failures. As another example of propagation of effects, consider an automobile designer's decision to change the tire size on a production model car from 13 to 15 inches. The reason for making the change might have been to improve the ride. On further analysis, this change leads to many other changes: redesigning the wheel wells, enlarging the spare tire space, rearranging the trunk that holds the spare tire, and moving the back seat forward slightly to accommodate the trunk redesign. The seat change makes knee room in the back seat too small, so the backs of the seats must be made thinner, which in turn reduces the comfort that was the original reason for changing the tire size, and it may also reduce safety in a collision. The extra weight of the trunk and rear seat design means that stiffer rear springs are now needed. The rear axle ratio must be modified to keep the force delivered to the road by the wheels correct, and the speedometer gearing must be changed to agree with the new tire size and axle ratio.
Those effects are the obvious ones. In complicated systems, as the analysis continues, more distant and subtle effects normally appear. As a typical example, the automobile manufacturer may find that the statewide purchasing office for Texas does not currently have a certified supplier for replacement tires of the larger size. Thus there will probably be no sales of cars to the Texas government for two years, which is the length of time it takes to add a supplier onto the certified list. Folk wisdom characterizes propagation of effects as: "There are no small changes in a large system".
188.8.131.52 Incommensurate Scaling
The third characteristic problem encountered in the study of systems is incommensurate scaling: as a system increases in size or speed, not all parts of it follow the same scaling rules, so things stop working. The mathematical description of this problem is that different parts of the system exhibit different orders of growth. Some examples:
* Galileo observed that "nature cannot produce a ... giant ten times taller than an ordinary man unless by ... greatly altering the proportions of his limbs and especially of his bones, which would have to be considerably enlarged over the ordinary" [Discourses and Mathematical Demonstrations on Two New Sciences, second day, Leiden, 1638]. In a classic 1928 paper, "On being the right size" [see Suggestions for Further Reading 1.4.1], J. B. S. Haldane uses the example of a mouse, which, if scaled up to the size of an elephant, would collapse of its own weight. For both examples, the reason is that weight grows with volume, which is proportional to the cube of linear size, but bone strength, which depends primarily on cross-sectional area, grows only with the square of linear size. Thus a real elephant requires a skeletal arrangement that is quite different from that of a scaled-up mouse.
* The Egyptian architect Sneferu tried to build larger and larger pyramids. Unfortunately, the facing fell off the pyramid at Meidum, and the ceiling of the burial chamber of the pyramid at Dashur cracked. He later figured out that he could escalate a pyramid to the size of the pyramids at Giza by lowering the ratio of the pyramid's height to its width. The reason this solution worked has apparently never been completely analyzed, but it seems likely that incommensurate scaling was involved—the weight of a pyramid increases with the cube of its linear size, while the strength of the rock used to create the ceiling of a burial chamber increases only with the area of its cross-section, which grows with the square.
Excerpted from Principles of Computer System Design by Jerome H. Saltzer M. Frans Kaashoek Copyright © 2009 by Jerome H. Saltzer and M. Frans Kaashoek. Excerpted by permission of MORGAN KAUFMANN. All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
and post it to your social network
Most Helpful Customer Reviews
See all customer reviews >