第1页 / 共2523页
第2页 / 共2523页
第3页 / 共2523页
第4页 / 共2523页
第5页 / 共2523页
第6页 / 共2523页
第7页 / 共2523页
第8页 / 共2523页
Computer Systems A Programmer's Perspective 3rd.pdf
Computer Systems A Programmer's Perspective
Computer Systems A Programmer's Perspective
MasteringEngineering®
Contents
Preface
Assumptions about the Reader's Background
How to Read the Book
Book Overview
New to This Edition
Origins of the Book
For Instructors: Courses Based on the Book
For Instructors: Classroom-Tested Laboratory Exercises
About the Authors
Chapter 1 A Tour of Computer Systems
1.1 Information Is Bits + Context
1.2 Programs Are Translated by Other Programs into Different Forms
1.3 It Pays to Understand How Compilation Systems Work
1.4 Processors Read and Interpret Instructions Stored in Memory
1.4.1 Hardware Organization of a System
Buses
I/O Devices
Main Memory
Processor
1.4.2 Running the hello Program
1.5 Caches Matter
1.6 Storage Devices Form a Hierarchy
1.7 The Operating System Manages the Hardware
1.7.1 Processes
1.7.2 Threads
1.7.3 Virtual Memory
1.7.4 Files
1.8 Systems Communicate with Other Systems Using Networks
1.9 Important Themes
1.9.1 Amdahl's Law
Practice Problem 1.1 (solution page 28)
Practice Problem 1.2 (solution page 28)
1.9.2 Concurrency and Parallelism
Thread-Level Concurrency
Instruction-Level Parallelism
Single-Instruction, Multiple-Data (SIMD) Parallelism
1.9.3 The Importance of Abstractions in Computer Systems
1.10 Summary
Bibliographic Notes
Part I Program Structure and Execution
Chapter 2 Representing and Manipulating Information
2.1 Information Storage
2.1.1 Hexadecimal Notation
Practice Problem 2.1 (solution page 143)
Practice Problem 2.2 (solution page 143)
Practice Problem 2.3 (solution page 144)
Practice Problem 2.4 (solution page 144)
2.1.2 Data Sizes
2.1.3 Addressing and Byte Ordering
Practice Problem 2.5 (solution page 144)
Practice Problem 2.6 (solution page 145)
2.1.4 Representing Strings
Practice Problem 2.7 (solution page 145)
2.1.5 Representing Code
2.1.6 Introduction to Boolean Algebra
Practice Problem 2.8 (solution page 145)
Practice Problem 2.9 (solution page 146)
2.1.7 Bit-Level Operations in C
Practice Problem 2.10 (solution page 146)
Practice Problem 2.11 (solution page 146)
Practice Problem 2.12 (solution page 146)
Practice Problem 2.13 (solution page 147)
2.1.8 Logical Operations in C
Practice Problem 2.14 (solution page 147)
Practice Problem 2.15 (solution page 148)
2.1.9 Shift Operations in C
Practice Problem 2.16 (solution page 148)
2.2 Integer Representations
2.2.1 Integral Data Types
2.2.2 Unsigned Encodings
2.2.3 Two's-Complement Encodings
Practice Problem 2.17 (solution page 148)
Practice Problem 2.18 (solution page 149)
2.2.4 Conversions between Signed and Unsigned
Practice Problem 2.19 (solution page 149)
Practice Problem 2.20 (solution page 149)
2.2.5 Signed versus Unsigned in C
Practice Problem 2.21 (solution page 149)
2.2.6 Expanding the Bit Representation of a Number
Practice Problem 2.22 (solution page 150)
Practice Problem 2.23 (solution page 150)
2.2.7 Truncating Numbers
Practice Problem 2.24 (solution page 150)
2.2.8 Advice on Signed versus Unsigned
Practice Problem 2.25 (solution page 151)
Practice Problem 2.26 (solution page 151)
2.3 Integer Arithmetic
2.3.1 Unsigned Addition
Practice Problem 2.27 (solution page 152)
Practice Problem 2.28 (solution page 152)
2.3.2 Two's-Complement Addition
Practice Problem 2.29 (solution page 152)
Practice Problem 2.30 (solution page 153)
Practice Problem 2.31 (solution page 153)
Practice Problem 2.32 (solution page 153)
2.3.3 Two's-Complement Negation
Practice Problem 2.33 (solution page 153)
2.3.4 Unsigned Multiplication
2.3.5 Two's-Complement Multiplication
Practice Problem 2.34 (solution page 153)
Practice Problem 2.35 (solution page 154)
Practice Problem 2.36 (solution page 154)
Practice Problem 2.37 (solution page 155)
2.3.6 Multiplying by Constants
Practice Problem 2.38 (solution page 155)
Practice Problem 2.39 (solution page 156)
Practice Problem 2.40 (solution page 156)
Practice Problem 2.41 (solution page 156)
2.3.7 Dividing by Powers of 2
Practice Problem 2.42 (solution page 156)
Practice Problem 2.43 (solution page 157)
2.3.8 Final Thoughts on Integer Arithmetic
Practice Problem 2.44 (solution page 157)
2.4 Floating Point
2.4.1 Fractional Binary Numbers
Practice Problem 2.45 (solution page 157)
Practice Problem 2.46 (solution page 158)
2.4.2 IEEE Floating-Point Representation
2.4.3 Example Numbers
Practice Problem 2.47 (solution page 158)
Practice Problem 2.48 (solution page 159)
Practice Problem 2.49 (solution page 159)
2.4.4 Rounding
Practice Problem 2.50 (solution page 159)
Practice Problem 2.51 (solution page 159)
Practice Problem 2.52 (solution page 160)
2.4.5 Floating-Point Operations
2.4.6 Floating Point in C
Practice Problem 2.53 (solution page 160)
Practice Problem 2.54 (solution page 160)
2.5 Summary
Bibliographic Notes
Homework Problems
2.55 ♦
2.56 ♦
2.57 ♦
2.58 ♦♦
2.59 ♦♦
2.60 ♦♦
Bit-Level Integer Coding Rules
2.61 ♦♦
2.62 ♦♦♦
2.63 ♦♦♦
2.64 ♦
2.65 ♦♦♦♦
2.66 ♦♦♦♦
2.67 ♦♦
2.68 ♦♦
2.69 ♦♦♦
2.70 ♦♦
2.71
2.72
2.73
2.74
2.75
2.76
2.77
2.78
2.79
2.80
2.81
2.82
2.83
2.84
2.85
2.86
2.87
2.88
2.89
2.90
2.91
Bit-Level Floating-Point Coding Rules
2.92 ♦♦
2.94
2.95
2.96
2.97
Chapter 3 Machine-Level Representation of Programs
3.1 A Historical Perspective
3.2 Program Encodings
3.2.1 Machine-Level Code
3.2.2 Code Examples
3.2.3 Notes on Formatting
3.3 Data Formats
3.4 Accessing Information
3.4.1 Operand Specifiers
Practice Problem 3.1 (solution page 325)
3.4.2 Data Movement Instructions
Practice Problem 3.2 (solution page 325)
Practice Problem 3.3 (solution page 326)
3.4.3 Data Movement Example
Practice Problem 3.4 (solution page 326)
Practice Problem 3.5 (solution page 327)
3.4.4 Pushing and Popping Stack Data
3.5 Arithmetic and Logical Operations
3.5.1 Load Effective Address
Practice Problem 3.6 (solution page 327)
Practice Problem 3.7 (solution page 328)
3.5.2 Unary and Binary Operations
Practice Problem 3.8 (solution page 328)
3.5.3 Shift Operations
Practice Problem 3.9 (solution page 328)
3.5.4 Discussion
Practice Problem 3.10 (solution page 329)
Practice Problem 3.11 (solution page 329)
3.5.5 Special Arithmetic Operations
Practice Problem 3.12 (solution page 329)
3.6 Control
3.6.1 Condition Codes
3.6.2 Accessing the Condition Codes
Practice Problem 3.13 (solution page 330)
Practice Problem 3.14 (solution page 330)
3.6.3 Jump Instructions
3.6.4 Jump Instruction Encodings
Practice Problem 3.15 (solution page 330)
3.6.5 Implementing Conditional Branches with Conditional Control
Practice Problem 3.16 (solution page 331)
Practice Problem 3.17 (solution page 331)
Practice Problem 3.18 (solution page 332)
3.6.6 Implementing Conditional Branches with Conditional Moves
Practice Problem 3.19 (solution page 332)
Practice Problem 3.20 (solution page 333)
Practice Problem 3.21 (solution page 333)
3.6.7 Loops
Do-While Loops
Practice Problem 3.22 (solution page 333)
Practice Problem 3.23 (solution page 334)
While Loops
Practice Problem 3.24 (solution page 335)
Practice Problem 3.25 (solution page 335)
Practice Problem 3.26 (solution page 336)
For Loops
Practice Problem 3.27 (solution page 336)
Practice Problem 3.28 (solution page 336)
Practice Problem 3.29 (solution page 337)
3.6.8 Switch Statements
Practice Problem 3.30 (solution page 338)
Practice Problem 3.31 (solution page 338)
3.7 Procedures
3.7.1 The Run-Time Stack
3.7.2 Control Transfer
Practice Problem 3.32 (solution page 339)
3.7.3 Data Transfer
Practice Problem 3.33 (solution page 339)
3.7.4 Local Storage on the Stack
3.7.5 Local Storage in Registers
Practice Problem 3.34 (solution page 340)
3.7.6 Recursive Procedures
Practice Problem 3.35 (solution page 340)
3.8 Array Allocation and Access
3.8.1 Basic Principles
Practice Problem 3.36 (solution page 341)
3.8.2 Pointer Arithmetic
Practice Problem 3.37 (solution page 341)
3.8.3 Nested Arrays
Practice Problem 3.38 (solution page 341)
3.8.4 Fixed-Size Arrays
Practice Problem 3.39 (solution page 342)
Practice Problem 3.40 (solution page 342)
3.8.5 Variable-Size Arrays
3.9 Heterogeneous Data Structures
3.9.1 Structures
Practice Problem 3.41 (solution page 343)
Practice Problem 3.42 (solution page 343)
3.9.2 Unions
Practice Problem 3.43 (solution page 344)
3.9.3 Data Alignment
Practice Problem 3.44 (solution page 345)
Practice Problem 3.45 (solution page 345)
3.10 Combining Control and Data in Machine-Level Programs
3.10.1 Understanding Pointers
3.10.2 Life in the Real World: Using the gdb Debugger
3.10.3 Out-of-Bounds Memory References and Buffer Overflow
Practice Problem 3.46 (solution page 346)
3.10.4 Thwarting Buffer Overflow Attacks
Stack Randomization
Practice Problem 3.47 (solution page 347)
Stack Corruption Detection
Practice Problem 3.48 (solution page 347)
Limiting Executable Code Regions
3.10.5 Supporting Variable-Size Stack Frames
Practice Problem 3.49 (solution page 347)
3.11 Floating-Point Code
3.11.1 Floating-Point Movement and Conversion Operations
Practice Problem 3.50 (solution page 347)
Practice Problem 3.51 (solution page 348)
3.11.2 Floating-Point Code in Procedures
Practice Problem 3.52 (solution page 348)
3.11.3 Floating-Point Arithmetic Operations
Practice Problem 3.53 (solution page 348)
Practice Problem 3.54 (solution page 349)
3.11.4 Defining and Using Floating-Point Constants
Practice Problem 3.55 (solution page 349)
3.11.5 Using Bitwise Operations in Floating-Point Code
Practice Problem 3.56 (solution page 350)
3.11.6 Floating-Point Comparison Operations
Practice Problem 3.57 (solution page 350)
3.11.7 Observations about Floating-Point Code
3.12 Summary
Bibliographic Notes
Homework Problems
3.58
3.59
3.60
3.61
3.62
3.63
3.64
3.65
3.66
3.67
3.68
3.69
3.70
3.71
3.72
3.73
3.74
3.75
Chapter 4 Processor Architecture
4.1 The Y86-64 Instruction Set Architecture
4.1.1 Programmer-Visible State
4.1.2 Y86-64 Instructions
4.1.3 Instruction Encoding
Practice Problem 4.1 (solution page 480)
Practice Problem 4.2 (solution page 481)
4.1.4 Y86-64 Exceptions
4.1.5 Y86-64 Programs
Practice Problem 4.3 (solution page 482)
Practice Problem 4.4 (solution page 482)
Practice Problem 4.5 (solution page 483)
Practice Problem 4.6 (solution page 483)
4.1.6 Some Y86-64 Instruction Details
Practice Problem 4.7 (solution page 484)
Practice Problem 4.8 (solution page 484)
4.2 Logic Design and the Hardware Control Language HCL
4.2.1 Logic Gates
4.2.2 Combinational Circuits and HCL Boolean Expressions
Practice Problem 4.9 (solution page 484)
4.2.3 Word-Level Combinational Circuits and HCL Integer Expressions
Practice Problem 4.10 (solution page 484)
Practice Problem 4.11 (solution page 484)
Practice Problem 4.12 (solution page 484)
4.2.4 Set Membership
4.2.5 Memory and Clocking
4.3 Sequential Y86-64 Implementations
4.3.1 Organizing Processing into Stages
Practice Problem 4.13 (solution page 485)
Practice Problem 4.14 (solution page 486)
Practice Problem 4.15 (solution page 486)
Practice Problem 4.16 (solution page 486)
Practice Problem 4.17 (solution page 486)
Practice Problem 4.18 (solution page 487)
4.3.2 SEQ Hardware Structure
4.3.3 SEQ Timing
4.3.4 SEQ Stage Implementations
Fetch Stage
Practice Problem 4.19 (solution page 487)
Decode and Write-Back Stages
Practice Problem 4.20 (solution page 488)
Practice Problem 4.21 (solution page 488)
Practice Problem 4.22 (solution page 488)
Execute Stage
Practice Problem 4.23 (solution page 488)
Practice Problem 4.24 (solution page 488)
Memory Stage
Practice Problem 4.25 (solution page 488)
Practice Problem 4.26 (solution page 489)
Practice Problem 4.27 (solution page 489)
PC Update Stage
Surveying SEQ
4.4 General Principles of Pipelining
4.4.1 Computational Pipelines
4.4.2 A Detailed Look at Pipeline Operation
4.4.3 Limitations of Pipelining
Nonuniform Partitioning
Practice Problem 4.28 (solution page 489)
Diminishing Returns of Deep Pipelining
Practice Problem 4.29 (solution page 490)
4.4.4 Pipelining a System with Feedback
4.5 Pipelined Y86-64 Implementations
4.5.1 SEQ+: Rearranging the Computation Stages
4.5.2 Inserting Pipeline Registers
4.5.3 Rearranging and Relabeling Signals
4.5.4 Next PC Prediction
4.5.5 Pipeline Hazards
Avoiding Data Hazards by Stalling
Avoiding Data Hazards by Forwarding
Load/Use Data Hazards
Avoiding Control Hazards
4.5.6 Exception Handling
4.5.7 PIPE Stage Implementations
PC Selection and Fetch Stage
Practice Problem 4.30 (solution page 490)
Decode and Write-Back Stages
Practice Problem 4.31 (solution page 490)
Practice Problem 4.32 (solution page 490)
Practice Problem 4.33 (solution page 491)
Practice Problem 4.34 (solution page 491)
Execute Stage
Practice Problem 4.35 (solution page 491)
Memory Stage
Practice Problem 4.36 (solution page 492)
4.5.8 Pipeline Control Logic
Desired Handling of Special Control Cases
Detecting Special Control Conditions
Pipeline Control Mechanisms
Combinations of Control Conditions
Practice Problem 4.37 (solution page 492)
Practice Problem 4.38 (solution page 492)
Control Logic Implementation
Practice Problem 4.39 (solution page 493)
Practice Problem 4.40 (solution page 493)
Practice Problem 4.41 (solution page 493)
Practice Problem 4.42 (solution page 493)
4.5.9 Performance Analysis
Practice Problem 4.43 (solution page 494)
Practice Problem 4.44 (solution page 494)
4.5.10 Unfinished Business
Multicycle Instructions
Interfacing with the Memory System
4.6 Summary
4.6.1 Y86-64 Simulators
Bibliographic Notes
Homework Problems
4.45
4.46
4.47
4.48
4.49
4.50
4.51
4.52
4.53
4.54
4.55
4.56
4.57
4.58
4.59
Chapter 5 Optimizing Program Performance
5.1 Capabilities and Limitations of Optimizing Compilers
Practice Problem 5.1 (solution page 573)
5.2 Expressing Program Performance
Practice Problem 5.2 (solution page 573)
5.3 Program Example
5.4 Eliminating Loop Inefficiencies
Practice Problem 5.3 (solution page 573)
5.5 Reducing Procedure Calls
5.6 Eliminating Unneeded Memory References
Practice Problem 5.4 (solution page 574)
5.7 Understanding Modern Processors
5.7.1 Overall Operation
5.7.2 Functional Unit Performance
5.7.3 An Abstract Model of Processor Operation
From Machine-Level Code to Data-Flow Graphs
Other Performance Factors
Practice Problem 5.5 (solution page 575)
Practice Problem 5.6 (solution page 575)
5.8 Loop Unrolling
Practice Problem 5.7 (solution page 575)
5.9 Enhancing Parallelism
5.9.1 Multiple Accumulators
5.9.2 Reassociation Transformation
Practice Problem 5.8 (solution page 576)
5.10 Summary of Results for Optimizing Combining Code
5.11 Some Limiting Factors
5.11.1 Register Spilling
5.11.2 Branch Prediction and Misprediction Penalties
Do Not Be Overly Concerned about Predictable Branches
Write Code Suitable for Implementation with Conditional Moves
Practice Problem 5.9 (solution page 576)
5.12 Understanding Memory Performance
5.12.1 Load Performance
5.12.2 Store Performance
Practice Problem 5.10 (solution page 577)
Practice Problem 5.11 (solution page 577)
Practice Problem 5.12 (solution page 577)
5.13 Life in the Real World: Performance Improvement Techniques
5.14 Identifying and Eliminating Performance Bottlenecks
5.14.1 Program Profiling
5.14.2 Using a Profiler to Guide Optimization
5.15 Summary
Bibliographic Notes
Homework Problems
5.13 ♦♦
5.14 ♦
5.15 ♦
5.16 ♦
5.17 ♦♦
5.18 ♦♦♦
5.19 ♦♦♦
Chapter 6 The Memory Hierarchy
6.1 Storage Technologies
6.1.1 Random Access Memory
Static RAM
Dynamic RAM
Conventional DRAMs
Memory Modules
Practice Problem 6.1 (solution page 660)
Enhanced DRAMs
Nonvolatile Memory
Accessing Main Memory
6.1.2 Disk Storage
Disk Geometry
Disk Capacity
Practice Problem 6.2 (solution page 661)
Disk Operation
Practice Problem 6.3 (solution page 661)
Logical Disk Blocks
Practice Problem 6.4 (solution page 661)
Connecting I/O Devices
Accessing Disks
6.1.3 Solid State Disks
Practice Problem 6.5 (solution page 662)
6.1.4 Storage Technology Trends
Practice Problem 6.6 (solution page 662)
6.2 Locality
6.2.1 Locality of References to Program Data
6.2.2 Locality of Instruction Fetches
6.2.3 Summary of Locality
Practice Problem 6.7 (solution page 662)
Practice Problem 6.8 (solution page 663)
6.3 The Memory Hierarchy
6.3.1 Caching in the Memory Hierarchy
Cache Hits
Cache Misses
Kinds of Cache Misses
Cache Management
6.3.2 Summary of Memory Hierarchy Concepts
6.4 Cache Memories
6.4.1 Generic Cache Memory Organization
Practice Problem 6.9 (solution page 663)
6.4.2 Direct-Mapped Caches
Set Selection in Direct-Mapped Caches
Line Matching in Direct-Mapped Caches
Word Selection in Direct-Mapped Caches
Line Replacement on Misses in Direct-Mapped Caches
Putting It Together: A Direct-Mapped Cache in Action
Conflict Misses in Direct-Mapped Caches
Practice Problem 6.10 (solution page 663)
Practice Problem 6.11 (solution page 663)
6.4.3 Set Associative Caches
Set Selection in Set Associative Caches
Line Matching and Word Selection in Set Associative Caches
Line Replacement on Misses in Set Associative Caches
6.4.4 Fully Associative Caches
Set Selection in Fully Associative Caches
Line Matching and Word Selection in Fully Associative Caches
Practice Problem 6.12 (solution page 663)
Practice Problem 6.13 (solution page 664)
Practice Problem 6.14 (solution page 664)
Practice Problem 6.15 (solution page 664)
Practice Problem 6.16 (solution page 665)
6.4.5 Issues with Writes
6.4.6 Anatomy of a Real Cache Hierarchy
6.4.7 Performance Impact of Cache Parameters
Impact of Cache Size
Impact of Block Size
Impact of Associativity
Impact of Write Strategy
6.5 Writing Cache-Friendly Code
Practice Problem 6.17 (solution page 665)
Practice Problem 6.18 (solution page 666)
Practice Problem 6.19 (solution page 666)
Practice Problem 6.20 (solution page 666)
6.6 Putting It Together: The Impact of Caches on Program Performance
6.6.1 The Memory Mountain
Practice Problem 6.21 (solution page 666)
6.6.2 Rearranging Loops to Increase Spatial Locality
6.6.3 Exploiting Locality in Your Programs
6.7 Summary
Bibliographic Notes
Homework Problems
6.22
6.23
6.24
6.25
6.26
6.27
6.28
6.29
6.30
6.31
6.32
6.33
6.34
6.35
6.36
6.37
6.38
6.39
6.40
6.41
6.42
6.43
6.44
6.45
6.46
Part II Running Programs on a System
Chapter 7 Linking
7.1 Compiler Drivers
7.2 Static Linking
7.3 Object Files
7.4 Relocatable Object Files
7.5 Symbols and Symbol Tables
Practice Problem 7.1 (solution page 717)
7.6 Symbol Resolution
7.6.1 How Linkers Resolve Duplicate Symbol Names
Practice Problem 7.2 (solution page 718)
7.6.2 Linking with Static Libraries
7.6.3 How Linkers Use Static Libraries to Resolve References
Practice Problem 7.3 (solution page 718)
7.7 Relocation
7.7.1 Relocation Entries
7.7.2 Relocating Symbol References
Relocating PC-Relative References
Relocating Absolute References
Practice Problem 7.4 (solution page 718)
Practice Problem 7.5 (solution page 718)
7.8 Executable Object Files
7.9 Loading Executable Object Files
7.10 Dynamic Linking with Shared Libraries
7.11 Loading and Linking Shared Libraries from Applications
7.12 Position-Independent Code (PIC)
7.13 Library Interpositioning
7.13.1 Compile-Time Interpositioning
7.13.2 Link-Time Interpositioning
7.13.3 Run-Time Interpositioning
7.14 Tools for Manipulating Object Files
7.15 Summary
Bibliographic Notes
Homework Problems
7.6 ♦
7.7 ♦
7.8 ♦
7.9 ♦
7.10 ♦♦
7.11 ♦♦
7.12 ♦♦
7.13 ♦♦
Chapter 8 Exceptional Control Flow
8.1 Exceptions
8.1.1 Exception Handling
8.1.2 Classes of Exceptions
Interrupts
Traps and System Calls
Faults
Aborts
8.1.3 Exceptions in Linux/x86-64 Systems
Linux/x86-64 Faults and Aborts
Linux/x86-64 System Calls
8.2 Processes
8.2.1 Logical Control Flow
8.2.2 Concurrent Flows
Practice Problem 8.1 (solution page 795)
8.2.3 Private Address Space
8.2.4 User and Kernel Modes
8.2.5 Context Switches
8.3 System Call Error Handling
8.4 Process Control
8.4.1 Obtaining Process IDs
8.4.2 Creating and Terminating Processes
Practice Problem 8.2 (solution page 795)
8.4.3 Reaping Child Processes
Determining the Members of the Wait Set
Modifying the Default Behavior
Checking the Exit Status of a Reaped Child
Error Conditions
Practice Problem 8.3 (solution page 797)
The wait Function
Examples of Using waitpid
Practice Problem 8.4 (solution page 797)
8.4.4 Putting Processes to Sleep
Practice Problem 8.5 (solution page 797)
8.4.5 Loading and Running Programs
Practice Problem 8.6 (solution page 797)
8.4.6 Using fork and execve to Run Programs
8.5 Signals
8.5.1 Signal Terminology
8.5.2 Sending Signals
Process Groups
Sending Signals with the /bin/kill Program
Sending Signals from the Keyboard
Sending Signals with the kill Function
Sending Signals with the alarm Function
8.5.3 Receiving Signals
Practice Problem 8.7 (solution page 798)
8.5.4 Blocking and Unblocking Signals
8.5.5 Writing Signal Handlers
Safe Signal Handling
Correct Signal Handling
Practice Problem 8.8 (solution page 799)
Portable Signal Handling
8.5.6 Synchronizing Flows to Avoid Nasty Concurrency Bugs
8.5.7 Explicitly Waiting for Signals
8.6 Nonlocal Jumps
8.7 Tools for Manipulating Processes
8.8 Summary
Bibliographic Notes
Homework Problems
8.9 ♦
8.10 ♦
8.11 ♦
8.12 ♦
8.13 ♦
8.14 ♦
8.15 ♦
8.16 ♦
8.17 ♦
8.18 ♦♦
8.19 ♦♦
8.20 ♦♦
8.21 ♦♦
8.22 ♦♦♦
8.23 ♦♦
8.24 ♦♦♦
8.25 ♦♦♦
8.26 ♦♦♦♦
Chapter 9 Virtual Memory
9.1 Physical and Virtual Addressing
9.2 Address Spaces
Practice Problem 9.1 (solution page 880)
9.3 VM as a Tool for Caching
9.3.1 DRAM Cache Organization
9.3.2 Page Tables
Practice Problem 9.2 (solution page 881)
9.3.3 Page Hits
9.3.4 Page Faults
9.3.5 Allocating Pages
9.3.6 Locality to the Rescue Again
9.4 VM as a Tool for Memory Management
9.5 VM as a Tool for Memory Protection
9.6 Address Translation
Practice Problem 9.3 (solution page 881)
9.6.1 Integrating Caches and VM
9.6.2 Speeding Up Address Translation with a TLB
9.6.3 Multi-Level Page Tables
9.6.4 Putting It Together: End-to-End Address Translation
Practice Problem 9.4 (solution page 881)
9.7 Case Study: The Intel Core i7/Linux Memory System
9.7.1 Core i7 Address Translation
9.7.2 Linux Virtual Memory System
Linux Virtual Memory Areas
Linux Page Fault Exception Handling
9.8 Memory Mapping
9.8.1 Shared Objects Revisited
9.8.2 The fork Function Revisited
9.8.3 The execve Function Revisited
9.8.4 User-Level Memory Mapping with the mmap Function
Practice Problem 9.5 (solution page 882)
9.9 Dynamic Memory Allocation
9.9.1 The malloc and free Functions
9.9.2 Why Dynamic Memory Allocation?
9.9.3 Allocator Requirements and Goals
9.9.4 Fragmentation
9.9.5 Implementation Issues
9.9.6 Implicit Free Lists
Practice Problem 9.6 (solution page 883)
9.9.7 Placing Allocated Blocks
9.9.8 Splitting Free Blocks
9.9.9 Getting Additional Heap Memory
9.9.10 Coalescing Free Blocks
9.9.11 Coalescing with Boundary Tags
Practice Problem 9.7 (solution page 883)
9.9.12 Putting It Together: Implementing a Simple Allocator
General Allocator Design
Basic Constants and Macros for Manipulating the Free List
Creating the Initial Free List
Freeing and Coalescing Blocks
Allocating Blocks
Practice Problem 9.8 (solution page 884)
Practice Problem 9.9 (solution page 884)
9.9.13 Explicit Free Lists
9.9.14 Segregated Free Lists
Simple Segregated Storage
Practice Problem 9.10 (solution page 885)
Segregated Fits
Buddy Systems
9.10 Garbage Collection
9.10.1 Garbage Collector Basics
9.10.2 Mark&Sweep Garbage Collectors
9.10.3 Conservative Mark&Sweep for C Programs
9.11 Common Memory-Related Bugs in C Programs
9.11.1 Dereferencing Bad Pointers
9.11.2 Reading Uninitialized Memory
9.11.3 Allowing Stack Buffer Overflows
9.11.4 Assuming That Pointers and the Objects They Point to Are the Same Size
9.11.5 Making Off-by-One Errors
9.11.6 Referencing a Pointer Instead of the Object It Points To
9.11.7 Misunderstanding Pointer Arithmetic
9.11.8 Referencing Nonexistent Variables
9.11.9 Referencing Data in Free Heap Blocks
9.11.10 Introducing Memory Leaks
9.12 Summary
Bibliographic Notes
Homework Problems
9.11
9.12
9.13
9.14
9.15
9.16
9.17
9.18
9.19
9.20
Part III Interaction and Communication between Programs
Chapter 10 System-Level I/O
10.1 Unix I/O
10.2 Files
10.3 Opening and Closing Files
Practice Problem 10.1 (solution page 915)
10.4 Reading and Writing Files
10.5 Robust Reading and Writing with the Rio Package
10.5.1 Rio Unbuffered Input and Output Functions
10.5.2 Rio Buffered Input Functions
10.6 Reading File Metadata
10.7 Reading Directory Contents
10.8 Sharing Files
Practice Problem 10.2 (solution page 915)
Practice Problem 10.3 (solution page 915)
10.9 I/O Redirection
Practice Problem 10.4 (solution page 915)
Practice Problem 10.5 (solution page 916)
10.10 Standard I/O
10.11 Putting It Together: Which I/O Functions Should I Use?
10.12 Summary
Bibliographic Notes
Homework Problems
10.6
10.7
10.8
10.9
10.10
Chapter 11 Network Programming
11.1 The Client-Server Programming Model
11.2 Networks
11.3 The Global IP Internet
11.3.1 IP Addresses
Practice Problem 11.1 (solution page 966)
Practice Problem 11.2 (solution page 967)
Practice Problem 11.3 (solution page 967)
11.3.2 Internet Domain Names
11.3.3 Internet Connections
11.4 The Sockets Interface
11.4.1 Socket Address Structures
11.4.2 The socket Function
11.4.3 The connect Function
11.4.4 The bind Function
11.4.5 The listen Function
11.4.6 The accept Function
11.4.7 Host and Service Conversion
The getaddrinfo Function
The getnameinfo Function
Practice Problem 11.4 (solution page 968)
11.4.8 Helper Functions for the Sockets Interface
The open_clientfd Function
The open_listenfd Function
11.4.9 Example Echo Client and Server
11.5 Web Servers
11.5.1 Web Basics
11.5.2 Web Content
11.5.3 HTTP Transactions
HTTP Requests
HTTP Responses
11.5.4 Serving Dynamic Content
How Does the Client Pass Program Arguments to the Server?
How Does the Server Pass Arguments to the Child?
How Does the Server Pass Other Information to the Child?
Where Does the Child Send Its Output?
Practice Problem 11.5 (solution page 969)
11.6 Putting It Together: The Tiny Web Server
11.7 Summary
Bibliographic Notes
Homework Problems
11.6
11.7
11.8
11.9
11.10
11.11
11.12
11.13
Chapter 12 Concurrent Programming
12.1 Concurrent Programming with Processes
12.1.1 A Concurrent Server Based on Processes
12.1.2 Pros and Cons of Processes
Practice Problem 12.1 (solution page 1036)
Practice Problem 12.2 (solution page 1036)
12.2 Concurrent Programming with I/O Multiplexing
Practice Problem 12.3 (solution page 1036)
12.2.1 A Concurrent Event-Driven Server Based on I/O Multiplexing
Practice Problem 12.4 (solution page 1036)
12.2.2 Pros and Cons of I/O Multiplexing
12.3 Concurrent Programming with Threads
12.3.1 Thread Execution Model
12.3.2 Posix Threads
12.3.3 Creating Threads
12.3.4 Terminating Threads
12.3.5 Reaping Terminated Threads
12.3.6 Detaching Threads
12.3.7 Initializing Threads
12.3.8 A Concurrent Server Based on Threads
Practice Problem 12.5 (solution page 1036)
12.4 Shared Variables in Threaded Programs
12.4.1 Threads Memory Model
12.4.2 Mapping Variables to Memory
12.4.3 Shared Variables
Practice Problem 12.6 (solution page 1036)
12.5 Synchronizing Threads with Semaphores
Practice Problem 12.7 (solution page 1037)
12.5.1 Progress Graphs
Practice Problem 12.8 (solution page 1038)
12.5.2 Semaphores
12.5.3 Using Semaphores for Mutual Exclusion
12.5.4 Using Semaphores to Schedule Shared Resources
Producer-Consumer Problem
Practice Problem 12.9 (solution page 1038)
Readers-Writers Problem
Practice Problem 12.10 (solution page 1038)
12.5.5 Putting It Together: A Concurrent Server Based on Prethreading
12.6 Using Threads for Parallelism
12.7 Other Concurrency Issues
12.7.1 Thread Safety
12.7.2 Reentrancy
Practice Problem 12.12 (solution page 1038)
12.7.3 Using Existing Library Functions in Threaded Programs
12.7.4 Races
Practice Problem 12.13 (solution page 1039)
Practice Problem 12.14 (solution page 1039)
12.7.5 Deadlocks
Practice Problem 12.15 (solution page 1039)
12.8 Summary
Bibliographic Notes
Homework Problems
12.16 ♦
12.17 ♦
12.18
12.19 ♦♦
12.20 ♦♦♦
12.21 ♦♦♦♦
12.22 ♦♦
12.23 ♦♦
12.24 ♦
12.25 ♦
12.26 ♦♦♦
12.27 ♦♦
12.28 ♦
12.29 ♦
12.30 ♦
12.31 ♦♦♦
12.32 ♦♦♦
12.33 ♦♦♦
12.34 ♦♦♦
12.35 ♦♦♦
12.36 ♦♦♦
12.37 ♦♦♦
12.38 ♦♦♦♦
12.39 ♦♦♦♦
Appendix A Error Handling
A.1 Error Handling in Unix Systems
A.2 Error-Handling Wrappers
References
Index
Computer Systems
A Programmer's Perspective
2
Computer Systems
A Programmer's Perspective
Third Edition
Randal E. Bryant
Carnegie Mellon University
David R. O'Hallaron
Carnegie Mellon University
Pearson
Boston Columbus Hoboken Indianapolis New York San
Francisco Amsterdam Cape Town Dubai London Madrid
Milan Munich Paris Montreal Toronto Delhi Mexico City
Sao Paulo Sydney Hong Kong Seoul Singapore Taipei
Tokyo
3
Vice President and Editorial Director: Marcia J. Horton
Executive Editor: Matt Goldstein
Editorial Assistant: Kelsey Loanes
VP of Marketing: Christy Lesko
Director of Field Marketing: Tim Galligan
Product Marketing Manager: Bram van Kempen
Field Marketing Manager: Demetrius Hall
Marketing Assistant: Jon Bryant
Director of Product Management: Erin Gregg
Team Lead Product Management: Scott Disanno
Program Manager: Joanne Manning
Procurement Manager: Mary Fischer
Senior Specialist, Program Planning and Support: Maura Zaldivar-
Garcia
over Designer: Joyce Wells
Manager, Rights Management: Rachel Youdelman
4
Associate Project Manager, Rights Management: William J. Opaluch
Full-Service Project Management: Paul Anagnostopoulos, Windfall
Software
Composition: Windfall Software
Printer/Binder: Courier Westford
Cover Printer: Courier Westford
Typeface: 10/12 Times 10, ITC Stone Sans
The graph on the front cover is a "memory mountain" that shows the
measured read throughput of an Intel Core i7 processor as a
function of spatial and temporal locality.
Copyright © 2016, 2011, and 2003 by Randal E. Bryant and
David R. O'Hallaron. All Rights Reserved. Printed in the United
States of America. This publication is protected by copyright, and
permission should be obtained from the publisher prior to any
prohibited reproduction, storage in a retrieval system, or
transmission in any form or by any means, electronic, mechanical,
photocopying, recording, or otherwise. For information regarding
permissions, request forms and the appropriate contacts within the
Pearson Education Global Rights & Permissions department, please
visit www.pearsoned.com/permissions/.
Many of the designations by manufacturers and seller to distinguish
their products are claimed as trademarks. Where those designations
5
appear in this book, and the publisher was aware of a trademark
claim, the designations have been printed in initial caps or all caps.
The author and publisher of this book have used their best efforts in
preparing this book. These efforts include the development,
research, and testing of theories and programs to determine their
effectiveness. The author and publisher make no warranty of any
kind, expressed or implied, with regard to these programs or the
documentation contained in this book. The author and publisher shall
not be liable in any event for incidental or consequential damages
with, or arising out of, the furnishing, performance, or use of these
programs.
Pearson Education Ltd., London
Pearson Education Singapore, Pte. Ltd
Pearson Education Canada, Inc.
Pearson Education—Japan
Pearson Education Australia PTY, Limited
Pearson Education North Asia, Ltd., Hong Kong
Pearson Educaciń de Mexico, S.A. de C.V.
Pearson Education Malaysia, Pte. Ltd.
Pearson Education, Inc., Upper Saddle River, New Jersey
6
Library of Congress Cataloging-in-Publication Data
Bryant, Randal E.
Computer systems : a programmer's perspective / Randal E.
Bryant, Carnegie Mellon University, David R. O'Hallaron, Carnegie
Mellon. University.—Third edition.
pages cm
Includes bibliographical references and index.
ISBN 978-0-13-409266-9—ISBN 0-13-409266-X
1. Computer systems. 2. Computers. 3. Telecommunication. 4.
User interfaces (Computer systems) I. O'Hallaron, David R. (David
Richard) II. Title.
QA76.5.B795 2016
005.3—
dc23
2015000930
10 9 8 7 6 5 4 3 2 1
www.pearsonhighered.com
7
ISBN 10: 0-13-409266-X
ISBN 13: 978-0-13-409266-9
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
