File systems: allocation, inodes और links
लक्ष्य और मान्यताएँ
Allocation methods compare करें, indexed-file capacity/access cost निकालें और file identity को नामों से अलग करें। पूर्वज्ञान: byte/block arithmetic और pointers। यहाँ simplified UNIX-जैसा inode model है; वास्तविक formats अलग हो सकते हैं। KiB=1024 bytes। Logical blocks zero से शुरू। Capacity में अलग file-size fields, disk limits और reserved pointer values छोड़ते हैं, जब तक दिए न हों। यह पाठ किसी वास्तविक filesystem में बदलाव नहीं करता।
1. नाम label हैं, contents blocks में हैं
Warehouse catalogue सोचें: label से record मिलता है और record storage locations बताता है। कई labels एक record को इंगित कर सकते हैं। Directory भी filename को inode number जैसी file identity से map करती है। Inode metadata और data blocks खोजने की जानकारी रखता है। Pathname directories से resolve होता है; नाम स्वयं पूरी file या सभी storage addresses नहीं है।
File descriptor process का open-file handle है, globally unique inode number नहीं। Separate opens के current offsets अलग हो सकते हैं; open descriptor duplicate करने पर descriptors एक open-file description और offset share कर सकते हैं। केवल filename समान होने से offset sharing न मानें।
2. तीन allocation तरीके
Contiguous allocation file को neighboring blocks की run में रखता है। Physical start s हो तो allocated range में logical block j का स्थान s+j है। Random access आसान, पर growth और पर्याप्त लंबी run खोजना कठिन हो सकता है। Variable-length contiguous model में external fragmentation हो सकती है।
Linked allocation हर block में next-block pointer रखता है। Growth scattered blocks ले सकती है, पर extra indexing न हो तो दूर का block ढूँढ़ने के लिए head से links traverse करने होंगे। Pointers space लेते हैं और broken link से chain का बाकी हिस्सा खो सकता है। FAT-जैसा format links को अलग table में रखता है; वह हर on-disk data block से pointer पढ़ने के समान नहीं।
Indexed allocation अलग index structure में block addresses रखता है। Logical block number address चुनता है; data-chain walk जरूरी नहीं। Index blocks space और reads लेते हैं। Extent-based format हर data block का pointer रखने की जगह runs रखता है। ये tradeoffs हैं; एक design हर workload में सर्वश्रेष्ठ नहीं।
3. Direct और indirect pointers
Inode में 6 direct, एक single-indirect और एक double-indirect pointer लें; triple नहीं। Block=1024 bytes, pointer=4 bytes। एक index block में 1024/4=256 pointers। Direct से 6 data blocks। Single-indirect से 256। Double-indirect से outer और inner index blocks द्वारा 256×256=65536 data blocks।
Maximum data blocks=6+256+65536=65798। Maximum data bytes=65798×1024=67,377,152। Index blocks metadata हैं, extra file data capacity नहीं। पूरी तरह भरी structure में 1 single-indirect index, 1 double-indirect outer और 256 inner, कुल 258 index blocks लगते हैं; इनके अलावा data blocks और inode है।
4. Reads गिनने से पहले byte ढूँढ़ें
इसी format में logical blocks 0..5 direct, 6..261 single-indirect, 262 से आगे double-indirect हैं। Byte offset 270000 पर logical block=floor(270000/1024)=263 और offset=688। Block 263 double-indirect region में है। Region start घटाएँ: 263−262=1। Outer index=floor(1/256)=0, inner index=1। चुने data block में byte offset 688 है।
मानें inode RAM में है, relevant index/data blocks cached नहीं, और हर block के लिए एक disk read है। Direct में 1 data read। Single-indirect में 1 index+1 data=2। Double-indirect में outer+inner+data=3। इसलिए ऊपर के offset को 3 reads चाहिए। Directory lookup/inode reads यहाँ excluded हैं। Cached index से count बदलेगा; तीन reads हर file access का सार्वभौमिक नियम नहीं।
5. Hard links और symbolic links
इस model में hard link उसी filesystem की उसी file identity के लिए दूसरा directory entry है। Data copy नहीं होती। a,b एक inode के नाम हों और a unlink हो, तो b अभी वही file दिखाता है। Symbolic link अलग object में target path रखता है। उसे resolve करते समय path follow होता है; target name हटे तो symlink बचकर dangling हो सकती है। एक नाम हटाना या move करना सभी hard-link names हटाना नहीं।
Simplified UNIX-like regular file में आखिरी name unlink करने से link count zero होता है। Open reference बची हो तो references release होने तक storage रखी जाती है। इसलिए unlink नाम हटाना है, तुरंत physical reclamation की guarantee नहीं। इसी कारण unlinked पर open file disk space ले सकती है। Permissions और filesystem-specific rules लागू हैं; ये conceptual operations हैं, कुछ delete करने का निर्देश नहीं।
6. Free-space bookkeeping
हर data block के लिए एक bit वाली bitmap stated convention से allocation बताती है। 32768 managed blocks के लिए raw bitmap=32768 bits=4096 bytes=4 KiB। 1 KiB storage blocks में चार blocks। Scheme कहे बिना एक byte प्रति block न लें। Failure के पार metadata/data updates consistent होने चाहिए; crash recovery/journaling आगे का विषय है। Successful buffered write को durable media completion का प्रमाण न मानें।
परीक्षा checklist
Filename, inode, open handle, index और data block अलग रखें। Powers से पहले pointer fan-out लिखें। Byte offset को logical block तथा intra-block offset में बाँटें, फिर region का start घटाएँ। Reads से पहले caching assumptions लिखें। Data capacity और metadata overhead अलग हैं; name removal, data copying और तत्काल reclamation भी अलग हैं।
मौलिक अभ्यास: छह single-correct MCQ
हर प्रश्न में ठीक एक विकल्प चुनें। हर प्रश्न की आवश्यक मान्यताएँ उसी में दी गई हैं।
FS01. Inode में 6 direct, एक single-indirect, एक double-indirect pointer है। Blocks 1024 bytes, pointers 4 bytes। अन्य limits छोड़कर कितने data blocks address होंगे?
A. 262 B. 65798 C. 66056 D. 65536
उत्तर: B
A: 262 में double-indirect region छूटा है।
B: Fan-out=256; total=6+256+256²=65798।
C: इसमें 258 metadata index blocks data capacity में जोड़ दिए।
D: 65536 केवल double-indirect data region है।
FS02. 6 direct pointers, indirect block में 256 entries और zero-based logical blocks पर पहला double-indirect data block number क्या है?
A. 6 B. 256 C. 261 D. 262
उत्तर: D
A: 6 से single-indirect शुरू है।
B: छह direct blocks भी गिनने हैं।
C: 261 आखिरी single-indirect block है।
D: Direct 0..5, single 6..261; अगला 262।
FS03. Requested data block double-indirect है। Inode RAM में; relevant दोनों index और data block cached नहीं। हर block एक I/O; pathname lookup excluded। कितनी reads?
A. 1 B. 2 C. 3 D. 4
उत्तर: C
A: दोनों index reads छूटी हैं।
B: एक index level या data read छूटी है।
C: Outer index, inner index, फिर data: तीन।
D: Inode RAM में है, उसकी read excluded है।
FS04. एक filesystem में regular-file a और b same inode के hard links हैं। कोई अन्य बदलाव नहीं। a unlink करने के बाद क्या सही है?
A. b अलग copy बनता है B. b उसी file का नाम रहता है C. b symlink की तरह अनिवार्य dangling है D. Data तुरंत नष्ट होना अनिवार्य है
उत्तर: B
A: Unlink file copy नहीं करता।
B: b का entry अभी उसी inode को दिखाता है।
C: Hard link identity को दिखाता है, removed path a को नहीं।
D: बचा hard link file का नाम रखता है।
FS05. Free-space bitmap 32768 managed blocks में हर एक के लिए एक bit रखती है। Headers/padding छोड़कर bytes कितने?
A. 32768 B. 4096 C. 1024 D. 256
उत्तर: B
A: यह एक bit की जगह एक byte प्रति block है।
B: 32768/8=4096 bytes।
C: 1024 bytes केवल 8192 bits रखते हैं।
D: 256 bytes केवल 2048 bits रखते हैं।
FS06. दिए UNIX-like model में regular file का आखिरी hard-link name हटता है, पर process ने file अभी open रखी है। क्या हो सकता है?
A. Open references release होने तक storage allocated रहे B. हर descriptor तुरंत inode number बने C. File अनिवार्य दूसरे directory में copy हो D. सभी buffered writes durable हों
उत्तर: A
A: Open references unlinked file को जीवित रख सकती हैं।
B: Descriptors और inode identifiers अलग हैं।
C: नाम हटाने से copy नहीं बनती।
D: Link removal ऐसी durability guarantee नहीं देता।
स्रोत और दायरा
यह मौलिक पाठ GATE 2026 course के मौजूदा OS foundations को आगे बढ़ाता है। इसका संबंध आधिकारिक 2026 syllabus के Section 8 से है; यह पूरे OS या GATE 2027 की पूर्ण तैयारी का दावा नहीं है। अभ्यास मौलिक हैं, पिछले वर्षों के प्रश्न नहीं।
- Official GATE 2026 CS syllabus, Section 8
- OSTEP: Files and Directories
- OSTEP: File System Implementation
स्रोत जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन