File Systems and I/O for GATE: Allocation, Inodes and Worked Examples

A file looks like one continuous sequence of bytes, but a question can suddenly combine directories, inodes, file descriptors, pointer blocks, allocation overhead and physical I/O. These are not separate facts. They are layers in one path from a pathname to metadata, logical file blocks and finally device blocks. Three calculations settle most of that path: a 13 KiB file laid out under contiguous, linked and indexed allocation, an inode whose pointers put byte offset 300,000 on logical block 292, and a disk model where four scattered reads cost 38.752 ms while one sequential run of the same total size costs 11.250 ms.

File-system mental model: from pathname to stored bytes

A file is a logical byte sequence plus metadata such as size, ownership, permissions and timestamps. A directory maps a name to a file identifier. An inode-like record locates data blocks, while lower layers take the request towards storage. The filename is not inherently stored inside the inode.

To resolve /home/anu/notes.txt, start at root. Find home, search it for anu, then search anu for notes.txt. Directory search permission is checked during traversal. Cached entries and metadata mean each component need not cause a disk read.

A file descriptor is a small integer referring to an open-file description with the current offset and status flags. Multiple descriptors can share one description, while separate opens of the same inode can maintain independent offsets.

Open, read, seek and close: trace the shared file offset

Take the 12-byte file ABCDEFGHIJKL in inode 85, with descriptors 0, 1 and 2 occupied.

1. open("notes.txt", O_RDONLY) returns fd 3 at offset 0.

2. dup(3) returns fd 4, sharing the same open-file description.

3. read(3, buf, 4) returns ABCD and moves their offset to 4.

4. read(4, buf, 3) returns EFG and moves it to 7.

5. A separate open returns fd 5 at offset 0. read(5, buf, 2) returns AB and moves only its offset to 2.

6. lseek(3, 1, SEEK_SET) sets the shared fd 3 and fd 4 offset to 1, leaving fd 5 at 2.

dup duplicates a descriptor reference, not the bytes. Closing fd 3 leaves the shared description reachable through fd 4. Calls such as fread add a buffered library layer above these kernel operations.

Contiguous, linked and indexed allocation on one file

A 13 KiB file with 4 KiB blocks needs ceil(13/4) = 4 data blocks, numbered 0 to 3. Its last unit has 4 x 4 - 13 = 3 KiB unused. This assumes each block contributes a full 4 KiB; linked pointer bytes would change usable payload and must be specified.

Contiguous allocation gives fast access but makes growth awkward. Linked allocation grows easily but has slow random access and pointer overhead. Indexed allocation supports direct lookup but consumes index space. If block 60 is uncached, the indexed lookup needs an index read and a data read; if cached, only the data read remains.

Direct and indirect inode pointers: complete numerical

Assume 1 KiB = 1024-byte blocks, 4-byte pointers, 10 direct pointers, one single-indirect pointer and one double-indirect pointer. One pointer block holds 1024/4 = 256 addresses.

• Direct pointers cover file blocks 0-9.

• The single-indirect pointer covers blocks 10-265.

• Double-indirect addressing starts at block 266 and covers 256 x 256 = 65,536 blocks.

Maximum payload is 10 + 256 + 65,536 = 65,802 data blocks, or 65,802 x 1024 = 67,381,248 bytes, about 64.26 MiB. Pointer blocks are metadata, not payload.

Now locate byte offset 300,000:

1. Logical block = floor(300000/1024) = 292.

2. In-block offset = 300000 mod 1024 = 992.

3. Relative double-indirect index = 292 - 266 = 26.

4. First-level index = floor(26/256) = 0.

5. Second-level index = 26 mod 256 = 26.

With the inode cached and both pointer blocks uncached, access needs three reads: the double-indirect root, selected second-level pointer block and data block. If both pointer blocks are cached, only the data read remains. An uncached inode adds another metadata I/O.

Directories, free-space tracking and links

For 64 blocks, a bitmap needs 64 bits = 8 bytes. With free blocks {2, 3, 5, 8, 9, 10, 21}, it identifies the three-block run 8-10. A chain 2 -> 3 -> 5 -> 8 -> 9 -> 10 -> 21 can supply any three blocks, but finding a contiguous run requires examining values.

Directory organisation answers how names reach objects; allocation answers where blocks live. A single-level directory keeps one namespace for the whole disk, so two users cannot both keep a notes.txt. A two-level directory gives each user a private list, which ends that collision but leaves no way to share one file. A tree adds subdirectories to any depth, so every file has one unique path. An acyclic-graph directory lets a single file sit under two paths at once, which is exactly what the link count below records.

If notes.txt -> 85 and backup.txt -> 85, inode 85 has link count 2. Removing notes.txt reduces it to 1; backup.txt still reaches the data. A symbolic link stores a pathname such as /home/anu/notes.txt and can dangle if that name is removed.

Buffering, caching and I/O time: locality changes the result

On a read miss, the path can cross the application buffer, system call, page cache, file-system mapping, block layer, driver and device. A cache hit can avoid the device. Buffering smooths speed differences; caching retains data for reuse.

Use this simplified HDD model: seek 5 ms, rotation 7200 rpm, transfer rate 120 MiB/s, with controller, queueing and metadata time ignored.

• Average rotation = (60/7200)/2 seconds = 4.167 ms.

• A 64 KiB transfer is 0.0625 MiB, so transfer time = 0.0625/120 seconds = 0.521 ms.

• One random read = 5 + 4.167 + 0.521 = 9.688 ms.

• Four unrelated random reads = 4 x 9.688 = 38.752 ms.

• One sequential 256 KiB run transfers 0.25 MiB in 0.25/120 seconds = 2.083 ms.

• Its total = 5 + 4.167 + 2.083 = 11.250 ms.

This model demonstrates locality, not measured device performance. An SSD does not use mechanical seek or rotational-latency terms. The 5 ms seek above also assumes the request reaches the arm alone; once several requests queue, the order they are served changes that term, and File Systems and Disk Scheduling in OS works four algorithms over the same kind of model.

File-system and I/O question forms and common traps

Six forms recur in GATE-style numericals: block count and internal waste, locating one logical block under each allocation method, inode addressing down to a byte offset, counting I/O under a stated cache assumption, offsets after dup and after a second open, and HDD service time. The mistakes that cost marks are narrow and repeatable.

KnowledgeGate's question bank carries more than 150 practice questions on operating-system file management. Use File Systems and Allocation MCQs for the allocation drill, and GATE CS Exam Preparation Courses for the wider course line-up.

File systems and I/O: the short version and next step

Use one six-step chain: resolve the path, reach metadata, map byte offset to logical block, follow the pointer structure, state what is cached, then count I/O.

Your paper check is compact: 13 KiB needs 4 blocks and leaves 3 KiB; contiguous logical block 2 maps to physical block 42; offset 300,000 becomes block 292 plus byte 992, using double-indirect indices 0, 26; four random reads take 38.752 ms, while the stated sequential run takes 11.250 ms.

For a sequenced route through Operating Systems and GATE CS, use GATE Guidance by Sanchit Sir. Once you can reproduce these calculations, GATE Test Series provides broader timed practice. If a course is not what you need today, redo every calculation above from a blank page until the numbers come out the same; that alone is real preparation.