Virtual Memory

Virtual memory is an abstraction that gives each process its own large address space, independent of the amount of physical RAM available. It allows processes to use more memory than physically available by using disk storage as an extension of RAM.

---

What is Virtual Memory?

Virtual memory provides:

• Larger address space: Processes can use more memory than RAM
• Memory protection: Each process has isolated address space
• Simplified programming: Processes don't manage physical memory
• Memory sharing: Processes can share code and data

How it works:

• Virtual addresses: Process uses virtual addresses (0 to 2^32-1 or 2^64-1)
• Physical addresses: OS maps virtual addresses to physical RAM
• Paging: Memory divided into pages, mapped to frames
• Swapping: Pages can be stored on disk when not in use

---

Address Translation

Virtual to Physical Address

Virtual Address: [Page Number | Offset]
                  ↓
            Page Table Lookup
                  ↓
         Physical Frame Number
                  ↓
    Physical Address: [Frame Number | Offset]

Example:

Virtual Address: 0x1234
  Page Number: 0x1 (page 1)
  Offset: 0x234 (offset within page)
  
Page Table:
  Page 1 → Frame 5
  
Physical Address: 0x5234
  Frame Number: 5
  Offset: 0x234 (same)

Page Table Entry (PTE)

[Frame Number | Present | Modified | Referenced | Protection]

Flags:

• Present: Page in memory (1) or on disk (0)
• Modified: Page has been written to (dirty bit)
• Referenced: Page recently accessed
• Protection: Read, write, execute permissions

---

Page Fault

Page fault occurs when process accesses page not in memory.

Page Fault Handling

1. Process accesses virtual address
2. Page table: Present bit = 0 (page not in memory)
3. CPU generates page fault (interrupt)
4. OS page fault handler:
   a. Check if page exists on disk
   b. If invalid address: 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

Types of Page Faults

1. Minor Page Fault:

• Page in memory but not in page table
• Fast (just update page table)

2. Major Page Fault:

• Page not in memory, must load from disk
• Slow (disk I/O required)

3. Invalid Page Fault:

• Invalid address (segmentation fault)
• Terminate process

---

Swapping

Swapping moves pages between RAM and disk.

Swap Out (Page to Disk)

When memory is full:
1. Select page to evict (page replacement algorithm)
2. If page modified: Write to swap space on disk
3. Update page table: Present = 0, disk address stored
4. Free frame for new page

Swap In (Page from Disk)

On page fault:
1. Check page table: Present = 0, disk address available
2. Find free frame (or evict page)
3. Load page from swap space to frame
4. Update page table: Present = 1
5. Resume process

---

Page Replacement Algorithms

When memory is full, OS must evict a page:

1. FIFO (First In First Out)

Evict oldest page:

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

Problem: May evict frequently used pages

2. LRU (Least Recently Used)

Evict least recently used page:

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

Optimal: Minimizes page faults (but requires tracking access)

3. 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

4. Optimal (Theoretical)

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

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

Not practical: Requires knowledge of future

---

Examples

Virtual Memory Address Space

#include <stdio.h>
#include <stdlib.h>

int main() {
    // Virtual addresses (same for all processes)
    int x = 42;
    int *ptr = malloc(1000 * sizeof(int));
    
    printf("Virtual address of x: %p\n", (void*)&x);
    printf("Virtual address of ptr: %p\n", (void*)ptr);
    
    // Each process sees same virtual addresses
    // But mapped to different physical addresses
    return 0;
}

Page Fault Simulation

class VirtualMemory:
    def __init__(self, physical_memory_size, page_size=4096):
        self.physical_memory = {}  # frame → page
        self.page_table = {}  # page → frame or None
        self.swap_space = {}  # page → data on disk
        self.page_size = page_size
        self.max_frames = physical_memory_size // page_size
    
    def access(self, virtual_address):
        """Access virtual address, handle page fault if needed"""
        page_number = virtual_address // self.page_size
        
        # Check page table
        if page_number not in self.page_table:
            # Page fault: Page not in memory
            return self.handle_page_fault(page_number)
        
        frame_number = self.page_table[page_number]
        if frame_number is None:
            # Page fault: Page on disk
            return self.handle_page_fault(page_number)
        
        # Page in memory
        return self.physical_memory[frame_number]
    
    def handle_page_fault(self, page_number):
        """Handle page fault"""
        # Check if page exists on disk
        if page_number not in self.swap_space:
            raise SegmentationFault("Invalid page")
        
        # Find free frame
        frame_number = self.find_free_frame()
        if frame_number is None:
            # No free frame: Page replacement
            frame_number = self.evict_page()
        
        # Load page from disk
        page_data = self.swap_space[page_number]
        self.physical_memory[frame_number] = page_data
        
        # Update page table
        self.page_table[page_number] = frame_number
        
        return page_data
    
    def evict_page(self):
        """Evict page using LRU"""
        # Find least recently used frame
        lru_frame = min(
            self.physical_memory.keys(),
            key=lambda f: self.get_access_time(f)
        )
        
        # Get page number
        page_number = self.get_page_for_frame(lru_frame)
        
        # If modified, write to disk
        if self.is_modified(page_number):
            self.swap_space[page_number] = self.physical_memory[lru_frame]
        
        # Remove from memory
        del self.physical_memory[lru_frame]
        self.page_table[page_number] = None
        
        return lru_frame

