This books introduces computer systems in a broad way, including operating system, architecture, compiler, network and more. It is a good reference for system programmers to improve their understanding on computer systems and improve programming skills.
Chapter 1. Introduction
- Compilation
- Processors Read and Interpret Instructions Stored in Memory
Hardware Organization of a System.
- Cache
- cache hierarchy (registers, on-chip L1 cache, off-chip L2 cache, memory, local disk, remote storage)
- OS: process, thread, virtual memory, files
- Inter system communication by network.
Part I Program Structure and Execution
Chapter 2 Representing and Manipulating Information
Chapter 3 Machine-Level Representation of C Programs
Chapter 4 Processor Architecture
Chapter 5 Optimizing Program Performance
5.1 Capabilities and Limitations of Optimizing Compilers
5.2 Expressing Program Performance
5.3 Program Example
5.4 Eliminating Loop Inefficiencies
5.5 Reducing Procedure Calls
5.6 Eliminating Unneeded Memory References
5.7 Understanding Modern Processors
5.7.1 Overall Operation
5.7.2 Functional Unit Performance
5.7.3 A Closer Look at Processor Operation
- Translating Instructions into Operations
- Processing of Operations by the Execution Unit
- Scheduling of Operations with Unlimited Resources
- Scheduling of Operations with Resource Constraints
5.8 Reducing Loop Overhead
5.9 Converting to Pointer Code
5.10 Enhancing Parallelism
5.10.1 Loop Splitting
5.10.2 Register Spilling
5.10.3 Limits to Parallelism
5.11 Putting it Together: Summary of Results for Optimizing Combining Code
5.11.1 Floating-Point Performance Anomaly
5.11.2 Changing Platforms
5.12 Branch Prediction and Misprediction Penalties
5.13 Understanding Memory Performance
5.13.1 Load Latency
5.13.2 Store Latency
5.14 Life in the Real World: Performance Improvement Techniques
5.15 Identifying and Eliminating Performance Bottlenecks
5.15.1 Program Profiling
5.15.2 Using a Profiler to Guide Optimization
5.15.3 Amdahl’s Law
5.16 Summary
Chapter 6 The Memory Hierarchy
- A memory system is a hierarchy of storage devices with different capacities, costs, and access times.
- SRAM, DRAM, disk.
- Storage technologies
- Random-access memory
- SRAM - bistable memory cell.
- DRAM - capacitors.
- Nonvolatile memory: ROM, PROM, EPROM, EEPROM.
- Accessing main memory.
- Disk storage
- geometry, capacity, operation (seek time, rotational latency, transfer time),
logical disk blocks, accessing disks
- Storage technology trends.
- price/performance trade-off
- Locality: temporal/spatial locality.
- Locality of references to program data.
- Locality of Instruction Fetches.
- Summary
- The memory hierarchy
+ Different storage technologies have widely different access times.
+ Well-written programs tend to exhibit good locality.
- Caching in the Memory Hierarchy
- Cache hits
- Cache misses
- Cache Management
- Summary of Memory Hierarchy Concepts
- Exploiting temporal/spatial locality
- Cache Memories
- CPU registers, L1 cache, L2 cache, main DRAM memory, and disk storage
- Writing Cache-friendly Code
+ Make the common case go fast.
+ Minimize the number of cache misses in each inner loop.
- Putting it Together: The Impact of Caches on Program Performance
- The Memory Mountain
- Rearranging Loops to Increase Spatial Locality
- Using Blocking to Increase Temporal Locality
- Summary
Part II Running Programs on a System
Chapter 7 Linking
Chapter 8 Exceptional Control Flow
Chapter 9 Measuring Program Execution Time
Chapter 10 Virtual Memory
10.1 Physical and Virtual Addressing
10.2 Address Spaces
10.3 VM as a Tool for Caching
+ Set of virtual pages: Unallocated/Cached/Uncached
10.3.1 DRAM Cache Organization
10.3.2 Page Tables
10.3.3 Page Hits
10.3.4 Page Faults
10.3.5 Allocating Pages
10.3.6 Locality to the Rescue Again
10.4 VM as a Tool for Memory Management
10.4.1 Simplifying Linking
10.4.2 Simplifying Sharing
10.4.3 Simplifying Memory Allocation
10.4.4 Simplifying Loading
10.5 VM as a Tool for Memory Protection
10.6 Address Translation
10.6.1 Integrating Caches and VM
10.6.2 Speeding up Address Translation with a TLB
10.6.3 Multi-level Page Tables
10.6.4 Putting it Together: End-to-end Address Translation
10.7 Case Study: The Pentium/Linux Memory System
10.8 Memory Mapping
10.8.1 Shared Objects Revisited
10.8.2 The fork Function Revisited
10.8.3 The execve Function Revisited
10.8.4 User-level Memory Mapping with the mmap Function
10.9 Dynamic Memory Allocation
10.9.1 The malloc and free Functions
10.9.2 Why Dynamic Memory Allocation?
10.9.3 Allocator Requirements and Goals
- Requirements:
- Handling arbitrary request sequences
- Making immediate responses to requests
- Using only the heap.
- Aligning blocks (alignment requirement).
- Not modifying allocated blocks.
- Goals:
- Goal 1: Maximizing throughput.
- Goal 2: Maximizing memory utilization.
10.9.4 Fragmentation
- internal fragmentation:
occurs when an allocated block is larger than the payload.
e.g. to satisfy memory alignment.
- external fragmentation:
there is enough aggregate free memory to satisfy an
allocate request, but no single free block is large enough
- External fragmentation is much more difficult to quantify than internal
fragmentation
10.9.5 Implementation Issues
10.9.6 Implicit Free Lists
10.9.7 Placing Allocated Blocks
10.9.8 Splitting Free Blocks
10.9.9 Getting Additional Heap Memory
10.9.10 Coalescing Free Blocks
10.9.11 Coalescing with Boundary Tags
10.9.12 Putting it Together: Implementing a Simple Allocator
10.9.13 Explicit Free Lists
10.9.14 Segregated Free Lists
10.10 Garbage Collection
10.10.1 Garbage Collector Basics
- A garbage collector views memory as a directed reachability graph.
- The nodes of the graph are partitioned into 1) root nodes and 2) heap nodes.
10.10.2 Mark&Sweep Garbage Collectors
10.10.3 Conservative Mark&Sweep for C Programs
10.11 Common Memory-related Bugs in C Programs
10.11.1 Dereferencing Bad Pointers
10.11.2 Reading Uninitialized Memory
10.11.3 Allowing Stack Buffer Overflows
10.11.4 Assuming that Pointers and the Objects they Point to Are the Same Size
10.11.5 Making Off-by-one Errors
10.11.6 Referencing a Pointer Instead of the Object it Points to
10.11.7 Misunderstanding Pointer Arithmetic
10.11.8 Referencing Non-existent Variables
10.11.9 Referencing Data in Free Heap Blocks
10.11.10 Introducing Memory Leaks
10.12 Summary
Part III Interaction and Communication Between Programs
Chapter 11 Concurrent Programming with Threads
- A thread is a unit of execution, associated with a process, with its own
thread ID, stack, stack pointer, program counter, condition codes, and
general-purpose registers.
11.1 Basic Thread Concepts
- process context: 1) program context, 2) kernel context.
11.2 Thread Control
- Pthreads defines about 60 functions
11.2.1 Creating Threads
11.2.2 Terminating Threads
11.2.3 Reaping Terminated Threads
11.2.4 Detaching Threads
11.3 Shared Variables in Threaded Programs
11.3.1 Threads Memory Model
11.3.2 Mapping Variables to Memory
11.3.3 Shared Variables
11.4 Synchronizing Threads with Semaphores
11.4.1 Sequential Consistency
11.4.2 Progress Graphs
11.4.3 Protecting Shared Variables with Semaphores
11.4.4 Posix Semaphores
11.4.5 SignalingWith Semaphores
11.5 Synchronizing Threads with Mutex and Condition Variables
11.5.1 Mutex Variables
11.5.2 Condition Variables
11.5.3 Barrier Synchronization
11.5.4 Timeout Waiting
11.6 Thread-safe and Reentrant Functions
- A function is thread-safe if and only if it will always produce correct results
when called repeatedly within multiple concurrent threads.
- Four (non-disjoint) classes of thread-unsafe functions:
1) Failing to protect shared variables.
2) Relying on state across multiple function invocations.
3) Returning a pointer to a static variable.
4) Calling thread-unsafe functions.
11.6.1 Reentrant Functions
- Property: do not reference any shared data when called by multiple threads.
- Reentrant functions are typically more efficient than non-reentrant
thread-safe functions because they require no synchronization operations.
- Reentrant functions is a subset of thread-safe functions.
11.6.2 Thread-safe Library Functions
11.7 Other Synchronization Errors
11.7.1 Races
11.7.2 Deadlocks
11.8 Summary
Chapter 12 Network Programming
12.1 Client-Server Programming Model
- The fundamental operation in the client-server model is the transaction.
12.2 Networks
12.3 The Global IP Internet
12.3.1 IP Addresses
12.3.2 Internet Domain Names
12.3.3 Internet Connections
12.4 Unix file I/O
12.4.1 The read and write Functions
12.4.2 Robust File I/OWith the readn and writen Functions
12.4.3 Robust Input of Text Lines Using the readline Function
12.4.4 The stat Function
12.4.5 The dup2 Function
12.4.6 The close Function
12.4.7 Other Unix I/O Functions
12.4.8 Unix I/O vs. Standard I/O
12.5 The Sockets Interface
12.5.1 Socket Address Structures
12.5.2 The socket Function
12.5.3 The connect Function
12.5.4 The bind Function
12.5.5 The listen Function
12.5.6 The accept Function
12.5.7 Example Echo Client and Server
12.6 Concurrent Servers
12.6.1 Concurrent Servers Based on Processes
12.6.2 Concurrent Servers Based on Threads
12.7 Web Servers
12.7.3 HTTP Transactions
12.8 Putting it Together: The TINY Web Server
12.9 Summary
Appendix A Error handling
Appendix B Solutions to Practice Problems
