Operating System I/O Management and File Systems

What the CPU does while a disk read is in flight, and how a file name reaches the actual data, laid out as one continuous path.

I/O management and the file system are the two axes on which an operating system handles storage devices. The first owns the path data travels between device and memory. The second decides how that data is laid out on disk.

Three ways to handle I/O

How the CPU drives a device comes down to how much the CPU participates in the transfer. Polling makes the CPU wait, interrupts remove the waiting, and direct memory access removes the transfer itself.

Polling means the CPU sits in a loop repeatedly checking the device status register. It cannot do anything else until the device is ready, so it wastes the CPU. Interrupt-driven I/O has the device raise an interrupt, a hardware signal that suspends whatever the CPU is doing, when the operation completes. The CPU can work on something else while waiting, but the CPU still performs the transfer itself.

Direct Memory Access (DMA) has a DMA controller move data between memory and device directly. The data never passes through the CPU, and an interrupt fires only when the transfer finishes. Because CPU involvement is minimal, it is the most efficient option for bulk transfers.

Synchronous vs asynchronous, blocking vs non-blocking

These are two independent axes, which yields four combinations. Synchronous versus asynchronous is about who checks for and announces completion. Blocking versus non-blocking is about whether control returns immediately from the call.

Using non-blocking on its own degenerates into polling, because you keep retrying until the data arrives. That is why it is normally paired with the I/O multiplexing covered below. select(), poll(), and epoll_wait() are usually classified as synchronous I/O multiplexing.

I/O multiplexing

I/O multiplexing is the technique of watching many file descriptors from a single thread. A file descriptor (fd) is an integer handle referring to an open file or socket. Once the watch set grows to thousands, the cost of watching itself determines performance.

select copies the entire fd list into the kernel on every call, and the kernel walks all of them, hence O(n). On Linux the FD_SETSIZE limit usually caps it at 1024 descriptors.

epoll registers an fd once into a kernel red-black tree via epoll_ctl(). After that, epoll_wait() returns only the ready descriptors, so the cost is close to O(1) in the number of events. Since the list is not copied on each call, the gap widens as connection counts grow.

Disk scheduling

A hard disk drive (HDD) is a mechanical device, so seek time, the time for the head to move to the target track, dominates performance. Scheduling reorders pending requests to shorten total head travel.

The numbers below are the total head movement from the standard disk scheduling example in Operating System Concepts (Silberschatz et al.). The head starts at 53, tracks range from 0 to 199, and the request queue is 98, 183, 37, 122, 14, 124, 65, 67.

SSTF is fast because it only serves nearby requests, but distant requests can be deferred forever, which is starvation. SCAN sweeps in one direction like an elevator and prevents starvation. On an SSD, random access cost is uniform, so this kind of scheduling has little effect.

Buffering and the page cache

Buffering holds data briefly to absorb the speed mismatch between a device and the code consuming its data. It splits into three structures.

The page cache is the kernel region that keeps disk blocks in memory so repeat access is fast. The default write policy is write-back, which writes to the cache first and pushes to disk later. Write-through writes to cache and disk at the same time, which is safer but slower. Circular buffers show up often in io_uring and in the transmit and receive rings of network drivers.

File system disk layout

A traditional Unix file system (the ext family) divides the disk into four regions: boot code, metadata, the inode array, and the actual data, in that order.

ext4 divides the disk into block groups, each holding a superblock copy, bitmaps, and an inode table. Distributing them this way keeps related data within one group for better locality, and the copies help with damage recovery.

inodes and block pointers

An inode (index node) is the data structure holding a file's metadata and the locations of its data blocks. The file name is not in the inode; it lives in the directory entry as a (name -> inode number) mapping. That is why several names can point at the same inode.

A traditional ext2/ext3 inode has 15 block pointers. Twelve point directly at data blocks, and the remaining three go through indirect blocks.

Assuming 4KB blocks and 4B pointers, each indirect level covers the capacity below. Small files are reached through direct blocks alone, and only large files pay the cost of the indirect levels.

ext4 uses extents instead of indirect blocks. A run of contiguous blocks is expressed as (start block, length), which cuts metadata overhead for large files.

The three-level file descriptor tables

An fd number returned by open() passes through three levels before it reaches the actual inode. The fd table is per process, while the open file table and the inode table are shared by the kernel.

The offset, meaning the read/write position, lives in the open file table entry rather than in the fd. Opening the same file twice creates two entries, so the offsets are independent. Duplicating an fd through fork() or dup() shares one entry instead, so the offset moves for both.

File allocation methods

How data blocks are laid out on disk determines direct access performance and fragmentation. The trade-offs among the three methods are sharp.

Contiguous allocation reaches any offset given the start block and length, but a growing file needs relocation. Linked allocation stores a next-block pointer in each block, which makes resizing easy but direct access slow. FAT (File Allocation Table) is a variant of linked allocation that gathers the next pointers into a separate table, improving direct access. The Unix inode is a form of indexed allocation.

Journaling and crash recovery

Journaling writes changes to a journal region (a log) before writing data in place. This write-first approach is called write-ahead logging (WAL). Even if power is lost mid-write, the journal makes it possible to restore consistency.

Recovery hinges on the commit point. A crash before the commit (TxEnd) means the journal is discarded and the change never happened; a crash after it means the journal is replayed and written in place again. What gets recorded in the journal defines the mode.

Ordered writes data blocks to disk first and then commits the metadata, so the data the metadata points at is always valid. Writeback guarantees no ordering, so after a crash the metadata can point at blocks that were never written, exposing garbage data. Copy-on-write (CoW) file systems such as Btrfs and ZFS take a different route: they never overwrite in place but write to new blocks, keeping consistency without a journal. The cost is write amplification, since even a small modification allocates new blocks.

Summary

The core of I/O management is how far the CPU steps back from the transfer. Polling makes the CPU wait, interrupts remove the waiting, and DMA hands the transfer itself to a controller. In the same spirit, epoll registers an fd once and returns only what is ready, watching large connection counts at close to O(1).

On the file system side, the central design decision is separating names from data. A directory entry turns a name into an inode number, the inode reaches the data through direct and indirect block pointers, and the journal preserves consistency after a crash. Viewed together, the two areas make it clear how scheduling, caching, block pointers, and journaling interlock during a single line read from a file.