THIRD EDITION
.
COMPUTER SYSTEMS
BRYANT • O’HALLARON I
C·oni.puter Systems
A Programmer’s Perspective THIRD EDITION
” .
. O’Hallaron Carnegie
Columbus Hoboken Indianapolis New York San Francisco
Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montre’h.1 .Jbro:rito Delhi Mexico City Sao Seoul Singapore Taipei Tokyo
Vice President and Editorial Director: . Editor:
Editorial Assistant:
VP of Marketing:
Director of Field Marketing: Product Marketing Manager: Bram van Kempen Field Marketing Manager: Demetrius Hall
Marketing Assistant:
Director of Product Management: Team Lead Product Management: Program Manager: Procurement Manager:
Senior Specialist, Program Planning and Support: -Garcia
Cover Designer:
Manager, Rights Management: Associate Project Manager, Rights Management:
. Opaluch
Full-Service Project Management: ,
Windfall Software
Composition: Windfall Software Printer/Binder: Courier Westford
Cover Printer: Courier Westford Typeface: 10/12 Times 10, ITC Stone Sans
Tue 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 , Inc. or its affiliates. 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 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 appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in
initial caps or all caps.
Tue 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.
\ I
Ltd., London Singapore, Pte. Ltd Canada, Inc. -Japan
Australia PTY, Limited
North Asia, Ltd., de Mexico, S.A. de C.V.
Malaysia, Pte. Ltd.
, Inc., Upper Saddle River,
Library of Congress Cataloging-in-Publication Data Bryant, .
Computer systems: a programmer’s perspective I . Bryant, Carnegie , . O’Hallaron, . 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.
I. O’Hallaron,
2015000930
ISBN 10: 0-13-409266-X ISBN 13: 978-0-13-409266-9
. ( ichard)
QA76.5.B795 2016 OOS.3–dc23
10 9 8 7 6 5 4 3 2
PEARSON
II. Title.
wmv.pearsonhighered.com
4. User interfaces (Computer systems)
,.
To the ~tutjenfs~lidinstructors of the 15-213 course at Carnegie , for inspiring us to develop and refine the material’ fo’r this book.
–
Mastering Engineering®
For Computer Systems: A Programmer’s Perspective, Third Edition
Mastering is Pearson’s proven online Tutorial Homework program, newly available with the third edition of Computer Systems: A Programmer’s Perspective. The Mastering platform allows you to integrate dynamic homework-with many problems taken directly from the Bryant/O’Hallaron textbook-with automatic grading. Mastering allows you to easily track the performance of your entire class on an assignment-by-assignment basis, or view the detaileq work of an individual
t -.I~
I’
student.
For more information or a demonstration of the course, visit www.MasteringEngineering.com
,” or contact your local Pearson representative.
.._._.
Contents
Preface xix
About the Autho~s xxxv
1
A Tour of Cqmputer ~ystell!;s 1
1.1 InformationIs,Bits+Context ”.l
L2 Programs Are Translated.by Other P,rograms into Different Forms 4
L3 It Pays to Understand How_Compilation Systems Work 6
1.4 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 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
t
,.
”
vii
viii Contents
2.2
Integer Representations 59
2.3
Integer Arithmetic 84
2.4
2.5
Floating Point 108
2.1.3 2.1.4 2.1.5 2.1.6
2.1.7 2.1.8 2.1.9
Addressing and Byte Ordering 42 Representing Strings 49
Representing Code 49
Introduction to Boolean Algebra 50 Bit-Level Operations in C 54 Logical Operations in C 56
Shift Operations in C 57
2.2.1 2.2.2 2.2.3 2.2.4
2.2.~
2.2.6
2.2.7 2.2.8
Integral Data Types 60
Unsigned Encodings 62
1\vo’s-Complement Encodings, 64 Conversions between Signed and Unsigned 70
Signed versus Unsigned inC 74 Expanding”the Bit Representation of a Number
Truncating Numbers 81
Advice on Signed versus Unsigned 83
76
2.3.1 2.3.2 2.3.3 2.3.4 2.3.5
2.3.6 2.3.7 2.3.8
Unsigned Addition 84 1\vo’s-Complement Addition 90 1\vo’s-Complement Negation 95
Unsigned Multiplication 96 1\vo’s-Complement Multiplication 97
Multiplying by Constants 101
Dividing by Powers of 2 103
Final Thoughts on Integer Arithmetic 107
2.4.1 2.4.2 2.4.3
Fractional Binary Numbers 109
IEEE Floating-Point Representation 112 Example Numbers 115
2.4.4 Rounding 120
2.4.5 Floating-Point Operations 122
2.4.6 Floating Point in C 124
Summary 126
Bibliographic Notes 127 Homework Problems 128 Solutions to Practice Problems 143
3
Machine-Level Representatioll’of Progralhs
3.1 A Historical Perspective 166
163
— – .
•
3.2
3.3 3.4
3.5
3.6
Program Encodings 169
3.2.l Machine-Level Code 170
3.2.2 Code Examples 172
3.2.3 Notes on Formatting 175
Data Formats 177·
Accessing Infonrlation 17~ 3.4.l , (!peranq,Speciflers. 180
(I’ 11
3.7
3.8
Procedures 238
3.7′.l The Run-Turie, Stack
3.7.2 Control Transfer 241
3.7.3 Data Transfer 245
”
3.4.2 3.4.3 3.4.4
‘Data Movell).ent Instwcti<;ms 0
"
, 1~2
lJ I'
" I·'\ ,,
f;t
3.5.1 3.5.2 3.5.3 3.5.4 3.5.5
Load Effective Address 191 Unary and Bi~ary9peqtip,J!~r 194 Shift Operations 194
,. Disc_u~sion, 196 , Special Arithmetic Operatio11s 197
•'l
~· , •
Control 200'
3.6.1 3.6.2 3.6.3 3.6.4 3.6.5
3.6.6
Condition Codes 201
Accessing the Condition Codes 202 Jump Instructions 205
Jump Instruction Encodings 207 Impleme9ting Conditional Branches with Conditional·Control 209 Implementing.Conditional Branches.with
Data Moyement Exllmple 186 Pushing and' Poppi~gStack Data
i89
Arithmetic and Logical Operations 191
Conditional Moves 3.6.7 Loops 220
214
>
248 251
‘) ‘
3.6.8 Switch Statements 232
3.7.4 Local Storage on the Stack ••J
3.7.5 Local Storage m Registers
3.7.6 Recursive Procedure~ 253
: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
,,
23~
· •
{
”
,,,
,,
Co,ntents- ix
x Contents
3.9
3.10
3.11
Heterogeneous Data Structures 265 3.9.l Structures 265
3.9.2 Unions 269
3.9.3 Data Alignment 273
Combining Control and Data in Machine-Level Progri’ms 276
4.1
4.2
4.3
The Y86-64 Instruction Set Architecture 355
3.10.1 3.10.2 3.10.3 3.10.4 3.10.5
Understanding Pointers 277
Life in the Real World: Using ihe GDB Debugger 279 Out-of- References and Buffer b,v,erflow 279 Thwarting Buffer Overflow Attacks 284
Supporting Variable-Size StacltFrames’ 290 Floating-Point Code 293
3.11.l 3.11.2
3.11.3 3.11.4 3.11.5 3.11.6 3.11.7
Floating-Point Movement and Conversion Operations 296 Floating-Point Code in Procedures 301
Floating-Point Arithmetic Operations 302
Defining and Using Floating-Point Constants 304 Using Bitwise Operations in Floating-Point Gode 305 Floating-Point Comparison Operations 306
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
4.1.1 4.1.2 4.1.3 4.1.4 4.1.5
Programmer-Visible State 355 Y86-64 Instructions 356 Instruction Encoding 358
Y86-64 Exceptions
Y86-64 Programs 364
Some Y86-64 Instruction Details 370
4.2.1 4.2.2
4.2.3
Logic Gates 373
Combinational Circuits and HCL Boolean Expressions 374
Word-Level Combinational Circuits and HCL Integer Expressions 376
Set Membership 380
Memory and Clocking 381
4.2.4
4.2.5
Sequential Y86-64 Implementations 384
4.3.1 Organizing Processing into Stages 384
363
4.1.6
Logic Design and the Hardware Control Language HCL 372
“”—l ..II
5
..
4.3.2 SEQ Hardware Structure 396G0 . ,.
‘· n•J
‘ •1.,
1 ,
• · ‘
:.
4.3.3 SEQ Timing 400
4.3.4 SEQ Stage Jmplementations
4.4 General Principles of Pipelining 412
·¥. ” ,. ‘! 404 11″‘ ., ‘
‘””
Coi;nputat~onal Pipelines 412·
A Detailed Look at Pipeline Operation,. il14l
4.4.1
4.4.2
4.4.3
4.4.4 <•,l?ipelihingc.a'System with Feedback· 419
Limit,atiqns of Pipelining 416
4.5 Pipelined Y86'64 Impleinentations• '421·tJ .·11<
4.5.l
4.5.2
4.5.3
4.5.4
4.5.5
4.5.6
4.5.7
4.5.8
4.5.9
4,5.10 Unfinisped Business 468
4.6 Summary 470
4.6.1 Y86-64 Simulators 472 Bibliographic Notes 473 Homework Problems 473 Solutions to Practice Problems 480
SEQ+: Rearranging the Computation Stagesu-.421 Insefting.Pipeline Registers 422 , .fi" Rearranging and Relabeling Signals 426
Next PC Prediction 427
Pipeline Hazards 429
Exception Handling 444 _, PIPE Stage Implementations 447 Pipeline Control Logic 455
- Performance Analysis -464.
Optimizing Program'P'erforniqnc~;
495
5.1 Capabilities and Limitations· of Optimizing Compilers 1198
5.2 Expressing Program Performance. ·502
5.3 Program Example 504
5.4 Eliminating Loop•I:gefficiencies 508
5.5 Reducing Procedure Calls 51'.Z.<
5.6 Eliminating Unneeded Memory Referencesu514 ...
5.7 Understanding Modern Processors ·517,.
5.7.l Overall Operation 518
5.7.2 Functional Unit Performance 523
5.7.3 An Abstract Model of Processor Operation 525
5.8 Loop Unrolling 53.hr" "'
5.9 Enhanqing Parallelism 536
5.9.l Multiple.Accumulators 536
5.9.2 Reassociation Transformation 541
•
>
, l ”
‘(It .t/
,,
‘” ”
.J•
~Contents xi
Xii Contents
5.10 5.11
5.12
5.13 5.14
Summary of Results for Optimizing Combining Code 547 Some Limiting Factors 548
5.11.1 Register Spilling 548
5.11.2 Branch Prediction and·Mispredictipn Penalties ·’549
Understanding Memory Performance 553 ,… •L
5.12.1 Load Performance 554’ri 1 d ”
5.12.2 Store Performance 555
Life in the Real World: Performance”Improvement Techniques • 561
6.1
6.2
6.3
6.4
6.5 6.6
Storage Technologies 581
6.1.1 Random Access Memory 581
6.1.2 Disk Storage 589
6.1.3 Solid State Disks 600
6.1.4 Storage Technology Trends 602
Locality 604
6.2.1 Locality of References to Program Data
6.2.2 Locality of Instruc,tion Fetche’l , 601
6.2.3 Summary of Locality 608 “‘
The Memory Hierarchy 609
6.3.1 Caching in the Memory Hierarchy 610
6.3.2 Summary of Memory Hierarchy Concepts
Cache Memories 614
606
Identifying and Eliminating Performance Bottlenecks 5.14.1 Program Profiling 562
562 •
”
5.14.2 Using a Profiler to Guide Optimization 5.15 Summary 568
Bibliographic Notes 569 Homework Problems 570 Solutions to Practice Problems 573
6
The Memory Hierarchy 579
565
6.4.1 6.4.2 6.4.3 6.4.4 6.4.5
6.4.6
6.4.7
Generic Cache Memory Organization ‘615 Direct-Mapped Caches 617 ”
Set Associative Cadres 624 ”
Fully Associative Caches 626
Issues with Writes 630
Anatomy of a Real Cache Hierarchy 631 Performance Impact of Cache Parameters 631
Writing Cache-Friendly Code 633
Putting It Together: The Impact of Caches on Program Performance 639
614
6.6.1 The Memory Mountain 639
6.6.2 Rearranging Loops to Increase Spatial Locality 643
6.6.3 Exploiting Locality in Your Programs ‘647
6.7 Summary 648
Bibliographic Notes 648
‘
Homework’ Problems 649
Solutions to Practice Problems 660
‘
Part II Running Programs on a System
7
Linking 669
7.1 7.2 7.3 7.4 7.5 7.6
7.7
7.8 7.9 7.10 7.11 7.12 7.13
7.14 7.15
Compiler Drivers 671
Static Linking 672
Object Files 673
Relocatable Object Files 674 SY1Pbols and Symbol.Tables 675 Symbol Resolution 679
d
7.6.1
7.6.2
7.6.3
Relocation 689
7.7.1 Relocation Entries 690
7.7.2 Relocating Symbol References 691
Executable Object Files 695
How Linkers Resolve Duplicate Symbol Names 680
Linking with Static Libraries 684
How Linkers Use Static Libraries to Resolve References 688
Loading Executable Object Files 697 Dynamic Linking with Shared Libraries 698
‘.
Loading and Linking Shared Libraries from Applications 701
Position-Independent Code (PIC) 704 Library Interpositioning 707
7.13.1 Compile-Time Interpositioning 708
7.13.2 Link-Time Interpositioning 708
7.13.3 Run-Time Interpositioning 710
Tools for Manipulating Object Files 713 Summary 713
Bibliographic Notes 714 Homework Problems 714 Solutions to Practice Problems 717
Contents xiii
xiv Contents
8
ExceptionalControlFlow” 721
Exceptions 723
8.1.1 Exception Handling 724
8.1.2 Classes of Exceptions 726
8.1.3 Exceptions in Linux/x86-64 Systems 729
Processes 732
8·.2.1 Logical ControfFlow 732
8.2.2 Concurrent Flows 733
8.2.3 Private Address Space 734
8.2.4 User and Kernel Modes 734
8.2.5 Context Switches 736
System Call Error Handling 737 Process Control 738
8.1
8.2
8:3
8.4
8.5
8.6 8.7 8.8
9
Virtual Memory 801
9.1 Physical and Virtual Addressing
9.2 Address Spaces 804
8.4.1 8.4.2 8.4.3 8.4.4 8.4.5 8.4.6 Signals 8.5.1
Obtaining Process IDs 739
Creating and Terminating Processes Reaping Child Processes 743
Putting Processes to Sleep 749 , Loading and Running Programs 750 Using fork and execve to Run Programs
756
Signal Terminology 758 Sending Signals 759
Receiving Signals 762
Blocking and Unblocking Signals Writing Signal Handlers 766
8.5.2
8.5.3
8.5.4
8.5.5
8.5.6
8.5.7
Nonlocal Jumps 781
Tools for Manipula\ing Processes. 786
764
11 Synchronizing Flows to Avoid Nasty. Concurrency Bugs 776
Explicitly Waiting fat Signals 778
Summary 787
Bibliographic Notes 787 Homework Problems 788 Solutions to Practice Problems
,
795
8Q3
739
753
9.3 VM as a Tool f6r Caching 805
9.3.1 9.3.2 9.3.3 9.3.4 9.3.5 9.3.6
DRAM Cache Organization 806
Page Tables
Page Hits,
Page Faults
Allocating Pages 810 Locality to the Rescue Again
806 808
810 9.4 VM as \I Tool fdr Memory Management 811
(
‘
~21
9.5 VM as a Tool for Mem’ofy Protection .812
9.6 Address Translation 813
9.6.l 9.6.2 9.6.3 9.6.4
9.7 Case 9.7.1 9.7.2
Integrati~gCaches andYM 817
Speeding Up Address ‘Ifanslation with a TLB Multi-Level Page Tables 819
Putting It Together: End-to-End Addrl’,s~Trapslation
Study: The Intel Core i7/Linux Memory System 825 Core i7 Address Translation 826
Linux Virtual Memory System 828
808- 1
9.8 Memory Mapping 833
9.8.1 Shared Objects Revisited 833
9.8.2 The fork Function Revisited 836
9.8.3 The execve Function Revisited 836
9.8.4 User-Level Memory Mapping with the mmap Function
9.9 Dynamic Memory Alloqtion 839
9.9.l The malloc and free Functions ~40
9.9.2 Why Dynamic Memory Allocation? 843
9.9.3 Allocator Requirements and Goals 844
9.9.4 Fragmentation 846
9.9.5 Implementation Issues 846
9.9.6 Implicit Free Lists 847
9.9.7 Pl~cingAllocated Blocks 849
9.9.8 Splitting·Free Blocks -849′ 1 L ‘
9.9.9 Getting Additional Heap Memory ‘850
9.9.10 Coalescing Free Blocks 850
9.9.11 Coalescing with Boundary Tags 851
9.9.12 Putting It Together: Implementing a Simple Allocator
9.9.13 Explicit Free Lists 862
9.9.14 S_egregated Free Lists 863
9.10 Garbage Collection 865’
9.10.l Garbage Collector Basics 866
9.10.2 Mark&Sweep Garbage Collectors 867 · • 9.10.3 Conservative Mark&Sweep for C Programs 869
837
‘I .,
.. ~ ..
817
” 854
h
Gontents xv
xvi Conterits
9.11 Common Memory-Related Bugs in-CPrqgfams 870.
9.11.1 9.11.2 9.11.3 9.11.4
Dereferencing Bad Pointers 870
Reading Uninitialized Memory 871
Allowing Stack Buffer Overflows 871
Assuming That Pointers and the Objects They Point to Are the Same Size 872
9.11.5
9.11.6
9.11.7
9.11.8
9.11.9
9.11.10 Introducing Memory Leaks 875.
9.12 Summary 875 Bibliographic Notes 876
Homework Problems 876 Solutions to Practice Pr6blems 880’
Part Ill Interaction and Communicatiqn between Programs
10
System-Level I/O 889
10.1 Unix I/O S90
10.2 Files 891
10.3 Opening and Closing Files 893
10.4 Reading and Writing Files 895
10.5 Robust Reading and Writing with the Rm Pack~ge 897_
10.5.1 Rm Unbuffered Input and Output Functions 897
10.5.2 Rio Buffered Input Function§ 898
10.6 Reading File Metadata 903
10.7 Reading Directory Contents 905
10.8 Sharing Files 206
10.9 I/O Redirection 909
10.10 Standard I/O 911
10.11 Putting It Together: Which I/O Functions Shoul,d I Use? 911
10.12 Summary 913
Bibliographic Notes 914 Homework Problems 914 Solutions to Practice Problems 915
Making Off-by-One Errors 872
Referencing a Pointer Instead of the Object It Points f’o 873 ‘Misunderstanding Pointer Arithmetic &73
Referencing Nonexistent Variables 874 Referencing Data in Free Heap Blocks 874
11
Network Programming 917
11.l The Client-Server Programming M9del 918
11.2 Networks 919
11.3 The Global IP Inten;iet 924
11.3.1 IP .:\dc!resses 925
11.3.2 Internet Domain N’ames 927
11.3.3 Internet Connections 929
11.4 The Sockets Interface 932
11.4.1 Socket Addre,ss Structures 933
11.4.2 The socket Function 934
£I
11.4.3 The connect Function
11.4.4 The bind Function 935
934
r ·~ f
11.4.5 The listen Function 93~
r.
11.4.6 The acc-:pt Function 936
11.4.7 Host and Service Conversion 937
11.4.8 Helper Functions for the Socket~ Ip.terface 942
11.4.9 Example Echo Client and Server ·944
11.S Web Servers 948
11.5.1 Web Basics 948
11.5.7 Web Content 949
11.5.3 HTIP Transactions 950
11.5.4 Serving Dynamic Content 953
11.6 Putting It Together: The TINY Web Server 956
11.7 Summary 964
Bibliographic Notes 965 Homework Problems 965 Solutions to Practice Problems 966
12
Concurrent Programming 971
12.l Concurrent Programming with Processes 973
12.1.1 A Concurrent Server Based on Processes 974
12.1.2 Pros and Cons of Processes 975
12.2 Concurrent Programming with I/O Multiplexing 977 12.2.l A Concurrent Event-Driven Server Based on I/O
Multiplexing 980
12.2.2 Pros and Cons of I/O Multiplexing 985
12.3 Concurrent Programming with Threads 985 12.3.l Thread Execution Model 986
Contents xvii
xviii
Contents
12.3.2 Posix Threads 987
12.3.3 Creating Threads 988
12.3.4 Terminating Threads 988
12.3.5 ReapingTerminatedThreads 9~9
12.3.6 Detaching Threads 989
12.3.7 Initializing Threads 990
12.3.8 A Concurrent Server Based on Threads 9~1
12.4 Shared Variables in Threaded Programs 992
12.4.1 Threads Memory Model 993
12.4.2 Mapping Variables to Memory 994
12.4.3 Shared Variables 995
12.5 Synchronizing Threads with Semaphores 995
12.5.1 12.5.2 12.5.3 12.5.4 12.5.5
Progress Graphs 999
Semaphores 1001
Using Semaphores for Mutual Exclusion lp02
Using Semaphores to Scqedule Shared Respurces. 1004 Putting It Together: A Concurrent Server Based on Prethreading 1008
12.6 Using
12.7 Other Concurrency Issues 1020
Threads for Parallelism 1013
12.7.1 Thread Safety 1020
12.7.2 Reentrancy 1023 ”
12.7.3 Using Existing Library Functions in Threaded Programs 1024
12.7.4 Races 1025
12.7.5 Deadlocks 1027
12.8 Summary 1030 Bibliographic Notes 1030
Homework Problems 1031 Solutions to Practice Problems 1036
A
Error Handling 1041:
A.1 Error Handling in Unix Systems 1042
A.2 Error-Handling Wrappers 1043
References 1047
Index 1053
–
~
This book (known as CS:APP) is for computer scientists, computer engineers, and others who want to be able to write better programs by learning what is going on “under the hood'” of.a computer systefn.
Our aim’is to explain the enduring concepts underlying all computer systenls, and to show you the cohcrete ways that these ideas affect the correctn’ess;perfSr- mance,’lmd utility of your application programs.’Mlmy systems bobks are1\vritten from a builder’s perspective, describing how to implement the hardware or th’e sys- tems software, inC!uding the operating system, compiler, and network·iiltefface. Thisbook is wrihen from”a progr’dmme””‘ pefspective,’describing how application programmers can use their knowledge of a system to write better programs.’Of course, learning what a system i§ supposed to do provide&.a good first step in learn- ing how to build one,’so this book also serves as a· valuable introduction to those who go on to iinplemeht systems hardware and soffware. Most systems books also tend to focus on just one aspect of the system, for example, the•hardware archi- tecture: the operating system, the compiler, or the “network. Tiiis book” spans all of·these aspects,’ with !lie unifying theme of aprogranfmer’s perspective.
If you·study ancl-learh>.the-concepts-in-this-!:mok~you-.wiU1:le”on·yoni-wzj>’tcr— becoming the ‘rare power progranimer’who knows how things work’and how io
fix them when tbey’bteak. You will·be able to write programs that·make•better
use of the’caP,abiij(ies provided by theloperating systeni’and systellis software,
that operate ‘correctly across’1i wicte’ range of operating conditibhs and run’.-t:llne parameters,’ that run faster, and that avoid the flaws that make·ptogramS vu!Iler-
able t’6 cybefatt’ack-. You will be prepared to delve deeper into ‘advanced topics
sucn as conipilers;’c6mputer architecture, ‘operating sy~tems, embedded systems, networking, and cybersecurity.
Assumptions’ abou’t the Reader’s Backgrourid ”
This book focuses on systems that execute x86-64 machine code. x86-64 is the latest in an evolutionary path followed by Intel and its competitors .that started with the 8086 microprocessor in 1978. Due to the naming conventions used by Intel for its microprocessor line, this class of microprocessors is referr~d tq coll9ql’ially as “x86.” As semiconductor technology has evolved to allow more transistors to be integrated onto a single. chip, these processors have progressed greatly in their computing.ppwer. and theii:.mel)lory capacity. ‘As.part of, this ptogression, (hey have gone from pp,erating on·16-bit ‘XQW, to.32-bit.words with the; introduction of IA32 processors, and most recently to 64-bit words with x86-64.
We consider how these machines execute C programs on Linux. Linux is.one of a number·of operating systems·having their heritage in the Unix operating system developed originally by Bell Laboratories. Other members-of this class
Preface
xix
l I
II
t
of operating systems include Solaris, FreeBSD, and MacOS X. In recent years, these operating systems have maintained a high level of compatibility through the efforts of the Posix and Standard Unix Specification standardization efforts. Thus, the material in this book applies almost directly to these “Unix-like” operating systems.
The,text contains numerous programming examples that have been compiled and run on Linux systems. We assume that you have access to such a machine, and are able to log in and do simple things such as listing files and changing directo- ries. If your computer runs Microsoft Windows, we recommend that you install one of the many different virtual machine environments (such as Virtua!Box or VMWare) that allow programs written for one operating system (the guest OS) to run under another (the host OS).
We also assume that you have some familiarity with C or C++. If your only prior experience is with Java, the transition will require more effort on your part, but we will help you. Java and C share similar syntax and control statements. However, there are aspects of C (particularly pointers, explicit dynamic memory allocation, and formatted I/O) that do not exist in Java. Fortunately, C is a small language, and it is clearly and beautifully described in the classic “K&R” text by J?rian Kernighan and [61]. Regardless of your programming background, consider K&R an essential part of your personal systems library. If your prior experience \s with an interpreted language, such as Python, Ruby, or Perl, you will definitely want to devote some ti_me to learning C before you attempt to use this book.
Several of the early chapters in the book explore the interactions between C programs and their machine-language counterparts. The machine-language exam- ples were all generated by the GNU ace compiler running on x86-64 processors. We do not assume any prior experience with hardware, machine language, or assembly-language programming.
How to Read the Book
Learning how computer systems work from a programmer’s perspective is great fun, mainly because you can do it actively. Whenever you learn somethihg new, you can try it out right away and see the result firsthand. In fact, we believe that the only way to learn systems is to do systems, either working concrete problems or writing and running programs on real systems.
This theme pervades the entire book. When a new concept is introduced, it is followed in the text by one or more practice problems that you should work
x x
Preface
–~·~·——‘———-~-‘—‘code!intro/hello.c
1’ #include
2
3 int main() 4{
5 printf(“hello, world\n”);
6 return O;
7}
————-~———- code/introlhel/o.c Figure 1 A typical code exqmple.
immeC!iately to test your understanding. Solutions t6 the practice problems are at the end of each chapter. As you read, try to solve each problem on your own and then check the solution to make sure you are on the rigll.t track. Each chapter is fallowed by a s6t of homework problems of varying difficulty. Your instructor has the solutiohs to \he h6mework p1ob!ems in an instructor’s manual. For each homew9rk problem, we show a rating 6f the amount of effort we feel it will require:
”
+ Should require just a few min~t~s. Little or no programming required.
~ •~ •.1 •
~,t MighVygui,re up, to 20 mip.utes. Often il)volves Wfili.i;ig.and ,t,esting some
code. (Many of these,arq’flerived from pn1blems.we ha,ve given on exams.)
+++ Requires a sjgnificant;,effort1 perhaps1-2 hours. Generally in\lolves writ- ing and testing a significant amount of code..
++++ A lab assignment, requiring up to 10 hours of effort.
Each eode example in the te;t was formatted directly, Without any manual
intervention, from a C program compile
0(c) 0(c) •
••• •••• •• •• ••
O R Q Q,RG+ res res+ SP • • ••
!=hapter
·1 2 3 4 5
10 11 12
Figure 2
from ‘. Notes: The 0 symbol denotes·partial coverage of a chapter, as follows: (a) hardware only; (bl no dynamic storage ~llocaHon; (c) no dynamic’linking;
Topic
~Tour of syste’ms
D a t a repres’en’tation
Machine language,
Processor architecttlre
Code optimization
11 T 1
Memo)”Y hierarchy
‘ j .I
Linking I!, ,
Exception\tl ~pntrol.flow Virtual memory System-level r/O Network .Programming Concurrent programming
‘
•·• •
“• • .; • 0(d)
FiV’e systems ~oursesbased on the CS:APP book. ICS+’is the 15-213 course
‘I
SP. A sys\ems pro’~tariuhingcourse. Th~scourse is’ similar to JCS+, 6ut if drops floating point “and performance ‘optimiZati:on, ‘and it places more empha- sis on systems ‘PJOgramJlling, iμclm~ing proces§ ,control, dynamic linking, system-ley<;>) 1/0, qe~work; Jlf9gramming, qnd con01rrent pr9gramming. In- structqr~ mjght,w,ant tq supply,n;ient fr,9111 othyr sources for advanced topics
,such as dayl1JO!}~,;terprinal ~ontr9l, anq U,Q,qJPC.
The main mes~ag;’ofFigu)’~2is that t)l~CS:APP’boqj< giyrs a lot 9f options to students anil instructors. If