File Systems: Structure, Allocation & Management

TAKEAWAYS:

• Files are organized hierarchically in directories and stored using allocation methods like contiguous, linked, or indexed allocation.
• Directory structures (flat, single-level, tree, graph) enable efficient file retrieval and management.
• File systems optimize performance using techniques like caching, buffering, and indexing.
• Metadata (file attributes, permissions, timestamps) is critical for file management and security.
• RAID (Redundant Array of Independent Disks) improves disk reliability and performance.
• File systems like FAT32, NTFS, ext4, and Btrfs use different allocation and error-handling strategies.

1. Introduction to File Systems

A file system is an organized way to store, retrieve, and manage files on secondary storage devices (e.g., hard disks, SSDs). It defines:

• How data is physically stored (e.g., contiguous blocks, linked lists).
• How files are named, organized, and accessed (e.g., directories, metadata).
• How permissions and security are enforced.
• How errors and failures are handled (e.g., checksums, journaling).

Key Components of a File System

mindmap
  root((File System))
    - Physical Storage
      - Disk Partitions
      - Block Allocation
    - Logical Structure
      - Files
      - Directories
    - Metadata
      - File Attributes (name, size, type)
      - Permissions (read/write/execute)
      - Timestamps (creation, modification)
    - System Components
      - File Control Block (FCB)
      - Directory Structure
      - Allocation Methods

2. File Types and Access Methods

Files can be classified based on their content and access patterns:

Access Methods

• Sequential Access: Data is read/written in order (e.g., tape drives).
• Random Access: Direct access to any block (e.g., hard disks).
• Direct Access: Uses a formula to compute block location (e.g., indexed files).

3. File Allocation Methods

Files are stored on disk using different allocation strategies:

(A) Contiguous Allocation

• A file occupies a single contiguous block of disk space.
• Advantages:
  • Fast sequential access (no pointer chasing).
  • Simple to implement.
• Disadvantages:
  • External fragmentation (wasted space due to unused contiguous blocks).
  • Difficult to resize files.

Disk: [File1][Free][File2][Free][File3][Free]

• Example: A 100 MB video file stored in one contiguous block.

(B) Linked Allocation

• Each block of the file points to the next block (using pointers).
• Advantages:
  • No external fragmentation.
  • Easy to grow/shrink files.
• Disadvantages:
  • Slow random access (must traverse pointers).
  • Reliability issue: If one pointer is lost, the file becomes corrupted.

Block1 → Block2 → Block3 → ... → BlockN

• Example: A large log file where each log entry is stored in a separate block linked sequentially.

(C) Indexed Allocation

• A separate index block contains pointers to all data blocks.
• Advantages:
  • Fast random access (via index).
  • No external fragmentation.
• Disadvantages:
  • Index block can become large (overhead).
  • Single point of failure (if index is lost, file is lost).

Index Block: [Block1][Block2][Block3]
Data Blocks: [Data1][Data2][Data3]

• Example: A database where each record’s location is stored in an index (like a phonebook).

(D) Hybrid Allocation (e.g., FAT32, NTFS)

• Combines contiguous allocation for small files and indexed allocation for large files.
• Example: Windows NTFS uses a Master File Table (MFT) to track file locations.

4. Directory Structures

Directories organize files hierarchically. Common structures:

Directory Entry Example

Each directory entry contains:

• File name
• File type (text, binary, etc.)
• File size
• Location (first block, index block)
• Permissions (read/write/execute)
• Timestamps (creation, modification)

+---------------------+
| File Name: "report.txt" |
+---------------------+
| File Type: Text      |
+---------------------+
| Size: 1024 bytes     |
+---------------------+
| First Block: 50     |
+---------------------+
| Permissions: rw-r--r-- |
+---------------------+

5. File System Performance Optimization

(A) Caching and Buffering

• Frequently accessed files are kept in RAM (cache) for faster access.
• Example: When you open a file in Notepad, it loads into memory before displaying.

(B) Indexing

• Creates an inverted index (like a database) for fast searches.
• Example: Search engines use indexing to find web pages quickly.

(C) RAID (Redundant Array of Independent Disks)

