Virtual memory and paging

WHY does virtual memory exist?

Three problems it solves at once:

1. Not enough RAM. Programs may need more memory than the physical RAM installed. Virtual memory lets us pretend RAM is as big as the disk by swapping inactive pages to disk.
2. Multiple programs, one RAM. If program A used physical address 0x4000 directly and program B also wanted 0x4000, they'd collide. Virtual memory gives each process its own address space — isolation & protection.
3. Fragmentation. Programs need contiguous chunks; RAM gets chopped into gaps over time. Paging removes the "must be contiguous in physical RAM" constraint.

WHAT are the key objects?

HOW does an address get translated? (derive it)

Let page size be $P = 2^p$ bytes. A virtual address of $n$ bits splits into two parts.

Why split? Because within a single page, virtual and physical addresses agree exactly — moving a page to a frame keeps the internal layout identical. Only which page/frame differs. So:

• The low $p$ bits = the offset inside the page. These are never translated.
• The high $n - p$ bits = the Virtual Page Number (VPN). Only this gets mapped.

$\text{VA} = \underbrace{\text{VPN}}_{n-p \text{ bits}} \;\Vert\; \underbrace{\text{offset}}_{p \text{ bits}}$

Deriving the split arithmetically. For a virtual address $A$: $\text{offset} = A \bmod 2^p = A \,\&\, (2^p - 1), \qquad \text{VPN} = \left\lfloor \frac{A}{2^p} \right\rfloor = A \gg p$

Why the mask/shift? Dividing by $2^p$ throws away the low $p$ bits (giving the page number); the remainder is exactly what's left inside the page.

Then look up the frame: $\text{PFN} = \text{PageTable}[\text{VPN}]$ $\text{PA} = (\text{PFN} \times 2^p) + \text{offset} = (\text{PFN} \ll p)\,|\,\text{offset}$

Why multiply PFN by $2^p$? Because frame number $f$ starts at physical byte $f \cdot P$. Add the untouched offset to land on the exact byte.

The TLB — why translation isn't slow

Effective access time (derive it). Let $t_{TLB}$ = TLB lookup time, $t_{mem}$ = memory access, hit ratio $h$. On a hit we pay TLB + memory. On a miss we pay TLB + page-table walk (one memory access, single-level) + the real memory access: $\text{EAT} = h\,(t_{TLB} + t_{mem}) + (1-h)\,(t_{TLB} + t_{mem} + t_{mem})$ $= t_{TLB} + t_{mem} + (1-h)\,t_{mem}$

Why the last term? The miss penalty is exactly one extra $t_{mem}$ for the table walk, weighted by miss probability $(1-h)$.

Worked examples

Common mistakes (steel-manned)

Recall

Connections

• Memory hierarchy — VM is the level between RAM and disk (RAM caches disk pages).
• CPU caches — TLB is a specialized cache; VA vs PA affects VIPT/PIPT cache indexing.
• Page replacement algorithms — LRU/Clock decide which frame to evict on a fault.
• Multi-level page tables — the fix for gigantic single-level tables.
• Locality of reference — the reason TLBs and demand paging actually work.
• Segmentation — the alternative/complement to paging.

Concept Map

Hinglish (regional understanding)