A PROGRAMMER'S PERSPECTIVE This book is for programmers who want to write faster and more reliable programs. By learning how programs are mapped onto the system and executed, readers will better understand why programs behave the way they do and how inefficiencies arise. Computer systems are viewed broadly, comprising processor and memory hardware, compiler, operating system, and networking environment. With its programmer's perspective, readers can clearly see how learning about the inner workings of computer systems will help their further development as computer scientists and engineers. It also helps prepare them for further study in computer architecture, operating systems, compilers, and networking. Topics include: data representations, machine-level representations of C programs, processor architecture, program optimization, memory hierarchy, linking, exceptional control flow, virtual memory and memory management, system-level 1/O, network programming, and concurrent programming. The coverage,focuses on how these areas affect application and system programmers. For example, when covering data representations, it considers how the finite representations used to represent numbers can approximate integer and real numbers, but with limitations that must be understood by programmers. When covering caching, it discusses how the ordering of loop indices in matrix code can affect program performance. When covering networking, it describes how a concurrent server can efficiently handle requests from multiple clients. The book is based on Intel-compatible (IA32) machines executing C programs on Unix or related operating systems such as Linux. Some familiarity with C or C++is assumed, although hints are included to help readers making the transition from Java to C. A complete set of resources, including labs and assignments, lecture notes, and code examples are available via the book's Web sit
Table of Contents
(NOTE: Each chapter concludes with Summary.)
1. A Tour of Computer Systems.
2. Representing and Manipulating Information.
Information Is Bits + Context. Programs Are Translated by Other Programs into Different Forms. It Pays to Understand How Compilation Systems Work. Processors Read and Interpret Instructions Stored in Memory. Caches Matter. Storage Devices Form a Hierarchy. The Operating System Manages the Hardware. Systems Communicate with Other Systems Using Networks. The Next Step.
I. PROGRAM STRUCTURE AND EXECUTION.
Information Storage. Integer Representations. Integer Arithmetic. Floating Point. 3. Machine-Level Representation of Programs.
A Historical Perspective. Program Encodings. Data Formats. Accessing Information. Arithmetic and Logical Operations. Control. Procedures. Array Allocation and Access. Heterogeneous Data Structures. Alignment. Putting It Together: Understanding Pointers. Life in the Real World: Using the GDB Debugger. Out-of-Bounds Memory References and Buffer Overflow. Floating-Point Code. Embedding Assembly Code in C Programs. 4. Processor Architecture.
The Y86 Instruction Set Architecture. Overview of Logic Design and the Hardware Control Language. A Sequential Implementation. General Principles of Pipelining. Pipelined Implementations. 5. Optimizing Program Performance.
Capabilities and Limitations of Optimizing Compilers. Expressing Program Performance. Program Example. Eliminating Loop Inefficiencies. Reducing Procedure Calls. Eliminating Unneeded Memory References. Understanding Modern Processors. Reducing Loop Overhead. Converting to Pointer Code. Enhancing Parallelism. Putting It Together: Summary of Results for Optimizing Combining Code. Branch Prediction and Misprediction Penalties. Understanding Memory Performance. Life in the Real World: Performance Improvement Techniques. Identifying and Eliminating Performance Bottlenecks. 6. The Memory Hierarchy.
Storage Technologies. Locality. The Memory Hierarchy. Cache Memories. Writing Cache-Friendly Code. Putting It Together: Exploiting Locality in Your Programs.
II. RUNNING PROGRAMS ON A SYSTEM.
Compiler Drivers. Static Linking. Object Files. Relocatable Object Files. Symbols and Symbol Tables. Symbol Resolution. Relocation. Executable Object Files. Loading Executable Object Files. Dynamic Linking with Shared Libraries. Loading and Linking Shared Libraries from Applications. Position-Independent Code (PIC). Tools for Manipulating Object Files. 8. Exceptional Control Flow.
Exceptions. Processes. System Calls and Error Handling. Process Control. Signals. Nonlocal Jumps. Tools for Manipulating Processes. 9. Measuring Program Execution Time.
The Flow of Time on a Computer Systems. Measuring Time by Interval Counting. Cycle Counters. Measuring Program Execution Time with Cycle Counters. Time-of-Day Measurements. Putting It Together: An Experimental Protocol. Looking into the Future. Life in the Real World: An Implementation of the K-Best Measurement Scheme. Lessons Learned. 10. Virtual Memory.
11. System-Level I/O.
Physical and Virtual Addressing. Address Spaces. VM as a Tool for Caching. VM as a Tool for Memory Management. VM as a Tool for Memory Protection. Address Translation. Case Study: The Pentium/Linux Memory System. Memory Mapping. Dynamic Memory Allocation. Garbage Collection. Common Memory-Related Bugs in C Programs. Recapping Some Key Ideas about Virtual Memory.
III. INTERACTION AND COMMUNICATION BETWEEN PROGRAMS.
Unix I/O. Opening and Closing Files. Reading and Writing Files. Robust Reading and Writing with the R10 Package. Reading File Metadata. Sharing Files. I/O Redirection. Standard I/O. Putting It Together: Which I/O Functions Should I Use? 12. Network Programming.
The Client-Server Programming Model. Networks. The Global IP Internet. The Sockets Interface. Web Servers. Putting It Together: The TINY Web Server. 13. Concurrent Programming.
Concurrent Programming with Processes. Concurrent Programming with I/O Multiplexing. Concurrent Programming with Threads. Shared Variables in Threaded Programs. Synchronizing Threads with Semaphores. Putting It Together: A Concurrent Server Based on Pre-Threading. Other Concurrency Issues. Appendix A. HCL Descriptions of Processor Control Logic.
HCL Reference Manual. SEQ. SEQ+. PIPE. Appendix B. Error Handling.
Error Handling in Unix Systems. Error-Handling Wrappers. The csapp .h Header File. The csapp .c Source File.
This book,Computer Systems: A Programmer's Perspective(CS:APP), is for programmers who want to improve their skills by learning what is going on "under the hood" of a computer system. Our aim is to explain the enduring concepts underlying all computer systems, and to show you the concrete ways that these ideas affect the correctness, performance, and utility of your application programs. Unlike other systems books, which are written primarily for system builders, this book is written for programmers, from a programmer's perspective. If you study and learn the concepts in this book, you will be on your way to becoming the rare "power programmer" who knows how things work and how to fix them when they break. You will also be prepared to study specific systems topics such as compilers, computer architecture, operating systems, embedded systems, and networking. Assumptions About the Reader's Background The examples in the book are based on Intel-compatible processors (called "IA32" by Intel and "x86" colloquially) running C programs on Unix or Unix-like (such as Linux) operating systems. (To simplify our presentation, we will use the term "Unix" as an umbrella term for systems like Solaris and Linux.) 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 changing directories. If your computer runs Microsoft Windows, you have two choices. First, you can get a copy of Linux (seewww.linux.orgorwww.redhat.com) and install it as a "dual boot" option, so that your machine can run either operating system. Alternatively, by installing a copy of the Cygwin tools (www.cygwin.com), you can have up a Unix-like shell under Windows and have an environment very close to that provided by Linux. Not all features of Linux are available under Cygwin, however. 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 Brian Kernighan and Dennis Ritchie 40. Regardless of your programming background, consider K&R an essential part of your personal systems library. Several of the early chapters in the book explore the interactions between C programs and their machine-language counterparts. The machine language examples were all generated by the GNU Gcc compiler running on an Intel IA32 processor. 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 it can be done so actively. Whenever you learn some new thing, you can try it out right away and see the result first hand. In fact, we believe that the only way to learn systems is todosystems, 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 morepractice problemsthat you should work immediately to test your understanding. Solutions to the practice problems are at the end of each chapter (look for the blue edge). As you read, try to solve each problem on your own, and then check the solution to make sure you are on the right track. Each chapter is followed by a set of homework problems of varying difficulty. Your instructor has the solutions to thehomework problemsin an instructor's manual. For each homework problem, we show a ra