Paging — page - frame size, page table structure

4.2.25 · Coding › Operating Systems

Intuition Core idea kya hai

Programs ko lagta hai ki unke paas ek bada, contiguous memory chunk hai jo address 0 se shuru hota hai. Reality yeh hai: physical RAM shared, fragmented, aur finite hoti hai. Paging woh trick hai jo humein allow karti hai ki hum har program ke saath convincingly jhooth bolein.

Hum program ke virtual address space ko fixed-size blocks mein kaatte hain jinhein pages kehte hain.
Hum physical RAM ko bhi usi same size ke fixed-size blocks mein kaatate hain jinhein frames kehte hain.
Koi bhi page kisi bhi frame mein reh sakta hai. Ek lookup table (page table) record karta hai ki kaunsa page kis frame mein hai.

YEH genius kyun hai: kyunki page size = frame size, koi bhi page kisi bhi free frame mein fit ho jaata hai. External fragmentation bilkul nahi hoti — humein kabhi "itna bada contiguous hole" nahi chahiye. Bas enough free frames chahiye, kahin bhi.

Page / Frame KYA hota hai?

Address KAISE split hota hai (scratch se derive karo)

Maano:

Virtual address $m$ bits wide hai → virtual address space $= 2^{m}$ bytes.
Page size $= 2^{p}$ bytes.

Sawaal: kitne pages hain, aur hum ek address kaise padhte hain?

Ek page $2^{p}$ byte-positions hold karta hai, toh page ke andar ek byte ko name karne ke liye humein exactly $p$ bits chahiye → offset $d$ , jahan $0 \leq d < 2^{p}$ .

Baaki bache $m - p$ high bits kaunsa page hai yeh naam karte hain. Toh:

$number of pages = \frac{2 ^{m}}{2 ^{p}} = 2^{m - p}$

Translation step. MMU page table mein $p_{num}$ lookup karta hai aur frame number $f$ laata hai. Physical address hai:

$phys = f \times 2^{p} + d$

Page Table

Ek (flat) page table kitna bada hota hai?

$# entries = 2^{m - p}, page-table size = 2^{m - p} \times (PTE size in bytes)$

Smarter page-table structures (YEH KYU exist karte hain)

1. Multi-level (hierarchical) page table

Page number ko khud chunks mein split karo; har chunk ek level ko index karta hai. Unused regions ke inner tables simply exist hi nahi karte (unka outer entry null hota hai).

2. Inverted page table

Har physical frame ke liye ek entry hoti hai (har virtual page ke liye nahi). Size $\propto$ RAM, nahi $\propto$ virtual space. (process-id, page-number) se search hota hai, usually hash ke zariye.

Kyun: total entries = frames ki sankhya, chahe kitne bhi processes hon ya unke spaces kitne bhi bade hon.
Cost: lookup direct index nahi raha → hashing chahiye.

3. TLB (kyun translation slow nahi hoti)

$EAT = (1 - miss rate) \cdot (t_{T L B} + t_{m e m}) + miss rate \cdot (t_{T L B} + L \cdot t_{m e m} + t_{m e m})$ jahan $L$ = miss pe walk kiye gaye page-table levels hain.

Worked examples

Common mistakes

Recall Feynman: 12-saal ke bacche ko explain karo

Socho ek badi kitaab jo tumhara program sochta hai ki uski apni hai, page 1, 2, 3... order mein. Lekin library mein sirf random khali shelf slots hain. Toh librarian (OS) tumhara "page 5" shelf 20 pe rakh deta hai, tumhara "page 6" shelf 2 pe — jahan bhi jagah mile. Woh ek chhoti notebook rakhta hai: "page 5 → shelf 20." Jab tum page 5 pe kuch maangto ho, woh notebook check karta hai, shelf 20 pe jaata hai, aur utne hi steps count karta hai us shelf ke andar jitne tum page ke andar chahte the. Page idhar-udhar jaata hai; page ke andar step count kabhi nahi badlata. Woh notebook page table hai, shelves frames hain, aur tumhare imaginary book pages pages hain.

Flashcards

Page size aur frame size ke beech kya invariant hai?

Woh hamesha equal hote hain (aur power of two hote hain), taaki koi bhi page kisi bhi free frame mein fit ho sake.

Page size

2^{p}

kyun hona chahiye?

Taaki address bit-slicing se split ho: low

p

bits = offset, high bits = page number — koi division hardware nahi chahiye.

m

-bit address aur

2^{p}

-byte pages ke liye, kitne pages exist karte hain?

2^{m - p}

Virtual address

A

aur page size

2^{p}

diya ho, page number aur offset kaise nikalte hain?

page number

= ⌊ A / 2^{p} ⌋

(high bits, yaani

A ≫ p

); offset

= A mod 2^{p}

(low

p

bits, yaani

A & (2^{p} - 1)

Translation mein address ka kaunsa part translate NAHI hota?

Offset — yeh unchanged copy hota hai; sirf page number → frame number lookup hota hai.

Frame

f

, page size

2^{p}

, offset

d

diya ho, physical address formula kya hai?

f \times 2^{p} + d

32-bit address, 4KB pages, 4-byte PTEs ke liye flat page-table size kya hogi?

2^{20}

entries

\times 4 = 4

MB per process.

Multi-level page table kaunsi problem solve karta hai?

Sparse address spaces — unused regions ke inner tables kabhi allocate nahi hote (null outer entry), memory bachti hai.

Inverted page table kise index karta hai, aur uska size kaise scale karta hai?

Har physical frame ke liye index hota hai; size RAM ke saath scale karta hai, virtual address space ke saath nahi; lookup (PID, page#) pe hashing use karta hai.

Paging kaunsa fragmentation khatam karti hai, aur kaunsa introduce karti hai?

External fragmentation khatam karti hai; internal fragmentation introduce karti hai (partly-empty last page, avg ½ page per region).

4 typical PTE control bits batao.

Valid/present, dirty, referenced, protection (R/W/X) (aur user/supervisor bhi).

TLB kyun exist karta hai?

Recent page→frame translations cache karne ke liye taaki zyaadatar accesses page table ke extra memory reads avoid kar sakein (locality exploit karta hai).

Connections

Virtual Memory — paging iska foundation hai; demand paging valid bit use karta hai.
TLB and Address Translation — yahan derive kiye gaye lookup ko speed up karta hai.
Segmentation — alternative/complement; variable size → external fragmentation.
Page Replacement Algorithms — PTE mein referenced/dirty bits use karte hain.
Internal vs External Fragmentation — woh trade-off jo paging karta hai.
Cache Memory and Locality — wahi locality principle jo TLB exploit karta hai.