Undergraduate Material

Recognizing that students come from different backgrounds, we enumerate topics that we expect students to have learned in their undergraduate coursework. You should identify any gaps in your understanding and review the material as needed. Although this list of undergraduate material is intended primarily as preparation for the readings in the next section, it is within scope for the preliminary exam (i.e., you may be tested on it directly).

We expect you to understand these topics in no greater depth than they are covered in the OSTEP textbook. If it's not in OSTEP, then it's not in scope.


List of Topics

  1. Operating System Concepts and Abstractions
    • Kernels, process, threads, address spaces, and hardware privilege level (also known as dual-mode operation)
    • APIs in a UNIX-like environment for using processes (fork, exec, and wait), threads (pthreads), and files (open, read, etc.)
  2. Synchronization
    • Implementation of threads and locks (disabling interrupts and atomic operations like CompareAndSwap)
    • How to use semaphores, locks, and condition variables
  3. CPU Scheduling
    • Classic policies: FCFS (First-Come, First-Served), Round Robin, Priorities, SRTF (Shortest Remaining Time First), MLFQ (Multi-Level Feedback Queue), and EDF (Earliest Deadline First)
    • Starvation (including priority donation/inheritance) and deadlock (including prevention techniques)
  4. Memory Management
    • Software support for address translation: page fault handler and multi-level page tables
    • Hardware support for address translation: cache, TLB, and MMU
    • Demand paging eviction policies: MIN (Belady's Algorithm), LRU (Least Recently Used), NRU (Not Recently Used, also known as the "Clock Algorithm"), and VAX/VMS second-chance lists
    • Spatial locality, temporal locality, working sets, Belady's anomaly, and thrashing
  5. Input/Output (I/O) and System Performance
    • Conceptual understanding of buses, controllers, interrupts, polling, programmed I/O (PIO), and Direct Memory Access (DMA)
  6. Storage Systems
    • Physical organization and performance of Hard Disk Drives (HDDs) and Solid State Drives (SSDs)
    • File system structure: directory structure, index structure (inodes), storage blocks, free space map, hard links, soft links, and buffer cache
    • Case studies: File Allocation Table (FAT) and Berkeley Fast File System (FFS)
    • Replication as a means for durability: erasure codes and RAID (disk replication)
    • Transactions as a means for reliability: journaling file systems and redo logging
  7. Networked and Distributed Systems
    • Remote Procedure Calls (RPCs) and their implementation
    • Reliable transport (TCP vs. UDP)
    • Conceptual understanding of symmetric-key encryption, public-key encryption, and cryptographic hash functions (you need to know what these primitives are and how to use them, but formal security definitions are out of scope)


Resources to Review Undergraduate Material

We particularly recommend the following textbook. We refer to it as "OSTEP" (an abbreviation of its title).


The course materials for CS 162, Berkeley's undergraduate operating systems course, are another excellent resource to review the above material.


Other relevant textbooks: