Topic Overview

Memory Management

Learn how operating systems manage memory: allocation, deallocation, protection, virtual memory, and memory hierarchy.

Memory management is a critical function of operating systems, responsible for allocating and deallocating memory, protecting memory spaces, and providing the abstraction of virtual memory to processes.

Memory Management Goals

  1. Allocation: Assign memory to processes
  2. Protection: Prevent processes from accessing each other's memory
  3. Sharing: Allow processes to share memory when needed
  4. Virtualization: Provide virtual memory abstraction
  5. Efficiency: Minimize fragmentation and overhead

Physical vs Virtual Memory

Physical Memory

Definition: Actual RAM hardware in the system.

Characteristics:

  • Limited size (e.g., 8GB, 16GB)
  • Directly addressable by CPU
  • Shared by all processes
  • Managed by OS

Virtual Memory

Definition: Abstraction that gives each process its own address space.

Characteristics:

  • Appears larger than physical memory
  • Each process has its own virtual address space
  • Mapped to physical memory by OS
  • Enables processes to use more memory than available RAM

Memory Allocation

Contiguous Allocation

Simple approach: Allocate contiguous blocks of memory.

Problems:

  • External fragmentation: Free memory scattered in small chunks
  • Internal fragmentation: Allocated block larger than needed

Paging

Concept: Divide memory into fixed-size pages (typically 4KB).

How it works:

  1. Physical memory divided into frames
  2. Virtual memory divided into pages
  3. Pages mapped to frames (not necessarily contiguous)
  4. Page table stores page → frame mappings

Benefits:

  • No external fragmentation
  • Simple allocation (allocate pages)
  • Efficient swapping to disk

Segmentation

Concept: Divide memory into variable-size segments (code, data, stack).

How it works:

  1. Process memory divided into logical segments
  2. Each segment has base address and limit
  3. Segment table stores segment information

Benefits:

  • Logical organization (code, data, stack)
  • Easy sharing (share code segment)
  • Protection per segment

Problems:

  • External fragmentation
  • Complex management

Page Table

Purpose: Maps virtual pages to physical frames.

Structure:

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

Example:

Virtual Address: 0x1234 (page 1, offset 0x234)
  Page Table Entry 1 → Frame 5
  Physical Address: 0x5234 (frame 5, offset 0x234)

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)
  • Referenced: Page recently accessed
  • Protection: Read, write, execute permissions

Memory Protection

Protection Mechanisms

  1. Base and Limit Registers

    Process memory: [Base, Base + Limit]
CPU checks: Base <= address < Base + Limit

  2. Page Table Protection

    Page Table Entry: [Frame | Protection Bits]
Protection: Read, Write, Execute

  3. Segmentation Protection

    Segment Table: [Base | Limit | Protection]
Protection: Code (execute), Data (read/write)

Memory Access Violation

Process tries to access memory outside its address space:
  → Segmentation fault / Access violation
  → OS terminates process

Virtual Memory

Concept

Virtual memory allows processes to use more memory than physically available by using disk as extension of RAM.

How it works:

  1. Process uses virtual addresses
  2. OS maps virtual pages to physical frames
  3. If page not in memory: Page fault → Load from disk
  4. If memory full: Page replacement → Swap page to disk

Page Fault

Page fault occurs when process accesses page not in memory:

1. Process accesses virtual address
2. Page table: Present bit = 0 (page not in memory)
3. CPU generates page fault
4. OS handles page fault:
   a. Check if page exists on disk
   b. Find free frame (or evict page)
   c. Load page from disk to frame
   d. Update page table
   e. Resume process

Page Replacement Algorithms

When memory is full, OS must evict a page:

  1. FIFO (First In First Out): Evict oldest page
  2. LRU (Least Recently Used): Evict least recently used page
  3. Optimal: Evict page that won't be used for longest time (theoretical)
  4. Clock: Circular buffer, evict page not recently used

Examples

Memory Allocation (C)

#include <stdlib.h>

// Dynamic memory allocation
int *array = (int*)malloc(100 * sizeof(int));
if (array == NULL) {
    // Allocation failed
    exit(1);
}

// Use memory
for (int i = 0; i < 100; i++) {
    array[i] = i;
}

// Free memory
free(array);
array = NULL;

Virtual Memory Address Space

#include <stdio.h>
#include <unistd.h>

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

