• Overview and Fault Model
• Belady’s anomaly and OPT
• LRU and the stack property
• CLOCK / Second-chance
• NFU, Aging, and Approximations
• Engineering notes (HW ref bits, TLB)
• Exercises

• Physical memory holds frames; each page reference hits or misses (page fault) and may evict a victim frame.
• Goal: minimize faults given a fixed number of frames; replacement policy chooses the victim.
• Reference string: sequence of page numbers derived from virtual addresses after page-size grouping.

• Belady’s anomaly: FIFO can have more faults with more frames.
• OPT (MIN): evict the page whose next use is farthest in the future (unimplementable online) — lower bound.
• Stack algorithms: never suffer Belady’s anomaly (e.g., LRU, LFU with perfect history).

// LRU using a Map to simulate an ordered dictionary (MRU at end)
function simulateLRU(refs, frames) {
  const cache = new Map(); // key: page, value: true; iteration order = recency
  let faults = 0;
  for (const p of refs) {
    if (!cache.has(p)) { // miss
      faults++;
      if (cache.size === frames) {
        // evict LRU (first key)
        const lruKey = cache.keys().next().value;
        cache.delete(lruKey);
      }
    } else {
      // refresh recency by deleting and re-inserting
      cache.delete(p);
    }
    cache.set(p, true);
  }
  return faults;
}

• Stack property: fault count with k frames ≥ count with k+1 frames.
• Implementation: exact LRU is costly; approximations (reference bits, aging) are common.

// Second-chance (CLOCK) simulation
function simulateCLOCK(refs, frames) {
  const frame = Array(frames).fill(null);
  const refbit = Array(frames).fill(0);
  let hand = 0, faults = 0;
  const pos = new Map();
  for (const p of refs) {
    if (pos.has(p)) { // hit
      refbit[pos.get(p)] = 1;
      continue;
    }
    faults++;
    while (frame[hand] !== null && refbit[hand] === 1) {
      refbit[hand] = 0; hand = (hand + 1) % frames;
    }
    // evict if occupied
    if (frame[hand] !== null) pos.delete(frame[hand]);
    frame[hand] = p; refbit[hand] = 1; pos.set(p, hand);
    hand = (hand + 1) % frames;
  }
  return faults;
}

• Uses a circular list and reference bits as a cheap LRU approximation.
• Variants: CLOCK-Pro, ARC (adaptive), and 2Q blend recency and frequency.

• NFU (Not Frequently Used): maintain counters incremented on reference; evict lowest.
• Aging: periodically right-shift counters and add ref bit to MSB to decay old references (approximates LRU).
• Working set: track pages referenced in last Δ time; replacement tries to keep working set resident.

• Hardware sets accessed/dirty bits in PTEs; OS periodically samples and clears to inform policies.
• TLB behavior interacts with replacement; huge pages reduce TLB pressure but increase fragmentation.
• Swapping I/O dominates costs; clustering adjacent pages improves throughput.

1. Generate random reference strings and compare fault counts of FIFO, LRU, CLOCK, and OPT (offline).
2. Implement aging with N-bit counters; study sensitivity to sampling interval and counter width.
3. Reproduce Belady’s anomaly for FIFO on a known sequence; verify LRU avoids the anomaly.