File allocation — contiguous, linked, indexed (inode): Worked examples

4.2.34 · D3 · Coding › Operating Systems › File allocation — contiguous, linked, indexed (inode)

Yeh page File allocation — contiguous, linked, indexed (inode) ke liye "sab kuch daal do" wali drill hai. Hum koi naya theory nahi seekhenge — hum teen schemes ko har tarah ke input pe exercise karenge: normal cases, do index levels ke beech ki boundary, ek zero-size file, ek file jo exactly ek block ki hai, ek growth request jo fail ho jaati hai, aur ek exam twist. Kisi bhi example se pehle, hum saare cases ka ek map banate hain.

Do numbers almost har example mein aate hain, toh hum unhe ek baar plain words mein pin kar dete hain:

The scenario matrix

Neeche har cell ek alag situation hai. Ex column batata hai ki kaun sa worked example use cover karta hai.

Case class	Contiguous	Linked	Indexed (inode)
Normal byte-to-block lookup	Ex 1	Ex 3	Ex 5
Boundary levels/blocks ke beech	Ex 2 (block edge)	—	Ex 6 (direct↔indirect edge), Ex 12 (single↔double↔triple)
Zero-size / degenerate input	Ex 8 (empty & 1-block)	Ex 8	Ex 8
Limiting value (max reach)	—	Ex 11 (pointer-width limit)	Ex 7 (max file size)
Growth request (kya grow kar sakta hai?)	Ex 4 (fails)	Ex 4 (succeeds)	Ex 4 (succeeds)
Real-world word problem	—	Ex 3	Ex 9 (photo library)
Exam-style twist	—	Ex 11 (width vs count)	Ex 10 (reads for 3 blocks)

Related boundaries External vs Internal Fragmentation (Ex 4), Free Space Management (bitmap, free list) (Ex 4 growth), aur File Systems (ext4, FAT, NTFS) (Ex 3 FAT note) mein hain.

Do tools jo hum reuse karte hain (pehli baar use se pehle define kiye gaye)

Neeche dii gayi picture (Figure s01) bytes ko ek lamba ruler dikhati hai aur blocks ko har $B$ bytes pe tick-marks; amber arrow byte 9000 ko block 2 mein offset 808 pe land karta hua dikhata hai.

Figure — File allocation — contiguous, linked, indexed (inode)

Ex 1 — Contiguous, normal lookup (matrix: Contiguous / normal)

Worked example

Ek file physical block $b = 50$ pe start hoti hai, block size $B = 4096$ . Byte 9000 ko kaun sa physical block aur offset hold karta hai?

Forecast: padhne se pehle guess karo — kya yeh block 51 hai ya 52? Roughly kaun sa offset?

$i = ⌊ 9000/4096 ⌋ = 2$ . Yeh step kyun? Bytes 0–4095 block 0 fill karte hain, 4096–8191 block 1 fill karte hain, toh 9000 teesre logical block mein, index 2 pe land karta hai. Yahi Figure s01 ka ruler hai.
offset $= 9000 mod 4096 = 9000 - 2 \cdot 4096 = 808$ . Kyun? Do poore blocks (8192 bytes) ke baad hum next block mein 808 bytes andar hain.
phys $= b + i = 50 + 2 = 52$ . Kyun? Contiguous ka matlab hai logical block $i$ , $b + i$ pe baitha hai — pure arithmetic, koi chain nahi, $O (1)$ .

Verify: physical byte $= 52 \cdot 4096 + 808 = 213, 800$ . Aur $b \cdot B + N = 50 \cdot 4096 + 9000 = 213, 800$ . ✓ Dono routes se same byte.

Ex 2 — Contiguous, block-edge boundary (matrix: Contiguous / boundary)

Ex 3 — Linked, word problem + random access (matrix: Linked / normal + word)

Worked example

Ek log file linked allocation ke saath store ki gayi hai; disk pe uske blocks chain $7 \to 3 \to 90 \to 12$ hain. Directory sirf pehla block, 7, jaanti hai. Ek program ko logical block 3 (uska data) chahiye. Use locate karne ke liye kitne disk reads, aur agar $p = 4$ ho toh per block kitne usable data bytes?

Forecast: read count guess karo — kya yeh 1 hai (jaise contiguous) ya 4?

