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

WHAT clue humein kya bata raha hai: sirf do numbers, ek start aur ek count. Yeh contiguous allocation ki fingerprint hai — contiguous ka poora point yahi hai ki arithmetic stored pointers ki jagah le leti hai, isliye metadata bahut chhota hota hai: sirf $(b,L)$. WHY: linked mein tum ek first (aur shayad last) block store karte; indexed mein tum ek index block ki taraf point karte. Dono "start + length" tak reduce nahi hote. Blocks occupied: $b=200$ se shuru hoti consecutive run, length $L=8$: $200,201,202,203,204,205,206,207.$ Last block $200+8-1=207$ hai (hum 1 isliye subtract karte hain kyunki block 200 khud 8 mein se pehla hai).

Answer: linked allocation (plain, in-block-pointer version). WHY: linked allocation mein har block apne andar next block ka address store karta hai. Block $i$ tak pahunchne ka ek hi rasta hai — block $i-1$ ka pointer padhna. Agar woh pointer garbage hai, tum block $i$ nahi dhundh sakte — aur na hi block $i+1$, $i+2$, … kyunki har ek pichle par depend karta hai. Ek broken link poori tail ko orphan kar deta hai. Contrast: indexed allocation mein har data-block address independently index array mein hota hai, isliye ek corrupted entry sirf woh ek block khoati hai, poori tail nahi. Yeh indexing ka reliability advantage hai.

Step 1 — WHAT: logical block index $i$ dhundo. Bytes 0–4095 logical block 0 mein hain, bytes 4096–8191 block 1 mein, etc. Toh $i=\lfloor \frac{30000}{4096}\rfloor =\lfloor 7.32\dots \rfloor =7.$ WHY floor: hum jaanna chahte hain kitne poore blocks of 4096 byte 30000 se pehle fit hote hain; fractional part current block ke andar ka leftover hai. Step 2 — block ke andar offset: $30000\mathrm{mod}4096=30000-7\times 4096=30000-28672=1328.$ Step 3 — physical block contiguous formula $\text{phys}(i)=b+i$ se: $\text{phys}(7)=50+7=57.$ Answer: physical block 57 padho, byte offset 1328.

(a) Logical blocks 0 se number hote hain: block 0 = physical 7, block 1 = 3, block 2 = 90, block 3 = 12. Logical block 3 tak pahunchne ka koi formula nahi — chain-walk karni padti hai, har pointer padho next address jaanne ke liye: $\underset{\text{read 1}}{\underbrace{7}}\to \underset{\text{read 2}}{\underbrace{3}}\to \underset{\text{read 3}}{\underbrace{90}}\to \underset{\text{read 4}}{\underbrace{12}}.$ Yeh $i+1=3+1=4$ disk reads hai. Yeh linked allocation ka $O(n)$ cost hai. (b) Next-pointer block ke andar hi rehta hai, $p$ bytes steal karta hai: $B_{\text{data}}=B-p=4096-4=4092\text{bytes}.$

Pehle region boundaries define karo (neeche figure dekho):

• Direct logical blocks $0$ se $11$ tak cover karta hai (12 pointers).
• Single indirect agle $k=1024$ blocks cover karta hai: $12$ se $12+1024-1=1035$ tak.
• Double indirect agle $k^2=1,048,576$ blocks cover karta hai: $1036$ se $1036+1048576-1=1,049,611$ tak.

Figure mein kya observe karo: coloured bars woh chaar pointer regions hain jo logical-block number line par rakhe gaye hain, har ek apne start aur end block ke saath labelled hai. Dekho kaise har region theek wahan shuru hota hai jahan pichla khatam hua + 1 — boundaries $\mathrm{0..1023}$ style round numbers nahi hain balki pehle waalon se offset hain. Teen arrows exercise blocks $i=5$, $i=500$, $i=100000$ ko unke regions mein daalte hain, aur har arrow ka caption read count = (pointer levels crossed) + 1 batata hai. Figure left-to-right padho aur tum kisi bhi block ko classify kar sakte ho dekh kar woh kaunsi bar mein land karta hai.

(a) $i=5$: $5\le 11$ → direct. Inode already direct pointers hold karta hai, toh seedha data padhte hain = 1 read. (b) $i=500$: $12\le 500\le 1035$ → single indirect. Hum (1) single-indirect block padhte hain address paane ke liye, phir (2) data block padhte hain = 2 reads. (c) $i=100000$: kyunki $1036\le 100000\le 1049611$ → double indirect. Hum (1) double-indirect block padhte hain, (2) us block ke double-indirect block ko padhte hain, phir (3) data block padhte hain = 3 reads. WHY read count = pointer levels ki sankhya + 1: indirection ka har level ek pointer block hai jo next address jaanne se pehle fetch karna padta hai; last +1 khud data block hai.

