Computer Systems: A Programmer's Perspective (3rd Edition)

This book (CS:APP3e) is the third edition of a book that stems from the introductory computer systems course we developed at Carnegie Mellon University, starting in the Fall of 1998, called "Introduction to Computer Systems" (ICS). The presentation is based on the following principles, which aim to help the students become better programmers and to help prepare them for upper-level systems courses: • Students should be introduced to computer systems from the perspective of a programmer, rather from the more traditional perspective of a system implementer. What does this mean? • Students should get a view of the complete system, comprising the hardware, operating system, compiler, and network. • Students learn best by developing and evaluating real programs that run on real machines. We cover data representations, machine level representations of C programs, processor architecture, program optimizations, the memory hierarchy, linking, exceptional control flow (exceptions, interrupts, processes, and Unix signals), virtual memory and memory management, system-level I/O, basic network programming, and concurrent programming. These concepts are supported by series of fun and hands-on lab assignments. See the manuscript Preface for more details. Front Cover 1 Preface 2 Table of Contents 6 Chapter 1: A Tour of Computer Systems 36 1.1: Information Is Bits + Context 38 1.2: Programs Are Translated by Other Programs into Different Forms 39 1.3: It Pays to Understand How Compilation Systems Work 41 1.4: Processors. Read and Interpret Instructions Stored in Memory 42 1.5: Caches Matter 46 1.6 Storage Devices Form a Hierarchy 49 1.7: The Operating System Manages the Hardware 49 1.8: Systems Communicate with Other Systems Using Networks 54 1.9: Important Themes 57 1.10: Summary 62 Bibliographic Notes 63 Solutions to Practice Problems 63 Part I: Program Structure and Execution 64 Chapter 2: Representing and Manipulating Information 66 2.1: lnformation Storage 69 2.2: Integer Representations 94 2.3: Integer Arithmetic 119 2.4: Floating Point 143 2.5: Summary 161 Bibliographic Notes 162 Homework Problems 163 Solutions to Practice Problems 178 Chapter 3: Machine-Level Representation of Programs 198 3.1: A Historical Perspective 201 3.2: Program Encodings 204 3.3: Data Formats 212 3.4: Accessing Information 214 3.5: Arithmetic and Logical Operations 226 3.6: Control 235 3.7: Procedures 273 3.8: Array Allocation and Access 290 3.9: Heterogeneous Data Structures 300 3.10: Combining Control and Data in Machine-Level Programs 311 3.11: F!oating-Point Code 328 3.12: Summary 344 Bibliographic Notes 345 Homework Problems 346 Solutions to Practice Problems 360 Chapter 4: Processor Architecture 386 4.1: The Y86-64 Instruction Set Architecture 390 4.2: Logic Design and the Hardware Control Language HCL 407 4.3: Sequential Y86-64 Implementations 419 4.4: General Principles of Pipelining 447 4.5: Pipelined Y86-64 Implementations 456 4.6: Summary 505 Bibliographic Notes 508 Homework Problems 508 Solutions to Practice Problems 515 Chapter 5: Optimizing Program Performance 530 5.1: Capabilities and Limitations of Optimizing Compilers 533 5.2: Expressing Program Performance 537 5.3: Program Example 539 5.4: Eliminating Loop Inefficiencies 543 5.5: Reducing Procedure Calls 547 5.6: Eliminating Unneeded Memory References 549 5.7: Understanding Modern Processors 552 5.8: Loop Unrolling 566 5.9: Enhancing Parallelism 571 5.10: Summary of Results for Optimizing Combining Code 582 5.11: Some Limiting Factors 583 5.12: Understanding Memory Performance 588 5.13: Life in the Real World: Performance Improvement Techniques 596 5.14: Identifying and Eliminating Performance Bottlenecks 597 5.15: Summary 603 Bibliographic Notes 604 Homework Problems 605 Solutions to Practice Problems 608 Chapter 6: The Memory Hierarchy 614 6.1: Storage Technologies 616 6.2: Locality 639 6.3: The Memory Hierarchy 644 6.4: Cache Memories 649 6.5: Writing Cache-Friendly Code 668 6.6: Putting It Together: The Impact of Caches on Program Performance 674 6.7: Summary 683 Bibliographic Notes 683 Homework Problems 684 Solutions to Practice Problems 695 Part II: Runinng Programs on a System 702 Chapter 7: Linking 704 7.1: Compiler Drivers 706 7.2: Static Linking 707 7.3: Object Files 708 7.4: Relocatable Object Files 709 7.5: Symbols and Symbol Tables 710 7.6: Symbol Resolution 714 7.7: Relocation 724 7.8: Executable Object Files 730 7.9: Loading Executable Object Files 732 7.10: Dynamic Linking with Shared Libraries 733 7.11: Loading and Linking Shared Libraries from Applications 736 7.12: Position-Independent Code (PIC) 739 7.13: Library lnterpositioning 742 7.14: Tools for Manipulating Object Files 748 7.15: Summary 748 Bibliographic Notes 749 Homework Problems 749 Chapter 8: Exceptional Control Flow 756 8.1: Exceptions 758 8.2: Processes 767 8.3: System Call Error Handling 772 8.4: Process Control 773 8.5: Signals 791 8.6: Nonlocal Jumps 816 8.7: Tools for Manipulating Processes 821 8.8: Summary 822 Bibliographic Notes 822 Homework Problems 823 Solutions to Practice Problems 830 Chapter 9: Virtual Memory 836 9.1: Physical and Virtual Addressing 838 9.2: Address Spaces 839 9.3: VM as a Tool for Caching 840 9.4: VM as a Tool for Memory Management 846 9.5: VM as a Tool for Memory Protection 847 9.6: Address Translation 848 9.7: Case Study: The Intel Core i7/Linux Memory System 860 9.8: Memory Mapping 868 9.9: Dynamic Memory Allocation 874 9.10: Garbage Collection 900 9.11: Common Memory-Related Bugs in C Programs 905 9.12: Summary 910 Bibliographic Notes 911 Homework Problems 911 Solutions to Practice Problems 915 Part III: Interaction and Communication between Programs 922 Chapter 10: System-Level I/O 924 10.1: Unix I/O 925 10.2: Files 926 10.3: Opening and Closing Files 928 10.4: Reading and Writing Files 930 10.5: Robust Reading and Writing with the RIO Package 932 10.6: Reading File Metadata 938 10.7: Reading Directory Contents 940 10.8: Sharing Files 941 10.9: I/O Redirection 944 10.10: Standard I/O 946 10.11: Putting It Together: Which I/O Functions Should I Use? 946 10.12: Summary 948 Bibliographic Notes 949 Homework Problems 949 Solutions to Practice Problems 950 Chapter 11: Network Programming 952 11.1: The Client-Server Programming Model 953 11.2: Networks 954 11.3: The Global IP Internet 959 11.4: The Sockets Interface 967 11.5: Web Servers 983 11.6: Putting It Together: The TINY Web Server 991 11.7: Summary 999 Bibliographic Notes 1000 Homework Problems 1000 Solutions to Practice Problems 1001 Chapter 12: Concurrent Programming 1006 12.1: Concurrent Programming with Processes 1008 12.2: Concurrent Programming with I/O Multiplexing 1012 12.3: Concurrent Programming with Threads 1020 12.4: Shared Variables in Threaded Programs 1027 12.5: Synchronizing Threads with Semaphores 1030 12.6: Using Threads for Parallelism 1048 12.7: Other Concurrency Issues 1055 12.8: Summary 1065 Bibliographic Notes 1065 Homework Problems 1066 Solutions to Practice Problems 1071 Appendix A: Error Handling 1076 A.1: Error Handling in Unix Systems 1077 A.2: Error-Handling Wrappers 1078 References 1082 Index 1088 Back Cover 1120 CS:APP 3e with scanned main text from the Chinese adaptation. Details and updates available at (in English and Chinese): https://forum.freemdict.com/t/topic/11216 Uploader's note: There are a few versions of electronic copies of the third edition available so far on the internet: - An EPUB file, likely scraped from somewhere similar to Pearson eText; - Some PDF file converted from the aforementioned EPUB file, the pages of which has no resemblance to the print copy; - A truePDF of the Global Edition, which the original authors complained about its modifications in exercises and problems in the online errata: https://csapp.cs.cmu.edu/3e/errata.html ; - A PDF, with the size of around 35 megabytes, of scanned, monochrome page images, with color front and back cover. The uploader made and uploaded this version to provide a reading experience similar to the original edition published in Norht America, with some tricks and tools to put several parts together. This file combines the color covers as well as references and index pages from the 35MB PDF file, the front matter (preface) PDF pages from CS:APP website, and main text from the book's adaptation in China. About the Chinese adaptation: Since book publishing in China are (nominally) restricted to those of the public sector, such foreign books are either sold directly or through importers, or as in this case, a domestic publisher obtains an authorization for an adaptation. The Chinese adaptation of CS:APP 3e, published by China Machine Press 机械工业出版社 in 2017, lacks certain sections of the original book, as what Pearson does in recent years, including in this case the English preface (replaced by a Chinese translation), list of references and index. But the main text remained mostly identical to the original North America edition. Some other adaptations or reprints of adaptations (such as a reprint of Weiss' Data Structure and Algorithms Analysis in C, an earlier adaptation published 2010 and a reprint in 2019) of Pearson textbooks in recent years, including those by China Machine Press and the Publishing House of Electronics Industory 电子工业出版社, among others, share similar issues. Some even redacted the original table of contents and a Chinese translation was put forward instead. About the source of the scanned main text: There is something called Chao Xing 超星 in China, which relies on libraries of colleges and public insitutions for book copies, and then scans the whole book for a digitized copy, many of which are for internal, proprietary use among those of the print copy providers. Some of these books are available online either within a group of higher education and research institutions or through access provided by public libraries. But such scanned data have had massive leaks in the past few years and in various forms, which enabled some third-party vendors to profit from the leaked database, by a single book (usually in the name of 代找, 'find (the scanned copy) on one's behalf') or in bulk. Some even provide access to a even larger collection of past leaks, known as 读秀 (Du Xiu) 2.0, 3.0, 4.0, etc. Such scanned copies have an SSID (SS means presumably 'super star', 超星) number, and the corresponding SSID for the adaptation used in this copy is 14679086. More details on the history as well as tools used to make this file can be found at cnblogs.com/stronghorse (in Chinese) or download the executables of the English edition at http://www.mediafire.com/folder/f0z2hexqdnr9a/Software . A brief description of making this copy: A few tools were used to implement the tricks to resemble the original book, including: - Extracting, renaming and reorganizing raw scanned image files. - Find the margins by inspecting and cropping the preface PDF. - Cut out the content, put it in a frame with the margins and other image processing using ComicEnhancerPro available from the aforementioned links to align the pages, in an attempt to smoothen the reading experience when switching between pages of different sources. - Make bookmarks of the covers and body text with `bookcontents.dat` using PdgCntEditor. - Combine and perform OCR of the processed front and back cover, the main text, references and index images using Pdg2Pic (no English version available). - Insert front matter PDF pages between the covers and the body text. - Edit the bookmarks of the combined PDF file with PdgCntEditor. \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* For courses in Computer Science and Programming Computer systems: A Programmer’s Perspective explains the underlying elements common among all computer systems and how they affect general application performance. Written from the programmer’s perspective, this book strives to teach readers how understanding basic elements of computer systems and executing real practice can lead them to create better programs. Spanning across computer science themes such as hardware architecture, the operating system, and systems software, the Third Edition serves as a comprehensive introduction to programming. This book strives to create programmers who understand all elements of computer systems and will be able to engage in any application of the field--from fixing faulty software, to writing more capable programs, to avoiding common flaws. It lays the groundwork for readers to delve into more intensive topics such as computer architecture, embedded systems, and cybersecurity. This book focuses on systems that execute an x86-64 machine code, and recommends that programmers have access to a Linux system for this course. Programmers should have basic familiarity with C or C++. Computer systems: A Programmer’s Perspective explains the underlying elements common among all computer systems and how they affect general application performance. Written from the programmer’s perspective, this book strives to teach students how understanding basic elements of computer systems and executing real practice can lead them to create better programs.--Publisher's website. G1. A Tour of Computer Systems -- Part I. Program Structure and Execution : -- 2. Representing and Manipulating Information -- 3. Machine-Level Representation of Programs -- 4. Processor Architecture -- 5. Optimizing Program Performance -- 6. The Memory Hierarchy -- Part II. Running Programs on a System : -- 7. Linking -- 8. Exceptional Control Flow -- 9. Virtual Memory -- Part III. Interaction and Communication Between Programs : -- 10. System-Level I/O -- 11. Network Programming -- 12. Concurrent Programming -- Appendix. Error Handling -- References -- Index. Randal E. Bryant, Carnegie Mellon University, David R. O'Hallaron, Carnegie Mellon. University. Includes bibliographical references and index.