---

Common Pitfalls

• Thrashing: Too many page faults, system spends time swapping. Fix: Increase RAM, reduce number of processes, optimize memory usage
• Not handling page faults: Assuming all memory always available. Fix: Handle page faults gracefully
• Poor page replacement: Evicting frequently used pages. Fix: Use LRU or similar algorithm
• Swap space too small: Can't swap enough pages. Fix: Allocate sufficient swap space
• Memory leaks: Processes not freeing memory. Fix: Proper memory management, garbage collection

---

Interview Questions

Beginner

Q: What is virtual memory and why is it used?

A:

Virtual memory is an abstraction that gives each process its own large address space, independent of physical RAM.

Why used:

1. Larger address space: Processes can use more memory than physically available
2. Memory protection: Each process has isolated address space
3. Simplified programming: Processes don't manage physical memory
4. Memory sharing: Processes can share code and data

How it works:

1. Virtual addresses: Process uses virtual addresses (0 to 2^32-1)
2. Page table: OS maps virtual pages to physical frames
3. Page fault: If page not in memory, load from disk
4. Swapping: Pages can be stored on disk when not in use

Example:

Process A: Virtual address 0x1000 → Physical address 0x5000
Process B: Virtual address 0x1000 → Physical address 0x8000

Same virtual address, different physical addresses

Benefits:

• Processes isolated (can't access each other's memory)
• Can use more memory than RAM (using disk)
• Easier programming (don't worry about physical addresses)

---

Intermediate

Q: Explain how page faults work and how the OS handles them.

A:

Page Fault occurs when process accesses page not in memory.

Process:

1. Process accesses virtual address

   Process tries to access 0x1234
   

2. Page table lookup

   Page number = 0x1
   Page table entry: Present bit = 0 (not in memory)
   

3. CPU generates page fault

   CPU interrupts, transfers control to OS
   

4. OS page fault handler

   def handle_page_fault(page_number):
       # Check if page exists on disk
       if page_number not in swap_space:
           raise SegmentationFault()
       
       # Find free frame
       frame = find_free_frame()
       if frame is None:
           frame = evict_page()  # Page replacement
       
       # Load page from disk
       page_data = swap_space[page_number]
       physical_memory[frame] = page_data
       
       # Update page table
       page_table[page_number] = frame
       page_table[page_number].present = 1
   

5. Resume process

   Process continues execution
   

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)

Performance:

• Page in memory: Fast (nanoseconds)
• Page on disk: Slow (milliseconds, disk I/O)

---

Senior

Q: Design a virtual memory system that handles 64-bit address spaces efficiently. How do you optimize page table size, TLB performance, and page replacement?

A:

class VirtualMemorySystem {
  private pageTable: MultiLevelPageTable;
  private tlb: TLB;
  private frameAllocator: FrameAllocator;
  private pageReplacer: PageReplacer;
  private swapSpace: SwapSpace;
  
  constructor() {
    // Multi-level page table for 64-bit
    this.pageTable = new MultiLevelPageTable({
      levels: 4, // 4-level page table
      pageSize: 4096
    });
    
    // TLB for fast translation
    this.tlb = new TLB({ size: 512 });
    
    this.frameAllocator = new FrameAllocator();
    this.pageReplacer = new PageReplacer({ algorithm: 'LRU' });
    this.swapSpace = new SwapSpace();
  }
  
  // 1. Address Translation with TLB
  translateAddress(virtualAddress: bigint): bigint {
    const { pageNumber, offset } = this.splitAddress(virtualAddress);
    
    // Check TLB first (fast path)
    const tlbEntry = this.tlb.lookup(pageNumber);
    if (tlbEntry) {
      return (tlbEntry.frameNumber * PAGE_SIZE) + offset;
    }
    
    // TLB miss: Check page table (slow path)
    const pte = this.pageTable.lookup(pageNumber);
    
    if (!pte.present) {
      // Page fault
      return this.handlePageFault(pageNumber, offset);
    }
    
    // Update TLB
    this.tlb.insert(pageNumber, pte.frameNumber);
    
    return (pte.frameNumber * PAGE_SIZE) + offset;
  }
  