Block 7 read karo; uska stored pointer kehta hai "next = 3". Kyun? Linked allocation "next" address ko block ke andar hi hide karta hai — tum block 1 ki location block 0 ko padhe bina nahi jaaan sakte.
Block 3 read karo → next = 90; block 90 read karo → next = 12; block 12 read karo = target. Kyun? Koi formula exist nahi karta; har address sirf pichle read se reveal hota hai. Yahi $O (n)$ cost hai.
Logical block $i$ tak pahunchne ke liye total reads $= i + 1 = 3 + 1 = 4$ . Kyun? Tum blocks $0, 1, 2, 3$ touch karte ho.
Per block usable data $= B - p = 4096 - 4 = 4092$ bytes. Kyun? 4-byte pointer block ke andar hi baitha hai, data space chura raha hai (yeh internal overhead hai).

Verify: FAT fix pointers ko RAM mein move kar deta hai, toh chain-walking mein 0 disk reads lagte hain aur usable data wapas full $B = 4096$ ho jaata hai. Consistency check: $4092 = 4096 - 4$ . ✓

Chain aur uske chaar reads Figure s02 mein draw kiye gaye hain: har cyan box ek data block hai, uske andar amber slot next-pointer hai, aur amber arrows wo links hain jinhe tumhe logical block 3 tak pahunchne ke liye ek-ek karke follow karna hai.

Ex 4 — Growth request, teeno schemes (matrix: growth row)

Worked example

Ek 3-block file contiguous blocks 20–22 pe baitha hai. Block 23 already dusri file ke dwara occupied hai. User ko ek 4th block ki zaroorat wala data append karna hai. Har scheme ke andar kya hoga?

Forecast: kaun sa/se scheme(s) in-place grow karte hain, aur kiski poori file copy karni padti hai?

Contiguous: block 23 liya hua hai, toh file extend nahi ho sakti. Use ≥4 blocks ke ek free run mein (say 60–63) poori tarah move karna hoga aur blocks 20–22 free karne honge. Kyun? Contiguous consecutive blocks maangta hai — koi gap allowed nahi. Cost = saara existing data copy karna. Agar kaafi total free space hone ke bawajood 4 ka koi run exist nahi karta, toh yeh external fragmentation hai.
Linked: koi bhi free block lo, say block 200; purane last block ka pointer 200 pe point karo. Kyun? Ek chain care nahi karta ki next link kahan hai. Growth = $O (1)$ , koi copy nahi.
Indexed (inode): koi bhi free block 200 lo; uska address next empty index slot mein likho. Kyun? Index sirf addresses ki ek array hai; appending ek slot write hai, koi copy nahi. Free block free-space bitmap ke zariye mili.

Verify: comparison table se match karta hai — "Grows easily?" contiguous / linked / indexed ke liye No / Yes / Yes hai. ✓

Ex 5 — Indexed, normal lookup (matrix: Indexed / normal)

Ex 6 — Inode, direct↔indirect boundary (matrix: Indexed / boundary)

Worked example

Unix inode: 12 direct pointers (logical blocks 0–11), phir ek single-indirect block jisme $k = 1024$ pointers hain (logical blocks 12–1035). Logical blocks 11 aur 12 ke liye, data fetch karne mein kitne disk reads lagte hain (inode already memory mein hai)?

Forecast: kya 11 se 12 cross karne mein ek extra read lagta hai?

Block 11: yeh ek direct pointer hai — inode already uska address hold karta hai. Reads = 1 (sirf data block). Kyun? Direct pointers inode mein rehte hain jo memory mein hai; koi pointer-block fetch nahi karna.
Block 12: 12 direct slots ke past pehla block → yeh single-indirect block ke zariye rehta hai. Reads = 2: (1) single-indirect block padhna address paane ke liye, (2) data block padhna. Kyun? Pointers ka ek extra level disk se dereference karna padta hai.
Jump 11→12 exactly ek disk read add karta hai. Kyun? Yahi direct region chhodne ki kimat hai — "80/20" design chhoti files (≤12 blocks) ko 1 read pe rakhta hai.

Verify: direct region size = 12 blocks (indices 0..11); single-indirect $k = 1024$ add karta hai (indices 12..1035). $12 + 1024 = 1036$ blocks double-indirect se pehle reachable. ✓

Figure s03 exactly yahi boundary draw karta hai: baayi taraf in-memory inode, data block 11 ki taraf cyan single-read arrow (direct), aur block 12 tak amber two-hop path (indirect block → data block).

Ex 7 — Inode, limiting value: maximum file size (matrix: Indexed / limiting)

