Everything a program persists eventually becomes blocks on a storage device. The file system organizes those blocks into a named hierarchy, and the OS schedules and buffers the I/O that moves data between memory and disk. This article covers file allocation, the inode model, disk-scheduling algorithms, and the I/O techniques interviewers expect.
What a file system provides
A file system maps human-friendly names and a directory tree onto raw disk blocks, while enforcing permissions, tracking free space, and surviving crashes. Its core on-disk structures are:
- Boot block / superblock: filesystem-wide metadata (block size, total/free counts, inode count).
- Inode (index node): per-file metadata — size, owner, permissions, timestamps, and pointers to data blocks. Crucially, the inode does not store the file name; names live in directory entries.
- Directory: a special file mapping names → inode numbers. This indirection lets multiple names (hard links) point to one inode.
- Data blocks: the file contents themselves.
Hard link vs symbolic link: a hard link is another directory entry pointing at the same inode (same file, reference-counted; the data survives until the last link is removed). A symbolic (soft) link is a small file containing a path; it can cross filesystems and can dangle if the target is deleted.
File allocation methods
How does a file's set of data blocks get laid out on disk?
| Method | How | Pros | Cons | |--------|-----|------|------| | Contiguous | One run of consecutive blocks | Fast sequential + random access; simple | External fragmentation; hard to grow a file | | Linked | Each block points to the next | No external fragmentation; grows easily | No random access (must follow chain); a broken pointer loses the rest | | Indexed | An index block lists all data-block pointers | Random access; no external fragmentation | Index block overhead; large files need multiple index blocks |
Real filesystems refine indexed allocation. The Unix inode uses multilevel indexing: a handful of direct pointers for small files, then single, double, and triple indirect pointers for progressively larger files. Small files stay cheap (data reachable directly) while huge files remain addressable, and access cost grows only logarithmically with size.
FAT (File Allocation Table) is linked allocation with all the "next block" pointers gathered into one in-memory table, which restores random access by letting you follow the chain in RAM instead of on disk.
Disk geometry and access time
On a spinning hard disk (HDD), a request's service time has three parts:
- Seek time: move the arm to the target track — the dominant, mechanical cost (milliseconds).
- Rotational latency: wait for the sector to spin under the head (on average, half a rotation).
- Transfer time: read/write the bytes.
Because seek time dominates and is roughly proportional to arm travel, disk scheduling aims to service requests in an order that minimizes total head movement. SSDs have no seek or rotational latency — access is uniform — so disk-scheduling algorithms largely stop mattering for them; SSD performance instead cares about wear leveling, write amplification, and the erase-before-write (garbage-collection) behavior of flash.
Disk-scheduling algorithms
Given a queue of track requests and a current head position, order them to minimize head movement.
- FCFS: serve in arrival order. Fair, but the head can zig-zag wildly.
- SSTF (Shortest Seek Time First): always serve the nearest request. Good average seek time, but starves distant requests and can get "stuck" servicing a cluster.
- SCAN (elevator): the head sweeps in one direction servicing everything, reaches the end, then reverses. No starvation; like an elevator.
- C-SCAN (circular SCAN): sweep in one direction only; at the end, jump back to the start without servicing and sweep again. Gives more uniform wait times than SCAN, which favors the middle tracks.
- LOOK / C-LOOK: like SCAN/C-SCAN but reverse at the last request rather than the physical end of the disk, saving needless travel.
Worked example: head at track 53, queue 98, 183, 37, 122, 14, 124, 65, 67.
- FCFS total movement = |53−98| + |98−183| + |183−37| + |37−122| + |122−14| + |14−124| + |124−65| + |65−67| = 640 tracks.
- SSTF repeatedly picks the nearest (65, 67, 37, 14, 98, 122, 124, 183) for 236 tracks — far better, but 183 waited a long time.
- SCAN toward larger tracks (65, 67, 98, 122, 124, 183, then reverse to 37, 14) sweeps smoothly with no starvation.
The takeaway interviewers want: SSTF minimizes average seek but risks starvation; SCAN/C-SCAN trade a little average performance for fairness and bounded waiting.
I/O techniques
How does data actually move between a device and memory?
- Programmed I/O (polling): the CPU busy-waits checking a status register. Simple but wastes CPU.
- Interrupt-driven I/O: the device raises an interrupt when ready, freeing the CPU to do other work meanwhile. Better, but one interrupt per byte/word is costly for bulk transfers.
- Direct Memory Access (DMA): a DMA controller transfers a whole block directly between device and memory, interrupting the CPU only once when the entire transfer completes. This is how disks and NICs move bulk data without saturating the CPU.
Buffering, caching, and blocking
- The OS keeps a buffer/page cache in RAM: reads are served from cache when possible, and writes are often buffered and flushed later (write-back) for speed.
- Write-back caching is fast but risks data loss on a crash; write-through is safe but slower. Filesystems add journaling — writing intended changes to a log first — so a crash can be recovered by replaying or discarding the journal, avoiding corruption.
- Blocking I/O parks the calling thread until the operation completes; non-blocking / asynchronous I/O returns immediately and notifies later (via callbacks,
epoll,io_uring), which is essential for high-concurrency servers.
Common follow-ups and gotchas
- "Where is the file name stored?" In the directory entry, not the inode. The inode holds metadata and block pointers; this separation is what makes hard links possible.
- "Which disk scheduler avoids starvation?" SCAN/C-SCAN (and LOOK variants). SSTF and pure priority can starve.
- "Do scheduling algorithms matter for SSDs?" Largely no — with no seek or rotational delay, access is uniform, so ordering by track is pointless; SSD concerns shift to write amplification and wear leveling.
- DMA's win is offloading bulk transfer and reducing interrupts to one per block, not making a single byte faster.
- Gotcha: rotational latency averages half a rotation, not a full one — a frequent arithmetic slip in access-time questions.