Saltzer & Kaashoek Ch. Part II, p. i June 24, 2009 12:14 am
Principles of Computer
System Design
An Introduction
Part II
Chapters 7–11
Jerome H. Saltzer
M. Frans Kaashoek
Massachusetts Institute of Technology
Version 5.0
Saltzer & Kaashoek Ch. Part II, p. ii June 24, 2009 12:14 am
Copyright © 2009 by Jerome H. Saltzer and M. Frans Kaashoek. Some Rights Reserved.
This work is licensed under a Creative Commons Attribution-Non-
commercial-Share Alike 3.0 United States License. For more information on what this
license means, visit
http://creativecommons.org/licenses/by-nc-sa/3.0/us/
Designations used by companies to distinguish their products are often claimed as trade-
marks or registered trademarks. In all instances in which the authors are aware of a claim,
the product names appear in initial capital or all capital letters. All trademarks that
appear or are otherwise referred to in this work belong to their respective owners.
Suggestions, Comments, Corrections, and Requests to waive license restrictions:
Please send correspondence by electronic mail to:
Saltzer@mit.edu
and
kaashoek@mit.edu
Saltzer & Kaashoek Ch. 0, p. iii June 24, 2009 12:21 am
iii
CHAPTER
PART I [In Printed Textbook]
List of Sidebars. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xix
Preface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxvii
Where to Find Part II and other On-line Materials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxvii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxxix
Computer System Design Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xliii
CHAPTER 1 Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
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
Contents
Saltzer & Kaashoek Ch. 0, p. iv June 24, 2009 12:21 am
Contents
iv
CHAPTER 2 Elements of Computer System Organization . . . . . . . . . . . . . . 43
Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44
2.1.
The Three Fundamental Abstractions
. . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.1.1 Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .45
2.1.2 Interpreters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53
2.1.3 Communication Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59
2.2.
Naming in Computer Systems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.2.1 The Naming Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61
2.2.2 Default and Explicit Context References . . . . . . . . . . . . . . . . . . . . . .66
2.2.3 Path Names, Naming Networks, and Recursive Name Resolution . . .71
2.2.4 Multiple Lookup: Searching through Layered Contexts . . . . . . . . . . .73
2.2.5 Comparing Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .75
2.2.6 Name Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .76
2.3.
Organizing Computer Systems with Names and Layers
. . . . . . . . . . . . . . 78
2.3.1 A Hardware Layer: The Bus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .80
2.3.2 A Software Layer: The File Abstraction . . . . . . . . . . . . . . . . . . . . . . .87
2.4.
Looking Back and Ahead
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
2.5.
Case Study:
UNIX
® File System Layering and Naming
. . . . . . . . . . . . . . 91
2.5.1 Application Programming Interface for the
UNIX
File System . . . . . .91
2.5.2 The Block Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .93
2.5.3 The File Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .95
2.5.4 The Inode Number Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .96
2.5.5 The File Name Layer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .96
2.5.6 The Path Name Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .98
2.5.7 Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .99
2.5.8 Renaming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .101
2.5.9 The Absolute Path Name Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . .102
2.5.10 The Symbolic Link Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .104
2.5.11 Implementing the File System API . . . . . . . . . . . . . . . . . . . . . . . .106
2.5.12 The Shell, Implied Contexts, Search Paths, and Name Discovery .110
2.5.13 Suggestions for Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . .112
Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112
CHAPTER 3 The Design of Naming Schemes . . . . . . . . . . . . . . . . . . . . . . . 115
Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .115
3.1.
Considerations in the Design of Naming Schemes
. . . . . . . . . . . . . . . . 116
3.1.1 Modular Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .116
Saltzer & Kaashoek Ch. 0, p. v June 24, 2009 12:21 am
Contents
v
3.1.2 Metadata and Name Overloading . . . . . . . . . . . . . . . . . . . . . . . . . . 120
3.1.3 Addresses: Names that Locate Objects . . . . . . . . . . . . . . . . . . . . . . 122
3.1.4 Generating Unique Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.1.5 Intended Audience and User-Friendly Names. . . . . . . . . . . . . . . . . 127
3.1.6 Relative Lifetimes of Names, Values, and Bindings . . . . . . . . . . . . . 129
3.1.7 Looking Back and Ahead: Names are a Basic System Component . 131
3.2.
Case Study: The Uniform Resource Locator (URL)
. . . . . . . . . . . . . . . 132
3.2.1 Surfing as a Referential Experience; Name Discovery . . . . . . . . . . . 132
3.2.2 Interpretation of the URL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
3.2.3 URL Case Sensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
3.2.4 Wrong Context References for a Partial URL . . . . . . . . . . . . . . . . . 135
3.2.5 Overloading of Names in URLs . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
3.3.
War Stories: Pathologies in the Use of Names
. . . . . . . . . . . . . . . . . . . . 138
3.3.1 A Name Collision Eliminates Smiling Faces . . . . . . . . . . . . . . . . . . 139
3.3.2 Fragile Names from Overloading, and a Market Solution . . . . . . . . 139
3.3.3 More Fragile Names from Overloading, with Market Disruption . . 140
3.3.4 Case-Sensitivity in User-Friendly Names . . . . . . . . . . . . . . . . . . . . 141
3.3.5 Running Out of Telephone Numbers . . . . . . . . . . . . . . . . . . . . . . . 142
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
CHAPTER 4 Enforcing Modularity with Clients and Services . . . . . . . . . . .147
Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
4.1.
Client/service organization
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.1.1 From soft modularity to enforced modularity . . . . . . . . . . . . . . . . . 149
4.1.2 Client/service organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
4.1.3 Multiple clients and services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.1.4 Trusted intermediaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.1.5 A simple example service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.2.
Communication between client and service
. . . . . . . . . . . . . . . . . . . . . 167
4.2.1 Remote procedure call (RPC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
4.2.2 RPCs are not identical to procedure calls . . . . . . . . . . . . . . . . . . . . 169
4.2.3 Communicating through an intermediary . . . . . . . . . . . . . . . . . . . 172
4.3.
Summary and the road ahead
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
4.4.
Case study: The Internet Domain Name System (DNS)
. . . . . . . . . . . 175
4.4.1 Name resolution in DNS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
4.4.2 Hierarchical name management . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
4.4.3 Other features of DNS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
- 1
- 2
前往页