دانلود کتاب Computer Systems: A Programmer's Perspective

فهرست مطالب :

Computer Systems A Programmer\'s Perspective......Page 2
Computer Systems A Programmer\'s Perspective......Page 3
MasteringEngineering®......Page 10
Contents......Page 11
Preface......Page 37
Assumptions about the Reader\'s Background......Page 38
How to Read the Book......Page 40
Book Overview......Page 43
New to This Edition......Page 51
Origins of the Book......Page 54
For Instructors: Courses Based on the Book......Page 56
For Instructors: Classroom-Tested Laboratory Exercises......Page 59
About the Authors......Page 70
Chapter 1 A Tour of Computer Systems......Page 74
1.1 Information Is Bits + Context......Page 79
1.2 Programs Are Translated by Other Programs into Different Forms......Page 83
1.3 It Pays to Understand How Compilation Systems Work......Page 87
1.4 Processors Read and Interpret Instructions Stored in Memory......Page 90
1.4.1 Hardware Organization of a System......Page 91
I/O Devices......Page 92
Main Memory......Page 93
Processor......Page 94
1.4.2 Running the hello Program......Page 96
1.5 Caches Matter......Page 98
1.6 Storage Devices Form a Hierarchy......Page 103
1.7 The Operating System Manages the Hardware......Page 105
1.7.1 Processes......Page 106
1.7.2 Threads......Page 111
1.7.3 Virtual Memory......Page 112
1.7.4 Files......Page 114
1.8 Systems Communicate with Other Systems Using Networks......Page 115
1.9.1 Amdahl\'s Law......Page 119
Practice Problem 1.1 (solution page 28)......Page 120
Practice Problem 1.2 (solution page 28)......Page 122
Thread-Level Concurrency......Page 123
Instruction-Level Parallelism......Page 127
1.9.3 The Importance of Abstractions in Computer Systems......Page 128
1.10 Summary......Page 131
Bibliographic Notes......Page 133
Part I Program Structure and Execution......Page 136
Chapter 2 Representing and Manipulating Information......Page 137
2.1 Information Storage......Page 145
2.1.1 Hexadecimal Notation......Page 149
Practice Problem 2.2 (solution page 143)......Page 152
Practice Problem 2.3 (solution page 144)......Page 154
Practice Problem 2.4 (solution page 144)......Page 155
2.1.2 Data Sizes......Page 156
2.1.3 Addressing and Byte Ordering......Page 161
Practice Problem 2.5 (solution page 144)......Page 176
2.1.4 Representing Strings......Page 177
2.1.5 Representing Code......Page 178
2.1.6 Introduction to Boolean Algebra......Page 180
Practice Problem 2.8 (solution page 145)......Page 183
Practice Problem 2.9 (solution page 146)......Page 186
2.1.7 Bit-Level Operations in C......Page 187
Practice Problem 2.10 (solution page 146)......Page 188
Practice Problem 2.11 (solution page 146)......Page 190
Practice Problem 2.12 (solution page 146)......Page 191
2.1.8 Logical Operations in C......Page 192
Practice Problem 2.14 (solution page 147)......Page 194
2.1.9 Shift Operations in C......Page 195
Practice Problem 2.16 (solution page 148)......Page 197
2.2 Integer Representations......Page 200
2.2.1 Integral Data Types......Page 201
2.2.2 Unsigned Encodings......Page 206
2.2.3 Two\'s-Complement Encodings......Page 209
Practice Problem 2.17 (solution page 148)......Page 213
Practice Problem 2.18 (solution page 149)......Page 221
2.2.4 Conversions between Signed and Unsigned......Page 223
Practice Problem 2.19 (solution page 149)......Page 226
Practice Problem 2.20 (solution page 149)......Page 230
2.2.5 Signed versus Unsigned in C......Page 233
2.2.6 Expanding the Bit Representation of a Number......Page 237
Practice Problem 2.22 (solution page 150)......Page 244
Practice Problem 2.23 (solution page 150)......Page 245
2.2.7 Truncating Numbers......Page 246
Practice Problem 2.24 (solution page 150)......Page 250
2.2.8 Advice on Signed versus Unsigned......Page 251
Practice Problem 2.26 (solution page 151)......Page 252
2.3.1 Unsigned Addition......Page 255
Practice Problem 2.27 (solution page 152)......Page 265
2.3.2 Two\'s-Complement Addition......Page 267
Practice Problem 2.29 (solution page 152)......Page 276
Practice Problem 2.31 (solution page 153)......Page 277
Practice Problem 2.32 (solution page 153)......Page 278
2.3.3 Two\'s-Complement Negation......Page 279
Practice Problem 2.33 (solution page 153)......Page 280
2.3.4 Unsigned Multiplication......Page 283
2.3.5 Two\'s-Complement Multiplication......Page 284
Practice Problem 2.35 (solution page 154)......Page 288
Practice Problem 2.37 (solution page 155)......Page 289
2.3.6 Multiplying by Constants......Page 293
Practice Problem 2.38 (solution page 155)......Page 297
Practice Problem 2.40 (solution page 156)......Page 298
2.3.7 Dividing by Powers of 2......Page 299
Practice Problem 2.42 (solution page 156)......Page 307
Practice Problem 2.43 (solution page 157)......Page 308
2.3.8 Final Thoughts on Integer Arithmetic......Page 309
Practice Problem 2.44 (solution page 157)......Page 310
2.4 Floating Point......Page 312
2.4.1 Fractional Binary Numbers......Page 313
Practice Problem 2.45 (solution page 157)......Page 317
Practice Problem 2.46 (solution page 158)......Page 318
2.4.2 IEEE Floating-Point Representation......Page 319
2.4.3 Example Numbers......Page 324
Practice Problem 2.47 (solution page 158)......Page 328
Practice Problem 2.48 (solution page 159)......Page 333
2.4.4 Rounding......Page 334
Practice Problem 2.50 (solution page 159)......Page 337
Practice Problem 2.52 (solution page 160)......Page 338
2.4.5 Floating-Point Operations......Page 339
2.4.6 Floating Point in C......Page 343
Practice Problem 2.53 (solution page 160)......Page 344
Practice Problem 2.54 (solution page 160)......Page 345
2.5 Summary......Page 347
Bibliographic Notes......Page 351
2.57 ♦......Page 352
Bit-Level Integer Coding Rules......Page 353
2.62 ♦♦♦......Page 356
2.63 ♦♦♦......Page 357
2.64 ♦......Page 358
2.66 ♦♦♦♦......Page 359
2.67 ♦♦......Page 360
2.68 ♦♦......Page 361
2.69 ♦♦♦......Page 362
2.71......Page 363
2.72......Page 365
2.74......Page 366
2.75......Page 367
2.76......Page 368
2.79......Page 369
2.81......Page 370
2.82......Page 371
2.84......Page 372
2.85......Page 373
2.86......Page 374
2.87......Page 375
2.88......Page 376
2.89......Page 378
2.90......Page 379
Bit-Level Floating-Point Coding Rules......Page 381
2.92 ♦♦......Page 383
2.95......Page 384
2.96......Page 385
2.97......Page 386
Chapter 3 Machine-Level Representation of Programs......Page 434
3.1 A Historical Perspective......Page 443
3.2 Program Encodings......Page 449
3.2.1 Machine-Level Code......Page 450
3.2.2 Code Examples......Page 454
3.2.3 Notes on Formatting......Page 462
3.3 Data Formats......Page 467
3.4 Accessing Information......Page 471
3.4.1 Operand Specifiers......Page 474
Practice Problem 3.1 (solution page 325)......Page 476
3.4.2 Data Movement Instructions......Page 478
Practice Problem 3.2 (solution page 325)......Page 484
Practice Problem 3.3 (solution page 326)......Page 486
3.4.3 Data Movement Example......Page 487
Practice Problem 3.4 (solution page 326)......Page 489
Practice Problem 3.5 (solution page 327)......Page 492
3.4.4 Pushing and Popping Stack Data......Page 493
3.5.1 Load Effective Address......Page 498
Practice Problem 3.6 (solution page 327)......Page 500
Practice Problem 3.7 (solution page 328)......Page 502
3.5.2 Unary and Binary Operations......Page 503
Practice Problem 3.8 (solution page 328)......Page 504
3.5.3 Shift Operations......Page 505
Practice Problem 3.9 (solution page 328)......Page 506
3.5.4 Discussion......Page 508
Practice Problem 3.10 (solution page 329)......Page 509
Practice Problem 3.11 (solution page 329)......Page 510
3.5.5 Special Arithmetic Operations......Page 511
Practice Problem 3.12 (solution page 329)......Page 517
3.6 Control......Page 518
3.6.1 Condition Codes......Page 519
3.6.2 Accessing the Condition Codes......Page 522
Practice Problem 3.13 (solution page 330)......Page 526
3.6.3 Jump Instructions......Page 528
3.6.4 Jump Instruction Encodings......Page 532
Practice Problem 3.15 (solution page 330)......Page 537
3.6.5 Implementing Conditional Branches with Conditional Control......Page 538
Practice Problem 3.16 (solution page 331)......Page 544
Practice Problem 3.17 (solution page 331)......Page 545
3.6.6 Implementing Conditional Branches with Conditional Moves......Page 546
Practice Problem 3.19 (solution page 332)......Page 553
Practice Problem 3.20 (solution page 333)......Page 560
Do-While Loops......Page 561
Practice Problem 3.22 (solution page 333)......Page 565
Practice Problem 3.23 (solution page 334)......Page 567
While Loops......Page 569
Practice Problem 3.24 (solution page 335)......Page 573
Practice Problem 3.25 (solution page 335)......Page 576
Practice Problem 3.26 (solution page 336)......Page 579
For Loops......Page 581
Practice Problem 3.28 (solution page 336)......Page 586
Practice Problem 3.29 (solution page 337)......Page 588
3.6.8 Switch Statements......Page 589
Practice Problem 3.30 (solution page 338)......Page 597
Practice Problem 3.31 (solution page 338)......Page 599
3.7 Procedures......Page 603
3.7.1 The Run-Time Stack......Page 604
3.7.2 Control Transfer......Page 608
Practice Problem 3.32 (solution page 339)......Page 614
3.7.3 Data Transfer......Page 616
Practice Problem 3.33 (solution page 339)......Page 618
3.7.4 Local Storage on the Stack......Page 621
3.7.5 Local Storage in Registers......Page 628
Practice Problem 3.34 (solution page 340)......Page 631
3.7.6 Recursive Procedures......Page 632
Practice Problem 3.35 (solution page 340)......Page 635
3.8.1 Basic Principles......Page 637
Practice Problem 3.36 (solution page 341)......Page 639
3.8.2 Pointer Arithmetic......Page 640
Practice Problem 3.37 (solution page 341)......Page 642
3.8.3 Nested Arrays......Page 643
Practice Problem 3.38 (solution page 341)......Page 646
3.8.4 Fixed-Size Arrays......Page 647
Practice Problem 3.40 (solution page 342)......Page 651
3.8.5 Variable-Size Arrays......Page 652
3.9.1 Structures......Page 658
Practice Problem 3.41 (solution page 343)......Page 664
Practice Problem 3.42 (solution page 343)......Page 665
3.9.2 Unions......Page 667
Practice Problem 3.43 (solution page 344)......Page 673
3.9.3 Data Alignment......Page 675
Practice Problem 3.44 (solution page 345)......Page 679
Practice Problem 3.45 (solution page 345)......Page 680
3.10.1 Understanding Pointers......Page 683
3.10.2 Life in the Real World: Using the gdb Debugger......Page 688
3.10.3 Out-of-Bounds Memory References and Buffer Overflow......Page 689
Practice Problem 3.46 (solution page 346)......Page 696
Stack Randomization......Page 700
Stack Corruption Detection......Page 704
Practice Problem 3.48 (solution page 347)......Page 707
Limiting Executable Code Regions......Page 709
3.10.5 Supporting Variable-Size Stack Frames......Page 711
Practice Problem 3.49 (solution page 347)......Page 717
3.11 Floating-Point Code......Page 719
3.11.1 Floating-Point Movement and Conversion Operations......Page 723
Practice Problem 3.50 (solution page 347)......Page 732
Practice Problem 3.51 (solution page 348)......Page 733
3.11.2 Floating-Point Code in Procedures......Page 734
3.11.3 Floating-Point Arithmetic Operations......Page 736
Practice Problem 3.53 (solution page 348)......Page 739
3.11.4 Defining and Using Floating-Point Constants......Page 740
3.11.5 Using Bitwise Operations in Floating-Point Code......Page 743
3.11.6 Floating-Point Comparison Operations......Page 744
Practice Problem 3.57 (solution page 350)......Page 751
3.11.7 Observations about Floating-Point Code......Page 752
3.12 Summary......Page 753
Bibliographic Notes......Page 756
3.58......Page 758
3.59......Page 759
3.60......Page 760
3.62......Page 762
3.63......Page 763
3.64......Page 768
3.65......Page 770
3.66......Page 771
3.67......Page 773
3.68......Page 776
3.69......Page 777
3.70......Page 779
3.71......Page 781
3.72......Page 782
3.74......Page 784
3.75......Page 785
Chapter 4 Processor Architecture......Page 851
4.1.1 Programmer-Visible State......Page 861
4.1.2 Y86-64 Instructions......Page 863
4.1.3 Instruction Encoding......Page 866
Practice Problem 4.2 (solution page 481)......Page 871
4.1.4 Y86-64 Exceptions......Page 878
4.1.5 Y86-64 Programs......Page 880
Practice Problem 4.3 (solution page 482)......Page 889
Practice Problem 4.5 (solution page 483)......Page 890
4.1.6 Some Y86-64 Instruction Details......Page 891
Practice Problem 4.7 (solution page 484)......Page 892
Practice Problem 4.8 (solution page 484)......Page 893
4.2 Logic Design and the Hardware Control Language HCL......Page 896
4.2.1 Logic Gates......Page 898
4.2.2 Combinational Circuits and HCL Boolean Expressions......Page 899
Practice Problem 4.9 (solution page 484)......Page 900
4.2.3 Word-Level Combinational Circuits and HCL Integer Expressions......Page 903
Practice Problem 4.10 (solution page 484)......Page 905
Practice Problem 4.11 (solution page 484)......Page 910
4.2.4 Set Membership......Page 911
4.2.5 Memory and Clocking......Page 913
4.3.1 Organizing Processing into Stages......Page 919
Practice Problem 4.13 (solution page 485)......Page 926
Practice Problem 4.14 (solution page 486)......Page 932
Practice Problem 4.15 (solution page 486)......Page 933
Practice Problem 4.16 (solution page 486)......Page 935
Practice Problem 4.17 (solution page 486)......Page 937
Practice Problem 4.18 (solution page 487)......Page 939
4.3.2 SEQ Hardware Structure......Page 941
4.3.3 SEQ Timing......Page 950
4.3.4 SEQ Stage Implementations......Page 958
Fetch Stage......Page 961
Practice Problem 4.19 (solution page 487)......Page 962
Decode and Write-Back Stages......Page 963
Practice Problem 4.20 (solution page 488)......Page 965
Execute Stage......Page 966
Practice Problem 4.23 (solution page 488)......Page 968
Practice Problem 4.24 (solution page 488)......Page 969
Memory Stage......Page 970
Practice Problem 4.26 (solution page 489)......Page 971
Practice Problem 4.27 (solution page 489)......Page 972
Surveying SEQ......Page 973
4.4 General Principles of Pipelining......Page 975
4.4.1 Computational Pipelines......Page 976
4.4.2 A Detailed Look at Pipeline Operation......Page 979
Nonuniform Partitioning......Page 983
Practice Problem 4.28 (solution page 489)......Page 985
Diminishing Returns of Deep Pipelining......Page 986
4.4.4 Pipelining a System with Feedback......Page 987
4.5.1 SEQ+: Rearranging the Computation Stages......Page 992
4.5.2 Inserting Pipeline Registers......Page 995
4.5.3 Rearranging and Relabeling Signals......Page 1000
4.5.4 Next PC Prediction......Page 1003
4.5.5 Pipeline Hazards......Page 1007
Avoiding Data Hazards by Stalling......Page 1014
Avoiding Data Hazards by Forwarding......Page 1020
Load/Use Data Hazards......Page 1025
Avoiding Control Hazards......Page 1030
4.5.6 Exception Handling......Page 1035
4.5.7 PIPE Stage Implementations......Page 1040
PC Selection and Fetch Stage......Page 1042
Decode and Write-Back Stages......Page 1044
Practice Problem 4.31 (solution page 490)......Page 1046
Practice Problem 4.34 (solution page 491)......Page 1051
Execute Stage......Page 1052
Memory Stage......Page 1054
4.5.8 Pipeline Control Logic......Page 1055
Desired Handling of Special Control Cases......Page 1056
Detecting Special Control Conditions......Page 1061
Pipeline Control Mechanisms......Page 1063
Combinations of Control Conditions......Page 1066
Practice Problem 4.37 (solution page 492)......Page 1068
Practice Problem 4.38 (solution page 492)......Page 1069
Control Logic Implementation......Page 1070
Practice Problem 4.40 (solution page 493)......Page 1072
4.5.9 Performance Analysis......Page 1073
Practice Problem 4.44 (solution page 494)......Page 1081
Multicycle Instructions......Page 1082
Interfacing with the Memory System......Page 1084
4.6 Summary......Page 1087
4.6.1 Y86-64 Simulators......Page 1091
Bibliographic Notes......Page 1093
4.45......Page 1094
4.47......Page 1095
4.48......Page 1096
4.50......Page 1097
4.52......Page 1099
4.53......Page 1100
4.55......Page 1101
4.57......Page 1102
4.58......Page 1105
4.59......Page 1108
Chapter 5 Optimizing Program Performance......Page 1146
5.1 Capabilities and Limitations of Optimizing Compilers......Page 1154
Practice Problem 5.1 (solution page 573)......Page 1158
5.2 Expressing Program Performance......Page 1163
Practice Problem 5.2 (solution page 573)......Page 1167
5.3 Program Example......Page 1168
5.4 Eliminating Loop Inefficiencies......Page 1176
Practice Problem 5.3 (solution page 573)......Page 1183
5.5 Reducing Procedure Calls......Page 1185
5.6 Eliminating Unneeded Memory References......Page 1188
Practice Problem 5.4 (solution page 574)......Page 1193
5.7 Understanding Modern Processors......Page 1196
5.7.1 Overall Operation......Page 1198
5.7.2 Functional Unit Performance......Page 1207
5.7.3 An Abstract Model of Processor Operation......Page 1210
From Machine-Level Code to Data-Flow Graphs......Page 1212
Other Performance Factors......Page 1219
Practice Problem 5.5 (solution page 575)......Page 1221
Practice Problem 5.6 (solution page 575)......Page 1222
5.8 Loop Unrolling......Page 1224
Practice Problem 5.7 (solution page 575)......Page 1226
5.9.1 Multiple Accumulators......Page 1233
5.9.2 Reassociation Transformation......Page 1242
Practice Problem 5.8 (solution page 576)......Page 1250
5.10 Summary of Results for Optimizing Combining Code......Page 1255
5.11.1 Register Spilling......Page 1257
5.11.2 Branch Prediction and Misprediction Penalties......Page 1260
Do Not Be Overly Concerned about Predictable Branches......Page 1261
Write Code Suitable for Implementation with Conditional Moves......Page 1264
Practice Problem 5.9 (solution page 576)......Page 1267
5.12 Understanding Memory Performance......Page 1269
5.12.1 Load Performance......Page 1270
5.12.2 Store Performance......Page 1272
Practice Problem 5.10 (solution page 577)......Page 1280
Practice Problem 5.11 (solution page 577)......Page 1282
Practice Problem 5.12 (solution page 577)......Page 1283
5.13 Life in the Real World: Performance Improvement Techniques......Page 1285
5.14.1 Program Profiling......Page 1287
5.14.2 Using a Profiler to Guide Optimization......Page 1292
5.15 Summary......Page 1301
Bibliographic Notes......Page 1303
5.13 ♦♦......Page 1305
5.14 ♦......Page 1307
5.17 ♦♦......Page 1308
5.19 ♦♦♦......Page 1311
Chapter 6 The Memory Hierarchy......Page 1325
6.1.1 Random Access Memory......Page 1329
Static RAM......Page 1330
Dynamic RAM......Page 1331
Conventional DRAMs......Page 1332
Memory Modules......Page 1335
Practice Problem 6.1 (solution page 660)......Page 1336
Enhanced DRAMs......Page 1337
Nonvolatile Memory......Page 1339
Accessing Main Memory......Page 1341
6.1.2 Disk Storage......Page 1345
Disk Geometry......Page 1346
Disk Capacity......Page 1348
Disk Operation......Page 1350
Practice Problem 6.3 (solution page 661)......Page 1354
Logical Disk Blocks......Page 1355
Practice Problem 6.4 (solution page 661)......Page 1356
Connecting I/O Devices......Page 1357
Accessing Disks......Page 1359
6.1.3 Solid State Disks......Page 1364
Practice Problem 6.5 (solution page 662)......Page 1367
6.1.4 Storage Technology Trends......Page 1368
Practice Problem 6.6 (solution page 662)......Page 1372
6.2 Locality......Page 1374
6.2.1 Locality of References to Program Data......Page 1377
6.2.2 Locality of Instruction Fetches......Page 1381
6.2.3 Summary of Locality......Page 1382
Practice Problem 6.7 (solution page 662)......Page 1383
Practice Problem 6.8 (solution page 663)......Page 1386
6.3 The Memory Hierarchy......Page 1387
6.3.1 Caching in the Memory Hierarchy......Page 1388
Cache Hits......Page 1391
Cache Misses......Page 1392
Kinds of Cache Misses......Page 1393
Cache Management......Page 1394
6.3.2 Summary of Memory Hierarchy Concepts......Page 1396
6.4 Cache Memories......Page 1398
6.4.1 Generic Cache Memory Organization......Page 1399
Practice Problem 6.9 (solution page 663)......Page 1401
6.4.2 Direct-Mapped Caches......Page 1403
Set Selection in Direct-Mapped Caches......Page 1404
Word Selection in Direct-Mapped Caches......Page 1405
Putting It Together: A Direct-Mapped Cache in Action......Page 1406
Conflict Misses in Direct-Mapped Caches......Page 1412
Practice Problem 6.10 (solution page 663)......Page 1417
6.4.3 Set Associative Caches......Page 1418
Set Selection in Set Associative Caches......Page 1419
Line Matching and Word Selection in Set Associative Caches......Page 1420
Line Replacement on Misses in Set Associative Caches......Page 1421
6.4.4 Fully Associative Caches......Page 1422
Line Matching and Word Selection in Fully Associative Caches......Page 1423
Practice Problem 6.12 (solution page 663)......Page 1424
Practice Problem 6.13 (solution page 664)......Page 1425
Practice Problem 6.14 (solution page 664)......Page 1426
6.4.5 Issues with Writes......Page 1427
6.4.6 Anatomy of a Real Cache Hierarchy......Page 1429
6.4.7 Performance Impact of Cache Parameters......Page 1430
Impact of Cache Size......Page 1432
Impact of Associativity......Page 1433
Impact of Write Strategy......Page 1434
6.5 Writing Cache-Friendly Code......Page 1435
Practice Problem 6.17 (solution page 665)......Page 1441
Practice Problem 6.18 (solution page 666)......Page 1443
Practice Problem 6.19 (solution page 666)......Page 1445
Practice Problem 6.20 (solution page 666)......Page 1446
6.6.1 The Memory Mountain......Page 1447
Practice Problem 6.21 (solution page 666)......Page 1455
6.6.2 Rearranging Loops to Increase Spatial Locality......Page 1456
6.6.3 Exploiting Locality in Your Programs......Page 1465
6.7 Summary......Page 1467
Bibliographic Notes......Page 1469
6.23......Page 1471
6.24......Page 1472
6.25......Page 1473
6.27......Page 1474
6.29......Page 1475
6.30......Page 1477
6.31......Page 1479
6.32......Page 1480
6.34......Page 1481
6.36......Page 1483
6.37......Page 1485
6.38......Page 1487
6.39......Page 1489
6.40......Page 1490
6.41......Page 1491
6.42......Page 1492
6.44......Page 1493
6.45......Page 1494
6.46......Page 1495
Part II Running Programs on a System......Page 1512
Chapter 7 Linking......Page 1513
7.1 Compiler Drivers......Page 1520
7.2 Static Linking......Page 1523
7.3 Object Files......Page 1525
7.4 Relocatable Object Files......Page 1527
7.5 Symbols and Symbol Tables......Page 1530
Practice Problem 7.1 (solution page 717)......Page 1535
7.6 Symbol Resolution......Page 1538
7.6.1 How Linkers Resolve Duplicate Symbol Names......Page 1540
Practice Problem 7.2 (solution page 718)......Page 1548
7.6.2 Linking with Static Libraries......Page 1549
7.6.3 How Linkers Use Static Libraries to Resolve References......Page 1557
Practice Problem 7.3 (solution page 718)......Page 1560
7.7 Relocation......Page 1562
7.7.1 Relocation Entries......Page 1563
7.7.2 Relocating Symbol References......Page 1565
Relocating PC-Relative References......Page 1568
Relocating Absolute References......Page 1570
Practice Problem 7.4 (solution page 718)......Page 1573
Practice Problem 7.5 (solution page 718)......Page 1574
7.8 Executable Object Files......Page 1575
7.9 Loading Executable Object Files......Page 1579
7.10 Dynamic Linking with Shared Libraries......Page 1582
7.11 Loading and Linking Shared Libraries from Applications......Page 1587
7.12 Position-Independent Code (PIC)......Page 1593
7.13 Library Interpositioning......Page 1601
7.13.1 Compile-Time Interpositioning......Page 1602
7.13.2 Link-Time Interpositioning......Page 1603
7.13.3 Run-Time Interpositioning......Page 1607
7.14 Tools for Manipulating Object Files......Page 1613
7.15 Summary......Page 1615
Bibliographic Notes......Page 1617
7.6 ♦......Page 1618
7.8 ♦......Page 1620
7.9 ♦......Page 1622
7.10 ♦♦......Page 1623
7.12 ♦♦......Page 1624
7.13 ♦♦......Page 1625
Chapter 8 Exceptional Control Flow......Page 1631
8.1 Exceptions......Page 1637
8.1.1 Exception Handling......Page 1639
8.1.2 Classes of Exceptions......Page 1642
Interrupts......Page 1643
Traps and System Calls......Page 1645
Faults......Page 1647
8.1.3 Exceptions in Linux/x86-64 Systems......Page 1648
Linux/x86-64 Faults and Aborts......Page 1649
Linux/x86-64 System Calls......Page 1650
8.2 Processes......Page 1655
8.2.1 Logical Control Flow......Page 1656
8.2.2 Concurrent Flows......Page 1658
Practice Problem 8.1 (solution page 795)......Page 1659
8.2.3 Private Address Space......Page 1660
8.2.4 User and Kernel Modes......Page 1661
8.2.5 Context Switches......Page 1663
8.3 System Call Error Handling......Page 1667
8.4.1 Obtaining Process IDs......Page 1670
8.4.2 Creating and Terminating Processes......Page 1671
Practice Problem 8.2 (solution page 795)......Page 1678
8.4.3 Reaping Child Processes......Page 1679
Modifying the Default Behavior......Page 1681
Checking the Exit Status of a Reaped Child......Page 1682
Practice Problem 8.3 (solution page 797)......Page 1684
Examples of Using waitpid......Page 1685
Practice Problem 8.4 (solution page 797)......Page 1690
8.4.4 Putting Processes to Sleep......Page 1693
Practice Problem 8.5 (solution page 797)......Page 1694
8.4.5 Loading and Running Programs......Page 1695
Practice Problem 8.6 (solution page 797)......Page 1699
8.4.6 Using fork and execve to Run Programs......Page 1700
8.5 Signals......Page 1709
8.5.1 Signal Terminology......Page 1713
8.5.2 Sending Signals......Page 1714
Process Groups......Page 1715
Sending Signals with the /bin/kill Program......Page 1716
Sending Signals from the Keyboard......Page 1717
Sending Signals with the kill Function......Page 1718
8.5.3 Receiving Signals......Page 1721
8.5.4 Blocking and Unblocking Signals......Page 1726
Safe Signal Handling......Page 1729
Correct Signal Handling......Page 1738
Practice Problem 8.8 (solution page 799)......Page 1745
Portable Signal Handling......Page 1746
8.5.6 Synchronizing Flows to Avoid Nasty Concurrency Bugs......Page 1749
8.5.7 Explicitly Waiting for Signals......Page 1754
8.6 Nonlocal Jumps......Page 1763
8.7 Tools for Manipulating Processes......Page 1773
8.8 Summary......Page 1774
Bibliographic Notes......Page 1776
8.9 ♦......Page 1777
8.11 ♦......Page 1778
8.12 ♦......Page 1779
8.13 ♦......Page 1780
8.14 ♦......Page 1781
8.15 ♦......Page 1782
8.17 ♦......Page 1784
8.18 ♦♦......Page 1785
8.19 ♦♦......Page 1786
8.20 ♦♦......Page 1787
8.21 ♦♦......Page 1788
8.22 ♦♦♦......Page 1789
8.24 ♦♦♦......Page 1790
8.25 ♦♦♦......Page 1792
8.26 ♦♦♦♦......Page 1793
Chapter 9 Virtual Memory......Page 1804
9.1 Physical and Virtual Addressing......Page 1809
9.2 Address Spaces......Page 1812
Practice Problem 9.1 (solution page 880)......Page 1813
9.3 VM as a Tool for Caching......Page 1815
9.3.1 DRAM Cache Organization......Page 1816
9.3.2 Page Tables......Page 1817
9.3.4 Page Faults......Page 1820
9.3.5 Allocating Pages......Page 1824
9.3.6 Locality to the Rescue Again......Page 1825
9.4 VM as a Tool for Memory Management......Page 1827
9.5 VM as a Tool for Memory Protection......Page 1831
9.6 Address Translation......Page 1833
Practice Problem 9.3 (solution page 881)......Page 1838
9.6.1 Integrating Caches and VM......Page 1839
9.6.2 Speeding Up Address Translation with a TLB......Page 1840
9.6.3 Multi-Level Page Tables......Page 1843
9.6.4 Putting It Together: End-to-End Address Translation......Page 1847
Practice Problem 9.4 (solution page 881)......Page 1852
9.7 Case Study: The Intel Core i7/Linux Memory System......Page 1855
9.7.1 Core i7 Address Translation......Page 1858
9.7.2 Linux Virtual Memory System......Page 1862
Linux Virtual Memory Areas......Page 1866
Linux Page Fault Exception Handling......Page 1869
9.8 Memory Mapping......Page 1871
9.8.1 Shared Objects Revisited......Page 1872
9.8.2 The fork Function Revisited......Page 1877
9.8.3 The execve Function Revisited......Page 1878
9.8.4 User-Level Memory Mapping with the mmap Function......Page 1880
Practice Problem 9.5 (solution page 882)......Page 1883
9.9 Dynamic Memory Allocation......Page 1884
9.9.1 The malloc and free Functions......Page 1886
9.9.2 Why Dynamic Memory Allocation?......Page 1891
9.9.3 Allocator Requirements and Goals......Page 1893
9.9.4 Fragmentation......Page 1897
9.9.5 Implementation Issues......Page 1899
9.9.6 Implicit Free Lists......Page 1900
Practice Problem 9.6 (solution page 883)......Page 1903
9.9.7 Placing Allocated Blocks......Page 1904
9.9.8 Splitting Free Blocks......Page 1905
9.9.9 Getting Additional Heap Memory......Page 1906
9.9.10 Coalescing Free Blocks......Page 1907
9.9.11 Coalescing with Boundary Tags......Page 1908
Practice Problem 9.7 (solution page 883)......Page 1911
9.9.12 Putting It Together: Implementing a Simple Allocator......Page 1913
General Allocator Design......Page 1914
Basic Constants and Macros for Manipulating the Free List......Page 1918
Creating the Initial Free List......Page 1921
Allocating Blocks......Page 1925
9.9.13 Explicit Free Lists......Page 1930
9.9.14 Segregated Free Lists......Page 1933
Simple Segregated Storage......Page 1934
Practice Problem 9.10 (solution page 885)......Page 1935
Segregated Fits......Page 1936
Buddy Systems......Page 1937
9.10 Garbage Collection......Page 1939
9.10.1 Garbage Collector Basics......Page 1940
9.10.2 Mark&Sweep Garbage Collectors......Page 1943
9.10.3 Conservative Mark&Sweep for C Programs......Page 1947
9.11.1 Dereferencing Bad Pointers......Page 1949
9.11.2 Reading Uninitialized Memory......Page 1951
9.11.3 Allowing Stack Buffer Overflows......Page 1952
9.11.4 Assuming That Pointers and the Objects They Point to Are the Same Size......Page 1953
9.11.5 Making Off-by-One Errors......Page 1954
9.11.6 Referencing a Pointer Instead of the Object It Points To......Page 1955
9.11.7 Misunderstanding Pointer Arithmetic......Page 1956
9.11.8 Referencing Nonexistent Variables......Page 1957
9.11.9 Referencing Data in Free Heap Blocks......Page 1958
9.11.10 Introducing Memory Leaks......Page 1959
9.12 Summary......Page 1961
Bibliographic Notes......Page 1963
9.11......Page 1964
9.12......Page 1966
9.13......Page 1967
9.14......Page 1968
9.16......Page 1969
9.18......Page 1970
9.19......Page 1971
9.20......Page 1972
Part III Interaction and Communication between Programs......Page 1984
Chapter 10 System-Level I/O......Page 1985
10.1 Unix I/O......Page 1988
10.2 Files......Page 1990
10.3 Opening and Closing Files......Page 1993
Practice Problem 10.1 (solution page 915)......Page 1997
10.4 Reading and Writing Files......Page 1998
10.5 Robust Reading and Writing with the Rio Package......Page 2002
10.5.1 Rio Unbuffered Input and Output Functions......Page 2003
10.5.2 Rio Buffered Input Functions......Page 2004
10.6 Reading File Metadata......Page 2015
10.7 Reading Directory Contents......Page 2019
10.8 Sharing Files......Page 2022
Practice Problem 10.2 (solution page 915)......Page 2025
Practice Problem 10.3 (solution page 915)......Page 2026
10.9 I/O Redirection......Page 2028
Practice Problem 10.4 (solution page 915)......Page 2029
Practice Problem 10.5 (solution page 916)......Page 2030
10.10 Standard I/O......Page 2032
10.11 Putting It Together: Which I/O Functions Should I Use?......Page 2034
10.12 Summary......Page 2039
Bibliographic Notes......Page 2040
10.6......Page 2041
10.9......Page 2042
10.10......Page 2043
Chapter 11 Network Programming......Page 2047
11.1 The Client-Server Programming Model......Page 2049
11.2 Networks......Page 2051
11.3 The Global IP Internet......Page 2060
11.3.1 IP Addresses......Page 2062
Practice Problem 11.1 (solution page 966)......Page 2065
Practice Problem 11.3 (solution page 967)......Page 2066
11.3.2 Internet Domain Names......Page 2067
11.3.3 Internet Connections......Page 2071
11.4 The Sockets Interface......Page 2077
11.4.1 Socket Address Structures......Page 2079
11.4.2 The socket Function......Page 2080
11.4.3 The connect Function......Page 2081
11.4.4 The bind Function......Page 2082
11.4.5 The listen Function......Page 2083
11.4.6 The accept Function......Page 2084
11.4.7 Host and Service Conversion......Page 2086
The getaddrinfo Function......Page 2087
The getnameinfo Function......Page 2092
11.4.8 Helper Functions for the Sockets Interface......Page 2097
The open_clientfd Function......Page 2098
The open_listenfd Function......Page 2101
11.4.9 Example Echo Client and Server......Page 2102
11.5.1 Web Basics......Page 2110
11.5.2 Web Content......Page 2112
11.5.3 HTTP Transactions......Page 2115
HTTP Requests......Page 2118
HTTP Responses......Page 2119
11.5.4 Serving Dynamic Content......Page 2121
How Does the Server Pass Arguments to the Child?......Page 2122
Where Does the Child Send Its Output?......Page 2123
Practice Problem 11.5 (solution page 969)......Page 2124
11.6 Putting It Together: The Tiny Web Server......Page 2128
11.7 Summary......Page 2144
Bibliographic Notes......Page 2146
11.8......Page 2148
11.11......Page 2149
11.13......Page 2150
Chapter 12 Concurrent Programming......Page 2157
12.1 Concurrent Programming with Processes......Page 2162
12.1.1 A Concurrent Server Based on Processes......Page 2165
Practice Problem 12.1 (solution page 1036)......Page 2166
Practice Problem 12.2 (solution page 1036)......Page 2167
12.2 Concurrent Programming with I/O Multiplexing......Page 2170
Practice Problem 12.3 (solution page 1036)......Page 2176
12.2.1 A Concurrent Event-Driven Server Based on I/O Multiplexing......Page 2177
Practice Problem 12.4 (solution page 1036)......Page 2186
12.2.2 Pros and Cons of I/O Multiplexing......Page 2187
12.3 Concurrent Programming with Threads......Page 2189
12.3.1 Thread Execution Model......Page 2190
12.3.2 Posix Threads......Page 2191
12.3.3 Creating Threads......Page 2194
12.3.4 Terminating Threads......Page 2195
12.3.5 Reaping Terminated Threads......Page 2196
12.3.6 Detaching Threads......Page 2197
12.3.8 A Concurrent Server Based on Threads......Page 2199
Practice Problem 12.5 (solution page 1036)......Page 2203
12.4 Shared Variables in Threaded Programs......Page 2204
12.4.1 Threads Memory Model......Page 2206
12.4.2 Mapping Variables to Memory......Page 2207
Practice Problem 12.6 (solution page 1036)......Page 2209
12.5 Synchronizing Threads with Semaphores......Page 2211
Practice Problem 12.7 (solution page 1037)......Page 2217
12.5.1 Progress Graphs......Page 2218
12.5.2 Semaphores......Page 2223
12.5.3 Using Semaphores for Mutual Exclusion......Page 2225
12.5.4 Using Semaphores to Schedule Shared Resources......Page 2229
Producer-Consumer Problem......Page 2230
Readers-Writers Problem......Page 2233
12.5.5 Putting It Together: A Concurrent Server Based on Prethreading......Page 2238
12.6 Using Threads for Parallelism......Page 2248
12.7.1 Thread Safety......Page 2262
12.7.2 Reentrancy......Page 2268
12.7.3 Using Existing Library Functions in Threaded Programs......Page 2269
12.7.4 Races......Page 2271
Practice Problem 12.13 (solution page 1039)......Page 2274
Practice Problem 12.14 (solution page 1039)......Page 2275
12.7.5 Deadlocks......Page 2276
Practice Problem 12.15 (solution page 1039)......Page 2280
12.8 Summary......Page 2281
Bibliographic Notes......Page 2283
12.17 ♦......Page 2284
12.18......Page 2285
12.21 ♦♦♦♦......Page 2286
12.24 ♦......Page 2287
12.27 ♦♦......Page 2288
12.28 ♦......Page 2289
12.29 ♦......Page 2290
12.31 ♦♦♦......Page 2291
12.35 ♦♦♦......Page 2293
12.38 ♦♦♦♦......Page 2294
12.39 ♦♦♦♦......Page 2295
Appendix A Error Handling......Page 2308
A.1 Error Handling in Unix Systems......Page 2310
A.2 Error-Handling Wrappers......Page 2314
References......Page 2319
Index......Page 2337