Chapter 12: File-System Implementation¶

File-System Structure¶

A file system is typically stored on disk using a layered structure:

Boot Block Contains code to boot the OS.
Superblock / File-System Control Block Holds metadata: size, number of blocks, free space, and layout.
Inode Table / File-Control Blocks (FCBs) Stores per-file metadata.
Data Blocks Contain actual file data.
Directory Structure Maps file names to inodes/FCBs.

The OS uses in-memory structures such as caches, directory caches, buffer caches, and file tables to improve performance.

Allocation Methods¶

Contiguous Allocation¶

Description: Files occupy a contiguous range of blocks.
Advantages: - Fast sequential and direct access. - Simple to implement.
Disadvantages: - External fragmentation. - Hard to grow files dynamically.

Linked Allocation¶

Description: Each block stores a pointer to the next block.
Advantages: - No external fragmentation. - Easy file growth.
Disadvantages: - No efficient direct access. - Reliability issues (pointer corruption).

Indexed Allocation¶

Description: An index block contains all pointers to the file’s blocks.
Advantages: - Supports direct access. - Avoids external fragmentation.
Disadvantages: - Index block must be large enough. - For big files, may need multilevel indexing (e.g., UNIX inodes).

Free-Space Management¶

Techniques used to track unused blocks:

Bitmaps (Bit Vectors)¶

Each block represented by 1 (free) or 0 (allocated).
Advantages: Compact, fast to search.
Disadvantages: Bitmap must be held in memory for efficiency.

Free Lists (Linked Lists)¶

Free blocks linked together.
Advantages: Simple.
Disadvantages: Slow for large file systems.

Grouping¶

First free block stores addresses of several free blocks.
Reduces traversal overhead.

Counting¶

Tracks free blocks in runs (start block + count).
Efficient for systems with contiguous free space.

Space Maps¶

Used in advanced file systems such as ZFS.
Log-structured metadata for efficient free space tracking.