File System Implementation

A Visual Guide aligned with Silberschatz & GeeksforGeeks Data

1. Layered File System Design

Application Programs

User interface, high-level APIs (fopen, fread).

Logical File System

Manages Metadata. Maintains File Control Blocks (FCB). Responsible for protection & security.

File-Organization Module

Maps logical block addresses (0..N) to physical block addresses. Manages free space.

Basic File System

Issues generic commands (read drive 1, cylinder 72) to device drivers. Manages buffers & caches.

I/O Control

Device drivers & Interrupt handlers. Translates high-level commands to hardware instructions.

Devices

Physical Hardware (HDD, SSD, Optical Disk)

2. Key Data Structures

How the OS maintains state on the disk versus in RAM.

💾 On-Disk Structures

Stored persistently on secondary storage.

  • Boot Control Block
    Contains info needed to boot the OS from the volume (e.g., Boot Sector in NTFS, Boot Block in UFS).
  • Volume Control Block
    Total blocks, free block count, block size. (e.g., Superblock in UFS, Master File Table in NTFS).
  • Directory Structure
    Organizes files (names, inode numbers).
  • File Control Block (FCB)
    Contains details: permissions, ownership, size, location of data blocks. (e.g., Inode in Unix).

⚡ In-Memory Structures

Loaded into RAM during file system operations.

  • Mount Table
    Info about each mounted volume/partition.
  • Directory-Structure Cache
    Holds directory info of recently accessed directories for speed.
  • System-Wide Open-File Table
    Contains a copy of the FCB for every currently open file.
  • Per-Process Open-File Table
    Pointers to the system-wide table + current file offset (read/write pointer).

3. File Allocation Methods

Contiguous Allocation

Each file occupies a set of contiguous blocks.

[Block 0] [Block 1] [Block 2] ...

Pros: Excellent for sequential & direct access. Simple.

Cons: External fragmentation. File growth is difficult.

Linked Allocation

Each file is a linked list of disk blocks. Blocks can be scattered.

[Block 5 -> 12] ... [Block 12 -> 9] ...

Pros: No external fragmentation. Easy file growth.

Cons: Slow random access (must traverse list). Pointer overhead.

Indexed Allocation

Prings all pointers together into one index block.

[Index Block] -> {Blk 1, Blk 5, Blk 2}

Pros: Supports direct access. No external fragmentation.

Cons: Wasted space for small files (overhead of index block).

4. Directory Implementation

Linear List

A list of filenames with pointers to data blocks.

  • Algorithm: Linear Search to find a file.
  • Pros: Simple to program.
  • Cons: Slow execution time for large directories.

Hash Table

Linear list with a hash data structure.

  • Algorithm: Hash(filename) -> index.
  • Pros: Fast directory search time.
  • Cons: Collision handling needed; Fixed size issues.

5. Free Space & Recovery

Free Space Management

  • Bit Vector: 1 bit per block (1 = free, 0 = allocated). Simple but requires hardware support for efficiency.
  • Linked List: Link together all free disk blocks. Low space waste, but traversing is slow.
  • Grouping: Store addresses of n free blocks in the first free block.
  • Counting: Store address of first free block and the count of following contiguous free blocks.

Recovery & Journaling

  • Consistency Checking: Compares data in directory structure with data blocks on disk (e.g., fsck).
  • Log-Structured (Journaling): Records updates to a log before applying them.
  • Benefit: Faster recovery after crashes; no need to scan entire disk.