Final Exam Topic List

  1. Concurrency

    • vs. Parallelism
    • motivation: partition blocking, improve utilization, improve performance
    • kernel vs. user space threads: defs and pros/cons
    • limits of performance gains: Amdahl's and Gustafson's laws
    • WP: max theoretical performance increase
  2. Concurrent Programming

    • Essential criteria (no starvation/deadlock, bounded waiting, max concurrency)
    • Locks and locking strategies (coarse vs. fine grained)
    • Semaphores
      • semantics and usage
      • basic patterns: rendezvous, barrier, turnstile, lightswitch
      • classical problems: producer/consumer, readers/writers, dining philosophers
      • combining patterns (e.g., see crossing baboons problem for turnstile + mutex + lightswitch)
    • WP: implementing synchronization using semaphores (Example)
  3. Alternative concurrent programming paradigms (concepts only!)

    • Actor model
      • Basic premise (purely functional, independent processes, asynch message-passing via "mailboxes")
      • Pros/Cons
    • Software Transactional Memory
      • Basic premise (system guarantees ACI properties, re-runs transactions)
      • Pros/Cons
    • WP: discussion of pros/cons of different approaches to concurrent programming
  4. I/O

    • Polling vs. Interrupts
    • Programmed I/O vs. DMA
    • Hard disk access
      • Seek / Rotate / Transfer
      • Sequential and Random Access Throughput calculations
      • Scheduling algorithms (FCFS, Elevator)
  5. Filesystems

    • Essential goals
      • Terms: CRUD, decoupling (of OS and FS), device agnosticism
    • Paths/Filenames/Links vs. Unique files
    • File allocation strategies: basic models and pros/cons
      • WP: max disk/file sizes of FAT/inode based system (Example)