File allocation — contiguous, linked, indexed (inode): Visual walkthrough

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

Hum kuch bhi assume nahi karte sirf itna: ek disk numbered boxes ka array hai. Chalo har symbol ko earn karte hain.

Step 1 — Ek disk bas numbered boxes hai

KYA HAI. Ek hard disk (ya SSD) ko equal-sized chunks mein kaata jaata hai jinhein blocks kehte hain. Socho ek lambi shelf jisme identical boxes hain, har ek pe ek number likha hai: box 0, box 1, box 2, … Har box mein same number of bytes aate hain.

KYUN. Operating system kabhi directly metal se "byte 9000" nahi padhta — woh ek baar mein poora block padhta hai. Toh sabse pehli cheez jo hume chahiye woh hai "ek box kitna bada hai" ka naam. Hum us size ko $B$ (bytes per block) kehte hain. Ek common value hai $B = 4096$ bytes (4 KB).

PICTURE. Pale-yellow boxes ki row dekho. Har ek $B$ bytes wide hai; neeche ka number uska physical block address hai — disk pe uska box label.

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

Step 2 — Ek file box numbers ki list hai

KYA HAI. Ek file ke bytes rarely ek box mein fit hote hain, aur woh boxes jo woh use karti hai shelf pe idhar-udhar bikhari hoti hain. Toh file aslmein bas ek physical block addresses ki ordered list hai: "mera data box 40 mein hai, phir box 7 mein, phir box 91 mein…"

KYUN. Agar woh list kho gayi, file gone — data abhi bhi disk pe hai, lekin hum nahi jaante kaunse boxes hamare hain ya kis order mein. Toh file allocation ka poora game yeh hai: yeh box numbers ki list hum kahan rakhte hain? Indexed allocation ka jawab: ise ek dedicated jagah mein rakho jise index block / inode kehte hain.

PICTURE. Blue arrows woh list hain. List ki position 0 box 40 ki taraf point karti hai, position 1 box 7 ki taraf, aur aise aage. List mein position logical block number $i$ hai; wahan stored value physical block number hai.

Step 3 — EK block mein kitne box numbers fit hote hain?

KYA HAI. Ek box number (ek pointer) khud sirf kuch bytes hota hai — uski size ko $p$ kaho (pointer size, e.g. $p = 4$ bytes). Agar hum ek poore block ko sirf pointers se bhaar dein, kitne fit honge?

KYUN. Yeh ratio poori derivation mein sabse important number hai, kyunki inode ka har level apni reach ko exactly itne se multiply karta hai. Hum ise apna naam dete hain: $k = \frac{B}{p}$

Term by term:

$B$ = ek block mein bytes (woh box jise hum pointers se bhaar rahe hain),
$p$ = ek pointer mein bytes (ek box-number ki width),
$k$ = ek block mein kitne pointers fit hote hain.

KYUN divide? Division ka jawab hai "size $p$ ki kitni cheezein size $B$ ke container mein fit hongi?" — yeh $B \div p$ ki definition hai. $B = 4096, p = 4$ ke saath: $k = 4096/4 = 1024$ pointers per block.

PICTURE. Ek block $k$ chhote slots mein kata hua, har slot mein ek physical block number. Pink brace $k$ slots dikhata hai.

Step 4 — Level 0: 12 direct pointers (tiny files, zero extra reads)

KYA HAI. Inode mein khud 12 pointers hote hain jo seedha data blocks ki taraf point karte hain. Yeh direct pointers hain. Koi middle-men nahi.

KYUN. Real-world fact: zyaadatar files choti hoti hain. Agar 12 direct pointers already $12 \times B$ bytes tak pahunch jaate hain, toh ek choti file ko zero extra disk reads chahiye — inode already memory mein hai, toh direct pointer follow karna kuch extra cost nahi karta. Yahi 80/20 design hai: common case ko free banao.

$direct reach = 12 \cdot B$

$12$ = inode mein direct slots ki sankhya,
$B$ = har data block mein bytes.

$B = 4096$ ke saath: $12 \times 4096 = 49, 152$ B ≈ 48 KB.