  // 2. Multi-Level Page Table (64-bit)
  class MultiLevelPageTable {
    private rootTable: PageTableLevel;
    private levels: number = 4;
    
    lookup(pageNumber: bigint): PageTableEntry {
      // 64-bit: 4-level page table
      // 48 bits for virtual address (typical)
      // 12 bits offset, 9 bits per level (4 levels × 9 = 36 bits)
      
      const level1 = Number((pageNumber >> 39n) & 0x1FFn);
      const level2 = Number((pageNumber >> 30n) & 0x1FFn);
      const level3 = Number((pageNumber >> 21n) & 0x1FFn);
      const level4 = Number((pageNumber >> 12n) & 0x1FFn);
      
      // Traverse levels
      let table = this.rootTable;
      table = table[level1];
      if (!table) return null;
      
      table = table[level2];
      if (!table) return null;
      
      table = table[level3];
      if (!table) return null;
      
      return table[level4];
    }
  }
  
  // 3. TLB (Translation Lookaside Buffer)
  class TLB {
    private entries: Map<bigint, TLBEntry>;
    private maxSize: number;
    
    lookup(pageNumber: bigint): TLBEntry | null {
      return this.entries.get(pageNumber) || null;
    }
    
    insert(pageNumber: bigint, frameNumber: number): void {
      if (this.entries.size >= this.maxSize) {
        // Evict (LRU)
        const lru = this.findLRU();
        this.entries.delete(lru);
      }
      
      this.entries.set(pageNumber, {
        frameNumber,
        accessTime: Date.now()
      });
    }
  }
  
  // 4. Page Replacement (LRU with Clock)
  class PageReplacer {
    private accessTimes: Map<number, number>;
    private referenceBits: Map<number, boolean>;
    
    async evict(): Promise<number> {
      // Clock algorithm: Circular scan
      let frame = this.clockHand;
      
      while (true) {
        const refBit = this.referenceBits.get(frame);
        
        if (!refBit) {
          // Not recently used: Evict
          this.evictFrame(frame);
          this.clockHand = (frame + 1) % this.maxFrames;
          return frame;
        } else {
          // Recently used: Clear bit, continue
          this.referenceBits.set(frame, false);
          frame = (frame + 1) % this.maxFrames;
        }
      }
    }
  }
  
  // 5. Page Fault Handling
  async handlePageFault(pageNumber: bigint, offset: number): Promise<bigint> {
    // Check if page exists on disk
    if (!await this.swapSpace.hasPage(pageNumber)) {
      throw new SegmentationFault();
    }
    
    // Allocate frame
    let frameNumber = this.frameAllocator.allocate();
    if (frameNumber === null) {
      frameNumber = await this.pageReplacer.evict();
    }
    
    // Load page from disk
    await this.swapSpace.loadPage(pageNumber, frameNumber);
    
    // Update page table
    this.pageTable.update(pageNumber, {
      frameNumber,
      present: true,
      modified: false,
      referenced: true
    });
    
    // Update TLB
    this.tlb.insert(pageNumber, frameNumber);
    
    return (frameNumber * PAGE_SIZE) + offset;
  }
  
  // 6. Optimization: Large Pages
  enableLargePages(): void {
    // Use 2MB pages for large allocations
    // Reduces page table size, TLB entries
  }
  
  // 7. Optimization: Prefetching
  async prefetchPages(pageNumber: bigint): Promise<void> {
    // Prefetch adjacent pages
    const adjacentPages = [
      pageNumber - 1n,
      pageNumber + 1n
    ];
    
    for (const page of adjacentPages) {
      if (!this.pageTable.isPresent(page)) {
        await this.handlePageFault(page, 0);
      }
    }
  }
}

Features:

1. Multi-level page table: Efficient for 64-bit address spaces
2. TLB: Fast translation cache
3. Page replacement: LRU with clock algorithm
4. Large pages: 2MB pages for large allocations
5. Prefetching: Load adjacent pages proactively
6. Optimization: Minimize page table size, maximize TLB hit rate

---

Key Takeaways

• Virtual memory: Abstraction providing larger address space than physical RAM
• Address translation: Virtual addresses mapped to physical addresses via page table
• Page fault: Occurs when page not in memory, OS loads from disk
• Swapping: Pages moved between RAM and disk
• Page replacement: Evict pages when memory full (LRU, FIFO, Clock)
• TLB: Translation Lookaside Buffer caches page table entries for fast access
• Multi-level page table: Efficient for 64-bit address spaces
• Benefits: Larger address space, memory protection, simplified programming
• Best practices: Optimize TLB hit rate, use large pages, implement prefetching