Computer Systems Fundamentals

This book provides a breadth-first overview of concurrent systems programming. Specifically, we aim to cover foundational material for the Networking and Communication (NC), Operating Systems (OS), Parallel and Distributed Computing (PDC), and Systems Fundamentals (SF) Knowledge Areas of the ACM Computing Curricula 2023. Rather than thoroughly covering all these topics—that would take several books—this book focuses on core concepts and programming techniques that underlie these areas. 

While the focus of this book is concurrent computing systems, we approach this topic from a pragmatic stance rooted in active learning. Throughout the text, we emphasize the application of systems concepts and integrating this material to the readers’ prior knowledge. Our aim is to provide a solid foundation of core computer systems ideas to all students, regardless of whether they go on to pursue advanced study in the systems area or other domains.

This book relies on a working knowledge of Computer Organization and C programming. In particular, this book assumes that readers are familiar with the C memory model, including memory addresses and pointers, as well as the relationship between high-level languages and assembly language. A specific knowledge of x86 assembly language is not necessary, as most references to it rely almost exclusively on instructions that are like other assembly languages.

• Covers foundational material for many Knowledge Areas of the ACM Computing Curricula 2023 (CS2023).
• Includes extensive exercises to support hands-on learning.
• Provides abundant working code samples.
• Takes a historical perspective on  developing technology.

TABLE OF CONTENTS

Chapter 1: Introduction to Concurrent Systems

Systems and Models
  Models as Representations
Themes and Guiding Principles
  Systems as Foundations of Computing
  Systems and Complexity
  The Semiotics of Computer Systems
System Architectures
  Client/Server Architectures
  Peer-to-peer (P2P) Architectures
  Layered Architectures
  Pipe-and-filter Architectures
  Event-driven Architectures
  Hybrid Architectures
State Models in UML
  State Space Explosion
Sequence Models in UML
Extended Example: State Model Implementation
Profiles in Computing: Bletchley Park
Further Reading
Summary
Key Terms
Review Questions
Problems

Chapter 2: Processes and OS Basics

Kernel Basics
  Kernel Memory Structure and Protections
Processes and Multiprogramming
  Uniprogramming and Utilization
  Multiprogramming and Concurrency
  Context Switches and Overhead Costs
Kernel Mechanics
  The Boot Procedure
  Kernel Invocation
  Mode Switches and Privileged Instruction
System Call Interface
  System Calls vs. Function Calls
  Linux System Calls
  Calling System Calls in Assembly
  Calling System Calls with syscall()
Process Life Cycle
  Process Creation
  Switching Program Code
  Using Environment Variables
  POSIX Spawn Interface
  Process Destruction
Signals
  Custom Signal Handlers
  Continuing after Signals
Extended Example: Listing Files with Processes
Profiles in Computing: Fernando Corbató
Further Reading
Summary
Key Terms
Review Questions
Problems

Chapter 3: Concurrency with IPC

IPC Models
  Advantages and Disadvantages
  An IPC Taxonomy
Pipes and FIFOs
  Basic Pipes
  Pipes and Shell Commands
  FIFOs
Memory-mapped Files
  Mapping Files
  Region Protections and Privacy
POSIX vs. System V IPC
  POSIX IPC Fundamentals
  System V IPC Keys and Utilities
Message Passing With Message Queues
  POSIX Message Queues
Shared Memory
  POSIX Shared Memory
Semaphores
  POSIX vs. System V Semaphores
  POSIX Named Semaphores
  POSIX Unnamed Semaphores
  System V Semaphores
Extended Example: Bash-lite: A Simple Command-line Shell
Profiles in Computing: Ken Thompson and Dennis Ritchie
Further Reading
Summary
Key Terms
Review Questions
Problems

Chapter 4: Networked Concurrency

The TCP/IP Internet Model
  Internet Model
  Packet Encapsulation and Nomenclature
Network Applications and Protocols
  Naming and Addressing
  Protocol Specifications and RFCs
The Socket Interface
  Networking Data Structures
  Client Socket Interface
  Server Socket Interface
  Socket Communication
TCP Socket Programming: HTTP
  Hypertext Transfer Protocol (HTTP)
  BNF Protocol Specification
  HTTP/1.1 Persistent Connections
  Processing HTTP Headers and Body
  Persistent State with Cookies
UDP Socket Programming: DNS
  Resolving DNS Queries
  DNS Resource Record Structure
  DNS Protocol Messages
  Constructing DNS Queries With Sockets
  Processing DNS Query Responses
Application-Layer Broadcasting: DHCP
  DHCP Overview
  DHCP Protocol Messages
