File allocation — contiguous, linked, indexed (inode): Question bank

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

Poore note mein use hone wale plain-word meanings ki reminders, taaki yahan kuch bhi bina explain kiye notation par depend na kare. Isse ek baar padho aur neeche har trap self-contained ho jaata hai:

Recall

Ek block disk ka ek fixed-size chunk hota hai (e.g. $B = 4096$ bytes) — woh sabse chhoti unit jise OS allocate karta hai. Toh $B$ = bytes per block.
Ek pointer ek disk address hota hai (ek number jo ek physical block ko name karta hai). Bytes mein iska size $p$ likha jaata hai (e.g. $p = 4$ bytes). Toh $p$ = bytes jo ek block address store karne ke liye chahiye.
$k = B / p$ = ek block ke andar kitne pointers fit hote hain. Yeh ratio kyun? Ek pointer-block sirf ek block ( $B$ bytes) hai jo addresses ( $p$ bytes each) se bhara hua hai, toh woh unke $B \div p$ rakhta hai. $B = 4096, p = 4$ ke saath: $k = 1024$ .
Logical block $i$ = file ka $i$ -wa block (0, 1, 2, …). Physical block = disk par actual slot.
Index array Index[] (indexed allocation): ek table jahan entry Index[i] woh physical block store karta hai jo logical block $i$ ko hold karta hai. Yeh file ke index block mein rehta hai. Index[i] lookup karna ek single array read hai — koi chain walk nahi.
inode (Unix index node): ek chhota per-file structure jo file ki metadata plus uska pointer array hold karta hai — 12 direct pointers (seedha data blocks tak), phir 1 single, 1 double, 1 triple indirect pointer (har ek pichle se ek level gehri block-of-pointers ki taraf point karta hai). File open hone ke baad uska inode RAM mein rehta hai.
$O (1)$ matlab hai "constant work, file size se independent"; $O (n)$ matlab hai "work blocks ki sankhya ke saath badhti hai".
External fragmentation = free space exist karta hai lekin chhote holes mein split ho jaata hai jo use karne ke liye bahut chhote hain — dekho External vs Internal Fragmentation.
Internal fragmentation / overhead = allocated block ke andar barta hua space.

Poora topic ek three-way tension hai — neeche har "why" ke liye yeh picture mind mein rakho:

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

Formula Triple-indirect factor, ek waqt mein ek multiplication

Reach = kitne data blocks ek pointer ultimately reach kar sakta hai. Levels walk karo:

Direct: pointer ek data-block address hai → $1$ data block reach karta hai. Inke 12 → $12$ blocks.
Single indirect: pointer ek block-of-pointers ko name karta hai jo $k$ addresses hold karta hai, har ek ek data block → $k$ blocks reach karta hai.
Double indirect: ek block-of-pointers ko name karta hai jo $k$ addresses hold karta hai, lekin unme se har ek ek single-indirect block hai jo $k$ reach karta hai → $k \times k = k^{2}$ blocks.
Triple indirect: $k$ pointers ko name karta hai, har ek ek double-indirect block hai jo $k^{2}$ reach karta hai → $k \times k^{2} = k^{3}$ blocks. Har extra level $k$ se multiply karta hai kyunki tum ek aur poora block of $k$ fan-out gain karte ho. Har block-count ko $B$ bytes se multiply karo sizes pane ke liye; triple term $k^{3} B$ dominate karta hai kyunki $k^{3} ≫ k^{2} ≫ k$ .

True or false — justify

True or false: Contiguous allocation

O (1)

random access deta hai, toh yeh overall best scheme hai.

"Best overall" par False.

O (1)

real hai (address bas start + i hai, ek addition), lekin yeh external fragmentation aur advance mein file size jaanne ki zaroorat ke saath payment karta hai — yeh trade-off triangle ke ek corner (fast access) mein jeetta hai jabki baaki do kho deta hai.

True or false: Linked allocation mein zero wasted space hai kyunki koi bhi free block kisi bhi file mein join ho sakta hai.

Sirf external half sach hai — koi free block kabhi unusable nahi hota. Lekin har block phir bhi next-pointer par

p

bytes kharach karta hai, toh internal overhead hai; block per usable data

B - p

hai,

B

nahi.

True or false: FAT scheme data blocks ke andar pointer overhead ko eliminate kar deta hai.

