Defragmentation and File-System Summary
Defragmentation
Fragmentation in a file system occurs when a file’s blocks are scattered across the disk rather than being contiguous. This happens naturally over time as files are created, extended, and deleted, leaving gaps that are filled by pieces of other files.
External fragmentation at the file-system level means the free space is broken into small pieces; allocating a new large file may require it to be fragmented across many scattered free blocks.
Internal fragmentation occurs within a block: if a file is 4.1 KB and the block size is 4 KB, the last block wastes 3.9 KB (or ~2 KB on average).
Defragmentation strategies
| Strategy | How it works |
|---|---|
| Online defrag | A background process (defrag on Windows, e4defrag on Linux ext4) identifies fragmented files and attempts to relocate their blocks to contiguous regions of free space. Runs while the file system is mounted and in use. |
| Offline defrag | Dump the file system to tape/backup, recreate it, restore the data. All files are contiguous. Requires unmounting and downtime. |
| Copy-on-write file systems (ZFS, Btrfs) | Never overwrite data in place — always write to new locations. This inherently prevents fragmentation for writes (which are always to fresh, contiguous space) but can lead to fragmentation over time as snapshots and overwrites accumulate. |
Defragmentation and the idle process
A classic Tripos question (2022 Q4(c)) asks why the “idle process” (the process that runs when no other process wants the CPU) might be a good place to put defragmentation work. The answer:
- The idle process runs when the CPU would otherwise be wasted. Defragmentation is CPU-intensive (scanning bitmaps, moving blocks), so scheduling it during idle time improves system utilisation without affecting user processes.
- However: if the idle process does disk I/O (to relocate blocks), it may delay a user process’s subsequent I/O request if the disk is shared. So the idle process should do the planning (scanning, identifying fragments) but defer the actual I/O to a kernel thread that can be throttled.
File-system summary
| Concept | Key points |
|---|---|
| File abstraction | Named, persistent byte array; directory maps names to inode numbers |
| Inode | Stores metadata (permissions, timestamps, block pointers); not the name |
| Hard links | Multiple names for same inode; equal status |
| Symbolic links | A file containing a path string; can dangle, cross file systems |
| Free-space management | Bitmap (common) or linked list |
| Journaling | Logs pending changes for fast crash recovery |
| LFS | Append-only log; optimised for writes; requires cleaner |
| Defragmentation | Reordering blocks for contiguity; can be done by idle process |
Summary
- File systems fragment naturally over time as files are created and deleted.
- Defragmentation restores contiguity; can run in the background or offline.
- The idle process is a natural home for defragmentation planning work.
- Journaling and LFS represent different approaches to the performance-reliability trade-off in file-system design.