Memory Management & Virtual Memory

How a process sees memory#

Every process gets its own virtual address space — it believes it has a large, private, contiguous block of memory. A typical layout:

high addresses
┌──────────────────────┐
│ stack  ↓             │  function calls, local variables (per thread)
│                      │
│ heap   ↑             │  dynamic allocations (objects, malloc, new)
├──────────────────────┤
│ data / BSS           │  global and static variables
├──────────────────────┤
│ text (code)          │  the program's machine instructions (read-only)
└──────────────────────┘
low addresses

Stack vs heap#

A recursive function without a base case fills the stack — that's the "stack overflow" error (and Python's RecursionError, which guards against it).

Virtual memory and paging#

Programs use virtual addresses. The CPU's memory management unit (MMU) translates them to physical addresses in RAM using page tables maintained by the OS.

Memory is divided into fixed-size blocks:

• Pages — blocks of virtual memory (commonly 4 KB).
• Frames — blocks of physical memory of the same size.

A virtual address splits into a page number and an offset within the page:

PAGE_SIZE = 4096
page_table = {0: 5, 1: 9, 2: 3}        # virtual page → physical frame (page 3 isn't in RAM)

def translate(virtual_address: int) -> str:
    page, offset = divmod(virtual_address, PAGE_SIZE)
    if page not in page_table:
        return f"{virtual_address:>6} → page {page}, offset {offset}: PAGE FAULT"
    physical = page_table[page] * PAGE_SIZE + offset
    return f"{virtual_address:>6} → page {page}, offset {offset} → frame {page_table[page]} → {physical}"

for address in (100, 8200, 13000):
    print(translate(address))

Output:

   100 → page 0, offset 100 → frame 5 → 20580
  8200 → page 2, offset 8 → frame 3 → 12296
 13000 → page 3, offset 712: PAGE FAULT

Because translation goes through page tables, each process can use the same virtual addresses without clashing, and the OS can protect pages (read-only code, no-execute stacks).

The TLB#

Looking up page tables on every memory access would be slow, so CPUs cache recent translations in the Translation Lookaside Buffer (TLB). Programs with good locality (accessing nearby memory) get more TLB and CPU-cache hits — one reason arrays are faster to iterate than linked lists.

Page faults#

A page fault occurs when a program touches a page that isn't currently mapped in RAM. The OS then:

1. Finds the page on disk (swap or the original file).
2. Picks a free frame — or evicts a page if memory is full.
3. Loads the page, updates the page table and resumes the program.

Page faults that need the disk are thousands of times slower than RAM access. When a system spends most of its time handling page faults, it is thrashing — everything grinds to a halt.

Virtual memory also enables:

• Lazy loading — pages are loaded only when first used.
• Copy-on-write — after fork(), parent and child share pages until one writes.
• Memory-mapped files (mmap) — file contents appear as memory.
• Overcommit — on Linux, if processes actually use more memory than available, the OOM killer terminates one (a common reason containers die with exit code 137).

Page replacement algorithms#

When RAM is full, which page should be evicted?

Simulating them on a classic reference string with 3 frames:

from collections import OrderedDict

def count_faults(pages, frames, policy):
    memory, faults = OrderedDict(), 0
    for i, page in enumerate(pages):
        if page in memory:
            if policy == "LRU":
                memory.move_to_end(page)          # mark as recently used
            continue
        faults += 1
        if len(memory) == frames:
            if policy == "OPT":
                future = pages[i + 1:]
                victim = max(memory, key=lambda p: future.index(p) if p in future else len(future) + 1)
                del memory[victim]
            else:
                memory.popitem(last=False)        # FIFO: oldest loaded; LRU: least recently used
        memory[page] = True
    return faults

refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
for policy in ("FIFO", "LRU", "OPT"):
    print(f"{policy:<4} page faults: {count_faults(refs, 3, policy)}")

belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print("FIFO with 3 frames:", count_faults(belady, 3, "FIFO"))
print("FIFO with 4 frames:", count_faults(belady, 4, "FIFO"))

Output:

FIFO page faults: 15
LRU  page faults: 12
OPT  page faults: 9
FIFO with 3 frames: 9
FIFO with 4 frames: 10

The last two lines show Belady's anomaly: with FIFO, adding memory caused more page faults. LRU and OPT never suffer from it. The same eviction ideas power application caches — see the Caching tutorial's LRU lesson.

Segmentation and fragmentation#

• External fragmentation — enough free memory in total, but not in one contiguous block. Paging avoids it.
• Internal fragmentation — wasted space inside an allocated block (a 4 KB page holding 100 bytes).
• Segmentation divides memory into logical segments (code, data, stack); modern systems mostly rely on paging.

Common mistakes#

• Saying "virtual memory = swap" — virtual memory is the address translation system; swap is just disk space it can use.
• Ignoring memory limits in containers — the app sees the host's memory but gets OOM-killed at the container limit.
• Unbounded in-memory caches — they eventually trigger the OOM killer.

Key takeaways#

• Each process has a private virtual address space with stack, heap, data and code.
• The MMU translates virtual pages to physical frames using page tables and the TLB.
• Page faults load missing pages; too many cause thrashing.
• LRU approximations are used in practice; FIFO can show Belady's anomaly.