Page Faults & Page Replacement Algorithms

Page Faults & Page Replacement Algorithms

Why This Matters

Think of page faults like asking for a book that's not on the shelf. You request a book (access a page), but it's not in the library's main collection (physical memory). The librarian (OS) fetches it from storage (disk) and brings it to you. Page faults work the same—when a process accesses a page not in memory, the OS loads it from disk. Page replacement algorithms decide which page to remove when memory is full.

This matters because physical memory is limited. Not all pages can fit in memory, so the OS uses virtual memory (pages on disk). When a process accesses a page not in memory, a page fault occurs, and the OS loads it. If memory is full, the OS must evict a page first. The replacement algorithm (LRU, FIFO, etc.) decides which page to evict, affecting performance.

In interviews, when someone asks "How does virtual memory work?", they're testing whether you understand page faults and replacement algorithms. Do you know what happens when a page isn't in memory? Do you understand LRU? Most engineers don't. They just use memory and assume it works.

What Engineers Usually Get Wrong

Most engineers think "page faults are errors." But page faults are normal—they're how virtual memory works. When a process accesses a page not in memory, a page fault occurs, and the OS loads it. This is expected behavior. Only invalid page faults (accessing invalid addresses) are errors.

Engineers also don't understand that page replacement affects performance. If the OS evicts a page that's about to be used (poor replacement algorithm), it causes another page fault immediately (thrashing). Good replacement algorithms (like LRU) evict pages that are unlikely to be used soon, reducing page faults. Understanding this helps you understand why some systems are slow.

How This Breaks Systems in the Real World

A service was using too much memory. The OS started swapping pages to disk. Page faults increased dramatically (thrashing). The system became slow—spending more time swapping pages than doing work. The fix? Reduce memory usage, or add more RAM. Understanding page faults helps you understand why systems slow down when memory is exhausted.

Another story: A service was experiencing high page fault rates. The OS was using a poor replacement algorithm (FIFO) that evicted pages regardless of usage. Frequently used pages were evicted, causing more page faults. The fix? Use a better replacement algorithm (LRU), or optimize memory usage to reduce page faults. Understanding replacement algorithms helps you understand system performance.

---

What is a Page Fault?

Page fault occurs when:

• Process accesses virtual address
• Page table: Present bit = 0 (page not in memory)
• CPU generates page fault interrupt
• OS handles page fault

Types:

• Minor page fault: Page in memory but not in page table (fast)
• Major page fault: Page on disk, must load (slow, disk I/O)
• Invalid page fault: Invalid address (segmentation fault)

---

Page Fault Handling

Process

1. Process accesses virtual address
2. Page table lookup: Present = 0
3. CPU generates page fault (interrupt)
4. OS page fault handler:
   a. Check if page exists on disk
   b. If invalid: Segmentation fault
   c. Find free frame (or evict page)
   d. Load page from disk to frame
   e. Update page table (Present = 1)
   f. Resume process execution

---

Page Replacement Algorithms

When memory is full, OS must evict a page to make room.

1. FIFO (First In First Out)

Evict oldest page:

Pages in memory: [A, B, C] (A oldest)
New page D arrives → Evict A
Memory: [B, C, D]

Problem: May evict frequently used pages

2. LRU (Least Recently Used)

Evict least recently used page:

Pages: [A, B, C]
Access: A, B, A, C
New page D → Evict B (least recently used)
Memory: [A, C, D]

Optimal: Minimizes page faults (but requires tracking)

3. Optimal

Evict page that won't be used for longest time:

Pages: [A, B, C]
Future: A, C, A, B
Evict B (won't be used for longest)

Not practical: Requires knowledge of future

4. Clock (Second Chance)

Circular buffer with reference bit:

Pages: [A(ref=1), B(ref=0), C(ref=1)]
Clock hand points to B
New page D → Evict B (ref=0)
If ref=1: Clear ref, move to next

---

Examples

Page Fault Handler

class PageFaultHandler:
    def __init__(self, memory_manager):
        self.memory_manager = memory_manager
        self.page_replacer = PageReplacer()
    
    def handle_page_fault(self, virtual_address, process):
        """Handle page fault"""
        page_number = virtual_address // PAGE_SIZE
        
        # Check if page exists on disk
        if not self.memory_manager.page_on_disk(page_number):
            raise SegmentationFault("Invalid page")
        
        # Find free frame
        frame = self.memory_manager.find_free_frame()
        
        if frame is None:
            # No free frame: Page replacement
            frame = self.page_replacer.evict()
        
        # Load page from disk
        self.memory_manager.load_page(page_number, frame)
        
        # Update page table
        process.page_table[page_number] = {
            'frame': frame,
            'present': True,
            'modified': False,
            'referenced': True
        }
        
        # Resume process
        return frame

LRU Page Replacement

class LRUPageReplacer:
    def __init__(self):
        self.access_times = {}  # page → last access time
    
    def evict(self):
        """Evict least recently used page"""
        if not self.access_times:
            return None
        
        # Find page with oldest access time
        lru_page = min(
            self.access_times.items(),
            key=lambda x: x[1]
        )[0]
        
        # Get frame for this page
        frame = self.get_frame(lru_page)
        
        # If modified, write to disk
        if self.is_modified(lru_page):
            self.write_to_disk(lru_page, frame)
        
        # Remove from access times
        del self.access_times[lru_page]
        
        return frame
    
    def record_access(self, page_number):
        """Record page access"""
        self.access_times[page_number] = time.time()

Clock Algorithm

class ClockPageReplacer:
    def __init__(self, num_frames):
        self.frames = [None] * num_frames
        self.reference_bits = [False] * num_frames
        self.clock_hand = 0
    
    def evict(self):
        """Evict using clock algorithm"""
        while True:
            frame = self.frames[self.clock_hand]
            
            if frame is None:
                # Empty frame
                return self.clock_hand
            
            if not self.reference_bits[self.clock_hand]:
                # Not recently used: Evict
                evicted_frame = self.clock_hand
                self.clock_hand = (self.clock_hand + 1) % len(self.frames)
                return evicted_frame
            else:
                # Recently used: Clear bit, continue
                self.reference_bits[self.clock_hand] = False
                self.clock_hand = (self.clock_hand + 1) % len(self.frames)

---

Common Pitfalls

• Belady's anomaly: More frames can cause more page faults (FIFO). Fix: Use LRU or other algorithms
• Not tracking access: Can't implement LRU. Fix: Track page access times
• Thrashing: Too many page faults. Fix: Increase RAM, reduce processes, optimize algorithms
• Not writing dirty pages: Modified pages lost. Fix: Write dirty pages to disk before eviction

---

Interview Questions

Beginner

Q: What is a page fault and how does the OS handle it?

A:

Page fault occurs when process accesses page not in memory.

When it happens:

• Process accesses virtual address
• Page table: Present bit = 0 (page not in memory)
• CPU generates page fault interrupt

How OS handles:

1. Check if page exists on disk

   • If invalid: Segmentation fault

2. Find free frame

   • If no free frame: Evict page (page replacement)

3. Load page from disk

   • Read page from swap space
   • Load into frame

4. Update page table

   • Set Present = 1
   • Set frame number

5. Resume process

   • Process continues execution

Types:

• Minor: Page in memory but not in page table (fast)
• Major: Page on disk, must load (slow, disk I/O)
• Invalid: Invalid address (segmentation fault)

---

Intermediate

Q: Explain different page replacement algorithms. Which is best and why?

A:

1. FIFO (First In First Out):

Evict oldest page
Pages: [A, B, C] (A oldest)
New D → Evict A

Problem: May evict frequently used pages

2. LRU (Least Recently Used):

Evict least recently used
Pages: [A, B, C]
Access: A, B, A, C
Evict B (least recently used)

Optimal: Minimizes page faults (but requires tracking)

3. Optimal:

Evict page that won't be used for longest time
Future: A, C, A, B
Evict B (won't be used for longest)

Not practical: Requires knowledge of future

4. Clock (Second Chance):

Circular scan, evict page with ref=0
If ref=1: Clear ref, continue

Good balance: Simpler than LRU, better than FIFO

Which is best:

• Optimal: Best (theoretical, not practical)
• LRU: Best practical (minimizes page faults)
• Clock: Good balance (simpler than LRU)
• FIFO: Simple but not optimal

Use LRU or Clock in practice

---

Senior

Q: Design a page replacement system that handles millions of pages efficiently. How do you implement LRU, handle dirty pages, and optimize for performance?

A:

class HighPerformancePageReplacement {
  private pageReplacer: PageReplacer;
  private dirtyPageTracker: DirtyPageTracker;
  private accessTracker: AccessTracker;
  
  constructor() {
    this.pageReplacer = new PageReplacer({ algorithm: 'LRU' });
    this.dirtyPageTracker = new DirtyPageTracker();
    this.accessTracker = new AccessTracker();
  }
  
  // 1. LRU Implementation
  class LRUPageReplacer {
    private accessTimes: Map<number, number>;
    private accessOrder: LinkedList<number>; // For O(1) operations
    
    evict(): number {
      // Find least recently used (head of list)
      const lruPage = this.accessOrder.head.value;
      
      // Remove from list
      this.accessOrder.removeHead();
      
      // Get frame
      const frame = this.getFrame(lruPage);
      
      // Handle dirty page
      if (this.isDirty(lruPage)) {
        this.writeToDisk(lruPage, frame);
      }
      
      return frame;
    }
    
    recordAccess(pageNumber: number): void {
      // Move to end of list (most recently used)
      this.accessOrder.moveToEnd(pageNumber);
      this.accessTimes.set(pageNumber, Date.now());
    }
  }
  
  // 2. Dirty Page Handling
  class DirtyPageTracker {
    private dirtyPages: Set<number>;
    
    markDirty(pageNumber: number): void {
      this.dirtyPages.add(pageNumber);
    }
    
    async evictDirtyPage(pageNumber: number, frame: number): Promise<void> {
      if (this.isDirty(pageNumber)) {
        // Write to disk before eviction
        await this.writeToDisk(pageNumber, frame);
        this.dirtyPages.delete(pageNumber);
      }
    }
  }
  
  // 3. Performance Optimization
  optimizePerformance(): void {
    // Batch write dirty pages
    this.batchWriteDirtyPages();
    
    // Prefetch adjacent pages
    this.prefetchAdjacentPages();
    
    // Use hardware support (TLB, page table cache)
    this.useHardwareSupport();
  }
}

Features:

1. LRU: Efficient implementation with linked list
2. Dirty pages: Track and write before eviction
3. Performance: Batch writes, prefetch, hardware support

---

• Page fault: Occurs when page not in memory, OS loads from disk

• Types: Minor (fast), Major (slow, disk I/O), Invalid (segmentation fault)

• Page replacement: Evict page when memory full

• Algorithms: FIFO, LRU, Optimal, Clock

• LRU: Best practical algorithm (minimizes page faults)

• Dirty pages: Write modified pages to disk before eviction

• Best practices: Use LRU or Clock, handle dirty pages, optimize for performance

• Virtual Memory - How page faults enable virtual memory by loading pages from disk

• Memory Management - Comprehensive overview of memory management including page faults and replacement

• Paging and Segmentation - How paging mechanism enables page faults and replacement

• I/O Management - How page faults trigger disk I/O operations

• System Calls - How page faults are handled through system calls to the kernel