Page Table Simulation

class PageTable:
    def __init__(self, page_size=4096):
        self.page_size = page_size
        self.table = {}  # page_number → frame_number
        self.frames = {}  # frame_number → page_number
    
    def translate(self, virtual_address):
        """Translate virtual address to physical address"""
        page_number = virtual_address // self.page_size
        offset = virtual_address % self.page_size
        
        if page_number not in self.table:
            # Page fault
            frame_number = self.allocate_frame(page_number)
            self.table[page_number] = frame_number
        
        frame_number = self.table[page_number]
        physical_address = (frame_number * self.page_size) + offset
        
        return physical_address
    
    def allocate_frame(self, page_number):
        """Allocate frame for page"""
        # Find free frame
        for frame in range(1000):  # Assume 1000 frames
            if frame not in self.frames:
                self.frames[frame] = page_number
                return frame
        
        # No free frame: page replacement needed
        return self.replace_page(page_number)
    
    def replace_page(self, new_page):
        """Replace page using LRU"""
        # Find least recently used frame
        lru_frame = min(self.frames.keys(), key=lambda f: self.get_access_time(f))
        old_page = self.frames[lru_frame]
        
        # Swap out old page
        del self.table[old_page]
        
        # Allocate to new page
        self.frames[lru_frame] = new_page
        return lru_frame

Common Pitfalls

  • Memory leaks: Not freeing allocated memory. Fix: Always free memory, use smart pointers
  • Dangling pointers: Accessing freed memory. Fix: Set pointers to NULL after free
  • Buffer overflow: Writing beyond allocated memory. Fix: Check bounds, use safe functions
  • Double free: Freeing memory twice. Fix: Set pointer to NULL after free
  • Not handling page faults: Assuming all memory is always available. Fix: Handle page faults gracefully
  • Fragmentation: Not considering fragmentation effects. Fix: Use paging, compaction

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 address space, independent of physical memory.

Why used:

  1. Larger address space: Processes can use more memory than physically available
  2. Protection: Each process has isolated address space
  3. Simplification: Processes don't need to manage physical memory
  4. Sharing: Processes can share memory (code, libraries)

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: OS can swap pages to disk when memory is full

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 paging works. What is a page table and how does address translation work?

A:

Paging divides memory into fixed-size pages (typically 4KB).

How it works:

  1. Physical memory: Divided into frames (fixed-size blocks)
  2. Virtual memory: Divided into pages (same size as frames)
  3. Page table: Maps virtual pages to physical frames
  4. Address translation: Convert virtual address to physical address

Address Translation:

Virtual Address: [Page Number | Offset]
  Example: 0x1234
    Page Number: 0x1 (page 1)
    Offset: 0x234 (offset within page)

Page Table Lookup:
  Page Table[1] → Frame 5

Physical Address: [Frame Number | Offset]
  Frame Number: 5
  Offset: 0x234 (same)
  Physical Address: 0x5234

Page Table Structure:

Page Table Entry:
  [Frame Number | Present | Modified | Referenced | Protection]

Flags:
  - Present: Page in memory (1) or on disk (0)
  - Modified: Page has been written to (dirty)
  - Referenced: Page recently accessed
  - Protection: Read, Write, Execute permissions

Page Fault:

1. Process accesses virtual address
2. Page table: Present bit = 0 (page not in memory)
3. CPU generates page fault
4. OS handles:
   a. Check if page exists on disk
   b. Find free frame (or evict page)
   c. Load page from disk to frame
   d. Update page table (Present = 1)
   e. Resume process

Benefits:

  • No external fragmentation
  • Simple allocation (allocate pages)
  • Efficient swapping to disk

Senior

Q: Design a memory management system for an operating system that supports 64-bit address spaces, handles page faults efficiently, and implements page replacement. How do you optimize for performance?

A:

class MemoryManager {
  private pageTable: PageTable;
  private frameAllocator: FrameAllocator;
  private pageReplacer: PageReplacer;
  private swapSpace: SwapSpace;
  private tlb: TLB; // Translation Lookaside Buffer
  
  constructor() {
    this.pageTable = new PageTable();
    this.frameAllocator = new FrameAllocator();
    this.pageReplacer = new PageReplacer({ algorithm: 'LRU' });
    this.swapSpace = new SwapSpace();
    this.tlb = new TLB({ size: 64 }); // 64-entry TLB
  }
  