Worked example

$B = 4096$ , $p = 4$ toh $k = 1024$ ke saath, ek inode ki maximum file size compute karo jo address kar sake.

Forecast: kya yeh megabytes, gigabytes, ya terabytes hai? Kaun sa level dominate karta hai?

Direct: $12 \times B = 12 \times 4096 = 49, 152$ B $\approx 48$ KB (yaad raho $\approx$ matlab "close to, rounding ke baad"). Kyun? 12 pointers, ek ek block.
Single-indirect: $k \times B = 1024 \times 4096 = 4, 194, 304$ B $=$ 4 MB. Kyun? $k$ pointers ka ek block, har ek ek data block.
Double-indirect: $k^{2} \times B = 102 4^{2} \times 4096 = 4, 294, 967, 296$ B $=$ 4 GB. Kyun? $k$ pointers, har ek $k$ wale single-indirect block ki taraf → $k^{2}$ data blocks.
Triple-indirect: $k^{3} \times B = 102 4^{3} \times 4096 = 4, 398, 046, 511, 104$ B $\approx 4$ TB. Kyun? Ek aur factor of $k$ .
Total $= 49, 152 + 4, 194, 304 + 4, 294, 967, 296 + 4, 398, 046, 511, 104 = 4, 402, 345, 721, 856$ B $\approx 4$ TB. Kyun? Har level reach ko $k = 1024$ se multiply karta hai, toh triple-indirect baaqi sab ko swamp kar deta hai.

Verify: total in TiB $= 4, 402, 345, 721, 856/102 4^{4} \approx 4.004$ TiB — triple term dominate karta hai, exactly jaisa geometric growth predict karta hai. ✓

Ex 8 — Degenerate inputs: empty file & one-block file (matrix: zero/degenerate)

Worked example

Har scheme mein do sabse chhote cases handle karo: ek 0-byte file (length $L = 0$ blocks) aur ek 1-block (4096-byte) file (length $L = 1$ block).

Forecast: kya ek 0-byte file ko phir bhi ek index block chahiye? Kya use koi bhi data blocks use hote hain?

0-byte file, teeno schemes: 0 data blocks use karta hai, yaani $L = 0$ . Contiguous $(b, L = 0)$ store karta hai; linked "first block = none" store karta hai; inode metadata store karta hai jisme saare pointers null hain. Kyun? $⌈ 0/ B ⌉ = 0$ blocks of data (0 ka ceiling 0 hai) — point karne ke liye kuch bhi nahi hai. Inode abhi bhi exist karta hai (name, permissions), sirf khaali hai.
1-block file, contiguous: $L = 1$ , byte $N$ jahan $0 \leq N < 4096$ hai $i = ⌊ N / B ⌋ = 0$ , phys $= b$ deta hai. Kyun? Sirf block 0 exist karta hai; har valid byte usse map hoti hai.
1-block file, linked: directory ka first block hi single block hai; usable data $= B - p = 4092$ , toh ek poori 4096-byte file ko actually $⌈ 4096/4092 ⌉ = 2$ linked blocks chahiye (4092 pehle mein, 4 doosre mein). Kyun? In-block pointer capacity shrink karta hai — ek subtle degeneracy jise ceiling pakad leta hai!
1-block file, inode: direct pointer 0 block hold karta hai; use fetch karne mein reads $= 1$ . Kyun? Yeh direct region mein fit ho jaata hai, zero indirection.

Verify: 4096 data bytes ke liye blocks chahiye $= ⌈ 4096/ B ⌉ = 1$ contiguous/indexed ke liye (full block usable), lekin plain linked ke liye $⌈ 4096/ (B - p)⌉ = ⌈ 4096/4092 ⌉ = 2$ . ✓

Ex 9 — Word problem: ek photo library (matrix: Indexed / word)

Worked example

Ek phone 6,000 photos store karta hai, har ek 3 MB, ek directory mein inodes use karke ( $B = 4096$ , $k = 1024$ ). (a) Ek photo kitne data blocks use karti hai? (b) Photo ke blocks kaun se inode region mein hain — direct, single, ya double? (c) Photo ka aakhri block fetch karne ke liye reads?

Forecast: 3 MB — kya 12 direct pointers kaafi honge?

