Operating Systems · Operating Systems
File systems
What a file is, contiguous / linked / indexed allocation, inodes and directories.
maya saves essay.txt. This lesson is that file: named bytes in disk blocks, the three allocation maps (contiguous, linked, indexed — 8 pointers × 1 KB = 8 KB), the inode that holds metadata and pointers, and the directory that holds only the name. Moving the disk head is the next lesson.
- Operating Systems
- Medium level
- 4 concepts
- 5 practice questions
1A file is named bytes on disk
maya saves essay.txt. To her it is a name and a document. To the operating system it is a sequence of bytes stored in disk blocks, plus metadata: size, permissions, timestamps. The name is not stored inside those bytes. The name lives in a directory.
A block is the disk's unit — here, 1 KB when we count pointers. A file that is 3 KB occupies three data blocks, not necessarily next to each other. How those blocks are found is allocation.
Figure. The name finds the metadata. The metadata finds the blocks. The bytes live in the blocks.
Name, bytes, blocks
- Nameessay.txt — an entry in a directory.
- BytesThe document contents.
- BlocksThe 1 KB disk units that hold those bytes.
| Piece | Where it lives |
|---|---|
| Name | A directory entry |
| Metadata | The inode (next cards) |
| Data bytes | Disk blocks pointed at by the inode |
Where does the filename essay.txt live?
- In a directory entry
- Inside the first data block of the file
- In the CPU's program counter
Directories map names to inodes. Data blocks hold file bytes, not the name.
2Contiguous, linked, indexed
Three classic ways to place essay.txt's blocks. Contiguous: the blocks sit in a row. Sequential reads are fast, but a hole the right size may not exist — external fragmentation — and growing the file means finding a new run. Linked: each block holds a pointer to the next. No external fragmentation, but a read of byte 2000 must walk the chain. Indexed: one index block holds the pointers to every data block, so a random read is one index lookup plus one data read.
The indexed max-size walk already on this card: an index block holds 8 pointers and each data block is 1 KB, so the file can be at most 8 × 1 KB = 8 KB under a single index block.
Figure. Linked allocation is a chain: block numbers need not be consecutive, but reaching a later block means following every next pointer first. Contiguous would be one solid run; indexed would replace the chain with a single index list.
How each method places blocks
- ContiguousReserve a run of consecutive blocks; start address plus length names the file.
- LinkedEach block ends with a pointer to the next; only the head need be stored in the directory or inode.
- IndexedOne index block lists every data-block address, so any offset is reachable without walking predecessors.
| Method | Sequential access | Random access | Fragmentation / growth |
|---|---|---|---|
| Contiguous | Fast (one seek) | Fast (offset arithmetic) | External fragmentation; hard to grow |
| Linked | OK (follow pointers) | Slow (walk the chain) | No external fragmentation; easy to grow |
| Indexed | OK | Fast (index lookup) | Index overhead; grows via more pointers |
A workload needs frequent random reads inside large files and must avoid walking a pointer chain. Which allocation method fits?
- Linked allocation
- Indexed allocation
- Contiguous allocation only, because indexed cannot support random access
Indexed allocation looks up any block through the index. Linked must walk predecessors; contiguous also supports random access but is not the only option, and the third choice misstates indexed.
3The inode holds metadata and pointers
A Unix inode is the metadata object for a file: size, permissions, timestamps, and the pointers that locate data blocks. The filename is not in the inode. Typical layouts mix a few direct pointers with single, double and triple indirect pointers so a small essay.txt stays cheap while a large file can still grow.
Pure indexed allocation is the same idea with one index block. Unix adds the indirect levels on top of a handful of direct pointers. The 8 KB ceiling above was the one-index-block case, not a full Unix inode.
Figure. Direct edges name data blocks immediately. The single-indirect node is itself a block of addresses — one extra hop for the later data blocks. Double and triple indirect add further hops the same way.
How an inode reaches data
- Metadata firstSize, mode and timestamps live in the inode; the data bytes do not.
- Direct pointersEarly block addresses sit in the inode itself for small files.
- Indirect levelsSingle/double/triple indirect blocks hold further addresses when the file grows past the direct slots.
Indexed max file size
An index block holds 8 block pointers and each data block is 1 KB. Under pure indexed allocation (one index block), what is the maximum file size?
- pointers per index block8
- block size1 KB
- max file size = 8 × 1 KB8 KB
Pro tip. Indexed max size = (pointers per index block) × (block size). Multi-level Unix inodes replace that single product with a sum over direct and indirect levels — same idea, more tiers.
Which statement about a Unix inode is correct?
- The inode stores the file's data bytes inline for every file size
- The inode stores metadata and pointers to data blocks
- The inode stores only the filename; block pointers live in the directory
Metadata plus block pointers are the inode's job. Filenames live in directories; data bytes live in the pointed-to blocks (aside from tiny fast-symlink specials GATE rarely centres).
4Directories map names to inodes
A directory is a table of filename → inode-number pairs. Opening /home/essay.txt walks each component: look up home in the root directory to get an inode, read that directory's blocks, look up essay.txt, then load that file's inode for metadata and block pointers.
The directory does not store the file's data and does not store permissions — those are in the inode. Two names can point at the same inode (a hard link). Deleting a name decrements a link count; the inode and blocks go away when the count hits zero.
Figure. Path lookup walks one directory component at a time — each step is a name→inode map in that directory.
Path lookup
- Split the pathEach component between slashes is one directory lookup.
- Name → inode #The directory entry yields an inode number, not a disk block list.
- Load the inodeThat inode supplies permissions, size and pointers to the file's (or next directory's) blocks.
| Structure | Holds |
|---|---|
| Directory entry | Filename and inode number |
| Inode | Metadata and pointers to data blocks |
| Data blocks | File bytes (or child directory entries) |
In a Unix-style file system, a directory entry primarily stores
- The file's data-block addresses
- The filename and the inode number
- The file's full permission bits and timestamps only
Directories bind names to inode numbers. Block addresses and the bulk of metadata live in the inode.
Notes
- File allocation methods: Contiguous (fast, external fragmentation), Linked (no fragmentation, no random access), and Indexed (index block, supports random access).
- An inode stores file metadata (size, permissions, timestamps) and pointers to data blocks; Unix inodes use direct plus single/double/triple indirect pointers.
- Disk seek time (moving the head) dominates access latency, so disk scheduling aims to minimize total head movement.
- FCFS serves requests in arrival order; SSTF picks the nearest request (may starve far ones); SCAN/LOOK sweep like an elevator.
- C-SCAN services in one direction then jumps back to the start for a more uniform wait time than SCAN.
Formulas
- Disk access time = Seek time + Rotational latency + Transfer time.
- Average rotational latency = time for half a rotation = (60 / RPM) / 2 seconds.
- SSTF total head movement = sum of |current - next nearest| across the schedule.
- Indexed allocation max file size = (pointers per index block) * (block size).
- Transfer time = (bytes to transfer) / (transfer rate).
Exam traps & shortcuts
- SSTF gives least head movement locally but can starve; SCAN/C-SCAN avoid starvation.
- LOOK/C-LOOK are optimizations of SCAN/C-SCAN that reverse at the last request instead of the disk end.
- Contiguous = fast read but hard to grow; Linked = flexible but sequential only; Indexed = balance with random access.
Reference tables
The lines GATE expects you to apply without re-deriving.
| Item | Statement |
|---|---|
| Disk access time | Seek time + rotational latency + transfer time |
| Average rotational latency | (60/\mathrm{RPM})/2 seconds (half a rotation) |
| Transfer time | (bytes to transfer) / (transfer rate) |
| Head-movement total | Sum of |current − next| along the visit order |
| Indexed max file size | (pointers per index block) × (block size) |
Name the fairness cost before you praise the shorter seek.
| Algorithm | Trap |
|---|---|
| FCFS | Fair, but long zigzag seeks |
| SSTF | Least local movement; can starve far requests |
| SCAN / LOOK | Elevator reverse; LOOK skips empty end |
| C-SCAN / C-LOOK | One-way service; return jump does not serve |
| Contiguous allocation | Fast sequential, external fragmentation |
| Linked allocation | No external fragmentation; poor random access |
Recap
essay.txt is a name in a directory, metadata in an inode, bytes in blocks.
- File
- Named bytes. The name is not inside the data blocks.
- Allocation
- Contiguous = fast + holes. Linked = chain. Indexed = pointer block.
- Indexed size
- 8 pointers × 1 KB = 8 KB for one index block.
- Inode
- Metadata + block pointers. Not the filename.
- Directory
- filename → inode number. Two names can share one inode.
Practise File systems
Reading is free and needs no account. Practice, mocks and progress live in the app.
- 5 exam-style questions on this topic, with explanations
- A 2-question practice set that ends the chapter
- Timed mocks scored with the real marking scheme
- Readiness tracked per topic, kept on your device