Virtual Memory & Paging: Abstracting Physical Memory

Understanding Virtual Memory

Virtual memory is one of the most important abstractions in modern operating systems, providing each process with its own private address space while efficiently sharing physical memory. Through paging, the OS can provide the illusion of large, contiguous memory spaces even when physical memory is limited and fragmented.

This abstraction enables memory protection, efficient memory sharing, and the ability to run programs larger than physical memory through demand paging and swapping.

Interactive Virtual Memory Explorer

Visualize address translation, page table lookups, TLB operations, and page fault handling:

Virtual Memory Translation Visualization

Choose your preferred learning mode

Simplified View - Best for Learning

• Clear, linear flow with animated arrows showing data path
• One component highlighted at a time for focused learning
• Step-by-step progression with pause/resume controls
• Perfect for understanding the basic translation process

Virtual Memory Translation - Simplified

Virtual Address:

Try:

Virtual Address

Hex: 0x1234

VPN: 1

Offset: 564

TLB Cache

VPN:1 → PFN:3

VPN:4 → PFN:7

VPN:8 → PFN:2

Page Table

VPN:0 → PFN:5

VPN:1 → PFN:3

VPN:2 → PFN:1

VPN:3 → Not Present

VPN:4 → PFN:7

VPN:5 → PFN:6

Physical Memory

Disk / Swap Space

Pages not in physical memory must be loaded from here (slow!)

Translation Steps

Click “Start” to begin the translation process

TLB (Fast Cache)

Translation Lookaside Buffer caches recent translations for instant access (~1 cycle)

Page Table (Slow)

Full mapping of virtual to physical pages, requires memory access (~100 cycles)

Page Fault (Very Slow)

When page not in memory, must load from disk (~1,000,000 cycles)

Virtual Memory Fundamentals

Key Concepts

Virtual Address Space: Each process sees a large, contiguous address space
Physical Memory: Actual RAM divided into fixed-size frames
Pages: Virtual memory divided into fixed-size blocks
Page Tables: Map virtual pages to physical frames
TLB: Cache for fast address translation

Address Translation

Virtual address → Physical address translation:

Virtual Address = VPN × Page Size + Offset

Where:

VPN = Virtual Page Number
Offset = Position within the page

Page Tables

Single-Level Page Table

Simple but memory-intensive for large address spaces:

typedef struct {
    uint32_t present    : 1;   // Page in memory?
    uint32_t writable   : 1;   // Read/write permission
    uint32_t user       : 1;   // User/kernel mode
    uint32_t accessed   : 1;   // Recently accessed?
    uint32_t dirty      : 1;   // Modified?
    uint32_t reserved   : 7;   // OS-specific flags
    uint32_t pfn        : 20;  // Physical frame number
} page_table_entry_t;

// Simple page table lookup
physical_addr_t translate(virtual_addr_t vaddr) {
    uint32_t vpn = vaddr >> PAGE_SHIFT;
    uint32_t offset = vaddr & PAGE_MASK;
    
    page_table_entry_t *pte = &page_table[vpn];
    
    if (!pte->present) {
        handle_page_fault(vaddr);
    }
    
    return (pte->pfn << PAGE_SHIFT) | offset;
}

Multi-Level Page Tables

Save memory by creating page tables on demand:

// x86-64 4-level page table
typedef struct {
    uint64_t entries[512];  // Each level has 512 entries
} page_table_t;

physical_addr_t translate_multilevel(virtual_addr_t vaddr) {
    // Extract indices for each level (9 bits each)
    uint64_t pml4_idx = (vaddr >> 39) & 0x1FF;
    uint64_t pdpt_idx = (vaddr >> 30) & 0x1FF;
    uint64_t pd_idx   = (vaddr >> 21) & 0x1FF;
    uint64_t pt_idx   = (vaddr >> 12) & 0x1FF;
    uint64_t offset   = vaddr & 0xFFF;
    
    // Walk the page table hierarchy
    page_table_t *pml4 = current_pml4;
    if (!pml4->entries[pml4_idx] & PRESENT) {
        handle_page_fault(vaddr);
    }
    
    page_table_t *pdpt = phys_to_virt(pml4->entries[pml4_idx] & FRAME_MASK);
    // Continue walking...
    
    return physical_address;
}

Page Table Entry Bits

Common flags in page table entries:

Bit	Name	Purpose
P	Present	Page is in physical memory
R/W	Read/Write	Write permission
U/S	User/Supervisor	Access level
A	Accessed	Used for page replacement
D	Dirty	Page has been modified
PWT	Write-Through	Cache policy
PCD	Cache Disable	Disable caching
G	Global	Don't flush from TLB