Blocks per photo $= ⌈ 3, 000, 000/4096 ⌉ = ⌈ 732.4 ⌉ = 733$ blocks (ceiling partial 733rd block ko upar pura block round karta hai). Kyun? $732 \times 4096 = 2, 998, 272 < 3, 000, 000$ , toh ek 733rd partial block chahiye.
Region: direct 0–11 (12 blocks) cover karta hai, single-indirect 12–1035 cover karta hai. Kyunki $733 \leq 1035$ , photo direct + single-indirect ke andar fit ho jaati hai — last logical block index $733 - 1 = 732$ hai, jo $\geq 12$ hai, toh yeh single-indirect region mein hai. Kyun? $732$ 12 direct slots ke baad hai lekin 1036 se neeche.
Last block ke liye reads: (1) single-indirect block padhna, (2) data block padhna $= 2$ reads. Kyun? Indirection ka ek level, inode already memory mein.

Verify: $732 \times 4096 = 2, 998, 272$ bytes 732 blocks se cover hote hain; 733rd block mein bache hue $3, 000, 000 - 2, 998, 272 = 1, 728$ bytes hain. Aur $12 \leq 732 \leq 1035$ ⇒ single-indirect. ✓

Ex 10 — Exam twist: ek range fetch karne ke liye reads (matrix: Indexed / exam twist)

Worked example

Inode, $k = 1024$ . Ek program logical blocks 10, 11, 12 sequence mein padhta hai. No caching of pointer blocks between reads assume karte hue, total disk reads count karo. Phir batao caching ke saath kya badalta hai.

Forecast: kya yeh $1 + 1 + 2 = 4$ hai, ya block 12 zyada costly hai?

Block 10 → direct: 1 read (sirf data). Block 11 → direct: 1 read. Kyun? Dono indices 12 se neeche hain, toh ye in-memory inode ke 12 direct slots mein baithe hain; koi pointer-block fetch nahi karna.
Block 12 → single-indirect: single-indirect block padhna (1) + data block (1) $=$ 2 reads. Kyun? Index 12 direct region ke baad pehla hai, toh data se pehle disk se ek pointer-block dereference karna padta hai — exactly Ex 6 ki boundary.
No-cache total $= 1 + 1 + 2 = 4$ reads. Kyun? No caching ke saath har fetch independent hai, toh hum simply per-block costs add karte hain.
Caching ke saath: single-indirect block, block 12 ke liye ek baar padha gaya, memory mein rehta hai; blocks 13, 14, … phir sirf 1 read cost karte hain (unke addresses already cached pointer block mein hain). Kyun? Pointer block reuse hota hai instead of re-read — isliye real filesystems indirect blocks aggressively cache karte hain, ek sequential scan ko ek pointer-block read plus ek read per data block mein convert karte hue.

Verify: bina cache ke, 3 blocks mein 4 reads lagte hain; block 12 hi akela hai jo indirection mein cross karta hai (index $12 \geq 12$ ). Direct blocks (indices $< 12$ ) 1 each cost karte hain ⇒ $1 + 1 + 2 = 4$ . ✓

Ex 11 — Linked, limiting value + width-vs-count twist (matrix: Linked / limiting + exam twist)

Worked example

Plain linked allocation mein "next block" address $p = 4$ bytes wide hai. (a) Ek 4-byte pointer sabse badi disk ko (blocks mein, phir bytes mein) kya name de sakta hai? (b) Yeh maximum linked file ko kya cap karta hai? (c) Twist: yeh ceiling Ex 7 ke inode ceiling se ek alag tarah ki limit kyun hai?

Forecast: linked files ek-ek block karke forever grow kar sakti hain — toh kya koi bhi size ceiling hai?

Ek $p = 4$ -byte pointer $4 \times 8 = 32$ bits ka hai, toh yeh zyada se zyada $2^{32}$ distinct block numbers hold kar sakta hai. Kyun? Har bit addresses ki count double karta hai; 32 bits $2^{32} = 4, 294, 967, 296$ blocks name kar sakte hain. Yahi asli ceiling hai — chain length nahi, balki pointer ki width jo chain store karti hai.
Total addressable disk $= 2^{32} \times B = 4, 294, 967, 296 \times 4096 = 17, 592, 186, 044, 416$ B $=$ 16 TiB. Kyun? Har block jise pointer name kar sakta hai $B$ bytes ka hai; multiply karo.
Ek single linked file poore addressable disk se badi nahi ho sakti, toh uska cap bhi $\approx$ 16 TiB hai (minus har block se khaaya gaya pointer overhead $p$ , aur minus dusri files ki space). Kyun? Ek file disk ke blocks ka ek subset hai; tum us block tak chain nahi kar sakte jiska number pointer express nahi kar sakta.
Twist answer: linked limit pointer width se aati hai (ek single block number kitna bada ho sakta hai), jabki Ex 7 mein inode limit pointer count se aati hai indirection levels ke across (kitne many pointers tum arrange kar sakte ho). Pointer ko 8 bytes tak widen karo aur linked disk $2^{64} \times B$ tak jump kar jaati hai; inode ki jagah indirection levels add karke badhti hai. Yeh kyun matter karta hai? Exam mein, "max file size badhaao" ke do bilkul alag answers hain scheme ke hisaab se.

