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