Translation Lookaside Buffer (TLB)

TLB Structure

Cache recent virtual→physical translations:

typedef struct {
    uint64_t vpn;       // Virtual page number
    uint64_t pfn;       // Physical frame number
    uint16_t asid;      // Address space ID
    uint8_t  valid;     // Entry valid?
    uint8_t  global;    // Global page?
    uint8_t  perms;     // Access permissions
} tlb_entry_t;

typedef struct {
    tlb_entry_t entries[TLB_SIZE];
    uint32_t replacement_counter;  // For LRU
} tlb_t;

TLB Lookup

Fast path for address translation:

physical_addr_t tlb_lookup(virtual_addr_t vaddr, uint16_t asid) {
    uint64_t vpn = vaddr >> PAGE_SHIFT;
    
    // Check TLB for translation
    for (int i = 0; i < TLB_SIZE; i++) {
        tlb_entry_t *entry = &tlb.entries[i];
        
        if (entry->valid && 
            entry->vpn == vpn && 
            (entry->global || entry->asid == asid)) {
            // TLB hit!
            entry->accessed = 1;  // Update for LRU
            return (entry->pfn << PAGE_SHIFT) | (vaddr & PAGE_MASK);
        }
    }
    
    // TLB miss - walk page tables
    return page_table_walk(vaddr);
}

TLB Management

// Insert new TLB entry
void tlb_insert(uint64_t vpn, uint64_t pfn, uint16_t asid, uint8_t perms) {
    // Find victim entry (LRU)
    int victim = find_lru_entry();
    
    tlb.entries[victim] = (tlb_entry_t){
        .vpn = vpn,
        .pfn = pfn,
        .asid = asid,
        .valid = 1,
        .perms = perms
    };
}

// Flush TLB entries
void tlb_flush(uint16_t asid) {
    for (int i = 0; i < TLB_SIZE; i++) {
        if (!tlb.entries[i].global && tlb.entries[i].asid == asid) {
            tlb.entries[i].valid = 0;
        }
    }
}

Page Faults

Types of Page Faults

Minor/Soft: Page in memory but not mapped
Major/Hard: Page must be loaded from disk
Invalid: Illegal memory access

Page Fault Handler

void handle_page_fault(virtual_addr_t fault_addr, uint32_t error_code) {
    // Decode fault type
    bool present = error_code & 0x1;
    bool write = error_code & 0x2;
    bool user = error_code & 0x4;
    
    if (!present) {
        // Page not present
        if (is_valid_address(fault_addr)) {
            // Demand paging - allocate and map
            physical_addr_t frame = allocate_frame();
            if (!frame) {
                // No free memory - evict a page
                frame = evict_page();
            }
            
            // Load page from disk if needed
            if (page_in_swap(fault_addr)) {
                load_from_swap(fault_addr, frame);
            } else {
                // First access - zero the page
                memset(phys_to_virt(frame), 0, PAGE_SIZE);
            }
            
            // Update page table
            map_page(fault_addr, frame, get_permissions(fault_addr));
            
        } else {
            // Segmentation fault
            terminate_process(SIGSEGV);
        }
    } else if (!write && is_cow_page(fault_addr)) {
        // Copy-on-write
        handle_cow_fault(fault_addr);
    } else {
        // Protection violation
        terminate_process(SIGSEGV);
    }
}

Page Replacement Algorithms

1. FIFO (First In, First Out)

typedef struct {
    page_t *pages[MAX_FRAMES];
    int head, tail;
} fifo_queue_t;

page_t* fifo_evict(fifo_queue_t *queue) {
    page_t *victim = queue->pages[queue->head];
    queue->head = (queue->head + 1) % MAX_FRAMES;
    return victim;
}

2. LRU (Least Recently Used)

typedef struct {
    page_t *page;
    uint64_t last_access;
} lru_entry_t;

page_t* lru_evict(lru_entry_t *entries, int count) {
    uint64_t oldest_time = UINT64_MAX;
    int victim_idx = 0;
    
    for (int i = 0; i < count; i++) {
        if (entries[i].last_access < oldest_time) {
            oldest_time = entries[i].last_access;
            victim_idx = i;
        }
    }
    
    return entries[victim_idx].page;
}

3. Clock Algorithm (Second Chance)

typedef struct {
    page_t *pages[MAX_FRAMES];
    uint8_t reference_bits[MAX_FRAMES];
    int hand;
} clock_t;