  // 1. Address Translation with TLB
  translateAddress(virtualAddress: number): number {
    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. Page Fault Handling
  async handlePageFault(pageNumber: number, offset: number): Promise<number> {
    // Check if page exists on disk
    const pageOnDisk = await this.swapSpace.hasPage(pageNumber);
    
    if (!pageOnDisk) {
      // Invalid address: Segmentation fault
      throw new SegmentationFault();
    }
    
    // Allocate frame
    let frameNumber = this.frameAllocator.allocate();
    
    if (frameNumber === null) {
      // No free frame: Page replacement
      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;
  }
  
  // 3. Page Replacement (LRU)
  class PageReplacer {
    private accessTimes: Map<number, number>; // frame → last access time
    
    async evict(): Promise<number> {
      // Find least recently used frame
      let lruFrame = null;
      let lruTime = Infinity;
      
      for (const [frame, time] of this.accessTimes.entries()) {
        if (time < lruTime) {
          lruTime = time;
          lruFrame = frame;
        }
      }
      
      // Get page number
      const pageNumber = this.pageTable.getPage(lruFrame);
      
      // If modified, write to disk
      const pte = this.pageTable.lookup(pageNumber);
      if (pte.modified) {
        await this.swapSpace.savePage(pageNumber, lruFrame);
      }
      
      // Update page table
      this.pageTable.update(pageNumber, { present: false });
      
      // Remove from access times
      this.accessTimes.delete(lruFrame);
      
      return lruFrame;
    }
    
    recordAccess(frameNumber: number): void {
      this.accessTimes.set(frameNumber, Date.now());
    }
  }
  
  // 4. TLB (Translation Lookaside Buffer)
  class TLB {
    private entries: Map<number, number>; // page → frame
    private maxSize: number;
    
    lookup(pageNumber: number): number | null {
      return this.entries.get(pageNumber) || null;
    }
    
    insert(pageNumber: number, frameNumber: number): void {
      if (this.entries.size >= this.maxSize) {
        // Evict oldest entry (FIFO)
        const firstKey = this.entries.keys().next().value;
        this.entries.delete(firstKey);
      }
      
      this.entries.set(pageNumber, frameNumber);
    }
  }
  
  // 5. Multi-level Page Tables (64-bit)
  class PageTable {
    private rootTable: PageTableLevel; // Top level
    
    lookup(pageNumber: number): PageTableEntry {
      // 64-bit: 4-level page table
      const level1 = (pageNumber >> 39) & 0x1FF;
      const level2 = (pageNumber >> 30) & 0x1FF;
      const level3 = (pageNumber >> 21) & 0x1FF;
      const level4 = (pageNumber >> 12) & 0x1FF;
      
      // Traverse page table levels
      let table = this.rootTable;
      table = table[level1];
      table = table[level2];
      table = table[level3];
      
      return table[level4];
    }
  }
  
  // 6. Performance Optimization
  optimizePerformance(): void {
    // Prefetch: Load pages before needed
    this.enablePrefetching();
    
    // Large pages: Use 2MB pages for large allocations
    this.enableLargePages();
    
    // NUMA awareness: Allocate frames from local NUMA node
    this.enableNUMA();
  }
}

Features:

  1. TLB: Fast address translation cache
  2. Multi-level page tables: Efficient for 64-bit address spaces
  3. Page replacement: LRU algorithm for eviction
  4. Swap space: Disk storage for pages
  5. Performance: Prefetching, large pages, NUMA awareness

Key Takeaways

  • Memory management: Allocation, protection, sharing, virtualization
  • Virtual memory: Abstraction that gives each process its own address space
  • Paging: Divide memory into fixed-size pages, map to frames
  • Page table: Maps virtual pages to physical frames
  • Page fault: Occurs when page not in memory, OS loads from disk
  • Page replacement: Evict pages when memory is full (LRU, FIFO, etc.)
  • TLB: Translation Lookaside Buffer caches page table entries for fast access
  • Protection: Base/limit registers, page table protection, segmentation protection
  • Best practices: Handle page faults, implement efficient replacement, use TLB, optimize for performance

About the author

InterviewCrafted helps you master system design with patience. We believe in curiosity-led engineering, reflective writing, and designing systems that make future changes feel calm.