Midterm 2 Review

Tom Kelliher, CS42

Nov. 6, 1996

1. Semaphores, locks, condition variables.

2. Synchronization problems: bounded buffers, sleepy barber, readers/writers, cigarette smokers, dining philosophers.

3. Critical regions, monitors.

4. Deadlock:
   1. Necessary conditions.

   2. Resource allocation graphs.

   3. Detection/recovery, prevention, avoidance.

   4. Safe, unsafe state. Banker's algorithm.

5. Memory management:
   1. Address binding.

   2. Dynamic loading, linking, shared libraries

   3. Logical, physical addressing.

   4. MMU architectures.

   5. Swapping. Optimizations.

   6. Contiguous allocation schemes: fixed and variable partitions.

   7. Internal, external fragmentation.

   8. Placement policies: first, best, worst fit. Hole combining, memory compaction.

   9. Paging:
      1. Frame sizes - power of 2.

      2. Entire process in memory.

      3. Page onto frame mapping.

      4. Address translation.

      5. Paging hardware. Page tables. TLBs.

      6. Shrinking the page table: multi-level paging.

      7. Protection, sharing.

6. Secondary Storage:
   1. Disk structure.

   2. Components of disk access time.

   3. Disk request scheduling: FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK.

7. Virtual memory:
   1. As opposed to paging.

   2. Advantages.

   3. Why it works. Assumptions.

   4. Kernel, CPU, MMU support.

   5. Page fault sequence. Page fault penalty (average access time).

   6. Replacement policies:
      1. FIFO. Belady's anomaly.

      2. Optimal.

      3. LRU.

      4. Clock.

      Implementation, approximations? Reference strings.

   7. Placement policies:
      1. Minimum # of frames.

      2. Equal, proportional allocation.

      3. Global vs. local victims.

      4. Thrashing.

      5. Working set, page fault frequency models.