Sach. FAT har "next" pointer ko data blocks se nikaal ke ek central table mein le aata hai, isliye har data block poore

B

bytes hold karta hai; pointers ab table mein rehte hain.

True or false: Indexed (inode) allocation har tarah ki fragmentation se completely bachta hai.

False. Yeh external fragmentation se bachta hai (data blocks kahin bhi baith sakte hain), lekin index block khud metadata overhead hai, aur file ka aakhri data block abhi bhi partly empty hota hai (internal fragmentation).

True or false: Sirf 12 direct pointers use karne wali file ke kisi bhi block ko fetch karne ke liye zero extra pointer-block reads chahiye.

Sach. 12 direct pointers inode ke andar hote hain, jo file open hone ke baad already memory mein hota hai, toh blocks 0–11 mein se har ek exactly ek data read karta hai aur koi pointer-block read nahi.

True or false: Linked allocation mein, agar teesre block ka pointer corrupt ho jaaye, toh sirf woh ek block lost hota hai.

False. Ek broken pointer chain ke poore remainder ko orphan kar deta hai — corruption ke baad ka har block unreachable ho jaata hai, kyunki unke addresses sirf us pointer ko follow karke jaane ja sakte the.

True or false: Contiguous allocation ko file ko sequentially padhte waqt kabhi disk seek nahi chahiye.

Essentially sach. Kyunki blocks physically consecutive hain, ek sequential read adjacent locations ko bina koi head repositioning ke walk karta hai — theek yahi wajah hai ki yeh streaming reads mein excels karta hai.

True or false: Triple-indirect pointer Unix file ki maximum size ka main contributor hai.

Sach. Har indirection level reach ko

k

(pointers per block) se multiply karta hai, toh triple level

k^{3} B

contribute karta hai — geometrically direct, single (

k B

), aur double (

k^{2} B

) contributions ko combined dominate karta hai.

True or false: Ek contiguous file ko grow karna hamesha sasta hai kyunki tum bas blocks append karte ho.

False. Tum sirf tabhi append kar sakte ho jab next physical block free ho. Agar ek neighbour file wahan already baith gayi hai, toh poori file ko ek bade free run mein relocate karna padega — potentially bahut expensive.

Spot the error

Spot the error: "Indexed allocation mein logical block

i

ke liye, physical address start + i hai."

Woh contiguous formula hai. Indexed allocation mein koi start nahi hai; address Index[i] hai, index array mein direct lookup, precisely isliye kyunki data blocks consecutive hone ki zaroorat nahi hai.

Spot the error: "Linked allocation

O (1)

access deta hai agar hum directory mein pehla aur aakhri dono blocks store kar lein."

Aakhri block store karna sirf appends mein help karta hai, random access mein nahi. Kisi middle block

i

tak pahunchne ke liye tumhe abhi bhi front se

i + 1

pointers follow karne padte hain — koi cheez tumhe middle mein jump karne nahi deti.

Spot the error: "

B = 4096

aur

p = 4

ke saath, ek single index block zyada se zyada

4096

blocks ki file ko address kar sakta hai."

Yeh

k = B / p = 4096/4 = 1024

pointers hold karta hai, toh yeh

1024

blocks (lagbhag 4 MB) address karta hai,

4096

nahi. Confusion bytes-per-block (

B

) ko pointers-per-block (

k

) se swap kar deta hai.

Spot the error: "FAT scheme mein, logical block

i

padhne ke liye abhi bhi

i + 1

disk reads chahiye chain walk karne ke liye."

Chain ab ek in-memory table mein rehti hai, toh ise walk karna RAM lookups karta hai, disk reads nahi. Tum sirf ek disk read karte ho: woh final data block.

Spot the error: "Double-indirection ke saath logical block 100000 fetch karne mein 2 disk reads lagte hain: double-indirect block aur data block."

Tum middle level bhool gaye. Double indirection matlab hai inode → double-indirect block → single-indirect block → data block, toh yeh 3 disk reads hain (do pointer blocks phir data).

Spot the error: "Contiguous allocation har block mein ek next-pointer store karta hai jaise linked karta hai, bas consecutively."

Nahi. Contiguous koi bhi per-block pointers store nahi karta — "next" block arithmetic se implied hai (b + i). Pointers ki woh absence hi exactly wajah hai ki iska metadata sirf (start, length) hai.