• Combines multiple disks for faster access and redundancy.
• RAID Levels:
  • RAID 0: Striping (no redundancy, faster).
  • RAID 1: Mirroring (duplicate data, fault-tolerant).
  • RAID 5: Striping + parity (fault-tolerant, good performance).

Disk1: [Data][Data][Data]
Disk2: [Data][Data][Data]

Example: NTC’s data centers use RAID for high availability.

6. Metadata and File Control Block (FCB)

• Metadata includes:
  • File name, size, type.
  • Owner, permissions (chmod in Linux).
  • Timestamps (mtime, atime, ctime).
• File Control Block (FCB) stores metadata and allocation info.
• Example: In Linux, metadata is stored in the inode table.

+---------------------+
| File Name: "data.bin" |
+---------------------+
| Size: 512 KB         |
+---------------------+
| Owner: User1         |
+---------------------+
| Permissions: 755     |
+---------------------+
| Allocation: Indexed |
+---------------------+

7. File System Implementation

(A) Boot Block

• Contains code to load the OS into memory.
• Example: GRUB (Linux bootloader).

(B) Superblock

• Stores global file system info (total blocks, free blocks, etc.).
• Example: In ext4, the superblock is at offset 1024.

(C) Allocation Table (e.g., FAT32)

• Tracks which blocks are free/used.
• Example: Windows uses FAT32 for older drives.

(D) Data Blocks

• Actual file storage.

+---------------------+---------------------+---------------------+
| Boot Block          | Superblock          | Allocation Table    |
+---------------------+---------------------+---------------------+
| Data Block 1        | Data Block 2        | ...                 |
+---------------------+---------------------+---------------------+

8. Real-World Applications

## In the real world

1. eSewa & Khalti (Mobile Wallets)

   • Idea: File systems store transaction logs in databases (e.g., MySQL, PostgreSQL).
   • How: Every payment is logged as a binary file with metadata (timestamp, amount, user ID).
   • Example: When you transfer ₹1000 via eSewa, the transaction is written to a sequential log file for auditing.

2. Daraz (E-commerce)

   • Idea: Indexed allocation for product catalogs.
   • How: Daraz uses a database (MySQL/NoSQL) where each product’s location is stored in an index for fast retrieval.
   • Worked Example:
     • A user searches for "iPhone 15".
     • The system indexes product IDs → directly accesses the relevant block.
     • Time saved: No scanning entire disk (unlike linked allocation).

3. NTC & Ncell (Telecom)

   • Idea: RAID for call records.
   • How: Telecom companies store bill data on RAID 5 disks for:
     • Fault tolerance (if one disk fails, data is recovered).
     • Fast access (billing systems need low latency).
   • Example: When you check your Ncell bill, the system reads from a RAID array in milliseconds.

9. Worked Example: File Allocation Table (FAT) Calculation

Problem: A 500 GB hard drive has a block size of 5 KB. Calculate the size of the File Allocation Table (FAT) if each entry is 4 bytes.

Solution:

1. Convert disk size to blocks:

   • Total disk space = 500 GB = $500\times 1024\times 1024\times 1024$ bytes.
   • Block size = 5 KB = $5\times 1024$ bytes.
   • Total blocks = $\frac{500\times 1024^3}{5\times 1024}=500\times 1024^2$.

2. Calculate FAT size:

   • Each FAT entry = 4 bytes.
   • Total FAT size = $500\times 1024^2\times 4$ bytes.
   • Simplify: $500\times 1024^2\times 4=2000\times 1024^2$ bytes ≈ 2 GB.

Answer: The FAT will require ~2 GB of storage.

10. Comparison Table: Allocation Methods

11. Exam Tip

• Focus on:
  • File allocation methods (contiguous, linked, indexed) and their trade-offs.
  • Directory structures (tree vs. graph) and how they affect performance.
  • FAT/NTFS vs. ext4 (real-world examples).
  • RAID levels (0, 1, 5) and their use cases.
• Common Exam Questions:
  • "Calculate FAT size given disk capacity and block size."
  • "Explain how indexed allocation improves random access."
  • "Compare contiguous and linked allocation in terms of fragmentation."
• Diagrams to Draw:
  • File system layout (boot block, superblock, data blocks).
  • Linked allocation (chain of blocks).
  • RAID 1 vs. RAID 5 (mirroring vs. striping + parity).