CSE 410 Sp09 Final Exam Topics

The final exam will be comprehensive, spread fairly evenly among topics covered during the quarter, although with a bit more emphasis on new material since the midterm. In general you are responsible for everything covered in class and on homework assignments. You are not responsible for specific readings in the textbook, but you are expected to know the material in the book related to topics covered in class.

The exam is closed-book, no notes, no calculators or other electronic devices. You may bring a single sheet of paper with whatever handwritten notes you wish. You can use the MIPS reference "green card" from the book. Copies of this will be provided if you do not bring your own. In general you should not be memorizing details that you can look up.

New topics since the midterm

• Memory hierarchy
  • Principles of temporal and spatial locality - why we can combine small, fast, expensive storage and large, slower, and cheaper storage to get something that is cheaper but still fast
  • Order-of-magnitude differences between access speeds to CPU registers, cache, main memory, and disks
  • Calculating effective access times given individual times and hit/miss ratios
• Cache memories
  • Position in the memory hierarchy
  • Terminology: hit/miss; hit rate/miss rate; access times
  • Fully associative vs direct-mapped vs set-associative cache organizations
  • How the bits of an address are used to calculate cache locations; address tags
  • Cache replacement policies: what line is replaced? Write-through vs write-back
  • Tradeoffs in cache line block size; advantages and disadvantages of larger blocks
• Operating System basics
  • Role of an operating system (provide services to application programs; manage shared resources, etc.)
• Process abstraction
  • Difference between programs and processes
  • Process states (ready, running, waiting); reasons for state change
  • Process data structure (Process Control Block, PCB) - what information does the OS need to maintain about each existing process?
  • Context switches: what happens when the OS switches from one process to another? What information is saved/restored when a process becomes inactive/active?
• Threads
  • Relationship to processes
  • What information is unique to each thread? What is shared among all threads that belong to the same process?
  • Kernel threads vs. user-space threads; tradeoffs, etc.
  • Benefits and costs of multi-threaded designs; tradeoffs
• Process scheduling
  • Strategies for deciding what process to run next: goals (troughput vs responsiveness and minimizing wait times vs "fairness"), conflicts among different goals
  • Preemptive vs non-preemptive scheduling: advantages and disadvantages
  • Pros and cons of some basic scheduling strategies: first-come, first-served; round robin; priority scheduling; shortest job first; multi-level scheduling queues and feedback queues
• Synchronization
  • Potential problems with multiple threads using shared resources without proper synchronization
  • Desirable correctness properties: safety and liveness (progress)
  • Definitions: synchronization, mutual exclusion, critical sections, atomic operations; busy waiting
  • Locks; use of locks for basic synchronization of shared resources
  • Implementing locks: disable interrupts (when does and doesn't this work?); atomic memory operations and why these are needed.
  • Semaphores: differences from locks, advantages
  • Monitors and condition variables: wait, signal and broadcast operations; using these to synchronize
• Deadlock
  • Conditions required for two processes (threads, tasks) to deadlock
  • Strategies for dealing with deadlock: prevention, avoidance, detect and recover, ignore
• Virtual memory - hardware address translation
  • Logical (virtual) vs physical addresses; address space layout (text, data, stack areas)
  • Paging: division of address spaces into logical and physical pages
  • Memory mapping hardware (MMU); operations needed to translate a virtual address to a physical one; which address bits do what
  • Flat page tables vs multi-level page tables (why might we want the later? what are the costs/benefits?)
  • TLB - Translation Lookaside Buffer; why it's there, contents, how and when it's used
• Virtual memory - operating system policies and implementation
  • Demand paging: what is it?
  • Virtual memory replacement algorithms: FIFO, RANDOM, MIN, LRU, CLOCK - which of these are good/bad/best? Which are feasible? What are the implementation and performance tradeoffs?
  • Thrashing: what is it? How can we prevent it?
  • Working set: definition; how is this related to thrashing?
• File systems
  • File abstraction (collection of bytes with a name, type, size, protection, etc)
  • User program file operations provided by operating system (open, read/write/seek/truncate/delete, close)
  • Disk file structures: what does the hardware give us? Tracks, cylinders, blocks
  • Directory structures; tree-structured directories
  • Unix inode structure (a file is really an inode and the blocks it points to); relationship to directories