Noesis
4.1.14Computer Architecture (Deep)

Virtual memory — concept, page table, virtual-to-physical translation

2,280 words10 min readdifficulty · medium6 backlinks
🇮🇳 Yeh note Hinglish mein padho →

WHY does virtual memory exist?

Three concrete problems it solves:

  1. Isolation / protection — Process A must not be able to read or smash Process B's memory. If both used raw physical addresses, address 0x4000 would mean the same byte for both → chaos.
  2. Relocation / fragmentation — A program shouldn't care where in RAM it lands. We want to load it into any free chunks, even non-contiguous ones.
  3. Over-commitment — We want to run programs needing more memory than physically exists, by parking unused parts on disk (swap).

WHAT are the key objects?

HOW does an address get split?

The genius trick: the offset within a page is identical in virtual and physical space, because pages and frames are the same size and aligned. Only the page number part needs translating.

Derivation that the offset is preserved. Let virtual address VA=VPN⋅2p+off\text{VA} = \text{VPN}\cdot 2^p + \text{off} with 0≤off<2p0 \le \text{off} < 2^p. Translation replaces the page: PA=PFN⋅2p+off\text{PA} = \text{PFN}\cdot 2^p + \text{off}. The same off appears, so we never translate offset bits. ∎

Figure — Virtual memory — concept, page table, virtual-to-physical translation

Forecast-then-Verify

Verify, step by step:

  • Page size =4 KiB=212= 4\text{ KiB} = 2^{12} → offset = 12 bits. Why? You need exactly 12 bits to address every byte inside one 4096-byte page.
  • VPN bits =32−12=20= 32 - 12 = 20. Why? The remaining high bits identify the page.
  • Entries =220=1,048,576= 2^{20} = 1{,}048{,}576. Why? One entry per possible virtual page.
  • If each entry is 4 bytes → table size =220×4=4 MiB= 2^{20}\times 4 = 4\text{ MiB} per process. Why this matters: this huge cost is exactly why real systems use multi-level page tables (only allocate sub-tables for pages actually used).

Worked translation examples

Common mistakes (Steel-manned)

Active recall

Recall Quick self-test (cover answers)
  • Q: Which part of the address is NOT translated? A: the offset.
  • Q: Page size 2p2^p → how many offset bits? A: pp bits.
  • Q: What triggers a page fault? A: accessing a page whose valid bit is 0.
  • Q: Why per-process page tables? A: isolation — same VA maps to different physical frames per process.
  • Q: Final PA formula? A: PA=PFN⋅2p+offset\text{PA} = \text{PFN}\cdot 2^p + \text{offset}.
Recall Feynman: explain to a 12-year-old

Imagine a huge hotel. Every guest is told "your room is Room 1" — they all think they're in Room 1. But the hotel has a secret notebook (the page table) that says "Guest Alice's Room 1 is really physical Room 305; Bob's Room 1 is really Room 712." When Alice asks for something on her "Room 1, shelf 7", the front desk looks up the notebook, sends her to the real room 305, and shelf 7 is still shelf 7 inside that room (the offset doesn't change). If the real stuff was put in the basement storage (disk), the desk runs to fetch it first (page fault) and updates the notebook. That way everyone feels like they own the whole hotel, nobody walks into anyone else's room, and the hotel can hold more "rooms" than it physically has by stashing extras in storage.

The 80/20 — what to truly internalize

  1. Offset bits =log⁡2(page size)= \log_2(\text{page size}); it's never translated.
  2. PA=PFN⋅pagesize+offset\text{PA} = \text{PFN}\cdot\text{pagesize} + \text{offset}.
  3. Page table is per process (isolation) and lives in RAM (→ TLB cache).
  4. Invalid entry → page fault → OS loads from disk → retry.

Connections

