PART I .
List of Sidehars
Preface
Where to find Part II and other On-line Materials
Acknowledgments
CHAPTER I Systems
Overview
1.1 Systems and Complexity
1.1.1 Common Problems of Systems in Many Fields
1.1.2 Systems, Components, Interfaces, and Environments
1.1.3 Complexity
1.2 Sources of Complexity
1.2.1 Cascading and Interacting Requirements
1.2.2 Maintaining High Utilization
1.3 Coping with Complexity I
1.3.1 Modularity
1.3.2 Abstraction
1.3.3 Layering
1.3.4 Hierarchy
1.3.5 Putting it Back Together: Names make Connections
1.4 Computer Systems are the Same but Different
1.4.1 Computer Systems have no Nearby Bounds on Composition
1.4.2 d(technology)/dt is Unprecedented
1.5 Coping with Complexity II
1.5.1 Why Modularity, Abstraction, Layering, and Hierarchy aren't Enough
1.5.2 Iteration
1.5.3 Keep it Simple
What the Rest of this Book is About
Exercises
CHAPTER 2 Elements of Computer System Organization
Overview
2.1 The Three Fundamental Abstractions
2.1.1 Memory
2.1.2 Interpreters
2.1.3 Communication Links
2.2 Naming in Computer Systems
2.2.1 The Naming Model
2.2.2 Default and Explicit Context References
2.2.3 Path Names, Naming Networks, and Recursive Name Resolution
2.2.4 Multiple Lookup: Searching through Layered Contexts
2.2.5 Comparing Names
2.2.6 Name Discovery
2.3 Organizing Computer Systems with Names and Layers
2.3.1 A Hardware Layer: The Bus
2.3.2 A Software Layer: The File Abstraction
2.4 Looking Back and Ahead
2.5 Case Study: UNLX~ File System Layering and Naming
2.5.1 Application Programming Interface for the UNIX File System.
2.5.2 The Block Layer
2.5.3 The File Layer
2.5.4 The Inode Number Layer
2.5.5 The File Name Layer
2.5.6 The Path Name Layer
2.5.7 Links
2.5.8 Renaming
2.5.9 The Absolute Path Name Layer
2.5.10 The Symbolic Link Layer
2.5.11 Implementing the File System API
2.5.12 The Shell and Implied Contexts, Search Paths, and Name Discovery
2.5.13 Suggestions for Further Reading
Exercises
CHAPTER 3 The Design of Naming Schemes
Overview
3.1 Considerations in the Design of Naming Schemes
3.1.1 Modular Sharing
3.1.2 Metadata and Name Overloading
3.1.3 Addresses: Names that Locate Objects
3.1.4 Generating Unique Names
3.1.5 Intended Audience and User-Friendly Names
3.1.6 Relative Lifetimes of Names,Values, and Bindings
3.1.7 Looking Back and Ahead: Names are a Basic System Component
3.2 Case Study: The Uniform Resource Locator (URL)
3.2.1 Surfing as a Referential Experience; Name Discovery
3.2.2 Interpretation of the URL
3.2.3 URL Case Sensitivity
3.2.4 Wrong Context References for a Partial URL
3.2.5 Overloading of Names in URLs
3.3 War Stories: Pathologies in the Use of Names
3.3.1 A Name Collision Eliminates Smiling Faces
3.3.2 Fragile Names from Overloading, and a Market Solution
3.3.3 More Fragile Names from Overloading, with Market Disruption
3.3.4 Case-Sensitivity in User-Friendly Names
3.3.5 Running Out of Telephone Numbers
Exercises
CHAPTER 4 Enforcing Modularity with Clients and Services
Overview
4.1 Client/Service Organization
4.1.1 From Soft Modularity to Enforced Modularity
4.1.2 Client/Service Organization
4.1.3 Multiple Clients and Services
4.1.4 Trusted Intermediaries
4.1.5 A Simple Example Service
4.2 Communication Between Client and Service
4.2.1 Remote Procedure Call (RPC)
4.2.2 RPCs are not Identical to Procedure Calls
4.2.3 Communicating through an Intermediary
4.3 Summary andThe Road Ahead ',
4.4 Case Study: The Internet Domain Name System (DNS)
4.4.1 Name Resolution in DNS
4.4.2 Hierarchical Name Management
4.4.3 Other Features of DNS
4.4.4 Name Discovery in DNS
4.4.5 Trustworthiness of DNS Responses
4.5 Case Study: The Network File System (NFS)
4.5.1 Naming Remote Files and Directories
4.5.2 The NFS Remote Procedure CaBs
4.5.3 Extending the UNIX File System to Support NFS
4.5.4 Coherence
4.5.5 NFSVersion 3 and Beyond
Exercises
CHAPTER 5 Enforcing Modularity with Virtualization
Overview
5.1 Client/Server Organization within a Computer Using Virtualization
5.1.1 Abstractions for Virtualizing Computers
5.1.2 Emulation andVirtual Machines
5.1.3 Roadmap: Step-by-Step Virtualization
5.2 Virtual Links Using SEND, RECEIVE, and a Bounded Buffer
5.2.1 An Interface for SEND and RECEIVE with Bounded Buffers
5.2.2 Sequence Coordination with a Bounded Buffer
5.2.3 Race Conditions
5.2.4 Locks and Before-or-AfterActions
5.2.5 Deadlock
5.2.6 Implementing ACQUIRE and RELEASE
5.2.7 Implementing a Before-or-AfterAction Using the One-Writer Principle
5.2.8 Coordination between Synchronous Islands with Asynchronous Connections
5.3 Enforcing Modularity in Memory
5.3.1 Enforcing Modularity with Domains
5.3.2 Controlled Sharing Using Several Domains
5.3.3 More Enforced Modularity with Kernel and User Mode
5.3.4 Gates and Changing Modes
5.3.5 Enforcing Modularity for Bounded Buffers
5.3.6 The Kernel
5,4 Virtualizing Memory
5.4.1 Virtualizing Addresses
5.4.2 Translating Addresses Using a Page Map ..
5.4.3 Virtual Address Spaces
5.4.4 Hardware versus Software and the Translation Look-Aside Buffer
5.4.5 Segments (Advanced Topic)
5.5 Virtualizing Processors Using Threads
5.5.1 Sharing a ProcessorAmong Multiple Threads
5.5.2 Implementing YIELD
5.5.3 Creating and Terminating Threads
5.5.4 Enforcing Modularity with Threads: Preemptive Scheduling
5.5.5 Enforcing Modularity with Threads and Address Spaces
5.5.6 Layering Threads
5.B Thread Primitives for Sequence Coordination
5.6.1 The Lost Notification Problem
5.6.2 Avoiding the Lost Notification Problem with Eventcounts and Sequencers
5.6.3 Implementing AWAIT, ADVANCE, TICKET, and READ (Advanced Topic)
5.6.4 Polling, Interrupts, and Sequence Coordination
5.7 Case Study: Evolution of Enforced Modularity in the Intel x86
5.7.1 The Early Designs: No Support for Enforced Modularity
5.7.2 Enforcing Modularity Using Segmentation
5.7.3 Page-Based Virtual Address Spaces
5.7.4 Summary: More Evolution
5.8 Application: Enforcing Modularity Using Virtual Machines
5.8.1 Virtual Machine Uses
5.8.2 Implementing Virtual Machines
5.8.3 Virtualizing Example
Exercises
CHAPTER 6 Performance
Overview
6.1 Designing for Performance
6.1.1 Performance Metrics
6.1.2 A Systems Approach to Designing for Performance
6.1.3 Reducing Latency by ExploitingWorldoad Properties
6.1.4 Reducing Latency using Concurrency
6.1.5 Improving Throughput: Concurrency
6.1.6 Queuing and Overload
6.1.7 Fighting Bottlenecks
6.1.8 An Example: The I/O Bottleneck
6.2 Multilevel Memories
6.2.1 Memory Characterization
6.2.2 Multilevel Memory Management using Virtual Memory
6.2.3 Adding Multilevel Memory Management to a Virtual Memory
6.2.4 Analyzing Multilevel Memory Systems
6.2.5 Locality of Reference and Working Sets
6.2.6 Multilevel Memory Management Policies
6.2.7 Comparative Analysis of Different Policies
6.2.8 Other Page-Removal Algorithms
6.2.90therAspects of Multilevel Memory Management
6.3 Scheduling
6.5.1 Scheduling Resources
6.3.2 Scheduling Metrics
6.3.3 Scheduling Policies
6.5.4 Case Study: Scheduling the DiskArm
Exercises
About Part II
Appendix A: The Binary Classification Trade-off
Suggestions for Further Reading
Problem Sets
Glossary
index of Concepts
PART II [ON-LINE]
Preface to Part II
CHAPTER 7 The Network as a System and as a System Component
Overview
7.1 Interesting Properties of Networks
7.2 Getting Organized: Layers
7.3 The Link Layer
7.4 The Network Layer
7.5 The End-to-end Layer
7.6 A Network System Design Issue: Congestion Control
7.7 Wrapping up Networks
7.8 Case Study: Mapping the Internet to the Ethernet
7.9 War Stories: Surprises in Protocol Design
Exercises
CHAPTER 8 Fault Tolerance: Reliable Systems from Unreliable Components
Overview
8.1 Faults, Failures, and Fault-Tolerant Design
8.2 Measures of Reliability and Failure Tolerance
8.3 Tolerating Active Faults
8.4 Systematically Applying Redundancy
8.5 Applying Redundancy to Software and Data
8.6 Wrapping up Reliability
8.7 Application: A Fault Tolerance Model for RAM
8.8 War Stories: Fault-Tolerant Systems that Failed
Exercises
CHAPTER 9 Atomicity: All-or-nothing and Before-or-after
Overview
9.1 Atomicity
9.2 All-or-NothingAtomicity I: Concepts
9.3 All-or-Nothing Atomicity II: Pragmatics
9.4 Before-or-AfterAtomicity I: Concepts
9.5 Before-or-AfterAtomicity II: Pragmatics
9.6 Atomicity across Layers and Multiple Sites
9.7 Case Studies: Machine Language Atomicity
9,8 A More Complete Model of Disk Failure (Advanced Topic)
Exercises
CHAPTER 10 Consistency
Overview
10.1 Constraints and Interface Consistency
10.2 Cache Coherence
10.3 Durable Storage Revisited: Geographically Separated Replicas
10.4 Reconciliation
10.5 Perspectives
Exercises
CHAPTER 11 Information Security
Overview
11.1 Introduction to Secure Systems
11.2 Authenticating Principals
11.3 Authenticating Messages
11.4 Message Confidentiality
11.5 Security Protocols
11.6 Authorization: Controlled Sharing
11.7 Reasoning about Authentication (Advanced Topic)
11.8 Summary
11.9 Cryptography as a Building Block (Advanced Topic)
11.10 Case Study: Transport Layer Security (TLS) for the Web
11.11 War Stories: Security System Breaches
Exercises
Suggestions for Further Reading
Problem Sets
Glossary
Complete Index to Parts I and II ...