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

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

Parent note (File allocation — contiguous, linked, indexed (inode)) padhne se pehle, tumhe us chhote alphabet mein fluent hona chahiye jo woh bina rukke use karta hai. Yeh page har letter ko kuch nahi se build karta hai.

0. Disk as an array of boxes

Poora subject ek picture par tika hai: disk numbered boxes ki ek row hai, sab ek hi size ki.

1. $B$ — the block size (bytes per box)

• Plain words: ek box kitna data hold kar sakta hai.
• Picture: shelf figure mein ek single box ki height — capacity $B$ ka ek container.
• Yeh topic isko kyun chahiye: har "is file ko kitne boxes chahiye?" aur "byte 9000 kis box mein hai?" waala sawaal $B$ se division ya multiplication hai. Yeh bytes (jo users mein sochte hain) aur blocks (jo disks mein sochte hain) ke beech conversion rate hai.

2. Ek byte, aur file ke andar byte-numbering

• Picture: agar ek block ek box hai, toh ek byte uske andar ek tiny cell hai. $B=4096$ ke block mein cells $0$ se $4095$ tak numbered hote hain.
• Yeh topic isko kyun chahiye: users poochte hain "mujhe byte 9000 do." OS ko woh flat byte-number translate karni hoti hai (kaun sa box, uske andar kaun si cell) mein. Yahi translation har scheme ka dil hai.

3. Logical block $i$ vs. physical block $b$

Yeh poore parent page par sabse zyada important distinction hai. Do alag numbering systems ek saath rehte hain.

• Picture: figure mein top row file ke apne pieces $i=0,1,2,3$ hain; arrows neeche disk par scattered boxes $b=50,51,90,12$ tak jaate hain. Same data, do naam.
• Yeh topic isko kyun chahiye: allocation wahi function hai jo logical $i$ ko physical $b$ mein badalta hai. Parent page ka har formula — $\text{phys}(i)=b+i$, $\text{phys}(i)=\text{Index}[i]$ — us same arrow ke liye bas ek alag rule hai.

4. $L$ — file length in blocks

• Plain words: is file ko kitne boxes chahiye.
• Picture: mapping figure mein top-row pieces gino — woh count $L$ hai.
• Yeh topic isko kyun chahiye: contiguous allocation sirf pair $(b,L)$ store karta hai aur kuch nahi. $L$ humein $i$ ki valid range bhi batata hai: block $L$ ya usse aage maangna file ke end ke past read karna hai.

5. Byte number ko (block, offset) mein convert karna

Ab hum parent ka pehla worked example symbol-for-symbol padh sakte hain.

• Picture: file ke bytes ko end to end rakho aur har $B$ bytes ko ek box mein kaato. Floor batata hai byte kis box mein pada; modulo batata hai kitna andar (cell).

6. $p$ — the pointer size

• Picture: ek chhota arrow jo ek box ke andar draw kiya gaya hai, doosre box ki taraf point karta hua. Woh arrow draw karna box ki apni space ke $p$ bytes kharcha karta hai.
• Yeh topic isko kyun chahiye:
  • Linked allocation mein pointer har data box ke andar rehta hai, isliye usable data $B_{\text{data}}=B-p$ hai.
  • Indexed allocation mein ek index box poori tarah pointers se bhara hota hai, isliye usmein $B/p$ pointers aate hain.

7. $k$ — pointers per block

• Picture: ek khali box $k$ chhote slots mein divided, har slot mein ek arrow.
• Yeh topic isko kyun chahiye: yeh single number poori inode size calculation drive karta hai. Ek index box $k$ data blocks tak pahuncha sakta hai; indirection ka har extra level reach ko $k$ se multiply karta hai → $k$, $k^2$, $k^3$.
• Numbers: $B=4096$, $p=4$ ke saath: $k=4096/4=1024$.

8. Big-O — the cost language ($O(1)$ vs $O(n)$)

• Picture: file position ke against do curves. $O(1)$ ek flat line hai (hamesha ek lookup). $O(n)$ ek rising straight line hai (block $i$ ka cost $i+1$ reads hai).
• Yeh topic isko kyun chahiye: yahi woh yardstick hai jo poori comparison table use karti hai. "Fast random access" ka matlab $O(1)$ hai; "slow random access" ka matlab $O(n)$ hai. Contiguous aur indexed $O(1)$ hain; plain linked $O(n)$ hai.

9. Do words jo milenge: fragmentation & inode

Prerequisite map

Har arrow kehta hai "right wali idea samajhne se pehle left wali idea chahiye." Sab kuch parent note parent note par teen schemes mein funnel ho jaata hai.

Related vault topics

• Free Space Management (bitmap, free list) — OS kaise ek free box dhundh ke deta hai.
• File Systems (ext4, FAT, NTFS) — real systems jo yeh schemes implement karte hain.
• Directory Structure — jahan "start block" / "inode number" actually stored hota hai.
• Disk Scheduling — ek "seek" ki cost jo contiguous layout ko attractive banati hai.
• Virtual Memory Paging — same logical→physical mapping idea, RAM ke liye.
• 🇮🇳 Hinglish version

Equipment checklist