Har region ki reach = (data blocks ki sankhya) $\times B$: $\text{Max}=\underset{\text{direct}}{\underbrace{12B}}+\underset{\text{single}}{\underbrace{kB}}+\underset{\text{double}}{\underbrace{k^{2}B}}+\underset{\text{triple}}{\underbrace{k^{3}B}}.$ $B=4096$, $k=1024$ plug karo:

• Direct: $12\times 4096=49,152$ B $\approx 48$ KB
• Single: $1024\times 4096=4,194,304$ B $=4$ MB
• Double: $1024^2\times 4096=4,294,967,296$ B $=4$ GB
• Triple: $1024^3\times 4096=4,398,046,511,104$ B $=4$ TB

Total $=49,152+4,194,304+4,294,967,296+4,398,046,511,104=4,402,345,721,856$ bytes. Dominant term: triple indirect ($4$ TB) — har extra level reach ko $k=1024$ se multiply karta hai, isliye top level neeche wale se ~1024× bada hai. Yeh geometric growth isliye hai ki teen levels bahut bade files ke liye bhi kaafi hain.

Workload facts jo matter karte hain: files chhoti hain aur grow karti hain. Contiguous: file grow karne ka matlab hai ki next physical block already taken ho sakta hai → poori file ko bade free run mein relocate karna padega. 10 M files churning ke saath, yeh catastrophic hai. Iske saath external fragmentation bhi suffer karta hai (free space chhote holes mein toot jaata hai jo reuse karne ke liye bahut chhote hain). Yahan sabse bura. Linked: koi bhi free block kisi bhi file mein join ho sakta hai, isliye growth trivial hai (ek block append karo, last pointer patch karo) aur koi external fragmentation nahi hai. Downside: har block $p$ bytes next-pointer ko de deta hai — yeh metadata overhead hai (ek fixed tax jo har allocated block ke andar pay hota hai), true internal fragmentation nahi. Random access $O(n)$ hai — lekin yeh files 1 block ki hain, isliye practice mein $O(n)=O(1)$. Achha. Indexed (inode): growth easy hai (index mein ek pointer add karo). 1-block file ke liye address direct pointer mein hota hai → 1-read access, koi external fragmentation nahi. Cost hai inode/index metadata (phir metadata overhead, fragmentation nahi). Overall best real filesystems ke liye kyunki yeh random access bhi $O(1)$ rakhta hai agar files baad mein badi ho jaayein. Ranking: Indexed $>$ Linked $\gg$ Contiguous. Fragmentation vs overhead map: Contiguous → true external fragmentation (files ke beech unusable gaps). Linked → metadata overhead (har data block ke andar pointer bytes ka tax) plus internal fragmentation sirf file ke last partly-filled block mein. Indexed → metadata overhead (index/inode blocks) plus last-block internal fragmentation. OS woh free blocks kaise dhundhta hai, yeh dekhne ke liye Free Space Management (bitmap, free list) dekho.

Sirf triple term hatao: ${\text{Max}}_{\text{no-triple}}=12B+kB+k^{2}B=49,152+4,194,304+4,294,967,296=4,299,210,752\text{bytes}\approx 4\text{GB}.$ Original total (Ex 3.2 se) $=4,402,345,721,856$ bytes. Fraction retained: $\frac{4,299,210,752}{4,402,345,721,856}\approx 0.000977\approx 0.098\%.$ Interpretation: har inode mein ek 4-byte pointer hatane se maximum file size ~1000× collapse ho jaati hai, $\sim 4$ TB se $\sim 4$ GB tak. Har inode mein 4 bytes bachane ke liye reach ke 3 orders of magnitude khoana ek terrible trade hai — isliye triple pointer exist karta hai chahe rarely use ho.

(a) WHY pehle $k$: baad ki har count "pointers per block" mein measure hoti hai, isliye pehle fan-out compute karo. $k=B/p=8192/8=1024.$ (Coincidentally abhi bhi 1024 — block aur pointer dono double ho gaye, toh unka ratio unchanged hai.)