page_t* clock_evict(clock_t *clock) {
    while (1) {
        if (clock->reference_bits[clock->hand] == 0) {
            // Found victim
            page_t *victim = clock->pages[clock->hand];
            clock->hand = (clock->hand + 1) % MAX_FRAMES;
            return victim;
        }
        
        // Give second chance
        clock->reference_bits[clock->hand] = 0;
        clock->hand = (clock->hand + 1) % MAX_FRAMES;
    }
}

Memory Mapping

mmap() Implementation

void* mmap(void *addr, size_t length, int prot, int flags, 
           int fd, off_t offset) {
    // Allocate virtual address range
    virtual_addr_t vaddr = allocate_virtual_range(addr, length);
    
    // Create mapping structure
    vm_area_t *vma = create_vma(vaddr, length, prot, flags);
    
    if (flags & MAP_ANONYMOUS) {
        // Anonymous mapping - no backing file
        vma->type = VMA_ANON;
    } else {
        // File-backed mapping
        vma->type = VMA_FILE;
        vma->file = get_file(fd);
        vma->offset = offset;
    }
    
    // Don't allocate physical memory yet (demand paging)
    if (!(flags & MAP_POPULATE)) {
        return (void*)vaddr;
    }
    
    // Pre-populate pages if requested
    for (size_t i = 0; i < length; i += PAGE_SIZE) {
        allocate_and_map_page(vaddr + i, prot);
    }
    
    return (void*)vaddr;
}

Shared Memory

// Create shared memory segment
int shmget(key_t key, size_t size, int flags) {
    shm_segment_t *segment = find_segment(key);
    
    if (!segment && (flags & IPC_CREAT)) {
        segment = allocate_segment(size);
        segment->key = key;
        segment->size = size;
        segment->pages = allocate_frames(size / PAGE_SIZE);
    }
    
    return segment ? segment->id : -1;
}

// Attach shared memory
void* shmat(int shmid, const void *addr, int flags) {
    shm_segment_t *segment = get_segment(shmid);
    virtual_addr_t vaddr = allocate_virtual_range(addr, segment->size);
    
    // Map shared pages into process address space
    for (size_t i = 0; i < segment->size; i += PAGE_SIZE) {
        map_page(vaddr + i, segment->pages[i / PAGE_SIZE], 
                flags & SHM_RDONLY ? PROT_READ : PROT_READ | PROT_WRITE);
    }
    
    return (void*)vaddr;
}

Copy-on-Write (COW)

Implementation

// Fork with COW
pid_t fork(void) {
    process_t *parent = current_process;
    process_t *child = create_process();
    
    // Copy page tables, marking pages as COW
    for (each_vma in parent->vmas) {
        vm_area_t *new_vma = copy_vma(each_vma);
        
        for (each_page in each_vma) {
            page_table_entry_t *parent_pte = get_pte(parent, page_addr);
            page_table_entry_t *child_pte = get_pte(child, page_addr);
            
            // Share the physical page
            *child_pte = *parent_pte;
            
            // Mark both as read-only for COW
            parent_pte->writable = 0;
            parent_pte->cow = 1;
            child_pte->writable = 0;
            child_pte->cow = 1;
            
            // Increment reference count
            increment_page_refcount(parent_pte->pfn);
        }
    }
    
    return child->pid;
}

// Handle COW fault
void handle_cow_fault(virtual_addr_t addr) {
    page_table_entry_t *pte = get_pte(current_process, addr);
    physical_addr_t old_frame = pte->pfn << PAGE_SHIFT;
    
    if (get_page_refcount(pte->pfn) == 1) {
        // We're the only user - just make writable
        pte->writable = 1;
        pte->cow = 0;
    } else {
        // Allocate new page and copy
        physical_addr_t new_frame = allocate_frame();
        memcpy(phys_to_virt(new_frame), phys_to_virt(old_frame), PAGE_SIZE);
        
        // Update page table
        pte->pfn = new_frame >> PAGE_SHIFT;
        pte->writable = 1;
        pte->cow = 0;
        
        // Decrement old page refcount
        decrement_page_refcount(old_frame >> PAGE_SHIFT);
    }
    
    // Flush TLB entry
    tlb_flush_page(addr);
}

Swap Space Management

Swap Operations

// Swap out a page
void swap_out_page(page_t *page) {
    // Find free swap slot
    swap_slot_t slot = allocate_swap_slot();
    
    // Write page to swap
    write_to_swap(slot, page->data);
    
    // Update page table entry
    page_table_entry_t *pte = page->pte;
    pte->present = 0;
    pte->swap_slot = slot;
    
    // Free physical frame
    free_frame(page->frame);
}

