Computer Systems Fundamentals

WHY THIS BOOK IS NEEDED

The aim of this book is to provide a breadth-first overview of concurrent systems architectures and programming. Specifically, this book aims to cover 100 percent of the Core Tier 1 material for the areas of System Fundamentals, Operating Systems, Network-centric Computing, and Parallel and Distributed Computing. In achieving this coverage, this book provides a flexible foundation for undergraduate Computer Science programs to achieve Core Tier 1 coverage while customizing their curriculum for Core Tier 2 as appropriate for their students. Furthermore, this approach provides a foundational scaffold for additional systems courses that can apply these principles and concepts with more in-depth study of specific areas.

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
  Process Destruction
Events and Signals
  Sending Process Signals
  Custom Signal Handlers
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
Shared Memory With Memory-mapped Files
  Memory-mapped 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 vs. System V Message Queues
  POSIX Message Queues
  System V Message Queues
Shared Memory
  POSIX Shared Memory
  System V 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
  5-layer 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
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: DNS client
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)
  TLS in Practice: HTTPS
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: CGI Web Server
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
Race Conditions and Critical Sections
  Race Conditions
  Critical Sections
  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
Semaphores
  Semaphores as Signaling
  Mutual Exclusion with Semaphores
  Multiplexing with Semaphores
Barriers
  Concurrent Calculations with Barriers
Condition Variables
  Condition Variables vs. Semaphores
  How to Use a Condition Variable
  A Condition Variable Example
  Monitors and Synchronized Methods
Deadlock
  Necessary Conditions
  Livelock and False Solutions
  Avoiding Deadlock
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
  Signaling
  Turnstiles
  Rendezvous
  Multiplexing
  Lightswitches
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