PICTURE. Left pe inode; 12 blue arrows seedhe 12 yellow data boxes ki taraf jaate hain. Inode aur data ke beech kuch nahi.

Step 5 — Level 1: single indirect (ek hop → $k$ aur blocks)

KYA HAI. Inode mein ek extra pointer hai, single indirect. Yeh data ki taraf point nahi karta — yeh ek pointers se bhare block ki taraf point karta hai. Woh block $k$ pointers hold karta hai, har ek ek data block ki taraf aim karta hua.

KYUN. Direct slots 12 pe khatam ho gaye. Inode mein hazaron pointers thusne ki jagah (jo har chhoti file ke liye inode ko huge bana deta), hum extra pointers ka kharcha tab karte hain jab file ko chahiye — ek block ko pointer-holder ke roop mein kharch karke. Ek extra read $k$ aur data blocks kharid deta hai.

$single reach = k \cdot B$

$k$ = us ek indirection block mein pointers (Step 3 se),
$B$ = un $k$ data blocks mein se har ek ke bytes.

$k = 1024$ ke saath: $1024 \times 4096 = 4$ MB.

PICTURE. Inode → ek pink "index" block → $k$ blue arrows $k$ data boxes ki taraf fan out karte hue. Ek hop data tak pahunchne se pehle — notice karo.

Step 6 — Levels 2 aur 3: double & triple indirect (fan-out squared, cubed)

KYA HAI. Wahi trick, stacked.

Double indirect: inode → $k$ pointers ka ek block, har ek ek single-indirect block of $k$ pointers ki taraf point karta hai → $k \times k = k^{2}$ data blocks.
Triple indirect: ek aur layer → $k \times k \times k = k^{3}$ data blocks.

KYUN. Pointers-pointing-to-pointers ki har nayi layer reach ko $k$ ke ek aur factor se multiply karti hai. Yahi wajah hai ki numbers explode karte hain: $k = 1024$ , toh har level pichle se hazaar guna bada hai. Do hops $k^{2}$ dete hain, teen hops $k^{3}$ .

$double reach = k^{2} \cdot B, triple reach = k^{3} \cdot B$

$k^{2}$ = $k$ first-level slots $\times$ $k$ second-level slots (multiply isliye kyunki $k$ top pointers mein se har ek ke neeche $k$ aur hain),
$k^{3}$ = wahi reasoning teen deep stacked.

PICTURE. Ek branching tree: root (inode ka double-indirect pointer) → $k$ branches → har ek $k$ leaves mein branch karta hai. Leaves count karo: $k^{2}$ . Dashed triple-indirect $k^{3}$ ke liye ek aur level of branching add karta hai.

Step 7 — Levels ko sum karo = 4 TB result

KYA HAI. Total reach = har level jod do. Har block count ko $B$ se multiply karke bytes mein convert karo: $Max = direct 12 B + single k B + double k^{2} B + triple k^{3} B$

KYUN add karte hain? File ke chaar regions disjoint hain — ek logical block exactly ek region mein hota hai — toh total addressable size unka sum hai (no double-counting).

$B = 4096, k = 1024$ plug in karo:

Level	Blocks	Bytes	Human
Direct	$12$	$49, 152$	≈ 48 KB
Single	$1024$	$4, 194, 304$	4 MB
Double	$1, 048, 576$	$4, 294, 967, 296$	4 GB
Triple	$1, 073, 741, 824$	$4, 398, 046, 511, 104$	4 TB

Triple-indirect term ( $k^{3} B$ ) double se hazaar guna bada hai, jo single se hazaar guna bada hai — toh total ≈ 4 TB hai, aur chhote terms use barely nudge karte hain.

PICTURE. Log scale pe ek stacked bar — har level pichle se hazaar guna oocha. Aankhein dekhti hain kyun "4 TB + 4 GB + 4 MB + 48 KB" basically sirf "4 TB" hai.

Step 8 — Edge & degenerate cases (kuch nahi chhoda)

KYA HAI & KYUN, case by case:

Empty file ( $0$ bytes). Koi data blocks nahi. Inode abhi bhi exist karta hai (woh metadata + all-null pointers hold karta hai). Max reach unchanged; actual reach = 0.
Tiny file ≤ 48 KB. Poori tarah 12 direct pointers mein rehti hai. Koi bhi byte padhna = in-memory inode ke baad 0 extra reads. Yeh woh fast common case hai jiske liye design optimize kiya gaya hai.
Ek block exactly boundary $i = 11$ vs $i = 12$ pe. $i = 11$ aakhri direct block hai; $i = 12$ pehla single-indirect block hai. Yahan off-by-one ka matlab ek galat disk read — dhyaan se count karo: direct logical blocks $0$ se $11$ tak cover karta hai.
Bade pointers ( $p = 8$ , 64-bit addresses). Tab $k = 4096/8 = 512$ , toh har level shrink hota hai: triple reach $= 51 2^{3} \times 4096 = 549, 755, 813, 888$ B ≈ 512 GB. Mote pointers → chhotii max file. Yahi wajah hai ki number exact filesystem pe depend karta hai, koi universal constant nahi.
Bade blocks ( $B = 8192$ ). Tab $k = 8192/4 = 2048$ aur $B$ khud double ho jaata hai, toh triple reach $= 204 8^{3} \times 8192$ — bahut zyada grow karta hai. Bade blocks → bahut badi max file (lekin half-empty last blocks mein zyada wasted space — dekho External vs Internal Fragmentation).

PICTURE. Teen cases side by side: empty inode (saare pointers null), tiny file (sirf direct used), aur "boundary" number line jo block 11 vs 12 mark karta hai.

Ek-picture summary

Sab kuch ek board pe: inode ke 12 direct + single + double + triple pointers, har ek pe block count label kiya hua ( $12, k, k^{2}, k^{3}$ ) aur data tak pahunchne ke liye hops ki depth. Left→right padho: fan-out compound karta hai, sizes explode karti hain, total ≈ 4 TB.

Recall Feynman retelling — plain words mein wapas bolo

Ek disk equal boxes ki shelf hai, har ek $B$ bytes ka. Ek file yaad rakhne ke liye hum box numbers ki list rakhte hain. Ek box $k = B / p$ box-numbers hold kar sakta hai, kyunki har number $p$ bytes wide hai. Inode seedha data ki taraf 12 numbers store karta hai (choti files ke liye great — koi extra reads nahi). Jab 12 enough nahi, woh ek poore box ko $k$ numbers ki list ke roop mein spend karta hai (single indirect: ek hop, $k$ blocks). Aur chahiye? $k$ numbers ka ek box jahan har ek doosre $k$ numbers ke box ki taraf point kare, $k \times k = k^{2}$ blocks deta hai (double). Ek aur layer $k^{3}$ deti hai (triple). Chaar regions ko add karo — yeh overlap nahi karte — blocks ko bytes mein badlo $\times B$ karke, aur $k = 1024$ ke saath tum paate ho $12 B + k B + k^{2} B + k^{3} B \approx 4 TB$ . $p$ ya $B$ badlo aur number badal jaata hai, kyunki $k$ badal jaata hai.

Recall

$k$ kya hai aur yeh kyun matter karta hai? ::: $k = B / p$ , pointers per block; har indirection level reach ko $k$ se multiply karta hai. Double indirect kyun $k^{2}$ blocks deta hai, $2 k$ nahi? ::: Do layers of fan-out multiply hoti hain: $k$ top pointers, har ek $k$ aur ke liye, toh $k \times k$ . Direct pointers choti files ke liye "free" kyun hain? ::: Inode already memory mein hota hai, toh ek direct pointer data tak zero extra disk reads mein pahunchta hai. Agar pointer size $p$ 4 se 8 bytes ho jaaye toh max file size ka kya hoga? ::: $k$ half ho jaata hai (1024 se 512), toh har level shrink hota hai; max ≈512 GB tak drop ho jaata hai.

Related: Directory Structure name→inode mapping store karta hai; Free Space Management (bitmap, free list) decide karta hai kaunse boxes free hain; File Systems (ext4, FAT, NTFS) in schemes ko practice mein implement karte hain.