Spot the error: "Inode mein 12 direct pointers ek aisi block ki taraf point karte hain jo 12 data addresses list karta hai."

Woh seedha 12 data blocks ki taraf point karte hain, kisi list ki taraf nahi. Sirf single/double/triple indirect pointers intermediate blocks-of-pointers ki taraf point karte hain.

Why questions

Teen allocation schemes kyun exist karte hain bajaye ek winner ke?

Kyunki teen goals — fast random access, koi wasted space nahi, aasaan growth — conflict karte hain (triangle figure dekho). Har scheme ek sacrifice karta hai doosre kharidne ke liye, isliye "sahi" choice workload par depend karti hai.

Linked allocation pointer size

p

ko usable capacity se kyun subtract karta hai lekin contiguous nahi?

Linked next-block pointer ko har data block ke andar store karta hai,

p

bytes chura leta hai; contiguous ko aisa pointer chahiye hi nahi kyunki agla block arithmetic se milta hai (b + i), toh saare

B

bytes data rehte hain.

Unix multiple levels of indirection kyun use karta hai ek giant index block ke bajaye?

Bahut badi files ke liye kaafi bada ek flat index bahut zyada choti files ki overwhelming majority par space waste karta. Tiered inode chhoti files ko zero-overhead direct pointers deta hai jabki

k

-fold fan-out ke through bahut badi files ko possible bhi banata hai — ek 80/20 optimisation.

Linked aur indexed allocation ke under external fragmentation impossible kyun hai?

Dono data blocks ko disk par kahin bhi rehne dete hain, toh koi bhi single free block kisi bhi file ke liye usable hai. External fragmentation tabhi aata hai jab tum ek badi contiguous run demand karte ho, jo sirf contiguous allocation karta hai.

Indexed allocation

O (1)

random access restore kar sakta hai jabki linked nahi kar sakta — kyun?

Index block saare block addresses side by side hold karta hai, toh Index[i] ek direct array lookup hai. Linked addresses ko blocks ke andar hi scatter karta hai, har ek ko discover karne ke liye sequential walk force karta hai.

Ek file ki maximum possible size jaanna aage se utne blocks allocate karne ki zaroorat kyun nahi?

Indirect pointer blocks lazily create hote hain — sirf jab file us range mein grow karti hai. Formula reachable ceiling deta hai; ek chhoti file sirf woh direct blocks allocate karti hai jo woh use karte hain.

Edge cases

Edge case: Jab ek contiguous file ki length

L = 1

ho toh phys(i) = b + i ka kya hota hai?

Sirf block 0 valid hai (

i = 0 \Rightarrow

physical

b

); koi bhi

i \geq 1

out of range hai. Formula abhi bhi sahi hai — bound

0 \leq i < L

hi ise guard karta hai.

Edge case: Indexed allocation mein, ek brand-new empty file ka index block kya contain karta hai?

Abhi tak koi valid data pointers nahi (saare Index[] entries unused/null). Index block exist kar sakta hai lekin zero logical blocks map karta hai jab tak data likha nahi jaata.

Edge case: Ek Unix file mein exactly 12 blocks hain — kya yeh kabhi single-indirect pointer touch karta hai?

Nahi. Blocks 0–11 precisely 12 direct pointers fill karte hain, toh single-indirect pointer unused rehta hai aur kisi bhi block ko padhna sirf ek data read karta hai.

Edge case: Linked allocation mein logical block 0 ki access cost kya hai?

Yeh sabse sasta case hai: block 0 directory ka stored first block hai, toh ek single read lagta hai (

i + 1 = 1

) — linked allocation sirf baad ke blocks ke liye hurt karta hai.

Edge case: Contiguous allocation mein, "pehle se file size jaanna zaroor hai" ka matlab ek aisi file ke liye kya hai jo shrink hoti hai?

Shrink karna aasaan hai — bas length reduce karo aur tail blocks free karo, ek hole chodke. Dard growth mein hai, kyunki freed hole kisi bade neighbour ke liye reusable nahi ho sakta, external fragmentation ko feed karta hai.

Edge case: Agar file ki size block size ka exact multiple hai, toh kya uske aakhri data block mein abhi bhi internal fragmentation hai?

Nahi — ek perfect multiple final block ko completely fill karta hai, zero internal waste chodke. Internal fragmentation sirf tabhi aata hai jab aakhri block partially used ho.