Page Faults & Page Replacement Algorithms

Page faults occur when a process accesses a page not currently in physical memory. Page replacement algorithms determine which page to evict when memory is full.

---

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

---

Key Takeaways

• 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