Virtual memory gives each process the illusion of
a large, private, contiguous address space starting at 0.
The unit of the virtual address space is called a
page.
The unit of physical RAM it maps to is called a
frame (page frame).
A page table maps
virtual page number (VPN) → physical frame number (PFN).
The hardware that performs translation on every access is the
MMU (Memory Management Unit).
For page size 2^p, the number of offset bits is
p.
The part of a virtual address that is NOT translated is
the offset.
Final physical address formula
PA = PFN * pagesize + offset.
Number of entries in a single-level page table for V-bit VA and 2^p pages
2^(V-p).
A page fault is triggered when
the accessed page's valid bit is 0 (not in RAM).
After servicing a page fault the OS does what to the faulting instruction
restarts it so the translation now succeeds.
Why are page tables per-process
for isolation — the same virtual address maps to different physical frames per process.
Big-page trade-off: fewer entries but
more internal fragmentation and larger fault transfers.
The cache that speeds up VPN→PFN lookups is the
TLB (Translation Lookaside Buffer).
32-bit VA, 4 KiB pages → offset bits / VPN bits / #entries
12 / 20 / 2^20.

Concept Map

solves

solves

solves

split into

maps to

split into VPN and offset

looked up by

translates VPN to PFN

offset preserved from

entry not in RAM

OS fetches from

Virtual Memory

Isolation and Protection

Relocation

Over-commitment

Page - virtual block

Frame - physical block

Page Table VPN to PFN

MMU hardware

Virtual Address

Page Fault

Physical Address

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, virtual memory ka basic funda ye hai ki har program ko ek jhoothi (illusion) duniya di jaati hai — har process sochta hai ki uske paas poori badi memory hai jo 0 se start hoti hai aur ek dum continuous hai. Asli RAM me uska data chote-chote tukdo (pages/frames) me bikhra padta hai, ya kabhi disk pe bhi hota hai. Is jhooth ko sach me badalne ke liye ek "dictionary" hoti hai jise page table kehte hain, jo har process ke liye alag hoti hai (isi se isolation milta hai — Process A, Process B ki memory ko touch nahi kar sakta).

Address ko samajhna simple hai: virtual address ko do part me kaat do — upar wala part VPN (virtual page number) aur neeche wala part offset. Agar page size 2p2^p bytes hai, to neeche ke pp bits offset hote hain. Sabse important baat: offset translate NAHI hota — kyunki page aur frame same size ke hote hain, to page ke andar position waisi ki waisi rehti hai. Sirf VPN ko page table me dekh kar PFN (physical frame number) nikaalte hain. Phir final physical address banta hai: PA=PFN×pagesize+offsetPA = PFN \times pagesize + offset (hardware me ye bas concatenation hai).

Agar page table ki entry "valid = 0" bole, matlab data RAM me nahi hai — tab page fault hota hai. OS disk se page laata hai, ek free frame me daalta hai, table update karta hai, aur instruction ko dobara chalata hai. Yahi mechanism allow karta hai ki tum apni physical RAM se bhi zyada memory use kar sako.

Exam aur real coding dono me ye kaam aata hai: jab tum dekhte ho "32-bit VA, 4KB pages", to seedha bolo — offset = 12 bits, VPN = 20 bits, entries = 2202^{20}. Mnemonic yaad rakho: "VPN Picks the Frame, Offset Stays the Same." Bas yahi 80/20 hai — baaki TLB, multi-level page tables wagairah isi base pe khade hote hain.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 2,602 wordsD2Visual walkthroughThe derivation in pictures · 2,003 wordsD3Worked examplesEvery scenario covered · 3,465 wordsD4ExercisesGraded, full solutions · 2,062 wordsD5Question bankConcept traps, quick reveals · 1,996 words

Test yourself — Computer Architecture (Deep)

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

TLB (translation lookaside buffer)Hardware · 5.4.12Multi-level page tables — why, overheadCoding · 4.2.26Memory hierarchy — registers, cache (L1 - L2 - L3), RAM, SSD, HDD — speed - size trade-offsCoding · 1.1.9Operating system role — resource manager, abstraction layerCoding · 1.1.13Cache organization — direct-mapped, n-way set associative, fully associativeCoding · 4.1.9TLB — structure, TLB miss handlingCoding · 4.1.15System calls — user mode vs kernel mode, trap mechanismCoding · 4.2.3Memory allocation — contiguous (first-fit, best-fit, worst-fit)Coding · 4.2.23Fragmentation — internal vs external, compactionCoding · 4.2.24