Final Exam Guide

Objective questions (concepts)

  1. Memory hierarchy and Caching

    • Types of memory and relative speeds
    • Memory hierarchy rationale and organization
    • Localities of reference
      • Temporal and Spatial
      • Examples and analysis
    • MMU responsibilities
    • Cache designs/policies
      • Direct-mapped
      • Fully associative
        • Scalability issues
      • Set associative
        • Terminology: n-way set-associative
      • Multi-byte/word blocks
      • Cache alignment
      • Replacement policies (operation and analysis)
        • FIFO, LFU, LRU
        • Write- through / back / around / allocate
      • Cache metrics
        • hit rate
        • miss rate
        • hit time
        • miss penalty
      • Multi-level caching
    • Cache optimization
      • Design principles
      • Blocking

  2. Virtual memory (DRAM-HDD)

    • Goals
      1. utilization
      2. throughput
      3. consistency & protection
    • Implementations: pros/cons and translation procedure
      1. Simple relocation
      2. Segmentation
      3. Paging
        • Page table size computation
        • TLB
        • Multi-level page tables
    • Fragmentation: internal and external

  3. Dynamic memory allocation

    • Process memory layout
    • Heap organization
      • brk pointer
    • DMA responsibilities and goals
      • Measuring utilization (peak memory utilization)
    • Self-describing blocks
    • Internal and External fragmentation
    • Implementing a DMA (in C)
      • malloc/realloc/free API: semantics and usage
      • DMA restrictions (e.g., no moving)
      • Basic concerns (implementation and analysis)
        • Metadata vs. Data
        • Block metadata
        • Boundary tags
        • Alignment
        • Free space search/reuse policies
        • Coalescing
      • Common designs (implementation and analysis)
        • Implicit list
        • Explicit list

  4. Garbage collection

    • Premise and Rationale
    • Reference counting GC
      • Manual vs. Automatic
      • Compared to explicit memory management (malloc/free)
      • Basic issues
        • Retain/Release mechanisms
        • Strong/Weak pointers
        • Handling circular references
    • Tracing GC
      • Memory as graph
        • Root vs. Heap nodes
      • Mark-and-Sweep algorithm (operation and analysis)
      • Conservative garbage collection
      • Additional heuristics and optimizations
        • e.g., generational and copying GC
      • Overhead and non-deterministic behavior

Discussion / Computational questions