深入理解计算机系统（英文版）下载

Contents Preface i 1 Introduction 1 1.1 Information isBits inContext . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Programs areTranslated byOtherPrograms intoDifferent Forms . . . . . . . . . . . . . . . 3 1.3 ItPays toUnderstandHowCompilation SystemsWork . . . . . . . . . . . . . . . . . . . . 4 1.4 Processors Read and Interpret Instructions Stored in Memory . . . . . . . . . . . . . . . . . 5 1.4.1 HardwareOrganization of aSystem . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4.2 Running the helloProgram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 CachesMatter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.6 StorageDevicesFormaHierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.7 TheOperating SystemManages theHardware . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.7.1 Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.7.2 Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.7.3 Virtual Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.7.4 Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.8 SystemsCommunicateWithOtherSystemsUsingNetworks . . . . . . . . . . . . . . . . . 16 1.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 I Program Structure and Execution 19 2 Representing and Manipulating Information 21 2.1 Information Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.1.1 HexadecimalNotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1.2 Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3 4 CONTENTS 2.1.3 DataSizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.4 Addressing and Byte Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.1.5 Representing Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.1.6 Representing Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.1.7 BooleanAlgebras andRings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.1.8 Bit-Level Operations in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.1.9 LogicalOperations inC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.1.10 ShiftOperations inC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.2 Integer Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.2.1 IntegralDataTypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.2.2 Unsigned andTwo’sComplementEncodings . . . . . . . . . . . . . . . . . . . . . 41 2.2.3 Conversions BetweenSigned andUnsigned . . . . . . . . . . . . . . . . . . . . . . 45 2.2.4 Signed vs.Unsigned inC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.2.5 Expanding the Bit Representation of a Number . . . . . . . . . . . . . . . . . . . . 49 2.2.6 TruncatingNumbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.2.7 Advice onSigned vs.Unsigned . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.3 Integer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.3.1 Unsigned Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.3.2 Two’s Complement Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.3.3 Two’sComplementNegation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.3.4 Unsigned Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.3.5 Two’s Complement Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.3.6 Multiplying by Powers of Two . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.3.7 Dividing byPowersofTwo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 2.4 Floating Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.4.1 FractionalBinaryNumbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 2.4.2 IEEE Floating-Point Representation . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.4.3 ExampleNumbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.4.4 Rounding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 2.4.5 Floating-PointOperations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 2.4.6 Floating Point inC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 CONTENTS 5 3 Machine-Level Representation of C Programs 89 3.1 AHistorical Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.2 ProgramEncodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.2.1 Machine-LevelCode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 3.2.2 CodeExamples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 3.2.3 A Note on Formatting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.3 DataFormats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 3.4 Accessing Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3.4.1 Operand Specifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3.4.2 DataMovement Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 3.4.3 DataMovementExample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.5 Arithmetic and Logical Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.5.1 LoadEffectiveAddress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3.5.2 Unary andBinaryOperations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3.5.3 ShiftOperations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 3.5.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 3.5.5 Special Arithmetic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 3.6 Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 3.6.1 Condition Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 3.6.2 Accessing the Condition Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 3.6.3 Jump Instructions and theirEncodings . . . . . . . . . . . . . . . . . . . . . . . . . 114 3.6.4 TranslatingConditionalBranches . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 3.6.5 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 3.6.6 SwitchStatements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 3.7 Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 3.7.1 StackFrameStructure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 3.7.2 Transferring Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 3.7.3 RegisterUsageConventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 3.7.4 Procedure Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 3.7.5 Recursive Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 3.8 Array Allocation and Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 3.8.1 BasicPrinciples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 3.8.2 Pointer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 6 CONTENTS 3.8.3 Arrays and Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 3.8.4 NestedArrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 3.8.5 FixedSizeArrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 3.8.6 DynamicallyAllocatedArrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 3.9 HeterogeneousDataStructures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 3.9.1 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 3.9.2 Unions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 3.10 Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 3.11 Putting it Together: Understanding Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . 162 3.12 Life in the Real World: Using the GDB Debugger . . . . . . . . . . . . . . . . . . . . . . . 165 3.13 Out-of-Bounds Memory References and Buffer Overflow . . . . . . . . . . . . . . . . . . . 167 3.14 *Floating-Point Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 3.14.1 Floating-PointRegisters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 3.14.2 Extended-Precision Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 3.14.3 Stack Evaluation of Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 3.14.4 Floating-PointDataMovement andConversionOperations . . . . . . . . . . . . . . 179 3.14.5 Floating-Point Arithmetic Instructions . . . . . . . . . . . . . . . . . . . . . . . . . 181 3.14.6 UsingFloating Point inProcedures . . . . . . . . . . . . . . . . . . . . . . . . . . 183 3.14.7 Testing andComparing Floating-PointValues . . . . . . . . . . . . . . . . . . . . . 184 3.15 *Embedding Assembly Code in C Programs . . . . . . . . . . . . . . . . . . . . . . . . . . 186 3.15.1 Basic Inline Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 3.15.2 Extended Form of asm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 3.16 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 4 Processor Architecture 201 5 Optimizing Program Performance 203 5.1 Capabilities and Limitations of Optimizing Compilers . . . . . . . . . . . . . . . . . . . . . 204 5.2 Expressing Program Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 5.3 ProgramExample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 5.4 Eliminating LoopInefficiencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 5.5 Reducing ProcedureCalls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 5.6 EliminatingUnneededMemoryReferences . . . . . . . . . . . . . . . . . . . . . . . . . . 218 CONTENTS 7 5.7 Understanding Modern Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 5.7.1 OverallOperation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 5.7.2 FunctionalUnitPerformance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 5.7.3 A Closer Look at Processor Operation . . . . . . . . . . . . . . . . . . . . . . . . . 225 5.8 Reducing LoopOverhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 5.9 Converting to Pointer Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 5.10 Enhancing Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 5.10.1 Loop Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 5.10.2 Register Spilling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 5.10.3 Limits toParallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 5.11 Putting it Together: Summary of Results for Optimizing Combining Code . . . . . . . . . . 247 5.11.1 Floating-Point PerformanceAnomaly . . . . . . . . . . . . . . . . . . . . . . . . . 248 5.11.2 Changing Platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 5.12 Branch Prediction and Misprediction Penalties . . . . . . . . . . . . . . . . . . . . . . . . . 249 5.13 UnderstandingMemoryPerformance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 5.13.1 LoadLatency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 5.13.2 StoreLatency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 5.14 Life intheRealWorld: Performance ImprovementTechniques . . . . . . . . . . . . . . . . 260 5.15 Identifying and Eliminating Performance Bottlenecks . . . . . . . . . . . . . . . . . . . . . 261 5.15.1 ProgramProfiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 5.15.2 Using aProfiler toGuideOptimization . . . . . . . . . . . . . . . . . . . . . . . . 263 5.15.3 Amdahl’sLaw . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 5.16 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 6 The Memory Hierarchy 275 6.1 Storage Technologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 6.1.1 Random-Access Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 6.1.2 DiskStorage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 6.1.3 Storage Technology Trends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 6.2 Locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 6.2.1 Locality of References to Program Data . . . . . . . . . . . . . . . . . . . . . . . . 295 6.2.2 Locality of Instruction Fetches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 6.2.3 Summary of Locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 8 CONTENTS 6.3 TheMemoryHierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 6.3.1 Caching in theMemoryHierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 6.3.2 Summary ofMemoryHierarchyConcepts . . . . . . . . . . . . . . . . . . . . . . . 303 6.4 CacheMemories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 6.4.1 GenericCacheMemoryOrganization . . . . . . . . . . . . . . . . . . . . . . . . . 305 6.4.2 Direct-MappedCaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 6.4.3 SetAssociativeCaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 6.4.4 FullyAssociativeCaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 6.4.5 Issues with Writes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 6.4.6 Instruction Caches andUnifiedCaches . . . . . . . . . . . . . . . . . . . . . . . . 319 6.4.7 Performance Impact ofCacheParameters . . . . . . . . . . . . . . . . . . . . . . . 320 6.5 Writing Cache-friendly Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 6.6 Putting it Together: The Impact of Caches on Program Performance . . . . . . . . . . . . . 327 6.6.1 The Memory Mountain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 6.6.2 Rearranging Loops to Increase Spatial Locality . . . . . . . . . . . . . . . . . . . . 331 6.6.3 Using Blocking to Increase Temporal Locality . . . . . . . . . . . . . . . . . . . . 335 6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 II Running Programs on a System 347 7 Linking 349 7.1 CompilerDrivers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 7.2 StaticLinking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 7.3 Object Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 7.4 RelocatableObjectFiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353 7.5 Symbols andSymbolTables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 7.6 SymbolResolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 7.6.1 How Linkers Resolve Multiply-Defined Global Symbols . . . . . . . . . . . . . . . 358 7.6.2 LinkingwithStaticLibraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 7.6.3 HowLinkersUseStaticLibraries toResolveReferences . . . . . . . . . . . . . . . 364 7.7 Relocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365 7.7.1 Relocation Entries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 7.7.2 Relocating SymbolReferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 CONTENTS 9 7.8 ExecutableObjectFiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371 7.9 LoadingExecutableObject Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372 7.10 DynamicLinkingwithSharedLibraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 7.11 Loading andLinking SharedLibraries fromApplications . . . . . . . . . . . . . . . . . . . 376 7.12 *Position-Independent Code (PIC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 7.13 Tools forManipulatingObjectFiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 7.14 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382 8 Exceptional Control Flow 391 8.1 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392 8.1.1 ExceptionHandling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393 8.1.2 Classes of Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394 8.1.3 Exceptions in Intel Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 8.2 Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398 8.2.1 LogicalControlFlow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398 8.2.2 PrivateAddress Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399 8.2.3 User andKernelModes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400 8.2.4 Context Switches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401 8.3 SystemCalls andErrorHandling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 8.4 Process Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403 8.4.1 Obtaining Process ID’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404 8.4.2 Creating and Terminating Processes . . . . . . . . . . . . . . . . . . . . . . . . . . 404 8.4.3 Reaping Child Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409 8.4.4 Putting Processes to Sleep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414 8.4.5 Loading and Running Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415 8.4.6 Using fork and execve toRunPrograms . . . . . . . . . . . . . . . . . . . . . . 418 8.5 Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 8.5.1 SignalTerminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 8.5.2 Sending Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 8.5.3 Receiving Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426 8.5.4 SignalHandling Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429 8.5.5 Portable SignalHandling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434 8.6 Nonlocal Jumps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436 10 CONTENTS 8.7 Tools for Manipulating Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441 8.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441 9 Measuring Program Execution Time 449 9.1 TheFlowofTimeonaComputerSystem . . . . . . . . . . . . . . . . . . . . . . . . . . . 450 9.1.1 Process Scheduling and Timer Interrupts . . . . . . . . . . . . . . . . . . . . . . . 451 9.1.2 Time fromanApplication Program’sPerspective . . . . . . . . . . . . . . . . . . . 452 9.2 Measuring Time by Interval Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454 9.2.1 Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 9.2.2 Reading the Process Timers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 9.2.3 Accuracy of Process Timers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457 9.3 Cycle Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459 9.3.1 IA32 Cycle Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460 9.4 Measuring Program Execution Time with Cycle Counters . . . . . . . . . . . . . . . . . . . 460 9.4.1 TheEffects ofContextSwitching . . . . . . . . . . . . . . . . . . . . . . . . . . . 462 9.4.2 Caching andOtherEffects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 9.4.3 The K-Best Measurement Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . 467 9.5 Time-of-Day Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476 9.6 Putting it Together: An Experimental Protocol . . . . . . . . . . . . . . . . . . . . . . . . . 478 9.7 Looking into the Future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480 9.8 Life in the Real World: An Implementation of the K-Best Measurement Scheme . . . . . . 480 9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 10 Virtual Memory 485 10.1 Physical and Virtual Addressing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486 10.2 Address Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487 10.3 VMas aTool forCaching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488 10.3.1 DRAM Cache Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 10.3.2 PageTables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 10.3.3 PageHits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490 10.3.4 PageFaults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491 10.3.5 Allocating Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492 10.3.6 Locality to the Rescue Again . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493 CONTENTS 11 10.4 VMas aTool forMemoryManagement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493 10.4.1 Simplifying Linking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 10.4.2 Simplifying Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 10.4.3 Simplifying Memory Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495 10.4.4 Simplifying Loading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495 10.5 VMas aTool forMemoryProtection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496 10.6 AddressTranslation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497 10.6.1 Integrating Caches andVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500 10.6.2 Speeding upAddressTranslationwith aTLB . . . . . . . . . . . . . . . . . . . . . 500 10.6.3 Multi-level Page Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 10.6.4 Putting it Together: End-to-end Address Translation . . . . . . . . . . . . . . . . . 504 10.7 Case Study: The Pentium/Linux Memory System . . . . . . . . . . . . . . . . . . . . . . . 508 10.7.1 PentiumAddressTranslation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508 10.7.2 Linux Virtual Memory System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513 10.8 MemoryMapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516 10.8.1 SharedObjectsRevisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517 10.8.2 The forkFunctionRevisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519 10.8.3 The execveFunctionRevisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519 10.8.4 User-level Memory Mapping with the mmapFunction . . . . . . . . . . . . . . . . 520 10.9 DynamicMemoryAllocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522 10.9.1 The malloc and freeFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . 523 10.9.2 WhyDynamicMemoryAllocation? . . . . . . . . . . . . . . . . . . . . . . . . . . 524 10.9.3 AllocatorRequirements andGoals . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 10.9.4 Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528 10.9.5 Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529 10.9.6 Implicit FreeLists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529 10.9.7 PlacingAllocatedBlocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531 10.9.8 Splitting Free Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531 10.9.9 Getting Additional Heap Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . 532 10.9.10 Coalescing Free Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532 10.9.11 Coalescing with Boundary Tags . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533 10.9.12 Putting it Together: Implementing a Simple Allocator . . . . . . . . . . . . . . . . . 535 10.9.13Explicit FreeLists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543 12 CONTENTS 10.9.14Segregated FreeLists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544 10.10GarbageCollection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546 10.10.1GarbageCollectorBasics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547 10.10.2Mark&SweepGarbageCollectors . . . . . . . . . . . . . . . . . . . . . . . . . . . 548 10.10.3ConservativeMark&Sweep forCPrograms . . . . . . . . . . . . . . . . . . . . . . 550 10.11CommonMemory-relatedBugs inCPrograms . . . . . . . . . . . . . . . . . . . . . . . . 551 10.11.1Dereferencing BadPointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551 10.11.2 Reading Uninitialized Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551 10.11.3AllowingStackBufferOverflows . . . . . . . . . . . . . . . . . . . . . . . . . . . 552 10.11.4Assuming thatPointers and theObjects theyPoint toAre theSameSize . . . . . . . 552 10.11.5MakingOff-by-oneErrors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553 10.11.6Referencing aPointer Instead of theObject itPoints to . . . . . . . . . . . . . . . . 553 10.11.7Misunderstanding Pointer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 554 10.11.8ReferencingNon-existentVariables . . . . . . . . . . . . . . . . . . . . . . . . . . 554 10.11.9ReferencingData inFreeHeapBlocks . . . . . . . . . . . . . . . . . . . . . . . . . 555 10.11.10Introducing Memory Leaks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555 10.12Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556 III Interaction and Communication Between Programs 561 11 Concurrent Programming with Threads 563 11.1 BasicThreadConcepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563 11.2 ThreadControl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566 11.2.1 CreatingThreads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567 11.2.2 TerminatingThreads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567 11.2.3 ReapingTerminatedThreads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568 11.2.4 Detaching Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568 11.3 SharedVariables inThreaded Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570 11.3.1 ThreadsMemoryModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570 11.3.2 MappingVariables toMemory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570 11.3.3 SharedVariables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572 11.4 Synchronizing Threads with Semaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . 573 11.4.1 SequentialConsistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573 CONTENTS 13 11.4.2 ProgressGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576 11.4.3 Protecting Shared Variables with Semaphores . . . . . . . . . . . . . . . . . . . . . 579 11.4.4 Posix Semaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580 11.4.5 Signaling With Semaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581 11.5 Synchronizing Threads with Mutex and Condition Variables . . . . . . . . . . . . . . . . . 583 11.5.1 MutexVariables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583 11.5.2 Condition Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586 11.5.3 Barrier Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587 11.5.4 Timeout Waiting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588 11.6 Thread-safe andReentrant Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592 11.6.1 Reentrant Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593 11.6.2 Thread-safe Library Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596 11.7 OtherSynchronization Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596 11.7.1 Races . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596 11.7.2 Deadlocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599 11.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600 12 Network Programming 605 12.1 Client-Server ProgrammingModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605 12.2 Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606 12.3 TheGlobal IPInternet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611 12.3.1 IP Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612 12.3.2 InternetDomainNames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614 12.3.3 InternetConnections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618 12.4 Unixfile I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 619 12.4.1 The read and writeFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . 620 12.4.2 Robust File I/O With the readn and writenFunctions. . . . . . . . . . . . . . . 621 12.4.3 Robust Input of Text Lines Using the readlineFunction . . . . . . . . . . . . . . 623 12.4.4 The statFunction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623 12.4.5 The dup2Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626 12.4.6 The closeFunction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627 12.4.7 OtherUnix I/OFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628 12.4.8 Unix I/Ovs. Standard I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628 14 CONTENTS 12.5 TheSockets Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629 12.5.1 SocketAddressStructures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629 12.5.2 The socketFunction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631 12.5.3 The connectFunction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631 12.5.4 The bindFunction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633 12.5.5 The listenFunction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633 12.5.6 The acceptFunction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635 12.5.7 ExampleEchoClient andServer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636 12.6 Concurrent Servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638 12.6.1 Concurrent Servers Based on Processes . . . . . . . . . . . . . . . . . . . . . . . . 638 12.6.2 Concurrent Servers Based on Threads . . . . . . . . . . . . . . . . . . . . . . . . . 640 12.7 WebServers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646 12.7.1 WebBasics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647 12.7.2 WebContent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647 12.7.3 HTTPTransactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648 12.7.4 ServingDynamicContent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651 12.8 Putting it Together: The TINYWebServer . . . . . . . . . . . . . . . . . . . . . . . . . . . 652 12.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662 A Error handling 665 A.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665 A.2 Error handling inUnix systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666 A.3 Error-handlingwrappers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667 A.4 The csapp.h header file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671 A.5 The csapp.c source file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675 B Solutions to Practice Problems 691 B.1 Intro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691 B.2 Representing and Manipulating Information . . . . . . . . . . . . . . . . . . . . . . . . . . 691 B.3 Machine Level Representation of C Programs . . . . . . . . . . . . . . . . . . . . . . . . . 700 B.4 Processor Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715 B.5 Optimizing ProgramPerformance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715 B.6 TheMemoryHierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 717 CONTENTS 15 B.7 Linking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723 B.8 ExceptionalControl Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725 B.9 Measuring Program Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728 B.10 Virtual Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 730 B.11 Concurrent ProgrammingwithThreads . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734 B.12 NetworkProgramming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736