Programs love to think they own one big, contiguous chunk of memory starting at address 0. Reality: physical RAM is shared, fragmented, and finite. Paging is the trick that lets us lie convincingly to every program.
We chop the program's virtual address space into fixed-size blocks called pages .
We chop physical RAM into fixed-size blocks of the same size called frames .
Any page can live in any frame. A lookup table (the page table ) records which page is in which frame.
WHY this is genius: because page size = frame size, any page fits in any free frame. There is no external fragmentation — we never need a "big enough contiguous hole." We just need enough free frames , anywhere.
Page ::= a fixed-size block of the virtual (logical) address space.Frame (page frame) ::= a fixed-size block of physical memory (RAM).Crucial invariant: page size frame size==, always a power of two (e.g. 4 KB = 2 12 4\text{ KB} = 2^{12} 4 KB = 2 12
Intuition Why a power of two?If page size = 2 p = 2^p = 2 p cleanly by bit-slicing — no division, no remainder hardware. The low p p p offset ; the high bits are the page number . Splitting an address is just "cut the bit string," which is free in hardware.
Suppose:
Virtual address is m m m = 2 m = 2^m = 2 m
Page size = 2 p = 2^p = 2 p
Question: how many pages, and how do we read an address?
A page holds 2 p 2^p 2 p inside a page we need exactly p p p offset d d d 0 ≤ d < 2 p 0 \le d < 2^p 0 ≤ d < 2 p
The remaining m − p m - p m − p which page. So:
number of pages = 2 m 2 p = 2 m − p \text{number of pages} = \frac{2^m}{2^p} = 2^{\,m-p} number of pages = 2 p 2 m = 2 m − p
Translation step. The MMU looks up p num p_{\text{num}} p num frame number f f f
phys = f × 2 p + d \text{phys} = f \times 2^{p} + d phys = f × 2 p + d
d d d whole inside a frame. The position of a byte within the block doesn't change when we relocate the block. So only the block number is translated; the offset is carried straight through. Translate the apartment building number, keep the same apartment number inside.
A per-process array indexed by page number , where each entry (a Page Table Entry, PTE ) stores the frame number plus control bits.
Definition Typical PTE fields
Frame number — where the page lives in RAM.Valid/Present bit — is this page in memory at all?Dirty bit — has the page been written (needs writeback)?Referenced bit — used recently? (for replacement algorithms)Protection bits — read / write / execute permissions.User/Supervisor bit — privilege needed to access.
# entries = 2 m − p , page-table size = 2 m − p × ( PTE size in bytes ) \#\text{entries} = 2^{\,m-p}, \qquad \text{page-table size} = 2^{\,m-p} \times (\text{PTE size in bytes}) # entries = 2 m − p , page-table size = 2 m − p × ( PTE size in bytes )
Worked example The "page table is HUGE" problem32-bit address (m = 32 m=32 m = 32 p = 12 p=12 p = 12
Entries = 2 32 − 12 = 2 20 = 1 048 576 = 2^{32-12} = 2^{20} = 1\,048\,576 = 2 32 − 12 = 2 20 = 1 048 576
Size = 2 20 × 4 = 2 22 = 4 MB = 2^{20} \times 4 = 2^{22} = 4\text{ MB} = 2 20 × 4 = 2 22 = 4 MB per process .
Why this hurts: with 100 processes that's 400 MB of page tables alone — most of it for pages a process never touches. We need a smarter structure.
Intuition The driving problemA flat (single-level) table reserves an entry for every possible page even if the process uses almost none. Address spaces are sparse (code low, stack high, huge gap between). We want to not allocate table space for empty regions .
Split the page number itself into chunks; each chunk indexes one level. Inner tables for unused regions simply don't exist (their outer entry is null).
Worked example Two-level, 32-bit, 4 KB pagesSplit the 20-bit page number into 10 + 10 :
[ 10 bits ] ⏟ outer (directory) [ 10 bits ] ⏟ inner (table) [ 12 bits ] ⏟ offset \underbrace{[\,10\text{ bits}\,]}_{\text{outer (directory)}}\;\underbrace{[\,10\text{ bits}\,]}_{\text{inner (table)}}\;\underbrace{[\,12\text{ bits}\,]}_{\text{offset}} outer (directory) [ 10 bits ] inner (table) [ 10 bits ] offset [ 12 bits ]
Outer table: 2 10 = 1024 2^{10}=1024 2 10 = 1024 1024 1024 1024
Why this saves memory: if a process uses 1 inner table's worth of pages, you store one outer table + one inner table = 2 × 1024 × 4 = 8 KB = 2 \times 1024 \times 4 = 8\text{ KB} = 2 × 1024 × 4 = 8 KB
One entry per physical frame (not per virtual page). Size ∝ \propto ∝ ∝ \propto ∝
Why: total entries = number of frames, independent of how many processes or how big their spaces are.Cost: lookup is no longer a direct index → needs hashing.
Intuition Every memory access would need anextra memory access to read the PTE — doubling traffic. Multi-level makes it worse (one access per level!). The TLB (Translation Lookaside Buffer) is a tiny fast cache of recent page→frame mappings, exploiting locality so most translations are a 1-cycle hit.
EAT = ( 1 − miss rate ) ⋅ ( t T L B + t m e m ) + miss rate ⋅ ( t T L B + L ⋅ t m e m + t m e m ) \text{EAT} = (1-\text{miss rate})\cdot(t_{TLB}+t_{mem}) + \text{miss rate}\cdot(t_{TLB}+ L\cdot t_{mem} + t_{mem}) EAT = ( 1 − miss rate ) ⋅ ( t T L B + t m e m ) + miss rate ⋅ ( t T L B + L ⋅ t m e m + t m e m ) L L L
Worked example Example 1 — split a virtual addressPage size 4 KB 4\text{ KB} 4 KB A = 0 x 00003 A B C A = 0\text{x}00003ABC A = 0 x 00003 A B C
4 KB = 2 12 4\text{ KB} = 2^{12} 4 KB = 2 12 low 12 bits . Why: 12 bits address all 4096 bytes in a page. Low 12 bits of 0x3ABC: 0 xABC 0\text{xABC} 0 xABC d = 0 xABC = 2748 d = 0\text{xABC} = 2748 d = 0 xABC = 2748 Why: mask with 2 12 − 1 2^{12}-1 2 12 − 1
Remaining bits: A ≫ 12 = 0 x 3 = 3 A \gg 12 = 0\text{x}3 = 3 A ≫ 12 = 0 x 3 = 3 = 3 = 3 = 3 Why: shift drops the offset, leaving the page index.
Worked example Example 2 — full translationPage table: page 3 → 3 \to 3 → 7 7 7 4 KB 4\text{ KB} 4 KB A = 0 x 00003 A B C A=0\text{x}00003ABC A = 0 x 00003 A B C
From Ex.1: page 3 3 3 0 xABC 0\text{xABC} 0 xABC
Frame = 7 = 7 = 7 Why: read PTE[3].
Phys = 7 × 2 12 + 0 xABC = 0 x 7000 + 0 xABC = 0 x 7 A B C = 7\times 2^{12} + 0\text{xABC} = 0\text{x}7000 + 0\text{xABC} = 0\text{x}7ABC = 7 × 2 12 + 0 xABC = 0 x 7000 + 0 xABC = 0 x 7 A B C Why: frame number shifts into high bits, offset unchanged.
Worked example Example 3 — table size & internal fragmentationA process uses exactly 5000 5000 5000 4 KB 4\text{ KB} 4 KB
Pages needed = ⌈ 5000 / 4096 ⌉ = 2 = \lceil 5000 / 4096 \rceil = 2 = ⌈ 5000/4096 ⌉ = 2 Why: can't have a partial page.
Allocated = 2 × 4096 = 8192 = 2 \times 4096 = 8192 = 2 × 4096 = 8192 = 8192 − 5000 = 3192 = 8192 - 5000 = 3192 = 8192 − 5000 = 3192
This waste is internal fragmentation : the last page is partly empty. Why paging trades external for internal fragmentation.
Common mistake "Bigger pages are always better."Why it feels right: bigger pages → fewer pages → smaller page table → fewer TLB misses. All true!
The fix: bigger pages also mean more internal fragmentation (avg 1 2 \frac12 2 1 trade-off ; 4 KB 4\text{ KB} 4 KB
Common mistake "The offset gets translated too."Why it feels right: the whole virtual address looks like it should map to a new physical address.
The fix: only the page number is looked up; the offset is copied verbatim , because a byte's position inside a block doesn't change when the block is relocated.
Common mistake "Page table size depends on how much RAM I have."Why it feels right: tables live in RAM, RAM is physical...
The fix: a flat page table's size depends on the virtual address space (2 m − p 2^{m-p} 2 m − p inverted page table scales with physical RAM.
Common mistake "Multi-level paging wastes memory because of extra tables."Why it feels right: more tables = more overhead, surely?
The fix: outer entries for unused regions are null — those inner tables are never allocated. For sparse address spaces this saves vastly more than the directory costs.
Recall Feynman: explain it to a 12-year-oldImagine a giant book your program thinks it owns, page 1, 2, 3... in order. But the library only has random empty shelf slots. So the librarian (the OS) puts your "page 5" on shelf 20, your "page 6" on shelf 2 — wherever there's room. They keep a little notebook: "page 5 → shelf 20." When you ask for something on page 5, they check the notebook, walk to shelf 20, and count the same number of steps into that shelf as you wanted into the page. The page moves around; the step count inside the page never changes. That notebook is the page table , the shelves are frames , and your imaginary book pages are pages .
Mnemonic Remember the split & the rule"POD" — P age number on top, O ffset on bottom, D ivide by page size.
And: "Offset rides free, only the frame changes seat." (offset copied; page→frame translated.)
What is the invariant relating page size and frame size? They are always equal (and a power of two), so any page fits in any free frame.
Why must page size be a power of two (2 p 2^p 2 p So an address splits by bit-slicing: low
p p p bits = offset, high bits = page number — no division hardware needed.
For an m m m 2 p 2^p 2 p Given virtual address A A A 2 p 2^p 2 p page number
= ⌊ A / 2 p ⌋ =\lfloor A/2^p\rfloor = ⌊ A / 2 p ⌋ (high bits, i.e.
A ≫ p A\gg p A ≫ p ); offset
= A m o d 2 p = A \bmod 2^p = A mod 2 p (low
p p p bits, i.e.
A & ( 2 p − 1 ) A \,\&\,(2^p-1) A & ( 2 p − 1 ) ).
In translation, what part of the address is NOT translated? The offset — it is copied unchanged; only the page number → frame number is looked up.
Physical address formula given frame f f f 2 p 2^p 2 p d d d f × 2 p + d f\times 2^p + d f × 2 p + d .
Flat page-table size for 32-bit address, 4KB pages, 4-byte PTEs? 2 20 2^{20} 2 20 entries
× 4 = 4 \times 4 = 4 × 4 = 4 MB per process.
What problem does a multi-level page table solve? Sparse address spaces — inner tables for unused regions are never allocated (null outer entry), saving memory.
What does an inverted page table index, and how does its size scale? Indexed per physical frame; size scales with RAM, not with virtual address space; lookup uses hashing on (PID, page#).
What kind of fragmentation does paging eliminate, and what does it introduce? Eliminates external fragmentation; introduces internal fragmentation (partly-empty last page, avg ½ page per region).
Name 4 typical PTE control bits. Valid/present, dirty, referenced, protection (R/W/X) (also user/supervisor).
Why does a TLB exist? To cache recent page→frame translations so most accesses avoid extra memory reads of the page table (exploits locality).
Virtual Memory — paging is its foundation; demand paging uses the valid bit.TLB and Address Translation — speeds up the lookup derived here.Segmentation — alternative/complement; variable size → external fragmentation.Page Replacement Algorithms — use the referenced/dirty bits in the PTE.Internal vs External Fragmentation — the trade-off paging makes.Cache Memory and Locality — same locality principle the TLB exploits.
No external fragmentation
Intuition Hinglish mein samjhoDekho, paging ka basic idea simple hai: har program sochta hai uske paas ek lamba, continuous memory hai jo address 0 se start hoti hai. Lekin actual RAM toh shared aur tukdo me bati hoti hai. Isliye OS program ki virtual memory ko fixed-size blocks me kaat deta hai — inhe page kehte hain. Aur physical RAM ko same size ke blocks me kaatta hai — inhe frame kehte hain. Page size aur frame size hamesha equal hote hain, aur power of two (jaise 4 KB = 2 12 2^{12} 2 12 external fragmentation khatam ho jati hai.
Address ko kaise todte hain? Agar page size 2 p 2^p 2 p niche ke p p p (page ke andar kaunsa byte), aur upar ke bits = page number . Hardware me ye bas bit-shift aur mask hai, koi division nahi. Phir page table me page number daal ke uska frame number nikalte hain. Important baat: offset ko translate nahi karte — wo seedha copy ho jata hai. Sirf page number → frame number badalta hai. Apartment ka building number badalta hai, par andar ka flat number same rehta hai.
Problem ye hai ki ek flat page table bahut bada ho jata hai — 32-bit address aur 4KB pages me 2 20 2^{20} 2 20 per process ! Isliye multi-level page table use karte hain: page number ko bhi chunks me todo, aur jo regions use nahi ho rahe unke inner tables banao hi mat (null rakho). Iska alternative hai inverted page table (har frame ke liye ek entry, RAM ke size pe depend karta hai). Aur translation slow na ho isliye TLB ek chhota fast cache rakhta hai recent mappings ka.
Exam tip: internal fragmentation yaad rakho — last page kabhi-kabhi adha khali rehta hai, average 1 2 \frac12 2 1
