File systems: organisation, directories and allocation
Clear, exam-focused notes on file-system organisation: files, directories, allocation methods (contiguous, linked, indexed, FAT, extents), free-space management and directory implementation, with formulas and worked examples.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
File systems are how an operating system stores and organises persistent data on disks and SSDs. An engineer uses this when designing OS storage layers, choosing allocation strategies for performance and reliability, or debugging storage-related bugs in systems like ext, NTFS or FAT.
Key ideas
- Block (or disk block) — the minimum unit of allocation on disk. Typical file-system block/cluster sizes are 1 KB, 2 KB, 4 KB (up to 64 KB on some systems); 512 B is a historical sector size. Files occupy an integer number of blocks (also called clusters in FAT/NTFS); some file systems support sub-block fragments or tail packing.
- Directory — a data structure that maps filenames to file-identifiers (inode numbers, FAT entries). Common organisations include single-level, two-level, and tree-structured directories; links may be hard (multiple directory entries to one inode) or symbolic (a special file pointing by path); implementations include linear lists, hashed directories, and B-tree variants.
- Inode (index node) — a fixed-size record storing file metadata (size, timestamps, ownership, pointers to blocks). Used by UNIX-like file systems.
- Free-space management — how the file system tracks which blocks are free: free list (linked), free bitmap, grouping, or counting.
- Allocation methods (how file blocks are placed on disk):
- Contiguous allocation: each file occupies a sequence of contiguous blocks. Advantages: simple, fast sequential and random access. Disadvantages: external fragmentation, file-size growth difficulty. Draw diagram: a horizontal strip of blocks; label a contiguous run from block s to block s+L-1 as file F.
- Linked allocation: file is a linked list of disk blocks; each block contains data and a pointer to the next block. Advantages: no external fragmentation, easy growth. Disadvantages: poor random access (must follow pointers), pointer overhead. Draw diagram: separate boxes for blocks with arrow pointers.
- Indexed allocation: each file has an index block (or inode) containing pointers to all its data blocks (direct pointers) and optionally pointers to indirect blocks (single/double/triple indirect). Advantages: constant-time random access (with index cached); no external fragmentation. Disadvantages: index block overhead and complexity.
- FAT (File Allocation Table): a table (kept in memory and on disk) where each entry corresponds to a block and contains the index of the next block. It is like a global linked list. Fast sequential but table size grows with disk size and random access remains O(n) because chains must be traversed.
- Extents: store ranges (start,length) instead of single-block pointers; reduces metadata for large contiguous regions, used in modern file systems (ext4, XFS).
Exact definitions and properties universities expect:
- Definition (Contiguous allocation): A file of size S bytes that uses block size B occupies N = ceil(S/B) contiguous blocks from some starting block s to s+N-1. Assumes blocks are fixed size and allocation requires finding a free contiguous run.
- Definition (Internal fragmentation): Wasted space inside allocated blocks because the file does not fill the last block. For a random file size distribution uniform over block boundaries, average internal fragmentation = B/2.
- Definition (External fragmentation): Free space is available in total but split into small non-contiguous holes such that a request for a contiguous region fails.
- Complexity claims often asked:
- Contiguous: sequential read O(1) per block using simple arithmetic; random access O(1) (compute block number: s + offset/B) assuming starting block known.
- Linked: sequential read O(1) per block following pointer; random access O(k) to reach k-th block.
- Indexed: random access O(1) once index is read; if multi-level indirect, extra O(level) disk accesses unless cached.
Diagram instructions (draw by hand in exams):
- Disk layout diagram: draw a large rectangle divided horizontally into regions. Label from left to right: Boot block (optional), Superblock (contains FS metadata), Inode table (array of inodes), Free-space bitmap or FAT, Data blocks. For inodes, draw one inode expanded to show fields: mode, owner, size, timestamps, direct pointers (array), single-indirect pointer, double-indirect pointer, triple-indirect pointer.
Formulas
N = ceil(S / B) — number of blocks required
- S = file size in bytes, B = block size in bytes. Applies for fixed-block allocation.
Internal_fragmentation_avg = B / 2 — average bytes wasted per file
- B in bytes. Assumes uniform distribution of file final fragment over [0, B).
p = floor(B / Psize) — pointers per block for indirect blocks
- B = block size in bytes, Psize = pointer size in bytes (e.g. 4). Unitless.
MaxSize = B * (Nd + p + p^2 + ... up to levels) — for indexed allocation with Nd direct pointers and multi-level indirects
- B = block size (bytes), Nd = number of direct pointers, p = pointers per block. Sum terms for direct, single-indirect (p), double-indirect (p^2), etc.
Free_space_percentage = (free_blocks / total_blocks) * 100% — when doing free-space accounting.
(Units: bytes for sizes. Use bytes, KB, MB as multiples of 1024 unless the question specifies SI decimal. Prefer IEC binary prefixes (KiB, MiB, GiB, TiB) in answers to avoid ambiguity.)
Worked examples
Example 1 — Blocks needed and internal fragmentation Given: file size S = 100000 bytes, block size B = 4096 bytes.
- Formula:
N = ceil(S / B). - Compute: S/B = 100000 / 4096 = 24.4140625 → N = 25 blocks.
- Allocated space = N * B = 25 * 4096 = 102400 bytes.
- Internal fragmentation = 102400 − 100000 = 2400 bytes. Final answer: 25 blocks, 102400 B allocated, 2400 B wasted.
Example 2 — Maximum file size for UNIX inode design Assume: block size B = 4096 B, pointer size Psize = 4 B, inode has Nd = 12 direct pointers, and single/double/triple indirect pointers.
- p = B / Psize = 4096 / 4 = 1024 pointers per indirect block.
- Direct data = Nd * B = 12 * 4096 = 49152 B.
- Single indirect = p * B = 1024 * 4096 = 4,194,304 B.
- Double indirect = p^2 * B = 1024^2 * 4096 = 4,294,967,296 B.
- Triple indirect = p^3 * B = 1024^3 * 4096 = 4,398,046,511,104 B.
- Sum = 4,402,345,721,856 B ≈ 4.0039 TiB (≈ 4,100 GiB). Final answer: ≈ 4.402 × 10^12 bytes ≈ 4.004 TiB.
Example 3 — Short model answer comparing allocation methods (exam style) Question: Compare contiguous, linked and indexed allocation for files. Give advantages and disadvantages and state where each is used. Model answer (points to include): define each method; state pros (contiguous: fast sequential and random, simple), cons (external fragmentation, difficult grows), typical use (simple file systems, boot partitions); linked: pros (no external fragmentation, easy grow), cons (random access slow, pointer overhead), typical use (FAT is a variant), indexed: pros (fast random access, supports sparse files), cons (index block overhead), typical use (UNIX inodes). Add complexity notes: contiguous random access O(1), linked random access O(n), indexed O(1) with cached index.
Common mistakes
- Using pointer size 8 B (64-bit) without stating the assumption; exam answers must state pointer size.
- Mixing units (KB as 1000 vs 1024) without saying which convention is used.
- Saying indexed allocation always gives O(1) access without mentioning cache: multi-level indirects cost extra disk reads if index not cached.
- Mixing inode (metadata structure) with directory (name-to-inode mapping).
For your exam
Question types you will see: definitions (define file, inode, directory, extent), short notes (compare allocation methods), derivations (derive formula for maximum file size with multi-level indirects), numericals (compute blocks used, internal fragmentation, max file size), diagrams (draw disk layout and inode with pointers), design/compare (choose allocation for given workload), small programs rarely asked here.
What a full-marks answer includes:
- Clear definitions of terms used (file, block, inode) exactly as above.
- Assumptions stated (block size, pointer size, units).
- Correct step-by-step derivation with formulas and arithmetic, carrying units.
- Diagrams drawn and labelled when asked (disk regions, inode fields, pointer structure).
- Conclusions comparing performance trade-offs and use-cases.
Quick check
- What is the average internal fragmentation per file for block size 4096 B?
- For block size 1024 B and pointer size 4 B, how many pointers fit in one indirect block?
- In linked allocation, is random access O(1) or O(n)? Answers: 1) 2048 B. 2) 256 pointers. 3) O(n) — you must follow pointers.
Note for reviewer: I stated typical numbers (block size 4096 B, pointer size 4 B) when doing worked examples; please check conventions used by the target universities. I am unsure about whether to prefer decimal (1000) or binary (1024) prefixes for KB/MB in some exam contexts — I used powers of 1024 (KiB) in calculations above. Also verify whether pointer size 4 B is acceptable as an exam assumption for all target courses; if some courses expect 8 B, numbers change.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?