(b) WHY yeh formula: direct pointers bina indirection ke $D$ blocks tak pahunchte hain; har indirection level reach ko fan-out $k$ se multiply karta hai (single = $k$, double = $k\cdot k=k^2$, triple = $k^3$). Har block-count ko $B$ bytes/block se multiply karo aur sum karo: $\text{Max}=D\cdot B+kB+k^{2}B+k^{3}B=B\left(D+k+k^2+k^3\right).$ $B$ factor out karne se arithmetic clean rehti hai — parentheses ke andar pehle integer sum karo, phir ek baar end mein multiply karo.

(c) $D=12$, $k=1024$ ke saath: sum term-by-term banao (WHY: yeh dikhata hai kaunsa level dominate karta hai). $D+k+k^2+k^3=12+1024+1,048,576+1,073,741,824=1,074,791,436.$ Ab ek baar $B=8192$ se multiply karo: $\text{Max}=8192\times 1,074,791,436=8,804,691,443,712\text{bytes}\approx 8\text{TB}.$ Triple term ($k^3=1,073,741,824$) sum ka ~99.99% hai — Ex 3.2 jaisa hi geometric domination.

(d) WHY pehle region classify karo: read count equals (pointer-block levels jo hum dereference karte hain) $+1$ final data block ke liye, isliye hume sirf jaanna hai block $2,000,000$ kaunse region mein hai. Boundaries compute karo, har region ko pehle waalon se offset karte hue:

• Direct: blocks $\mathrm{0..}D-1=\mathrm{0..11}$.
• Single indirect: agle $k$ blocks $=\mathrm{12..12}+1024-1=\mathrm{12..1035}$.
• Double indirect: agle $k^2$ blocks $=\mathrm{1036..1036}+1,048,576-1=\mathrm{1036..1},049,611$.
• Triple indirect: agle $k^3$ blocks, $1,049,612$ se shuru.

Kyunki $2,000,000>1,049,611$, block $2,000,000$ triple-indirect region mein hai. WHY count 4 hai: hume triple-indirect block fetch karna hoga, phir woh jis double-indirect block ki taraf point karta hai, phir woh jis single-indirect block ki taraf point karta hai (3 pointer levels), phir khud data block: $\text{reads}=3+1=4\text{disk reads (inode already memory mein hai)}.$

Linked hamesha succeed karta hai: ek linked file ko kisi bhi position mein $s$ free blocks chahiye, kyunki har block ko sirf next ki taraf point karna hai — position irrelevant hai. Toh agar free blocks ki sankhya $\ge s$ hai, hum hamesha unme se $s$ pick kar sakte hain aur chain kar sakte hain. Formally: free blocks ek set banate hain; koi bhi $s$-subset kaam karta hai. Koi positional constraint nahi ⇒ koi failure nahi. ∎ Contiguous fail ho sakta hai: ise $s$ consecutive free blocks chahiye — ek positional constraint jo linked mein nahi hai. Yeh external fragmentation hai. Sabse chhota concrete counterexample. Woh tiniest disk lo jis par failure appear ho sake: $N=3$ blocks pattern free, used, free ke saath — yaani block 0 free, block 1 used, block 2 free.

• Free blocks $=2$, toh size $s=2$ ka request $s\le$ (free blocks) satisfy karta hai.
• Is request par Linked: blocks 0 aur 2 pick karo, chain $0\to 2$. ✔ succeeds (positions matter nahi karte).
• Is request par Contiguous: 2 adjacent free blocks chahiye, lekin sirf free blocks (0 aur 2) used block 1 se separated hain — length 2 ki koi run exist nahi karti. ✘ fails chahe $s=2\le 2$ free blocks hon.

WHY $N=3$ sabse chhota hai: $N=1$ ya $N=2$ ke saath tum "free–used–free" split nahi bana sakte (tumhe kam se kam ek used block beech mein chahiye do free waalon ke, isliye kam se kam 3 blocks). Isliye $N=3$ woh minimal disk hai jo prove karta hai "enough free space" $\ne$ "enough contiguous free space." ∎

Contiguous file (start=200, len=8) ka last block ::: 207 Linked file mein logical block 3 tak pahunchne ke reads ::: 4 4096/4 inode mein logical block 500 ka region ::: single indirect (2 reads) Logical block 100000 ka region ::: double indirect (3 reads) Max file size, 4096/4 inode, bytes mein ::: 4,402,345,721,856 ($\approx$ 4 TB) Triple-indirect hatane ke baad max (4096/4) ::: $\approx$ 4 GB (original ka lagbhag 0.098%) $k$ jab $B=8192$, $p=8$ ::: 1024