Verify: $2^{32} = 4, 294, 967, 296$ blocks; $\times 4096 = 17, 592, 186, 044, 416$ B; $102 4^{4}$ se divide karne pe exactly 16 TiB milta hai. ✓

Ex 12 — Inode, single↔double↔triple boundaries (matrix: Indexed / deep boundary)

Worked example

Inode, $k = 1024$ , saare pointer blocks uncached (inode khud memory mein). Har region ka pehla logical block fetch karne ke liye disk reads dhundho: last single-indirect block, pehla double-indirect block, last double-indirect block, aur pehla triple-indirect block.

Forecast: har region crossing exactly ek extra pointer-block read add karni chahiye. Sahi hai?

Region indices (Ex 6/7 se build kiye gaye): direct $= 0 \dots 11$ ; single $= 12 \dots 1035$ (yaani $12 + k - 1$ ); double $= 1036 \dots (1036 + k^{2} - 1) = 1036 \dots 1, 049, 611$ ; triple $1, 049, 612$ pe start. Kyun? Single $k$ blocks add karta hai, double $k^{2}$ add karta hai, toh har region ka last index previous last plus uski span hai.
Last single-indirect block (index 1035): single-indirect block padhna (1) + data (1) $=$ 2 reads. Kyun? Ek pointer level.
Pehla double-indirect block (index 1036): double-indirect block padhna (1) → uske point kiye single-indirect block ko padhna (1) → data padhna (1) $=$ 3 reads. Kyun? Do pointer levels: double block single-indirect blocks list karta hai, toh hum do baar dereference karte hain.
Last double-indirect block (index 1,049,611): abhi bhi 3 reads — same two-level path, sirf double ke neeche last single-indirect block ka last slot. Kyun? Double region ke andar rehne se level count kabhi nahi badlata.
Pehla triple-indirect block (index 1,049,612): triple block padhna (1) → double block (1) → single block (1) → data (1) $=$ 4 reads. Kyun? Teen pointer levels stack up ho jaate hain.

Verify: reads per region = 2, 3, 3, 4 — har region boundary (single→double, double→triple) exactly ek pointer-block read add karta hai, "ek extra level = ek extra read" se match karta hai. Region spans: single $= 1024$ , double $= 102 4^{2} = 1, 048, 576$ ; last double index $= 1036 + 1, 048, 576 - 1 = 1, 049, 611$ ; triple $1, 049, 612$ pe start. ✓

Figure s04 chaar regions ko nested pointer-block ladders ki tarah stack karta hai; har ek ke saath amber count reads ko 1 → 2 → 3 → 4 climb karte hue dikhata hai jaisa tum deeper indirection mein jaate ho.

Recall Quick self-test

Byte 9000 ka contiguous phys, start block 50, B=4096? ::: block 52, offset 808. Linked: chain 7→3→90→12 ke logical block 3 tak pahunchne ke liye reads? ::: 4 reads. Inode with B=4096, p=4, k=1024 — max file size? ::: approximately 4 TB (49152 + 4 MB + 4 GB + 4 TB bytes). Inode mein logical block 12 fetch karne ke liye reads (inode RAM mein)? ::: 2 (single-indirect block + data block). Pehla triple-indirect block fetch karne ke liye reads (uncached)? ::: 4 (triple + double + single + data). B=4096 pe ek 3 MB photo ko kitne blocks chahiye? ::: 733 blocks. Kya ek 0-byte file ko koi data blocks chahiye? ::: Nahi — saare pointers null, lekin inode abhi bhi exist karta hai. Ek 4-byte linked pointer jo sabse badi disk name kar sakta hai? ::: 2^32 blocks × 4096 B = 16 TiB.