Unit 10 · Self-check
Unit 10 Self-Check Quiz
Twenty-four questions covering the file abstraction, inodes, directory organisation, file allocation, journaling, and modern file system designs. Each question can be expanded to reveal a model answer.
Questions
Multiple choice and short answer
Answer each question before expanding. These span all seven lessons of Unit 10.
Question 1
What is the file abstraction, and what operations does the file system provide on files?
Show answer
A file is a named, persistent sequence of bytes. The abstraction hides the physical layout of storage: the application sees a linear array of bytes, and the file system maps that array onto disk sectors. The operations the file system provides are:
create, open, read, write, lseek, close, unlink, truncate, rename, and stat. Everything else — buffering, blocking, allocation, caching, consistency — is the file system's responsibility.
Question 2
What is an inode, and what does it contain? Why is the file name not stored in the inode?
Show answer
An inode (index node) is the data structure that describes a file. It contains the file's metadata — owner UID and GID, permissions, size, timestamps (atime, mtime, ctime), link count, file type — and the pointers to the file's data blocks. The name is not stored in the inode because names are a property of the directory, not of the file: a single inode can be reached through multiple names (hard links), and the same name in different directories can refer to different inodes. Storing the name in the inode would make hard links impossible and would require a variable-length field inside the fixed-size inode structure.
Question 3
A file system uses 4 KB blocks and the inode has 12 direct pointers, one single-indirect pointer, one double-indirect pointer, and one triple-indirect pointer. With 4-byte block pointers, what is the maximum file size?
Show answer
Each indirect block holds 4096 / 4 = 1024 pointers.
- Direct: 12 × 4 KB = 48 KB
- Single-indirect: 1024 × 4 KB = 4 MB
- Double-indirect: 1024 × 1024 × 4 KB = 4 GB
- Triple-indirect: 10243 × 4 KB = 4 TB
Question 4
Explain the difference between a hard link and a symbolic link.
Show answer
A hard link is a directory entry that points to an existing inode. The inode's link count increases; the data is shared; the two names are indistinguishable. Removing one name decrements the link count but does not delete the data until the count reaches zero. Hard links cannot cross file system boundaries (the inode is local to one file system) and cannot be created for directories (which would create cycles). A symbolic link is a small file whose contents are the path to another file. It has its own inode and its own metadata. Following a symbolic link requires reading its contents and resolving the path; if the target is removed, the symbolic link becomes dangling. Symbolic links can cross file system boundaries and can point to directories.
Question 5
Compare contiguous, linked, and indexed file allocation. Which is best for sequential access, which for random access, and which is used by modern file systems?
Show answer
Contiguous: the file's blocks are consecutive on disk. Sequential access is optimal (one seek then a linear read); random access is also good. But external fragmentation and the difficulty of growing a file in place are serious problems. Linked: each block contains a pointer to the next. Sequential access is fine, but random access requires traversing the chain and is poor. Growth is easy. A single corrupted pointer truncates the file. Indexed: an index block holds the addresses of the data blocks. Random access is good; growth is easy; there is no external fragmentation; the cost is an extra block per file. Modern file systems use variations of indexed allocation: ext4 uses extents (contiguous runs of blocks, indexed by a B-tree), XFS uses B-trees of extents, and Btrfs and ZFS use copy-on-write B-trees of block pointers.
Question 6
A file system uses 1 KB blocks. A file is 100 KB in size. How many direct, single-indirect, and double-indirect blocks does it need? (Assume 4-byte pointers and 12 direct pointers.)
Show answer
Each indirect block holds 1024 / 4 = 256 pointers.
- The first 12 blocks are accessed through the direct pointers: 12 KB.
- The next 256 blocks are accessed through the single-indirect pointer: 256 KB.
- 100 KB is larger than 12 KB but smaller than 12 KB + 256 KB = 268 KB, so the file needs:
Question 7
Why does a directory need its own inode? What is stored in a directory?
Show answer
A directory is itself a file — a file whose contents map names to inode numbers — so it needs its own inode to store its metadata (permissions, owner, size, timestamps). The directory's contents are a sequence of entries, each of which contains a name and an inode number. The inode of the directory tells the file system where the directory's data blocks are; the data blocks hold the name-to-inode mappings. In ext4, the directory's data blocks are organised as a hash tree (htree) to make lookup fast; in older file systems, they are a linear list and lookup is O(n).
Question 8
What is journaling, and what problem does it solve?
Show answer
Journaling is a technique in which the file system writes metadata (and optionally data) to a log before applying the changes to the file system's structures. After a crash, the file system replays the log to bring the structures to a consistent state. It solves the problem that a crash during a multi-step update (for example, allocating a block, updating the inode, updating the free-block bitmap) can leave the file system in an inconsistent state. Without journaling, the system must run an
fsck pass over the entire volume, which can take hours on a large file system. With journaling, recovery is a matter of replaying the small tail of the log, which takes seconds.
Question 9
Describe the three journaling modes of ext4: data=journal, data=ordered, and data=writeback.
Show answer
data=journal: both metadata and data are written to the journal before being written to the file system. This is the strongest consistency guarantee — after a crash, both the metadata and the data are in a consistent state. It is also the slowest, because data is written twice (once to the journal, once to its final location).
data=ordered: only metadata is journaled, but data blocks are written to disk before the metadata that references them. This is the default for ext4. After a crash, the metadata is consistent and the data is present (it was written before the metadata). The cost is the write ordering, which slightly reduces throughput.
data=writeback: only metadata is journaled, and data may be written at any time. This is the fastest option, but after a crash the metadata may reference data blocks that were never written, so a file may contain stale or garbage data. The file system's structures are consistent, but the file's contents are not guaranteed.
Question 10
What is the difference between ext4's "extent" and the classical "block pointer" scheme? Why are extents better?
Show answer
A block pointer in a classical indexed file system records the address of a single data block. A file of 1 MB with 4 KB blocks requires 256 block pointers, and a large file requires many indirect blocks. An extent is a run of contiguous blocks, described by a starting block address and a length. A 1 MB file that is stored contiguously needs only one extent instead of 256 block pointers. Extents reduce the metadata overhead for large files and, because they describe contiguous runs, they allow the file system to read and write large sequential regions efficiently. If a file's blocks are not contiguous, multiple extents are used, but still fewer than one per block. The ext4 file system uses a B-tree of extents to manage files with many fragments.
Question 11
What is a copy-on-write file system, and how does it differ from a journaling file system?
Show answer
A copy-on-write file system (Btrfs, ZFS) never overwrites live data in place. Instead, when a block is modified, the new content is written to a fresh block, and the tree of pointers is updated to point at the new block; the old block is left untouched until the transaction commits, at which point the new tree becomes the live one and the old tree's blocks are freed. Atomicity is achieved by switching a single root pointer. Journaling, by contrast, writes metadata to a log before applying it to the file system's structures; the structures are updated in place, and the log is replayed after a crash to restore consistency. Copy-on-write avoids the consistency problem entirely — after a crash, the file system is either on the old tree or the new one, never a mix — and it makes snapshots cheap (a snapshot is just a copy of the root pointer). The cost is that writes are fragmented across fresh blocks, and file system management (garbage collection, space reclamation) is more complex.
Question 12
Why does a modern file system store checksums for data and metadata?
Show answer
Checksums (CRC32C in Btrfs, Fletcher-based in ZFS) allow the file system to detect corruption — whether from a failing disk, a firmware bug, or a cosmic ray. The checksum is stored separately from the data (in Btrfs, it is stored in a checksum tree keyed by the block's logical address), so a corrupted data block will fail its checksum verification when read. ZFS goes further: with RAID-Z, it can use the checksum to identify which copy is corrupted and reconstruct the correct data from parity. Without checksums, silent data corruption (a bit flip in a data block that the disk's own ECC did not catch) would go undetected, and the application would read corrupt data without knowing it. Checksums are one of the primary reliability features of modern file systems.
Question 13
What is the difference between a file's "atime", "mtime", and "ctime"? Which can be changed by a read?
Show answer
atime: the last access time — updated when the file is read (unless mounted with
noatime or relatime). mtime: the last modification time — updated when the file's contents are written. ctime: the last change time — updated when the file's metadata changes (permissions, owner, link count, size) or when the contents are written (which is a metadata change because the size and mtime are metadata). A read updates only atime. A write updates mtime and ctime. A chmod updates ctime only. The distinction matters for backup tools (which use mtime) and for forensic analysis (which uses all three).
Question 14
A file system's block size is 4 KB. What is the wasted space for a file of 1 byte? What about a file of 1 MB?
Show answer
A 1-byte file occupies one 4 KB block, so the wasted space (internal fragmentation) is 4095 bytes — 99.98% of the allocated block. A 1 MB file requires 256 blocks (assuming no extents), and if its size is exactly 1,048,576 bytes, no space is wasted; if it is 1,048,577 bytes, one more block is allocated and 4095 bytes are wasted. On average, a file wastes half a block, so 2 KB per file. On a file system with many small files, this internal fragmentation can be significant. The countermeasure is to use a smaller block size (at the cost of more block pointers and more metadata), or to pack small files together (as in the "tail packing" of ReiserFS, or the "inline data" feature of some file systems).
Question 15
What is the difference between a "block" in the file system sense and a "sector" in the device sense?
Show answer
A sector is the smallest unit the device can read or write — traditionally 512 bytes on hard disks, now commonly 4096 bytes on modern devices. A block is the file system's allocation unit, typically 4 KB or larger. The file system reads and writes whole blocks, and each block is composed of one or more device sectors. This distinction matters because the file system cannot update a single byte without reading the containing block, modifying the block in memory, and writing the block back. It also matters for alignment: if a file system block is not aligned to the device's sector size, a single block write may require two device reads and two device writes.
Question 16
In the ext2/3/4 file system, what is a "block group"? Why is the disk divided into groups?
Show answer
A block group is a contiguous region of the disk containing a copy of the superblock, a group descriptor, a block bitmap, an inode bitmap, an inode table, and data blocks. Dividing the disk into block groups improves performance because related metadata (a file's inode and its data blocks) is kept close together, reducing the head movement needed to access a file. The file system tries to allocate a file's inode and its data blocks in the same block group, and to allocate a directory's files in the same group. This locality is the central idea of the Fast File System (FFS) and it is why ext2 and its descendants outperform the original UNIX file system by a large margin on workloads with many small files.
Question 17
A program opens a file, reads 100 bytes, and closes it. List the file system structures that are accessed, in order.
Show answer
- The process's current directory entry is used to resolve the first component of the path (or the root is used if the path is absolute).
- For each path component, the directory's data blocks are read to find the name-to-inode mapping.
- The target file's inode is read from the inode table.
- The file's permissions are checked against the process's effective UID and GID.
- A file descriptor is allocated in the process's file descriptor table, pointing at an entry in the system-wide open file table, which points at the inode.
- On read, the file's data block (or blocks, if the read spans a block boundary) is read from disk (or from the page cache, if cached).
- On close, the file descriptor is freed; the inode's reference count is decremented; if it reaches zero and the link count is also zero, the inode and its data blocks are freed.
Question 18
What is an "orphan" inode, and how does the file system handle it?
Show answer
An orphan inode is an inode that is still open by some process but whose link count has dropped to zero — the file has been unlinked but is still in use. On UNIX-like systems, the inode is not freed until the last file descriptor referring to it is closed. The inode remains in the inode table (with link count 0) but its data blocks are not freed. When the last file descriptor is closed, the file system frees the inode and its blocks. This behaviour is what allows a program to create a temporary file, unlink it immediately, and continue to use it — the file exists only as long as the process holds it open. After a crash, the file system's recovery must clean up any orphan inodes that were open at the time of the crash: it scans the inode table for inodes with link count 0 and frees them.
Question 19
Why do modern file systems use B-trees for directory lookup?
Show answer
A directory with many entries — thousands or millions of files — cannot be searched linearly with acceptable performance. A linear search is O(n) per lookup, which is fine for small directories but becomes unusable for large ones. A B-tree (or, in ext4's case, an htree, which is a specialised B-tree) provides O(log n) lookup. The tree is indexed by a hash of the file name, and the search follows the tree from the root to a leaf containing the matching entry. The improvement is dramatic: a directory with 1,000,000 entries has a linear-search cost of ~500,000 comparisons on average, versus about 20 tree-node accesses for a B-tree. Modern file systems (ext4, XFS, Btrfs, ZFS) all use B-tree-based directories for this reason.
Question 20
What is a "sparse file", and how does the file system represent it?
Show answer
A sparse file is a file whose logical size is large but which contains large regions of zero bytes. The file system represents the zero regions by leaving the corresponding block pointers empty (a null pointer) rather than allocating data blocks. When the program reads from a null region, the file system returns zeros without reading from disk. A sparse file of 1 GB that contains only a few kilobytes of non-zero data at the beginning and end occupies only a few blocks on disk, even though its logical size is 1 GB. Sparse files are used for virtual-machine images, database files, and any application that needs to reserve a large amount of space but uses only a small part of it.
Question 21
Explain the difference between "blocking" and "non-blocking" I/O on a file descriptor. Which is the default?
Show answer
A blocking file descriptor causes a
read or write call to suspend the calling thread until the operation can complete (or the data is available). This is the default for file descriptors, and it is convenient for programs that expect to wait for their I/O. A non-blocking file descriptor (set with O_NONBLOCK) causes the call to return immediately with an error (EAGAIN or EWOULDBLOCK) if the operation cannot be completed. Non-blocking I/O is used with select or poll to multiplex many file descriptors in a single thread, which is the basis of event-driven servers (nginx, Node.js). It is also used with aio (asynchronous I/O) for high-performance applications.
Question 22
A file system is described as "log-structured". Explain the idea and describe one advantage and one disadvantage.
Show answer
A log-structured file system (LFS, and its descendant F2FS) writes all modifications as a sequential log: new data and new metadata are appended to the end of a circular log, and the file system's tree is updated to point at the new locations. The old locations become free and are reclaimed by a garbage collector that copies live data from partially occupied segments and erases the rest.
Advantage: sequential writes are the fastest kind of disk I/O, both on hard disks (no seek time) and on SSDs (no erase-before-write penalty). LFS also makes file system recovery fast: after a crash, the file system is reconstructed from the log, without the need for a full fsck.
Disadvantage: garbage collection adds overhead and can interfere with foreground writes. Write amplification (a logical write may trigger several physical writes because of GC) reduces the effective throughput, especially when the disk is nearly full. LFS is also less efficient for random reads, which must consult the tree to find the current location of each block.
Question 23
What is the difference between the file's "logical" size and its "physical" size? When do they differ?
Show answer
The logical size (also called the apparent size) is the number of bytes the file contains as seen by a program reading it. The physical size is the number of disk blocks the file actually occupies. They differ in three cases:
- Sparse files: the logical size includes the zero regions, which occupy no disk blocks.
- Internal fragmentation: the last block is partly unused, so the physical size is rounded up to a block boundary.
- Compression or deduplication: if the file system compresses or deduplicates data, the physical size may be smaller than the logical size.
stat reports the logical size in the size field and the physical size in the blocks field (in 512-byte sectors).
Question 24
In one or two sentences, state the central design problem of a file system and how journaling and copy-on-write each address it.
Show answer
The central design problem is that a single logical operation (creating a file, appending data) requires updating several on-disk structures, and a crash part-way through leaves the structures inconsistent. Journaling solves the problem by recording the intended changes in a log before applying them, so that after a crash the changes can be replayed or discarded as a unit. Copy-on-write solves it by never modifying live data in place — a new version of each block is written to a fresh location and a single atomic pointer update makes the new version live, so a crash leaves either the old or the new state, never a mix.
Ready for the graded quiz?
Once you are comfortable with every question above, take the graded Unit 10 quiz in the LMS. It covers the same material with multiple-choice questions, inode-size calculations, and a file-system-layout exercise.