Memory Management — Paging & Virtual Memory

Every process believes it has the entire address space to itself. This is a lie — a very useful lie. The OS and hardware work together to create the illusion of virtual memory, mapping each process's addresses to wherever they actually live in physical RAM.

The Problem: Multiple Processes Need Memory

If processes used physical addresses directly:

• Process A at 0x0–0x4000, Process B at 0x4000–0x8000 — they'd need to know each other's locations at compile time
• A buggy process could overwrite another's memory
• You couldn't run more programs than RAM can hold

Virtual memory solves all three.

Logical vs Physical Address

• Logical (virtual) address: what the program uses (0x1234 in process A's view)
• Physical address: the actual RAM address (0xABCD where it really lives)

The Memory Management Unit (MMU) — hardware inside the CPU — translates every logical address to a physical one on every memory access.

Paging

The OS divides:

• Virtual address space into fixed-size pages (typically 4 KB)
• Physical RAM into equal-size frames

The page table (per process) maps page numbers → frame numbers.

Page Table Entry (PTE) Fields

Bit	Meaning
Valid	Is this page currently in RAM?
Dirty	Has this page been written to?
Referenced	Has this page been accessed recently?
Protection	Read / Write / Execute permissions
Frame number	Where in RAM this page lives

The TLB — Translation Lookaside Buffer

Translating every address via the page table would be brutally slow (2 memory accesses per instruction). The TLB is a small, fast cache of recent page-to-frame translations inside the CPU.

TLBs hold 64–1024 entries. Because programs have temporal and spatial locality, hit rates are very high.

Page Faults

When a process accesses a page whose valid bit is 0 (not in RAM), the CPU raises a page fault:

1. OS traps the fault
2. Finds the page on disk (in the swap space)
3. Selects a free frame (evicting a page if RAM is full)
4. Loads the page into that frame
5. Updates the page table entry
6. Resumes the faulting instruction

This is slow (disk access = millions of CPU cycles), so minimising page faults is critical.

Virtual Memory — More Memory Than You Have

Virtual memory allows the total size of all processes to exceed physical RAM by keeping rarely used pages on disk.

Page Replacement Algorithms

When RAM is full and a new page must be loaded, the OS must evict an existing page. Which one?

FIFO (First-In, First-Out)

Evict the page that has been in RAM the longest.

Suffers from Belady's anomaly: more frames can cause more page faults (counterintuitive!).

Optimal (OPT)

Evict the page that won't be used for the longest time in the future. Theoretically perfect but requires future knowledge — only useful as a benchmark.

LRU (Least Recently Used)

Evict the page that was used least recently. Excellent in practice — approximates OPT.

Approximate LRU (clock algorithm):

• Each page has a reference bit, set to 1 on access
• A clock hand sweeps pages; if bit=1, clear it and move on; if bit=0, evict it

Memory-Mapped Files

The OS can map a file directly into a process's address space. Reading and writing the virtual addresses reads/writes the file — no explicit read()/write() calls needed.

Segmentation

An alternative to paging: divide the address space into variable-size segments (code, stack, heap, data). Each segment has a base address and a limit.

Modern OSes use paging as the primary mechanism but expose a segmented view at the programming model level (stack, heap, text, data sections).

Key Takeaways

• Virtual addresses are an illusion — the MMU maps them to physical frames on every access
• Paging uses fixed-size pages to avoid fragmentation and enable sparse address spaces
• The TLB caches recent translations; without it, virtual memory would be too slow
• Page faults are expensive — keep the working set in RAM
• LRU page replacement approximates optimal performance; the clock algorithm implements it cheaply