// Swap in a page
void swap_in_page(virtual_addr_t vaddr) {
    page_table_entry_t *pte = get_pte(current_process, vaddr);
    swap_slot_t slot = pte->swap_slot;
    
    // Allocate physical frame
    physical_addr_t frame = allocate_frame();
    
    // Read from swap
    read_from_swap(slot, phys_to_virt(frame));
    
    // Update page table
    pte->present = 1;
    pte->pfn = frame >> PAGE_SHIFT;
    pte->swap_slot = 0;
    
    // Free swap slot
    free_swap_slot(slot);
}

Performance Optimizations

1. Huge Pages

Reduce TLB pressure with larger pages:

// Allocate 2MB huge page
void* alloc_huge_page(size_t size) {
    if (size % HUGE_PAGE_SIZE != 0) {
        return NULL;
    }
    
    virtual_addr_t vaddr = allocate_virtual_range(NULL, size);
    
    for (size_t i = 0; i < size; i += HUGE_PAGE_SIZE) {
        physical_addr_t frame = allocate_huge_frame();
        map_huge_page(vaddr + i, frame);
    }
    
    return (void*)vaddr;
}

2. NUMA Awareness

// Allocate memory on specific NUMA node
void* numa_alloc(size_t size, int node) {
    virtual_addr_t vaddr = allocate_virtual_range(NULL, size);
    
    for (size_t i = 0; i < size; i += PAGE_SIZE) {
        physical_addr_t frame = allocate_frame_on_node(node);
        map_page(vaddr + i, frame, PROT_READ | PROT_WRITE);
    }
    
    return (void*)vaddr;
}

3. Prefaulting

// Prefault pages to avoid page faults
void prefault_range(void *addr, size_t size) {
    for (size_t i = 0; i < size; i += PAGE_SIZE) {
        volatile char *p = (char*)addr + i;
        *p = *p;  // Touch the page
    }
}

Security Features

1. ASLR (Address Space Layout Randomization)

virtual_addr_t randomize_mmap_base(void) {
    uint64_t random = get_random_long();
    return TASK_UNMAPPED_BASE + (random % ASLR_RANGE);
}

2. NX/DEP (No Execute)

void mark_pages_nx(virtual_addr_t start, size_t len) {
    for (size_t i = 0; i < len; i += PAGE_SIZE) {
        page_table_entry_t *pte = get_pte(current_process, start + i);
        pte->executable = 0;
    }
}

3. Guard Pages

void* alloc_with_guard(size_t size) {
    // Allocate extra pages for guards
    size_t total_size = size + 2 * PAGE_SIZE;
    virtual_addr_t vaddr = allocate_virtual_range(NULL, total_size);
    
    // Map guard pages as non-accessible
    map_page(vaddr, 0, PROT_NONE);
    map_page(vaddr + size + PAGE_SIZE, 0, PROT_NONE);
    
    // Map data pages
    for (size_t i = PAGE_SIZE; i < size + PAGE_SIZE; i += PAGE_SIZE) {
        physical_addr_t frame = allocate_frame();
        map_page(vaddr + i, frame, PROT_READ | PROT_WRITE);
    }
    
    return (void*)(vaddr + PAGE_SIZE);
}

Common Issues and Solutions

1. TLB Shootdown

void tlb_shootdown(cpu_set_t *cpus, virtual_addr_t addr) {
    // Send IPI to other CPUs
    for_each_cpu(cpu, cpus) {
        if (cpu != current_cpu()) {
            send_ipi(cpu, IPI_TLB_FLUSH, addr);
        }
    }
    
    // Flush local TLB
    tlb_flush_page(addr);
    
    // Wait for acknowledgment
    wait_for_tlb_flush_complete(cpus);
}

2. Memory Pressure

void handle_memory_pressure(void) {
    // Try to free clean pages first
    reclaim_clean_pages();
    
    // Compact memory to reduce fragmentation
    compact_memory();
    
    // Start swapping if needed
    if (free_memory() < MIN_FREE_MEMORY) {
        start_kswapd();
    }
    
    // Last resort - OOM killer
    if (free_memory() < CRITICAL_MEMORY) {
        oom_kill_process();
    }
}

Understanding virtual memory connects to:

CPU Cache Lines: Cache interactions with virtual memory
NUMA Architecture: Memory locality in NUMA systems
Memory Access Patterns: Optimizing for virtual memory
Memory Protection: Security through isolation
Process Management: Address space creation

Conclusion

Virtual memory is a cornerstone of modern operating systems, enabling efficient and secure memory management through hardware-software cooperation. The combination of paging, TLBs, and demand loading allows systems to provide each process with a large, isolated address space while making efficient use of limited physical memory. Understanding these mechanisms is crucial for system programming and performance optimization.

Table of Contents