THIRD EDITION COMPUTER SYSTEMS A PROGRAMMER'S PERSPECTIVE BRYANT·O'HALLARON
THIRD EDITION . COMPUTER SYSTEMS BRYANT • O'HALLARON I
Contents Preface xix About the Authors XXXV 1 A Tour of Computer Systems 1 1.1 Information Is,Bits Context 3 1.2 Programs Are Translated.by Other Programs into Different Forms 4 13 It Pays to Understand How Compilation Systems Work 6 14 Processors Read and Interpret Instructions Stored in Memory 7 1.4.1 Hardware Organization of a System 8 1.4.2 Running the hello Program 10 1.5 Caches Matter 11 1.6 Storage Devices Form a Hierarchy.14 1.7 The Operating System Manages the Hardware 14 1.7.1 Processes 15 1.7.2 Threads 17 1.7.3 Virtual Memory 18 1.7.4Fi1es19 18 Systems Communicate with Other Systems Using Networks 19. 19 Important Themes 22 1.9.1 Amdahl's Law 22. 1.9.2 Concurrency and Parallelism 24 1.9.3 The Importance of Abstractions in Computer Systems 26 1.10 Summary 27 Bibliographic Notes 28 Solutions to Practice Problems 28 Part I Program Structure and Execution 2 Representing and Manipulating Information 31 2.1 Information Storage 34 一 2.1.1 Hexadecimal Notation 36 2.1.2 Data Sizes 39 vii
Contents t " ,. Preface xix About the Autho~s xxxv 1 A Tour of Cqmputer ~ystell!;s 1 1.1 Information Is,Bits + Context ''.l L2 L3 1.4 Programs Are Translated .by Other P,rograms into Different Forms 4 It Pays to Understand How_ Compilation Systems Work 6 1.5 Processors Read and-Interpret Instructions Stored in Memory 7 1.4.1 Hardware Organization of a System 8 1.4.2 Running the hello Program 10 Caches Matter 11 1.6 Storage Devices Form a Hierarchy. 14 1. 7 The Operating System Manages the Hard~are 14 1.7.1 Processes 15 1.7.2 Threads 17 1.7.3 Virtual Memory 18 1.7.4 Files 19 LS Systems Communicate with Other Systems Using Networks 19. 1.9 Important Themes 22 1.9.1 Amdahl's Law 22· '•· 1.9.2 Concurrency and Parallelism 24 1.9.3 The Importance of Abstractions in Computer Systems 26 1.10 Summary 27 Bibliographic Notes 28 Solutions to Practice Problems 28 Part I Program Structui:e and.Execution 2 Represepting and Manipulating Information Jl 2.1 Information Storage 34 2.1.1 Hexadecimal Notation 36 2.1.2 Data Sizes 39 vii
viⅷi Contents 2.1.3 Addressing and Byte Ordering 42 2.1.4 Representing Strings 49 2.1.5 Representing Code 49 2.1.6 Introduction to Boolean Algebra 50 2.1.7 Bit-Level Operations in C 54 2.1.8 Logical Operations in C 56 2.1.9 Shift Operations in C 57 2.2 Integer Representations 59 2.2.1 Integral Data Types 60 2.2.2 Unsigned Encodings 62 2.2.3 Two's-Complement Encodings,64 2.2.4 Conversions between Signed and Unsigned 70 2.2.5 Signed versus Unsigned in C 74 2.2.6 Expanding'the Bit Representation of a Number 76 2.2.7 Truncating Numbers 81 2.2.8 Advice on Signed versus Unsigned 83 2.3 Integer Arithmetic 84 2.3.1 Unsigned Addition 84 2.3.2 Two's-Complement Addition 90 2.3.3 Two's-Complement Negation 95 2.3.4 Unsigned Multiplication 96 2.3.5 Two's-Complement Multiplication 97 2.3.6 Multiplying by Constants 101 2.3.7 Dividing by Powers of 2 103 2.3.8 Final Thoughts on Integer Arithmetic 107 2.4 Floating Point 108 2.4.1 Fractional Binary Numbers 109 2.4.2 IEEE Floating-Point Representation 112 2.4.3 Example Numbers 115 2.4.4 Rounding 120 2.4.5 Floating-Point Operations 122 2.4.6 Floating Point in C 124 2.5 Summary 126 Bibliographic Notes 127 Homework Problems 128 Solutions to Practice Problems 143 3 Machine-Level Representation'of Programs 163 3.1 A Historical Perspective 166
viii Contents 2.1.3 Addressing and Byte Ordering 42 2.1.4 Representing Strings 49 2.1.5 Representing Code 49 2.1.6 Introduction to Boolean Algebra 50 2.1.7 Bit-Level Operations in C 54 2.1.8 Logical Operations in C 56 2.1.9 Shift Operations in C 57 2.2 Integer Representations 59 2.2.1 Integral Data Types 60 2.2.2 Unsigned Encodings 62 2.2.3 1\vo's-Complement Encodings, 64 2.2.4 Conversions between Signed and Unsigned 70 2.2.~ Signed versus Unsigned inC 74 2.2.6 Expanding"the Bit Representation of a Number 76 2.2.7 Truncating Numbers 81 2.2.8 Advice on Signed versus Unsigned 83 2.3 Integer Arithmetic 84 2.3.1 Unsigned Addition 84 2.3.2 1\vo's-Complement Addition 90 2.3.3 1\vo's-Complement Negation 95 2.3.4 Unsigned Multiplication 96 2.3.5 1\vo's-Complement Multiplication 97 2.3.6 Multiplying by Constants 101 2.3.7 Dividing by Powers of 2 103 2.3.8 Final Thoughts on Integer Arithmetic 107 2.4 Floating Point 108 2.4.1 Fractional Binary Numbers 109 2.4.2 IEEE Floating-Point Representation 112 2.4.3 Example Numbers 115 2.4.4 Rounding 120 2.4.5 Floating-Point Operations 122 2.4.6 Floating Point in C 124 2.5 Summary 126 3 Bibliographic Notes 127 Homework Problems 128 Solutions to Practice Problems 143 Machine-Level Representatioll'of Progralhs 163 3.1 A Historical Perspective 166 -- - . •
Contents ix 3.2 Program Encodings 169 3.2.1 Machine-Level Code 170 3.2.2 Code Examples 172 3.2.3 Notes on Formatting 175 3.3 Data Formats 177- 3.4 Accessing Informiation 179 3.4.1 Operand Specifiers.180 3.4.2 Data Movement Instryctions 182 3.4.3 Data Moyement Example 186 I 3.4.4 Pushing and Popping Stack Data 189 3.5 Arithmetic and Logical Operations 191 3.5.1 Load Effective Address 191 3.5.2 Unary and Binary Operations 194 3.5.3 Shift Operations 194 3.5.4 Discussion,196 g 3.5.5 Special Arithmetic Operations 197 3.6 Control 200' 3.6.1 Condition Codes 201 3.6.2 Accessing the Condition Codes 202 3.6.3 Jump Instructions 205 3.6.4 Jump Instruction Encodings 207 3.6.5 Implementing Conditional Branches with Conditional Control 209 3.6.6 Implementing Conditional Branches.with Conditional Moves 214s 3.6.7 Loops 220 3.6.8 Switch Statements 232 3.7 Procedures 238 9 3.7.1 The Run-Time Stack 239 3.7.2 Control Transfer 241 3.7.3 Data Transfer 245 3.7.4 Local Storage on the Stack 248 3.7.5 Local Storage in Registers 251 3.7.6 Recursive Procedures 253 3.8 Array Allocation and Access 255 3.8.1 Basic Principles 255 1 3.8.2 Pointer Arithmetic 257 3.8.3 Nested Arrays 258 3.8.4 Fixed-Size Arrays 260, 14 3.8.5 Variable-Size Arrays 262
3.2 Program Encodings 169 3.3 3.4 3.5 3.6 3.2.l Machine-Level Code 170 3.2.2 Code Examples 172 3.2.3 Notes on Formatting 175 Data Formats 177· (I ' 11 Accessing Infonrlation 17~ 3.4.l , (!peranq,Speciflers. 180 " 3.4.2 'Data Movell).ent Instwcti<;ms , 1~2 3.4.3 Data Moyement Exllmple 0 186 3.4.4 Pushing and' Poppi~g Stack Data Arithmetic and Logical Operations 191 3.5.1 Load Effective Address 191 i89 3.5.2 Unary and Bi~ary 9peqtip,J!~r 194 3.5.3 Shift Operations 194 3.5.4 ,. Disc_u~sion, 196 , 3.5.5 Special Arithmetic Operatio11s 197 Control 200' 3.6.1 Condition Codes 201 l J I ' " f;t I ·'\ ,, • ' l 3.6.2 Accessing the Condition Codes 202 · • ~· , 3.6.3 Jump Instructions 205 • 3.6.4 Jump Instruction Encodings 207 3.6.5 Impleme9ting Conditional Branches with Conditional ·Control 209 3.6.6 Implementing.Conditional Branches.with Conditional Moves 214 > 3.6.7 Loops 220 3.6.8 Switch Statements 232 3.7 Procedures 238 3.7'.l The Run-Turie, Stack 23~ 3.7.2 Control Transfer 241 3.7.3 Data Transfer 245 3.7.4 3.7.5 3.7.6 Local Storage on the Stack 248 • • J Local Storage m Registers 251 Recursive Procedure~ 253 " "· 3.8 :Array Allocati91)-~nd Access 255 3.8.1 Basic Principles 255 3.8.2 Pointer Arithmetic 257 3.8.3 Nested Arrays 258 3.8.4 Fixed-Size Arrays 260, 3.8.5 Variable-Size Arrays 262 , , " ; l " Co,ntents- ix { ,, ') '
x Contents 3.9 Heterogeneous Data Structures 265 3.9.1 Structures 265 3.9.2 Unions 269 3.9.3 Data Alignment 273 3.10 Combining Control and Data in Machine-Level Programs 276 3.10.1 Understanding Pointers 277 3.10.2 Life in the Real World:Using the GDB Debugger 279 3.10.3 Out-of-Bounds Memory References and Buffer Overflow 279 3.10.4 Thwarting Buffer Overflow Attacks 284 3.10.5 Supporting Variable-Size Stack Frames'290 3.11 Floating-Point Code 293 3.11.1 Floating-Point Movement and Conversion Operations 296 3.11.2 Floating-Point Code in Procedures 301 3.11.3 Floating-Point Arithmetic Operations 302 3.11.4 Defining and Using Floating-Point Constants 304 3.11.5 Using Bitwise Operations in Floating-Point Code 305 3.11.6 Floating-Point Comparison Operations 306 3.11.7 Observations about Floating-Point Code 309 3.12 Summary 309 Bibliographic Notes 310 Homework Problems 311 Solutions to Practice Problems 325 4 Processor Architecture 351 The Y86-64 Instruction Set Architecture 355 4.1 4.1.1 Programmer-Visible State 355 4.1.2 Y86-64 Instructions 356 4.1.3 Instruction Encoding 358 4.1.4 Y86-64 Exceptions 363 4.1.5 Y86-64 Programs 364 4.1.6 Some Y86-64 Instruction Details 370 4.2 Logic Design and the Hardware Control Language HCL 372 4.2.1 Logic Gates 373 4.2.2 Combinational Circuits and HCL Boolean Expressions 374 4.2.3 Word-Level Combinational Circuits and HCL Integer Expressions 376 4.2.4 Set Membership 380 4.2.5 Memory and Clocking 381 43 Sequential Y86-64 Implementations 384 4.3.1 Organizing Processing into Stages 384
x Contents 3.9 Heterogeneous Data Structures 265 3.9.l Structures 265 3.9.2 Unions 269 3.9.3 Data Alignment 273 3.10 Combining Control and Data in Machine-Level Progri'ms 276 3.10.1 Understanding Pointers 277 ""---l ..II 3.10.2 Life in the Real World: Using ihe GDB Debugger 279 3.10.3 Out-of-Bounds Memory References and Buffer b,v,erflow 279 3.10.4 Thwarting Buffer Overflow Attacks 284 3.10.5 Supporting Variable-Size StacltFrames' 290 3.11 Floating-Point Code 293 3.11.l Floating-Point Movement and Conversion Operations 296 3.11.2 Floating-Point Code in Procedures 301 3.11.3 Floating-Point Arithmetic Operations 302 3.11.4 Defining and Using Floating-Point Constants 304 3.11.5 Using Bitwise Operations in Floating-Point Gode 305 3.11.6 Floating-Point Comparison Operations 306 3.11.7 Observations about Floating-Point Code 309 3.12 Summary 309 4 Bibliographic Notes 310 Homework Problems 311 Solutions to Practice Problems 325 Processor Architecture 351 4.1 The Y86-64 Instruction Set Architecture 355 4.1.1 Programmer-Visible State 355 4.1.2 Y86-64 Instructions 356 4.1.3 Instruction Encoding 358 4.1.4 Y86-64 Exceptions 363 4.1.5 Y86-64 Programs 364 4.1.6 Some Y86-64 Instruction Details 370 4.2 Logic Design and the Hardware Control Language HCL 372 4.2.1 Logic Gates 373 4.2.2 Combinational Circuits and HCL Boolean Expressions 374 4.2.3 Word-Level Combinational Circuits and HCL Integer Expressions 376 4.2.4 Set Membership 380 4.2.5 Memory and Clocking 381 4.3 Sequential Y86-64 Implementations 384 4.3.1 Organizing Processing into Stages 384