Final Exam Review Guide

Objective questions (concepts)

  1. Virtual memory

    • Standard process address space layout
    • Goals: transparency, efficiency, protection
    • Address translation mechanisms (implementation, capabilities, and analysis)
      • Relocation
      • Segmentation
        • Segment sharing and access control
        • Segmentation faults
      • Paging
        • Page table implementation
        • Interaction with caches
        • Translation Lookaside Buffer (TLB)
        • Segmentation + Paging
        • Multi-level page tables
    • Swapping
      • Page faults
      • Medium term scheduler
      • Thrashing and mitigation
    • General x86 VM capabilities
    • Linux VM features
      • Page and Swap caches
      • Copy-on-write optimization
  2. Concurrency

    • Parallelism and Time-multiplexing
    • Processes vs. Threads
    • For improving utilization and performance
    • User vs. Kernel threads (implementation and analysis)
    • Limits on performance: Amdahl's and Gustafson's laws
    • Non-determinism and race conditions
      • Critical sections
    • Lock-based synchronization
      • Coarse- vs. Fine-grained locking
      • Implementing locks
    • Condition variables
    • Semaphores and classical synchronization problems
      • Basic patterns (rendezvous, mutex, multiplex, lightswitch)
      • Producer/Consumer
      • Readers/Writers
      • Dining Philosophers
  3. Concurrent programming paradigms

    • Issues with lock-based concurrent programming
      • Composability
    • Alternative models (design and analysis)
      • Software transactional memory
        • Transaction properties
        • Clojure STM (MCC)
      • Message-passing / Actor model
      • Event-driven paradigm
        • Event loops and queues
        • Callback functions
  4. I/O devices and drivers

    • Basic protocol requirements, implementation, and issues
    • Protocol variants
      • Polled vs. Interrupt-driven
      • Programmed I/O vs. Direct Memory Access
      • Special instructions vs. Memory-mapped I/O
    • Hard disk drives
      • HDD geometry and access characteristics
      • Seek/Rotate/Transfer behavior
      • Disk scheduling
        • FCFS, SSTF, Elevator algorithms
  5. Filesystems

    • Unix I/O API
      • Block- vs. Stream-oriented files
      • Inodes vs. Paths vs. File descriptors
    • Simple Unix FS implementation
      • Metadata structures and contents: superblock, free bitmap, inodes, directories
      • Disk layout
      • Path lookup procedure
      • Indirect inode pointers
    • Fast File System optimizations and takeaways
    • FS consistency issues
      • Analysis and correction (fsck)
    • Journaling
      • Full vs. Metadata journals

Discussion / Computational problems