Extended Example: CGI Web Server
Profiles in Computing: Bob Kahn and Vint Cerf
Further Reading
Summary
Key Terms
Review Questions
Problems

Chapter 5: The Internet and Connectivity

Application Layer: Overlay Networks
  Characteristics of Peer-to-Peer Networks
Transport Layer
  Unreliable Transport: UDP
  Reliable Transport: TCP
  TCP Handshake and Connections
  TCP Timeout and Packet Loss
Network Security Fundamentals
  Symmetric Key Encryption
  Public Key Encryption
  Cryptographic Hash Functions
  Transport Layer Security (TLS)
Network Layer: IP
  IP Addresses and Subnets
  IP Packet Formats
  Network Routing Protocols
Link Layer
  LAN Packet Transmission: Ethernet
  LAN Packet Transmission: ARP
  What Lies Beneath: Carrier Signals
Wireless Connectivity: Wi-Fi, Bluetooth, and Zigbee
  Wireless Protocol Stacks and Uses
Extended Example: DNS Client
Profiles in Computing: Radia Perlman
Further Reading
Summary
Key Terms
Review Questions
Problems

Chapter 6: Concurrency with Multithreading

Processes vs. Threads    
  Multithreading
  Advantages and Disadvantages of Threads
  Thread Models
Race Conditions and Critical Sections
  Race Conditions
  Thread Safety and Reentrancy
POSIX Thread Library
  Creating and Joining Threads
  Attached and Detached Threads
Thread Arguments and Return Values
  Passing a Single Argument to Threads
  Passing Multiple Arguments to Threads
  Returning Values from Threads
Implicit Threading and Language-based Threads
  Implicit Threading with OpenMP
  Threads as Objects
  Concurrency as Language Design
Extended Example: Keyboard Input Listener
Extended Example: Concurrent Prime Number Search
Profiles in Computing: Margaret Hamilton
Further Reading
Summary
Key Terms
Review Questions
Problems

Chapter 7: Synchronization Primitives

Critical Sections and Peterson’s Solution
  Peterson’s Solution
  Synchronization Properties
  Peterson’s Solution and Modern Hardware
Locks
  POSIX Mutexes
  Spinlocks
  Defining Critical Sections
Condition Variables
  A Condition Variable Example
Synchronization Barriers
  Concurrent Calculations with Barriers
Semaphores
  Creating POSIX Semaphores
  Semaphore Mechanics
  Basic Semaphore Applications
  Condition Variables vs. Semaphores
Extended Example: Event Log File
Profiles in Computing: Edsger Dijkstra
Further Reading
Summary
Key Terms
Review Questions
Problems

Chapter 8: Synchronization Patterns and Problems

Basic Synchronization Design Patterns
  Rendezvous
  Turnstiles and Alternating Execution
  Resource Pools
  Lightswitches
  Monitors and Synchronized Methods
Producer-Consumer Problem
  Producer–Consumer with Unbounded Queue
  Single Producer–Single Consumer Solution Using a Bounded Queue
  Multiple Producers Solution Using a Bounded Queue
Readers-Writers Problem
  A Solution Using Lightswitches
  Fairness to Writers
  Search-Insert-Delete Problem
Dining Philosophers Problem and Deadlock
  Solution of Limiting Accesses
  Solution by Breaking Hold-and-wait
  Solution by Imposing Order
Cigarette Smokers Problem and the Limits of Semaphores and Locks
  Implications of the Cigarette Smokers Problem
  On Cigarette Smokers and Dining Philosophers
Extended Example: Parallel Modular Exponentiation
Profiles in Computing: Tony Hoare
Further Reading
Summary
Key Terms
Review Questions
Problems

Chapter 9: Parallel and Distributed Systems

Parallelism vs. Concurrency
Parallel Design Patterns
  Algorithmic Strategy Patterns
  Implementation Strategy Patterns
  Parallel Execution Patterns
Limits of Parallelism and Scaling
  Amdahl’s Law and Strong Scaling
  Gustafson’s Law and Weak Scaling
Timing in Distributed Environments
  Clock Synchronization
  Logical Clocks and Lamport Timestamps
  Vector Clocks
Reliable Data Storage and Location
  Google File System
  Distributed Hash Tables
Consensus in Distributed Systems
  Byzantine Generals Problem
  Limits on Consensus
  Practical Byzantine Fault Tolerance
Extended Example: Blockchain Proof-of-Work
Profiles in Computing: Leslie Lamport
Profiles in Computing: Barbara Liskov
Further Reading
Summary
Key Terms
Review Questions
Problems

Appendix A: C Language Reintroductions

Appendix B: System V IPC